欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)5種限流算法及7種限流方式

 更新時(shí)間:2022年08月02日 10:02:00   作者:程序猿阿朗  
本文主要介紹了Java實(shí)現(xiàn)5種限流算法及7種限流方式,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

最近幾年,隨著微服務(wù)的流行,服務(wù)和服務(wù)之間的依賴越來越強(qiáng),調(diào)用關(guān)系越來越復(fù)雜,服務(wù)和服務(wù)之間的穩(wěn)定性越來越重要。在遇到突發(fā)的請(qǐng)求量激增,惡意的用戶訪問,亦或請(qǐng)求頻率過高給下游服務(wù)帶來較大壓力時(shí),我們常常需要通過緩存、限流、熔斷降級(jí)、負(fù)載均衡等多種方式保證服務(wù)的穩(wěn)定性。其中限流是不可或缺的一環(huán),這篇文章介紹限流相關(guān)知識(shí)。

1. 限流

限流顧名思義,就是對(duì)請(qǐng)求或并發(fā)數(shù)進(jìn)行限制;通過對(duì)一個(gè)時(shí)間窗口內(nèi)的請(qǐng)求量進(jìn)行限制來保障系統(tǒng)的正常運(yùn)行。如果我們的服務(wù)資源有限、處理能力有限,就需要對(duì)調(diào)用我們服務(wù)的上游請(qǐng)求進(jìn)行限制,以防止自身服務(wù)由于資源耗盡而停止服務(wù)。

在限流中有兩個(gè)概念需要了解。

  • 閾值:在一個(gè)單位時(shí)間內(nèi)允許的請(qǐng)求量。如 QPS 限制為10,說明 1 秒內(nèi)最多接受 10 次請(qǐng)求。
  • 拒絕策略:超過閾值的請(qǐng)求的拒絕策略,常見的拒絕策略有直接拒絕、排隊(duì)等待等。

2. 固定窗口算法

固定窗口算法又叫計(jì)數(shù)器算法,是一種簡(jiǎn)單方便的限流算法。主要通過一個(gè)支持原子操作的計(jì)數(shù)器來累計(jì) 1 秒內(nèi)的請(qǐng)求次數(shù),當(dāng) 1 秒內(nèi)計(jì)數(shù)達(dá)到限流閾值時(shí)觸發(fā)拒絕策略。每過 1 秒,計(jì)數(shù)器重置為 0 開始重新計(jì)數(shù)。

2.1. 代碼實(shí)現(xiàn)

下面是簡(jiǎn)單的代碼實(shí)現(xiàn),QPS 限制為 2,這里的代碼做了一些優(yōu)化,并沒有單獨(dú)開一個(gè)線程去每隔 1 秒重置計(jì)數(shù)器,而是在每次調(diào)用時(shí)進(jìn)行時(shí)間間隔計(jì)算來確定是否先重置計(jì)數(shù)器。

/**
 * @author https://www.wdbyte.com
 */
public class RateLimiterSimpleWindow {
    // 閾值
    private static Integer QPS = 2;
    // 時(shí)間窗口(毫秒)
    private static long TIME_WINDOWS = 1000;
    // 計(jì)數(shù)器
    private static AtomicInteger REQ_COUNT = new AtomicInteger();
    
    private static long START_TIME = System.currentTimeMillis();
 
    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            REQ_COUNT.set(0);
            START_TIME = System.currentTimeMillis();
        }
        return REQ_COUNT.incrementAndGet() <= QPS;
    }
 
    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 被限流");
            } else {
                System.out.println(now + " 做點(diǎn)什么");
            }
        }
    }
}

運(yùn)行結(jié)果:

20:53:43.038922 做點(diǎn)什么
20:53:43.291435 做點(diǎn)什么
20:53:43.543087 被限流
20:53:43.796666 做點(diǎn)什么
20:53:44.050855 做點(diǎn)什么
20:53:44.303547 被限流
20:53:44.555008 被限流
20:53:44.809083 做點(diǎn)什么
20:53:45.063828 做點(diǎn)什么
20:53:45.314433 被限流

