Design a key-value store in HLD - System Design Exercise

Design: Key-Value Store

Design covers core key-value storage, data replication, and client API. Does not cover advanced features like transactions, complex queries, or multi-region geo-distribution.

Functional Requirements

FR1: Store and retrieve data as key-value pairs

FR2: Support basic operations: put(key, value), get(key), delete(key)

FR3: Handle up to 1 million keys

FR4: Provide low latency for read and write operations (p99 < 50ms)

FR5: Ensure data durability and availability

FR6: Support concurrent access from multiple clients

Non-Functional Requirements

NFR1: System should be highly available with 99.9% uptime

NFR2: Data consistency should be eventual consistency

NFR3: Storage should scale horizontally

NFR4: Latency target: p99 < 50ms for reads and writes

NFR5: Support up to 1000 concurrent clients

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Client API layer

Storage engine (in-memory or disk-based)

Indexing mechanism for fast key lookup

Replication module for data durability

Cache layer for hot keys

Load balancer or proxy for request distribution

Design Patterns

Sharding to distribute keys across nodes

Replication for fault tolerance

Consistent hashing for key distribution

Write-ahead logging for durability

Cache aside pattern for read optimization

Reference Architecture

Client(s)
   |
Load Balancer / Proxy
   |
+-------------------------+
|       KV Store Cluster   |
| +-------+  +-------+     |
| | Node1 |  | Node2 | ... |
| +-------+  +-------+     |
+-------------------------+
   |
Persistent Storage (Disk)

Components

Client API

REST/gRPC

Interface for clients to perform put, get, delete operations

Load Balancer / Proxy

Nginx or custom proxy

Distributes client requests to KV nodes based on consistent hashing

KV Store Nodes

In-memory store with disk persistence (e.g., RocksDB)

Store key-value pairs, handle requests, replicate data

Replication Module

Asynchronous replication protocol

Replicates data to other nodes for durability and availability

Persistent Storage

SSD-backed storage

Durable storage of data with write-ahead logging

Request Flow

1. Client sends put/get/delete request to Load Balancer

2. Load Balancer uses consistent hashing on key to select KV node

3. KV node processes request:

4. - For put: store key-value in memory and write-ahead log, then replicate asynchronously

5. - For get: check in-memory store and return value

6. - For delete: remove key from store and replicate deletion

7. KV node acknowledges client after local write (for put/delete) or returns value (for get)

8. Replication module sends updates to replica nodes asynchronously

9. Replica nodes apply updates to maintain eventual consistency

Database Schema

Entity: KeyValue Attributes: key (string, primary), value (blob), timestamp (for versioning) Relationships: None (flat key-value pairs) Indexes: Primary index on key for fast lookup

Scaling Discussion

Bottlenecks

Single node storage capacity limits total data size

Load balancer can become a bottleneck under high concurrency

Replication lag can cause stale reads

Disk I/O limits write throughput

Memory limits in-memory cache size

Solutions

Use sharding with consistent hashing to distribute keys across multiple nodes

Deploy multiple load balancers with DNS round-robin or anycast

Implement quorum-based reads/writes for stronger consistency if needed

Use SSDs and optimize write-ahead logging for faster disk writes

Implement cache eviction policies and tiered storage to manage memory

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 15 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, 10 minutes for questions and wrap-up.

Clarify consistency and durability requirements early

Explain choice of consistent hashing for key distribution

Discuss replication strategy and its impact on availability

Highlight how latency targets influence design choices

Mention trade-offs between strong and eventual consistency

Address scaling challenges and mitigation strategies

Practice

1. What is the primary purpose of a key-value store in system design?

easy

A. To perform complex relational queries

B. To store large binary files efficiently

C. To save data as pairs for quick lookup

D. To manage user authentication and sessions

Solution

1. Step 1: Understand key-value store basics

   A key-value store saves data as pairs where each key maps to a value for fast retrieval.

2. Step 2: Compare with other storage types

   Unlike relational databases, key-value stores do not support complex queries or file storage.

3. Final Answer:

   To save data as pairs for quick lookup -> Option C

4. Quick Check:

   Key-value store = data pairs [OK]

Hint: Key-value stores focus on pairs, not complex queries [OK]

Common Mistakes:

• Confusing key-value store with relational database
• Thinking it handles large files natively
• Assuming it manages user sessions directly

2. Which of the following is the correct operation to add or update a value in a key-value store?

easy

A. exists(key)

B. put(key, value)

C. delete(key)

D. get(key)

Solution

1. Step 1: Identify operation purpose

   Adding or updating a value requires an operation that sets the value for a key.

2. Step 2: Match operation names

   "put" is commonly used to insert or update key-value pairs; "get" retrieves, "delete" removes, "exists" checks presence.

3. Final Answer:

   put(key, value) -> Option B

4. Quick Check:

   Put = add/update [OK]

Hint: Put means add or update a key-value pair [OK]

Common Mistakes:

• Using get to add data
• Confusing delete with update
• Using exists to insert values

3. Given this pseudo-code for a key-value store:

store = {}
store.put('a', 1)
store.put('b', 2)
store.put('a', 3)
value = store.get('a')

What is the value of value after these operations?

medium

A. 3

B. 2

C. 1

D. None

Solution

1. Step 1: Track put operations

   First, key 'a' is set to 1, then 'b' to 2, then 'a' is updated to 3, overwriting previous value.

2. Step 2: Retrieve the value for 'a'

   The last value assigned to 'a' is 3, so store.get('a') returns 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Last put for 'a' = 3 [OK]

Hint: Last put for a key overwrites previous value [OK]

Common Mistakes:

• Assuming first value stays after update
• Confusing keys 'a' and 'b'
• Thinking get returns None if key exists

4. Consider this code snippet for a key-value store:

store = {}
def get_value(key):
    if key in store:
        return store[key]
    else:
        return None

store.put('x', 10)
print(get_value('x'))

What is the main issue preventing this code from working correctly?

medium

A. The put method is not defined for the dictionary

B. The get_value function returns None incorrectly

C. The key 'x' is not added to the store

D. The print statement syntax is wrong

Solution

1. Step 1: Check dictionary operations

   Python dictionaries do not have a put method; they use assignment like store[key] = value.

2. Step 2: Identify error cause

   Calling store.put('x', 10) will cause an AttributeError because put is undefined.

3. Final Answer:

   The put method is not defined for the dictionary -> Option A

4. Quick Check:

   Dicts use assignment, not put [OK]

Hint: Dictionaries use assignment, not put() method [OK]

Common Mistakes:

• Assuming put exists on dict
• Ignoring error from undefined method
• Thinking get_value logic is faulty

5. You want to design a scalable key-value store that handles millions of requests per second. Which design choice best supports this goal?

hard

A. Use a single in-memory dictionary on one server

B. Store all data on a single disk-based database

C. Use a relational database with complex joins

D. Partition data across multiple servers using consistent hashing

Solution

1. Step 1: Understand scalability needs

   Handling millions of requests requires distributing load and data to avoid bottlenecks.

2. Step 2: Evaluate design options

   A single in-memory dictionary or disk-based DB limits capacity; relational DB with joins is slow for key-value access. Consistent hashing partitions data evenly across servers, enabling horizontal scaling.

3. Final Answer:

   Partition data across multiple servers using consistent hashing -> Option D

4. Quick Check:

   Consistent hashing = scalable partitioning [OK]

Hint: Distribute data with consistent hashing for scalability [OK]

Common Mistakes:

• Relying on single server limits throughput
• Using disk-based DB slows access
• Choosing relational DB for simple key-value