In-Memory KV Store with Sliding-Window QPS Metrics

0) Problem Restatement

Build an in-memory key-value store with get(key), put(key, value) and delete(key), plus methods that report the store's recent load:

• get_qps() / put_qps(): how many get and put calls happened in the last 5 minutes (or the average per second over that window).

Many threads call the store at the same time. Databricks asked this twice: once as an in-memory LLD with concurrency focus, and once asking how it would become a scalable, highly available store with real-time QPS reporting.

1) Requirements

• get, put, delete: O(1).
• count_last(window=300s) per operation type, which should be O(window) or better, not O(number of requests).
• Thread-safe, with low overhead on the hot path (the metrics must not slow the store down much).
• Bounded memory for metrics.

2) Design

• Store: a hash map, sharded into N segments, each with its own lock, to reduce contention (like Java's ConcurrentHashMap).
• Metrics: a ring buffer of 300 per-second buckets per operation type. Each bucket stores (second, count).
• To record: compute now_sec, index i = now_sec % 300. If bucket[i].second != now_sec, it holds old data, so reset it to (now_sec, 0). Then increment.
• To query: sum buckets whose second is within [now - 299, now].
• Memory: 300 buckets, regardless of traffic.

Why not store a timestamp per request? At 100K requests/sec that's 30M timestamps in 5 minutes. Buckets trade a tiny bit of precision (1 second) for fixed memory.

flowchart LR
    T["Client threads"] --> KV["Sharded hash map - lock per shard"]
    T --> M["Metrics recorder"]
    M --> RB["Ring buffer - 300 x 1-second buckets per op"]
    Q["get_qps / put_qps"] --> RB

3) Code (Python)

import threading, time

class RollingCounter:
    def __init__(self, window=300):
        self.window = window
        self.secs = [0] * window
        self.counts = [0] * window
        self.lock = threading.Lock()

    def add(self, now=None):
        s = int(now if now is not None else time.time())
        i = s % self.window
        with self.lock:
            if self.secs[i] != s:          # bucket holds an old second: reset it
                self.secs[i], self.counts[i] = s, 0
            self.counts[i] += 1

    def total(self, now=None):
        s = int(now if now is not None else time.time())
        with self.lock:
            return sum(c for sec, c in zip(self.secs, self.counts) if s - self.window < sec <= s)

class KVStore:
    def __init__(self, shards=16, window=300):
        self.shards = [({}, threading.Lock()) for _ in range(shards)]
        self.metrics = {op: RollingCounter(window) for op in ("get", "put", "delete")}

    def _shard(self, key):
        return self.shards[hash(key) % len(self.shards)]

    def put(self, key, value):
        self.metrics["put"].add()
        data, lock = self._shard(key)
        with lock:
            data[key] = value

    def get(self, key):
        self.metrics["get"].add()
        data, lock = self._shard(key)
        with lock:
            return data.get(key)

    def delete(self, key):
        self.metrics["delete"].add()
        data, lock = self._shard(key)
        with lock:
            data.pop(key, None)

    def qps(self, op, window=300):
        return self.metrics[op].total() / window

4) Reducing Contention on the Metrics

Every operation touches the metrics lock, which becomes the bottleneck under heavy load. Options:

• Striped counters: keep K ring buffers (e.g., one per CPU core, or pick by thread ID) and sum them when querying. Writes rarely collide. (Java's LongAdder uses this idea.)
• Atomic increments instead of locks for the count, handling the bucket reset carefully (compare-and-swap on the bucket's second).
• Queries are rare compared to writes, so making reads do more work (summing stripes) is a good trade.

5) Precision Options

• 1-second buckets over 300 seconds: the window edge is fuzzy by up to 1 second. Fine for monitoring.
• Need finer precision at the edge? Use 100 ms buckets (3,000 buckets), which uses more memory but is still fixed.
• An exact sliding window needs per-request timestamps (a deque per stripe, trimmed on each insert). Memory then grows with traffic.

6) Making It Distributed and Highly Available

• Partition keys across nodes with consistent hashing, and replicate each partition (e.g., 3 replicas, leader-based or quorum). See the distributed KV store design.
• Cluster-wide QPS: each node keeps its own rolling counters and exports per-second counts to a metrics system (e.g., a Prometheus scrape every 10s, or pushing to a time-series DB). Cluster QPS = the sum across nodes, computed by the metrics system, not by every node talking to every other node.
• For a live admin API, a coordinator can ask all nodes for their last-5-minute totals and add them up (fine for occasional queries).

7) Wrap-Up

Store data in a sharded hash map with a lock per shard, and count operations in a fixed ring buffer of 300 one-second buckets that reset themselves when reused, so memory stays constant and a 5-minute count is a sum of buckets. Reduce contention with striped counters summed at query time, choose bucket size for the precision you need, and in a distributed store keep counters per node and aggregate them in a metrics system.