Cloudflare Reclaims 100 TB of RAM by Optimizing Consistent Hashing

Cloudflare recently documented how it reduced the memory footprint of its internal load-balancing service by more than 100 TB by optimizing the Rust implementation of consistent hashing in pingora-ketama. The changes compacted hash-ring entries and used statistical analysis of hash distribution and collision rates to reduce the number of hashes per backend by about 90% while preserving load-balancing accuracy.

Cloudflare relies on consistent hashing in its Pingora Backend Router to distribute cacheable requests across servers, but supporting weighted servers and different feature combinations required many hash rings, significantly increasing memory usage. The team identified excessive memory usage coming from its pingora-ketama consistent-hashing data structures, prompting an investigation into their design and optimization.

Cloudflare applied probability theory to consistent hashing to determine the minimum number of hash points needed to achieve the required distribution, allowing the team to significantly reduce the size of the hashing structures while maintaining the required distribution.

Kevin Guthrie, principal distributed systems engineer at Cloudflare, Mariia Iurchenko, senior software engineer at Cloudflare, Zaidoon Abd Al Hadi, systems engineer at Cloudflare, and Ivan Babrou, performance engineer at Cloudflare, write:

Each step down in error margin requires (almost) an order of magnitude increase in the number of hashes per server, so adding more hashes yields less and less improvement.

Source: Cloudflare blog

Adding more hashes produced diminishing improvements in load distribution, with the final 90000 hashes improving the error by only 0.7%, and the team used the analysis to reduce the number of hashes per server by 90%. The birthday paradox, which describes the unexpectedly high probability of collisions in a set of randomly chosen values, also explains why collisions become increasingly likely as the number of 32-bit hash points grows, introducing additional distribution error.

The team also optimized the Rust data structures storing the remaining hashes: the existing representation used an 8-byte Point, even though the hash and server index could be represented in just 6 bytes, further reducing memory usage. Guthrie, Iurchenko, Abd Al Hadi, and Babrou add:

There was one more problem: changing the hash ring changes where some cacheable requests go. Even if the new ring is better, switching the whole network at once would effectively invalidate almost all cached content. It would turn a memory optimization into an apocalyptic increase in origin traffic.

The new implementation was rolled out gradually alongside the existing ring to limit cache churn and origin traffic spikes.

Source: Cloudflare blog

In popular Hacker News and Reddit discussions, many developers debate why consistent hashing remains useful despite its overhead and how it differs from request hashing. User Teanut writes:

It's fun seeing what little changes at massive scales can do. Good use of math to justify the changes, too.

The Pingora Backend Router effort is not the only one by Cloudflare to optimize memory usage at scale: in August, the company described how its DNS team reduced the memory footprint of its cache through a series of data-structure optimizations.