专栏首页码匠的流水账聊聊token bucket算法的实现

聊聊token bucket算法的实现

本文主要研究一下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

本文分享自微信公众号 - 码匠的流水账(geek_luandun),作者:码匠乱炖

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聊聊leaky bucket算法的实现

    codecraft
  • leetcode之错误的集合

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

    codecraft
  • leetcode之错误的集合

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

    codecraft
  • 聊聊leaky bucket算法的实现

    codecraft
  • [剑指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 ~ 引入大神的解答.

    程序员养成日记
  • java之学习Arrays类的方法的应用

    吾爱乐享
  • OEA 中的多国语言实现

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

    用户1172223
  • H3C配置常用命令

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

    py3study

扫码关注云+社区

领取腾讯云代金券