How would you scale a key-value store toward ~1M requests/sec

• Partitioning – data is divided across nodes using consistent hashing with virtual nodes so each node owns a distinct slice of the keyspace.
• Routing – a coordinator, smart client, or gossip-based membership ensures each request reaches the node that owns its key.
• Replication – each key is stored on N successive ring nodes for availability and read scaling, with quorum parameters (R + W > N) for consistency.
• Capacity planning – target TPS divided by per-node throughput gives the node count, multiplied by the replication factor and headroom for peak.
• Hot-key handling – caching, extra replicas, sub-key sharding, and per-key rate limiting prevent one key from overwhelming one node.
• Node-failure behaviour – surviving replicas serve traffic, gossip marks the node down, and hinted handoff delivers missed writes on recovery.

Why is "add more servers" insufficient?

A key-value store's capacity only grows if both data and traffic are spread across nodes. Adding servers without partitioning means they hold no data and receive no requests, so throughput does not rise. Even with partitioning, raw server count does nothing about a single hot key whose traffic all lands on one node, or about what happens when a node dies.

How do you partition the data?

Consistent hashing with virtual nodes on a ring divides the keyspace. Each key is hashed to a ring position and assigned to the next node clockwise. Virtual nodes keep the per-node load even and let you weight bigger machines.

package com.bank.kvstore;

import java.util.TreeMap;

public class PartitionRouter {
    private final TreeMap<Integer, String> ring = new TreeMap<>();

    public void addNode(String node, int vnodes) {
        for (int i = 0; i < vnodes; i++) {
            int hash = (node + "-vn" + i).hashCode() & 0x7FFFFFFF;
            ring.put(hash, node);
        }
    }

    public String nodeFor(String key) {
        int hash = key.hashCode() & 0x7FFFFFFF;
        var tail = ring.tailMap(hash);
        return ring.get(tail.isEmpty() ? ring.firstKey() : tail.firstKey());
    }
}

How is a request routed to the right node?

There are three models. A coordinator receives every request, computes the owning node from the ring, and forwards it. A smart client holds the ring topology and routes directly, saving a hop. Or any node acts as a coordinator and forwards internally (Dynamo style). The routing must stay consistent with the current ring via gossip.

How does replication provide availability?

Each key is stored on the N successive nodes clockwise on the ring (e.g., replication factor 3). Quorum reads and writes require W replicas to acknowledge a write and R replicas for a read such that R + W > N, guaranteeing a read sees the latest write while tolerating some node failures.

package com.bank.kvstore;

import java.math.BigDecimal;
import java.util.List;

public class QuorumClient {
    private final int replicationFactor = 3; // N
    private final int writeQuorum = 2;       // W
    private final int readQuorum = 2;        // R (R+W > N)

    public void put(String key, BigDecimal balance, List<Node> replicas) {
        int acks = 0;
        for (Node node : replicas) {
            if (node.write(key, balance)) acks++;
            if (acks >= writeQuorum) return; // success
        }
        throw new RuntimeException("Write quorum not met");
    }

    public BigDecimal get(String key, List<Node> replicas) {
        int responses = 0;
        BigDecimal latest = null;
        for (Node node : replicas) {
            BigDecimal val = node.read(key);
            if (val != null) {
                responses++;
                if (latest == null || node.timestamp(key) > 0) latest = val;
            }
            if (responses >= readQuorum) return latest;
        }
        throw new RuntimeException("Read quorum not met");
    }
}

How do you plan capacity?

Start from the budget: 1M requests/sec at a target latency, with a read-to-write ratio. If one tuned node sustains 100K ops/sec, you need at least 10 nodes for throughput, then multiply by the replication factor (3 replicas = 30 nodes of storage), add headroom for peak bursts (e.g., 1.5x), and add spare capacity for failover.

How do you handle hot keys?

A single popular key (e.g., a viral merchant account) sends all traffic to one node regardless of cluster size.

• Cache the hot key in a local or distributed cache so most reads never reach the owning node.
• Replicate the hot key to extra nodes and spread reads across them.
• Shard a hot counter into sub-keys and aggregate: balance:SAV2001:0, balance:SAV2001:1, etc.
• Per-key rate limiting so one key cannot starve others.

// Sub-key sharding for a hot counter
public class ShardedCounter {
    private static final int SHARDS = 8;

    public void increment(String key, int delta, KVStore store) {
        int shard = ThreadLocalRandom.current().nextInt(SHARDS);
        String subKey = key + ":" + shard;
        store.increment(subKey, delta);
    }

    public long total(String key, KVStore store) {
        long sum = 0;
        for (int i = 0; i < SHARDS; i++) {
            sum += store.getLong(key + ":" + i);
        }
        return sum;
    }
}

What happens when a node fails?

With replication factor 3, two other copies still serve the key's reads. The ring membership is updated via gossip, routing stops sending traffic to the dead node, and its share of load redistributes to peers. When the node recovers, it catches up through a throttled background transfer with hinted handoff delivering writes it missed.

What should a senior engineer know?

• Separate the control plane (membership, topology) from the data plane so topology churn does not stall requests.
• Pick quorum parameters to match the consistency each use case needs: a balance lookup and a like counter tolerate different staleness.
• Put a caching tier in front for read-heavy and hot-key traffic.
• Monitor per-node and per-key metrics so skew and failures are detected quickly.