Overflow in consistent hashing (2018)
rmarcus.info
rmarcus.info
Practical systems deal with this by not caring strongly about overflow (caches), by running at low enough utilizations that overflow is very unlikely given their item counts (e.g. Dynamo), by using explicit partitioning rather than consistent hashing (e.g. DynamoDB), by being able to take advantage of multi-tenancy to drive up per-physical-node utilization even in the case of low per-logical-node utilization, or by using some additional algorithmic sophistication (e.g. Chen et al https://arxiv.org/pdf/1908.08762).
In practice, this kind of overflow is a big deal for systems that deal with relatively small numbers of large objects, and are not as big a deal for systems that deal with large numbers of small objects. Try out the numbers in the page's "Handy Calculator" to see how that plays out.
It's also worth mentioning that this isn't unique to consistent hashing, but is a problem with random load balancing more generally. "Pick a random server and send traffic to it" is an OK load balancing strategy when requests are small and servers are large, but a terrible one when requests become relatively large or expensive. In the general load balancing/placement problem this is easier than the storage case, because you don't need to find requests again after dispatching them. That makes simple algorithms like best-of-2 and best-of-k applicable.
Your point about systems dealing with a relatively small number of large objects vs. small objects also makes sense: this is essentially the "cost" of an overflow (4kb spills once in a blue moon? Oh well, handle that as a special case. 4TB spills once in a blue moon? The system might crash). This is more obvious, as you also point out, in load balancing.
One aspect I found very counter-intuitive: before this investigation, I would've guessed that having a large number of large bins makes overflow increasingly unlikely. This is only partially true: more bins is obviously good, but larger bins are actually more sensitive to changes in load factor!
Overall, I think you are right that this is not really a concern in modern systems today. Compared to Dynamo, I still think Vimeo's solution (linked at the bottom of the post) is both intuitive and low-complexity. But regardless, more of an interesting mathematical diversion than a practical systems concern these days.
e.g. Ceph used to have a big problem with overloaded placement groups, causing some disks to get twice as much load; max throughput was when those maxed out, leaving the rest half-idle. I don't recall the details of the current solution, but I think it's equivalent to generating a random assignment, and then tweaking it to get rid of over-full bins.
The original Chord-style consistent hashing is easier in the P2P environments it was designed for, but typically consistent hashing is used today in much more closely-coupled systems.
Multiplicity does help with a major operational concern, though: when a node fails and recovery is needed, the recovery traffic can be spread uniformly across all cluster members rather than hot-spotting a small number of neighbors. Incidentally, this is a classic congestive collapse scenario in consistent hashed systems: a node looks failed because its overloaded, which starts recovery, which adds load to the neighbors which makes them look overloaded, and the whole thing collapses.
If you double the number of keys and you double the number of bins (load factor stays constant), then the problem becomes much worse very quickly.
If you double the number of keys and you double the size of each bin (load factor stays constant), then the problem diminishes as you suggest. BUT, larger bins are more sensitive to changes in load factor.
The sibling comment ( https://news.ycombinator.com/item?id=40415826 ) does a good job of summarizing how post-2018 systems handle this issue.