Java限流之令牌桶算法、漏桶算法

限流在实际使用场景中应用十分广泛,尤其针对并发场景下的高并发,为了保证系统的可用性,我们需要采取一些限流措施降级,以防止非预期的请求对系统压力过大而引起的系统瘫痪。

对于过量的请求一般的措施就是丢掉多余的请求,或者让请求排队,再或者引流

下面说下常用的限流方式:

1.计数器方法

比如在1分钟内限制请求次数不超过100,那我们定义一个变量counter,每来一个请求则counter加1,如果在一分钟之内counter累计超过100,新来的请求则超过限制。然后,超过1s之后,这个counter就重置。这是比较简单的计数器法;

但是这种方法会有一个问题,那就是比如某个人在0:59秒的时候打了100个请求过来,然后,在1min的时候counter就置零了,他又在1:01的时候打了100个请求过来,所以说,在最近的1min之内其实是接收到200个请求,这明显超出了我们的预期,所以说这种方法不满足我们的需求。

聪明的小伙伴一眼就能看出问题所在,其实是我们统计的精度太低了,于是就引出下面的滑动窗口计数法;

2.滑动窗口

比如我们把1min划分成6个小格,则每10s为一个分割单位,比如在0:35分钟来了100个请求,则会落在0:30-0:39这个区间内,当1:01再来100个请求时,显然,最近1分钟内的请求次数超过了100,那么这100个请求则被限制住了,这种是符合我们的预期。但是滑动窗口对存储有比较大的需求,尤其在窗口比较小的情况下不满足需求。

3.漏桶算法

漏桶算法的思路就是,水(请求)先进入漏桶里,漏桶以一定的速度出水(接口响应时间),当水流入速度(接口请求的速度)越来越大时,漏桶就会溢出,然后新来的请求就会被拒绝。无论请求量多大,漏洞的出水速率是不变的,所以针对突发的大流量场景,这种方案是不支持的。

漏洞算法示意图

4.令牌桶算法

令牌桶算法是我们日常使用比较多的方案,它的基本方案是:系统以恒定速率向桶里放入令牌,,如果桶满了则不加。当请求来的时候,从桶里拿走一个令牌,如果桶里没有令牌则阻塞或者拒绝新的请求。令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 

可以参考RateLimiter类来进行实际应用。


令牌桶算法示意图
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,616评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,020评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,078评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,040评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,154评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,265评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,298评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,072评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,491评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,795评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,970评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,654评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,272评论 3 318
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,985评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,815评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,852评论 2 351

推荐阅读更多精彩内容

  • 夜莺2517阅读 127,717评论 1 9
  • 我是黑夜里大雨纷飞的人啊 1 “又到一年六月,有人笑有人哭,有人欢乐有人忧愁,有人惊喜有人失落,有的觉得收获满满有...
    陌忘宇阅读 8,532评论 28 53
  • 兔子虽然是枚小硕 但学校的硕士四人寝不够 就被分到了博士楼里 两人一间 在学校的最西边 靠山 兔子的室友身体不好 ...
    待业的兔子阅读 2,596评论 2 9
  • 信任包括信任自己和信任他人 很多时候,很多事情,失败、遗憾、错过,源于不自信,不信任他人 觉得自己做不成,别人做不...
    吴氵晃阅读 6,187评论 4 8