Cloudflare recovered more than 100 terabytes of RAM across its global network after redesigning part of the request distribution algorithm in the Pingora Backend Router (PBR) service. The improvement came from a combination of compressing the representation of hash points, reducing their number based on statistical analysis, and carrying out a gradual migration that preserved cache stability and traffic to origin servers.
The Problem with Request Distribution
Cloudflare uses the pingora-ketama library to implement consistent hashing, a method that helps route cacheable requests to the same server whenever possible. This makes it possible to keep a single copy of the file inside the data center and provide a consistent path for accessing it.
However, using a single hash point per server can lead to significant variation in the sizes of the ranges owned by servers on the hash ring, and therefore variation in workloads. Pingora consequently uses a large number of virtual hashes per server, with weights tied to storage capacity. Separate rings are also created for different groups of properties and constraints. The accumulation of these rings led in some cases to consumption of up to 6 gigabytes per process.
Improving Data Representation and Reducing Hashes
Each element representing a point on the ring consisted of a 32-bit hash value and a 32-bit index to the server, totaling eight bytes in memory. Cloudflare’s team determined that the index practically needed no more than 16 bits, because the service would not coordinate more than approximately 65,000 servers at the same time.
Reducing the index type alone was not enough because of Rust’s alignment rules: the structure would still remain eight bytes in size. Cloudflare therefore stored the value and index in a raw six-byte array, with functions for accessing each one. This change reduced memory consumption for hashing by 25%.
The larger gain came from reviewing the number of hashes. The service had used a baseline value of 160 points per server, multiplied by the server’s weight associated with storage capacity. The analysis showed that large increases in the number of hashes provided diminishing improvements in the error margin. In the example discussed by Cloudflare, adding the final 90,000 hashes reduced the error by only about 0.7%.
Using 32-bit hash values also makes collisions more likely as the number of points increases, which can add unexpected error to the distribution. Based on calculations and simulations, Cloudflare reduced the number of hashes per server by 90% without a noticeable increase in error, contributing to the final savings.
What Changes in Practice?
Switching the hash ring across the network all at once was not a safe option, because it would redistribute requests and effectively cause a significant loss in cache effectiveness, with the possibility of increasing traffic toward origin servers. PBR therefore temporarily kept both the old and new rings in memory and selected between them for each request, providing a clear rollback path.
The migration was carried out in stages, beginning with small validation sites and then moving to larger data centers. Control over the percentage of requests using the new ring was separated from determining which data centers were allowed to participate. Cloudflare monitored the effects of server selection, ring versions, connection errors, memory consumption, startup time, cache behavior, and traffic to origin servers before removing the old path.
Engineering Significance
The experience shows that low-level improvements, such as choosing the size of a field within a data structure or determining an appropriate number of hash points, can have effects that multiply when applied across a network containing thousands of servers. At the same time, the result does not mean that reducing memory is safe in every system. Distribution accuracy, collision probabilities, server weights, feature constraints, and the migration implementation are all factors that must be measured before making a change.
The changes are available in the pingora-ketama package through a Cargo feature that is currently undocumented. Version v2 supports the compressed storage format, a faster sorting method, and the ability to configure the baseline number of hashes, while retaining version v1 and allowing both rings to run together with the decision made at the request level.