Key Value Store

Key-Value Store, we'll go through the High-Level Design (HLD) and Low-Level Design (LLD) components. A Key-Value Store is similar to a dictionary or hash table, where each key is associated with a value, and it's commonly used in distributed systems for caching, quick data retrieval, and session management.

Requirements

Functional Requirements:

  1. Set a Value: Store a value with a given key.

  2. Get a Value: Retrieve the value associated with a key.

  3. Delete a Key: Remove a key-value pair.

  4. TTL (Time-to-Live): Support optional expiry for each key.

  5. Persistence (Optional): Store data on disk to allow recovery after a restart.

  6. Distribution (Optional): Scale horizontally for handling larger loads, possibly using sharding.

Non-Functional Requirements:

  1. High Availability: The system should be resilient and available.

  2. Low Latency: Responses should be fast, as key-value stores are often used in real-time applications.

  3. Scalability: The store should handle high read and write loads and scale as needed.

  4. Consistency: Ensure consistency when values are updated, even in a distributed setup.

High-Level Design (HLD)

We'll break down the components that make up a distributed Key-Value Store and the flow between them.

1. Key Components

  1. Client API: Exposes operations like GET, SET, DELETE, and optionally EXPIRE (TTL).

  2. Cache Layer: Optionally stores data temporarily for faster access.

  3. Data Storage Layer: Persistent layer that stores key-value pairs on disk (e.g., in a NoSQL database or custom storage engine).

  4. Coordinator: Responsible for sharding, ensuring data consistency, and communicating with the right nodes to fulfill a request.

  5. Replication Manager: Handles data replication to ensure high availability and fault tolerance.

  6. Consistency Manager: Ensures data consistency across replicas.

  7. Load Balancer: Distributes incoming requests among nodes to balance the load.

Architecture Diagram

                           +----------------+
                           |    Clients     |
                           +--------+-------+
                                    |
                                    ▼
                           +----------------+
                           |  Load Balancer |
                           +--------+-------+
                                    |
                   +----------------+----------------+
                   |                                 |
                   ▼                                 ▼
          +----------------+                 +----------------+
          |    Node 1      |                 |    Node 2      |
          +----------------+                 +----------------+
          |                |                 |                |
    +-----+-----+    +-----+-----+     +-----+-----+    +-----+-----+
    |  Cache   |     |  Storage  |     |  Cache    |    |  Storage  |
    +----------+     +-----------+     +-----------+    +-----------+

Workflow

  1. Client Request:

    • A client sends a request to perform operations (GET, SET, DELETE) to the load balancer.

  2. Load Balancer:

    • The load balancer forwards the request to one of the nodes based on availability and load.

  3. Node:

    • Each node contains a Cache and a Storage layer.

    • The Cache layer stores frequently accessed data to reduce read times.

    • The Storage layer is responsible for persisting data.

  4. Replication and Consistency:

    • When a new key-value pair is added or updated, the Replication Manager ensures that the data is copied to other nodes (replicas) to ensure availability.

    • The Consistency Manager enforces consistency across replicas to make sure the latest data is available on all nodes.

  5. Data Expiry (TTL):

    • When a key is set with a TTL, the system automatically removes it after the TTL expires.

Sharding Strategy

For large-scale systems, consistent hashing can be used to distribute data among nodes. This hashing strategy reduces the impact of adding or removing nodes in the system by minimizing data movement across nodes.

Low-Level Design (LLD)

Core Classes and Interfaces

  1. KeyValueStore Interface:

    • get(key: String): String

    • set(key: String, value: String, ttl?: number): void

    • delete(key: String): void

    • expire(key: String, ttl: number): void

  2. CacheManager:

    • Manages cache storage and retrieval to speed up access times.

    • Cache replacement policies like LRU (Least Recently Used) can be implemented to manage the cache size.

  3. StorageManager:

    • Responsible for persistent storage.

    • Methods: save(key: String, value: String), load(key: String): String, and remove(key: String): void.

  4. ReplicationManager:

    • Handles data replication across nodes to ensure redundancy.

    • Methods like replicateData(key: String, value: String), syncWithNode(nodeID: String) help maintain consistency.

  5. TTLManager:

    • Manages key expiration.

    • Maintains a separate data structure to track TTL and automatically deletes keys after expiry.

UML Class Diagram

+-----------------------+
|   KeyValueStore       |
+-----------------------+
| + get(key): String    |
| + set(key, value): void|
| + delete(key): void   |
| + expire(key, ttl): void|
+-----------------------+
           |
           |
           ▼
+-----------------------+
|   CacheManager        |
+-----------------------+
| - cache: Map<String, String> |
| + getFromCache(key): String |
| + setInCache(key, value): void|
| + removeFromCache(key): void|
+-----------------------+

+-----------------------+
|   StorageManager      |
+-----------------------+
| - storage: Map<String, String> |
| + save(key, value): void       |
| + load(key): String            |
| + remove(key): void            |
+-----------------------+

+-----------------------+
|   ReplicationManager  |
+-----------------------+
| + replicateData(key, value): void|
| + syncWithNode(nodeID): void      |
+-----------------------+

+-----------------------+
|    TTLManager         |
+-----------------------+
| - ttlData: Map<String, number> |
| + setTTL(key, ttl): void        |
| + checkExpiry(): void           |
+-----------------------+

Data Flow

  1. Write Operation (SET):

    • The client sends a SET request to store a key-value pair.

    • The system first updates the CacheManager and then persists it in StorageManager.

    • If a TTL is provided, TTLManager tracks the expiry time.

    • The ReplicationManager ensures that the data is copied to replicas.

  2. Read Operation (GET):

    • The client sends a GET request for a specific key.

    • The CacheManager is checked first; if the data is found, it's returned directly (cache hit).

    • If not found (cache miss), the StorageManager is queried, and the result is added to the cache.

  3. Delete Operation (DELETE):

    • The client requests a DELETE operation.

    • The key is removed from both CacheManager and StorageManager.

    • Replicas are updated via ReplicationManager to ensure consistency.

  4. TTL Expiry:

    • The TTLManager checks for expired keys periodically.

    • Expired keys are automatically removed from the cache and storage

Scaling Considerations

  • Sharding: Use consistent hashing to distribute keys among multiple nodes.

  • Replication Factor: Configure a replication factor to ensure data availability in case of node failure.

  • Cache Invalidation: Implement a cache invalidation strategy to ensure data consistency across replicas.

  • Consistency Models: Options include strong consistency (with acknowledgments from replicas) or eventual consistency for faster reads.

PreviousHLDNextJava

Last updated