Enabling efficient OS paging for main-memory OLTP databases

Even though main memory is becoming large enough to fit most OLTP databases, it may not always be the best option. OLTP workloads typically exhibit skewed access patterns where some records are hot (frequently accessed) but many records are cold (infrequently or never accessed). Therefore, it is more economical to store the coldest records on a fast secondary storage device such as a solid-state disk. However, main-memory DBMS have no knowledge of secondary storage, while traditional disk-based databases, designed for workloads where data resides on HDD, introduce too much overhead for the common case where the working set is memory resident. In this paper, we propose a simple and low-overhead technique that enables main-memory databases to e• ciently migrate cold data to secondary storage by relying on the OS's virtual memory paging mechanism. We propose to log accesses at the tuple level, process the access traces o• ine to identify relevant access patterns, and then transparently re-organize the in-memory data structures to reduce paging I/O and improve hit rates. The hot/cold data separation is performed on demand and incrementally through careful memory management, without any change to the underlying data structures. We validate experimentally the data re-organization proposal and show that OS paging can be efficient: a TPC-C database can grow two orders of magnitude larger than the available memory size without a noticeable impact on performance. Copyright © 2013 ACM.

Flash-aware Database Transactions

Radu Ioan Stoica

Over the past 40 years, hard disks, the traditional building block of storage systems, have become increasingly slower when compared to the other system components such as the main memory and the CPU. Hard disks face mechanical constraints that cause their I/O bandwidth to lag behind capacity growth, while the access latency has remained virtually unchanged for the past 20 years. The growing gap between the main memory and the persistent storage brought us to a point where I/O accesses are the main bottleneck that limits the performance of database management systems. Several new solid-state storage technologies have been under development and are now commercially successful, with NAND flash memory being the most mature. Such technologies store data durably, have no mechanical constraints to limit their I/O performance, and can bridge the growing gap between the main memory and the persistent storage. Solid-state drives, however, have very different characteristics compared to hard disks, making it challenging to integrate such technology. For decades, database management systems have been implicitly developed and optimized around the model of a slow rotating hard disk. In this thesis, we focus on transactional database workloads composed of large numbers of small concurrent queries. Transactional workloads generate large numbers of scattered I/O requests at the level of the storage system that are traditionally challenging for hard disks to service. Solid-state drives, on the other hand, are a much better suited technology as they service natively I/O requests in parallel and their performance is not constrained by access locality. The approach we take in this thesis is to traverse the I/O stack of a database management system, i.e. the major software layers that define how data is stored and accessed, and show how these components can, with careful consideration of flash behavior and through novel algorithms, make efficient use of flash-based storage devices. The methodology we use is to observe the data access patterns and the data access frequencies at each level of the I/O stack and design new algorithms and data structures that match the characteristics of the workload with the constraints of flash memory. We use a bottom up approach to revisit the Storage Device, the Storage Manager, and the Caching layers of a data management system and show how each component can better exploit flash technology. At the level of the Storage Device, we show how a solid-state drive can minimize the overhead of storing data on the raw flash chips by exploiting the write skew present in real-life transactional workloads. We then introduce a log-structured data placement policy for the Storage Manager of a database system that can transparently adapt the data access pattern to eliminate all random I/O writes that are problematic for flash solid-state drives. Finally, we propose an architecture for the Caching layer that allows database systems to efficiently move data between main memory and a fast solid-state drive without having to incur the large overhead and limitations of the traditional buffer pool design.

EPFL2014

Flash-aware Database Transactions

Radu Ioan Stoica

EPFL2014