The Scaling Problem Behind Cache Servers

Traffic spikes can overwhelm a website in short order. Cache servers exist to absorb that load by serving frequently requested data without hitting the origin server. But a fixed pool of cache servers is a bottleneck in itself: when demand outstrips capacity, or when nodes fail, the system must redistribute data quickly. If it cannot, a cascade of cache misses will send every request to the origin server, which can degrade or crash the service.

This is the core problem that consistent hashing solves. It is a partitioning scheme designed to minimize disruption when the number of nodes in a distributed cache changes.

Why Simple Partitioning Approaches Fail

Before looking at consistent hashing, it is worth reviewing the alternatives and why they break down under dynamic load.

Random assignment

Distributing data objects randomly across cache servers produces a fairly uniform distribution for large data sets. The problem is discoverability: a client has no efficient way to determine which node holds a given key. The retrieval cost makes this approach unscalable.

Single global cache

Storing the entire data set on one server makes lookups trivial but creates a single point of failure and a performance ceiling. It does not scale horizontally and offers poor availability.

Key range partitioning

Dividing the data by key ranges (for example, alphabetical or numerical) allows clients to locate data easily. However, real-world data is rarely uniform. Certain ranges can become hot, concentrating load on specific nodes and creating hotspots.

Static hash partitioning

Static hash partitioning places node identifiers on an array of length N. To find the node for a data key, the system computes:

node ID = hash(key) mod N

This lookup is O(1) in time complexity. Collisions—when two nodes hash to the same array position—can be handled with open addressing or chaining, but they degrade performance.

The fatal flaw is that this mapping is static. When a node fails or a new node is added, N changes. The modulo operation then yields different results for nearly every key, breaking the existing key-to-node mappings. The entire data set must be rehashed and moved. During this migration, most requests result in cache misses, and the origin server absorbs the full request volume. This makes static hash partitioning unsuitable for horizontal scaling in a dynamic environment.

How Consistent Hashing Works

Consistent hashing solves the rehashing problem by changing the data structure, not the hash function. The algorithm operates as follows:

  1. The output of the hash function maps onto a virtual ring structure known as the hash ring.
  2. Each node's IP address is hashed to assign its position on the hash ring.
  3. A data key is hashed with the same function to find its position on the ring.
  4. Starting from the key's position, the ring is traversed clockwise until a node is found.
  5. The data object is stored on or retrieved from that node.

When a node is added or removed, only the keys that map to the immediate clockwise neighbor of that node's position need to be remapped. The majority of keys remain on their original nodes. This dramatically reduces the amount of data movement compared to static hash partitioning.

Core Terminology

  • Node: a server that provides functionality to other services
  • Hash function: a mathematical function used to map data of arbitrary size to fixed-size values
  • Data partitioning: a technique of distributing data across multiple nodes to improve performance and scalability
  • Data replication: a technique of storing multiple copies of the same data on different nodes to improve availability and durability
  • Hotspot: a performance-degraded node caused by a disproportionate share of data storage or request volume
  • Gossip protocol: a peer-to-peer communication technique used by nodes to periodically exchange state information

Requirements for a Cache Partitioning Algorithm

Functional requirements

  • Design an algorithm to horizontally scale cache servers
  • Minimize the occurrence of hotspots in the network
  • Handle internet-scale dynamic load
  • Reuse existing network protocols such as TCP/IP

Non-functional requirements

  • Scalable
  • High availability
  • Low latency
  • Reliable

Partitioning and Replication Tradeoffs

Horizontal scaling requires partitioning the data set across multiple cache servers. Replication and partitioning are orthogonal. Multiple data partitions can live on a single node to improve fault tolerance and increase throughput. Partitioning is necessary because a cache server is memory bound and throughput must be increased to serve demand.

Replication alone does not solve the dynamic load problem because only a limited data set can be cached. Replication also introduces two significant drawbacks: consistency between cache replicas is expensive to maintain, and a fixed number of replicas cannot absorb unbounded traffic growth.

Performance in a distributed cache is measured by two metrics:

  • Spread: the number of cache servers holding the same key-value pair
  • Load: the number of distinct data objects assigned to a cache server

The optimal configuration keeps both spread and load as low as possible.

Figure 1: Cache replication—multiple copies of data stored on different nodes to improve availability, at the cost of consistency overhead.

Because each cache server is memory bound, a single server or a small replicated set can only hold a finite slice of the data. The combination of partitioning and replication across a dynamic set of nodes is what enables a cache tier to scale with demand.

A quick tour of the ring

Consistent hashing is a distributed systems technique that assigns both data objects and nodes a position on a virtual ring structure, often called a hash ring. Its main advantage is that it minimizes the number of keys that must be remapped when the total number of nodes in the system changes.

The core idea is to hash both node identifiers and data keys with the same hash function—typically a uniform, independent function such as MD5. The output range of the hash function must be large enough to avoid collisions. That output space is treated as a fixed circular space: the largest hash value wraps around to the smallest, forming a ring with a finite number of positions.

Placing a node on the ring involves three steps:

  1. Hash the node's IP address or domain name.
  2. Base-convert the resulting hash code.
  3. Modulo the hash code by the total number of available positions on the ring.

For example, if the hash function produces a 10-bit output (210 = 1024), the ring covers the range 0 through 1023, and each node lands at the position derived from hashing its IP address.

Storing and retrieving data

To store a data object, its key is hashed with the same function to find its position on the ring. The ring is then traversed clockwise from that position until a node is found—the first node with a position value greater than the key's position is where the object is stored. Retrieval works identically: locate the key on the ring, walk clockwise to the first node, and fetch the object from it. A cache miss means the origin server must be queried.

