如何设计一个分布式限流器（distributed rate limiter）

Rate Limiter

限流器（rate limiter）是一种在实际工程中广泛应用的组件，其主要作用就是限制上游服务的请求量。比如一个公司有两个服务：服务A和服务B，服务A需要经常请求服务B，那么服务B为了保证自己不被来自A的异常高的请求打挂（即是现在分布式系统时代做自动扩容很快，但对于TPS较大的服务来说这些异常高的请求量仍然是有显著影响的），就会和服务A协商，定一个服务A的TPS阈值，设置限流器来保证自己服务的安全。又比如某公司G提供某种有偿的API服务，G公司为了赚钱需要对不同级别的TPS定不同的收费标准，那么G公司就必须要对这个API做流量控制，如果用户的TPS超过了某个阈值，那就返回错误，要想访问这个API更频繁并且获得正确的结果就得多交钱。
很多提供API服务的公司都有自己的限流器，比如著名的同性交友网GitHub: GitHub REST API v3，明确了普通用户对API的请求必须在5000次/小时以内，否则就会返回403 Forbidden。类似的，领英也有自己的rate limiter，对不同的API有不同的限流准则：LinkedIn Getting started with the REST API。

限流算法（rate limiting algorithm）

限流算法有很多，各有优劣，在这里简单介绍一下各种限流算法的差异。

漏桶法（Leaky Bucket）和令牌桶法（Token Bucket）

其实我感觉两种算法虽然都带桶字，但两者的思路却完全不同。
漏桶法比较直观，想象一个底部有个洞的桶，向桶口灌水，水通过底部的洞漏出来。桶底的洞一般是比桶口小很多的，所以如果灌水太快了桶就会被灌满，这样水就会溢出。灌水相当于上游打来请求，底部洞中漏水相当于处理请求，桶的大小即服务能够承受的流量，溢出的水就是被拒绝处理的请求。用数据结构抽象，漏桶就是一个FIFO的队列，请求不断地从队尾插入，服务不断地从队首取出请求进行处理，队列的容量就是服务能够承受的流量。
漏桶法的好处很明显，服务完全不会被异常高的TPS打垮，并且原理很简单，比较容易实现。但如果有个请求处理时间较长，那么他后面的请求都会跟着遭殃，所以漏桶法会有一个请求阻塞其他请求的可能。并且如果上游打来的请求不均匀，则漏桶很容易被灌满，所以漏桶法也处理不了burst。
令牌桶是想象有一个桶里放满了令牌，每来一个请求就取一个令牌，如果没有令牌可取了就拒绝处理请求，同时也会以一定的速率往桶里加令牌。一般往桶里加令牌的速率就被配置为平均的TPS，桶的容量则为能够接受的最大burst。令牌桶相比漏桶就有一个比较大的好处，那就是能够处理请求量的burst，能够处理上游不均匀的请求。

固定窗口法（Fixed Window）

这里所说的窗口（window）就是时间窗口。固定窗口法规定了在某个固定的时间范围内的请求量阈值，如果在这个时间范围内的请求量超过阈值，则直接拒绝处理。
固定窗口法的好处就是旧请求不会影响后面的新请求，但缺点也很明显，在窗口刷新的时候可能会放更多请求进来，比如配置的QPS是100，在上一个窗口的最后0.5秒打来了100个请求，在当前窗口的第一个0.5秒打来了100个请求，这样会在一秒内接受200个请求，与配置相去甚远。

滑动日志法（Sliding Log）

滑动日志以日志的形式记录每个请求，每条日志包含一个请求的时间戳，如果有新请求，则根据其时间戳和之前的日志，计算TPS，如果TPS超过阈值则，则只加到日志不作处理。
滑动日志法更像是无限容量的漏桶法，解决了固定窗口法的edge case，但需要存储日志，对存储来说有压力，并且每次来请求都要计算一次日志量，计算成本太高。

滑动窗口法（Sliding Window）

滑动窗口法和固定窗口法很相似，区别就是固定窗口法每个时间窗口只能处理固定的请求量，而滑动窗口根据请求的时间往前找一个时间窗口，查看这个时间窗口的请求量是否超过了阈值，如果没有超过则处理请求，否则拒绝处理该请求。

滑动窗口法咋看起来很漏桶法很类似，但漏桶法新请求可能会被旧请求阻塞住，滑动窗口法就不会，并且滑动窗口的原理也比较简单易懂。滑动窗口也能处理请求量的burst，比如我们设置了时间窗口为一小时，有可能在上一个小时请求量还没超过阈值，则相当于可以将上一个小时剩余的容量加到当前这个小时，当前小时就能够处理更多的请求。

