Rendezvous vs consistent hashing

user_1732769 0
Viewed 509

I read on Wikipedia:

Unlike consistent hashing, HRW (Highest Random Weight, aka Rendezvous Hashing) requires no precomputing or storage of tokens.

Why?

My understanding is that:

  • In consistent hashing, one hashes objects and sites independently (i.e. h(Oi) and h(Sj)) to the unit circle, and then for a given object, it finds the nearest site in the hashed space.

  • In HRW (Rendezvous hashing) one hashes both objects and sites simultaneously i.e. h(Oi, Sj), and then pick the highest hashed result to decide the destination site for an object.

so, if anything, it looks to me that in consistent hashing, one could choose to pre-compute and pre-store h(Sj)s but you are not required to do so. In other words, consistent hashing provides that flexibility whereas HRW doesn't.

Am I wrong? If so why?

Here's a reference description of HRW from the same link:

consistent-hashing distributed-computing hash
2 Answers

You are correct. The fact that we can pre-compute and pre-store h(Sj) is rather an advantage for consistent hashing.

Wikipedia states that the advantage for Rendezvous hashing is that its conceptually simpler to understand and implement (although I dont agree personally).

And it mentions one more advantage:

Rendezvous hashing also has the great advantage that it provides simple solutions to other important problems, such as distributed k-agreement.

user_19253880

The explanation with the circle for rendezvous hashing was wrong.

RendezVous Hashing: Hash(object + Site) : the site with the highest result (highest random weight (HRW) hashing) get to store the object. If you remove a site, for every object that was on that site, redo the operation Hash(object + Site) for each site left to find the one with the highest result.

Consistent hashing: Give each Site a number of Site-key(the higher the number of Site-key , the more uniform will be the repartition of objects, you generate them by : Hash(site + number) ). Put them on a circle.(All of this is the part that can be pre computed). To store an object, Hash(Object) to get an object-key, put it on a circle and find the nearest site-key clockwise. The site that has this site-key will store the object If you remove a site, you remove on the circle the site-keys the site had. For each object that was stored on that site , you go again clockwise on the circle to find the nearest site key.

user_126626480
Related