Search code examples
hashdistributed-computingconsistent-hashing

Rendezvous vs consistent hashing

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:

Solution

  • 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.