Consistent Hashing

#1

Post by ibobev » Sat, Sep 27, 2025, 9:03 PM UTC

Consistent Hashing
eli.thegreenplace.net

Re: Consistent Hashing

#2

Post by age123456gpg » Sun, Sep 28, 2025, 10:04 AM UTC

  // 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

Re: Consistent Hashing

#3

Post by commandersaki » Sun, Sep 28, 2025, 11:39 AM UTC

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.

Re: Consistent Hashing

#4

Post by eliben » Sun, Sep 28, 2025, 1:20 PM UTC

commandersaki wrote: post #3

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…

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.

Re: Consistent Hashing

#5

Post by eliben » Sun, Sep 28, 2025, 1:21 PM UTC

age123456gpg wrote: post #2

// 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

Thanks for spotting this, what a silly typo :)

... Fixed