// 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.
Thanks for spotting this, what a silly typo :)
... Fixed
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.
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.