Distributed Key-Value Storage

What's being tested

Interviewers are probing your ability to design a practical, reliable distributed key-value store that meets ML-serving needs: low-latency reads for features/embeddings, correctness of feature freshness (offline vs online parity), and operational trade-offs (consistency, replication, capacity, and monitoring). They want to see clear assumptions, an architecture addressing ML-specific access patterns, and how you reason about failures, rollback, and rollout for models that depend on this storage.

Core knowledge

• Workload characteristics: ML serving is typically read-heavy (reads:writes can be 100:1–1000:1), with tiny keys (IDs) and values that can be scalars, feature vectors, or embeddings (values 8B–1MB). Design to optimize for high read throughput and low tail latency (p99).

• Capacity math: total_storage_bytes = N_keys × avg_value_size × replication_factor. Include index/metadata overhead (~10–30%). Example: 100M keys × 1 KB × 3 → ~300 GB + overhead.

• Replication vs consistency: choose between strong consistency (leader-based, Raft/Paxos) and eventual consistency (Dynamo-style). ML-serving often tolerates slight staleness for features but requires read-after-write guarantees for label stores or online feature writes.

• Partitioning (sharding): use consistent hashing or range sharding to distribute keys and enable re-sharding with minimal movement. Hot-key mitigation (tokenization, hashing with salt) is essential for skew (Zipfian) access.

• Storage engines: for low-latency reads use in-memory stores (Redis, memcached), for large persistent KV use Cassandra/Scylla/Bigtable or local RocksDB backed services. Hybrid: local RocksDB + remote replication for cold storage.

• Indexing & lookup: avoid secondary indexes in simple KV stores; if you need attribute queries, use a separate index service. For embeddings, consider vector index (HNSW) separate from scalar feature KV.

• Serialization & schema: use compact binary formats (Protobuf, Avro) and include schema version and value TTL. Provide backwards-compatible readers for model rollouts.

• Feature freshness & time travel: support versioned keys or event-time stamped values to reproduce training-time feature views and ensure offline/online parity. Tag writes with ingestion timestamp and feature version.

• Caching & warmups: introduce a multi-tier cache (edge cache + local per-node cache). Tune TTLs per feature freshness guarantees; pre-warm caches during rollouts to avoid cold-start performance cliffs.

• Atomicity & multi-key updates: for multi-feature atomicity (all-or-none updates), either use transactional primitives (rare in distributed KV) or implement versioned bundles and read the latest consistent bundle.

• Monitoring & SLOs: instrument latency (median, p95, p99), error rate, cache hit-rate, eviction rate, and replication lag. Set SLOs for end-to-end ML request latency and degrade gracefully (fallback features/flags).

• Failure modes & recovery: handle node failure, network partition, and data corruption. Plan for repair (read-repair, anti-entropy), compaction, and backup/restore workflows. Consider how stale or missing features affect model outputs and user-facing metrics.

Worked example — "Design a distributed key-value store"

Start by clarifying scope and SLAs: ask about expected QPS, read/write ratio, p99 latency target, dataset size, and whether strong consistency is required for online writes. Declare assumptions: e.g., 10k QPS, 99.99% reads, 500M keys, p99 ≤ 10 ms, replication factor 3.

Organize the design into pillars: (1) partitioning & data placement with consistent hashing and hot-key mitigation; (2) replication & consistency model — choose leader replication with asynchronous replicas for reads, accept eventual consistency for features but enforce leader reads for label writes; (3) storage engine & caching — edge cache (CDN or local LRU) + persistent store (Cassandra or local RocksDB per node); (4) operational guarantees — monitoring, backups, schema versioning, and migration plan.

Flag tradeoff: choosing asynchronous replication reduces write latency but risks replication lag and stale features; mitigate by adding per-key version and letting model fetch the version or fall back to last-known-good. For rollout, stage migration by traffic percentage and pre-warm caches.

Close with next steps: if more time, design a concrete API (GET/PUT/GET-MANY), show failure-handling sequences (leader failover), sketch capacity diagrams, and write benchmarking scenarios to validate p99.

A second angle

Now assume the same store must host high-dimensional embeddings (512-d float vectors) for nearest-neighbor lookup in addition to scalar features. This changes constraints: value sizes increase (~2 KB per vector), storage and network cost rise, and read throughput per query may include bulk fetches (top-N lookups). You’d separate concerns: keep embeddings in a purpose-built vector store or a shard optimized for large values, enable compression (quantization, int8), and add batching APIs (GET_BATCH) to reduce RPC overhead. Also prioritize bandwidth-aware replication and prefetching; for model-serving, accept slightly higher latency for ANN searches but ensure deterministic fallbacks when the vector store is temporarily unavailable.

Common pitfalls

Pitfall: Designing for perfect consistency by default.
Assuming strong consistency everywhere increases latency and operational complexity; instead, pick per-data-class consistency based on how errors propagate to model outputs.

Pitfall: Ignoring tail latency sources.
Focusing on average latency hides p99 issues caused by GC, head-of-line blocking, and network spikes—these directly harm real-time model serving.

Pitfall: Treating feature store like a generic DB.
Using generic secondary indexes or cross-partition transactions for fast feature joins leads to brittle deployments. Prefer pre-joined feature bundles or versioned feature vectors for serving.

Connections

This topic commonly pivots to feature store design, online vs offline feature parity, or model serving architectures (e.g., embedding servers and model inference caches). Interviewers may also ask about monitoring-driven retraining pipelines (drift detection) or efficient bulk import for training offline replicas.

Further reading

• Dynamo: Amazon’s Highly Available Key-value Store — foundational tradeoffs between availability and consistency.

• Designing Data-Intensive Applications — chapters on replication, partitioning, and storage engines; practical for system tradeoffs relevant to ML serving.