Design of a Key-Value Store
Define the functional and non-functional requirements essential for designing a highly available key-value store. Analyze how needs like configurable consistency and always-write capability influence System Design decisions. Understand the simple get and put operations that enables complex distributed storage.
We'll cover the following...
Requirements
We will design a key-value store that addresses the limitations of traditional databases.
Functional requirements
While standard key-value stores offer get and put operations, this design focuses on specific characteristics:
Configurable service: Applications often trade strong consistency for higher availability. The system must support configurable consistency models that allow users to balance availability, consistency, cost, and performance.
Note: These configurations are set when instantiating a key-value store instance and cannot be changed dynamically during operation.
Ability to always write: Applications must always be able to write to storage. This prioritizes availability over consistency (choosing “A” over “C” in the CAP theorem).
Note: Whether a requirement is classified as functional or non-functional depends on context. For example, in a shopping cart system, the ability to accept writes at all times (high availability) can be treated as a functional requirement. Following the Dynamo design principles, we treat “always write” as a functional requirement in this context.
Hardware heterogeneity: The system must seamlessly integrate new servers with different capacities without upgrading existing ones. Workload distribution should align with server capacity, favoring a peer-to-peer design without distinguished nodes.
Non-functional requirements
The system must meet the following non-functional requirements:
Scalability: The system must support tens of thousands of servers globally. Incremental scalability is essential, allowing servers to be added or removed with minimal service disruption.
Fault tolerance: The system must operate uninterrupted despite server or component failures.
Now that you understand the functional and non-functional requirements of a key-value store, what do you think are the key differences between key-value stores and traditional databases? In what scenarios are key-value stores particularly advantageous?
Assumptions
We make the following assumptions to simplify the design:
Data centers hosting the service are trusted (non-hostile).
Authentication and authorization are handled externally.
User requests and responses use HTTPS.
API design
Like hash tables, key-value stores provide two primary operations: get and put.
The get function:
The API call to get a value should look like this:
get(key)
Returns the value associated with key. In replicated environments, the system locates the object replica hidden from the user. If configured for weaker consistency (e.g., eventual consistency), the system may return multiple values (versions) for a single key.
Parameter | Description |
| It’s the |
The put function:
The API call to put the value into the system should look like this:
put(key, value)
Stores the value associated with key. The system automatically determines data placement and maintains metadata, such as the object version.
Parameter | Description |
| It's the |
| It's the object to be stored against the |
Data type
The key serves as the unique identifier, while the value can be any arbitrary binary data.
Note: Dynamo uses MD5 hashes to generate a 128-bit identifier for the key. These identifiers determine which server node is responsible for the specific key.
The next lesson covers the key-value store design, with an emphasis on scalability, replication, and versioning. We start with non-functional requirements, since the chosen scalability strategy shapes how functional requirements are implemented.
Note: This chapter is based on
, an influential work in the domain of key-value stores. Dynamo Amazon’s Highly Available Key-value Store (https://assets.amazon.science/ac/1d/eb50c4064c538c8ac440ce6a1d91/dynamo-amazons-highly-available-key-value-store.pdf)