最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

Java中4種經(jīng)典限流算法講解

 更新時(shí)間:2022年08月02日 10:13:48   作者:撿田螺的小男孩  
本文主要介紹了Java中4種經(jīng)典限流算法講解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

最近,我們的業(yè)務(wù)系統(tǒng)引入了Guava的RateLimiter限流組件,它是基于令牌桶算法實(shí)現(xiàn)的,而令牌桶是非常經(jīng)典的限流算法。本文將跟大家一起學(xué)習(xí)幾種經(jīng)典的限流算法。

限流是什么?

維基百科的概念如下:

In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks and limit web scraping

簡(jiǎn)單翻譯一下:在計(jì)算機(jī)網(wǎng)絡(luò)中,限流就是控制網(wǎng)絡(luò)接口發(fā)送或接收請(qǐng)求的速率,它可防止DoS攻擊和限制Web爬蟲(chóng)。

限流,也稱(chēng)流量控制。是指系統(tǒng)在面臨高并發(fā),或者大流量請(qǐng)求的情況下,限制新的請(qǐng)求對(duì)系統(tǒng)的訪問(wèn),從而保證系統(tǒng)的穩(wěn)定性。限流會(huì)導(dǎo)致部分用戶請(qǐng)求處理不及時(shí)或者被拒,這就影響了用戶體驗(yàn)。所以一般需要在系統(tǒng)穩(wěn)定和用戶體驗(yàn)之間平衡一下。舉個(gè)生活的例子:

一些熱門(mén)的旅游景區(qū),一般會(huì)對(duì)每日的旅游參觀人數(shù)有限制的。每天只會(huì)賣(mài)出固定數(shù)目的門(mén)票,比如5000張。假設(shè)在五一、國(guó)慶假期,你去晚了,可能當(dāng)天的票就已經(jīng)賣(mài)完了,就無(wú)法進(jìn)去游玩了。即使你進(jìn)去了,排隊(duì)也能排到你懷疑人生。

常見(jiàn)的限流算法

固定窗口限流算法

首先維護(hù)一個(gè)計(jì)數(shù)器,將單位時(shí)間段當(dāng)做一個(gè)窗口,計(jì)數(shù)器記錄這個(gè)窗口接收請(qǐng)求的次數(shù)。

  • 當(dāng)次數(shù)少于限流閥值,就允許訪問(wèn),并且計(jì)數(shù)器+1
  • 當(dāng)次數(shù)大于限流閥值,就拒絕訪問(wèn)。
  • 當(dāng)前的時(shí)間窗口過(guò)去之后,計(jì)數(shù)器清零。

假設(shè)單位時(shí)間是1秒,限流閥值為3。在單位時(shí)間1秒內(nèi),每來(lái)一個(gè)請(qǐng)求,計(jì)數(shù)器就加1,如果計(jì)數(shù)器累加的次數(shù)超過(guò)限流閥值3,后續(xù)的請(qǐng)求全部拒絕。等到1s結(jié)束后,計(jì)數(shù)器清0,重新開(kāi)始計(jì)數(shù)。如下圖:

偽代碼如下:

    /**
     * 固定窗口時(shí)間算法
     * @return
     */
    boolean fixedWindowsTryAcquire() {
        long currentTime = System.currentTimeMillis();  //獲取系統(tǒng)當(dāng)前時(shí)間
        if (currentTime - lastRequestTime > windowUnit) {  //檢查是否在時(shí)間窗口內(nèi)
            counter = 0;  // 計(jì)數(shù)器清0
            lastRequestTime = currentTime;  //開(kāi)啟新的時(shí)間窗口
        }
        if (counter < threshold) {  // 小于閥值
            counter++;  //計(jì)數(shù)器加1
            return true;
        }

        return false;
    }

但是,這種算法有一個(gè)很明顯的臨界問(wèn)題:假設(shè)限流閥值為5個(gè)請(qǐng)求,單位時(shí)間窗口是1s,如果我們?cè)趩挝粫r(shí)間內(nèi)的前0.8-1s和1-1.2s,分別并發(fā)5個(gè)請(qǐng)求。雖然都沒(méi)有超過(guò)閥值,但是如果算0.8-1.2s,則并發(fā)數(shù)高達(dá)10,已經(jīng)超過(guò)單位時(shí)間1s不超過(guò)5閥值的定義啦。

滑動(dòng)窗口限流算法

