Saving another 100TB of RAM with math (and Rust)

Cloudflare, a massive company with thousands of servers worldwide, faced a memory usage issue with its Pingora Backend Router (PBR). The internal load-balancing service was using significantly more memory than expected, especially in structures associated with pingora-ketama, an open-source library for consistent hashing. Consistent hashing is a method for distributing tasks across multiple servers without requiring large changes when servers are added or removed.

It is used to route cacheable requests to servers by URL, keeping only one copy of a file stored per data center and providing a stable way to find the location of each file.

The key concept behind consistent hashing is that hash functions output limited 32, 64, or 128-bit integers, allowing tasks and servers to be related consistently. These integers are visualized as a number line, with tasks and servers assigned based on their hash values. While the basic concept is simple, consistent hashing can lead to imbalanced workloads, as the range covered by one server may be significantly larger than that of others.

In the case of Cloudflare's PBR, the server with the largest range handled 0.99% of the total, while the standard deviation indicated that most ranges would fall within 1% of the expected value. This imbalance needed to be addressed, as it would result in unequal distribution of requests among servers. To solve this problem, Cloudflare added multiple hashes to represent each server instead of just one.

This approach increased the complexity of the system but allowed for more balanced workloads and reduced memory usage, reclaiming over 100TB of RAM globally.