Cloudflare saves 100TB of RAM by fixing a single algorithm
Saving another 100TB of RAM with math (and Rust)
Cloudflare's Pingora Backend Router was using up to 6GB of memory per node due to an explosion of consistent hashing rings. By shrinking the index in the hash point struct from 32 to 16 bits and applying mathematical analysis, the team reclaimed over 100TB of RAM globally—following another 100TB saved by the DNS team last month.
At this scale, small improvements are greatly magnified, so even 1%-at-a-time improvements are worth celebrating.
- zer0x4d
Incredibly happy to see this series of CF articles. I was always so proud of devs back in the days where RAM and processing were scarce and who had to get creative to fit even the most basic stuff in the budget. It seemed to me that after RAM and processing became abundant, most gave up on optimization and focused on shipping instead which meant now that even with several cores, a basic notepad or music player failed to work. In a way, RAM becoming more expensive has ushered in a new era of forced optimizations, which I'm really happy for
- nopurpose
Do I understand correctly, that they spent memory storing largish N hash values per server, so that request hash determines which server to send request to using closest higher value of all server hashes?
That in effect boils down to consistently selecting server S with probability P, where P is function of weight and total number of servers?
Surely there must be better way to select server with a given probability without storing a massive lookup table of hashes? Randevouz hashing of some sorts
- dr_dshiv
Cloudflare is truly amazing, they have made so much possible for my main side-project at a price and performance that I can’t really take credit for (http://sourcelibrary.org), I don’t care if their text was written with AI, I just wish I could get my own AI to sing so well about hashing… but wait.. today I noticed Claude trying to use hashing when a timestamp would honestly do, and now I’m really doubting myself, hmm…
- vlovich123
I would get rid of consistent hashing and ketama for a better system which works save an additional 600TiB.
You use the first N bits of your key hash to pick the server partition so it’s a reasonable number (eg 128 servers per partition). Then use high quality precomputed hashes (first 64 bits of sha256) for the server name as N in H(K + N). Use wymum from wyhash as the H so that you do o(n) integer multiplications while retaining a result that’s still a good hash statistically.
Now you’re using a tournament hash, the small N means O(N) vs O(N log N) doesn’t matter, and also this O(N) is also going to be much less CPU than computing 160 hashes per key as they do now, so much less latency added per request.
- Fordec
This sort of thing makes me thing that we're about to enter an era where software development is going to be where most of the jobs fallout will be. You can't one-shot vibe code your way to this. But for proper Software Engineering, those jobs are safe where more and more problems are going to actually need solving by creatively using math because all the problems individuals deliver are just going to be larger. People are just mourning the loss of the low hanging fruit.
- ricardobeat
These optimizations are impressive, but it gets me thinking: at what point does a company become a collection of impenetrable siloes, where nothing really does what you expect? Maybe know with AI this is less of an issue as exploring a codebase is also much faster.
- agosta
Bang up article! As someone who doesn't get to do enough (almost any) calculus in my daily programming assignments, I thoroughly enjoyed reading about Kevin's dive into that derivation (linked in the supplemental article). All the people being negative here can swallow raisins
- proc0
The only Rust section is the one on storage improvements about the struct that stores the hash, but do they really need that many hashes that 2 bytes makes that big of a difference? Article doesn't expand, but I guess it's a hash for every task on every computer, so maybe yes.