Design a Key-Value Store

Question

Design a distributed key-value store like Bigtable or DynamoDB. Cover consistent hashing, replication strategies, read/write quorums, compaction, and tunable consistency levels.

Codemia · Accepted Answer

### Functional Requirements
1. **Key-Value Storage**: Users can store and retrieve values associated with unique keys.
2. **CRUD Operations**: Support for Create, Read, Update, and Delete operations.
3. **Batch Operations**: Ability to perform batch read/write operations.
4. **Tunable Consistency Levels**: Users can configure consistency levels for operations (strong, eventual).
5. **Replication**: Automatic replication of data across multiple nodes for fault tolerance.

### Non-Functional Requirements
1. **Scalability**: The system should handle millions of reads and writes per second as demand scales.
2. **Low Latency**: Read and write operations should have sub-second latencies.
3. **High Availability**: The system must ensure 99.999% availability.
4. **Data Durability**: Data should be durable and recoverable even in the event of hardware failure.
5. **Security**: Implement encryption for data at rest and in transit.

### Capacity Estimation
- **Expected Users**: Assume 1 million active users.
- **Requests per User**: Each user generates approximately 10 requests per minute.
- **Total Requests per Minute**: 1,000,000 users * 10 requests/user/min = 10 million requests/minute.
- **Requests per Second**: 10 million requests/minute / 60 seconds = ~166,667 requests/second.
- **Data Size**: Assume each value stored is approximately 1KB.
- **Total Data Size**: If each user stores an average of 100 keys, total size = 1 million users * 100 keys * 1KB = 100 TB.
- **Replication Factor**: Using a replication factor of 3, total storage = 100 TB * 3 = 300 TB.

### High-Level Architecture
- **Client Interface**: RESTful API using gRPC for efficient communication.
- **Load Balancer**: Distributes incoming requests to appropriate key-value store nodes.
- **Key-Value Store Nodes**: Implemented using Google Cloud Bigtable for managing distributed storage.
- **Consistent Hashing Layer**: To distribute keys across nodes, ensuring load balancing and fault tolerance.
- **Replication Manager**: Handles data replication across nodes and manages write quorum.
- **Compaction Service**: Periodically compacts SSTables to optimize read performance and reclaim space.
- **Cache Layer**: Redis or Memcached for caching frequently accessed data to reduce latency.

### Data Model
- **Key-Value Schema**: Each entry consists of a unique key and a value.
- **Table Structure**: 
  - **Key** (string): Unique identifier for the value.
  - **Value** (blob): The data stored (could be JSON, binary data, etc.).
  - **Timestamp** (int): For versioning and ensuring the latest write is fetched.
  - **Metadata** (JSON): Optional metadata for additional information (e.g., TTL, user tags).
- **Access Patterns**: Optimized for key-based lookups and range queries using row keys.

### Key Trade-offs
1. **Consistency vs. Availability**: Choosing eventual consistency for higher availability and lower latency, which may lead to stale reads.
2. **Complexity of Tunable Consistency**: Implementing tunable consistency increases complexity; however, it allows flexibility for different use cases.
3. **Replication vs. Performance**: Higher replication factors improve durability but can impact write latency; balancing this based on use case is crucial.
4. **Read/Write Quorum**: A larger quorum increases consistency but affects performance; a balance needs to be struck based on application requirements.
5. **Compaction Strategy**: Choosing between size-tiered and leveled compaction affects read/write performance and storage efficiency, requiring careful consideration based on expected workloads.

Design a Key-Value Store

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements

Capacity Estimation

Capacity Estimation

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search