resolver: Add an endpoint map type #6679

zasweq · 2023-10-03T17:23:08Z

This PR adds an endpoint map type for use by Petiole policies for pick first children and also balancers like Outlier Detection which store state unique to individual endpoints. The endpoints are unique based off the unordered set of address string counts within an endpoint.

RELEASE NOTES:

resolver: Add an endpoint map type

dfawley · 2023-10-05T16:11:41Z

resolver/map.go

+// Equal returns whether the unordered set of addrs counts are the same between
+// the endpoint nodes.


Why use the counts? I don't think an endpoint should include the same address multiple times, and if it does, it seems like we'd just ignore the duplicates.

I use the counts because it feels like a defensive way with no cost incured. I.e. I either do a presence check with a struct{} or bool or I have the value be an int. I know it's not an intended use case of an endpoint to have the same address (by string) multiple times but I added this since it seems to be similar to add it vs. presence.

This is more about how we want it to behave vs. what's an easy feature to add in.

In general I think we want to consider these endpoints as equivalent, so we should be using a set of addresses instead of a set with counts.

Ping. Let's make this a set, which is how the docstring below indicates it behaves as well.

This is still technically a set, right? I don't see any downside to doing it this way, and I think it is more technically correct to take into account address counts (still unordered). Technically, what do you see as the pro of AABC == ABC vs AABC != ABC? I feel like it makes more sense that they're not equivalent (and this case will never happen in practice anyway). It allows the resolver to encode more information in the endpoint (250 ms delay fail address a, then try address a again)...hmmm. I don't think happy eyeballs makes sense wrt doing aa, but right now unless we use keys() to pass down to child the duplicated addresses in an endpoint will be conveyed to the pick first child. So I think whether we account for address counts here is orthogonal to whether we want to pass down AABC to pick first child and have it do happy eyeballs algorithm on AA (relates to that discussion we had monday about pick first never reporting TF).

I put this in the dualstack design chat. Will wait for more discussion before choosing to implement this suggestion or not.

Mark said to strip counts, so will implement this suggestion.

dfawley · 2023-10-05T16:13:41Z

resolver/map.go

+// unordered set of addresses string within an endpoint. The reason this uses a
+// slice instead of a map is because slices or maps cannot be used as map keys.


External documentation should not include implementation details or rational for implementation details unless it's important to the user of the type.

Ah, ok noted. Moved the comment to the field (which is unexported and users of this package won't see it).

Also added a top level comment to external type about it not being thread safe and cannot access multiple times concurrently.

resolver/map.go

dfawley · 2023-10-05T16:23:38Z

resolver/map.go

+// NewEndpointMap returns a new EndpointMap.
+func NewEndpointMap() *EndpointMap {
+	return &EndpointMap{}
+}


Generally if the zero value of the struct is safe to use, we'd just avoid having a constructor and say the zero value is safe to use as an empty map. E.g. https://pkg.go.dev/bytes@go1.21.1#Buffer

The exception is if you think it might need an initialization later, especially if it's an API that we can't ever change.

Yeah since you can append and operate on nil slices the zero value here should be safe to use. Deleted this constructor and use the zero value in tests. However if I go down the map way you mentioned in another comment I'll need to construct that map, since nil doesn't work for map operations (would panic). If I go down that route I'll keep it.

As per comment below, chose not to go map route so deleted this constructor. If we do need to change this, it's internal and we won't break users :).

This is not internal. This is in the grpc/resolver package, which is experimental and intended to be accessed by users, but subject to change. But breaking changes will still break users.

Ah, ok sounds good.

dfawley · 2023-10-05T16:28:12Z

resolver/map.go

+		if count, ok := en[addr.Addr]; ok {
+			en[addr.Addr] = count + 1
+		}
+		en[addr.Addr] = 1


en[addr.Addr]++

Interesting, switched.

dfawley · 2023-10-05T16:35:02Z

resolver/map.go

+	en := toEndpointNode(e)
+	entry := em.endpoints.find(en)
+	if entry == -1 {
+		return
+	}
+	if len(em.endpoints) == 1 {
+		em.endpoints = nil
+	}
+	copy(em.endpoints[entry:], em.endpoints[entry+1:])
+	em.endpoints = em.endpoints[:len(em.endpoints)-1]


Another option would be to make endpoints a map[*endpointNode]struct{}. find would return the *endpointNode if the endpoint can be found. Delete can be a simple delete(endpoints, entry).

The issue I see with using a map of unordered addresses in a map itself is it's not allowed (similar to how you exclude attributes in your address map, since map[key] underlying using something similar to cmp.Equal, which panics on a map key, as you mentioned offline). Thus, I made it a list, with o(n) operations not on the RPC path, so I can do comparisons on each node. I don't think this would work with a map, unless you can overwrite the _, ok := map[key] operation, which I have not have found a way to do.

Maybe you weren't understanding my suggestion. Pointers are valid for map keys, and are compared using pointer equality:

https://go.dev/play/p/VWhAQUEueKR

We wouldn't do lookups using the key, though, even though a map was used. But this simplifies deletions to: 1. find the entry to be deleted by scanning all the entries; 2. delete(endpoints, entryPtr)

Ah, I see. Switched to that.

codecov · 2023-10-06T20:17:11Z

Codecov Report

❗ No coverage uploaded for pull request base (master@9e1fc3e). Click here to learn what that means.
The diff coverage is n/a.

Additional details and impacted files

dfawley · 2023-10-11T16:13:36Z

resolver/map.go

+// unordered set of address strings within an endpoint. This map is not thread
+// safe, cannot access multiple times concurrently. The zero value for an


"This map is not thread safe, cannot access multiple times concurrently."

