HRW Hash Load Balancing

[Agent-Tao]

HRW Hash Load Balancing

(Highest Random Weight, HRW) hashing, an alternative to the ring based, consistent hashing, allows clients to achieve distributed agreement on which node (or proxy) a given key is to be placed in.

this hash has two advantages

1、Load balancing: Since the hash function is randomizing, each of the n nodes is equally likely to receive the key K. Loads are uniform across the sites.

2、High hit rate: Since all clients agree on placing an key K into the same node N , each fetch or placement of K into N yields the maximum utility in terms of hit rate. The key K will always be found unless it is evicted by some replacement algorithm at N.

how about adding HRW hash to envoy ?

https://en.wikipedia.org/wiki/Rendezvous_hashing

[snowp]

I think we would be amendable to adding this as a cluster or lb extension (doesn't exist yet, but I believe someone might be working on it) if someone is able to pick up the work.

[Agent-Tao]

so how about adding this hrw hash to lb policy? to be specific， in cluster.proto, add HrwHash to LbPolicy： enum LbPolicy { HRW_HASH = 8; }

and implement hrw hash lb as one type of HashingLoadBalancer？ @snowp cc @mattklein123

[mattklein123]

I think we are trying not add new stuff like this to the core unless necessary. It shouldn't be too much work to add an LB extension point and it would be good to go ahead and do that.

[Agent-Tao]

I am not sure how to add LB extension. can you tell me how to do it or give me some reference ? if it is not too much work and nobody work on it, i can take this. thanks. @mattklein123

[mattklein123]

The basic idea is you need to add a new TypedExtension configuration point for LB. It might be worth it to take a look at this ongoing PR which adds a new extension points and wires everything up. I will admit it's not trivial, but following an example it might not be too bad for the uninitiated. https://github.com/envoyproxy/envoy/pull/15619

[mattklein123]

Cross reference https://github.com/envoyproxy/envoy/issues/5598

[Agent-Tao]

thanks