Key-Value Store (Redis, Memcached — O(1) Lookups)

Tier 1 — Building Block

1. What Is It?

A key-value store is the simplest form of a database: it maps opaque string keys to arbitrary byte-value payloads, with O(1) (constant-time, regardless of how much data is stored) average-time GET and SET operations. There is no schema, no query language, no joins — just PUT(key, value) and GET(key).

The reason they matter: a hash table in RAM is the fastest data structure for point lookups. Redis and Memcached keep their entire dataset in memory, achieving ~100K–1M operations per second at sub-millisecond latency — orders of magnitude faster than a disk-based relational database. Any system with a read-heavy workload and a hot set of frequently accessed data benefits from a key-value store in front of the primary database.

Beyond simple string caches, Redis extends the model with richer data structures (sorted sets, hashes, pub/sub streams), enabling use cases like leaderboards, session stores, rate limiters, distributed locks, and message queues — all with the same sub-millisecond SLA.

2. How It Works

Core Data Path

-+ResetFullscreen

Hash Table Mechanics

Both Redis and Memcached use an open-addressed or chained hash table internally. For each key:

1. Compute hash(key) → bucket index
2. Follow bucket chain / probe to find or insert the entry
3. Return the value or nil

Average case: O(1). Worst case (hash collision storm): O(N) — mitigated by good hash functions (Redis uses SipHash for security; Memcached uses Jenkins hash).

Redis Data Structures

Redis extends beyond simple string → string mapping:

Redis Persistence Modes

-+ResetFullscreen

Eviction Policies (when memory is full)

3. Variants & Comparisons

Redis Cluster Architecture:

-+ResetFullscreen

4. When to Use It (and When NOT To)

Use a Key-Value Store When:

• Session store: HTTP sessions mapped by session_id → user_data JSON. Fast O(1) lookup; TTL-based expiry for automatic cleanup.
• Cache: product:123 → serialized product JSON. Cache-aside pattern in front of a PostgreSQL or MySQL DB.
• Distributed rate limiter: rate:user:123 → INCR counter with TTL. Redis INCR is atomic — safe for concurrent rate limiting across multiple app servers.
• Distributed lock: Redis SETNX (set if not exists) + TTL implements a basic distributed mutex. More robust: Redlock algorithm across multiple Redis nodes.
• Leaderboard: ZADD leaderboard <score> <user_id> with sorted set. ZRANGE leaderboard 0 9 REV WITHSCORES for top 10 in O(log N + K).
• Pub/Sub / lightweight message queue: Redis Streams or PubSub for event broadcasting within a service mesh (not as durable as Kafka).

Decision triggers:

• "If you have a hot read path hitting the DB > 1000 QPS with the same keys → add Redis cache-aside"
• "If you need distributed rate limiting across multiple app servers → Redis INCR + TTL"
• "If you need a real-time leaderboard → Redis Sorted Set"

Do NOT Use a Key-Value Store When:

• Complex queries needed: Any JOIN, aggregate, range scan, or full-text search. Key-value stores have no query language — use a relational DB or search engine.
• Strong ACID transactions across multiple keys: Redis has MULTI/EXEC (optimistic transactions), but it's not equivalent to database ACID. For financial records, use PostgreSQL.
• Primary durable store for critical data without a backup DB: Redis persistence (AOF) can still lose data. Use a relational DB as the source of truth; Redis as a cache/secondary store.
• Large values: Storing 10MB blobs per key wastes memory fast. Redis is cost-effective for small-to-medium values (< 10KB per key is typical).

Anti-patterns:

• Storing too much in one key: A hash key with 10M fields degrades to O(N) for HGETALL. Design keys to be small and focused.
• No TTL on cache keys: Memory fills up permanently. Always set a TTL on cached data.
• Redlock for linearizability: Redlock provides distributed mutex semantics but NOT linearizability guarantees. For true distributed coordination, use ZooKeeper or etcd (CP systems).
• Using Redis as primary DB without understanding persistence: Default Redis config has no persistence. A restart = all data gone. Explicitly configure AOF or RDB for production.

5. Real-World Usage

Twitter (Redis for timelines): Twitter stores pre-computed home timelines as Redis lists. For active users, the most recent ~800 tweet IDs are stored in memory. LPUSH timeline:user_id tweet_id on write (fan-out); LRANGE timeline:user_id 0 19 for the first page of 20 tweets. Sub-millisecond latency for timeline reads, serving ~300K timeline reads/sec at peak.

Stack Overflow (Redis for everything): Stack Overflow uses Redis for session storage, rate limiting, distributed locking, real-time view counts, and question score counts. Their architecture paper notes they serve the entire site from a few high-memory Redis instances with ~99.9% of requests hitting Redis before the DB. Their Redis hit rate exceeds 99% for most endpoints.

Discord (Redis for presence): Discord stores online/offline presence for 500M+ users using Redis. User presence is a Redis hash (HSET presence:user_id status online device mobile). Redis TTL-based expiry handles automatic offline detection when heartbeats stop. Redis Pub/Sub broadcasts presence changes to subscribed guild channels. At scale, Discord shards presence Redis across hundreds of nodes.

6. Interview Cheat Sheet

Key sentences to demonstrate depth:

1. "Redis gives you O(1) average GET/SET at sub-millisecond latency by keeping the entire dataset in memory — 100K–200K ops/sec per shard, scaling linearly with Redis Cluster."
2. "Beyond simple caching, Redis's rich data types unlock use cases a plain key-value cache can't do: sorted sets for leaderboards, atomic INCR for rate limiting, and SETNX for distributed locks."
3. "Redis vs. Memcached: Memcached wins on raw throughput for simple string caching (multi-threaded); Redis wins on everything else — persistence, replication, rich data types. Default to Redis unless you have benchmarked a bottleneck Memcached solves."
4. "For production, I'd use AOF + RDB hybrid persistence with Redis Sentinel for HA — async replication with automatic failover in ~30 seconds if the primary goes down."
5. "Memory is the constraint. At ~$6/GB/month for managed Redis, a 10GB instance costs ~$720/year — much cheaper than DB compute for the same QPS. But I'd design to keep individual values small (<10KB) and always set TTLs."

Common follow-up questions:

Connections to other building blocks:

• Caching Strategies: Redis is the most common implementation of cache-aside, write-through, and write-back caching patterns.
• Consistent Hashing: Redis Cluster uses a variant of consistent hashing with 16,384 fixed hash slots. Memcached uses client-side consistent hashing via twemproxy or ketama.
• Rate Limiter: Redis is the standard backend for distributed rate limiters due to atomic INCR and TTL operations.
• Distributed Locking: Redis SETNX + TTL is the basic distributed lock. Redlock uses multiple Redis nodes for higher reliability.
• Message Queues: Redis Streams provide lightweight pub/sub and consumer group semantics — simpler than Kafka for low-volume event broadcasting.