<li id='0ymwn'></li>

<dd id='0ymwn'><tbody id='0ymwn'><td id='0ymwn'><optgroup id='0ymwn'><strong id='0ymwn'></strong></optgroup><address id='0ymwn'><ul id='0ymwn'></ul></address><big id='0ymwn'></big></td><table id='0ymwn'></table></tbody><pre id='0ymwn'></pre></dd><span id='0ymwn'><b id='0ymwn'></b></span>

<dfn id='0ymwn'><optgroup id='0ymwn'></optgroup></dfn><tfoot id='0ymwn'><bdo id='0ymwn'><div id='0ymwn'></div><i id='0ymwn'><dt id='0ymwn'></dt></i></bdo></tfoot>

<ul id='0ymwn'></ul>

<fieldset id='0ymwn'></fieldset>

• 引言

在高并發的系統中，為了保證系統的穩定運行，通常會對系統的訪問進行限制，這就是所謂的限流。限流可以有效地防止系統過載，保證系統的穩定性和可用性。在眾多的限流算法中，有幾種算法經常使用，如：。本文將重點介紹這固定窗口、滑動窗口、漏桶算法和令牌桶算法四種算法，并給出相關的Java代碼實現。

 

• 固定窗口（計算法）的原理

固定窗口（計算器法）的核心思想是將時間劃分為一系列的固定窗口，每個窗口內的流量進行計數，當流量超過設定的閾值時，就進行限流。這種方法的優點是實現簡單，易于理解和實現，但是缺點是對時間的粒度控制不夠精細，可能會出現流量突增的情況。

Java代碼實現

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.atomic.AtomicInteger;

 

public class FixedWindowRateLimiter {

    private final int maxQps; // 最大請求數

    private final ConcurrentHashMap<String, AtomicInteger> counters = new ConcurrentHashMap<>(); // 計數器

    private final long interval; // 時間窗口長度

 

    public FixedWindowRateLimiter(int maxQps, long interval) {

        this.maxQps = maxQps;

        this.interval = interval;

    }

 

    public boolean tryAcquire() {

        long currentTime = System.currentTimeMillis();

        for (String key : counters.keySet()) {

            AtomicInteger counter = counters.get(key);

            if (counter.get() == 0) {

                continue;

            }

            long windowStart = currentTime - interval;

            if (counter.get() > maxQps && currentTime - counter.getAndSet(0) >= windowStart) {

                return false;

            }

        }

        return true;

    }

}

 

三、滑動窗口算法的原理

滑動窗口算法的核心思想是將時間劃分為一系列的固定窗口，每個窗口內的流量進行計數，當流量超過設定的閾值時，就進行限流。與固定窗口算法不同，滑動窗口算法的窗口不是固定的，而是隨著時間的推進而不斷向前滑動。這樣，即使有一個短暫的瞬時大流量，也不會導致限流，只有當流量持續超過閾值一段時間后，才會觸發限流。

以下是滑動窗口算法的Java代碼實現：

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.atomic.AtomicInteger;

 

public class SlidingWindowRateLimiter {

    private final int maxQps; // 最大請求數

    private final long interval; // 時間窗口長度

    private final ConcurrentHashMap<String, AtomicInteger> counters = new ConcurrentHashMap<>(); // 計數器

 

    public SlidingWindowRateLimiter(int maxQps, long interval) {

        this.maxQps = maxQps;

        this.interval = interval;

    }

 

    public boolean tryAcquire() {

        long currentTime = System.currentTimeMillis();

        for (String key : counters.keySet()) {

            AtomicInteger counter = counters.get(key);

            if (counter.get() == 0) {

                continue;

            }

            long windowStart = currentTime - interval;

            if (counter.get() > maxQps && currentTime - counter.getAndSet(0) >= windowStart) {

                return false;

            }

        }

        return true;

    }

}

 

四、漏桶算法的原理

漏桶算法的名字來源于其工作原理。漏桶算法假設有一個固定容量的桶，系統的流量就像是水一樣流入桶中。如果桶滿了，那么多余的水就會溢出。漏桶算法就是通過控制桶的大小來限制流量，從而達到限流的目的。

漏桶算法的主要特點是：流量是均勻的，但速率是受限的。漏桶算法不會因為突發的流量而立即觸發限流，而是會平滑地處理流量，從而避免了瞬時的高流量對系統的沖擊。

以下是漏桶算法的Java代碼實現：

import java.util.concurrent.TimeUnit;

import com.google.common.util.concurrent.RateLimiter;

 

public class LeakyBucketRateLimiter {

    private final RateLimiter rateLimiter;

 

    public LeakyBucketRateLimiter(double permitsPerSecond) {

        this.rateLimiter = RateLimiter.create(permitsPerSecond);

    }

 

    public boolean tryAcquire() throws InterruptedException {

        return rateLimiter.tryAcquire(1, TimeUnit.SECONDS);

    }

}

   

在上述代碼中，我們使用了Google Guava庫中的RateLimiter類來實現漏桶算法。RateLimiter類提供了一個高效的令牌桶實現，可以用來限制對共享資源的訪問速率。

五、令牌桶算法的原理

令牌桶算法的名字來源于其工作原理。令牌桶算法假設有一個固定容量的桶，系統的流量就像是水一樣流入桶中。如果桶滿了，那么多余的水就會溢出。令牌桶算法就是通過控制桶的大小和生成令牌的速度來限制流量，從而達到限流的目的。

