Overview
People
Publications
Download
Changes
Wiki
(member only)
Contact Us
Sponsors
This project is sponsored by the National Science Foundation(NSF Grant No. IIS-0848503)

The Objectives and Scope of the Project

Flash memory storage devices are now considered to have tremendous potential as a new storage medium that can replace magnetic disks. Flash memory, however, has its own limitations such as erase-before-update and exhibits poor performance for small-to-moderate sized writes requested in a random order.


The goal of this project is to develop new flash-aware designs and optimization strategies that allow large-scale transactional database applications to run efficiently on computing platforms equipped with flash memory storage devices as a main storage medium.

This project achieves its goal by (1) analyzing the performance implications of different I/O workloads on flash memory, and the applicability of flash memory to different types of tablespaces in databases, (2) inventing new paradigms, designs, data structures and algorithms, hot spot separation, and write optimization techniques, so that enterprise database servers can run on the target computing platforms efficiently.

The findings from this project will not only overcome the limitations of flash memory but also exploit the advantages of flash memory for transactional database workloads exhibiting randomly scattered data access patterns. New paradigms and processing strategies that will be designed, implemented and evaluated for this project can be applied to other areas such as health-care and sensor-network based environment study that require data management on flash memory storage systems. The findings and deliverables of the project will be disseminated broadly in the form of software packages, research articles, technical reports, and data sets via the project web site.

A case for Flash Memory SSD in Enterprise Database Applications

Due to its superiority such as low access latency, low energy consumption, light weight, and shock resistance, the success of flash memory as a storage alternative for mobile computing devices has been steadily expanded into personal computer and enterprise server markets with ever increasing capacity of its storage. However, since flash memory exhibits poor performance for small-to-moderate sized writes requested in a random order, existing database systems may not be able to take full advantage of flash memory without elaborate flash-aware data structures and algorithms. The objective of this work is to understand the applicability and potential impact that flash memory SSD (Solid State Drive) has for certain type of storage spaces of a database server where sequential writes and random reads are prevalent. We show empirically that up to more than an order of magnitude improvement can be achieved in transaction processing by replacing magnetic disk with flash memory SSD for transaction log, rollback segments, and temporary table spaces.

Characteristics of Flash Memory

Flash memory is a purely electronic device with no mechanically moving parts like disk arms in a magnetic disk drive. Hence, it supports uniform random access speed. The time to access data in flash memory is almost linearly proportional to the amount of data, regardless of their physical locations in flash memory. The ability of flash memory to quickly perform a sector read or a sector write located anywhere in flash memory is one of the key characteristics we can exploit. Also, with flash memory, no data item can be updated in place just by overwriting it. To update an existing data item stored in flash memory, a time-consuming erase operation must be performed before overwriting. The erase operation can be only done for an entire block of flash memory(called erase unit) containing a data item, not the particular data item or sector. In addition, the read and write speed of flash memory is asymmetric, because it takes longer to write a cell until reaching a stable status than to read the status from a cell. For instance, the sustained read speed is almost twice faster than write speed.

Flash SSD for Database Workload

Typical transactional database workloads like TPC-C exhibit little locality and sequentiality in data accesses, a high percentage of which are synchronous writes. Such latency hiding techniques as prefetching and write buffering become less effective for this type of workload, and the performance of transactional database applications tends to be more closely limited by disk latency than disk bandwidth and capacity. Nonetheless, for more than a decade in the past, the latency of disk has improved at a much slower pace than the bandwidth of disk, and the latency-bandwidth imbalance is expected to be even more evident in the future.

In this regard, the low latency of flash memory SSD can reduce the average transaction commit time and enhance the throughput of transaction processing significantly. If multiversion read consistency is supported, rollback data are typically written to rollback segments sequentially in append-only fashion and read from rollback segments randomly during transaction processing. This peculiar I/O pattern is a good match for the characteristics of flash memory itself and a super-block(eight erase units, or large blocks of 128 KBytes each) scheme of the Samsung flash memory SSD. Also, external sorting can be another operation to be able to exploit the low latency of flash memory SSD, for its read pattern is quite random during the merge phase in particular.

This flash memory SSD(Solid State Drive) of Samsung Electronics is a non-volatile storage device based on NAND-type flash memory, which is being marketed as a replacement type flash memory. Its spec is Samsung Standard Type MCAQE32G8APP-0XA with 32 GB capacity and 1.8 inch PATA interface, which internally deploys Samsung K9WAG08U1A 16 Gbits SLC NAND flash chips.

Experimental Results

