Design Redis

Problem Statement

Design an in-memory key-value store like Redis that supports fast data operations with key expiration, starting with a single-node implementation and then expanding to a distributed system.

Redis is an in-memory key-value data store used for ultra-fast reads/writes, atomic counters, and caching with key expiration. Think of it as a blazingly fast dictionary that also supports features like time-to-live (TTL), simple transactions, and replication. Many large-scale systems rely on Redis-style primitives to keep latency low and throughput high.

Interviewers ask you to design Redis to test your ability to make disciplined data structure choices, reason about thread safety and contention, and balance latency against durability and memory constraints. After the single-node design, they typically push into sharding, replication, and failover to see if you can evolve a clean, high-performance core into a fault-tolerant distributed system.

Key Requirements

Functional

• Key-value operations -- set, get, and delete keys with sub-millisecond latency for small values
• Key expiration -- set keys with an optional TTL and have expired keys become unavailable after their expiration
• Atomic operations -- perform atomic operations on values (INCR/DECR, compare-and-set) to avoid race conditions
• Distributed scaling -- scale to multiple nodes with partitioning and replication while preserving correctness and predictable performance

Non-Functional

• Scalability -- handle millions of keys across a distributed cluster with thousands of operations per second per node
• Reliability -- maintain data durability through persistence options (snapshots, append-only logs) and automatic failover on node failure
• Latency -- P99 read and write latency under 1ms for single-node operations; under 5ms for cross-shard operations
• Consistency -- strong consistency within a single shard; configurable consistency levels across replicas

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Single-Node Data Structures and Concurrency Model

The foundational challenge is choosing a concurrency model that delivers sub-millisecond latency without sacrificing throughput. Interviewers want to see whether you understand why Redis chose a single-threaded event loop and the tradeoffs involved.

Hints to consider:

• A single-threaded event loop with non-blocking I/O avoids lock contention entirely and simplifies atomic operations
• Consider how different data structures (hash tables, skip lists, zip lists) serve different access patterns and memory profiles
• Discuss the tradeoff between a single-threaded model (simpler, no contention) and per-core sharding (higher throughput)
• Explain how to handle slow commands that could block the event loop, such as large key scans or persistence operations

2. Key Expiration Strategy

Naive expiration approaches like full keyspace scans or a single global min-heap create latency spikes. Interviewers expect a combined strategy that keeps P99 stable under load.

Hints to consider:

• Combine lazy expiration (check TTL on access) with active expiration (periodic sampling of keys with TTLs)
• For active expiration, randomly sample a small batch of keys with TTLs each cycle and delete expired ones; repeat if the expiration rate exceeds a threshold
• Use per-bucket or sharded timer wheels to avoid a single global priority queue bottleneck
• Discuss memory reclamation strategies and how expired keys affect memory reporting

3. Persistence and Durability

An in-memory store risks total data loss on crash. Interviewers expect you to discuss persistence strategies and their impact on the hot path.

Hints to consider:

• RDB snapshots provide point-in-time backups via fork and copy-on-write, with minimal impact on the main thread
• AOF (append-only file) logs every write command for replay-based recovery, with configurable fsync policies (every command, every second, OS-managed)
• Discuss the tradeoff between fsync frequency and write latency -- fsync on every write guarantees durability but adds milliseconds
• Consider hybrid approaches: AOF for recent writes plus periodic RDB snapshots for fast bulk recovery

4. Sharding, Replication, and Failover

Scaling beyond a single node requires partitioning the keyspace and replicating data for fault tolerance. Interviewers probe the details of slot mapping, rebalancing, and leader election.

Hints to consider:

• Use hash slots (e.g., 16384 slots like Redis Cluster) with consistent hashing to distribute keys across nodes
• Each slot has a primary and one or more replicas; replicas apply the replication stream asynchronously
• Online resharding moves slots between nodes by streaming keys while the cluster continues serving traffic
• Implement leader election via a consensus system (Raft, ZooKeeper) so replicas can promote automatically when a primary fails

Suggested Approach

Step 1: Clarify Requirements

Start by confirming the scope. Ask whether the system needs to support only simple key-value operations or also complex data types like lists, sets, and sorted sets. Clarify the expected data size per key, total keyspace size, and read/write ratio. Determine durability requirements: is some data loss acceptable on crash, or must every write be persisted? Ask about multi-tenancy, access control, and whether clients need pub/sub or transaction support. Confirm whether the distributed design should prioritize availability or consistency during network partitions.

Step 2: High-Level Architecture

Sketch a single-node architecture first: a network layer using epoll/kqueue for multiplexed I/O, a command parser, a single-threaded event loop that processes commands against an in-memory hash table, and background threads for persistence (RDB snapshots, AOF rewriting). Then expand to a cluster: show multiple nodes each owning a subset of hash slots, with clients using a slot-aware routing library. Add replica nodes that follow their primaries via replication streams. Include a cluster bus for gossip-based failure detection and slot metadata propagation. Show a ZooKeeper or Raft-based coordinator for authoritative slot assignments and failover orchestration.

Step 3: Deep Dive on Core Operations and Expiration

Walk through the critical path of a SET command with TTL. The client sends the command to the correct node (determined by hashing the key to a slot). The event loop reads the command from the socket buffer, parses it, inserts or updates the key in the hash table, and records the TTL in a separate expiry dictionary keyed by absolute timestamp. The command is appended to the AOF buffer and acknowledged to the client. For expiration, explain the dual strategy: on every key access, check the expiry dictionary and return a miss if expired (lazy); every 100ms, sample 20 random keys from the expiry dictionary and delete those that have expired, repeating the cycle if more than 25% were expired (active). Discuss how this bounded, probabilistic cleanup keeps memory usage reasonable without causing latency spikes.

Step 4: Address Secondary Concerns

Cover replication: the primary streams its AOF to replicas, which replay commands to maintain an eventually consistent copy. Discuss replication lag and how clients can route reads to replicas for scale while accepting slightly stale data. Address memory management: set a maxmemory limit with eviction policies (LRU, LFU, random, volatile-ttl) to handle memory pressure gracefully. Explain monitoring: expose metrics for memory usage, command latency histograms, replication lag, and keyspace hit/miss ratios. Touch on security: require authentication, support TLS for in-transit encryption, and implement ACLs for multi-tenant access control. Finally, discuss client-side caching with server-assisted invalidation to reduce read load on the cluster.

Related Learning

Deepen your understanding of the patterns used in this problem:

• Distributed Cache -- distributed caching architecture with eviction policies, consistency, and replication
• Job Scheduler -- scheduling patterns applicable to background expiration and persistence tasks
• Caching -- cache layers, eviction strategies, and write-through versus write-behind patterns
• Databases -- persistence models, replication topologies, and partitioning strategies
• Message Queues -- replication streams and pub/sub messaging for cluster coordination