從輸出結(jié)果中可以看到大概每秒操作 3 次,由于限制 QPS 為 2,所以平均會(huì)有一次被限流??雌饋砜梢粤?,不過我們思考一下就會(huì)發(fā)現(xiàn)這種簡(jiǎn)單的限流方式是有問題的,雖然我們限制了 QPS 為 2,但是當(dāng)遇到時(shí)間窗口的臨界突變時(shí),如 1s 中的后 500 ms 和第 2s 的前 500ms 時(shí),雖然是加起來是 1s 時(shí)間,卻可以被請(qǐng)求 4 次。

固定窗口算法

簡(jiǎn)單修改測(cè)試代碼,可以進(jìn)行驗(yàn)證:

// 先休眠 400ms,可以更快的到達(dá)時(shí)間窗口。
Thread.sleep(400);
for (int i = 0; i < 10; i++) {
    Thread.sleep(250);
    if (!tryAcquire()) {
        System.out.println("被限流");
    } else {
        System.out.println("做點(diǎn)什么");
    }
}

得到輸出中可以看到連續(xù) 4 次請(qǐng)求,間隔 250 ms 沒有卻被限制。:

20:51:17.395087 做點(diǎn)什么
20:51:17.653114 做點(diǎn)什么
20:51:17.903543 做點(diǎn)什么
20:51:18.154104 被限流
20:51:18.405497 做點(diǎn)什么
20:51:18.655885 做點(diǎn)什么
20:51:18.906177 做點(diǎn)什么
20:51:19.158113 被限流
20:51:19.410512 做點(diǎn)什么
20:51:19.661629 做點(diǎn)什么

3. 滑動(dòng)窗口算法

我們已經(jīng)知道固定窗口算法的實(shí)現(xiàn)方式以及它所存在的問題,而滑動(dòng)窗口算法是對(duì)固定窗口算法的改進(jìn)。既然固定窗口算法在遇到時(shí)間窗口的臨界突變時(shí)會(huì)有問題,那么我們?cè)谟龅较乱粋€(gè)時(shí)間窗口前也調(diào)整時(shí)間窗口不就可以了嗎?

下面是滑動(dòng)窗口的示意圖。

滑動(dòng)窗口算法

上圖的示例中,每 500ms 滑動(dòng)一次窗口,可以發(fā)現(xiàn)窗口滑動(dòng)的間隔越短,時(shí)間窗口的臨界突變問題發(fā)生的概率也就越小,不過只要有時(shí)間窗口的存在,還是有可能發(fā)生時(shí)間窗口的臨界突變問題。

3.1. 代碼實(shí)現(xiàn)

下面是基于以上滑動(dòng)窗口思路實(shí)現(xiàn)的簡(jiǎn)單的滑動(dòng)窗口限流工具類。

package com.wdbyte.rate.limiter;
 
import java.time.LocalTime;
import java.util.concurrent.atomic.AtomicInteger;
 
/**
 * 滑動(dòng)窗口限流工具類
 *
 * @author https://www.wdbyte.com
 */
public class RateLimiterSlidingWindow {
    /**
     * 閾值
     */
    private int qps = 2;
    /**
     * 時(shí)間窗口總大小(毫秒)
     */
    private long windowSize = 1000;
    /**
     * 多少個(gè)子窗口
     */
    private Integer windowCount = 10;
    /**
     * 窗口列表
     */
    private WindowInfo[] windowArray = new WindowInfo[windowCount];
 
    public RateLimiterSlidingWindow(int qps) {
        this.qps = qps;
        long currentTimeMillis = System.currentTimeMillis();
        for (int i = 0; i < windowArray.length; i++) {
            windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
        }
    }
 
