漏桶算法
漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量, 执行过程如下图所示。
实现代码案例：
public class LeakyBucket { public long timeStamp = System.currentTimeMillis(); // 当前时间 public long capacity; // 桶的容量 public long rate; // 水漏出的速度 public long water; // 当前水量(当前累积请求数) public boolean grant() { long now = System.currentTimeMillis(); // 先执行漏水，计算剩余水量 water = Math.max(0, water - (now - timeStamp) * rate); timeStamp = now; if ((water + 1) < capacity) { // 尝试加水,并且水还未满 water += 1; return true; } else { // 水满，拒绝加水 return false; } } }
说明：
（1）未满加水：通过代码 water +=1进行不停加水的动作。 （2）漏水：通过时间差来计算漏水量。 （3）剩余水量：总水量-漏水量。
在 Sentine 中RateLimiterController 实现了了漏桶算法 , 核心代码如下
@Override public boolean canPass(Node node, int acquireCount, boolean prioritized) { // Pass when acquire count is less or equal than 0. if (acquireCount <= 0) { return true; } // Reject when count is less or equal than 0. // Otherwise,the costTime will be max of long and waitTime will overflow in some cases. if (count <= 0) { return false; } long currentTime = TimeUtil.currentTimeMillis(); // Calculate the interval between every two requests. // 计算时间间隔 long costTime = Math.round(1.0 * (acquireCount) / count * 1000); // Expected pass time of this request. // 期望的执行时间 long expectedTime = costTime + latestPassedTime.get(); // 当前时间 > 期望时间 if (expectedTime <= currentTime) { // Contention may exist here, but it's okay. // 可以通过，并且设置最后通过时间 latestPassedTime.set(currentTime); return true; } else { // Calculate the time to wait. // 等待时间 = 期望时间 - 最后时间 - 当前时间 long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis(); // 等待时间 > 最大排队时间 if (waitTime > maxQueueingTimeMs) { return false; } else { // 上次时间 + 间隔时间 long oldTime = latestPassedTime.addAndGet(costTime); try { // 等待时间 waitTime = oldTime - TimeUtil.currentTimeMillis(); // 等待时间 > 最大排队时间 if (waitTime > maxQueueingTimeMs) { latestPassedTime.addAndGet(-costTime); return false; } // in race condition waitTime may <= 0 // 休眠等待 if (waitTime > 0) { Thread.sleep(waitTime); } // 等待完了，就放行 return true; } catch (InterruptedException e) { } } } return false; }
令牌桶算法
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。如下图所示：
简单的说就是，一边请求时会消耗桶内的令牌，另一边会以固定速率往桶内放令牌。当消耗的请求大于放入的速率时，进行相应的措施，比如等待，或者拒绝等。
实现代码案例：
public class TokenBucket { public long timeStamp = System.currentTimeMillis(); // 当前时间 public long capacity; // 桶的容量 public long rate; // 令牌放入速度 public long tokens; // 当前令牌数量 public boolean grant() { long now = System.currentTimeMillis(); // 先添加令牌 tokens = Math.min(capacity, tokens + (now - timeStamp) * rate); timeStamp = now; if (tokens < 1) { // 若不到1个令牌,则拒绝 return false; } else { // 还有令牌，领取令牌 tokens -= 1; return true; } } }
Sentinel 在 WarmUpController 中运用到了令牌桶算法，在这里可以实现对系统的预热，设定预热时间和水位线，对于预热期间多余的请求直接拒绝掉。
public boolean canPass(Node node, int acquireCount, boolean prioritized) { long passQps = (long) node.passQps(); long previousQps = (long) node.previousPassQps(); syncToken(previousQps); // 开始计算它的斜率 // 如果进入了警戒线，开始调整他的qps long restToken = storedTokens.get(); if (restToken >= warningToken) { long aboveToken = restToken - warningToken; // 消耗的速度要比warning快，但是要比慢 // current interval = restToken*slope+1/count double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); if (passQps + acquireCount <= warningQps) { return true; } } else { if (passQps + acquireCount <= count) { return true; } } return false; }
限流算法总结
计数器 VS 时间窗
- 时间窗算法的本质也是通过计数器算法实现的。
- 时间窗算法格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确，但是也会占用更多的内存存储。
漏桶 VS 令牌桶
- 漏桶算法和令牌桶算法本质上是为了做流量整形或速率限制，避免系统因为大流量而被打崩，但是两者的核心差异在于限流的方向是相反的
- 漏桶：限制的是流量的流出速率，是相对固定的。
- 令牌桶 ： 限制的是流量的平均流入速率，并且允许一定程度的突然性流量，最大速率为桶的容量和生成token的速率。
- 在某些场景中，漏桶算法并不能有效的使用网络资源，因为漏桶的漏出速率是相对固定的，所以在网络情况比较好并且没有拥塞的状态下，漏桶依然是会有限制的，并不能放开量，因此并不能有效的利用网络资源。而令牌桶算法则不同，其在限制平均速率的同时，支持一定程度的突发流量。
