限流算法

限流，也称流量控制。是指系统在面临高并发，或者大流量请求的情况下，限制新的请求对系统的访问，从而保证系统的稳定性。限流会导致部分用户请求处理延迟或者被拒，从而影响用户体验，因此也属于一种降级。限流的使用场景包括限制上游访问或者下游调用。常见的限流算法有下面几种。

固定窗口限流算法

固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一种最简单的限流算法，其原理是在固定时间窗口(单位时间)内限制请求的数量。该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。具体来说，算法将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。

比如，我们会维护一个计数器，将单位时间段当做一个窗口，计数器记录这个窗口接收请求的次数。

• 当次数少于限流阀值，就允许访问，并且计数器+1
• 当次数大于限流阀值，就拒绝访问。
• 当前的时间窗口过去之后，计数器清零。

举个具体例子，我们将单位时间设置为1分钟，限流阈值设置为60，1分钟内每来一个请求，计数器+1，如果计数器达到了60，1分钟内后续请求全局拒绝，1分钟结束后，计数器清0，开始下一轮循环。 这个算法的优点是简单容易实现，缺点是存在明显的临界值问题。比如，还是继续上面的例子，限流阈值是1分钟60（折算下来qps max不能超过1），0-60s和60-120s分别为一个固定的时间窗口，59-60s秒内的时候突然来了10个请求，60s-61s秒内也来了10个请求，虽然在各自的时间窗口内都没有问题，但实际上，59-61s请求数达到了120，qps达到了60，远远超过系统所能承载的吞吐量，所以这种算法有一定的系统风险，一般实战很少使用。

滑动窗口

滑动窗口限流算法（rolling window）是一种常用的限流算法，用于控制系统对外提供服务的速率，防止系统被过多的请求压垮。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。它可以解决固定窗口临界值的问题。

如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。如下面所示，假设一个时间窗口是1分钟，我们将时间窗口进行均分划分，下图中是分成了6格，所以每格代表的是10秒钟。每过10秒钟，时间窗口就会往右滑动一格。每个格子都有自己独立的计数器counter，当该格子的时间范围内有请求访问counter+1，而时间窗口内共享一个限流阈值，所有格子的counter相加不能超过这个值。

滑动窗口算法可以很好地解决固定窗口算法中的临界问题。比如，还是继续之前的例子来说，时间达到59秒的时候，突如其来的100个请求会落在灰色的格子中，而60s到达的时候，接下去的请求会落在橘黄色的格子中。当时间到达60s时，我们的窗口会往右移动一格，当有新的请求来临时，该格子的counter会+1，加上之前5个格子的counter总和将超过阈值100，所以触发了限流。 当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。 算法的优点是精度高（可以通过调整时间窗口的格子大小来调节限流效果），扩展性强，算法的缺点是限流之后会直接拒绝请求，做法相对比较暴力，对用户不太友好

漏桶算法

漏桶限流算法（Leaky Bucket Algorithm）是一种流量控制算法，用于控制流入网络的数据速率，以防止网络拥塞。它的思想是将数据包看作是水滴，漏桶看作是一个固定容量的水桶，数据包像水滴一样从桶的顶部流入桶中，并通过桶底的一个小孔以一定的速度流出，从而限制了数据包的流量。

如下图所示，漏桶限流算法的基本工作原理是：对于每个到来的数据包，都将其加入到漏桶中，并检查漏桶中当前的水量是否超过了漏桶的容量。如果超过了容量，就将多余的数据包丢弃。如果漏桶中还有水，就以一定的速率从桶底输出数据包，保证输出的速率不超过预设的速率，从而达到限流的目的。 漏桶算法提供了一种机制，通过它可以让突发流量以常速速率流入（因为流出的水滴是会按照缺口大小恒定过滤），以便为系统提供稳定的请求，比如 Sentinel 中流量整形（匀速排队功能）就是此算法实现的。 优点

• 灵活性更高，可以通过调整桶的大小和漏出速率来满足不同的限流需求
• 保证处理请求的速度比较平滑，避免瞬间请求过多导致系统崩溃或者雪崩，又不会暴力拒绝请求
• 可以平滑限制请求的处理速度，避免瞬间请求过多导致系统崩溃或者雪崩。
• 可以控制请求的处理速度，使得系统可以适应不同的流量需求，避免过载或者过度闲置。

缺点

• 对于还没有流出桶的请求我们需要在内存中暂时缓存，所以会有内存消耗，而桶的大小决定了请求缓存的上限。
• 对于流量波动比较大的场景或者不同服务，需要较为灵活的参数配置才能达到较好的效果。

令牌桶算法

令牌桶算法是一种常用的限流算法，可以用于限制单位时间内请求的数量。该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入一定数量的令牌。当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，否则请求被拒绝。

如下图所示，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，令牌（token）以一个固定的速率往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求则被拒绝。 令牌桶算法的优点是弹性好，可以处理突发流量，以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流。

总结

固定窗口算法实现简单，但是会有临界突发流量问题。为了解决临界突发流量，可以将窗口划分为多个更细粒度的单元，每次窗口向右移动一个单元，于是便有了滑动窗口算法。滑动窗口当流量到达阈值时会瞬间掐断流量，所以导致流量不够平滑。如果想要达到限流的目的又让流量更加平滑，可以考虑漏桶算法，该算法通常需要配置一个先进先出（FIFO）队列来达到排序的作用。由于速率固定，即使在某个时刻下游处理能力过剩，也不能得到很好的利用，这是漏桶算法的一个短板。限流和瞬时流量其实并不矛盾，在大多数场景中，短时间突发流量系统是完全可以接受的。令牌桶算法就可以处理这类问题，令牌桶算法是按照固定速率往桶中添加令牌的，请求是否被处理需要看桶中的令牌是否足够，当令牌数减为零时，拒绝新的请求。令牌桶算法允许突发请求，只要有令牌就可以处理，允许一定程度的突发流量。漏桶算法限制的是常量流出速率，从而使突发流入速率平滑。比如服务器空闲时，理论上使用漏桶算法服务器可以直接处理一次洪峰，但是漏桶算法处理请求的速率是恒定的，因此，前期服务器资源只能根据恒定的漏水速度逐步处理请求，无法直接处理这次洪峰。而使用令牌桶算法就不存在这个问题，因为它可以先把令牌桶一次性装满，处理一次洪峰之后再走限流。 还有一点需要注意，以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到整体限流的目的，但是机器性能和数量的动态变化导致这个方式不够灵活，所以单机限流在分布式场景中会存在一定的局限性，此时我们可以考虑分布式限流，分布式限流最简单的实现就是利用中心化存储，比如redis。

负载均衡（WIP）

静态负载均衡算法：以固定的概率分配任务，不考虑服务器的状态信息，如：轮询法、加权轮询法、随机法、加权随机法等。 动态负载均衡算法：以服务器的实时负载状态信息来决定任务的分配，如：最小连接法、加权最小连接数法等。