    /**
     * 1. 計(jì)算當(dāng)前時(shí)間窗口
     * 2. 更新當(dāng)前窗口計(jì)數(shù) & 重置過期窗口計(jì)數(shù)
     * 3. 當(dāng)前 QPS 是否超過限制
     *
     * @return
     */
    public synchronized boolean tryAcquire() {
        long currentTimeMillis = System.currentTimeMillis();
        // 1. 計(jì)算當(dāng)前時(shí)間窗口
        int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
        // 2.  更新當(dāng)前窗口計(jì)數(shù) & 重置過期窗口計(jì)數(shù)
        int sum = 0;
        for (int i = 0; i < windowArray.length; i++) {
            WindowInfo windowInfo = windowArray[i];
            if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
                windowInfo.getNumber().set(0);
                windowInfo.setTime(currentTimeMillis);
            }
            if (currentIndex == i && windowInfo.getNumber().get() < qps) {
                windowInfo.getNumber().incrementAndGet();
            }
            sum = sum + windowInfo.getNumber().get();
        }
        // 3. 當(dāng)前 QPS 是否超過限制
        return sum <= qps;
    }
 
    private class WindowInfo {
        // 窗口開始時(shí)間
        private Long time;
        // 計(jì)數(shù)器
        private AtomicInteger number;
 
        public WindowInfo(long time, AtomicInteger number) {
            this.time = time;
            this.number = number;
        }
        // get...set...
    }
}

下面是測(cè)試用例,設(shè)置 QPS 為 2,測(cè)試次數(shù) 20 次,每次間隔 300 毫秒,預(yù)計(jì)成功次數(shù)在 12 次左右。

public static void main(String[] args) throws InterruptedException {
    int qps = 2, count = 20, sleep = 300, success = count * sleep / 1000 * qps;
    System.out.println(String.format("當(dāng)前QPS限制為:%d,當(dāng)前測(cè)試次數(shù):%d,間隔:%dms,預(yù)計(jì)成功次數(shù):%d", qps, count, sleep, success));
    success = 0;
    RateLimiterSlidingWindow myRateLimiter = new RateLimiterSlidingWindow(qps);
    for (int i = 0; i < count; i++) {
        Thread.sleep(sleep);
        if (myRateLimiter.tryAcquire()) {
            success++;
            if (success % qps == 0) {
                System.out.println(LocalTime.now() + ": success, ");
            } else {
                System.out.print(LocalTime.now() + ": success, ");
            }
        } else {
            System.out.println(LocalTime.now() + ": fail");
        }
    }
    System.out.println();
    System.out.println("實(shí)際測(cè)試成功次數(shù):" + success);
}

下面是測(cè)試的結(jié)果。

當(dāng)前QPS限制為:2,當(dāng)前測(cè)試次數(shù):20,間隔:300ms,預(yù)計(jì)成功次數(shù):12
16:04:27.077782: success, 16:04:27.380715: success, 
16:04:27.684244: fail
16:04:27.989579: success, 16:04:28.293347: success, 
16:04:28.597658: fail
16:04:28.901688: fail
16:04:29.205262: success, 16:04:29.507117: success, 
16:04:29.812188: fail
16:04:30.115316: fail
16:04:30.420596: success, 16:04:30.725897: success, 
16:04:31.028599: fail
16:04:31.331047: fail
16:04:31.634127: success, 16:04:31.939411: success, 
16:04:32.242380: fail
16:04:32.547626: fail
16:04:32.847965: success, 
實(shí)際測(cè)試成功次數(shù):11

4. 滑動(dòng)日志算法

滑動(dòng)日志算法是實(shí)現(xiàn)限流的另一種方法,這種方法比較簡(jiǎn)單?;具壿嬀褪怯涗浵滤械恼?qǐng)求時(shí)間點(diǎn),新請(qǐng)求到來時(shí)先判斷最近指定時(shí)間范圍內(nèi)的請(qǐng)求數(shù)量是否超過指定閾值,由此來確定是否達(dá)到限流,這種方式?jīng)]有了時(shí)間窗口突變的問題,限流比較準(zhǔn)確,但是因?yàn)橐涗浵旅看握?qǐng)求的時(shí)間點(diǎn),所以占用的內(nèi)存較多。

