Consistent Hashing(eli.thegreenplace.net)

17 pointsby ibobevvor 10 Monaten4 comments

eli.thegreenplace.net

https://eli.thegreenplace.net/2025/consistent-hashing/

4 comments

  // hashItem computes the slot an item hashes to, given a total number of slots.
  func hashItem(item string, nslots uint64) uint64 {
    digest := md5.Sum([]byte(item))
    digestHigh := binary.BigEndian.Uint64(digest[8:16])
    digestLow := binary.BigEndian.Uint64(digest[:8])
    return (digestHigh | digestLow) % nslots
  }

Should be using XOR: (digestHigh ^ digestLow) % nslots

elibenvor 10 Monaten

Thanks for spotting this, what a silly typo :)

... Fixed

commandersakivor 10 Monaten

Love this post. It's been always in the back of my mind to figure out how consistent hashing works, and Eli's presentation was concise and to the point.

So what qualifies for a good ring size? I'm thinking 2^32 or 2^64, since it is sparse and would be harder to find collisions when adding a (v)node. Or maybe there is a way to resolve collisions by trying different sequences when adding a vnode, such that if foo@8 is a collision, skip it an go to foo@9; I think deletion is still pretty straightfoward.

elibenvor 10 Monaten

Thanks for the kind words!

Regarding ring size, yes I'd say 2^64 is good. Since the representation is sparse, it seems safe but I'd be interested in hearing other views.