• 令牌桶算法谷歌实现
2022-01-24 21:25:32

# 令牌桶算法

## 小序

The token bucketis an algorithm used in packet-switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth) and burstiness (a measure of the unevenness or variations in the traffic flow).
令牌桶是一种用于分组交换和电信网络的算法。它可用于检查数据包形式的数据传输是否符合定义的带宽和突发性限制（流量不均匀或变化的度量)


## 谷歌实现

### 添加maven依赖

<dependency>
<artifactId>guava</artifactId>
<version>30.1-jre</version>
</dependency>


### 测试用例

import com.google.common.util.concurrent.ListeningExecutorService;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.Executors;

public class LimitTest {

public static void main(String[] args) {

RateLimiter limiter = RateLimiter.create(1);
for (int i = 1; i < 50; i++) {
Double acquire = limiter.acquire(i);
}
}
static class PrintTask implements Runnable {
String out;
this.out = out;
}
@Override
public void run() {
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
}
}
}



### 核心方法

//实例化处理器 每秒允许一个请求通过
RateLimiter limiter = RateLimiter.create(1);
//获取令牌
Double acquire = limiter.acquire(i);


### 源码

/**
创建具有指定稳定吞吐量的RateLimiter ，以“每秒允许数”（通常称为QPS ，每秒查询数）的形式给出。
返回的RateLimiter确保在任何给定的秒内平均发出不超过permitsPerSecond ，持续的请求在每一秒内顺利传播。 当传入请求速率超过permitsPerSecond时，速率限制器将每(1.0 / permitsPerSecond)秒释放一个许可。 当速率限制器未使用时，将允许最多permitsPerSecond许可的突发，随后的请求以permitsPerSecond的稳定速率平滑限制。

参数：
permitPerSecond – 返回的RateLimiter的速率，以每秒可用的许可数量衡量
抛出：
IllegalArgumentException – 如果permitsPerSecond为负数或零
推断注释：
@org.jetbrains.annotations.NotNull @org.jetbrains.annotations.Contract("_->new")

*/
public static RateLimiter create(double permitsPerSecond) {
/*
* The default RateLimiter configuration can save the unused permits of up to one second. This
* is to avoid unnecessary stalls in situations like this: A RateLimiter of 1qps, and 4 threads,
* all calling acquire() at these moments:
*
* T0 at 0 seconds
* T1 at 1.05 seconds
* T2 at 2 seconds
* T3 at 3 seconds
*
* Due to the slight delay of T1, T2 would have to sleep till 2.05 seconds, and T3 would also
* have to sleep till 3.05 seconds.
默认的 RateLimiter 配置最多可以保存一秒钟的未使用许可。这是为了避免在以下情况下出现不必要的停顿： 1qps 的 RateLimiter 和 4 个线程，在这些时刻都调用 acquire()： T0 在 0 秒 T1 在 1.05 秒 T2 在 2 秒 T3 在 3 秒 由于轻微延迟在 T1 中，T2 必须睡到 2.05 秒，T3 也必须睡到 3.05 秒。
*/
return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
}



从源码中我们可以看到，除了传入的速率值，还需要初始化一个SleepingStopwatch.createFromSystemTimer()定时处理器，我们看看这个里面到底有什么。

### SleepingStopwatch

 public static SleepingStopwatch createFromSystemTimer() {
return new SleepingStopwatch() {
//初始化Stopwatch 并启动
final Stopwatch stopwatch = Stopwatch.createStarted();

/**
读取秒表
*/
@Override
return stopwatch.elapsed(MICROSECONDS);
}

/**
睡眠
*/
@Override
protected void sleepMicrosUninterruptibly(long micros) {
if (micros > 0) {
Uninterruptibles.sleepUninterruptibly(micros, MICROSECONDS);
}
}
};
}
//stopwatch.elapsed(MICROSECONDS) 获取当前时间
public long elapsed(TimeUnit desiredUnit) {
//获取时间并转换为纳秒
return desiredUnit.convert(elapsedNanos(), NANOSECONDS);
}
//elapsedNanos() 获取时间
private long elapsedNanos() {
// 如果当前处于运行状态 则从ticker中读取时间-开始计时的时间+elapsedNanos时间， 否则返回elapsedNanos 过去时间
return isRunning ? ticker.read() - startTick + elapsedNanos : elapsedNanos;
}
//追踪ticker 初始化对象中Stopwatch.createStarted();
Stopwatch() {
this.ticker = Ticker.systemTicker();
}
// Ticker 源码 其实就是去读取系统的纳秒时间
public abstract class Ticker {
protected Ticker() {}
public static Ticker systemTicker() {
return SYSTEM_TICKER;
}
private static final Ticker SYSTEM_TICKER =
new Ticker() {
@Override
return Platform.systemNanoTime();
}
};
}
//Platform.systemNanoTime 读取系统时间
static long systemNanoTime() {
return System.nanoTime();
}