滑動(dòng)窗口限流解決固定窗口臨界值的問(wèn)題。它將單位時(shí)間周期分為n個(gè)小周期,分別記錄每個(gè)小周期內(nèi)接口的訪問(wèn)次數(shù),并且根據(jù)時(shí)間滑動(dòng)刪除過(guò)期的小周期。

一張圖解釋滑動(dòng)窗口算法,如下:

假設(shè)單位時(shí)間還是1s,滑動(dòng)窗口算法把它劃分為5個(gè)小周期,也就是滑動(dòng)窗口(單位時(shí)間)被劃分為5個(gè)小格子。每格表示0.2s。每過(guò)0.2s,時(shí)間窗口就會(huì)往右滑動(dòng)一格。然后呢,每個(gè)小周期,都有自己獨(dú)立的計(jì)數(shù)器,如果請(qǐng)求是0.83s到達(dá)的,0.8~1.0s對(duì)應(yīng)的計(jì)數(shù)器就會(huì)加1。

我們來(lái)看下滑動(dòng)窗口是如何解決臨界問(wèn)題的?

假設(shè)我們1s內(nèi)的限流閥值還是5個(gè)請(qǐng)求,0.8~1.0s內(nèi)(比如0.9s的時(shí)候)來(lái)了5個(gè)請(qǐng)求,落在黃色格子里。時(shí)間過(guò)了1.0s這個(gè)點(diǎn)之后,又來(lái)5個(gè)請(qǐng)求,落在紫色格子里。如果是固定窗口算法,是不會(huì)被限流的,但是滑動(dòng)窗口的話,每過(guò)一個(gè)小周期,它會(huì)右移一個(gè)小格。過(guò)了1.0s這個(gè)點(diǎn)后,會(huì)右移一小格,當(dāng)前的單位時(shí)間段是0.2~1.2s,這個(gè)區(qū)域的請(qǐng)求已經(jīng)超過(guò)限定的5了,已觸發(fā)限流啦,實(shí)際上,紫色格子的請(qǐng)求都被拒絕啦。

TIPS: 當(dāng)滑動(dòng)窗口的格子周期劃分的越多,那么滑動(dòng)窗口的滾動(dòng)就越平滑,限流的統(tǒng)計(jì)就會(huì)越精確。

滑動(dòng)窗口算法偽代碼實(shí)現(xiàn)如下:

 /**
     * 單位時(shí)間劃分的小周期(單位時(shí)間是1分鐘,10s一個(gè)小格子窗口,一共6個(gè)格子)
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分鐘限流請(qǐng)求數(shù)
     */
    private int thresholdPerMin = 100;

    /**
     * 計(jì)數(shù)器, k-為當(dāng)前窗口的開(kāi)始時(shí)間值秒,value為當(dāng)前窗口的計(jì)數(shù)
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

   /**
     * 滑動(dòng)窗口時(shí)間算法實(shí)現(xiàn)
     */
    boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //獲取當(dāng)前時(shí)間在哪個(gè)小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //當(dāng)前窗口總請(qǐng)求數(shù)

        //超過(guò)閥值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //計(jì)數(shù)器+1
        counters.get(currentWindowTime)++;
        return true;
    }

   /**
    * 統(tǒng)計(jì)當(dāng)前窗口的請(qǐng)求數(shù)
    */
    private int countCurrentWindow(long currentWindowTime) {
        //計(jì)算窗口開(kāi)始位置
        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
        int count = 0;

        //遍歷存儲(chǔ)的計(jì)數(shù)器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 刪除無(wú)效過(guò)期的子窗口計(jì)數(shù)器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加當(dāng)前窗口的所有計(jì)數(shù)器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }

滑動(dòng)窗口算法雖然解決了固定窗口的臨界問(wèn)題,但是一旦到達(dá)限流后,請(qǐng)求都會(huì)直接暴力被拒絕。醬紫我們會(huì)損失一部分請(qǐng)求,這其實(shí)對(duì)于產(chǎn)品來(lái)說(shuō),并不太友好。

漏桶算法

漏桶算法面對(duì)限流,就更加的柔性,不存在直接的粗暴拒絕。

它的原理很簡(jiǎn)單,可以認(rèn)為就是注水漏水的過(guò)程。往漏桶中以任意速率流入水,以固定的速率流出水。當(dāng)水超過(guò)桶的容量時(shí),會(huì)被溢出,也就是被丟棄。因?yàn)橥叭萘渴遣蛔兊模WC了整體的速率。

  • 流入的水滴,可以看作是訪問(wèn)系統(tǒng)的請(qǐng)求,這個(gè)流入速率是不確定的。
  • 桶的容量一般表示系統(tǒng)所能處理的請(qǐng)求數(shù)。
  • 如果桶的容量滿了,就達(dá)到限流的閥值,就會(huì)丟棄水滴(拒絕請(qǐng)求)
  • 流出的水滴,是恒定過(guò)濾的,對(duì)應(yīng)服務(wù)按照固定的速率處理請(qǐng)求。