以上的方法都是对于单机而言的，关于单机版的限流器，比较著名的基本上都是基于令牌桶实现的，比如Google的Guava，Go语言的官方库中也有rate。

分布式限流器（distributed rate limiter）

可以看到，以上的算法中，令牌桶（Token Bucket）和滑动窗口（Sliding Window）是两种最优的算法，都能够处理不均匀的请求。以上描述的算法都只是理论，在单机或许能够有效，但如今各个服务基本上都是分布式的，如何设计分布式限流器呢。

配置在负载均衡器（Load Balancer）

首先最容易想到的是，在服务的负载均衡器（Load Balancer）中配置一个限流器，这样每来一个请求就可以进行一次检查，并且配置绝对是全局性的。这样做确实可以做到丝毫不差。但由于负载均衡器一般是云服务商提供的，一般的程序员可能无法直接在上面写代码。并且配置在负载均衡器上也做不了容错，可能还会影响扩容。

配置在中心化数据库

由于我们想要一个全局的限流器，也就是说服务虽然部署在分布式系统中，但在外界看起来就像部署在单台机器上一样，那样就必须要一个中心化的存储设备去管理限流器，比如Redis。
一种直观的做法是，将限流器配置在数据库中，每个节点收到来自上游的请求后直接请求数据库，然后数据库根据限流器判断是否处理这个请求，最后返回给节点相关信息。如果用Redis实现，限流器的代码可以通过Lua脚本的方式放在Redis端，从而减少节点访问Redis的次数。
如果服务的流量不大的话，这种简单的基于中心化数据库的实现方法还能撑住。但如果服务的流量很大，这种方法则会有很大的成本和性能问题，每有一个上游的请求，节点就会请求一次数据库并等待数据库是否限流的回复，那么数据库的压力的特别大，会造成从数据库返回结果的延迟较高。并且为了得到正确的结果，每个节点访问数据库的时候还需要避免数据竞争，如果是支持事物的数据库还好，如果基于Redis做，这就需要对限流器加锁，Redis的延迟会更高，这样会导致服务处理请求的延迟很高。

优化基于中心化数据库的限流器

为了解决因为对中心化数据库访问过于频繁并且需要加锁导致的延迟问题，做分布式限流器就必须要减少节点访问Redis的频次。这里我们就可以在节点上做一部分限流器的工作，再周期性地访问数据库同步，以达到减少对数据库请求的目的。以下称中心化数据库上的限流器为中心限流器，每个节点上的限流器为本地限流器。
第一种方法是在节点上积攒够一定的请求量N后再去请求中心限流器，这样节点对中心化数据库的请求频次会降低为1/N。但在请求积攒阶段这些请求就无法决定是否被处理，这样也会造成一定的延迟增加。并且如果请求十分不均匀，在积攒阶段迟迟攒不到N个，即使设置了积攒超时也会大大增加延迟。同时，由于是一次性发送N个请求，也会造成一定的误差。
第二种方法是认为负载均衡器会将流量十分均匀的分布在各个节点上，这样本地限流器的配置就等于全局限流器的配置除以节点数量。这样不需要中心限流器，只需要用一个中心化的数据库比如etcd/Redis存储节点的数量，每个节点以固定的频率请求节点数量更新本地的配置即可。每个节点可以定时向中心化数据库发送心跳，以便中心化数据库可以统计出活着的节点数。这样做对中心化数据库的压力更小，但误差也更大。首先负载均衡器并不能保证流量会十分均匀地打到各个节点上，其次中心化数据库也可能对活着的节点数量统计不准确，因为有可能节点在两次发送心跳图中就挂了。但个人觉得这个误差会始终在容忍范围内。
前两种方法对于令牌桶和滑动窗口都适用，还有一种针对于令牌桶的方法：每个节点初始时请求中心限流器N个令牌，当N个令牌都消耗完了再去数据库请求N个。这种方法和第一种方法比较类似，也会有误差，但相比之下延迟会有所降低。

以上三种方法都会有一定的误差，就目前搜集到的资料来看，笔者没有发现没有误差且成本和性能都能接收的分布式限流器设计。如果是像G公司那样要靠限流来精准定价收费，可能他们就算建分布式数据库做中心化限流器也要准确地计算出TPS。如果是公司内部两个服务之间搞搞，那以上三种方法皆可，个人比较倾向于第二种方法，因为第二种方法对中心化数据库的压力最小，逻辑也比较简单，这样实现成本最小，误差虽然是最大的但感觉也在可容忍范围内。

小结

以上这些都是些原理性的东西，为什么我不写个示例代码？因为这玩意儿已经有很多开源项目都搞了，最著名的应该就是Hystrix，还有一个轻量级的resilience4j，还有个人开发者弄的SnowJena。