Please fix the grammar.

Switched to "This map is not thread safe, thus it is unsafe to access concurrently".

dfawley · 2023-10-11T16:13:47Z

resolver/map.go

+// safe, cannot access multiple times concurrently. The zero value for an
+// EndpointMap is an empty EndpointMap ready to use.


The zero value is no longer safe to use, so change comment to say to use NewEndpointMap to create.

Ah whoops yeah forgot to change this. Switched comment to what you said for address map switched to endpoint map: "Must be created via NewEndpointMap; do not construct directly."

dfawley · 2023-10-11T16:14:57Z

resolver/map.go

+// Equal returns whether the unordered set of addrs counts are the same between
+// the endpoint nodes.


Ping. Let's make this a set, which is how the docstring below indicates it behaves as well.

dfawley · 2023-10-11T16:18:31Z

resolver/map.go

+// addresses present in the endpoint keys, in which uniqueness is determined by
+// the unordered set of addresses. Thus, endpoint information returned is not
+// the full endpoint data but can be used for EndpointMap accesses.
+func (em *EndpointMap) Keys() []Endpoint { // TODO: Persist the whole endpoint data to return in nodes? No use case now, but one could come up in future.


Are you sure we don't already need it? You can't create/update a child policy without the full endpoint data.

Yeah. This usage of Keys() for resolver map is simply a helper to index back into the map:

grpc-go/examples/features/customloadbalancer/client/customroundrobin/customroundrobin.go

Line 139 in b0e5540

for _, e := range crr.pfs.Keys() {

(this is how AddressMap.Keys() is used as well, to build a set and use to immediately access map. So thus, this comment is there because we do not persist any attributes to return in this function, and simply build out a new endpoint with the unordered set of addresses to return. Also, the number of addresses will be lost here if I implement your count suggestion above.

https://github.com/grpc/grpc-go/blob/master/balancer/base/balancer.go#L124

Deleted this TODO and added information to top level docstring.

resolver/map.go

dfawley · 2023-10-11T16:21:51Z

resolver/map.go

+// find returns the pointer to endpoint node in the EndpointMap endpoints map if
+// the endpoint node is already present. If not found, nil is returned. The


find returns a pointer to the endpoint node?

Sorry, I don't get what is wrong with this statement.

The wrong part is "to endpoint node". You forgot article. Also we usually talk about pointers as indefinite ("a pointer to") vs. definite ("the pointer to") since there can be more than one pointer to a thing (non Highlander), so my suggestion updated that as well.

While you're here, "in the EndpointMap endpoints map" stutters; you really only need one of those. Or "in em" would be even shorter and more precise.

dfawley · 2023-10-11T16:22:42Z

resolver/map.go

+	entry := em.find(en)
+	if entry != nil {


Merge lines and reduce variable scope: if entry := em.find(en); entry != nil {

Alright sounds good. Done.

Add an endpoint map type

004d1b8

zasweq requested a review from dfawley October 3, 2023 17:23

zasweq assigned dfawley Oct 3, 2023

zasweq added the Type: Feature New features or improvements in behavior label Oct 3, 2023

zasweq added this to the 1.59 Release milestone Oct 3, 2023

dfawley reviewed Oct 5, 2023

View reviewed changes

dfawley assigned zasweq and unassigned dfawley Oct 5, 2023

zasweq mentioned this pull request Oct 5, 2023

examples: Add custom load balancer example #6691

Merged

ginayeh modified the milestones: 1.59 Release, 1.60 Release Oct 5, 2023

Responded to Doug's comments

7fe96a0

zasweq assigned dfawley and unassigned zasweq Oct 9, 2023

dfawley assigned zasweq and unassigned dfawley Oct 10, 2023

Responded to Doug's comment

813cb4e

zasweq assigned dfawley and unassigned zasweq Oct 11, 2023

dfawley reviewed Oct 11, 2023

View reviewed changes

zasweq added 2 commits October 11, 2023 13:30

Respond to Doug's comments partially

ef7069d

Dropped address counts for endpoint equality

b6574f7

dfawley assigned zasweq and unassigned dfawley Oct 16, 2023

Responded to Doug's comment about comment

0aad3f2

zasweq assigned dfawley and unassigned zasweq Oct 16, 2023

dfawley approved these changes Oct 16, 2023

View reviewed changes

dfawley assigned zasweq Oct 16, 2023

dfawley removed their assignment Oct 16, 2023

zasweq merged commit e14d583 into grpc:master Oct 16, 2023
13 checks passed

arvindbr8 pushed a commit to arvindbr8/grpc-go that referenced this pull request Nov 7, 2023

resolver: Add an endpoint map type (grpc#6679)

2a6352e

github-actions bot locked as resolved and limited conversation to collaborators Apr 14, 2024

		// Equal returns whether the unordered set of addrs counts are the same between
		// the endpoint nodes.

		// unordered set of addresses string within an endpoint. The reason this uses a
		// slice instead of a map is because slices or maps cannot be used as map keys.

		// unordered set of address strings within an endpoint. This map is not thread
		// safe, cannot access multiple times concurrently. The zero value for an

		// safe, cannot access multiple times concurrently. The zero value for an
		// EndpointMap is an empty EndpointMap ready to use.

		// find returns the pointer to endpoint node in the EndpointMap endpoints map if
		// the endpoint node is already present. If not found, nil is returned. The

resolver: Add an endpoint map type #6679

resolver: Add an endpoint map type #6679

Conversation

zasweq commented Oct 3, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codecov bot commented Oct 6, 2023 • edited Loading

Codecov Report

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codecov bot commented Oct 6, 2023 •

edited

Loading