Hi @cgetzen, welcome and thank you for your contribution.

We will try to review your Pull Request as quickly as possible.

In the meantime, please take a look at the contribution guidelines if you have not done so already.

CC @envoyproxy/api-shepherds: Your approval is needed for changes made to api/envoy/.
API shepherd assignee is @markdroth
CC @envoyproxy/api-watchers: FYI only for changes made to api/envoy/.
CC @envoyproxy/dependency-shepherds: Your approval is needed for changes made to (bazel/.*repos.*\.bzl)|(bazel/dependency_imports\.bzl)|(api/bazel/.*\.bzl)|(.*/requirements\.txt)|(.*\.patch).

@cgetzen can we please move this to an issue with a proposed design that we can iterate on before we go to code? From there it might be more efficient to also iterate in a gdoc as part of the issue (up to you where you want to start). A few quick comments:

If having ~10^4 - 10^5 shards in memory is reasonable, I will turn off turn off cache eviction and potentially pre-calculate all shards.

I don't see a huge issue here (though it really depends as always on a memory <-> CPU/locking/complexity), and I would definitely do pre-computation if possible in the MVP, so I would probably have the max shards / hosts per shard be configurable so the user can clearly understand what the memory implications are? Also, if you implement as a thread aware load balancer I think you can do the pre-computation once on the main thread and then share the LB on all the other threads like maglev/ring do.

How will shards be configured? Maybe there is a more performant method?

My preference would be to do away with caching, etc. and do pre-computation, unless we show this is unreasonable. Also, I have general questions on whether the choosing has to be perfect or it could be probabilistically close enough. Imagine for example the following theoretical implementations:

1. If we don't need stable consistent hashing properties, I think everything could be implemented inline on the fly: a) compute shard hash, b) derive shard ID, c) use shard ID as a psuedo-random seed to generate the picks for members, d) use real random to pick the host index inside virtual shard.
2. If we need more consistency, use a giant Maglev table to map hash into shard ID. Then proceed to b) above. This would provide consistency but random LB within a shard. Edit: For shard member consistency I think you probably then want a 2nd Maglev of just the hosts, and then use the shard ID as a seed into a hash function that would pick hosts, dealing with duplicates.
3. Maglev + inner LBs that track state. This would give better LB but use more memory.
4. Some type of caching, on the fly implementation as you listed out above.

All of ^ have trade-offs. cc @tonya11en also who is into this kind of thing. Anyway, I would suggest we move to an issue and writeup a doc to look at this in more detail. Interesting stuff!

FWIW I just looked at the AWS reference code and I think https://github.com/awslabs/route53-infima/blob/master/src/main/java/com/amazonaws/services/route53/infima/SimpleSignatureShuffleSharder.java is basically my (1) above in spirit. But like I said there are a lot of trade-offs here depending on requirements.

Going to close this for now in favor of the issue and design doc.