令牌桶算法的主要特點是：流量是均勻的，但速率是受限的。令牌桶算法會按照設定的速度生成令牌，當有請求需要處理時，會從桶中取出一個令牌。如果桶中沒有令牌，那么請求就會被阻塞或者拒絕。

以下是令牌桶算法的Java代碼實現：

import java.util.concurrent.TimeUnit;

import com.google.common.util.concurrent.RateLimiter;

 

public class TokenBucketRateLimiter {

    private final RateLimiter rateLimiter;

 

    public TokenBucketRateLimiter(double permitsPerSecond) {

        this.rateLimiter = RateLimiter.create(permitsPerSecond);

    }

 

    public boolean tryAcquire() throws InterruptedException {

        return rateLimiter.tryAcquire(1, TimeUnit.SECONDS);

    }

}

 

六、四種算法的優缺點分析

算法	優點	缺點	總結
固定窗口	實現簡單：固定窗口（計算器法）的實現非常簡單，只需要一個計數器和一個時間窗口就可以實現。 易于理解和實現：固定窗口（計算器法）的原理非常直觀，易于理解和實現。 資源消耗小：固定窗口（計算器法）只需要一個計數器和一個時間窗口，因此資源消耗非常小。	時間粒度控制不夠精細：固定窗口（計算器法）的時間粒度是固定的，如果流量突增，可能會導致限流的效果不佳。 無法應對瞬時高流量：固定窗口（計算器法）只能應對持續的高流量，對于瞬時的高流量，固定窗口（計算器法）無法做出有效的應對。 無法應對周期性的流量波動：固定窗口（計算器法）只能應對持續的高流量，對于周期性的流量波動，固定窗口（計算器法）也無法做出有效的應對。	是一種實現簡單，易于理解和實現的限流算法。但是，由于其時間粒度控制不夠精細，無法應對瞬時高流量和周期性的流量波動，因此在實際應用中需要根據具體的場景和需求來選擇適合的限流算法。
滑動窗口	靈活性好：滑動窗口算法的時間粒度是可變的，可以根據實際需求進行調整，因此具有很好的靈活性。 能夠應對瞬時高流量：滑動窗口算法只有在流量持續超過閾值一段時間后，才會觸發限流，因此能夠有效地應對瞬時高流量。 資源消耗小：滑動窗口算法只需要一個計數器和一個時間窗口，因此資源消耗非常小。	實現復雜：滑動窗口算法需要維護一個時間窗口和一個計數器，因此實現相對復雜。 存在假陽性：由于滑動窗口算法的時間粒度是可變的，因此在時間窗口的邊界處，可能會出現假陽性的情況。例如，當流量從閾值降到零后，再升到閾值的過程中，雖然流量沒有超過閾值，但是由于時間窗口已經移動，因此可能會被誤判為超過閾值。 存在假陰性：同樣，由于滑動窗口算法的時間粒度是可變的，因此在時間窗口的邊界處，也可能會出現假陰性的情況。例如，當流量持續超過閾值一段時間后，再降回閾值的過程中，雖然流量已經超過了閾值，但是由于時間窗口還沒有移動，因此可能會被誤判為沒有超過閾值。	總的來說，滑動窗口算法是一種靈活性好，能夠應對瞬時高流量的限流算法。但是，由于其實現復雜，存在假陽性和假陰性的情況，因此在實際應用中需要根據具體的場景和需求來選擇適合的限流算法。
漏桶算法	平滑處理流量：漏桶算法可以平滑地處理流量，避免了瞬時的高流量對系統的沖擊。 易于理解和實現：漏桶算法的原理簡單，易于理解和實現。 可以應對突發的流量：漏桶算法不會因為突發的流量而立即觸發限流，而是會平滑地處理流量。	不能精確控制：由于漏桶算法是通過控制桶的大小來限制流量，因此不能精確地控制流量。如果桶的大小設置得過大，可能會導致過多的流量通過；如果桶的大小設置得過小，可能會導致限流過于嚴格。 無法應對周期性的流量波動：漏桶算法只能平滑地處理流量，無法應對周期性的流量波動。如果系統的流量有周期性的波動，漏桶算法可能無法有效地進行限流。	漏桶算法是一種簡單、易于理解和實現的限流算法，可以有效地防止系統過載，保證系統的穩定性和可用性。但是，由于其不能精確地控制流量和無法應對周期性的流量波動，因此在實際應用中需要根據具體的場景和需求來選擇適合的限流算法。
令牌桶算法	平滑處理流量：令牌桶算法可以平滑地處理流量，避免了瞬時的高流量對系統的沖擊。 可以應對突發的流量：令牌桶算法會按照設定的速度生成令牌，因此可以應對突發的流量。 可以應對周期性的流量波動：令牌桶算法可以通過調整生成令牌的速度來應對周期性的流量波動。	需要合理設置桶的大小和生成令牌的速度：如果桶的大小設置得過大，可能會導致過多的流量通過；如果生成令牌的速度設置得過小，可能會導致限流過于嚴格。如果生成令牌的速度設置得過大，可能會導致過多的令牌在桶中積累，從而浪費資源。 無法精確控制：由于令牌桶算法是通過控制桶的大小和生成令牌的速度來限制流量，因此無法精確地控制流量。	總的來說，令牌桶算法是一種能夠平滑處理流量，可以應對突發的流量和周期性的流量波動的限流算法。但是，由于其需要合理設置桶的大小和生成令牌的速度，以及無法精確地控制流量，因此在實際應用中需要根據具體的場景和需求來選擇適合的限流算法。