1. 漏桶

我们在实际项目中，可能会遇到为请求限速的需求。这时候，搜索一下如何进行限流，我们往往会得到两个成对儿的概念——漏桶(Leaky Bucket)和令牌桶(Token Bucket)。出于好奇，也许你也会一起来了解这两者，来看看它们的异同和优缺点。但是，我发现很多技术博客或者B站面试速成课视频并没有解释很清楚这个问题。今天就来从漏桶/令牌桶说起，分析下两者的概念和异同；然后再谈下与之相关的却可能不着边际的一些概念和想法。

对于限速，如果不提这两个词，相信每个人也会有一些直觉的想法，比如搞一个计数器，记录最近几秒的请求数，如果这几秒的请求数大于某个预先设定的限速值，就停下来等一会儿，直到近几秒的平均速度小于限速值时，再继续处理。其实，这个思路完全没错，本质上和“两桶”相同。甚至，“两桶”之间的差异也是同一种实现的内部参数设置上的。维基百科的Leaky Bucket词条[1]中给出了两种漏桶的定义——leaky bucket as a meter和leaky bucket as a queue，并指出leaky bucket as a meter 与 token bucket 本质上就是相同的，只是描述方式不同：

In fact both (leaky bucket and tocken bucket) are effectively the same, i.e. implementations of both the leaky bucket and token bucket, as these are the same basic algorithm described differently.

并且，词条中也说明了leaky bucket as a queue是leaky bucket as a meter/token bucket的一种特例。

Analysis of the two versions of the leaky bucket algorithm shows that the version as a queue is a special case of the version as a meter.

那问题就简单了，我直接从我的理解介绍leaky bucket as a meter的原理，然后说明为啥它还能解释成一个token bucket，和啥时候它会退化成一个leaky bucket as a queue。

什么是Leaky Bucket as a Meter（或称 Token Bucket）？

先说个想法，个人认为leaky bucket as a meter虽然看上去很直观，但并不是一个很恰当的比喻，咱们一会儿会看到token bucket其实是更恰当的。

我们假设上游请求速度为λ，所期望的到下游系统的限速值是μ，那么在下图中，上游请求速度λ就是进水速度λ，期望限速值μ就是出水速度：

继续看这个图，你也许和我一样想到一道小学数学题，假设水桶大小S，注水速度v1，出水速度v2，v1>v2，多久能注满呢？我也忍不住算了一下，水桶注满时间T是bucket_size / (λ – μ)。其实这个T就是允许突发请求（burst）的时间，后边详细解释下。

对于图的含义，有一点可能会引起误解，所以一定要注意：限速值μ和漏水速度μ只是数值上相等，并不是说漏出的水是请求。真正被限速模块发送到下游的是那些成功进桶的请求，而桶出水只是为了保证后续请求可以成功进桶。这就是很多网上的博客没有解释明白的地方，也是我说把这个统一的模型解释成token bucket（下图）更好的原因：

Token bucket这个解释中，上游请求的速度仍然是速度λ，token放入的速度是μ，每个上游请求只有从桶里拿走一个token，才会被限速模块发送给下游系统。这里注满时间T会变为token放满桶的时间T。我们进一步看下为啥这“两桶”本质是相同的：对于leaky bucket as a meter，它允许可以进入桶的请求被发送到下游，对于token bucket，它允许可以拿到token的请求被发送到下游，考虑下图leaky bucket水满或者token bucket桶空的情况，下一秒时，leaky bucket中流出的水会为后续请求腾出位置，token bucket放入的token给后续请求继续被放行提供可能，因此，两者相同。

突发（Burst）和 Leaky Bucket as a Queue

那么，为什么网上的资料普遍会将两者区分对待呢，leaky bucket as a queue又是什么呢？其实，leaky bucket as a queue才更对应网络上广泛讨论的leaky bucket，因为网络上普遍称“token bucket支持突发流量，leaky bucket则不支持”。

在上边图中我举得例子中我提到，两桶都是支持突发流量的，且最大连续突发时间就是我们做小学数学题算出来的桶注满的时间T。这是因为，对于leaky bucket as a meter，只要桶中还有空间注入一个请求，这个请求就被马上放行到下游，若某段时间λ为0，那么桶很快被流光，这个时候如果突然λ变得很大，将会有很多请求短时间被注入到桶里，在注满桶的时间T里，向下游的请求便取决于较大的λ，而非限速值μ，也就是突发了；类似的，如果从token bucket角度解释，若某段时间λ为0，那么桶很快被放满token，这个时候如果突然λ变得很大，将会有很多请求短时间内拿到token被放行到下游，同样这小段时间T里向下游的请求便取决于较大的λ，而非限速值μ。

而leaky bucket as a queue的确不支持突发的。大家现在也许理解怎么支持突发了，但怎么能不支持突发呢，其实只要让突发时间T足够小，就约等于不支持突发了，也就是让桶的大小尽量小，比如桶中每次只能容纳1个请求的水量，桶会每1/μ秒从桶中漏1个请求的水量，这就是leaky bucket as a queue了，桶的大小很小，不支持突发（与其看成一个桶，不如看成一个阀门）。