4.1. 代碼實(shí)現(xiàn)

下面是簡(jiǎn)單實(shí)現(xiàn)的 一個(gè)滑動(dòng)日志算法,因?yàn)榛瑒?dòng)日志要每次請(qǐng)求單獨(dú)存儲(chǔ)一條記錄,可能占用內(nèi)存過多。所以下面這個(gè)實(shí)現(xiàn)其實(shí)不算嚴(yán)謹(jǐn)?shù)幕瑒?dòng)日志,更像一個(gè)把 1 秒時(shí)間切分成 1000 個(gè)時(shí)間窗口的滑動(dòng)窗口算法。

package com.wdbyte.rate.limiter;
 
import java.time.LocalTime;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;
 
/**
 * 滑動(dòng)日志方式限流
 * 設(shè)置 QPS 為 2.
 *
 * @author https://www.wdbyte.com
 */
public class RateLimiterSildingLog {
 
    /**
     * 閾值
     */
    private Integer qps = 2;
    /**
     * 記錄請(qǐng)求的時(shí)間戳,和數(shù)量
     */
    private TreeMap<Long, Long> treeMap = new TreeMap<>();
 
    /**
     * 清理請(qǐng)求記錄間隔, 60 秒
     */
    private long claerTime = 60 * 1000;
 
    public RateLimiterSildingLog(Integer qps) {
        this.qps = qps;
    }
 
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 清理過期的數(shù)據(jù)老數(shù)據(jù),最長(zhǎng) 60 秒清理一次
        if (!treeMap.isEmpty() && (treeMap.firstKey() - now) > claerTime) {
            Set<Long> keySet = new HashSet<>(treeMap.subMap(0L, now - 1000).keySet());
            for (Long key : keySet) {
                treeMap.remove(key);
            }
        }
        // 計(jì)算當(dāng)前請(qǐng)求次數(shù)
        int sum = 0;
        for (Long value : treeMap.subMap(now - 1000, now).values()) {
            sum += value;
        }
        // 超過QPS限制,直接返回 false
        if (sum + 1 > qps) {
            return false;
        }
        // 記錄本次請(qǐng)求
        if (treeMap.containsKey(now)) {
            treeMap.compute(now, (k, v) -> v + 1);
        } else {
            treeMap.put(now, 1L);
        }
        return sum <= qps;
    }
 
    public static void main(String[] args) throws InterruptedException {
        RateLimiterSildingLog rateLimiterSildingLog = new RateLimiterSildingLog(3);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (rateLimiterSildingLog.tryAcquire()) {
                System.out.println(now + " 做點(diǎn)什么");
            } else {
                System.out.println(now + " 被限流");
            }
        }
    }
}

代碼中把閾值 QPS 設(shè)定為 3,運(yùn)行可以得到如下日志:

20:51:17.395087 做點(diǎn)什么
20:51:17.653114 做點(diǎn)什么
20:51:17.903543 做點(diǎn)什么
20:51:18.154104 被限流
20:51:18.405497 做點(diǎn)什么
20:51:18.655885 做點(diǎn)什么
20:51:18.906177 做點(diǎn)什么
20:51:19.158113 被限流
20:51:19.410512 做點(diǎn)什么
20:51:19.661629 做點(diǎn)什么

5. 漏桶算法

漏桶算法中的漏桶是一個(gè)形象的比喻,這里可以用生產(chǎn)者消費(fèi)者模式進(jìn)行說明,請(qǐng)求是一個(gè)生產(chǎn)者,每一個(gè)請(qǐng)求都如一滴水,請(qǐng)求到來后放到一個(gè)隊(duì)列(漏桶)中,而桶底有一個(gè)孔,不斷的漏出水滴,就如消費(fèi)者不斷的在消費(fèi)隊(duì)列中的內(nèi)容,消費(fèi)的速率(漏出的速度)等于限流閾值。即假如 QPS  為 2,則每 1s / 2= 500ms 消費(fèi)一次。漏桶的桶有大小,就如隊(duì)列的容量,當(dāng)請(qǐng)求堆積超過指定容量時(shí),會(huì)觸發(fā)拒絕策略。