In practical terms, each node is responsible for the region of the ring between itself and its predecessor. The overall algorithm boils down to:

  1. Place the hash function output (e.g., MD5) on the ring.
  2. Hash node IP addresses to assign node positions.
  3. Hash the data key to locate its position.
  4. Traverse clockwise to find the owning node.

Adding and removing nodes

When a node fails or crashes, its data objects move to the immediate neighboring node in the clockwise direction; all other nodes remain unaffected. Conversely, when a new node joins the ring, keys that fall within the new node's range are moved out of its clockwise neighbor to the new node.

The average number of keys stored on a node is k/N, where k is the total number of keys and N is the node count. Adding or removing a node only redistributes that average—about one node's worth of keys—which is what makes consistent hashing valuable for cloud systems facing dynamic load.

Virtual nodes and hotspots

A key weakness is that nodes may not distribute uniformly on the ring. When a node attracts a disproportionate amount of traffic, it becomes a hotspot and can trigger cascading failure. To mitigate this, virtual nodes assign each physical node multiple positions on the ring by hashing its ID through distinct hash functions. This spreads load more evenly and prevents hotspots; nodes with greater capacity can be given more positions. Traffic handled by a node is also spread more uniformly across neighbors during downtime, and a newly provisioned node accepts load from across the ring rather than from a single successor.

Implementation with a binary search tree

In practice, implementations often store node positions in a self-balancing BST. A BST offers O(log n) time for search, insert, and delete. Keys in the BST correspond to node positions on the ring.

The BST can live on a centralized highly available service, or it can be replicated on every node with state synchronized through the gossip protocol.

Inserting a key involves hashing the key, locating the BST entry immediately greater than the hash output, and storing the object on that successor node. Inserting a node requires adding its hash position to the BST, identifying the keys that fall within its subrange on the successor, and moving those keys over. Deleting a node is symmetric: remove its position, gather the keys in its range, and move them to the successor. Each node may also keep an internal or external BST to track which keys it owns.

Concurrency, hash function choice, and complexity

Because the BST is mutable and nodes can be added or removed concurrently, it must be synchronized. A readers-writer lock is the standard approach, at the cost of a modest increase in latency.

The hash function itself matters. Cryptographic choices such as MD5, SHA-1, and SHA-256 are relatively slow. Practical alternatives like MurmurHash, xxHash, MetroHash, or SipHash1–3 are cheaper while still producing uniform output.

Trade-offs and real-world use

The main strengths of consistent hashing are horizontal scalability, minimal data movement when the node count changes, and straightforward replication and partitioning. Virtual nodes add better load balancing across heterogeneous machines and smoother redistribution during downtime or scale-out.

Its drawbacks include potential hotspots and cascading failures, non-uniform node/key distribution, and insensitivity to node performance differences. Virtual nodes introduce their own complications: capacity planning is harder, BST maintenance raises memory and operational costs, replication logic must distinguish physical from virtual nodes, and a failing virtual node can affect multiple ring positions.

Consistent hashing underpins several well-known systems. Discord uses it to map chat servers to hosting nodes. Distributed NoSQL stores such as Amazon DynamoDB, Apache Cassandra, and Riak partition data across nodes with it. Vimeo balances video streaming traffic with it, and Netflix relies on it to route uploaded content across its CDN.

Production implementations are available out of the box in Memcached clients (notably Ketama) and Amazon Dynamo. HAProxy ships with a bounded-load variant for load balancing. For many applications, one of these existing implementations is sufficient; otherwise, the algorithm is straightforward to implement directly.

Refinements to Consistent Hashing

Two notable variations address different weaknesses in the basic consistent hashing scheme: multi-probe consistent hashing and consistent hashing with bounded loads.

Multi-Probe Consistent Hashing

Multi-probe consistent hashing abandons virtual nodes in favor of assigning each physical node a single position on the ring. This yields linear O(n) space complexity for storing node positions, and the amortized complexity for adding or removing nodes drops to constant O(1). The trade-off surfaces during lookups, which become comparatively slower.

The core mechanism is straightforward: rather than relying on one ring position per node and virtual-node fan-out, the key (data object) is hashed multiple times using distinct hash functions. The closest node found in the clockwise direction from any of those hashed positions returns the requested data object.

Consistent Hashing with Bounded Loads

Bounded-load consistent hashing constrains how much traffic any single node can receive relative to the average load across the entire ring. As long as nodes remain under that ceiling, request distribution follows standard consistent hashing behavior. The constraint only kicks in when a node risks overload.

The motivating scenario is a suddenly popular data object. The node hosting that object gets hit with a disproportionate share of requests, degrading its service. In the bounded-load variant, an incoming request destined for an overloaded node is redirected to a fallback node. Critically, the fallback selection is deterministic with respect to the request hash: the same set of fallback nodes is always considered for the same popular object. This prevents the "hot object" problem from cascading unpredictably.

Different request hashes, however, tend to produce different fallback lists. The practical effect is that traffic meant for an overloaded node is spread across the pool of available nodes rather than piled onto one designated backup. This spreads the burden of a hotspot across more machines, while the deterministic fallback per hash keeps routing stable and consistent.

Summary

Consistent hashing underpins data partitioning and load balancing in many internet-scale distributed systems. Its ability to minimize remapping when the membership of the ring changes makes it a core primitive in designs like URL shorteners and Pastebin. The optimizations presented here — multi-probe hashing for simpler node management and bounded-load hashing for fairness under hot spots — give engineers levers to tune for their specific workload.