Saving another 100TB of RAM

Cloudflare's performance team has managed to reclaim over 100TB of RAM globally by optimizing a single algorithm within their Pingora-based services. The issue stemmed from excessive memory usage from pingora-ketama, an open-source library for consistent hashing, within the Pingora Backend Router (PBR). To understand this memory issue, it's crucial to grasp the concept of consistent hashing and how it's utilized in PBR.

Consistent hashing is a method used for distributing tasks across multiple servers without requiring significant adjustments when servers are added or removed. This technique is employed to route cacheable requests to servers by their URL, ensuring only one copy of a file is stored per data center while providing a stable way to locate each file.

The algorithm functions by representing the 32-bit output of a hash function as a number line, with servers and tasks mapped based on the hash of their representative values. This arrangement facilitates the assignment of tasks to the first server to the left of their assigned hash.

However, the challenge arises when certain servers, like server A in the example, have significantly larger ranges compared to others (B and C). This imbalance leads to an unequal distribution of requests among servers, with the workload being proportional to the size of each server's range on the number line. To address this, Cloudflare's Performance team sought a solution that would maintain the simplicity and ease of implementation inherent to consistent hashing while mitigating the imbalances in workload distribution.

The breakthrough came when the team added multiple hashes to represent each server instead of relying on just one. This approach may seem counterintuitive at first, as it appears to introduce more complexity. However, it effectively reduced the standard deviation in the range sizes associated with each server, leading to a more balanced distribution of the workload.

By doing so, Cloudflare successfully optimized memory usage and reclaimed over 100TB of RAM, demonstrating that even seemingly small improvements can have a significant impact at the scale of their operations.