{"id":17,"date":"2014-01-19T04:13:04","date_gmt":"2014-01-19T04:13:04","guid":{"rendered":"http:\/\/www.csforge.com\/?p=17"},"modified":"2014-04-15T16:32:01","modified_gmt":"2014-04-15T16:32:01","slug":"rendezvous-or-highest-random-weight-hrw-hashing-algorithm","status":"publish","type":"post","link":"http:\/\/www.csforge.com\/?p=17","title":{"rendered":"Rendezvous or Highest Random Weight (HRW) hashing algorithm"},"content":{"rendered":"<p>I committed an implementation of HRW on <a href=\"https:\/\/github.com\/clohfink\/RendezvousHash\">github<\/a>. It seems to have an advantage over consistent hashing in having an even distribution of data across all the nodes after modifications to the pool. \u00a0Consistent hashing mitigates its weakness by placing nodes multiple times into the ring creating many virtual nodes. \u00a0HRW tends to be slower with having to run hash functions against each node instead of the just once with the CH algorithm. \u00a0HRW is still very fast (ie 100k+\/sec if parallelized depending on hash function) with pool sizes smaller than 1000 nodes. \u00a0It is possible to achieve O(logN) lookups with HRW, this implementation is much simpler and is O(N) but with N being generally so small its irrelevant.<\/p>\n<p>It makes sense for a lot of things to use consistent hashing instead (providing you use virtual nodes!). To show the importance here is an example of using just a single token per node on the ring below.<\/p>\n<p><a href=\"https:\/\/raw.github.com\/clohfink\/RendezvousHash\/master\/images\/chd.png\" target=\"_blank\"><img decoding=\"async\" alt=\"\" src=\"https:\/\/raw.github.com\/clohfink\/RendezvousHash\/master\/images\/chd.png\" \/><\/a><\/p>\n<p>Only node4 takes the load of the 2 that were removed. However using HRW the distribution remains even<\/p>\n<p><a href=\"https:\/\/raw.github.com\/clohfink\/RendezvousHash\/master\/images\/hrwd.png\" target=\"_blank\"><img decoding=\"async\" alt=\"\" src=\"https:\/\/raw.github.com\/clohfink\/RendezvousHash\/master\/images\/hrwd.png\" \/><\/a><\/p>\n<p>If using say, 200 vnodes are added per node with CH the distribution looks the same as the HRW distribution above.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I committed an implementation of HRW on github. It seems to have an advantage over consistent hashing in having an even distribution of data across all the nodes after modifications to the pool. \u00a0Consistent hashing mitigates its weakness by placing nodes multiple times into the ring creating many virtual nodes. \u00a0HRW tends to be slower [&hellip;]<\/p>\n<div class=\"clearfix text-center more-button\"><a href=\"http:\/\/www.csforge.com\/?p=17\" class=\"btn btn-success\">Continue reading<\/a><\/div>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-17","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/posts\/17","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.csforge.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17"}],"version-history":[{"count":4,"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/posts\/17\/revisions"}],"predecessor-version":[{"id":25,"href":"http:\/\/www.csforge.com\/index.php?rest_route=\/wp\/v2\/posts\/17\/revisions\/25"}],"wp:attachment":[{"href":"http:\/\/www.csforge.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.csforge.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.csforge.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}