漏桶算法偽代碼實(shí)現(xiàn)如下:

 /**
     * 每秒處理數(shù)(出水率)
     */
    private long rate;

    /**
     *  當(dāng)前剩余水量
     */
    private long currentWater;

    /**
     * 最后刷新時(shí)間
     */
    private long refreshTime;

    /**
     * 桶容量
     */
    private long capacity;

    /**
     * 漏桶算法
     * @return
     */
    boolean leakybucketLimitTryAcquire() {
        long currentTime = System.currentTimeMillis();  //獲取系統(tǒng)當(dāng)前時(shí)間
        long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(當(dāng)前時(shí)間-上次刷新時(shí)間)* 出水率
        long currentWater = Math.max(0, currentWater - outWater); // 當(dāng)前水量 = 之前的桶內(nèi)水量-流出的水量
        refreshTime = currentTime; // 刷新時(shí)間

        // 當(dāng)前剩余水量還是小于桶的容量,則請(qǐng)求放行
        if (currentWater < capacity) {
            currentWater++;
            return true;
        }
        
        // 當(dāng)前剩余水量大于等于桶的容量,限流
        return false;
    }

在正常流量的時(shí)候,系統(tǒng)按照固定的速率處理請(qǐng)求,是我們想要的。但是面對(duì)突發(fā)流量的時(shí)候,漏桶算法還是循規(guī)蹈矩地處理請(qǐng)求,這就不是我們想看到的啦。流量變突發(fā)時(shí),我們肯定希望系統(tǒng)盡量快點(diǎn)處理請(qǐng)求,提升用戶體驗(yàn)嘛。

令牌桶算法

面對(duì)突發(fā)流量的時(shí)候,我們可以使用令牌桶算法限流。

令牌桶算法原理

  • 有一個(gè)令牌管理員,根據(jù)限流大小,定速往令牌桶里放令牌。
  • 如果令牌數(shù)量滿了,超過(guò)令牌桶容量的限制,那就丟棄。
  • 系統(tǒng)在接受到一個(gè)用戶請(qǐng)求時(shí),都會(huì)先去令牌桶要一個(gè)令牌。如果拿到令牌,那么就處理這個(gè)請(qǐng)求的業(yè)務(wù)邏輯;
  • 如果拿不到令牌,就直接拒絕這個(gè)請(qǐng)求。

漏桶算法偽代碼實(shí)現(xiàn)如下:

    /**
     * 每秒處理數(shù)(放入令牌數(shù)量)
     */
    private long putTokenRate;
    
    /**
     * 最后刷新時(shí)間
     */
    private long refreshTime;

    /**
     * 令牌桶容量
     */
    private long capacity;
    
    /**
     * 當(dāng)前桶內(nèi)令牌數(shù)
     */
    private long currentToken = 0L;

    /**
     * 漏桶算法
     * @return
     */
    boolean tokenBucketTryAcquire() {

        long currentTime = System.currentTimeMillis();  //獲取系統(tǒng)當(dāng)前時(shí)間
        long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(當(dāng)前時(shí)間-上次刷新時(shí)間)* 放入令牌的速率
        currentToken = Math.min(capacity, generateToken + currentToken); // 當(dāng)前令牌數(shù)量 = 之前的桶內(nèi)令牌數(shù)量+放入的令牌數(shù)量
        refreshTime = currentTime; // 刷新時(shí)間
        
        //桶里面還有令牌,請(qǐng)求正常處理
        if (currentToken > 0) {
            currentToken--; //令牌數(shù)量-1
            return true;
        }
        
        return false;
    }

如果令牌發(fā)放的策略正確,這個(gè)系統(tǒng)即不會(huì)被拖垮,也能提高機(jī)器的利用率。Guava的RateLimiter限流組件,就是基于令牌桶算法實(shí)現(xiàn)的。

