The consistent hash lookup is done as normal, then if balancing is enabled, we progress through the hash ring until we find a server that doesn't have "too much" load. In the case of equal weights for all servers, the allowed number of requests for a server is either the floor or the ceil of (num_requests * hash-balance-factor / num_servers); with unequal weights things are somewhat more complicated, but the spirit is the same -- a server should not be able to go too far above (its relative weight times) the average load. Using the hash ring to make the second/third/etc. choice maintains as much locality as possible given the load limit. --- src/lb_chash.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)
diff --git a/src/lb_chash.c b/src/lb_chash.c index a62dfb5..401e36e 100644 --- a/src/lb_chash.c +++ b/src/lb_chash.c @@ -242,6 +242,31 @@ static void chash_update_server_weight(struct server *srv) } /* + * This function implements the "Consistent Hashing with Bounded Loads" algorithm + * of Mirrokni, Thorup, and Zadimoghaddam (arxiv:1608.01350), adapted for use with + * unequal server weights. + */ +int chash_server_is_eligible(struct server *s) { + /* The total number of slots to allocate is the total number of outstanding requests + * (including the one we're about to make) times the load-balance-factor, rounded up. + */ + unsigned tot_slots = ((s->proxy->served + 1) * s->proxy->lbprm.chash.balance_factor + 99) / 100; + unsigned slots_per_weight = tot_slots / s->proxy->lbprm.tot_weight; + unsigned remainder = tot_slots % s->proxy->lbprm.tot_weight; + + /* Allocate a whole number of slots per weight unit... */ + unsigned slots = s->eweight * slots_per_weight; + /* And then distribute the rest among servers proportionally to their weight. */ + slots += ((s->cumulative_weight + s->eweight) * remainder) / s->proxy->lbprm.tot_weight + - (s->cumulative_weight * remainder) / s->proxy->lbprm.tot_weight; + /* But never leave a server with 0. */ + if (slots == 0) + slots = 1; + + return s->served < slots; +} + +/* * This function returns the running server from the CHASH tree, which is at * the closest distance from the value of <hash>. Doing so ensures that even * with a well imbalanced hash, if some servers are close to each other, they @@ -287,7 +312,19 @@ struct server *chash_get_server_hash(struct proxy *p, unsigned int hash) dp = hash - prev->key; dn = next->key - hash; - return (dp <= dn) ? psrv : nsrv; + if (dp <= dn) { + next = prev; + nsrv = psrv; + } + + while (p->lbprm.chash.balance_factor && !chash_server_is_eligible(nsrv)) { + next = eb32_next(next); + if (!next) + next = eb32_first(root); + nsrv = eb32_entry(next, struct tree_occ, node)->server; + } + + return nsrv; } /* Return next server from the CHASH tree in backend <p>. If the tree is empty, -- 2.9.3