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
I don't remember those days with a ton of fondness. Yes, the challenge was fun, but I really wanted to ship it and get my product in the hands of customers. Now I can spend more time thinking about what they want and less time about what the computer wants.
Yes, I remember those too. The costs of manual memory management were real and were not low.
But costs on the cloud are real too, especially now. I’ve been living in JVM land for a very long time, but now it’s especially clear how important lean services are. Especially now that the bar for writing lean code is so much lower: let the borrow checker figure it out, etc.
I just spent a couple days wringing out more performance/memory efficiency for our services. Nice gains to be sure, but it’s still so immensely wasteful compared to something well written running native. If it was my money, I’d be going native for sure.
> But costs on the cloud are real too, especially now. I’ve been living in JVM land for a very long time, but now it’s especially clear how important lean services are. Especially now that the bar for writing lean code is so much lower: let the borrow checker figure it out, etc.
I don't think even Cloudflare bothers with this waste of time. If they did, they would certainly not have built their global infrastructure on JavaScript running on V8. They'd have done what Google and old-time Facebook did and built their whole infrastructure on low-level system languages, and hiring the world's leading minds on the subject to milk the last drop of performance from their hardware.
Even Google stopped to look at the problem and came up with Go. Not V8.
> The key point here is our programmers are Googlers, they’re not researchers. They’re typically, fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
All those things happened before the era of decent AI.
Also, it really does matter what you're building. Yet another CRUD app? Don't waste time on (super) lean languages - use Go or something else you like and move on.
Building a Kafka replacement? Making something that processes gobs of data quickly? Perhaps think about using something lean and efficient, as the economics have changed. "waste of time" (or memory) also applies to the cloud and your (or your company's) bill. And if you haven't noticed, you're being ripped off on the cloud, running something 10-50x less efficient has real bottom line impact.
The world turned millenia ago and will turn millenia later.
The problem statement is of applications using up expensive RAM. Incidentally, expensive RAM is just one of the problems we face in the computing space. Forced obsolescence is another, when running hardware needs to be replaced because software is built for only newer CPUs.
You are right, but it reads (to me, could be just me) you mean newer specs which used to be true when I shipped software in the 70-90s; you mean faster machines / more memory right? Like installing a new version of software or OS and suddenly all memory is used, system is swapping and you did not ask for that but some obscure feature you didn't need needed to be shipped fast.
> The problem statement is of applications using up expensive RAM. Incidentally, expensive RAM is just one of the problems we face in the computing space.
You need to stop and think about the problem. Nowadays RAM is expensive because many people now want to max out their computers with RAM to run LLMs and AI coding assistants. Today's software is still the same software that ran perfectly well half a dozen years ago. Cloudflare happens to operate a large global computer infrastructure, and it's scale is such that 1% gains are lauded as fantastic cost savers. But that's the bean counter's perspective, pointing out that they saved a bean.
> Today's software is still the same software that ran perfectly well half a dozen years ago.
This statement is quite honestly not true at all. Just take the two largest OS from 6 years ago and compare resource usage between them and you will find you are incorrect, never mind the software running on it.
> Nowadays RAM is expensive because many people now want to max out their computers with RAM to run LLMs and AI coding assistants.
Source? I imagine the amount of people trying to run local LLMs is miniscule. RAM is expensive because a handful of companies have spent billions buying all of the compute.
That statement can be used to justify anything, to the point it is utterly useless.
— Humanity has been on the decline. People are hateful towards each other, striking their fellow man and poisoning the environment. Despots eventually launched nukes which killed everyone but the cockroaches.
On the contrary. Industrial developing countries saw bigger % increases in their economic growth in the last couple of decades than the fully developed "old" western ones. Mostly due to "the rich" shipping western jobs there to cut costs and increase their margins.
For example the likes of Poland, China, India and Vietnam were and still are growing like crazy when you compare to the likes of UK or Germany.
> And its this obsession with shipping things as fast as possible quality be dammed (...)
You seem confused. Allocating more memory than optimal levels is not a measure of quality. Similarly, a web page is not suddenly lower quality if an image asset is 50kb instead of 25kb. And how much complexity and engineering effort and bugs are you willing to tolerate to halve your memory allocations?
You are conflating quality with mindless minimization, not even knowing or caring that are the tradeoffs. The blog post you're commenting on starts by presenting the case for celebrating small improvements, even 1% improvements at a time. A similar 1% improvement in a mobile app is at like 1MB. Do you ever notice it? How many hours of engineering effort are you hoping to spend on this nonsense? And you prefer to spend it on this or in actually fixing a bug or implementing a feature?
This puerile conflation of minimization with quality suggests your personal notion of quality has no bearing on what quality actually is.
> And how much complexity and engineering effort and bugs are you willing to tolerate to halve your memory allocations?
You seem to be confused about this relationship. It's usually exactly the opposite.
The wasteful applications are generally not well reasoned about and half assed implementations. That's why they're guzzling resources
There is ofc a middle ground, because targeting eg incredibly resource constrained embedded systems will naturally increase complexity, but that's something entirely different to the scenario this discussion was about up to this point.
Exactly, that`s why i refuse to call 99.9% of "software engineers" engineers. Imagine you optimize a aircraft turbine 1%....man you get to drink a pool of champagne with the highest ceo's and aircraft carriers try to buy that turbine as fast as possible.
But with software and a install base of some millions 1% optimization is seen as wasteful, its like software slop is acceptable since forever because hardware gets faster, and electricity is "green" anyway.
Resource constraints have historically been a bastion of quality engineering, though. The relationship is not directly causal, but any time an engineer must not only solve a problem but _fit it within some kind of a budget_ vs having an unlimited budget, it forces them to slow down and think more carefully about what they are producing and how well it actually functions.
Ultimately it is an expression of anti-fragility: some minimal challenge must be met and conquered on many different axes of a production in order to help the full production itself mature to the best possible quality.
It is the same reason we exercise, the same reason that cars and toilets and so many products greatly increase in quality after emissions and usage and waste-related regulations get applied from above, etc.
The appreciation of the refining force of outside limitations is not about min-maxing, but it is at least partly about curbing the min-maxing of other concerns such as "ship the fastest garbage possible to move on to the next opportunity to repeat that process".
The vast majority of people do not care about memory efficiency on the levels we're talking about. I've never met a non-technical person who has cared. And out of the technical people that I know (which represent less than 5% of the population), no more than half of them have complained about the memory usage of an electron app.
Or, they care but they lack the vocabulary to express what they care about.
You can get a new laptop to run software A or competing software B.
You can pay $1000 for the laptop with 4GB of RAM, and software A either can't run on that or will act like pulling teeth, so that software requires you to upgrade to 16GB of RAM which will put you back another $2000.
Or you can run software B which will hum along perfectly smoothly on the original $1000 laptop.
(All of that of course simplifying right past "everyone runs every app 24/7 with five trillion browser tabs open")
Are you honestly suggesting that the end user doesn't care about having to throw exponentially more money at stuffing RAM into their PC just to make the game all their friends are playing online function?
> Or, they care but they lack the vocabulary to express what they care about.
That's speculative to the point of being conspiratorial.
> Are you honestly suggesting that the end user doesn't care about having to throw exponentially more money at stuffing RAM into their PC just to make the game all their friends are playing online function?
I'm extremely clearly not suggesting that. Don't make up things and pretend that other people said them. Engage honestly or not at all.
Customers often want to pay less, and shareholders often want lower capital costs. A tasteful optimization is a win-win. The opportunity cost should be traded off against new features of course, but tasteful optimization is a good thing for customers.
While it's nice to see this focus, while they highlight absolute figures, we are still talking about 1% improvement. For most other software systems, nothing worth putting effort in for.
> In a way, RAM becoming more expensive has ushered in a new era of forced optimizations, which I'm really happy for
Isn't this mainly Cloudflare's scale though? That's literally also what's in the introduction written as the reason why they are doing the optimization
During the Moore's Law years you didn't have to optimize much, if you did a significant release yearly computer hardware grew faster than your optimization problems.
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…
This is pleasant coincidence. Really like your site and it's queued to send in my newsletter in the morning! Just happened to see your comment here while I was reading. Great work.
> 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…
Tried out the first 1000 words in Pangram, and it seemed happy it was human written. Not surprised either, it has been some of the better writing I've seen out of Cloudflare recently.
They do deliberately err on the side of not accusing people of using AI when unsure. I think that's a good decision.
Do you know it was actually AI? I've seen humans imitating AI "it's not X — it's Y" to try to fool it that it correctly guessed was still human. Humans did use those patterns before AI so they're not enough on their own to flag.
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.
I think they do only a hash per request. The 160*weight hashes were done per server (per feature set), to partition the hash space.
Per request you do a single hash and then a lower_bound on a sorted map to find the serving server (again, on the ring appropriate for the features required by the request, so likely a hash map lookup first)
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
Plus it's limited to 65k entries. Perhaps a btree where parent nodes sum the weights of child nodes would work well. Using the input hash scaled by total weight, a binary search lookup would compute the partial sums for comparison on the fly. Adding/removing a node would only update the ~8 parents when the btree order is 4. Eytzinger layout and struct-of-arrays could be used to improve cache locality during lookup. This does mean an add/remove could drastically change the overall mapping, perhaps that's why consistent hashing is used instead.
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.
I think you're speaking like a software engineer, which is understandable, and not like a historian or economist. There's no reason to believe math based jobs would survive. The models regularly do well on math problems. You can auto-research loop ways to optimize memory usage for any particular program.
The point isn't that "doing math" is safe. Auto-research solves one target variable in one system, doing it at scale where say one developer is SME for the agentically manged 200 microservices down the line, heh I mean you certainly can, but good luck with that token cost of auto-research when that problem space is O(microservice^2). I point at that example yesterday of that optimized database memory with the comments pointing out that the specific problem fit in memory, over optimized and didn't generalize. The problem isn't the work, but the rework. A historian should know that new solutions to problems doesn't lead to "no problems ever again" but only problems with barriers that the new solution doesn't solve.
The argument is probably that LLMs can find those optimizations cheaper than a human expert. Since LLM cost at fixed capability seems to be going down you either expect humans to be completely replaced or human wages to be lowered by LLMs.
I expect average human wages for programming to get lower and the overall percentage of the developer to move lower wage countries and this probably means away from the US and US salary expectations. Meat proxies and agentic CRUD will be off-shored to low wage Asian or even African countries with AI handling language barriers. Why wouldn't they be? Why pay six figures for a meat proxy? Product Builders should weather the storm the most, but they'll be the high end skilled PMs/engineers that of the overall industry but probably won't break 10% of total global headcount. In a world where knowing the domain will be the key driver of differentiation, as building averages out and knowing the customer and how to market to them becomes the differentiator, being closer to the target market will fragment competition from four global winners with over 10k employees in a space to 100 niche/regionally tailored winners with maybe 500 employees a piece. Not to mention if you thought GDPR was a pain, wait until AI laws that vary by country to country get added in.
I also expect as AI becomes more cost sensitive once the quality plateaus (there's only so many ways to get an answer to 100% right), the data centers are going to chase where the cheap power is, and this long term is likely to be in high-solar locations. So lower latitudes. Doesn't rule out places like Texas of course, but places like India, Mexico, Brazil, Israel or Saudi Arabia will have home field advantages.
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.
I feel like any company whose products have RESTful interfaces are already there…
One wants to turn on an indicator on a remote device. A simple Boolean value. But we need networking, TLS, authentication plugins, certificate validation, distributed logging, containers, orchestration, HTTP client/server, interprocess communication, daemon dependency management, …
Sure, one can say each of these layers and abstractions has an important and justifiable purpose. But one can also step back and start wondering - what the hell are we really doing???
At some level, it seems like each layer of abstraction has to manage others, only simply because they exist.
Imagine the simplicity of 1800s telegraph signaling - no software!
Too often we build systems with Fortune-50 style hierarchies when a 5-person team could do the whole job.
And at what point does a company start to care about performance? 100TB of RAM is expensive as hell, but getting products to market faster was worth the cost
Cloudflare is unusual in that their product is performance and their costs are primarily hardware and networking. You see similar performance initiatives from companies like AWS who also need to maximise their hardware usage.
Whereas for somewhere like Burger King, the costs are all rent and staff, so they wouldn’t care how much RAM their website uses. But you would see similar optimisation in their supply chains for their ingredients, and their rotas to reduce staffing.
I mean you can just pause and refactor regularly. I tend to use every ~4th session as an opportunity to refactor, adjust interfaces, break overly large modules into smaller ones and suchlike.
The trick is to keep the silos losely coupled and small enough that you can understand it reasonably quickly. A component like the one in the article is pretty good like that. It just routes traffic according to weights. It doesn't care what the weights represent. It doesn't care where the servers are. It doesn't care what the traffic is
The team that owns it needs to understand it. Everyone else can just use it.
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
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.
That's exactly his point/the area of cost saving - that they didn't actually need as many hashes as they had started with. The trick was in finding out how many hashes they could cull without degrading load balance.
So interesting to see. Though I think if Cloudflare really wanted to safe more memory, there are even more strategies. Just starting with pointer compression, even if that is not an option, other techniques exist in rust. Assuming some numbers in from the previous post, with 250GB per byte wasted, you could shave off 2bytes of every pointer or 4 if you can fit them into a context related memory cage. And even that is just a beginning here.
CPU DRAM can't really be used for inference efficiently -- inference mostly wants memory bandwidth, not memory capacity, and GPU DRAM has >10x more bandwidth. The fabs can switch between them but you can't switch after the fact.
Those machines with GPUs still need RAM of their own, and they generally want large caches to avoid SSD penalties. You even see this spill out in the form of costs for KV cache in <1min, 5m, 1hr rates etc.
This is just wrong unless you're using some confusing definition. Notice that companies trying to do lots of inference aren't looking for CPUs, they're looking for GPUs/TPUs.
It's crazy to realize 100TB of RAM isn't that much anymore. 10TB server racks are already in production. Before long we'll have 100TB racks serving one instance of an LLM.
I’m not sure why folks are finding this so revolutionary. There are teams of scientists at big techs with PhDs working on all kinds of optimization across compute fleets. This seems cute but its exposition of math is more along the lines of “look at how cool I am that I could do a bit of calculus”, and that makes me question the technical depth at CF.
I found the motivation pretty lackluster: nowhere does it actually explain why you use consistent hashing (dividing the item space naively/regularly would actually cause much more than 1/n items to move, which is unintuitive) and how you actually use it.
That said, it got me to spend a few minutes studying this and got me to understand the key bit I was missing.
I've hit the same thing at smaller scale — once you know the real cardinality, shaving a few bytes per entry beats the clever stuff that never got profiled.
I read the article thinking it would make for a great brain puzzle, but I quickly decided there's something wrong with the question setup because the initial solution didn't make sense. I assumed it was just missing a constraint that would be revealed later, but I'm still not seeing it -- the article just kept patching up the flaws in the wrong solution, the one that is more complicated than the straightforward one.
I'm probably still missing something obvious? It's probably something to do with "...in a way that does not require large changes when servers are added or removed."
But let's start with the problem as initially posed: you have an infinite stream of tasks and you need to deterministically assign them to N servers. (Perhaps you have to shard the collections of servers, so not every load balancer knows about all of them? But no, that would break the solution in the article.) Ok, then hash the task request (I assume that you hash it, the article doesn't explicitly say, but that's how you'd get determinism) and take that hash mod N, that's your server index.
Why hash the servers too? If you roll 6 dice, and then another one to choose which die to use, you're not getting any more randomness. You're matching up two sides, the tasks on one side and the servers on the other; no need to randomize both.
Ooh, but that's not a perfect distribution? Ok, if the hash value is large enough to be in the at most N-1 slop values at the top of UINT_MAX, then roll again (compute another hash). But CF is happy with 8% unevenness, there should be no problem with this 0.1% or whatever.
Also, how do they find the nearest server hash to a task hash? Surely it's not a log(n) binary search through sorted server hashes, I hope?
Weights break this scheme. Now each server has some number of tickets. So you compute hash % T (where T=total tickets) and have to figure out what server that is. There's probably a more clever way, but you could make a big array of (2-byte!) server indexes, one per ticket, and just fill them in and look up at index hash % T.
That's 2 bytes per ticket, which feels uncomfortably wasteful if weights can be large. That's where things get more complicated for me: since the tasks are hashed, it doesn't matter what order a server's indexes come in relative to other servers', so sort them by descending weight. [I'm starting to suspect I'm making a fool of myself here by missing something obvious with the whole setup...] Now you can make an array of indexes for servers with the highest weight, then the next lower, then the next. Record the number of servers of each weight. Then you can take the hash % T and figure out which array it's in, then divide by the weight to give the index within that array.
To reduce the number of per-weight arrays, you can restrict the weights allowed. If you restrict weights to be powers of two, you can eliminate a division by using a shift. If you really want more flexible weights, you can allow servers to be in more than one of the arrays. Let the arrays be powers of two, and then add an entry to each array corresponding to 1 bits in the binary representation of the weights. That increases the total memory usage of the arrays, so you could somewhat restrict the allowed weights by rounding to the nearest number with, say, 2 or 3 "on" bits at most. With at most 2 bits, that means weights are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, .... The error really isn't bad.
And this should all be easily doable without any branches, I'm pretty sure. As long as you statically cap the max weight.
Anyway, that's just plowing through with the straightforward approach, and I still think I'm probably missing something major here. I imagine with large numbers of servers, some go down, so fast deletions are probably important. You can get by a little while by marking dead servers and if you "roll" one, just roll again. (Yes, deterministically, assuming other load balancers agree that the server is down.) But when more than some number of servers go down, you'd want to kick off a background task to rebuild a new set of tables -- so that's a factor 2 in size usage to have them both in memory during the rebuild.
Adding is trickier, you'd probably want to do a 2-level structure where first you use the hash to decide whether it's in the old set that the table is built for or the set of servers that hasn't been incorporated yet (you'd collect these over time, and empty them out on the next table rebuild.) It's a little weird, because the load balancers' outputs would only agree when the added and deleted sets agreed, but I don't see how to do better than that. (I think you could set up some kind of synchronization scheme so that the old sets would agree, which would make them usually agree on which of the old set of machines gets it.)
Somebody, feel free to tell me I'm being stupid! I'm sure there's a constraint that I'm missing, given that my understanding of the initial problem doesn't require any memory at all except for the servers' info.
(Or if not, I'll let you know where I'd like to receive shipment of 1% of the memory I've saved...)
You hash the servers because then adding or removing a server doesn't directly affect other servers position on the ring; adding a server just takes some load from som servers.
This is useful because you want stickiness, so requests for the same key mostly go to the same server.
Sorting servers by weight means that removing or adding a server will shift a lot of traffic from the servers it used to go to. A flapping server early in the list will break stickiness for the whole set of servers.
The simplicity of stable hashing means you don't have to think about new sets, old sets, table rebuilds, synchronisation schemes etc, and that's useful because every such extra step adds bugs and corner cases
The part I missed is that the load balancers don't have a consistent view of the set of servers. There is no magical synchronization scheme that creates that consistent view. You want load balancers with slightly different ideas of what servers are available to mostly make the same choices for the servers they do agree on.
Doh! I should have been able to infer that from the original solution.
Not foolish. The constraint of no-need-for-globally-consistent-state is so important and rules out so many approaches that it was well worth stating in the article.
Indeed the statistical model described in the article does not model the distribution over server hash allocations you'd get if you allow them to be inconsistent across load balancer hosts, so the model actually models (and thus implies) a single global source of truth that they probably don't have in practice.
Well, given that I knew that I was probably missing something, and the fact that their solution made no sense with the constraints I was using, pretty strongly implied that there was an additional constraint. And that's a fairly obvious one to have.
I can't do the math to prove it, but their solution still seems wrong to me. Rather than generating and storing and searching so many hashes, it seems like you should get partway there with a different sampling procedure that doesn't do quite as well with the inconsistent sets of servers, and then only use duplication to limit the consistency loss.
Simple example: use their scheme but instead of choosing the first server to the left of the probe, grab the first two and flip a coin to decide which one to use. That already spreads the bucket variance out a bit, without using any extra space. It does have a penalty in that if one balancer has a server that the other doesn't, then it spreads out the range of probes that could get a disagreement. But I don't know how to quantify that; if the balancers disagree on the set of servers available, you have to produce different results part of the time, and I haven't thought through how to characterize when that disagreement is "bad".
Then you could extend that to looking at the previous 8 servers. Or the previous k tickets, if you give each server a ticket for each weight unit.
The math works out easier if you sample regions of probe space rather than server counts: hash the incoming task, map that to a range of space on the number line, and all servers within that range are your candidate set. Choose from that set, making the candidates be either equally weighted, weighted proportionally to their weight (size/capacity/whatever), or weighted by how much they got shafted by the random distribution of the server hashes.
I get EBRAINTOOSMALL when I try to work out the statistics, especially when I try to figure out what the inconsistency cost is, but intuitively it still seems better than recording a bajillion hashes for each server. (With the latter sampling mechanism, you'd need to deal with the possibility of probing a window with no server in it, either by double hashing the task and trying again, or expanding the probed region. Details schmetails.)
In practice, I'd probably simulate it and look at the distributions. Or nerd snipe a math geek.
The coin flip method you describe breaks the same-query same-server locality (unless adding or removing servers) that is one motivation for the consistent hashing method.
You could solve that by storing the new-query flip result, but the goal was reducing storage…
I'm assuming all coin flips are deterministic based on the task. In this case, it'd be equivalent to generating a slightly longer hash and using a couple of bits for the "coin flip". (Or just generating a new hash with 1 or 3 bits or whatever you need.)
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
I don't remember those days with a ton of fondness. Yes, the challenge was fun, but I really wanted to ship it and get my product in the hands of customers. Now I can spend more time thinking about what they want and less time about what the computer wants.
Yes, I remember those too. The costs of manual memory management were real and were not low.
But costs on the cloud are real too, especially now. I’ve been living in JVM land for a very long time, but now it’s especially clear how important lean services are. Especially now that the bar for writing lean code is so much lower: let the borrow checker figure it out, etc.
I just spent a couple days wringing out more performance/memory efficiency for our services. Nice gains to be sure, but it’s still so immensely wasteful compared to something well written running native. If it was my money, I’d be going native for sure.
> But costs on the cloud are real too, especially now. I’ve been living in JVM land for a very long time, but now it’s especially clear how important lean services are. Especially now that the bar for writing lean code is so much lower: let the borrow checker figure it out, etc.
I don't think even Cloudflare bothers with this waste of time. If they did, they would certainly not have built their global infrastructure on JavaScript running on V8. They'd have done what Google and old-time Facebook did and built their whole infrastructure on low-level system languages, and hiring the world's leading minds on the subject to milk the last drop of performance from their hardware.
Even Google stopped to look at the problem and came up with Go. Not V8.
Google came up with Go because:
> The key point here is our programmers are Googlers, they’re not researchers. They’re typically, fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
From Rob Pike
All those things happened before the era of decent AI.
Also, it really does matter what you're building. Yet another CRUD app? Don't waste time on (super) lean languages - use Go or something else you like and move on.
Building a Kafka replacement? Making something that processes gobs of data quickly? Perhaps think about using something lean and efficient, as the economics have changed. "waste of time" (or memory) also applies to the cloud and your (or your company's) bill. And if you haven't noticed, you're being ripped off on the cloud, running something 10-50x less efficient has real bottom line impact.
Different people are different.
Some of us find production and optimization more interesting than marketing and distribution.
And its this obsession with shipping things as fast as possible quality be dammed that got us basic weather apps that eat a gigabyte+ of RAM.
And yet the world still turned
The world turned millenia ago and will turn millenia later.
The problem statement is of applications using up expensive RAM. Incidentally, expensive RAM is just one of the problems we face in the computing space. Forced obsolescence is another, when running hardware needs to be replaced because software is built for only newer CPUs.
> because software is built for only newer CPUs.
You are right, but it reads (to me, could be just me) you mean newer specs which used to be true when I shipped software in the 70-90s; you mean faster machines / more memory right? Like installing a new version of software or OS and suddenly all memory is used, system is swapping and you did not ask for that but some obscure feature you didn't need needed to be shipped fast.
> The problem statement is of applications using up expensive RAM. Incidentally, expensive RAM is just one of the problems we face in the computing space.
You need to stop and think about the problem. Nowadays RAM is expensive because many people now want to max out their computers with RAM to run LLMs and AI coding assistants. Today's software is still the same software that ran perfectly well half a dozen years ago. Cloudflare happens to operate a large global computer infrastructure, and it's scale is such that 1% gains are lauded as fantastic cost savers. But that's the bean counter's perspective, pointing out that they saved a bean.
> Today's software is still the same software that ran perfectly well half a dozen years ago.
This statement is quite honestly not true at all. Just take the two largest OS from 6 years ago and compare resource usage between them and you will find you are incorrect, never mind the software running on it.
> Nowadays RAM is expensive because many people now want to max out their computers with RAM to run LLMs and AI coding assistants.
Source? I imagine the amount of people trying to run local LLMs is miniscule. RAM is expensive because a handful of companies have spent billions buying all of the compute.
Sam and Dario really maxed out their rigs.
Thankfully the world's turning is not decided by big tech
Probably not for the lack of trying.
That statement can be used to justify anything, to the point it is utterly useless.
— Humanity has been on the decline. People are hateful towards each other, striking their fellow man and poisoning the environment. Despots eventually launched nukes which killed everyone but the cockroaches.
— And yet the world still turned.
For the rich, those in developing countries often were behind
On the contrary. Industrial developing countries saw bigger % increases in their economic growth in the last couple of decades than the fully developed "old" western ones. Mostly due to "the rich" shipping western jobs there to cut costs and increase their margins.
For example the likes of Poland, China, India and Vietnam were and still are growing like crazy when you compare to the likes of UK or Germany.
> And its this obsession with shipping things as fast as possible quality be dammed (...)
You seem confused. Allocating more memory than optimal levels is not a measure of quality. Similarly, a web page is not suddenly lower quality if an image asset is 50kb instead of 25kb. And how much complexity and engineering effort and bugs are you willing to tolerate to halve your memory allocations?
You are conflating quality with mindless minimization, not even knowing or caring that are the tradeoffs. The blog post you're commenting on starts by presenting the case for celebrating small improvements, even 1% improvements at a time. A similar 1% improvement in a mobile app is at like 1MB. Do you ever notice it? How many hours of engineering effort are you hoping to spend on this nonsense? And you prefer to spend it on this or in actually fixing a bug or implementing a feature?
This puerile conflation of minimization with quality suggests your personal notion of quality has no bearing on what quality actually is.
> And how much complexity and engineering effort and bugs are you willing to tolerate to halve your memory allocations?
You seem to be confused about this relationship. It's usually exactly the opposite.
The wasteful applications are generally not well reasoned about and half assed implementations. That's why they're guzzling resources
There is ofc a middle ground, because targeting eg incredibly resource constrained embedded systems will naturally increase complexity, but that's something entirely different to the scenario this discussion was about up to this point.
Exactly, that`s why i refuse to call 99.9% of "software engineers" engineers. Imagine you optimize a aircraft turbine 1%....man you get to drink a pool of champagne with the highest ceo's and aircraft carriers try to buy that turbine as fast as possible.
But with software and a install base of some millions 1% optimization is seen as wasteful, its like software slop is acceptable since forever because hardware gets faster, and electricity is "green" anyway.
Resource constraints have historically been a bastion of quality engineering, though. The relationship is not directly causal, but any time an engineer must not only solve a problem but _fit it within some kind of a budget_ vs having an unlimited budget, it forces them to slow down and think more carefully about what they are producing and how well it actually functions.
Ultimately it is an expression of anti-fragility: some minimal challenge must be met and conquered on many different axes of a production in order to help the full production itself mature to the best possible quality.
It is the same reason we exercise, the same reason that cars and toilets and so many products greatly increase in quality after emissions and usage and waste-related regulations get applied from above, etc.
The appreciation of the refining force of outside limitations is not about min-maxing, but it is at least partly about curbing the min-maxing of other concerns such as "ship the fastest garbage possible to move on to the next opportunity to repeat that process".
incredible way to put it!!
(Cat reading newspaper) I should build a database out of pointers
I wish I could care more about what the computer wants (because it’s fun). I couldn’t care less what the product demands.
"Now I can spend more time thinking about what they want and less time about what the computer wants."
What if they want memory efficiency
They wanted that in the 90s, didn't work out well as a software product https://en.wikipedia.org/wiki/SoftRAM
To rephrase the question, what if they wanted software that used less memory, i.e., software that used memory more efficiently
The OP, GGP and GP are about reducing memory usage by software
Pretending the parent question is about a different subject is unconvincing. The context does not support it
The vast majority of people do not care about memory efficiency on the levels we're talking about. I've never met a non-technical person who has cared. And out of the technical people that I know (which represent less than 5% of the population), no more than half of them have complained about the memory usage of an electron app.
So this hypothetical is wrong.
Or, they care but they lack the vocabulary to express what they care about.
You can get a new laptop to run software A or competing software B.
You can pay $1000 for the laptop with 4GB of RAM, and software A either can't run on that or will act like pulling teeth, so that software requires you to upgrade to 16GB of RAM which will put you back another $2000.
Or you can run software B which will hum along perfectly smoothly on the original $1000 laptop.
(All of that of course simplifying right past "everyone runs every app 24/7 with five trillion browser tabs open")
Are you honestly suggesting that the end user doesn't care about having to throw exponentially more money at stuffing RAM into their PC just to make the game all their friends are playing online function?
> Or, they care but they lack the vocabulary to express what they care about.
That's speculative to the point of being conspiratorial.
> Are you honestly suggesting that the end user doesn't care about having to throw exponentially more money at stuffing RAM into their PC just to make the game all their friends are playing online function?
I'm extremely clearly not suggesting that. Don't make up things and pretend that other people said them. Engage honestly or not at all.
Customers often want to pay less, and shareholders often want lower capital costs. A tasteful optimization is a win-win. The opportunity cost should be traded off against new features of course, but tasteful optimization is a good thing for customers.
While it's nice to see this focus, while they highlight absolute figures, we are still talking about 1% improvement. For most other software systems, nothing worth putting effort in for.
> In a way, RAM becoming more expensive has ushered in a new era of forced optimizations, which I'm really happy for
Isn't this mainly Cloudflare's scale though? That's literally also what's in the introduction written as the reason why they are doing the optimization
During the Moore's Law years you didn't have to optimize much, if you did a significant release yearly computer hardware grew faster than your optimization problems.
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…
This is pleasant coincidence. Really like your site and it's queued to send in my newsletter in the morning! Just happened to see your comment here while I was reading. Great work.
Oh super — I appreciate that!
> 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…
Tried out the first 1000 words in Pangram, and it seemed happy it was human written. Not surprised either, it has been some of the better writing I've seen out of Cloudflare recently.
An AI would have known that saying, “Hi, mom” in a professional post was a bad idea.
Great - now you've trained the next set of AI to put things like "Hi, mom" into their text as a tell that they're human ...
Please stop using this stuff. It's snake oil.
No, pangram is fairly decent, unlike the others.
Maybe, but when I used it recently on my annoyingly AI-written something it said 100% human.
They do deliberately err on the side of not accusing people of using AI when unsure. I think that's a good decision.
Do you know it was actually AI? I've seen humans imitating AI "it's not X — it's Y" to try to fool it that it correctly guessed was still human. Humans did use those patterns before AI so they're not enough on their own to flag.
Yeah, because I had generated it, and I wanted to see if I could get it to sound more human with pangram’s crit.
I don’t know if I’m just a lot more sensitive, but I find it really hard to write up even basic communication with Claude. Super overwrought.
What does Cloudflare make possible for your project?
Super cheap storage and CDN for rapid image access — plus bot control.
That’s some great work! It’s interesting to read the LLMs translation of the yoga sutras
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.
I think they do only a hash per request. The 160*weight hashes were done per server (per feature set), to partition the hash space. Per request you do a single hash and then a lower_bound on a sorted map to find the serving server (again, on the ring appropriate for the features required by the request, so likely a hash map lookup first)
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
Who cares if you can buy all the RAM available. To hell with small business and working class who now cannot afford it.
Plus it's limited to 65k entries. Perhaps a btree where parent nodes sum the weights of child nodes would work well. Using the input hash scaled by total weight, a binary search lookup would compute the partial sums for comparison on the fly. Adding/removing a node would only update the ~8 parents when the btree order is 4. Eytzinger layout and struct-of-arrays could be used to improve cache locality during lookup. This does mean an add/remove could drastically change the overall mapping, perhaps that's why consistent hashing is used instead.
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.
I think you're speaking like a software engineer, which is understandable, and not like a historian or economist. There's no reason to believe math based jobs would survive. The models regularly do well on math problems. You can auto-research loop ways to optimize memory usage for any particular program.
The point isn't that "doing math" is safe. Auto-research solves one target variable in one system, doing it at scale where say one developer is SME for the agentically manged 200 microservices down the line, heh I mean you certainly can, but good luck with that token cost of auto-research when that problem space is O(microservice^2). I point at that example yesterday of that optimized database memory with the comments pointing out that the specific problem fit in memory, over optimized and didn't generalize. The problem isn't the work, but the rework. A historian should know that new solutions to problems doesn't lead to "no problems ever again" but only problems with barriers that the new solution doesn't solve.
The argument is probably that LLMs can find those optimizations cheaper than a human expert. Since LLM cost at fixed capability seems to be going down you either expect humans to be completely replaced or human wages to be lowered by LLMs.
I expect average human wages for programming to get lower and the overall percentage of the developer to move lower wage countries and this probably means away from the US and US salary expectations. Meat proxies and agentic CRUD will be off-shored to low wage Asian or even African countries with AI handling language barriers. Why wouldn't they be? Why pay six figures for a meat proxy? Product Builders should weather the storm the most, but they'll be the high end skilled PMs/engineers that of the overall industry but probably won't break 10% of total global headcount. In a world where knowing the domain will be the key driver of differentiation, as building averages out and knowing the customer and how to market to them becomes the differentiator, being closer to the target market will fragment competition from four global winners with over 10k employees in a space to 100 niche/regionally tailored winners with maybe 500 employees a piece. Not to mention if you thought GDPR was a pain, wait until AI laws that vary by country to country get added in.
I also expect as AI becomes more cost sensitive once the quality plateaus (there's only so many ways to get an answer to 100% right), the data centers are going to chase where the cheap power is, and this long term is likely to be in high-solar locations. So lower latitudes. Doesn't rule out places like Texas of course, but places like India, Mexico, Brazil, Israel or Saudi Arabia will have home field advantages.
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.
My intuition around larger companies is they are already impenetrable silos, and AI makes it worse
I feel like any company whose products have RESTful interfaces are already there…
One wants to turn on an indicator on a remote device. A simple Boolean value. But we need networking, TLS, authentication plugins, certificate validation, distributed logging, containers, orchestration, HTTP client/server, interprocess communication, daemon dependency management, …
Sure, one can say each of these layers and abstractions has an important and justifiable purpose. But one can also step back and start wondering - what the hell are we really doing???
At some level, it seems like each layer of abstraction has to manage others, only simply because they exist.
Imagine the simplicity of 1800s telegraph signaling - no software!
Too often we build systems with Fortune-50 style hierarchies when a 5-person team could do the whole job.
Build a system as simple as possible but no simpler.
An 1800s telegraph system doesnt work in the modem world, there is far too much communication and the system would just collapse into molten slag.
All those things you've listed are because we live in an adversarial world and I'd steal all your money off the telegraph wire if you tried it.
Kind of like analogue TV. Sure it worked and was simple, but consumed some prime spectral real estate.
Having worked in hardware for a moment, everything we do in software is like this. Even C.
There are a whole series of blog posts from the Fishworks guys explaining why it could possibly be so hard to turn on one LED.
But Oracle probably deleted then so you'll have to find them on archive.org.
like this one? https://eschrock.dtrace.org/2008/07/
And at what point does a company start to care about performance? 100TB of RAM is expensive as hell, but getting products to market faster was worth the cost
Cloudflare is unusual in that their product is performance and their costs are primarily hardware and networking. You see similar performance initiatives from companies like AWS who also need to maximise their hardware usage.
Whereas for somewhere like Burger King, the costs are all rent and staff, so they wouldn’t care how much RAM their website uses. But you would see similar optimisation in their supply chains for their ingredients, and their rotas to reduce staffing.
Actually, AI creates spaghetti faster than any human ever could before.
Do you feel like this is a very meaningful comment? Will someone go "mm yes, actually it's spaghetti, I didn't think of that.."
Are you trying to succinctly say AL'S spaghetti code outweighs the benefits of what it produces quickly?
If you're not saying it outweighs it, what are you saying?
The steelman argumentation is probably that spaghetti doesn't matter to LLMs and no humans will read that code anyway.
I mean you can just pause and refactor regularly. I tend to use every ~4th session as an opportunity to refactor, adjust interfaces, break overly large modules into smaller ones and suchlike.
>at what point does a company become a collection of impenetrable siloes, where nothing really does what you expect?
Around the year 2015.
The trick is to keep the silos losely coupled and small enough that you can understand it reasonably quickly. A component like the one in the article is pretty good like that. It just routes traffic according to weights. It doesn't care what the weights represent. It doesn't care where the servers are. It doesn't care what the traffic is
The team that owns it needs to understand it. Everyone else can just use it.
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
Thanks! Maybe dial it back or people are going to think I paid you
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.
That's exactly his point/the area of cost saving - that they didn't actually need as many hashes as they had started with. The trick was in finding out how many hashes they could cull without degrading load balance.
So interesting to see. Though I think if Cloudflare really wanted to safe more memory, there are even more strategies. Just starting with pointer compression, even if that is not an option, other techniques exist in rust. Assuming some numbers in from the previous post, with 250GB per byte wasted, you could shave off 2bytes of every pointer or 4 if you can fit them into a context related memory cage. And even that is just a beginning here.
Someone really needed a few hundred TB to waste on inference and went looking under the rugs…
CPU DRAM can't really be used for inference efficiently -- inference mostly wants memory bandwidth, not memory capacity, and GPU DRAM has >10x more bandwidth. The fabs can switch between them but you can't switch after the fact.
Those machines with GPUs still need RAM of their own, and they generally want large caches to avoid SSD penalties. You even see this spill out in the form of costs for KV cache in <1min, 5m, 1hr rates etc.
yeah there's some KV cache offload
The majority of inference actually does happen in cpu.
This is just wrong unless you're using some confusing definition. Notice that companies trying to do lots of inference aren't looking for CPUs, they're looking for GPUs/TPUs.
It's crazy to realize 100TB of RAM isn't that much anymore. 10TB server racks are already in production. Before long we'll have 100TB racks serving one instance of an LLM.
I’m not sure why folks are finding this so revolutionary. There are teams of scientists at big techs with PhDs working on all kinds of optimization across compute fleets. This seems cute but its exposition of math is more along the lines of “look at how cool I am that I could do a bit of calculus”, and that makes me question the technical depth at CF.
I found the motivation pretty lackluster: nowhere does it actually explain why you use consistent hashing (dividing the item space naively/regularly would actually cause much more than 1/n items to move, which is unintuitive) and how you actually use it.
That said, it got me to spend a few minutes studying this and got me to understand the key bit I was missing.
I'm surprised to see no mention of hierarchical rendezvous hashing in either the article or the comments here.
It is purpose-designed for exactly this type of proxy/cache load-balancing scenario!
I've hit the same thing at smaller scale — once you know the real cardinality, shaving a few bytes per entry beats the clever stuff that never got profiled.
Stop hoarding RAM. Are they going to offload it through ebay? Unlikely.
I definitely enjoyed this writing style more than a lot of the recent cf blog posts. Cool article!
Every single optimization stories I read such as these make me super happy
I like that they have a performance team that actually tries to improve their products over time.
I also really appreciate the fact that this is human-written and not just AI slop. It’s refreshing to actually read English instead of Claudelish.
I can imagine the other internal teams looking at this.. "100 TB gets you attention? Hold my beer.. we will try that as well!"
It’s nice to see Cloudflare is letting humans write the blog posts again after all the fallout from their LLM slop blogs
Um.
I read the article thinking it would make for a great brain puzzle, but I quickly decided there's something wrong with the question setup because the initial solution didn't make sense. I assumed it was just missing a constraint that would be revealed later, but I'm still not seeing it -- the article just kept patching up the flaws in the wrong solution, the one that is more complicated than the straightforward one.
I'm probably still missing something obvious? It's probably something to do with "...in a way that does not require large changes when servers are added or removed."
But let's start with the problem as initially posed: you have an infinite stream of tasks and you need to deterministically assign them to N servers. (Perhaps you have to shard the collections of servers, so not every load balancer knows about all of them? But no, that would break the solution in the article.) Ok, then hash the task request (I assume that you hash it, the article doesn't explicitly say, but that's how you'd get determinism) and take that hash mod N, that's your server index.
Why hash the servers too? If you roll 6 dice, and then another one to choose which die to use, you're not getting any more randomness. You're matching up two sides, the tasks on one side and the servers on the other; no need to randomize both.
Ooh, but that's not a perfect distribution? Ok, if the hash value is large enough to be in the at most N-1 slop values at the top of UINT_MAX, then roll again (compute another hash). But CF is happy with 8% unevenness, there should be no problem with this 0.1% or whatever.
Also, how do they find the nearest server hash to a task hash? Surely it's not a log(n) binary search through sorted server hashes, I hope?
Weights break this scheme. Now each server has some number of tickets. So you compute hash % T (where T=total tickets) and have to figure out what server that is. There's probably a more clever way, but you could make a big array of (2-byte!) server indexes, one per ticket, and just fill them in and look up at index hash % T.
That's 2 bytes per ticket, which feels uncomfortably wasteful if weights can be large. That's where things get more complicated for me: since the tasks are hashed, it doesn't matter what order a server's indexes come in relative to other servers', so sort them by descending weight. [I'm starting to suspect I'm making a fool of myself here by missing something obvious with the whole setup...] Now you can make an array of indexes for servers with the highest weight, then the next lower, then the next. Record the number of servers of each weight. Then you can take the hash % T and figure out which array it's in, then divide by the weight to give the index within that array.
To reduce the number of per-weight arrays, you can restrict the weights allowed. If you restrict weights to be powers of two, you can eliminate a division by using a shift. If you really want more flexible weights, you can allow servers to be in more than one of the arrays. Let the arrays be powers of two, and then add an entry to each array corresponding to 1 bits in the binary representation of the weights. That increases the total memory usage of the arrays, so you could somewhat restrict the allowed weights by rounding to the nearest number with, say, 2 or 3 "on" bits at most. With at most 2 bits, that means weights are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, .... The error really isn't bad.
And this should all be easily doable without any branches, I'm pretty sure. As long as you statically cap the max weight.
Anyway, that's just plowing through with the straightforward approach, and I still think I'm probably missing something major here. I imagine with large numbers of servers, some go down, so fast deletions are probably important. You can get by a little while by marking dead servers and if you "roll" one, just roll again. (Yes, deterministically, assuming other load balancers agree that the server is down.) But when more than some number of servers go down, you'd want to kick off a background task to rebuild a new set of tables -- so that's a factor 2 in size usage to have them both in memory during the rebuild.
Adding is trickier, you'd probably want to do a 2-level structure where first you use the hash to decide whether it's in the old set that the table is built for or the set of servers that hasn't been incorporated yet (you'd collect these over time, and empty them out on the next table rebuild.) It's a little weird, because the load balancers' outputs would only agree when the added and deleted sets agreed, but I don't see how to do better than that. (I think you could set up some kind of synchronization scheme so that the old sets would agree, which would make them usually agree on which of the old set of machines gets it.)
Somebody, feel free to tell me I'm being stupid! I'm sure there's a constraint that I'm missing, given that my understanding of the initial problem doesn't require any memory at all except for the servers' info.
(Or if not, I'll let you know where I'd like to receive shipment of 1% of the memory I've saved...)
You hash the servers because then adding or removing a server doesn't directly affect other servers position on the ring; adding a server just takes some load from som servers.
This is useful because you want stickiness, so requests for the same key mostly go to the same server.
Sorting servers by weight means that removing or adding a server will shift a lot of traffic from the servers it used to go to. A flapping server early in the list will break stickiness for the whole set of servers.
The simplicity of stable hashing means you don't have to think about new sets, old sets, table rebuilds, synchronisation schemes etc, and that's useful because every such extra step adds bugs and corner cases
Ah, right. The joys of being a fool in public.
The part I missed is that the load balancers don't have a consistent view of the set of servers. There is no magical synchronization scheme that creates that consistent view. You want load balancers with slightly different ideas of what servers are available to mostly make the same choices for the servers they do agree on.
Doh! I should have been able to infer that from the original solution.
Not foolish. The constraint of no-need-for-globally-consistent-state is so important and rules out so many approaches that it was well worth stating in the article.
Indeed the statistical model described in the article does not model the distribution over server hash allocations you'd get if you allow them to be inconsistent across load balancer hosts, so the model actually models (and thus implies) a single global source of truth that they probably don't have in practice.
Well, given that I knew that I was probably missing something, and the fact that their solution made no sense with the constraints I was using, pretty strongly implied that there was an additional constraint. And that's a fairly obvious one to have.
I can't do the math to prove it, but their solution still seems wrong to me. Rather than generating and storing and searching so many hashes, it seems like you should get partway there with a different sampling procedure that doesn't do quite as well with the inconsistent sets of servers, and then only use duplication to limit the consistency loss.
Simple example: use their scheme but instead of choosing the first server to the left of the probe, grab the first two and flip a coin to decide which one to use. That already spreads the bucket variance out a bit, without using any extra space. It does have a penalty in that if one balancer has a server that the other doesn't, then it spreads out the range of probes that could get a disagreement. But I don't know how to quantify that; if the balancers disagree on the set of servers available, you have to produce different results part of the time, and I haven't thought through how to characterize when that disagreement is "bad".
Then you could extend that to looking at the previous 8 servers. Or the previous k tickets, if you give each server a ticket for each weight unit.
The math works out easier if you sample regions of probe space rather than server counts: hash the incoming task, map that to a range of space on the number line, and all servers within that range are your candidate set. Choose from that set, making the candidates be either equally weighted, weighted proportionally to their weight (size/capacity/whatever), or weighted by how much they got shafted by the random distribution of the server hashes.
I get EBRAINTOOSMALL when I try to work out the statistics, especially when I try to figure out what the inconsistency cost is, but intuitively it still seems better than recording a bajillion hashes for each server. (With the latter sampling mechanism, you'd need to deal with the possibility of probing a window with no server in it, either by double hashing the task and trying again, or expanding the probed region. Details schmetails.)
In practice, I'd probably simulate it and look at the distributions. Or nerd snipe a math geek.
The coin flip method you describe breaks the same-query same-server locality (unless adding or removing servers) that is one motivation for the consistent hashing method.
You could solve that by storing the new-query flip result, but the goal was reducing storage…
I'm assuming all coin flips are deterministic based on the task. In this case, it'd be equivalent to generating a slightly longer hash and using a couple of bits for the "coin flip". (Or just generating a new hash with 1 or 3 bits or whatever you need.)
Ah. That’s an unusual thing to mean by ‘coin flip’!
anyone remember 100tb hosting company?
TLDR: the existing implementation was poorly designed. They packed 2 integers better and saved memory.
does this mean RAM prices can go down now? Please?