envoyproxy/envoy

HRW Hash Load Balancing

Open

#15,596 opened on Mar 22, 2021

View on GitHub
 (7 comments) (0 reactions) (0 assignees)C++ (5,373 forks)batch import
area/load balancingdesign proposalenhancementhelp wanted

Repository metrics

Stars
 (27,997 stars)
PR merge metrics
 (Avg merge 8d) (378 merged PRs in 30d)

Description

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

Contributor guide

Research direction
Study the existing ring hash load balancer implementation in Envoy and design an HRW hash variant following the rendezvous hashing algorithm. Consider integration with the existing load balancing infrastructure.
Tech stack
cpp
Domain
backend
Issue type
Feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
2
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
C++consistent hashing
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
70