可以看到createFromSystemTimer 方法返回了一个只有读取秒表时间和睡眠的方法的实例。可以看到这个方法主要是获取系统的纳秒时间

我们继续跟踪主线代码create方法

  @VisibleForTesting
static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
rateLimiter.setRate(permitsPerSecond);
return rateLimiter;
}
----->创建对象
SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
super(stopwatch);
this.maxBurstSeconds = maxBurstSeconds;
}



到这里我们可以看到，ReteLimiter真正的实现是SmoothBursty，然后设置下流速，就返回了。到此对象的实例算是完成了，我们这条线暂时到这。接下来看看acquire获取令牌的方法。

### acquire 获取令牌

/**
从此RateLimiter获取给定数量的许可，阻塞直到可以授予请求。 告知睡眠时间（如果有）
*/
@CanIgnoreReturnValue
public double acquire(int permits) {
//获取需要等待的时间
long microsToWait = reserve(permits);
//阻塞等待
stopwatch.sleepMicrosUninterruptibly(microsToWait);
//返回一个值，其实这个值是多少没什么太大作用
return 1.0 * microsToWait / SECONDS.toMicros(1L);
}


可以看到，申请token的方法中，主要实现三个功能：

1. 计算等待时间
2. 阻塞等待
3. 返回一个值

可以看到核心是reserve计算等待时间这个方法，我们可以继续跟进去。

/**
* Reserves the given number of permits from this {@code RateLimiter} for future use, returning
* the number of microseconds until the reservation can be consumed.
* 从此RateLimiter保留给定数量的许可以供将来使用，返回微秒数，直到可以使用保留
* @return time in microseconds to wait until the resource can be acquired, never negative
*/
final long reserve(int permits) {
//校验permits是否大于0，负责抛出异常
checkPermits(permits);
// mutex 设置上锁点
synchronized (mutex()) {
//核心 保留并计算等待时间长度
}
}


可以看到reserveAndGetWaitLength才是我们算法的核心所在，这个方法需要的参数，除了我们传入的速率之外，还有一个从stopwatch中读取的秒表，我们继续跟踪查看：

/**
* Reserves next ticket and returns the wait time that the caller must wait for.
* 保留下一张票并返回调用者必须等待的等待时间
* @return the required wait time, never negative
*/
final long reserveAndGetWaitLength(int permits, long nowMicros) {
//获取最早可用的时间
long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
//返回需要等待时间值
return max(momentAvailable - nowMicros, 0);
}


这里reserveEarliestAvailable 就是我们的主要目标了，怼吧。

  @Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
//1.重新同步时间
resync(nowMicros);
//2.将下次可以获取获取令牌的时间作为返回值
long returnValue = nextFreeTicketMicros;
//3.存储消费许可， 取要求token个数和已有token个数的最小值
/*
3.存储消费许可， 取要求token个数和已有token个数的最小值
4.去除要求的token之外，剩余token个数
这两步要合起来看
需求toke个数： requiredPermits
已有token： storedPermits
如果requiredPermits > storedPermits，则需要新令牌的个数为
requiredPermits - storedPermits
如果requiredPermits <= storedPermits,则需要新令牌的个数为
requiredPermits - storedPermits
这两行代码写的真是厉害
*/
double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
// 4.去除要求的token之外，需要重新刷的token个数
double freshPermits = requiredPermits - storedPermitsToSpend;
//5.令牌消费之后,剩余令牌可以使用的时间
long waitMicros =
storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros);
//6.刷新下个允许获取令牌的时间
//7.更新消费许可
this.storedPermits -= storedPermitsToSpend;
return returnValue;
}