下面是漏桶算法的示意圖。

漏桶算法

由介紹可以知道,漏桶模式中的消費(fèi)處理總是能以恒定的速度進(jìn)行,可以很好的保護(hù)自身系統(tǒng)不被突如其來的流量沖垮;但是這也是漏桶模式的缺點(diǎn),假設(shè) QPS 為 2,同時(shí) 2 個(gè)請(qǐng)求進(jìn)來,2 個(gè)請(qǐng)求并不能同時(shí)進(jìn)行處理響應(yīng),因?yàn)槊?nbsp;1s / 2= 500ms 只能處理一個(gè)請(qǐng)求。

6. 令牌桶算法

令牌桶算法同樣是實(shí)現(xiàn)限流是一種常見的思路,最為常用的 Google 的 Java 開發(fā)工具包 Guava 中的限流工具類 RateLimiter 就是令牌桶的一個(gè)實(shí)現(xiàn)。令牌桶的實(shí)現(xiàn)思路類似于生產(chǎn)者和消費(fèi)之間的關(guān)系。

系統(tǒng)服務(wù)作為生產(chǎn)者,按照指定頻率向桶(容器)中添加令牌,如 QPS 為 2,每 500ms 向桶中添加一個(gè)令牌,如果桶中令牌數(shù)量達(dá)到閾值,則不再添加。

請(qǐng)求執(zhí)行作為消費(fèi)者,每個(gè)請(qǐng)求都需要去桶中拿取一個(gè)令牌,取到令牌則繼續(xù)執(zhí)行;如果桶中無令牌可取,就觸發(fā)拒絕策略,可以是超時(shí)等待,也可以是直接拒絕本次請(qǐng)求,由此達(dá)到限流目的。

下面是令牌桶限流算法示意圖。

令牌桶算法

思考令牌桶的實(shí)現(xiàn)可以以下特點(diǎn)。

  • 1s / 閾值(QPS)  = 令牌添加時(shí)間間隔。
  • 桶的容量等于限流的閾值,令牌數(shù)量達(dá)到閾值時(shí),不再添加。
  • 可以適應(yīng)流量突發(fā),N 個(gè)請(qǐng)求到來只需要從桶中獲取 N 個(gè)令牌就可以繼續(xù)處理。
  • 有啟動(dòng)過程,令牌桶啟動(dòng)時(shí)桶中無令牌,然后按照令牌添加時(shí)間間隔添加令牌,若啟動(dòng)時(shí)就有閾值數(shù)量的請(qǐng)求過來,會(huì)因?yàn)橥爸袥]有足夠的令牌而觸發(fā)拒絕策略,不過如 RateLimiter 限流工具已經(jīng)優(yōu)化了這類問題。

6.1. 代碼實(shí)現(xiàn)

Google 的 Java 開發(fā)工具包 Guava 中的限流工具類 RateLimiter 就是令牌桶的一個(gè)實(shí)現(xiàn),日常開發(fā)中我們也不會(huì)手動(dòng)實(shí)現(xiàn)了,這里直接使用 RateLimiter 進(jìn)行測(cè)試。

引入依賴:

<exclusion>
   <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
   <version>31.0.1-jre</version>
</exclusion>

RateLimiter 限流體驗(yàn):

// qps 2
RateLimiter rateLimiter = RateLimiter.create(2);
for (int i = 0; i < 10; i++) {
    String time = LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
    System.out.println(time + ":" + rateLimiter.tryAcquire());
    Thread.sleep(250);
}

代碼中限制 QPS 為 2,也就是每隔 500ms 生成一個(gè)令牌,但是程序每隔 250ms 獲取一次令牌,所以兩次獲取中只有一次會(huì)成功。

