Author

Xingbo Wu

ORCID Identifier(s)

0000-0003-1649-2612

Graduation Semester and Year

2018

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Engineering

Department

Computer Science and Engineering

First Advisor

Song Jiang

Abstract

Driven by the growing demands from big-data applications, the focus of their data management has been largely shifted from traditional SQL databases to NoSQL (Not-only- SQL) databases, such as key-value (KV) stores, which provides essential functionalities and much higher performance for storing and retrieving data. Correspondingly new hardware technologies have been developed to support the fast data accesses, such as NVMe SSDs and Infiniband network. However, existing designs of NoSQL databases usually see sub- optimal performance on fast hardware. Traditionally the computing overhead of a database system is overshadowed by the slow storage and network. With the adoption of the new hardware technologies the inefficiency at the software side is now the major source of bottlenecks in today’s systems. In this dissertation we propose solutions to overcome barriers on the adoption of new technologies, such as large DRAMs, fast SSDs, and low-latency Infiniband network, into existing stacks of software systems. Accordingly introduce new designs, including Search Lookaside Buffer (SLB), zExapnder, LSM-trie, and NVMcached, to improve the systems’ efficiency on accessing SSD, DRAM, non-volatile main memory, and CPU cache. We identify false temporal locality and false spatial locality in index search and propose SLB to effectively improve index search by removing the false localities. In zExpander we use compression to increase the effective capacity in KV caches without adding DRAM, which can substantially reduce misses in the KV cache. In LSM-trie we introduce a trie-based data structure to reduce the overhead of internal data reorganization by an order of magnitude for KV stores on SSDs. In NVMcached we remove expansive FLUSH operations for persistent and crash-consistent KV caches on byte-addressable NVM.

Keywords

Key-value store, Key-value cache, NoSQL databases, Caching, Index data structures

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

27669-2.zip (11721 kB)

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.