聊聊leaky bucket算法的实现

本文主要研究一下leaky bucket算法的实现

leaky bucket算法

  • bucket以一定速率滴水,相当于增加桶容量
  • bucket有其容量限制,请求过来时bucket满,则直接被抛弃
  • 请求到来时,如果bucket不满,则放入bucket,相当于放行

简单实现

public class LeakyBucket {

    private final long capacity;
    private final long leaksIntervalInMillis;

    private double used;
    private long lastLeakTimestamp;

    public LeakyBucket(long capacity, long leaksIntervalInMillis) {
        this.capacity = capacity;
        this.leaksIntervalInMillis = leaksIntervalInMillis;

        this.used = 0;
        this.lastLeakTimestamp = System.currentTimeMillis();
    }

    synchronized public boolean tryConsume(int drop) {
        leak();

        if (used + drop > capacity) {
           return false;
        }

        used = used + drop;
        return true;
    }

    private void leak() {
        long currentTimeMillis = System.currentTimeMillis();
        if (currentTimeMillis > lastLeakTimestamp) {
            long millisSinceLastLeak = currentTimeMillis - lastLeakTimestamp;
            long leaks = millisSinceLastLeak / leaksIntervalInMillis;
            if(leaks > 0){
                if(used <= leaks){
                    used = 0;
                }else{
                    used -= (int)leaks;
                }
                this.lastLeakTimestamp = currentTimeMillis;
            }
        }
    }
}
  • 这个实现设计了lastLeakTimestamp字段,用于计算时间差,以及在这个时间段内需要漏水的数量
  • 每次tryConsume的时候,方法内部首先调用leak,根据设定的速度以及时间差计算这个时间段需要漏水的数量,更新桶的当前使用量以及lastLeakTimestamp
  • 之后限流判断,就是判断used与请求的drop是否会超过桶容量,超出则限流,否则放入桶中,更新桶容量

小结

  • leaky bucket与token bucket算法相反,前者是漏水,后者是添加token
  • leaky bucket由于是漏水算法,所以不能像token bucket添加token那种可以累积,因此leaky bucket不能支持burst突发流量

doc

  • Leaky Bucket Algorithm
  • Leaky bucket algorithm for flow control
  • Computer Network | Leaky bucket algorithm

原文发布于微信公众号 - 码匠的流水账(geek_luandun)

原文发表时间:2018-08-30

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 "二分查找(Binary Search

43311
来自专栏小樱的经验随笔

Codeforces 626F Group Projects(滚动数组+差分dp)

F. Group Projects time limit per test:2 seconds memory limit per test:256 megaby...

3547
来自专栏章鱼的慢慢技术路

OpenGL中的二维编程——从简单的矩形开始

1954
来自专栏机器之心

业界 | 谷歌开源DeepLearn.js:可实现硬件加速的机器学习JavaScript库

选自GitHub 机器之心编译 参与:蒋思源、路雪 deeplearn.js 是一个可用于机器智能并加速 WebGL 的开源 JavaScript 库。de...

3858
来自专栏calmound

HDU 1536 S-Nim

师时隔几个月后,在看博弈NIM终于懂了,做出了第一道根据所有堆的异或和的题 题意:在一个Si容器中,输入可以行走的步数,然后在下面T组测试数据中,输入堆的情况 ...

3646
来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

973
来自专栏用户2442861的专栏

阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

1462
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

1052
来自专栏Crossin的编程教室

【每周一坑】矩阵旋转

每N周一坑(N>=1)又来啦!之前我们玩过一次矩阵【每周一坑】螺旋矩阵,今天继续来做矩阵相关的操作: 题目说明 给定一个 N * N 的矩阵(N >= 0),将...

3617
来自专栏AI科技大本营的专栏

入门 | 海量数据处理算法总结【超详解】

作者 | Angel_Kitty ➤1. Bloom Filter 【Bloom Filter】 Bloom Filter(BF)是一种空间效率很高的随机数据...

4399

扫码关注云+社区

领取腾讯云代金券