限流

漏桶算法

漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

如图所示，把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

令牌桶算法

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

漏桶算法和令牌桶算法的选择

漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。

漏桶算法与令牌桶算法的区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要注意的是，在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

以上都是摘抄，下面才是重点，自己的理解

查看原文可以戳这里
限流技术早期被应用于控制网络接口收发通信数据的速率，在互联网领域，也借鉴了这个概念，用于为服务控制请求的速率。

在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率

这段话怎么理解呢，比如说存在两个系统A、B，公用一个网络，网络带宽为2M, A、B各分得1M，此时通过漏桶算法控制两个系统使用网络的速率，A、B系统使用网络的速率固定最大值为1M,无论A、B系统接受多少流量，但流出的速率都限制在最大1M,当网络中没有发生拥塞，也就是可能出现B系统可能空闲没有使用网络，对应分给B系统的1M带宽是空闲的，而A系统这一时刻接收了5M的流量，由于漏桶限流的存在，A只能使用1M带宽，我们的带宽有2M,此刻我们只能使用1M,也就是达不到带宽的最大速率，另外1M带宽是浪费的，因此不能充分利用，缺乏效率；当然从另一方面来讲也带来了好处，就是隔离性，A系统无论收到多大的流量冲击，对于B系统的无感的，不会因为流量冲击A,而B受到影响.

令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

这段又该怎么理解呢，比如我们的目标现在是每秒钟处理10个请求，使用漏桶法，我们设置桶的大小为10，流出的速率为0.1s流出一个请求，我们可以达成我们的目标；而使用令牌桶的话，我们会设置每1s向桶中放入10个令牌，请求如果是平稳的，每0.1s过来一个请求，来十个，同样能达到我们的目标，这里所说的某种程度的突发传输是指，比如在一秒内前0.5请求是平稳的，每0.1s来一个，但在0.6s的时候突发请求同时来个5个请求，此时令牌算法是可以承受这个突发流量的，并且让5个请求成功立刻同时通过，完成了所谓的某种程度的突发传输，而漏桶算法，也可以应对这种突发流量，但不同的是没有让5个请求同时立刻通过，而是缓冲在桶中，然后仍然以固定速率每0.1s通过一个。

这两种算法，都可以实现流速的控制，1s处理10个请求，多于10个的请求都会被拒绝，但由于漏桶算法流出速率是一定的，所以请求可能会被缓冲在桶中，不能马上得到处理，从而徒增了等待时间，而对于令牌桶算法，没有这种等待时间，有令牌则通过，无令牌则抛弃。