到此這篇關(guān)于Java中4種經(jīng)典限流算法講解的文章就介紹到這了,更多相關(guān)Java 經(jīng)典限流算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java中synchronized正確使用方法解析

    Java中synchronized正確使用方法解析

    這篇文章主要介紹了Java中syncronized正確使用方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-09-09
  • 深入解析Java中volatile的底層原理

    深入解析Java中volatile的底層原理

    這篇文章主要介紹了深入解析Java中volatile的底層原理,volatile關(guān)鍵字用于保證變量的可見(jiàn)性和禁止指令重排序,即當(dāng)一個(gè)線程修改了volatile變量的值,其他線程能夠立即看到這個(gè)變量的最新值,而不是使用緩存中的舊值,需要的朋友可以參考下
    2023-07-07
  • Java虛擬機(jī)最多支持多少個(gè)線程的探討

    Java虛擬機(jī)最多支持多少個(gè)線程的探討

    這篇文章主要介紹了Java虛擬機(jī)最多支持多少個(gè)線程的問(wèn)題,從StackOverflow上摘錄而來(lái),需要的朋友可以參考下
    2014-04-04
  • 二進(jìn)制中1的個(gè)數(shù)

    二進(jìn)制中1的個(gè)數(shù)

    這篇文章介紹了二進(jìn)制中1的個(gè)數(shù),有需要的朋友可以參考一下
    2013-09-09
  • Java實(shí)現(xiàn)歸并排序的示例代碼

    Java實(shí)現(xiàn)歸并排序的示例代碼

    歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide?and?Conquer)的一個(gè)非常典型的應(yīng)用。本文將用Java實(shí)現(xiàn)這一排序,需要的可以參考一下
    2022-08-08
  • kafka添加安全驗(yàn)證配置方式

    kafka添加安全驗(yàn)證配置方式

    這篇文章主要介紹了kafka添加安全驗(yàn)證配置方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-10-10
  • SpringBoot實(shí)現(xiàn)自定義線程池的方法

    SpringBoot實(shí)現(xiàn)自定義線程池的方法

    這篇文章主要介紹了SpringBoot中的自定義線程池解析,實(shí)現(xiàn)自定義線程池重寫(xiě)spring默認(rèn)線程池的方式使用的時(shí)候,只需要加@Async注解就可以,不用去聲明線程池類(lèi),需要的朋友可以參考下
    2023-11-11
  • idea如何自動(dòng)添加版權(quán)許可證信息

    idea如何自動(dòng)添加版權(quán)許可證信息

    這篇文章主要介紹了idea如何自動(dòng)添加版權(quán)許可證信息問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-07-07
  • 詳解Java的Spring框架中bean的注入集合

    詳解Java的Spring框架中bean的注入集合

    這篇文章主要介紹了詳解Java的Spring框架中bean的注入集合,Spring是Java的SSH三大web開(kāi)發(fā)框架之一,需要的朋友可以參考下
    2015-12-12
  • 淺談Java中的interface應(yīng)用與面向接口編程

    淺談Java中的interface應(yīng)用與面向接口編程

    這篇文章主要介紹了淺談Java中的interface應(yīng)用與面向接口編程,Java的關(guān)鍵字interface應(yīng)用,一個(gè)接口,多個(gè)實(shí)現(xiàn)類(lèi),面向接口編程,把業(yè)務(wù)邏輯線提取出來(lái)作為接口,具體的業(yè)務(wù)實(shí)現(xiàn)通過(guò)該接口的實(shí)現(xiàn)類(lèi)來(lái)完成,需要的朋友可以參考下
    2023-10-10

最新評(píng)論

安多县| 乌审旗| 潜江市| 江津市| 尖扎县| 海安县| 休宁县| 固阳县| 南昌市| 静安区| 金乡县| 安塞县| 观塘区| 枣庄市| 青冈县| 开原市| 广灵县| 临潭县| 阿坝| 大庆市| 滕州市| 杭锦旗| 奎屯市| 和平县| 集贤县| 陕西省| 盐亭县| 龙江县| 丽江市| 瑞安市| 皮山县| 玛纳斯县| 高碑店市| 米泉市| 颍上县| 镇安县| 永寿县| 青川县| 嘉义县| 西安市| 静乐县|