Design a key-value store in HLD - Scalability & System Analysis

Scalability Analysis - Design a key-value store

Growth Table: Key-Value Store Scaling

Users / Requests	100 Users	10K Users	1M Users	100M Users
Requests per second (QPS)	~100	~10,000	~1,000,000	~100,000,000
Data size	~10 GB	~1 TB	~100 TB	~10 PB
Number of servers	1-2	10-20	100-200	10,000+
Latency	<1 ms	<5 ms	<10 ms	<20 ms
Storage type	SSD local	Distributed SSD	Sharded distributed storage	Multi-region distributed storage
Replication	Simple master-slave	Multi-replica for availability	Geo-replication	Global replication with consistency

First Bottleneck

At small scale (100 users), the database server CPU and disk I/O are the first bottlenecks because a single server handles all requests and data.

At medium scale (10K to 1M users), the database query throughput and network bandwidth become bottlenecks as requests increase beyond a single server's capacity.

At large scale (100M users), data partitioning and cross-region replication latency become bottlenecks due to massive data size and global distribution.

Scaling Solutions

• Vertical scaling: Upgrade server CPU, RAM, and SSDs for small scale.
• Horizontal scaling: Add more servers behind a load balancer to distribute requests.
• Sharding: Split data by key ranges or hash to distribute storage and load across servers.
• Caching: Use in-memory caches (e.g., Redis) to reduce database load for frequent reads.
• Replication: Use master-slave or multi-master replication for availability and read scaling.
• Consistent hashing: To minimize data movement when scaling out or in.
• Geo-distribution: Deploy data centers closer to users to reduce latency at large scale.

Back-of-Envelope Cost Analysis

• At 1M QPS, assuming 1KB per request, bandwidth needed is ~1 GB/s (8 Gbps).
• Storage for 100 TB data requires multiple SSD servers; each SSD ~4 TB, so ~25 servers minimum.
• Each server handles ~5,000 QPS; for 1M QPS, need ~200 servers.
• Network infrastructure must support high throughput and low latency.
• Replication doubles storage and bandwidth needs.

Interview Tip

Start by clarifying requirements: data size, read/write ratio, latency needs.

Discuss simple design first, then identify bottlenecks as scale grows.

Explain how each scaling solution addresses specific bottlenecks.

Use real numbers to justify design choices and trade-offs.

Self Check Question

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Add read replicas and implement caching to reduce load on the primary database before scaling vertically or sharding.

Key Result

A key-value store scales by starting with vertical scaling and simple replication, then moves to horizontal scaling with sharding and caching as traffic and data grow, addressing bottlenecks in database throughput, storage, and network bandwidth.

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