//-----------------------------resync 代码------------------------------
void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
//如果允许获取下一个令牌的时间小于当前时间，则更新nextFreeTicketMicros为当前时间
if (nowMicros > nextFreeTicketMicros) {
//计算当前时间和next的时间差内可以产生的token个数
double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
//更新存储的可用token的个数
storedPermits = min(maxPermits, storedPermits + newPermits);
//更新允许可以获取下一个token的时间
nextFreeTicketMicros = nowMicros;
}
}



可以看到这里就是我们的索要追踪的核心所在了，

1. 重新同步时间的逻辑

1.2.1. 计算当前时间和上一个next的时间差内可以产生的token个数

1.2.2. 更新当前可存储的token个数

1.2.3. 更新允许获取下一个token的时间next

2. 将下次可以获取获取令牌的时间作为返回值

3. 存储消费许可， 取要求token个数和已有token个数的最小值，具体原因可以看代码注释

4. 去除要求的token之外，需要重新刷的token个数

5. 令牌消费之后,剩余令牌可以使用的时间

6. 计算下个允许获取令牌的时间

7. 更新剩下的消费许可

获取到需要等待的时间之后，我们就可以返回方法处了

/**
从此RateLimiter获取给定数量的许可，阻塞直到可以授予请求。 告知睡眠时间（如果有）
*/
@CanIgnoreReturnValue
public double acquire(int permits) {
//获取需要等待的时间
long microsToWait = reserve(permits);
//阻塞等待
stopwatch.sleepMicrosUninterruptibly(microsToWait);
//返回一个值，其实这个值是多少没什么太大作用
return 1.0 * microsToWait / SECONDS.toMicros(1L);
}


这个拿到需要阻塞的时间之后，直接阻塞，时间到了，返回值。 到此算是整个过程处理完毕。

## 总结

从源码看这个令牌桶算法是先拿的人是无限制，拿到之后，下次可以获取令牌的时间，就要等到这些令牌的制造所需时间过后才能重新获取。

更多相关内容
• 主要介绍了15行Python代码带你轻松理解令牌桶算法,需要的朋友可以参考下
• RateLimiters .NET中的和实现。 这些策略可用于对各种Web，后端或API调用方案中的限制请求进行评分。 此项目是@sudohippie在此之后的.NET克隆。 建置状态 该库使用服务不断集成。
• 基于令牌桶算法的Java限流实现。 项目需要使用限流措施，查阅后主要使用令牌桶算法实现，为了更灵活的实现限流，就自己实现了一个简单的基于令牌桶算法的限流实现。
• 令牌桶 Java 源码 不限制桶大小
• 利用Redis和Golang实现分布式令牌桶算法，令牌桶算法对速率限制和网络拥塞控制非常有用
• 系统在运行过程中，如遇上某些活动，访问的人数会在一瞬间内爆增，导致服务器瞬间压力飙升，使系统超...本文介绍php基于redis，使用令牌桶算法，实现访问流量的控制，提供完整算法说明及演示实例，方便大家学习使用。
• Token Bucket Emulation in C using Multithreading This project involved emulation of the Token Bucket algorithm using POSIX threads in C. The aim was to simulate a traffic shaper that receives and ...
• 基于令牌桶算法实现的SpringBoot无锁限流插件，支持方法级别、系统级别的限流，提供快速失败与CAS阻塞两种方案，开箱即用！
• Linux多线程实现令牌桶流量控制,内有makefile
• ratelimit 基于令牌桶算法和漏桶算法来实现的限速限流，Golang实现
• 这里的Open vSwitch利用分层令牌桶排队规则来管理带宽。 路由算法是在Ryu控制器中分别基于尽力而为图和QoS数据流的图形实现的。 最短路径路由基于交换机的距离图来实现尽力而为流。 最短的QoS路径路由基于资源残差...
• 提出一种基于令牌桶算法的抵御Flood攻击的通信量整形模型和过滤规则,从硬件线路的改进着手对Flood攻击行为进行瓦解。
• 本文章是关于令牌桶算法的应用。
• 设计了一个基于令牌桶阵列(TBA)的实现方案，不需要实时估计攻击流的参数，有效提高了过滤的性能。理论推导表明： Poisson流随机分解模型的理论错误率上限为最大后验概率判决法错误率上限的2倍，TBA在过滤突发性强的...
• 2、令牌桶算法 3、两种算法的区别 4、限流工具类RateLimiter 4.1 RateLimiter demo 4.2 主要接口 常用的限流算法有两种：漏桶算法和令牌桶算法。 1、漏桶算法 漏桶算法思路很简单，请求先进入到漏桶里，漏桶...

