Adaptive Concurrency Control

The Dispatch infrastructure uses a mechanism called Adaptive Concurrency Control to automatically adapt the throughput of request execution to the capacity and availability of the destinations.

Benefits

Remote systems typically throttle the request throughput. However, due to the linear relationship between throughput, latency, and concurrency, measuring the number of inflight requests allows Dispatch to dynamically adapt to rate limits, system capacity, downtime, or any combination of issues and limits that arise in distributed systems.

Dispatch provides clients with the benefits of Adaptive Concurrency Control to all requests it serves on their behalf, with no need for upfront configuration.

Achieving fairness in multi-tenant systems

Instead of varying the transmission window size, Dispatch uses the number of inflight requests as a measure to continuously adapt the number of requests sent to each destination.

Individual nodes in the underlying Dispatch infrastructure do not share any state. Still, just like TCP, the algorithm always converges towards fairly sharing resources between tenants, preventing unhealthy links from damaging the overall quality of service.

Relationship between concurrency and throughput

Using concurrency as the metric works because distributed systems obey Little's Law, stating that the amount of work in a system is proportional to the average rate of incoming work multiplied by the average time to perform the work:

L=λWL = λW

In our case, L is the number of inflight requests, λ the average request rate, and W is the average request latency.

AIMD Algorithm

Adaptive Concurrency Control is derived from the Congestion Control algorithm in network protocols like TCP.

Dispatch groups requests using a composite key, including the source organization and destination hostname. It starts each group with a default concurrency allocation and then adapts that allocation based on the result of each request:

  • On successful requests, the concurrency allocation is increased

  • On failed requests (e.g., 5xx, timeouts), the concurrency allocation is decreased

This algorithm is known as AIMD, which stands for Additive Increase Multiplicative Decrease. The increase is an addition by a constant factor, and the decrease is a multiplication by a factor smaller than 1.

Last updated

©️ Stealth Rocket, Inc. All rights reserved.