Disk optimized paging for column oriented databases

Implementing a database system using a plurality of sequentially ordered drives to store sequential portions of columns of the database, but where the database system is usable by a system configured for use with in-memory database systems. The method includes loading one or more columns of a database into main memory of a computing system as a table based database. The method further includes dividing a column of the database into sequential portions. Each of the sequential portions is of sufficient size to create efficient transfers using hard disk controllers to transfer an entire sequential portion. The method further includes writing each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion such that sequential portions of the column are on sequential drives.

BACKGROUND

Background and Relevant Art

Further, computing system functionality can be enhanced by a computing systems ability to be interconnected to other computing systems via network connections. Network connections may include, but are not limited to, connections via wired or wireless Ethernet, cellular connections, or even computer to computer connections through serial, parallel, USB, or other connections. The connections allow a computing system to access services at other computing systems and to quickly and efficiently receive application data from other computing system.

Interconnection of computing systems has facilitated distributed computing systems, such as so-called “cloud” computing systems. In this description, “cloud computing” may be systems or resources for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, services, etc.) that can be provisioned and released with reduced management effort or service provider interaction. A cloud model can be composed of various characteristics (e.g., on-demand self-service, broad network access, resource pooling, rapid elasticity, measured service, etc), service models (e.g., Software as a Service (“SaaS”), Platform as a Service (“PaaS”), Infrastructure as a Service (“IaaS”), and deployment models (e.g., private cloud, community cloud, public cloud, hybrid cloud, etc.).

Cloud and remote based service applications are prevalent. Such applications are hosted on public and private remote systems such as clouds and usually offer a set of web based services for communicating back and forth with clients.

Some such systems implement distributed database systems. However, some of these distributed database systems, such as Microsoft Analysis Services available from Microsoft Corporation of Redmond, Wash., implemented in tabular mode require all data in the database to be loaded into main memory. However, in many current systems, this limits the size of the database to 120 GB. To expand the size of the database, a hard drive may be used. However, this comes with a performance hit. In particular, a nave memory-mapped file or paging file approach will have, even on SSDs, a performance degradation of 3 orders of magnitude, as the IOs are too small and not numerous enough to pose a significant enough load on the SSD controller.

BRIEF SUMMARY

One embodiment illustrated herein includes a method that may be practiced in a computing environment. The method includes acts for implementing a database system using a plurality of sequentially ordered drives to store sequential portions of columns of the database, but where the database system is usable by a system configured for use with in-memory database systems. The method includes loading one or more columns of a database into main memory of a computing system as a table based database. The method further includes dividing a column of the database into sequential portions. Each of the sequential portions is of sufficient size to create efficient transfers using hard disk controllers to transfer an entire sequential portion. The method further includes writing each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion such that sequential portions of the column are on sequential drives.

DETAILED DESCRIPTION

Some embodiments described herein implement a database system using hard drives, such as solid state drives (SSDs) that will work well for column-oriented in-memory databases without changing much the in-memory architecture. Embodiments use a new, generation-based caching system that allows keeping essentially the same architecture as in-memory systems without sacrificing significant amounts of speed. In particular, by using a sequentially ordered series of different drives to sequentially store different segments, and by reading sufficiently large amounts of data into each drive to optimize drive controller reads, embodiments can achieve the maximum throughput of the drive rather than being limited by the number of Input/Output Operations per Second (IOPS) for the drives. This allows embodiments to keep the same or substantially similar memory specific speeds by having an architecture that allows combining paging and scaling the database out.

The improved system is implemented in a fashion that makes drives look, and in many cases, perform, like memory so that the architecture does not need to be drastically modified so that current performance characteristics are maintained. To accomplish this, embodiments may implement any or all of the following functionality: paging in full segments (which may be required by the column-oriented query engine) into a drive; using a buffer pool in which memory is allocated circularly (to avoid the overhead of “real” memory allocation); adjusting the scale-out algorithm to keep the same memory bandwidth as the original in-memory system; using a read-ahead of one segment to keep the data as warm as possible without exceeding the bufferpool.

In considering how to reduce costs for in-memory database systems, the following factors may be relevant:

SSD throughputs are good, and are approaching memory throughputs (500+MBs for SATA3 SSDs and 1500+MBs for PCIe SSD boards).

SSDs are cheap (presently, typically $0.8 GB up to $2 GB).

Memory is also cheap.

Machines that can accommodate large amounts of memory (e.g. 2 TB) come in expensive form factors.

Machines that can accommodate similar amounts of SSD storage space can be implemented in much less expensive form factors. For example, a typical Windows Azure™ compute node available from Microsoft Corporation of Redmond Wash. will have 120 GB of (usable) RAM but 2.4 TB of SSD storage.

In the example above, the machine can generally accommodate two orders of magnitude more SSD (or other disk) storage than memory, while the performance of memory is only within one order of the SSD speed. Furthermore, a machine may be implemented with a set of SSDs rather than a single SSD, and striping the access across the disks could result in a significant improvement over the performance of a single SSD.

The following illustrates experimental results validating the effectiveness of some of the embodiments described herein. The experiment was run on a (standard developer) Z420 machine with 1 processor E5-1650 @3.2 GHz, 24 GB RAM system available from Hewlett Packard Corporation of Palo Alto, Calif. The stock machine was equipped with a 2 TB SATA (rotational) disk with modest performance. Four 240 GB of OCZ RevoDrive 3 X2 drives were added. These are SSD boards that can be coupled on the PCIe interface and can deliver up to 1.5 GB/sec.

The simulated workload was characterized by a moderate number of large IOs (i.e. high 100 kBs to a few MBs). The results are presented in the table below:

As can be observed from the preceding experiment, as long as the physical bus permits, embodiments can achieve an acceptable bandwidth of the SSD hardware with a workload that might be implemented in a desired database system. Also, to achieve higher performance, a custom RAID0 system can be implemented rather than simply using an off the shelf RAID0 system. Further, performance is better if large IOs (i.e. IOs that are of significant size in comparison to drive controller capabilities) are performed at the SSDs, even if smaller queue depths are employed. For example, in many modern SSD drives or drive cards, there may be a desire to reach data transfer that approximates the specified throughput of the drive. Small reads from the drives will not approach these throughputs; however, large reads may. Thus, performing a group of 10×1 MB reads would result in a 10 MB read from a drive which would saturate the controller and cause the disk to perform at or near its specified throughput that is identified in the disk specification. Thus, disk reads, in some embodiments, may be some value above about 4 MB. However, reasonable performance can be achieved when reads are above 500 KB.

In implementing embodiments herein, several factors may contribute to the design. It is desirable to implement some embodiments with minimal changes compared to in-memory database systems. This may be important to protect the stability of a system as a whole which incorporates the database system into it.

Embodiments may implement disk paging into memory on top of a distributed on-disk caching structure. This allows for other portions of the system, such as storage, to remain the same. As illustrated below, embodiments create a caching structure on load and operate with the caching structure at query time.

When paging in, embodiments could choose to operate either with fixed size pages or with segments. A typical representative system in which the database may be used may have 16 processor cores, for a typical representative query involving about 6 columns that would need to be paged in such that in a cold page in, about 100 column segments would be paged in. Better performance can be achieved in some embodiments if whole segments will be paged in rather than individual pages. In particular, for some systems to work unmodified, a whole segment has to be available when the query starts. Thus, it may be more efficient to page in a whole segment. Further, issuing between high tens to low hundreds of larger outstanding IOs across multiple disks is more efficient than issuing thousands or 10 s of thousands of smaller IOs. Additionally, paging in whole segments has also the advantage that the processing code stays largely unmodified. Embodiments that page in pages will need to make sure that runs get split (artificially) at page boundaries, which is a significant change in the processing pipeline

As the sizes of the segments are large (up to 32 MB and typically around 2-4 MB, assuming a 10-15× compression ratio), embodiments may not be able to allocate system memory with each page-in operation, as it would delegate to expensive allocation procedures. Thus, as illustrated below, embodiments implement a buffer pool. To deal with fragmentation and different allocation sizes, embodiments may implement a ring buffer pool, as illustrated below, that operates in a circular fashion using pointers to keep track of free portions of the buffer pool rather than using fixed page sizes.

Further, some embodiments only page the data files of the subsegments, not the RLE runs, dictionaries, hierarchies, metadata, etc. This may be done as an optimization when paging dictionaries and hierarchies results in large amounts of work that will cause instability in the system.

Referring now toFIG. 1A, an example implementation is illustrated. In the example illustrated, data can be stored in cloud storage102. For example, the cloud storage may be implemented using an Azure Blob Store available in Windows Azure™ system. Portions of data from the cloud storage102can be cached locally at a service104in a local database cache106. Initially, portions of data from the local database cache106can be read into main memory into a table108. From the table108in main memory, the data is scattered out to available drives at a segment level. A segment, as used herein, is a predetermined number of rows in a table. In some embodiments, a segment size may be a default of 8 million rows. However, this size is configurable and in some embodiments, not all segments are the same size. Rather, some embodiments allow for segments to be of different sizes. Returning now to the present example, the system104includes four drives110-1through110-4. Four drives are illustrated in the example, but it should be appreciated that a different number of drives could be used in other embodiments.

When a model loads, data goes to the main memory only to be scattered at the segment level onto the n (in the illustrated example, n=4) SSD cache drives available. Then, the memory in the segment is freed and the segment remembers a handle (that a paging module can interpret appropriately) that has in the underlying structure, among other things, the file and offset for the data to be paged in.

When the data is paged out to the drives, embodiments create one file per column partition per drive location. Note that the file, in this particular embodiment, is per column, and not per segment. Thus, a given file may store several segments from a column. Illustratively,FIG. 1Aillustrates that each of the drives110-1through110-4includes one file for each column in the table110. For example, inFIG. 1A, a file112-1-1is included in the drive110-1for column C1in the table108. A file112-2-1in included in the drive110-2for column C1in the table108. A file112-3-1in included in the drive110-3for column C1in the table108. A file112-4-1in included in the drive110-4for column C1in the table108.FIG. 1Aalso illustrates files112-1-2,112-1-3and112-1-4for columns C2, C3, and C4in the table108respectively. Similar files are included in drives110-2,110-3and110-4for those columns as well.

As segments are loaded, they are cached out to the n locations (again, in the illustrated example, n=4). Assuming N segments, for each column partition, there are n files, each with about Nn segments. The shuffling of the segments is round robin, in order to achieve parallelism during querying. For example, as illustrated in the example ofFIG. 1A, there are 5 segments for each column. Using the round-robin paging out, the file112-1-1stores segment51from column C1. The file112-2-1stores segment S2from column C1. The file112-3-1stores segment S3from column C1. The file112-4-1stores segment S4from column C1. The round robin algorithm continues and circles around such that the file112-1-1stores segment S5from column C1. Similar actions are performed for the remaining columns in the table108, but with different files at each drive for each different column. For example,FIG. 1Aillustrates file112-1-2for column C2in the table108. Various other files are evident inFIG. 1Afor the different columns and different drives.

An engine114can be implemented at the service104to handle the paging in/out. Additionally, as illustrated below, the engine114can handle overlapped IOs, buffer pool management and buffer pool caches.

When the server104starts, it also allocates a buffer pool116. The buffer pool116is global per server. The size of the buffer pool116is configured according to pre-defined initialization settings. In some embodiments, a recommended buffer pool size is about 40% of the physical memory size. The buffer pool116is implemented as a ring buffer where the next storage address at the end of the buffer pool116is the first address in the buffer pool110.

When a query executes, each job (that now handles an array of segments) will get an appropriate memory allocation out of the buffer pool116, overlapped IOs will be spawned for all of the columns needed by the current segment of the job. In some embodiments, overlapped IOs will be spawned for all of the columns needed by the next segment of the job as well, as a look-ahead technique to keep data warm. In particular, one additional segment needed for a next portion of a job is read into the buffer pool116so that that data is warm. The job will block to wait on the IOs of the current segment. At the end of the segment query, the segment data is “freed”, i.e. memory is returned to the buffer pool116. The buffer pool is typically significantly larger than the typical instantaneous outstanding memory needs. The allocation/free technique of the buffer pool is as follows:

(1) If there is not sufficient memory in the buffer pool116, embodiments can wait for a short period of time for memory in the buffer pool116to be freed up and made available.

(2) When returning memory to the buffer pool116, the memory becomes available only when the free happens at the end of the (ring) buffer pool. If not, the actual availability is deferred to the moment of when the free at the end of the buffer pool is issued, which also triggers a garbage collect operation of the previously freed operations.

(3) To easily manage the buffer pool, internally, in the illustrated example, it is divided in 4 kB pages, but its API has to possibility of allocating contiguous ranges of pages, which is how embodiments herein allocate portions of the buffer pool116. The division into 4 kB pages makes the management reasonable by providing direct access without too much overhead. A 50 GB buffer pool, for example, requires only 1 bit per 4 kB, meaning only about 1.5 MB of map (a 0.31% memory overhead).

Experimental results have shown that using the 1 segment look-ahead technique described above, embodiments are able to achieve about 99% of the potential bandwidth of about 6 GB/s on the Z420 machine considered above. In particular, the look-ahead technique gives the last 30% performance boost by insuring that, while the current (already paged in) segment is queried, the IO system works on paging in the next segment.

Embodiments may be implemented where not all tables are paged out to the drives. For example, in some embodiments, only shared tables and/or smaller models are paged out to drives.

In some embodiments, even further improvements can be implemented. For example, in some embodiments an additional feature may be to have a hot list of the memory inside the buffer pool and an appropriate eviction mechanism. For example, a last recently used (LRU) eviction mechanism may be used. For example, as illustrated inFIG. 1A, embodiments may implement a second ring buffer118in main memory of a smaller size where hot memory gets promoted. Items in the second ring buffer118are not recycled as quickly, and thus remain available for longer periods of time. Count usage per configurable time or some other policy. May use approximate most recently used, least recently used.

A further enhancement in some embodiments is the ability to reuse invalidated data from the buffer pool116. In particular, data may be invalidated in the buffer pool116after it has been accessed. Invalidating the data essentially indicates that the portion of the ring containing the data is available for use by new data being read into the buffer pool116. However, so long as new data has not been moved into the memory for data that has been invalidated, the data can actually be reused until it is actually overwritten. Thus, so called “invalidated” data can be used nonetheless as if it were valid data.

Referring now toFIG. 1B, and example is illustrated.FIG. 1Billustrates the ring buffer116. As illustrated inFIG. 1B, two pointers can be used to indicate the portion124of the ring buffer116marked as free. The first pointer120marks where the free portion124of the ring buffer116starts and the second pointer122marks where the end of the free portion124of the ring buffer116. When data has been read and used, the second pointer can be moved to a memory location past that data to indicate that that portion of the ring buffer116is now free. However, a subsequent search may wish to use some data that has already been read used and marked as free. So long as that data has not been overwritten, the data can be reused.

For example, assume inFIG. 1Bthat a subsequent search will use data such as that in the location labeled126. The memory location is marked as free, but the data has not been overwritten. Thus the data in location126can be reused. This may be accomplished by moving the second pointer122back to the start of location126(i.e. the end of location128) so that the location126is no longer marked as free. The data in location126can then simply be used as normal. Alternatively, the data in location126may be read from location126in the ring buffer116and rewritten to the beginning of the free portion124. The first pointer120is moved as performed when reading from disk. While this may be slower than simply moving the second pointer122, it is still faster than reading directly from disk. Further, as noted below, various considerations may be taken into account to determine whether the second pointer122should be moved, or if the data should be re-read, re-written and the first pointer120moved.

For example, consider if the data to be reused is stored in location128. Rather than moving the pointer122back to the start of location128, and un-necessarily un-freeing location126, the data in location128can be read from location128of the ring buffer116and written into the start of the free portion124. The first pointer120would then be moved passed the written data so that the written data would be in the active portion of the ring buffer116. However, if the data to be re-used is in location126, the second pointer122can be moved without re-capturing any unnecessary data so as to efficiently use the ring buffer.

In an alternative embodiment, a determination may be made as to how much unneeded data will be revalidated by unfreezing portions of the ring buffer116versus how much needed data will be revalidated by unfreezing portions of the ring buffer116. This can affect whether the second pointer122is moved or whether the data is re-read (either from the ring buffer116, or disk). For example, if moving the second pointer will result in 80% of the data revalidated being needed data and 20% being unneeded data, then embodiments may determine this to be sufficiently efficient and cause the second pointer122to be moved thus revalidating data at the end of the free portion124. However, if moving the second pointer will result in 80% of the data revalidated being unneeded data and 20% being needed data, then embodiments may determine this to not be sufficiently efficient and will instead reread the needed data, either from the ring buffer116or from one of the drives110.

Referring now toFIG. 2, a method200is illustrated. The method200may be practiced in a computing environment. The method200includes acts for implementing a database system using a plurality of sequentially ordered drives to store sequential portions of columns of the database. The database system is usable by a system configured for use with in-memory database systems. The method includes loading one or more columns of a database into main memory of a computing system as a table based database (act202). For example, as illustrated inFIG. 1A, database data may be loaded from cloud storage102into a local database cache106and then loaded into a table108implemented in main memory of the system104.

The method200may further include dividing a column of the database into sequential portions (act204). The sequential portions are generally of sufficient size to create efficient transfers using hard disk controllers to transfer an entire sequential portion. Thus, as illustrated inFIG. 1A, each of the columns is divided into segments. The segments are generally sufficiently large enough to be significant to the drives110-1through110-4. As illustrated above, using current SSD or disk card storage, reads of about 4 GB may be sufficiently large. Some embodiments can even perform acceptably using reads as low as about 500 KB.

The method200further includes writing each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion such that sequential portions of the column are on sequential drives (act206). This is illustrated inFIG. 1Awhich illustrates drives110-1through11-4ordered sequentially each with a file where each file on each sequential drive stores a sequential segment. Further, as described above, the segments are stored in a round robin fashion. Thus, in the illustrated example, file112-1-1stores segment1from column1and segment5from column1because it is, in a round robin sequence, next after the file112-4-1.

As illustrated in various examples above, the method200may be practiced where each of the sequentially ordered drives is an SSD drive.

As illustrated in the example inFIG. 1A, the method200may be practiced where each of the sequential portions is a segment.

The method200may be practiced where each of the drives stores database data on a file per column basis such that each drive has a single data file for a given column of the database irrespective of how many portions of a column are stored at a given drive.FIG. 1Aillustrates an example of this where each drive includes a file for each of the n columns.

Similarly, the method200may further include, for one or more other columns, repeating the acts of dividing a column of the database into sequential portions and writing each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion.

The method200may further include, reading sequential portions from the drives into a ring buffer. The ring buffer is implemented in the main memory of the computing system. An example is illustrated above where portions are read into the ring buffer116from the drives110-1through110-4. In particular, portions can be simultaneously read from the different drives110-1through110-4into different portions of the ring buffer116. Operations can then be performed on the data in the ring buffer116. Some embodiments may determine that certain data from in the ring buffer is hot data in that the data has a predetermined frequency of reuse. As a result, embodiments may include transferring the certain data to another buffer implemented in the main memory of the computing system. For example, as illustrated inFIG. 1A, heavily used data from the buffer116can be moved to the buffer118.

Referring now toFIG. 3, a method300is illustrated. The method300may be practiced in a computing environment. The method300includes acts for reusing data in a memory buffer. The method300includes reading data into a first portion of memory of a buffer implemented in the memory (act302). For example, inFIG. 1A, data may be read from a drive110-1into the ring buffer116.

The method300may further include invalidating the data and marking the first portion of memory as free (act304). Thus, the first portion of memory is marked as being usable for storing other data, but where the data is not yet overwritten. For example, the location126may be marked as a free portion by moving the pointer122to the end of the location126.

The method300includes reusing the data in the first portion of memory after the data has been invalidated and the first portion of the memory is marked as free (act306). Thus, in the illustrated example, data can be used from the location126even though that data had been invalidated by the location126being marked as free.

The method300may be practiced where reusing the data in the first portion of memory comprises unmarking the first portion of memory so that the first portion of memory is no longer marked as free. Thus, for example, the pointer122could be moved to the end of location128thus revalidating the data in location126. The method300may be practiced where the first portion of memory is unmarked based on a determination of the position of the first portion of memory with respect to other portions of free memory in the buffer. Thus, for example, since the location126is at the end of the free portion124of the buffer116, it may be a simple task to simply move the pointer122. However, if the portion in question was at location128, then a determination may be made to not move the pointer122and instead either read the data from the portion128and rewrite it to the buffer or to read the data from disk110and rewrite it to the buffer.

The method300may be practiced where the first portion of memory is unmarked based on a determination that unmarking the first portion of memory will not cause a predetermined amount of other data to be revalidated where the other data is data not intended to be reused. Thus, for example, if the data to be reused is in location128moving the pointer to the beginning of location128will not cause too much unneeded data (i.e. the data in location126) to be revalidated, then a determination may be made that it is acceptable to move the pointer122.

The method300may be practiced where reusing the data in the first portion of memory comprises reading the data from the first portion of memory that has been marked as free and writing the data to a different portion of the buffer. Thus, as illustrated above, in some embodiments, data in location126may be reused by re-reading the data from location126and writing it to a different portion of the buffer116, such as the beginning of the free portion124, and moving the first pointer120to a location after the rewritten data. In some such embodiments, the data is read from the first portion of memory that has been marked as free and written to a different portion of the buffer based on a determination of the position of the first portion of memory with respect to other portions of free memory in the buffer. Thus in the illustrated example, it may be more efficient to read data from location128and rewrite the data rather than moving the pointer122. As discussed above, the data may be read from the first portion of memory that has been marked as free and written to a different portion of the buffer based a determination that unmarking the first portion of memory will cause a predetermined amount of other data to be revalidated where the other data is data not intended to be reused and thus reading and rewriting the data is more efficient than unmarking the first portion as free.

The method300may be practiced where the buffer is a ring buffer.

Further, upon reaching various computer system components, program code means in the form of computer-executable instructions or data structures can be transferred automatically from transmission computer readable media to physical computer readable storage media (or vice versa). For example, computer-executable instructions or data structures received over a network or data link can be buffered in RAM within a network interface module (e.g., a “NIC”), and then eventually transferred to computer system RAM and/or to less volatile computer readable physical storage media at a computer system. Thus, computer readable physical storage media can be included in computer system components that also (or even primarily) utilize transmission media.