目录

1、漏桶算法

2、令牌桶算法

3、两种算法的区别

4、限流工具类RateLimiter

4.1 RateLimiter demo

4.2 主要接口

常用的限流算法有两种：漏桶算法和令牌桶算法。

## 1、漏桶算法

漏桶算法思路很简单，请求先进入到漏桶里，漏桶以固定的速度出水，也就是处理请求，当水加的过快，则会直接溢出，也就是拒绝请求，可以看出漏桶算法能强行限制数据的传输速率

但是对于很多场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。

## 2、令牌桶算法

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

为了更好的理解令牌桶算法，自己造了一个限流算法的简略代码，方便理解。

创建一个需要执行的任务，使用线程池执行。

public class TaskRunnable implements Runnable {
private Integer reqCount;//已使用令牌数量
this.reqCount = reqCount;
}
@Override
public void run() {
}
}

具体执行逻辑和限流逻辑，//自己造轮子

public class TokenTask {
//关键：时间控制周期+令牌桶容量
static volatile long timeStamp = getNowTime();//令牌桶计时开始
static AtomicInteger reqCount = new AtomicInteger(0);//统计调用数
static final int maxReqCount = 5;//时间周期内最大请求数
static final long effectiveDuration = 1000;//时间控制周期(秒)
/**
* 限流逻辑
* @return
*/
public static boolean passControl() {
long now = getNowTime();//程序执行时间
if (now < (timeStamp + effectiveDuration)) {//在时间控制范围内
reqCount.getAndIncrement();
return reqCount.get() <= maxReqCount;//当前时间范围内超过最大请求控制数
} else {
timeStamp = now;//超时后重置
reqCount = new AtomicInteger(1);//占用一个令牌
return true;
}
}
//获取执行时间
public static long getNowTime() {
return System.currentTimeMillis();
}

public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10; i++) {
if (passControl()) {//放行
} else {
System.out.println("被限流，请稍后访问！");
}
}
}
}

限流效果

注：本算法只是简单模拟了一下限流流程，不能用于生产。

## 3、两种算法的区别

漏桶算法输入的时候请求不固定，但都会在漏桶里边先保存起来（小于漏桶的容量），然后输出的时候采用的是恒定的速率执行请求，有点像队列的先进先出，只是队列中的元素出队的时间间隔一致。

令牌桶算法跟漏桶算法刚好相反，令牌桶的大小就是接口所能承载的最大访问量，令牌的发放是恒速的，而最终能在某一时间处理的请求数不是恒定的，这取决于单位时间内令牌桶中的令牌数量。

## 4、限流工具类RateLimiter

### 4.1 RateLimiter demo

//多任务执行,但每秒执行不超过2个任务
final RateLimiter rateLimiter = RateLimiter.create(2.0);
rateLimiter.acquire(); //默认获取1个令牌
}
}
//以每秒5kb内的速度发送-限制数据包大小
final RateLimiter rateLimiter = RateLimiter.create(5000.0);
void submitPacket(byte[] packet) {
rateLimiter.acquire(packet.length);//获取指定数量的令牌
networkService.send(packet);
}
//以非阻塞的形式达到降级
if(limiter.tryAcquire()) { //未请求到limiter则立即返回false
doSomething();
}else{
doSomethingElse();
}

### 4.2 主要接口

RateLimiter其实是一个abstract类，但是它提供了几个static方法用于创建RateLimiter：

/**
* 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* 当请求到来的速度超过了permitsPerSecond，保证每秒只处理permitsPerSecond个请求
* 当这个RateLimiter使用不足(即请求到来速度小于permitsPerSecond)，会囤积最多permitsPerSecond个请求
*/
public static RateLimiter create(double permitsPerSecond);