17:19:06.797557:true
17:19:07.061419:false
17:19:07.316283:true
17:19:07.566746:false
17:19:07.817035:true
17:19:08.072483:false
17:19:08.326347:true
17:19:08.577661:false
17:19:08.830252:true
17:19:09.085327:false

6.2. 思考

雖然演示了 Google Guava 工具包中的 RateLimiter 的實(shí)現(xiàn),但是我們需要思考一個(gè)問題,就是令牌的添加方式,如果按照指定間隔添加令牌,那么需要開一個(gè)線程去定時(shí)添加,如果有很多個(gè)接口很多個(gè) RateLimiter 實(shí)例,線程數(shù)會(huì)隨之增加,這顯然不是一個(gè)好的辦法。顯然 Google 也考慮到了這個(gè)問題,在 RateLimiter 中,是在每次令牌獲取時(shí)才進(jìn)行計(jì)算令牌是否足夠的。它通過存儲(chǔ)的下一個(gè)令牌生成的時(shí)間,和當(dāng)前獲取令牌的時(shí)間差,再結(jié)合閾值,去計(jì)算令牌是否足夠,同時(shí)再記錄下一個(gè)令牌的生成時(shí)間以便下一次調(diào)用。

下面是 Guava 中 RateLimiter 類的子類 SmoothRateLimiter 的 resync() 方法的代碼分析,可以看到其中的令牌計(jì)算邏輯。

void resync(long nowMicros) { // 當(dāng)前微秒時(shí)間
    // 當(dāng)前時(shí)間是否大于下一個(gè)令牌生成時(shí)間
    if (nowMicros > this.nextFreeTicketMicros) { 
       // 可生成的令牌數(shù) newPermits = (當(dāng)前時(shí)間 - 下一個(gè)令牌生成時(shí)間)/ 令牌生成時(shí)間間隔。
       // 如果 QPS 為2,這里的 coolDownIntervalMicros 就是 500000.0 微秒(500ms)
        double newPermits = (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
    // 更新令牌庫存 storedPermits。
       this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
    // 更新下一個(gè)令牌生成時(shí)間 nextFreeTicketMicros
       this.nextFreeTicketMicros = nowMicros;
    }
}

7. Redis 分布式限流

Redis 是一個(gè)開源的內(nèi)存數(shù)據(jù)庫,可以用來作為數(shù)據(jù)庫、緩存、消息中間件等。Redis 是單線程的,又在內(nèi)存中操作,所以速度極快,得益于 Redis 的各種特性,所以使用 Redis 實(shí)現(xiàn)一個(gè)限流工具是十分方便的。

下面的演示都基于Spring Boot 項(xiàng)目,并需要以下依賴。

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

配置 Redis 信息。

spring:
  redis:
    database: 0
    password: 
    port: 6379
    host: 127.0.0.1
    lettuce:
      shutdown-timeout: 100ms
      pool:
        min-idle: 5
        max-idle: 10
        max-active: 8
        max-wait: 1ms

7.1. 固定窗口限流

Redis 中的固定窗口限流是使用 incr 命令實(shí)現(xiàn)的,incr 命令通常用來自增計(jì)數(shù);如果我們使用時(shí)間戳信息作為 key,自然就可以統(tǒng)計(jì)每秒的請(qǐng)求量了,以此達(dá)到限流目的。

這里有兩點(diǎn)要注意。

  • 對(duì)于不存在的 key,第一次新增時(shí),value 始終為 1。
  • INCR 和 EXPIRE 命令操作應(yīng)該在一個(gè)原子操作中提交,以保證每個(gè) key 都正確設(shè)置了過期時(shí)間,不然會(huì)有 key 值無法自動(dòng)刪除而導(dǎo)致的內(nèi)存溢出。

由于 Redis 中實(shí)現(xiàn)事務(wù)的復(fù)雜性,所以這里直接只用 lua 腳本來實(shí)現(xiàn)原子操作。下面是 lua 腳本內(nèi)容。

local count = redis.call("incr",KEYS[1])
if count == 1 then
  redis.call('expire',KEYS[1],ARGV[2])
end
if count > tonumber(ARGV[1]) then
  return 0
end
return 1

下面是使用 Spring Boot 中 RedisTemplate 來實(shí)現(xiàn)的 lua 腳本調(diào)用測(cè)試代碼。

/**
 * @author https://www.wdbyte.com
 */
@SpringBootTest
class RedisLuaLimiterByIncr {
    private static String KEY_PREFIX = "limiter_";
    private static String QPS = "4";
    private static String EXPIRE_TIME = "1";
 
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
 
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
 
    /**
     * 計(jì)數(shù)器限流
     *
     * @param key
     * @return
     */
    public boolean acquire(String key) {
        // 當(dāng)前秒數(shù)作為 key
        key = KEY_PREFIX + key + System.currentTimeMillis() / 1000;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目錄下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), QPS, EXPIRE_TIME) == 1;
    }
}

