Repository: grpc/grpc-go

Issue:
SubChannels stuck in Idle when using Weighted Round Robin
### What version of gRPC are you using?

- Discovered on 1.70.0
- Reproduced on master, 1.71.0, 1.70.0.
- There seems to also be a similar problem in 1.69.0, but it is looks slightly different (it looks more like an infinite loop or something like that).
- The example works fine when executed against 1.68.4.

### What version of Go are you using (`go version`)?

go version go1.24.0 darwin/arm64

### What operating system (Linux, Windows, …) and version?

Discovered on Linux, reproduced locally on MacOS.

### What did you do?

We use the `weighted_round_robin` balancer with `MaxConnectionAge` set to 5 minutes. Most services worked fine. However, one service with a large number of instances (500+) experienced a surge of errors waiting for subchannels to transition to ready:


### What did you expect to see?

RPC succeed.

### What did you see instead?

```
rpc error: code = DeadlineExceeded desc = received context error while waiting for new LB policy update: context deadline exceeded
```

### Additional context

Turning on the logs, we found that after a period of the max connection age causing servers to close connections, subchannels would transition to Idle and never go back to Connecting. Since weighted round robin is not a lazy balancer, transitions to `Idle` happening due to the server closing the connection should immediately trigger a transition to `Connecting`. The logs for a single subchannel look like this:

```
Date,Message
"2025-03-13T15:41:15.536Z","[core] [Channel #32 SubChannel #208]Subchannel created"
"2025-03-13T15:41:15.536Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to CONNECTING"
"2025-03-13T15:41:15.536Z","[core] [Channel #32 SubChannel #208]Subchannel picks a new address ""10.51.65.5:2787"" to connect"
"2025-03-13T15:41:15.552Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to READY"
"2025-03-13T15:45:45.751Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to IDLE"
"2025-03-13T15:49:23.496Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to CONNECTING"
"2025-03-13T15:49:23.496Z","[core] [Channel #32 SubChannel #208]Subchannel picks a new address ""10.51.65.5:2787"" to connect"
"2025-03-13T15:49:23.502Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to READY"
"2025-03-13T15:54:03.737Z","[core] [Channel #32 SubChannel #208]Subchannel Connectivity change to IDLE"
```

No subsequent update happen for this subchannel. Since all subchannel follow the same patterns, RPCs start failing.

Note that:
- This seems to only happen on very large services (>500 instances)
- This only happens with weighted round robin, which delegates to `endpointsharding` and uses the new load balancer infrastructure. `round_robin` is not affected.

### Local reproduction steps

