On Sharding

Adding hysteresis definitely helps to stabilize issues like this. Using rolling windows or exponentially decayed weighting has worked out well in my experience. In general, it seems like load based routing can be quite perfidious if you get the heuristic for “load” wrong.

I worked on a system that used total connections as our heuristic, measured by the load balancer. The problem we experienced was that some failure scenarios could cause requests to fail quickly compared to normal traffic. In effect what would happen is that a host would go into a bad state, start failing requests with a lower latency than normal traffic causing the load balancer to route an increasing amount of traffic to the bad host. This happened because the load balancer was only capable of measuring connections and didn’t discriminate between good/bad responses.

We ended up injecting fake latency into bad responses at the application layer which worked to prevent this sort of “black hole” effect.

Sorta related:

I managed a team that built a 5x 1000 node distributed setup 10+ years ago.

We ended up going with

a) short DNS TTL + a custom DNS server that sent people to the closest cluster (with some intra-communication to avoid sending people to broken clusters)

b) in each cluster; three layers: 1) Linux keepalived load balancing, 2) Our custom HTTP/TLS-level loadbalancers (~20 nodes per DC), 3) our application (~1000 nodes per DC)

A typical node had 24 (4x6) CPU cores when we started and 48 (4x12) towards the end.

These were not GC/AWS nodes, we were buying hardware directly from IBM/HP/Dell/AMD/Intel/SuperMicro and flying our own people out to mount them in DCs that we hired. Intel gave us some insane rebates when they were're recovering from the AMD dominance.

Load-balancing policy: we just randomized targets, but kept sticky sessions. Nodes were stateless, except for shared app properties - we built a separate globally/dc-aware distributed key-value store - that was a whole new thing 12 years ago we built based on the vague concept of AWS Dynamo. App nodes reported for duty to the load balancers when they were healthy.

We had a static country-to-preferred-DC mapping. That worked fine at this scale.

This setup worked fine for a decade and 250M+ MAUs. We had excellent availability.

At some point like 10 years ago a kinda well known US-based board member really, really wanted to us to move to AWS. So we did the cost calculations and realized it would cost like 8X more to host the service on AWS. That shut him up.

Different times. It's so much easier now with AWS/GC to build large-scale services. But also so much more expensive - still! I wonder how long that can last until the concept of dealing with computation, network and storage really becomes a commodity.

Per Brendan Gregg's Gesamptkunstwerk, BPF Performance Tools, I feel like you should be able to measure instructions per cycle at the service level. Even in the cloud if exposed by Xen. And even at the resource utilization level for each container.

http://www.brendangregg.com/bpf-performance-tools-book.html

Of course, you can always just use cloudflare ;)

Some more resources re Shuffle Sharing: https://news.ycombinator.com/item?id=19291163

Also see, this nice little blog post: https://maisonbisson.com/post/hash-rings-sharding-request-re...

This sounds a lot like the control-theory problem of balancing the proportional, integral, and derivative coefficients of a PID controller [1]?

I'm curious how you reached this condition as a requirement:

> The moral of the story here is make sure you pick a metric that reacts to the change in request rate as quickly as your request rate changes!

It makes sense intuitively, but I'm having trouble proving to myself that this is necessary+sufficient.

[1]: https://en.wikipedia.org/wiki/PID_controller