代碼中雖然限制了 QPS 為 4,但是因?yàn)檫@種限流實(shí)現(xiàn)是把毫秒時(shí)間戳作為 key 的,所以會(huì)有臨界窗口突變的問題,下面是運(yùn)行結(jié)果,可以看到因?yàn)闀r(shí)間窗口的變化,導(dǎo)致了 QPS 超過了限制值 4。

17:38:23.122044 true
17:38:23.695124 true
17:38:23.903220 true
# 此處有時(shí)間窗口變化,所以下面繼續(xù) true
17:38:24.106206 true
17:38:24.313458 true
17:38:24.519431 true
17:38:24.724446 true
17:38:24.932387 false
17:38:25.137912 true
17:38:25.355595 true
17:38:25.558219 true
17:38:25.765801 true
17:38:25.969426 false
17:38:26.176220 true
17:38:26.381918 true

7.3. 滑動(dòng)窗口限流

通過對(duì)上面的基于 incr 命令實(shí)現(xiàn)的 Redis 限流方式的測(cè)試,我們已經(jīng)發(fā)現(xiàn)了固定窗口限流所帶來的問題,在這篇文章的第三部分已經(jīng)介紹了滑動(dòng)窗口限流的優(yōu)勢(shì),它可以大幅度降低因?yàn)榇翱谂R界突變帶來的問題,那么如何使用 Redis 來實(shí)現(xiàn)滑動(dòng)窗口限流呢?

這里主要使用 ZSET 有序集合來實(shí)現(xiàn)滑動(dòng)窗口限流,ZSET 集合有下面幾個(gè)特點(diǎn):

  • ZSET 集合中的  key 值可以自動(dòng)排序。
  • ZSET 集合中的 value 不能有重復(fù)值。
  • ZSET 集合可以方便的使用 ZCARD 命令獲取元素個(gè)數(shù)。
  • ZSET 集合可以方便的使用 ZREMRANGEBYLEX 命令移除指定范圍的 key 值。

基于上面的四點(diǎn)特性,可以編寫出基于 ZSET 的滑動(dòng)窗口限流 lua 腳本。

--KEYS[1]: 限流 key
--ARGV[1]: 時(shí)間戳 - 時(shí)間窗口
--ARGV[2]: 當(dāng)前時(shí)間戳(作為score)
--ARGV[3]: 閾值
--ARGV[4]: score 對(duì)應(yīng)的唯一value
-- 1. 移除時(shí)間窗口之前的數(shù)據(jù)
redis.call('zremrangeByScore', KEYS[1], 0, ARGV[1])
-- 2. 統(tǒng)計(jì)當(dāng)前元素?cái)?shù)量
local res = redis.call('zcard', KEYS[1])
-- 3. 是否超過閾值
if (res == nil) or (res < tonumber(ARGV[3])) then
    redis.call('zadd', KEYS[1], ARGV[2], ARGV[4])
    return 1
else
    return 0
end

下面是使用 Spring Boot 中 RedisTemplate 來實(shí)現(xiàn)的 lua 腳本調(diào)用測(cè)試代碼。

@SpringBootTest
class RedisLuaLimiterByZset {
 
