Evaluation of High Performance Key-Value Stores

Abstract

Key-value stores have a long history of providing users with a simple to use, yet powerful, interface to durable data storage. Useful for various purposes in their own right, they are also often used as storage layers in more complicated systems---such as fully featured database management systems. For these reasons, it is educational to investigate how such systems are actually architectured and implemented. This thesis looks in detail at two recently developed embedded key-value stores, Google LevelDB and Symas Lightning Memory-Mapped Database (LMDB). Both systems' overarching architecture and lower-level implementation details are considered to provide a thorough description of how they work. While exposing largely the same set of features, the systems are shown to take vastly different approaches to data storage. These techniques are described, and put in context with regards to existing ideas from the database management systems field. It is also shown how the designs impact performance in the face of different types of workloads.