Distributed Key-Value Store

May 14, 2023 7:00 PM PDT

---

This document summarizes the design considerations and technical discussions surrounding a distributed key-value store system. The focus is on functional requirements, system architecture, consistency models, concurrency handling, and durability strategies.

Requirements

Functional Requirements

• Key-Value Store: The system should support a key-value storage model.
• Data Size: Expected data growth is 10 TB per year.
• Value Size: Average value size is 1 KB, with no need for handling large key-values.
• Queries Per Second (QPS): Targeting 100,000 QPS.
• Latency: Maximum latency should be 50 ms.
• Availability: Target availability is 99.99%.
• Fault Tolerance: The system must be fault-tolerant with no single point of failure.
• Scalability: The system should support high concurrency.

System Design

Architecture

1. Client-Server Interaction:

   • Clients communicate with a load balancer using HTTP and JSON.
   • The load balancer forwards requests to a request manager.
   • The request manager queries a config server to find the responsible storage node and then communicates with the data server.

2. Config Server:

   • Responsible for maintaining metadata and mapping of data servers.
   • Can maintain a heartbeat with data servers for leader election.
   • A replica config server and sentinel can be used for monitoring and failover.

3. Data Server:

   • Responsible for data storage and migration.
   • Utilizes a database engine such as LevelDB, which employs a log-structured merge tree (LSM tree) for efficient write operations.

Caching

• A server-side cache can be implemented before the config server to reduce load.
• Cache invalidation occurs when the config mapping is updated, ensuring clients receive the latest mapping.

Data Distribution

• Consistent hashing can be used for data distribution across servers.
• A mapping table maintained by the config server contains information about data server locations.

Consistency and Concurrency

Consistency Model

• The system targets eventual consistency but can provide strong consistency using techniques like RAFT.
• When data is modified on multiple nodes, the system can acknowledge success to the client based on a majority of nodes confirming the change.

Concurrency Control

• Versioning is used to handle concurrent modifications to the same key.
• Optimistic locking is preferred over pessimistic locking for independent records.

Durability

• Durability is ensured through backup mechanisms for both the config server and data store.
• Write-ahead logging can be implemented to safeguard against data loss during server failures.

Audience Discussion

• The discussion included comparisons with other systems like Elasticsearch, focusing on consistency models and data replication strategies.
• The importance of understanding the differences between primary and replica shards in Elasticsearch was highlighted.
• The order of discussing distributed systems versus single-node systems was debated, suggesting that starting with single-node considerations may provide clearer insights.

Conclusion

The design of a distributed key-value store involves careful consideration of functional requirements, system architecture, consistency models, concurrency handling, and durability strategies. By leveraging techniques such as consistent hashing, versioning, and write-ahead logging, the system can achieve high availability and fault tolerance while maintaining performance under high load.