/**
* 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* 还包含一个热身期(warmup period),热身期内，RateLimiter会平滑的将其释放令牌的速率加大，直到起达到最大速率
* 同样，如果RateLimiter在热身期没有足够的请求(unused),则起速率会逐渐降低到冷却状态
*
* 设计这个的意图是为了满足那种资源提供方需要热身时间，而不是每次访问都能提供稳定速率的服务的情况(比如带缓存服务，需要定期刷新缓存的)
* 参数warmupPeriod和unit决定了其从冷却状态到达最大速率的时间
*/
public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit);

提供了两个获取令牌的方法，不带参数表示获取一个令牌。如果没有令牌则一直等待，返回等待的时间(单位为秒)，没有被限流则直接返回0.0

public double acquire();//默认获取一个令牌
public double acquire(int permits);//获取指定令牌数

尝试获取令牌，分为待超时时间和不带超时时间两种：

//尝试获取一个令牌,立即返回
public boolean tryAcquire();
public boolean tryAcquire(int permits);
//尝试获取permits个令牌，带超时时间
public boolean tryAcquire(long timeout, TimeUnit unit);
public boolean tryAcquire(int permits, long timeout, TimeUnit unit);

下篇这篇文章一点要看：

https://zhuanlan.zhihu.com/p/60979444

参考阅读：

流量控制算法——漏桶算法和令牌桶算法 - 知乎

展开全文
• bucket4j, 基于令牌桶算法的Java速率限制库 Bucket4j - 基于令牌桶算法的Java速率限制库。 的优点在已经知算法的基础上实现，它是in行业的速率限制的实际标准。有效的锁自由实现，Bucket4j可以用于多线程处理。绝对...
• 在网络中传输数据的时候时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能，可控制发送到网络上数据的数目，并允许突发数据的发送。

# 简介

在网络中传输数据的时候时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能，可控制发送到网络上数据的数目，并允许突发数据的发送。

令牌桶算法是网络流量整形和速率限制中最常使用的一种算法。大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。

传送到令牌桶的数据包需要消耗令牌。不同大小的数据包，消耗的令牌数量不一样。

令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。

与“令牌桶算法”类似的算法还有“漏桶算法”，这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。

在本文中，我们使用 Golong 语言实现一个简单的“令牌桶算法”，或者说是“漏桶算法”更为合适。

# 实现

首先，我们假设令牌桶的放入令牌的速率是恒定的，不考虑流量速率突变的情况。

package awesomeProject

import (
"sync"
"time"
)

// 定义令牌桶结构
type tokenBucket struct {
limitRate int           // 限制频率，即每分钟加入多少个令牌
tokenChan chan struct{} // 令牌通道，可以理解为桶
cap       int           // 令牌桶的容量
muLock    *sync.Mutex   // 令牌桶锁，保证线程安全
stop      bool          // 停止标记，结束令牌桶
}

// NewTokenBucket 创建令牌桶
func NewTokenBucket(limitRate, cap int) *tokenBucket {
if cap < 1 {
panic("token bucket cap must be large 1")
}
return &tokenBucket{
tokenChan: make(chan struct{}, cap),
limitRate: limitRate,
muLock:    new(sync.Mutex),
cap:       cap,
}
}

// Start 开启令牌桶
func (b *tokenBucket) Start() {
go b.produce()
}

// 生产令牌
func (b *tokenBucket) produce() {
for {
b.muLock.Lock()
if b.stop {
close(b.tokenChan)
b.muLock.Unlock()
return
}
b.tokenChan <- struct{}{}
d := time.Minute / time.Duration(b.limitRate)
b.muLock.Unlock()
time.Sleep(d)
}
}

// Consume 消费令牌
func (b *tokenBucket) Consume() {
<-b.tokenChan
}

// Stop 停止令牌桶
func (b *tokenBucket) Stop() {
b.muLock.Lock()
defer b.muLock.Unlock()
b.stop = true
}


其中，

