Rate-limiting algorithms

Fixed window

固定窗口算法又叫计数法，在固定时间窗口里记录请求次数，当计数达到阈值时，拒绝请求。当前时间窗口结束后，重置计数器。

这种算法到优点是简单易实现。缺点是可能存流量尖刺，即请求集中在两个时间窗口交界处。

滑动窗口算法是固定窗口算法的改进版，在固定窗口的基础上又划分若干子窗口，每个字窗口单独计数，每次只往前移动一个子窗口。相比固定窗口，随着子窗口数量增加，其限流计算更加准确。

不过这种方式也只是缓解了固定窗口算法的缺点，并不能彻底解决。

滑动日志算法会记录每个请求的时间戳，然后计算最近一个时间窗口内的请求数量，如果达到上限，则请求拒绝。

这种算法的优点是限流精确，缺点也很明显，因为要在内存中记录每一条请求的时间戳，会占用较多内存。

漏桶算法会维护一个单端队列，从请求在尾部排队，以固定速率从队列头部取出请求进行处理，队列长度达到上限时拒绝服务。因这种模型就像一个水桶，底部以固定流速漏水，所以称为漏桶算法。

这种算法能够对突发流量进行整形并以恒定速率进行处理，保证系统的稳定运行。缺点是，它不能很好处理流量波动的场景，当流量短时间少量增加时无法提供更快的处理速度。

令牌桶和漏桶算法虽然都有桶，但是处理的角度确不太一样，漏桶桶里装的是请求，而令牌桶内装的是server的处理能力。当请求到来时，只有桶内有足够令牌时，才会消耗令牌并处理请求。桶内令牌以固定速率进行补充，直到达到上限。

通过调整令牌生成速率和桶大小，可以灵活应对流量波动。缺点是实现相对复杂。

前面的算法都是在本地维护一个 limiter，不能跨 server instance 进行流量控制。当需要支持分布式流量控制时，可以使用 Redis 保存 limiter。