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示意

工程应用

试举两例应用,其中第一个是在微服务级的调用频次“拥塞控制”,及时回退避免将瓶颈服务卡死;第二个是借用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