    private String KEY_PREFIX = "limiter_";
    private String QPS = "4";
 
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
 
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
 
    /**
     * 計(jì)數(shù)器限流
     *
     * @param key
     * @return
     */
    public boolean acquire(String key) {
        long now = System.currentTimeMillis();
        key = KEY_PREFIX + key;
        String oldest = String.valueOf(now - 1_000);
        String score = String.valueOf(now);
        String scoreValue = score;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目錄下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter2.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), oldest, score, QPS, scoreValue) == 1;
    }
}

代碼中限制 QPS 為 4,運(yùn)行結(jié)果信息與之一致。

17:36:37.150370 true
17:36:37.716341 true
17:36:37.922577 true
17:36:38.127497 true
17:36:38.335879 true
17:36:38.539225 false
17:36:38.745903 true
17:36:38.952491 true
17:36:39.159497 true
17:36:39.365239 true
17:36:39.570572 false
17:36:39.776635 true
17:36:39.982022 true
17:36:40.185614 true
17:36:40.389469 true

這里介紹了 Redis 實(shí)現(xiàn)限流的兩種方式,當(dāng)然使用 Redis 也可以實(shí)現(xiàn)漏桶和令牌桶兩種限流算法,這里就不做演示了,感興趣的可以自己研究下。

8. 總結(jié)

這篇文章介紹實(shí)現(xiàn)限流的幾種方式,主要是窗口算法和桶算法,兩者各有優(yōu)勢(shì)。

  • 窗口算法實(shí)現(xiàn)簡(jiǎn)單,邏輯清晰,可以很直觀的得到當(dāng)前的 QPS 情況,但是會(huì)有時(shí)間窗口的臨界突變問題,而且不像桶一樣有隊(duì)列可以緩沖。
  • 桶算法雖然稍微復(fù)雜,不好統(tǒng)計(jì) QPS 情況,但是桶算法也有優(yōu)勢(shì)所在。
    • 漏桶模式消費(fèi)速率恒定,可以很好的保護(hù)自身系統(tǒng),可以對(duì)流量進(jìn)行整形,但是面對(duì)突發(fā)流量不能快速響應(yīng)。
    • 令牌桶模式可以面對(duì)突發(fā)流量,但是啟動(dòng)時(shí)會(huì)有緩慢加速的過程,不過常見的開源工具中已經(jīng)對(duì)此優(yōu)化。

單機(jī)限流與分布式限流

上面演示的基于代碼形式的窗口算法和桶算法限流都適用于單機(jī)限流,如果需要分布式限流可以結(jié)合注冊(cè)中心、負(fù)載均衡計(jì)算每個(gè)服務(wù)的限流閾值,但這樣會(huì)降低一定精度,如果對(duì)精度要求不是太高,可以使用。

而 Redis 的限流,由于 Redis 的單機(jī)性,本身就可以用于分布式限流。使用 Redis 可以實(shí)現(xiàn)各種可以用于限流算法,如果覺得麻煩也可以使用開源工具如 redisson,已經(jīng)封裝了基于 Redis 的限流。

其他限流工具

文中已經(jīng)提到了 Guava 的限流工具包,不過它畢竟是單機(jī)的,開源社區(qū)中也有很多分布式限流工具,如阿里開源的 Sentinel 就是不錯(cuò)的工具,Sentinel 以流量為切入點(diǎn),從流量控制、熔斷降級(jí)、系統(tǒng)負(fù)載保護(hù)等多個(gè)維度保護(hù)服務(wù)的穩(wěn)定性。

一如既往,文章中的代碼存放在:github.com/niumoo/JavaNotes

參考

Redis INCR:https://redis.io/commands/incr

Rate Limiting Wikipedia:https://en.wikipedia.org/wiki/Rate_limiting

SpringBoot Redis:https://www.cnblogs.com/lenve/p/10965667.html

到此這篇關(guān)于Java實(shí)現(xiàn)5種限流算法及7種限流方式的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)限流算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論