Consistent Hashing

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

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.