Locality Based Routing Support

[tanujd11]

Description:
Implement locality based routing support by default in EG. Now that we we can have individual endpoints as backend to EG. Can we support region/zone/subzone based routing based on EndpointSlice information, node labels etc.?

[arkodg]

Hey @tanujd11 from a user perspective can you share what you like to happen on the data plane ( from gateway to multiple backend endpoints with different topology info )

[arkodg]

I understand this is very useful for optimizing East West traffic within a cluster, is that also the case for north South ?

[tanujd11]

I think for an Envoy gateway running in us-east-1/us-east-1a should prefer the same zone backend to prevent cross zonal traffic. I think this behaviour could be made as default as cross zone communication is obviously costly. WDYT?

[arkodg]

thanks, here's something more to think about

• opt in or default - K8s service has a opt in annotation https://kubernetes.io/docs/concepts/services-networking/topology-aware-routing/#enabling-topology-aware-routing service.kubernetes.io/topology-mode
• Is this a soft preference (weighted) or hard preference (priority)

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[arkodg]

there's a new field in the Service spec (trafficDistribution.preferClose) https://kubernetes.io/docs/concepts/services-networking/service/#traffic-distribution that we could consider using to automate priority amongst endpoints within a Service

[aoledk]

there's a new field in the Service spec (trafficDistribution.preferClose) https://kubernetes.io/docs/concepts/services-networking/service/#traffic-distribution that we could consider using to automate priority amongst endpoints within a Service

Could be an option when this new field is stable and corresponding K8s version is adopted by massive companies.

Before that, IMO it's better to do load balancing accross endpoints in the cluster via Envoy's capability.

Currently EG has implemented locality weighted load balancing ¹, one BackendRef is translated to one LocalityLbEndpoints.

locality := &endpointv3.LocalityLbEndpoints{
	Locality: &corev3.Locality{
		Region: fmt.Sprintf("%s/backend/%d", clusterName, i),
  	},
	LbEndpoints: endpoints,
	Priority:    0,
}
  
// Set locality weight
var weight uint32
if ds.Weight != nil {
	weight = *ds.Weight
} else {
	weight = 1
}

Actually endpoints inside a LocalityLbEndpoints may be running in different zone, cross zone cost can't be saved in this way.

---

Through Envoy's capability, priority levels ² or zone aware routing ^{3 4} can archive the goal to save cross zone cost.

priority levels

1. Backend endpoint should be set with correct zone, it can be retrieved from EndpointSlice, inherited from Node topology.kubernetes.io/zone label.
2. Envoy's command options should be set with --service-zone option, means which zone Envoy Pod is running in.
3. EG rearranges EDS resources for each Envoy, if Envoy and Backend endpoint are in same zone, priority as 0, else 1.

zone aware routing

This approach is mutually exclusive with locality weighted load balancing, 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.

1. Backend endpoint should be set with correct zone, it can be retrieved from EndpointSlice, inherited from Node topology.kubernetes.io/zone label.
2. Envoy's command options should be set with --service-zone option, value meaning which zone Envoy Pod is running in.
3. Envoy's bootstrap config should be set with cluster_manager. local_cluster_name, means which fleet Envoy Pod belongs to, it will be irKey in implementation.
4. Add cluster corresponding to cluster_manager. local_cluster_name to CDS resources.
5. Design a mechanism to discover Envoy Pods belongs to cluster_manager. local_cluster_name as endpoints and add them to EDS resources.
6. Both Envoy and Backend cluster are not in panic mode ⁵.

personal preference

Since step 1 and 2 is required by both, priority levels can work with implemented locality weighed load balancing, but zone aware routing can't. Apparently priority levels are easier to implement. But it requires EDS resources should be arranged in xds/cache module for individual Envoy. No matter EG do this, or create new xDS Hook API, like PostEndpointModify(ClusterLoadAssignment, Node) which allow extension server to do this.

Footnotes

1. https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/locality_weight ↩

2. https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/priority ↩

3. https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/zone_aware ↩

4. https://www.envoyproxy.io/docs/envoy/latest/faq/configuration/zone_aware_routing ↩

5. https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/panic_threshold#arch-overview-load-balancing-panic-threshold ↩