网上很多资料的矛盾点在于在对比leaky bucket和token bucket的时候认为leaky bucket是不支持突发的，但在具体讲leaky bucket时却认为桶是可以不断注水的。而在本文的假设中，可蓄水和非突发是矛盾的，蓄水的作用就是支持突发，水进入桶了就放行到下游了，非突发只能通过限制桶大小来达到。不过也可以从不同的角度理解网上其他资料的解释：他们可能是将leaky bucket中进桶的意义解释为同意请求阻塞等待而桶满时直接拒绝请求，但如果这样解释，我认为就应该让token bucket桶空时也将请求拒绝，大多数资料没有提这一点。

总之，无论如何解释，只要理解底层的道理，都是可以实现所设计的功能的，重要的是定义好桶满、漏水、拿令牌等抽象动作的具体行为，它们对应的是放行、允许阻塞等待还是丢弃…… 比如，对于本文所统一的leaky bucket as a meter/token buket，注水和拿token等价，都意味着放行；leaky桶满和token桶空等价都意味着阻塞而非丢弃；桶的大小和限速值μ共同决定了突发的时间T， leaky bucket as a queue只是 leaky bucket as a meter桶大小为1的特例。

我们理解了限速是什么原理，但是我们也许还有再进一步的疑惑没有解开：假如限速器的限速生效了，那么上游系统的请求就是很快，应该怎么办，每秒相对限速值多出的请求会怎样？答案是，阻塞或丢弃，取决于具体系统的设计。丢弃了，上游系统可能会重试，可能会不开心；阻塞了，上游系统也可能会不开心。

2. 焦虑和心流

那么我们为什么会焦虑呢，其实和限速器面临的问题是一样的，我们自身就像一个前端装有限速器的下游系统，每天所能处理的事情是有限的，但是如果每天新增的事情处理不完会怎样呢？答案可能是推迟到明天，但是如果事情产生的速度大于事情处理的速度，没有完成的事情会一天比一天多，如果我们一直按事情到来的先后顺序（FIFO）一件件处理，那么这会由于事情的排队等待使得每件事情的响应速度越来越慢。如果某件事情的优先级比较靠前，那么我们可能还会重排事情处理的顺序，但这并不能改变所有事情整体的完成时间，而且有时候也会由于很多事情都很重要产生事情做不完的焦虑感。

解决的方法可能只能是“减少桶的大小”，将来排队的过多的请求丢弃掉，但这也有潜在的风险，它可能让上游系统不高兴，所以这也是焦虑的来源。所以，从排队或者限速器的角度来考虑问题，焦虑的根源是因为待办事情产生速度，大于我们处理事情的速度。要减少焦虑，一是可以提升自身的办事效率，增加事情完成出队的速度；二是尽量减少事情排队的速度。

有一个近年比较火的心理学说叫“心流”[2]，它指的是持续去完成难度适中的挑战，能让我们更有成就感、更高效、更愉悦。我是十分认同这个观点的，但是不容易的是如何去持续地找到难度适中的任务，我认为这在现实中是不可能的。我们要面对的经常是意料之外的困难或容易，事情发生的速度也不是均匀的，往往有突发。这就要求我们像调节漏桶参数一样调节自身和外界的关系，而更困难的往往是现实或者心理上的身不由己。

“心流”的概念我在一本讲游戏设计的书里看到过，也在社交媒体网文中见到过。在这两种地方的，了解或实现“心流”的目的是不同的，前者是告诉游戏设计者要让玩家在游戏中体验到心流，后者是希望读者能有更成功、更快乐的人生。虽然我认同“心流”的基本原理，但我认为一个人要在现实中达到“心流”的内外部环境远比游戏设计师在虚拟世界中为玩家设计一个“心流”的游戏环境难得多！

3. 漏桶效应

在网上搜索漏桶限速器算法相关资料时，我也看到也有人介绍漏桶效应[3]，漏桶效应是一个经济学原理。大概说的是，社会上的富人有很多粥，吃不完，穷人却吃不饱，监管机构就希望从富人那里用桶拿一些粥分给穷人（即增加对富人的税收），这样做的初衷是好的，但是漏桶效应认为在粥从富人转移到穷人的过程中，桶往往是漏的，从富人那里拿来的是一桶粥，往往到了穷人那里只剩了多半桶粥。这背后的原理可以解释为公平和效率不可兼得。漏桶效应和漏桶算法没有什么直接的关系，因为一个漏的的是粥，一个漏的是水。但漏桶效应和漏桶算法都将背后的原理过度抽象化（黑话化），也许再深入设定好前提条件、建立具体模型，我们才能更好的分析和解释具体问题，而非给出简单的结论，比如漏桶就是不支持突发、漏桶漏粥肯定会漏少半桶等等。

[1] Leaky bucket, https://en.wikipedia.org/wiki/Leaky_bucket

[2] 心流理论, https://zh.wikipedia.org/wiki/%E5%BF%83%E6%B5%81%E7%90%86%E8%AB%96

[3] 漏桶效应, https://baike.baidu.com/item/%E6%BC%8F%E6%A1%B6%E6%95%88%E5%BA%94/1550138