# 聊聊token bucket算法的实现

## 限流算法概述

• 基于信号量Semaphore只有数量维度，没有时间维度
• 基于fixed window带上了时间维度，不过在两个窗口的临界点容易出现超出限流的情况，比如限制每分钟10个请求，在00:59请求了10次，在01:01又请求了10次，而从00:30-01:30这个时间窗口来看，这一分钟请求了20次，没有控制好
• 基于rolling window就是要解决fixed window没解决的窗口临界问题，主要有基于token bucket的算法，以及基于leaky bucket的算法

## token bucket算法

• token按指定速率添加到bucket中
• 一个bucket有其容量限制，超过其容量则多余的token会被丢弃
• 当请求到来时，先试图获取token，如果剩余token足够则放行，不够则不允许放行(`可能等待token足够再继续`)

## 简单实现

```/**
* The minimalistic token-bucket implementation
*/
public class MinimalisticTokenBucket {

private final long capacity;
private final double refillTokensPerOneMillis;

private double availableTokens;
private long lastRefillTimestamp;

/**
* Creates token-bucket with specified capacity and refill rate equals to refillTokens/refillPeriodMillis
*/
public MinimalisticTokenBucket(long capacity, long refillTokens, long refillPeriodMillis) {
this.capacity = capacity;
this.refillTokensPerOneMillis = (double) refillTokens / (double) refillPeriodMillis;

this.availableTokens = capacity;
this.lastRefillTimestamp = System.currentTimeMillis();
}

synchronized public boolean tryConsume(int numberTokens) {
refill();
if (availableTokens < numberTokens) {
return false;
} else {
availableTokens -= numberTokens;
return true;
}
}

private void refill() {
long currentTimeMillis = System.currentTimeMillis();
if (currentTimeMillis > lastRefillTimestamp) {
long millisSinceLastRefill = currentTimeMillis - lastRefillTimestamp;
double refill = millisSinceLastRefill * refillTokensPerOneMillis;
this.availableTokens = Math.min(capacity, availableTokens + refill);
this.lastRefillTimestamp = currentTimeMillis;
}
}

private static final class Selftest {

public static void main(String[] args) {
// 100 tokens per 1 second
MinimalisticTokenBucket limiter = new MinimalisticTokenBucket(100, 100, 1000);

long startMillis = System.currentTimeMillis();
long consumed = 0;
while (System.currentTimeMillis() - startMillis < 10000) {
if (limiter.tryConsume(1)) {
consumed++;
}
}
System.out.println(consumed);
}

}

}```
• 以上是bucket4j给出的一个简单实现，用于理解token bucket算法
• 这个算法没有采用线程去refill token，因为bucket太多的话，线程太多，耗cpu
• 这个算法没有存储每个period使用的token，设计了lastRefillTimestamp字段，用于计算需要填充的token
• 每次tryConsume的时候，方法内部首先调用refill，根据设定的速度以及时间差计算这个时间段需要补充的token，更新availableTokens以及lastRefillTimestamp
• 之后限流判断，就是判断availableTokens与请求的numberTokens

## 小结

token bucket算法，是基于qps来限流，其简单的实现，就是计算单位时间补充token的速率，然后每次tryConsume的时候根据速率修正availableTokens。

## doc

• Brief overview of token-bucket algorithm

0 条评论

• ### leetcode之错误的集合

这里遍历一次数组，求出总和，并计算每个元素的count，同时找出重复的元素，之后根据自然数求和公式与现有总和的差值及重复的元素计算得出缺失的元素。

• ### leetcode之错误的集合

这里遍历一次数组，求出总和，并计算每个元素的count，同时找出重复的元素，之后根据自然数求和公式与现有总和的差值及重复的元素计算得出缺失的元素。

• ### [剑指offer] 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

• ### Android异步消息机制详解

Android中的异步消息机制分为四个部分：Message、Handler、MessageQueue和Looper。

• ### 详解 mysql int 类型的长度值问题

创建数据库的时候发现一个问题: 改变 length 的值, 不能影响到实际的存储长度! 秉着好奇心, 打开了 google ~ 引入大神的解答.

• ### OEA 中的多国语言实现

本篇博客主要描述在 OEA 框架中的多国语言框架的原理及应用。 多国语言常见实现及原理分析     管理软件平台，一般来说，都应该支持多国语言，以支持应...

• ### H3C配置常用命令

超级用户终端登陆交换机 SYS进入                              //sys进入系统视图 输入以下命令 #  sysname...