uber / cadence / 018e43c7-e893-4c40-a63b-442d9dceb207

72%

Build Type

push

buildkite

Committed by web-flow

Commit Message

Global ratelimiter, part 1: core algorithm for computing weights (#5689)

A high level overview is covered in `common/quotas/global/doc.go`, and this specific piece is further covered in the `./algorithm/requestweighted.go` file.

At a very high level though, this is an isolated piece of a "deployment-wide load-balance-aware ratelimiter", intended to solve problems with our internal clusters with our current high-level frontend ratelimiters around client-triggered domain actions (start workflow, poll, etc).

This is the "logical core" of the whole system, with as few dependencies and concerns as I can manage.  All frontend hosts that will be imposing limits eventually send the update arguments to an aggregating host, and the aggregating host largely just delegates to a single instance of this algorithm.  Essentially all the aggregating host needs to do to respond is multiply the weight by each configured ratelimit (from dynamic config).

I've left the concurrency fairly coarse, both for simplicity and for computational speed. I don't believe this will be a bottleneck in even our largest cluster, but even if it is it should be fairly trivial to split each batch's ratelimit keys into N different sharded instances, which can be completely independent.

# The problem

All of our current ratelimiters currently fall into two conceptual buckets:
1. they enforce N rps on that in-memory instance
2. they enforce N rps on that in-memory instance _divided by the number of hosts in a ring_

While these are very straightforward and have served us well, they're proving inadequate in our internal clusters due to imbalanced load on our frontend instances.  Sometimes _wildly_ imbalanced, e.g. 10% of hosts receiving _all_ traffic for a domain.

What this leads to is a lower _effective_ ratelimit than is intended, e.g.:
- 100 rps is allowed
- 10 hosts exist (so each host allows 10 rps)
- 1 host receives 100 rps, the others receive 0
- the requests are... (continued)

Run Details

191 of 191 new or added lines in 1 file covered. (100.0%)

102 existing lines in 20 files now uncovered.

94707 of 145968 relevant lines covered (64.88%)

2377.72 hits per line