Implement AIMD algorithm calculator
Following the blueprint, we need to implement Additive increase/multiplicative decrease algorithm. This method involves gradually increasing the limit during normal process functioning but quickly reducing it when an issue occurs.
During initialization, we configure the following parameters:
-
initialLimit
: Concurrency limit to start with. This value is essentially equal to the current static concurrency limit. -
maxLimit
: Maximum concurrency limit. -
minLimit
: Minimum concurrency limit so that the process is considered as functioning. If it’s equal to 0, it rejects all upcoming requests. -
backoffFactor
: how fast the limit decreases when a backoff event occurs (0 < backoff < 1, default to 0.75)
Each limiter (concurrency limiter/pack-object limiter) may have various configurations. Each config is applied for a particular RPC with a different value.
The resource usage is polled from the environment or fed from an event stream. There might be various resource watchers. Value re-calibration should be in-sync. Letting them run independently leads to chaos.
Hence, each Gitaly server should have only one calculator. A limiter requests the calculator to issue one instance for it at initialization. The calculator keeps a map of issued instances. They are updated in two ways: calculator polling and real-time event.
- The calculator allows the resource watchers to add pollers. It starts a ticker goroutine which accumulates events from the watchers.
- It also exposes one channel letting watchers push events actively.