We were able to reproduce the problem in the repo by modifying the load balancing examples. The commit to reproduce is here: https://github.com/atollena/grpc-go/commit/ec3b1c7a23da495d56429bbd50f0cd4fa7235b23
The changes included in the commit:
- set max connection age to 15 seconds
- add 2000 servers instead of 2 (1000 servers didn't seem to reproduce reliably)
- set load balancing policy to weighted_round_robin.
- make RPCs in an infinite loop and errors non-fatal, to see more than 1
- remove the example using pick_first.

When running the server and client examples, you'll end up with logs like this (debug logs enabled):
```
2025/03/14 17:09:08 INFO: [core] blockingPicker: the picked transport is not ready, loop back to repick
2025/03/14 17:09:09 INFO: [core] blockingPicker: the picked transport is not ready, loop back to repick
2025/03/14 17:09:09 INFO: [core] blockingPicker: the picked transport is not ready, loop back to repick
2025/03/14 17:09:09 could not greet: rpc error: code = DeadlineExceeded desc = context deadline exceeded while waiting for connections to become ready
```

Discussion:
@atollena: cc @arjan-bal @s-matyukevich @s-matyukevich: I tried to debug this issue today and the only thing that I found so far is that it looks like balancer_wrapper serializer is the bottleneck. [acBalancerWrapper.updateState](https://github.com/grpc/grpc-go/blob/775150f68c1759ad4b1230d09fe41efb6f3c76ad/balancer_wrapper.go#L309) is responsible for triggering reconnection  by exiting idle mode, but by the time this method is called serializer is already filled with callbacks registred by the [RegisterHealthListener](https://github.com/grpc/grpc-go/blob/775150f68c1759ad4b1230d09fe41efb6f3c76ad/balancer_wrapper.go#L472) method, and for some reason it takes a really long time to process all those callbacks. This is reproducible with both short and large maxConnectionAge. @arjan-bal: It looks like the callback_serializer in balancer_wrapper is getting blocked. So the subchannel notification for IDLE is not getting delivered to the LB policy.

There is a O(n^2) loop in wrr here every time an endpoint reports ready: https://github.com/grpc/grpc-go/blob/775150f68c1759ad4b1230d09fe41efb6f3c76ad/balancer/weightedroundrobin/balancer.go#L260-L264

When all n children become ready the loop is run n times, so total time spent is O(n^3). For n = 2*10^3, this will probably take minutes to complete.@atollena: I can confirm this theory by profiles, as `EndpointMap.find` shows up at the top of CPU profiles.

Do you have a sense of what the right fix is? It's a bit confusing that something called "map" has O(n) lookup. There is good context in the PR that introduces EndpointMap: https://github.com/grpc/grpc-go/pull/6679.@arjan-bal: The simplest fix I can think of is to make the EndpointMap operation complexities match a Go map instead of a slice.

I've thought of a way to make lookups O(1). The key of an endpoint map is a slice of strings. We can create a canonical representation of a slice of strings by sorting it and removing duplicates. We can then encode the string slice (using json or using base64) to convert []string->string that can be used as a map key. This should allow using a Go map to store and query endpoints instead of a slice.

Solution patch:
diff --git a/resolver/map.go b/resolver/map.go
index ada5b9bb..975b4997 100644
--- a/resolver/map.go
+++ b/resolver/map.go
@@ -18,6 +18,12 @@
 
 package resolver
 
+import (
+	"encoding/base64"
+	"sort"
+	"strings"
+)
+
 type addressMapEntry struct {
 	addr  Address
 	value any
@@ -137,66 +143,61 @@ func (a *AddressMap) Values() []any {
 	return ret
 }
 
-type endpointNode struct {
-	addrs map[string]struct{}
-}
-
-// Equal returns whether the unordered set of addrs are the same between the
-// endpoint nodes.
-func (en *endpointNode) Equal(en2 *endpointNode) bool {
-	if len(en.addrs) != len(en2.addrs) {
-		return false
-	}
-	for addr := range en.addrs {
-		if _, ok := en2.addrs[addr]; !ok {
-			return false
-		}
-	}
-	return true
-}
-
-func toEndpointNode(endpoint Endpoint) endpointNode {
-	en := make(map[string]struct{})
-	for _, addr := range endpoint.Addresses {
-		en[addr.Addr] = struct{}{}
-	}
-	return endpointNode{
-		addrs: en,
-	}
-}
+type endpointMapKey string
 
 // EndpointMap is a map of endpoints to arbitrary values keyed on only the
 // unordered set of address strings within an endpoint. This map is not thread
 // safe, thus it is unsafe to access concurrently. Must be created via
 // NewEndpointMap; do not construct directly.
 type EndpointMap struct {
-	endpoints map[*endpointNode]any
+	endpoints map[endpointMapKey]endpointData
+}
+
+type endpointData struct {
+	// decodedKey stores the original key to avoid decoding when iterating on
+	// EndpointMap keys.
+	decodedKey Endpoint
+	value      any
 }
 
 // NewEndpointMap creates a new EndpointMap.
 func NewEndpointMap() *EndpointMap {
 	return &EndpointMap{
-		endpoints: make(map[*endpointNode]any),
+		endpoints: make(map[endpointMapKey]endpointData),
+	}
+}
+
+// encodeEndpoint returns a string that uniquely identifies the unordered set of
+// addresses within an endpoint.
+func encodeEndpoint(e Endpoint) endpointMapKey {
+	addrs := make([]string, 0, len(e.Addresses))
+	// base64 encoding the address strings restricts the characters present
+	// within the strings. This allows us to use a delimiter without the need of
+	// escape characters.
+	for _, addr := range e.Addresses {
+		addrs = append(addrs, base64.StdEncoding.EncodeToString([]byte(addr.Addr)))
 	}
+	sort.Strings(addrs)
+	// " " should not appear in base64 encoded strings.
+	return endpointMapKey(strings.Join(addrs, " "))
 }
 
 // Get returns the value for the address in the map, if present.
 func (em *EndpointMap) Get(e Endpoint) (value any, ok bool) {
-	en := toEndpointNode(e)
-	if endpoint := em.find(en); endpoint != nil {
-		return em.endpoints[endpoint], true
+	val, found := em.endpoints[encodeEndpoint(e)]
+	if found {
+		return val.value, true
 	}
 	return nil, false
 }
 
 // Set updates or adds the value to the address in the map.
 func (em *EndpointMap) Set(e Endpoint, value any) {
-	en := toEndpointNode(e)
-	if endpoint := em.find(en); endpoint != nil {
-		em.endpoints[endpoint] = value
-		return
+	en := encodeEndpoint(e)
+	em.endpoints[en] = endpointData{
+		decodedKey: Endpoint{Addresses: e.Addresses},
+		value:      value,
 	}
-	em.endpoints[&en] = value
 }
 
 // Len returns the number of entries in the map.
@@ -211,12 +212,8 @@ func (em *EndpointMap) Len() int {
 // used for EndpointMap accesses.
 func (em *EndpointMap) Keys() []Endpoint {
 	ret := make([]Endpoint, 0, len(em.endpoints))
-	for en := range em.endpoints {
-		var endpoint Endpoint
-		for addr := range en.addrs {
-			endpoint.Addresses = append(endpoint.Addresses, Address{Addr: addr})
-		}
-		ret = append(ret, endpoint)
+	for _, en := range em.endpoints {
+		ret = append(ret, en.decodedKey)
 	}
 	return ret
 }
@@ -225,27 +222,13 @@ func (em *EndpointMap) Keys() []Endpoint {
 func (em *EndpointMap) Values() []any {
 	ret := make([]any, 0, len(em.endpoints))
 	for _, val := range em.endpoints {
-		ret = append(ret, val)
+		ret = append(ret, val.value)
 	}
 	return ret
 }
 
-// find returns a pointer to the endpoint node in em if the endpoint node is
-// already present. If not found, nil is returned. The comparisons are done on
-// the unordered set of addresses within an endpoint.
-func (em EndpointMap) find(e endpointNode) *endpointNode {
-	for endpoint := range em.endpoints {
-		if e.Equal(endpoint) {
-			return endpoint
-		}
-	}
-	return nil
-}
-
 // Delete removes the specified endpoint from the map.
 func (em *EndpointMap) Delete(e Endpoint) {
-	en := toEndpointNode(e)
-	if entry := em.find(en); entry != nil {
-		delete(em.endpoints, entry)
-	}
+	en := encodeEndpoint(e)
+	delete(em.endpoints, en)
 }



Test patch:
diff --git a/resolver/map_test.go b/resolver/map_test.go
index c14f3eb3..ab4daceb 100644
--- a/resolver/map_test.go
+++ b/resolver/map_test.go
@@ -287,3 +287,25 @@ func (s) TestEndpointMap_Values(t *testing.T) {
 		t.Fatalf("em.Values() returned unexpected elements (-want, +got):\n%v", diff)
 	}
 }
+
+// BenchmarkEndpointMap benchmarks map operations that are expected to run
+// faster than O(n). This test doesn't run O(n) operations including listing
+// keys and values.
+func BenchmarkEndpointMap(b *testing.B) {
+	em := NewEndpointMap()
+	for i := range b.N {
+		em.Set(Endpoint{
+			Addresses: []Address{{Addr: fmt.Sprintf("%d.%d.%d.%d", i, i, i, i)}},
+		}, i)
+	}
+	for i := range b.N {
+		em.Get(Endpoint{
+			Addresses: []Address{{Addr: fmt.Sprintf("%d.%d.%d.%d", i, i, i, i)}},
+		})
+	}
+	for i := range b.N {
+		em.Delete(Endpoint{
+			Addresses: []Address{{Addr: fmt.Sprintf("%d.%d.%d.%d", i, i, i, i)}},
+		})
+	}
+}