Consistent Hashing

Posted3 months agoActive3 months ago

zoidb

98 points

25 comments

eli.thegreenplace.netTechstory

calmpositive

Debate

20/100

Consistent HashingDistributed SystemsAlgorithms

Key topics

Consistent Hashing

Distributed Systems

Algorithms

The post discusses consistent hashing, a technique used in distributed systems to map keys to nodes, and the discussion revolves around its implementation, variations, and related concepts.

Snapshot generated from the HN discussion

Discussion Activity

Active discussion

First comment

Peak period

96-108h

Avg / period

8.3

Comment distribution25 data points

Loading chart...

Based on 25 loaded comments

Key moments

01Story posted
Sep 29, 2025 at 4:16 AM EDT
3 months ago
Step 01
02First comment
Oct 3, 2025 at 12:17 AM EDT
4d after posting
Step 02
03Peak activity
13 comments in 96-108h
Hottest window of the conversation
Step 03
04Latest activity
Oct 4, 2025 at 3:07 AM EDT
3 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (25 comments)

Showing 25 comments

anotherhue

3 months ago

1 reply

Can't mention this without mentioning Akamai founder Lewin, who had a sad ending.

https://en.wikipedia.org/wiki/Daniel_Lewin

eatonphil

3 months ago

Wow I didn't know this history about Akamai, thanks for mentioning, interesting as a former Linode guy and a fan of consistent hashing.

sidcool

3 months ago

1 reply

The typo is really really bothering me, because the future generations would not be able to search for it.

mkl

3 months ago

1 reply

You can get things like this fixed with the Contact link at the bottom of the page (I just emailed them about it).

It's so much better to copy and paste the title of articles.

ndr

3 months ago

1 reply

They seem to have fixed the title. It looks wrong only here on HN now.

sidcool

3 months ago

Nice, thanks Dang.

eru

3 months ago

2 replies

Have a look at rendezvous hashing (https://en.wikipedia.org/wiki/Rendezvous_hashing). It's simpler, and more general than 'consistent hashing'. Eg you don't have to muck around with virtual nodes. Everything just works out, even for small numbers of targets.

It's also easier to come up with an exact weighted version of rendezvous hashing. See https://en.wikipedia.org/wiki/Rendezvous_hashing#Weighted_re... for the weighted variant.

Faintly related: if you are into load balancing, you might also want to look into the 'power of 2 choices'. See eg https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.... or this HN discussion at https://news.ycombinator.com/item?id=37143376

The basic idea is that you can vastly improve on random assignment for load balancing by instead picking two servers at random, and assigning to the less loaded one.

It's an interesting topic in itself, but there's also ways to combine it with consistent hashing / rendezvous hashing.

Snawoot

3 months ago

1 reply

I also double that rendezvous hashing suggestion. Article mentions that it has O(n) time where n is number of nodes. I made a library[1] which makes rendezvous hashing more practical for a larger number of nodes (or weight shares), making it O(1) amortized running time with a bit of tradeoff: distributed elements are pre-aggregated into clusters (slots) before passing them through HRW.

[1]: https://pkg.go.dev/github.com/SenseUnit/ahrw

karakot

3 months ago

1 reply

Does it really matter? Here, n is a very small number, which is almost a constant. I'd assume the iteration over the n space is negligible compared to the other parts of a request to a node.

eru

3 months ago

Yes, different applications have different trade-offs.

gopalv

3 months ago

1 reply

> if you are into load balancing, you might also want to look into the 'power of 2 choices'.

You can do that better if you don't use a random number for the hash, instead flip a coin (well, check a bit of the hash of a hash), to make sure hash expansion works well.

This trick means that when you go from N -> N+1, all the keys move to the N+1 bucket instead of being rearranged across all of them.

I've seen this two decades ago and after seeing your comment, felt like getting Claude to recreate what I remembered from back then & write a fake paper [1] out of it.

See the MSB bit in the implementation.

That said, consistent hashes can split ranges by traffic not popularity, so back when I worked in this, the Membase protocol used capacity & traffic load to split the virtual buckets across real machines.

Hot partition rebalancing is hard with a fixed algorithm.

[1] - https://github.com/t3rmin4t0r/magic-partitioning/blob/main/M...

eru

3 months ago

> This trick means that when you go from N -> N+1, all the keys move to the N+1 bucket instead of being rearranged across all of them.

Isn't that how rendezvous hashing (and consistent hashing) already work?

dataflow

3 months ago

2 replies

Is it just me or can you describe the whole scheme in one sentence?

tl;dr: subdivide your hash space (say, [0, 2^64)) by the number of slots, then utilize the index of the slot your hash falls in.

Or, in another sense: rely on / rather than % for distribution.

Is this accurate or am I missing something?

zvr

3 months ago

1 reply

You're missing that the hash space is not divided uniformly. Which means one can vary the number of slots without recomputing the hash space division -- and without reassigning all of the existing entries.

dataflow

3 months ago

I must've totally misunderstood what I read then. I'll give it another read, thanks!

immibis

3 months ago

That's the naive method which tends to redistribute most objects when the number of slots changes.

modderation

3 months ago

Ceph storage uses a hierarchical consistent hashing scheme called "CRUSH" to handle hierarchical data placement and replication across failure domains. Given an object ID, its location can be calculated, and the expected service queried.

As a side effect, it's possible to define a logical topology that reflects the physical layout, spreading data across hosts, racks, or by other arbitrary criteria. Things are exactly where you expect them to be, and there's very little searching involved. Combined with a consistent view of the cluster state, this avoids the need for centralized lookups.

The original paper is a surprisingly short read: https://ceph.com/assets/pdfs/weil-crush-sc06.pdf DOI: 10.1109/SC.2006.19

catoc

3 months ago

Was the HN-post title also hashed? (It’s inconstitent with the actual title)

Groxx

3 months ago

seems worth fixing the spelling mistake here - this is a consistent hashing post (currently "constitent hashing")

packetlost

3 months ago

I've implemented a cache-line aware (from a paper) version of a persistent, consistent hashing algorithm that gets pretty good performance on SSDs:

https://github.com/chiefnoah/mehdb

It's used as the index for a simple KV store I did as an interview problem awhile back, it pretty handily does 500k inserts/s and 5m reads/s and it's nothing special (basic write coalescing, append-only log):

https://git.sr.ht/~chiefnoah/keeeeyz/tree/meh

wyldfire

3 months ago

s/Constitent/Consistent/

Unless it's a clever play on "consistent", that is. In which case: carry on.

alanfranz

3 months ago

A final mention of the “simplifying” Lamping-Veach algorithm would have been great: https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf?ref=fr...

ignoreusernames

3 months ago

Another strategy to avoid redistribution is simply having a big enough number of partitions and assign ranges instead of single partitions. A bit more complex on the coordination side but works well in other domains (distributed processing for example)

sillypointer

3 months ago

https://www.metabrew.com/article/libketama-consistent-hashin...

Ketama implementation of consistent hashing algorithm is really intuitive and battle tested.

ryuuseijin

3 months ago

Shameless plug for my super simple consistent-hashing implementation in clojure: https://github.com/ryuuseijin/consistent-hashing

View full discussion on Hacker News

ID: 45411435Type: storyLast synced: 11/20/2025, 8:47:02 PM

Want the full context?