AIMD算法在工程上的应用

AIMD (additive-increase/multiplicative-decrease)是用于TCP拥塞控制的算法。AIMD思想虽然简单，但我认为它非常符合“simple but elegant”的哲学。尤其是在多连接拥塞控制中的公平性分析，还挺巧妙。这里主要探讨AIMD在非TCP场景下的应用，不对其原理进行深度剖析。

AIMD简介

顾名思义，AIMD就是线性增长，指数回退的意思。TCP用此机制来控制拥塞窗口的大小。其中线性增长是在未遇到异常(丢包)情况下进行，直到收敛至异常出现，认为遇到了瓶颈，然后将拥塞窗口降至一半，直到完全收敛。下图是《Computer Networking: A Top-Down Approach》第6版中的图3.54，对拥塞窗口随时间的变化进行展示：

工程应用

试举两例应用，其中第一个是在微服务级的调用频次“拥塞控制”，及时回退避免将瓶颈服务卡死；第二个是借用AIMD机制来定义服务的可用度，留下高可用服务，淘汰不稳定服务。

服务调用回退机制

微服务(microservice)框架下，服务之间的调用通过RPC或RESTful接口进行调用。若被调用服务的处理速度有限，而又不易scale up，则在系统设计上需要考虑防止服务的卡死：该服务本已处理不及，而调用方继续以常规速度调用，则从调用方看起来所有请求都超时，而被调用服务一直在处理队列中的信息，导致未有及时回复，队列越积越长，整个系统卡死且不能恢复正常状态。另一方面，也要考虑系统的吞吐量，最大化被调用服务的效率，从而让系统性能最优。

这种情况其实与TCP拥塞控制是基本一致的需求，直接应用AIMD机制即可：调用方通过返回的状态码对所依赖的服务状态进行被动检测，如遇到超时或异常返回，则触发回退机制，调用速率减半，从而让被依赖服务将队列中积压的请求处理完毕后恢复正常状态。若被依赖服务正常，则常数增长调用速率，直到达到系统的最大吞吐量。

不稳定服务状态检测与维护

假设有一个服务池，需要维护服务状态，即把挂掉的服务挪出服务池，而将稳定服务放在池中的队列头，优先调用。

可以应用AIMD算法定义服务质量Q：

if (success)
{
    Q = Q + 1;
}
else
{
    Q = Q / 2;
}

当服务质量变为0时，则将此服务标记为不可用状态。

下面是10个服务的服务质量示例：

服务名	服务质量Q
service1	445
service2	225
service3	22
service4	32
service5	80
service6	74
service7	16
service8	12
service9	12
service10	1