Scalable low-latency indexes for a key-value store
Abstract/Contents
- Abstract
- Many large-scale key-value storage systems sacrifice features like secondary indexing and/or strong consistency in favor of scalability or performance. This limits the ease and efficiency of application development on such systems. Implementing secondary indexing in a large-scale memory based system is challenging because the goals for low latency, high scalability, strong consistency and high availability often conflict with each other. This dissertation shows how a large-scale key-value storage system can be extended to provide secondary indexes while meeting those goals. The resulting architecture is called Scalable Low-Latency Indexes for a Key-Value Store, or SLIK. It extends a standard key-value store to enable multiple secondary keys for each object and allows lookups and range queries on these keys via secondary indexes. SLIK allows indexes to be partitioned and distributed independently of the data in tables in order to ensure scalability. Locating objects and corresponding index entries on different servers can lead to potential consistency issues. However, SLIK provides strong consistency guarantees using a lightweight ordered write approach. While SLIK stores indexes in DRAM to enable low latency, it ensures that the index information is durable and quickly recovered using backups in case of crashes. This design was implemented in RAMCloud, a distributed in-memory key-value storage system. This implementation performs indexed reads in 11--13 μs and writes in 30--37 μs, which is approximately twice the latency of basic non-indexed reads and writes in RAMCloud. It supports indexes spanning thousands of nodes, and yields linear scalability for throughput.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Kejriwal, Ankita Arvind |
|---|---|
| Associated with | Stanford University, Computer Science Department. |
| Primary advisor | Ousterhout, John K |
| Thesis advisor | Ousterhout, John K |
| Thesis advisor | Garcia-Molina, Hector |
| Thesis advisor | Winstein, Keith |
| Advisor | Garcia-Molina, Hector |
| Advisor | Winstein, Keith |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Ankita Arvind Kejriwal. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Ankita Arvind Kejriwal
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...