阅读中文版本

Cache Partitioning via Consistent Hashing

Cache partitioning spreads keys across nodes with consistent hashing, so adding a node moves only a fraction of keys instead of reshuffling everything.

Definition

Cache partitioning is the distribution of cache entries across multiple nodes by mapping each key to a node, typically using consistent hashing so topology changes relocate a minimal set of keys.

It is used to scale a cache beyond one machine’s memory and to keep hot data spread evenly. Compared to simpler alternatives, this concept fits best when the trade-off it represents is the one the system actually cares about.

When to use it

A common use case is applying it at the boundary where the cost of getting it wrong is highest, and the scenario usually involves a concrete guarantee the system must uphold. Unlike an ad hoc approach, it makes that guarantee explicit, reviewable, and testable.

How it works

Modulo hashing maps a key to node by the remainder of a hash, so changing the node count remaps nearly every key and triggers a mass invalidation.

Consistent hashing places keys and nodes on a ring so adding or removing a node affects only the adjacent range, which keeps most cached data valid across scaling events.

Trade-offs and alternatives

Partitioning distributes keys but not load, so a single very hot key still lands on one node and needs replication or client-side caching to spread the pressure. The main drawback is the extra complexity it introduces, so the benefit should clearly outweigh that cost before a team adopts it.

Common misconceptions

A persistent misconception is that modulo hashing distributes keys just as well when nodes change. Another is that hot keys are automatically spread across partitions. For example, an engineer who assumes otherwise may design around a guarantee that does not actually exist, which only becomes obvious under load or failure.

Anti-patterns to avoid

Two recurring anti-patterns are to resizing the node count with modulo hashing and invalidating most keys and to routing a single popular key to one node and concentrating load. Both tend to surface as hard-to-debug production issues rather than obvious test failures. Related concepts include Edge Caching at the CDN, Request Deduplication, Cache-Control Directives.