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

Saving another 100TB of RAM with math (and Rust). Along the way, we’ll learn some Rust and even a little math.

What happened

You might not be able to solve all your problems with Rust, but math is universal. That allowed us to reclaim more than 100TB of RAM globally, on top of the 100TB of memory the DNS team was able to shed last month. Ideally we would like to guarantee each server will have an equal size, but because hashes are essentially random numbers, we have to talk about the size of the regions in terms of statistics. 😨Math and consequencesFirst: don’t panic.

We’ll get to the math behind this momentarily, but it should make some intuitive sense that while each individual range has a large standard deviation, adding a bunch together should make their total size even out. Each segment in the sum has a chance of balancing another. I’ll spare you the math for now, but if we go back to our 100-server example, if we use 160 points per server instead of just one, the coefficient of variation (which we can think of like an error margin) drops from about 99% to about 8%, a significant improvement.

That struct looks like this:struct Point { hash: u32, index: u32, } In memory this is represented as eight bytes, where four go to the hash (which is unavoidable), and four go to an index pointing to the server which is stored in another array.

The wider picture

So we can replace the struct above with this one:struct PointV2 { hash: u32, index: u16, } Unfortunately, Rust doesn’t make it that easy. This is because Rust has alignment rules that require the size of a structure in memory to be a multiple of its largest (or “most aligned”) field. In order to do better than that, we’ll need to jump back into the math, so everybody hang on to something; this is the home stretch.

To make the math easier, we'll say the weighting factor $m{m_w}m$ for a server is 625, so we get $m{k = 160\times625 = 100{,}000}m$. The predictions from my beautiful math only work if we think about hashes in a continuous ring, but in practice we use 32-bit numbers for the hashes that have the potential for collisions, and the probability of collisions goes up surprisingly quickly as the number of hashes increases (see the birthday paradox).

Now that we have some math to back it up, we determined that we could decrease the number of hashes we were generating for each server by 90% without incurring any appreciable error, so that is what we set out to do. Looking at the difference, we get the satisfying result that our changes dropped the used memory by 100TB! Skip to contentCloudflare operates at a scale so big that even after working here for years, it doesn’t seem real.

What has been reported

We have thousands of servers all over the world with petabytes of RAM and millions of CPU cores, and all of it is pushed to the max. As vast as those resources feel, they are still finite, and when you need every service to run on every node, it doesn’t leave room for wasted space. At this scale, small improvements are greatly magnified, so even 1%-at-a-time improvements are worth celebrating. And some tweaks add up to a lot more: in this post, we’ll look at how small changes to a single algorithm reduced the memory footprint of one of our Pingora-based services significantly.

Waste notMaintaining equitable resource sharing between teams is not easy, especially in large organizations. One of the ways Cloudflare ensures the balance is kept is through the tireless efforts of the wonderful Performance team. This story starts with a ticket filed by Ivan who found: Excessive memory usage from pingora-ketama in Pingora Backend Router. The finding was that our internal load-balancing service, Pingora Backend Router (yes, PBR), was using significantly more memory than expected — specifically in structures associated with pingora-ketama, which is our open-source library for handling consistent hashing.

What happens next

In order to talk about how we addressed this seeming overuse of memory, we need to talk about what consistent hashing even is, why we are using it in PBR, and how it became so memory hungry. Consistent hashingConsistent hashing is a widely used method for distributing tasks across multiple servers in a way that does not require large changes when servers are added or removed. Internally we use it to route cacheable requests to servers by URL.

This allows us to keep only one copy of a file stored per data center and gives a stable way to find the location of each file. We have mentioned this system before, but let’s take the time to walk through how and why this algorithm is used and how it works. The key concept of consistent hashing is that while hash functions can accept any kind of input, their output is limited to a single unsigned integer (32, 64, or 128-bit integers depending on which hash function).

This allows us to relate tasks and servers to each other in a consistent way.