3 ms·
My favorite sharding/load balancing algorithm is Highest Random Weight, or Rendezvous hashing [0]. It has all the benefits of consistent key hashing without th
by jedberg 7y ago
My favorite sharding/load balancing algorithm is Highest Random Weight, or Rendezvous hashing [0]. It has all the benefits of consistent key hashing without the hotspots, and it doesn't require any coordination between nodes.
[0] https://en.wikipedia.org/wiki/Rendezvous_hashing https://en.wikipedia.org/wiki/Rendezvous_hashing
- ignoramous 7y agoSquid (http cache) uses Rendezvous Hashing, iirc. Google's Maglev Hash and Jump Hash are other alternatives that spring to mind: https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8 https://medium.com/@dgryski/consistent-hashing-algorithmic-t... Two years or so back, I stumbled on power-of-2 load balancing via Twitter Finagle documentation. Found it pretty interesting. Here is a relevant news.yc discussion: https://news.ycombinator.com/item?id=14640811 https://news.ycombinator.com/item?id=14640811 And of course, the exponential weighted moving average is a good algorithm too. It is, I believe, used by Elasticsearch. Cloudflare blogged abt using it, as well: https://blog.cloudflare.com/i-wanna-go-fast-load-balancing-dynamic-steering/ https://blog.cloudflare.com/i-wanna-go-fast-load-balancing-d...