Storage system design for non-volatile byte-addressable memory using consistent and durable data structures

The predicted shift to low cost, non-volatile, byte-addressable memory (e.g., Phase Change Memory and Memristor), the growth of “big data”, and the subsequent emergence of frameworks such as memcached and NoSQL systems require us to rethink the design of storage systems. Today, the predominant method available to application programmers for obtaining persistence of data is through the file interface which provides access to a filesystem, which in turn uses the block layer to provide access to hard disk drives or solid state disks. With the advent of non-volatile byte-addressable memory (NVBM), buffered I/O systems designed primarily for hard disks are no longer the most efficient design for storage. We show that the overheads imposed by system calls, the file interface, and the block device layer can make NVBM access up to 266 times slower compared to directly performing loads and stores. With performance characteristics closer to DRAM, NVBM demands software designs that resemble common heap data structures rather than current systems that serialize data via the file interface. To derive the maximum performance, we propose the use of single-level data stores where no distinction is made between a volatile and a persistent copy of data. For these systems, we present Consistent and Durable Data Structures (CDDSs) that, on current hardware, allows programmers to safely exploit the low-latency and non-volatile aspects of new memory technologies. CDDSs use versioning to allow atomic updates without requiring logging. The same versioning scheme also enables rollback for failure recovery. When compared to a memory-backed Berkeley DB B-Tree, our prototype- based results show that a CDDS B-Tree can increase put and get throughput by 74% and 138%. Tembo, a CDDS B-Tree enabled distributed Key-Value system, has up to 250%–286% higher throughput than Cassandra, a two-level data store.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Venkataraman, Shivaram

Contributors dc:contributor

• Campbell, Roy H.

• storage system
• non-volatile memory
• data structures

Statement dc:rights

• Copyright 2011 Shivaram Venkataraman

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24054

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24054