We have observed more than an order of magnitude improvement in transaction throughput and response time by replacing a magnetic disk drive with a flash memory SSD drive for transaction log or rollback segments. We have also observed more than a factor of two improvement in response time for processing a sort-merge or hash join query by adopting a flash memory SSD drive instead of a magnetic disk drive for temporary table spaces. We believe that a strong case has been made out for flash memory SSD, and due attention should be paid to it in all aspects of database system design to maximize the benefit from this new technology.

Design of Flash-Based DBMS: An In-Page Logging Approach

The popularity of high-density flash memory as data storage media has increased steadily for a wide spectrum of computing devices such as PDAs, MP3 players, mobile phones and digital cameras. More recently, computer manufacturers started launching new lines of mobile or portable computers that did away with disk drives altogether, replacing them with tens of gigabytes of NAND flash memory. Like EEPROM and magnetic disk drives, flash memory is non-volatile and retains its contents even when the power is turned off. As its capacity increases and price drops, flash memory will compete more successfully with lower-end, lower-capacity disk drives. It is thus not inconceivable to consider running a full database system on the flash-only computing platforms or running an embedded database system on the lightweight computing devices. In this paper, we present a new design called in-page logging(IPL) for flash memory based database servers. This new design overcomes the limitations of flash memory such as high write latency, and exploits unique characteristics of flash memory to achieve the best attainable performance for flash-based database servers. We show empirically that the IPL approach can yield considerable performance benefit over traditional design for disk-based database servers. We also show that the basic design of IPL can be elegantly extended to support transactional database recovery.

Basic Concepts of IPL

Since flash memory does not have any mechanical component, it never suffers from subtantial performance penalty by random writes, and does not have to write log records sequentially at all. Therefore, we co-locate a data page and its log records in the same physical location of flash memory, specifically, in the same erase unit(a large block of flash memory), which is called 'In-Page' logging. Because only the previous data page and its log records stored in the same erase unit should be accessed, the current version of the page can be re-created efficiently under the IPL approach. Even though the amount of data to read will increase by the number of log records belonging to the data page, it will still be a sensible trade-off for the reduced write and erase operations particularly considering the fact that read is typically at least twice faster than write for flash memory. Hence, the IPL approach can enhance the overall write performance considerably.

This figure shows how the IPL approach is evolved from the traditional update-in-place and log-structured approaches. While logging is a consequential decision due to the erase-before-write limitation of flash memory, in-page logging is to exploit the desirable properties(i.e., no mechanical latency and fast reads) of flash memory.

The Design of IPL

To realize the basic concepts of the in-page logging with the minimal cost, logging has to be done by the buffer manager as well as the storage manager. Whenever an update is performed on a data page, the in-memory copy of the data page is updated just as done by traditional database servers. Furthermore, the IPL buffer manager adds a physiological log record on the per-page basis to the in-memory log sector associated with the in-memory copy of the data page. An in-memory log sector can be allocated on demand when a data page becomes dirty, and can be released when the log records are written to a log sector on the flash memory. The log records in an in-memory log sector are written to flash memory when the in-memory log sector becomes full or when a dirty data page is evicted from the buffer pool. The effect of the in-memory logging is similar to that of write caching, so that multiple log records can be written together at once and accordingly frequent erase operations can be avoided. When a dirty page is evicted, it is not necessary to write the content of the dirty page back to flash memory, because all of its updates are stored in the form of log records in flash memory. Hence, the previous version of the data page remains intact in flash memory, but is just augmented with the update log records. When an in-memory log sector is to be flushed to flash memory, its content is written to a flash log sector in the erase unit which its corresponding data page belongs to, so that the data page and its log records are physically co-located in the same erase unit. To do this, the IPL storage manager divides each erase unit of flash memory into two segments âΆζ΅° one for data pages and the other for log sectors.

Example: In this figure, an erase unit of 128KBbytes can be divided into 15 data pages of 8KBbytes each and 16 log sectors of 512 bytes each. When an erase unit runs out of free log sectors, the IPL storage manager merges the data pages and log sectors in the erase unit into a new erase unit.

Merge Operation

An in-memory log sector can store only a finite number of log records, and the content is flushed into a flash log sector when it becomes full. Since there are only a small number of log sectors available in each erase unit of flash memory, if data pages fetched from the same erase unit are frequently updated, the erase unit may run short of free log sectors. It is when merging data pages and their log sectors is triggered by the IPL storage manager. If there is no free log sector left in an erase unit, the IPL storage manager allocates a free erase unit, computes the new version of the data pages by applying the log records to the previous version, writes the new version into the free erase unit, and then erases and releases the old erase unit.