Locality weighted load balancing

One approach to determining how to weight assignments across different zones and geographical locations is by using explicit weights supplied via EDS in the LocalityLbEndpoints message. This approach is mutually exclusive with zone aware routing, since in the case of locality aware LB, we rely on the management server to provide the locality weighting, rather than the Envoy-side heuristics used in zone aware routing.

When all endpoints are available, the locality is picked using a weighted round-robin schedule, where the locality weight is used for weighting. When some endpoints in a locality are unavailable, we adjust the locality weight to reflect this. As with priority levels, we assume an over-provision factor (default value 1.4), which means we do not perform any weight adjustment when only a small number of endpoints in a locality are unavailable.

Assume a simple set-up with 2 localities X and Y, where X has a locality weight of 1 and Y has a locality weight of 2, L=Y 100% available, with default overprovisioning factor 1.4.

L=X healthy endpoints Percent of traffic to L=X Percent of traffic to L=Y
100% 33% 67%
70% 33% 67%
69% 32% 68%
50% 26% 74%
25% 15% 85%
0% 0% 100%

To sum this up in pseudo algorithms:

availability(L_X) = 140 * available_X_upstreams / total_X_upstreams
effective_weight(L_X) = locality_weight_X * min(100, availability(L_X))
load to L_X = effective_weight(L_X) / Σ_c(effective_weight(L_c))

Note that the locality weighted pick takes place after the priority level is picked. The load balancer follows these steps:

  1. Pick priority level.
  2. Pick locality (as described in this section) within priority level from (1).
  3. Pick endpoint using cluster specified load balancer within locality from (2).

Locality weighted load balancing is configured by setting locality_weighted_lb_config in the cluster configuration and providing weights in LocalityLbEndpoints via load_balancing_weight.

This feature is not compatible with load balancer subsetting, since it is not straightforward to reconcile locality level weighting with sensible weights for individual subsets.