• tokenBucket为令牌桶的结构，包括限制频率、令牌桶容量和通道等；
• NewTokenBucket为对外提供的创建令牌桶的方法；
• Start为开启令牌桶的方法；
• produce为以恒定速率生成令牌的方法，以协程的方式启动；
• Consume为消费令牌的方法；
• Stop为停止令牌桶的方法。

如上述所示，即为令牌桶的简易实现。

# 轮子

实际上，在 Go 语言中已经提供了对令牌桶的支持了，因此不需要我们重复造轮子。

更详细的内容，大家可以点击「limiter」进行查看，祝好！

参考资料

展开全文
• token_bucket令牌桶算法原理 讲在原理之前 我们今天主要是分析令牌桶算法，分析之前我们先介绍一下使用该算法的背景。 限流 每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限...

## token_bucket令牌桶算法原理

### 讲在原理之前

我们今天主要是分析令牌桶算法，分析之前我们先介绍一下使用该算法的背景。

#### 限流

每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.

通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.

如果要准确的控制QPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零.此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的QPS.

总的来说，限流就是可以认为服务降级的一种，限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。
常见的限流算法有漏桶算法和令牌桶算法，今天我们主要来看令牌桶算法。

### 令牌桶算法

#### 算法简介

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

#### 算法原理

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。 当桶满时，新添加的令牌被丢弃或拒绝。
令牌桶算法是一个存放固定容量令牌（token）的桶，按照固定速率往桶里添加令牌。令牌桶算法基本可以用下面的几个概念来描述：

• 令牌将按照固定的速率被放入令牌桶中。比如每秒放10个。
• 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。
• 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。
• 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

如下示意图：

通俗的理解，令牌桶是一个水桶，而令牌是通过一根水管流到水桶中的水。
令牌桶的填满时间，是由桶的自身容量、令牌漏出速率（桶下面的水管）、超过平均速率的突发流量持续的时间三个方面共同决定的。如果突发流量的时间比较短，令牌桶不会溢出，在通信流上不会受到影响，如果突发流量比较大，时间比较长，那令牌桶就会溢出，多余的通信流就会被限制。
令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

展开全文
• redis实现令牌桶的正确姿势 最近需要自己做一个限流功能，其他业务代码都好说。唯一的终点就是限流实现，想到redis可以实现令牌桶。一拍脑门，就用它了！ 真实开发中才发现想的太简单，如果是基于redis提供的命令...
• 能够“保留”令牌并创建“令牌债务” 需要Redis 3.2或更高版本。 安装 将此行添加到您的应用程序的Gemfile中： gem 'redis_token_bucket' 用法 基本速率限制： require 'redis' require 'redis_token_bucket' # ...
• 令牌以固定速率产生，并缓存到令牌桶中； 令牌桶放满时，多余的令牌被丢弃； 请求要消耗等比例的令牌才能被处理； 令牌不够时，请求被缓存。 漏桶算法 算法思想是： 水（请求）从上方倒入水桶，从水桶下方...
• ## 令牌桶算法实现

千次阅读 2022-04-01 22:19:37
#define MYTBF_MAX 1024 //能够支持1024个不同速率的令牌桶 typedef void mytbf_t; mytbf_t *mytbf_init(int, int); int mytbf_fetchtoken(mytbf_t *, int); int mytbf_returntoken(mytbf_t *, int); int mytbf...
• ## 限速之令牌桶理解

千次阅读 2021-03-11 14:55:17
背景 在高并发的场景下，我们的优化和保护系统的方式通常有：多级缓存...匀速的产生令牌，往里面丢； 每次请求来，看是否有多余的令牌。如果有，获取令牌执行正常业务；如没有，丢包限速。 适用场景 原理 ...
• 序言 此两种算法是服务降级的一种实现. 常用于限制我们的对外服务的QPS,即控制对外服务在单位时间内所能处理的请求数量.... 漏算法(有点像Kafka,大批量的数据吞吐) ... 漏层将大批量的请求以特定的速度转发给co..
• 令牌桶在容量固定，在请求量平缓且低于令牌生成速率（令牌生成速率及令牌桶容量要根据系统的处理能力设置）时，令牌桶是满的，面对突发的大流量，令牌桶容量大小的请求数能获取到令牌，降低流量峰值的同时，避免大量...

...