Optimizing Consistent Hashing for Memory Efficiency at Cloudflare

The Challenge of Scale and Resource Optimization

Operating at Cloudflare's scale means even minor inefficiencies can lead to enormous resource waste. The article highlights how their internal load-balancing service, Pingora Backend Router (PBR), experienced excessive memory usage due to its consistent hashing library, `pingora-ketama`. This prompted an investigation into how to optimize memory while maintaining performance and equitable resource distribution across thousands of servers globally. The goal was to find a balance between efficient resource usage and the inherent statistical properties of consistent hashing.

Understanding Consistent Hashing and its Distribution Problems

Consistent hashing distributes requests across servers such that adding or removing servers minimizes key remappings. Cloudflare uses it to route cacheable requests by URL, ensuring only one copy of a file is stored per data center. The core concept involves mapping server and task hashes onto a number line (or ring). Tasks are assigned to the nearest server to their left. A key challenge is achieving an even distribution of workload, as simple hashing can lead to highly unequal ranges for servers due to the random nature of hash outputs.

Improving Distribution with Virtual Nodes (More Hashes)

To mitigate uneven distribution, the standard practice is to assign multiple hash points (virtual nodes) to each server. While each individual hash segment remains random, the Law of Large Numbers dictates that the sum of many segments assigned to a server will tend to average out, leading to a more uniform workload distribution. For example, increasing from 1 hash per server to 160 hashes per server can reduce the coefficient of variation (error margin) from ~99% to ~8% in a 100-server setup. Cloudflare also uses weighted consistent hashing (like the Ketama algorithm) to distribute requests proportionally to server capacities (e.g., disk space for storage-intensive services, CPU for compute-intensive ones), requiring even more hash points.

Memory Optimization Strategies

• Compact Structs: Initial memory savings came from optimizing the `Point` struct in Rust. Due to Rust's alignment rules, a `Point` containing a 4-byte hash and a 2-byte index would occupy 8 bytes. By storing hash and index as a raw byte array and using getters, the memory footprint per `Point` was reduced by 25%. This highlights the importance of understanding language-specific memory layouts at scale.
• Reducing Hash Count: The most significant optimization involved re-evaluating the necessary number of hashes per server. Through detailed mathematical analysis (deriving an exact formula for standard deviation instead of approximations), Cloudflare discovered that they could reduce the number of hashes generated for each server by 90% without incurring appreciable error. This was particularly effective because, beyond a certain point, the benefits of adding more hashes diminish, and 32-bit hash collisions can even introduce unpredictable errors.

Graceful Migration for Architectural Changes

A crucial architectural consideration for such a change is migration. Altering the hash ring changes request routing, which could invalidate a large portion of cached content and overwhelm origin servers. Cloudflare avoided a 'single global flip' by carefully orchestrating the transition, emphasizing that memory optimizations must not compromise system stability or performance during deployment.