[arkodg]

thanks for outlining the steps @aoledk ! we currently have #3055 open to get explicit priority per backendRef and program that into the xds cluster resource.

In the future, we can use this issue to make sure we track the auto priority work, the field in k8s preferClose could be the knob for users to say they want to opt in to this feature

[guydc]

Hi @aoledk, regarding:

priority levels
[...]
EG rearranges EDS resources for each Envoy, if Envoy and Backend endpoint are in same zone, priority as 0, else 1.

Is this option viable? Can our XDS server produce different EDS for different envoy pods that are part of the same Envoy deployment?

[modatwork]

I think it's possible. xDS server can read the locality info of envoy node.

The cache will be keyed based on a pre-defined hash function whose keys are based on the Node information.

// Identifies a specific Envoy instance. Remote server may have per Envoy configuration.
message Node {
  // An opaque node identifier for the Envoy node. This must be set.
  string id = 1;
  // The cluster that the Envoy node belongs to. This must be set.
  string cluster = 2;
  google.protobuf.Struct metadata = 3;
  Locality locality = 4;
  // This is motivated by informing a management server during canary which
  // version of Envoy is being tested in a heterogeneous fleet.
  string build_version = 5;
}

[guydc]

Thanks for pointing that out @modatwork. My other concerns wrt. to this approach are:

• Conflict with general-purpose use cases of priorities (e.g. to support things like active/passive failover)
• Possible impact on memory consumption if we have to maintain a copy of the cache for each locality. Not sure if that's already the situation today. @arkodg - do you know?

In general:

• I'm +1 to supporting zone-aware routing in EG.
• I would avoid using priorities for this feature in EG's built-in feature set.
• The the extension-server approach to EP priority manipulation could work. If we don't have a per-locality cache, maybe that should be an opt-in feature.

Is there a reason to prefer the Priority-based approach? I'm not sure that it's significantly simpler than enabling zone-aware routing.

[arkodg]

is @modatwork the same person as @aoledk :) ?

Possible impact on memory consumption if we have to maintain a copy of the cache for each locality. Not sure if that's already the situation today. @arkodg - do you know?

@guydc we have are dumuxing on gateway/IR, with locality it would add another dimension lookup and would increase memory by num localities * total (xds per gateway * gateway resources)

[aoledk]

@arkodg I work together with @modatwork

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[arkodg]

hey @aoledk , adding this issue to the v1.2 milestone, is this something you can help with ?

1. Lets configure zone aware routing in envoy by default https://www.envoyproxy.io/docs/envoy/latest/faq/configuration/zone_aware_routing
2. If a Service has TrafficDistribution set to PreferClose https://kubernetes.io/docs/concepts/services-networking/service/#traffic-distribution, lets rearrange the EDS endpoint (so Service opts in)

[aoledk]

hey @aoledk , adding this issue to the v1.2 milestone, is this something you can help with ?

1. Lets configure zone aware routing in envoy by default https://www.envoyproxy.io/docs/envoy/latest/faq/configuration/zone_aware_routing
2. If a Service has TrafficDistribution set to PreferClose https://kubernetes.io/docs/concepts/services-networking/service/#traffic-distribution, lets rearrange the EDS endpoint (so Service opts in)

@arkodg I can help.

[arkodg]

awesome thanks @aoledk !

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[arkodg]

hey @aoledk still planning on working on this one for v1.2 ?

[aoledk]

hey @aoledk still planning on working on this one for v1.2 ?

Hi @arkodg nowadays I'm working on bring in EG v1.1., next month I will continue on this feature, but not sure whether it can be merged into v1.2 (Due by October 30, 2024), maybe v1.3.

[arkodg]

thanks for the update @aoledk, let us know if you hit any issues while running EG v1.1
moving this issue into backlog

[aoledk]

@arkodg LGTM.

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days.

[flyik]

Hi @aoledk! Are you still looking into implementing it yourself? If not, I’m interested in this feature and can work on bringing it to life.

[aoledk]

@flyik recently I'm busy with bringing in EG, you can go ahead.

[aoledk]

@flyik I've unassigned myself, you can assign to yourself.