SILT Key-Value Store

Motivation

Key-value stores are ubiquitous in modern systems. We want a key-value store that can store huge numbers of keys and their values using storage efficiently, while still serving the put and get operations fast. There is a trade-off between storage efficiency and making operations fast. In this design problem, we will construct a key-value store (SILT—scalable small index large table) that internally uses multiple stores, each optimized for some use cases, but exporting an interface for the user where multiple stores appear as one, fulfilling our goals.

Distributed key-value stores consist of many instances of single-node stores. Our focus in SILT design will be on the single-node key-value store. We can extend it to the multi-node store as discussed in Amazon Dynamo system design. SILT’s design is involved, but we must leave out many details in this abridged version. If you need full details, see the more extended version.

Design goals

The following are our main design goals. We use flash disks for persistent storage and RAM for speedy operations.

1. Efficient use of resources

   1. Minimize the use of memory (RAM) per key (for quick access, we want to keep key indices and at least some of the data in the RAM).

   2. Computation-efficient indexing (bytes needed per key for indexing a key should be low)

2. High performance with low latency

   1. Quick lookups and writes

   2. Low read and write amplifications

Since the main problem we are trying to solve is data storage and retrieval, we can focus on read and write operations. Read operations involve looking up values in data. Ideally, we would want these to be as fast as possible. One metric to gauge the efficiency of read and write operations is amplification. We will use the terms read amplification and write amplification.

Read amplification means when a single read operation requires multiple storage reads or seeks. We can measure it using the following formula.