Partitioning, hot keys and caching

Why it matters

Once data or traffic outgrows one machine you split it, and the split decides which queries are cheap, which are expensive and which machine melts when one customer goes viral. Caches then hide most reads from the store, until they fail, go cold or serve stale data. In a design interview, "how would you shard this?" and "what would you cache, and how do you keep it correct?" arise naturally, and the follow-ups concern skew and failure, not the happy path.

Core ideas

Range versus hash partitioning. Range partitioning keeps keys sorted, so range scans touch few partitions, but sequential keys (timestamps, auto-increment IDs) pile writes onto one partition. Hash partitioning spreads keys evenly and keeps point lookups cheap, at the price of range locality. A compound key (hash of a user ID, then a sorted timestamp within it) often gets both: even spread across users and efficient scans within one user.

Consistent hashing. Hash-mod-N remaps almost every key when N changes. Placing nodes and keys on a hash ring, with each key owned by the next node clockwise, means a join or leave moves only about 1/N of the keys. Virtual nodes (many ring positions per machine) smooth out uneven arcs, let a machine's share follow its capacity, and spread a failed node's load over many survivors instead of one neighbor. Another common approach is a fixed number of partitions, much larger than the node count, moved whole between nodes; both avoid mass reshuffling.

Hot keys. No hash function splits a single key. Options: append a small random suffix to spread writes for a hot key across sub-keys (and merge on read), replicate hot read-mostly keys to several cache nodes, cache them briefly inside application servers, and coalesce identical concurrent requests. Detect hotness with per-key sampling; averages hide it.

Cache policies.

• Cache-aside: the application reads the cache; on a miss it reads the store and fills the cache; on a write it updates the store and deletes the entry. Simple; the consistency races are yours.
• Read-through / write-through: the cache layer loads from and writes to the store itself. Write-through keeps the cache fresh at the cost of write latency.
• Write-back: writes land in the cache and are flushed later. Fast, but acknowledged data is lost if the cache dies before flushing.

Invalidation races. With cache-aside, a reader can miss, read the old value from the store, stall, and fill the cache after a writer has updated the store and deleted the entry, leaving stale data until the TTL expires. Fixes: leases or tokens handed out on a miss and invalidated by deletes, versioned sets that refuse to overwrite newer data, and short TTLs as a backstop. TTLs bound staleness; they do not provide correctness.

Stampedes. When a popular entry expires, many requests miss together and hit the store at once. Controls:

• Request coalescing (single flight): one caller recomputes, the others wait for its result.
• Jittered TTLs: randomize expiry so entries written together do not expire together.
• Probabilistic early refresh: each reader recomputes slightly before expiry with a probability that rises as expiry nears, so one reader refreshes while the rest still hit.
• Serve stale while revalidating where the product tolerates it.

Capacity depends on the cache. If the store can only handle a fraction of total reads, a flush, cold restart or lost cache node becomes a store outage. Plan warm-up, cap concurrent misses and know what the store can absorb.

Common misconceptions

• "Hashing removes hot spots." It removes skew across keys, not load on one key.
• "Delete-on-write cache-aside is always consistent." Concurrent readers can repopulate stale values; use leases, versions or accept bounded staleness explicitly.
• "A longer TTL always reduces load." It increases staleness and can synchronize expirations; tune per data type and add jitter.
• "The cache is an optimization, so losing it is harmless." If the store cannot serve the uncached load, losing the cache is an outage.
• "Consistent hashing balances load perfectly." Without virtual nodes arcs are uneven, and request skew remains either way.

How to approach it

Read DDIA Ch. 6, the Dynamo paper's partitioning section and the Builders' Library caching article. If your cloud coursework involved memcached, revisit it with these questions: what was the key-popularity distribution, what would a stampede look like, how would you shard the keys? Graduates should choose a sensible partition key and cache-aside with TTLs. Mid-level candidates should handle hot keys, invalidation and stampedes. Senior candidates should quantify cache dependence, plan rebalancing and warm-up, and treat consistency races explicitly.