億級流量治理系列：常用的限流算法有哪些？

前言

上篇文章《爲什麼大公司都要做流量治理？》跟大家聊了下做流量治理的真正目的是什麼。如果你要開發一個流量治理的平臺或者一個限流的框架，那麼必不可少的就是要選擇一種合適的限流算法。本篇文章就跟大家聊聊目前常用的限流算法有哪些。

計數器

計數器是最簡單，最直接明瞭的限流算法。說白了就是進行數字累加操作，也就是 count++ 這你總能看懂吧！

單機限流可以直接使用 LongAdder 或者 AtomicLong 這些原子類進行計數操作即可。用 Semaphore 也可以，Semaphore 內部本身就是計數器的方式實現。

集羣限流可以使用 Redis 的 incr 進行計數累加即可，用其他的存儲也可以，核心就是要有集中存儲計數的地方。

計數器算法也分爲兩種形式，一種是有時間段的限制，另一種是沒有時間段的限制。

有時間段限制

有時間段限制就是你限流的時長是多少，一般我們都會以秒爲單位。比如限制 QPS 爲 1000。

有時間限制會存在一個臨界區的問題，假設第 1 秒中的第 999 毫秒的時候，來了 800 個請求，這個時候是沒有超過 1000 QPS 的限制。然後第 2 秒的 1 毫秒來了 800 個請求，相隔幾毫秒，很有可能前面的請求還沒執行完成，這麼又來了，其實這個時候的請求已經超出了你係統能夠承受的範圍了，也就失去了限流的效果。

如果非得要用有時間限制的計數器算法，那麼可以將時間單位調的越小越好。當然還有其他的算法能夠解決這個臨界區的問題，下面會介紹到。

無時間段限制

無時間段限制就不會存在臨界區的問題，請求進來數量加一，請求結束數量減一。將併發量最高永遠限制在你想要的範圍內。跟 Semaphore 是一樣的作用。

這個其實跟我們去飯店喫飯一樣，飯店總共 10 個座位，坐滿了你就得在外面等着叫號。如果有客人喫完離開了，空了一個座位出來，下一個客人才能進去。這樣就能永遠保證進去的人不超過飯店的座位數量，也在廚師和服務員能夠服務的範圍之內。

僞代碼示列：

@Slf4j
public class RatelimitFilter implements Filter {
    private AtomicLong atomicLong = new AtomicLong();
    @Override
    public void doFilter(ServletRequest servletRequest, ServletResponse servletResponse, FilterChain filterChain) throws IOException, ServletException {
        HttpServletRequest request = (HttpServletRequest)servletRequest;
        try {
            long currentQps = atomicLong.incrementAndGet();
            log.info("當前QPS: {}", currentQps);
            if (currentQps > 1) {
                throw new RuntimeException("限流中。。。。");
            }
            try {
                // 模擬業務耗時
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } finally {
            atomicLong.decrementAndGet();
        }
    }
}

滑動窗口

瞭解滑動窗口前先需要了解下固定窗口，固定窗口比較簡單，也就相當於固定大小。比如限制 1 秒內的訪問次數，那麼這個 1 秒就是一個固定的時間窗口。

滑動窗口可以將固定窗口再進行細分成多個窗口，比如將 1 秒中的固定窗口細分成 5 個窗口，那麼每個窗口的時間就是 200 毫秒。

假設每秒鐘限流 100，在 201ms-1000ms 之間的時候來了 99 個請求，不滿足限流條件，放行。在第 2 秒的 100ms 的時候來了 999 個請求，這個時候多餘的請求會被限制。當前窗口的範圍是 1 秒的 201ms~2 秒的 200ms。

通過滑動窗口算法，同時也能解決了上面計數算法臨界區的問題。窗口是一直滑動的，計算的數量也不是固定時間內的，而是隨着窗口的滑動一直在變化。

漏桶

漏桶算法能夠很好的保證穩定性，可以將突發的高流量以固定的速度流出來保證穩定性。

我記得小時候，家裏每年都會釀米酒，甜甜的米酒很好喝。當然我們不是來講米酒好不好喝的問題，而是要講解漏洞算法。那麼漏桶算法跟米有又有什麼聯繫呢？

釀好的米酒會裝在酒罈裏面，有時候村裏的其他人需要用到米酒的時候，如果自己家裏沒有釀的話就會去別人家買，一般都是拿一個瓶子來裝，比如我們的可樂瓶子。

但是可樂瓶子的入口很小，直接往裏面倒酒的話很容易灑出來。這個時候就有一個裝酒的漏斗，這個東西就跟我們今天要講的漏桶一樣，下面很小，上面很大。酒就相當於流量，倒入這個漏桶裏面，然後會從下面很小的口流出來，這個速度是固定的，這麼說相信大家一定明白了什麼是漏桶算法吧。

漏桶算法的優點是能夠以固定的速率去控制流量，穩定性比較好。缺點就是無法應對突發流量的來襲，我們來分析具體的分析下這個缺點。

假設你的漏桶出口固定了每秒鐘只能通過 100 個請求，如果此時有 150 個請求，無論你後方的系統能不能抗住這 150 個請求，通過漏桶算法都會將另外 50 個請求進行攔截，只能等前面的 100 個請求結束後才能繼續放行剩下的 50 個請求。

那麼有沒有什麼算法既能做流量控制，又能應對突發流量的場景呢？接下來爲你介紹令牌桶算法。

令牌桶

令牌桶算法用比較官方的術語來解釋就是：一個有固定容量的桶，按一定的速度往桶裏面放令牌，如果桶裏面裝不下令牌了就不放了。有請求進來就去桶裏面獲取對應的令牌，能拿到令牌就可以通過，拿不到就拒絕，也就是限流了。

我們還是用生活中的方式來解釋下令牌桶的原理，有天你帶着你的女朋友去喫自助餐，那些喫的你們可以隨便拿，如果拿完了，是不是就得等待餐廳重新供應了纔行，這就是限流了。同時，餐廳會定時的供應新的食物，食物供應上了，你能夠拿到了那就是放行，相當於拿到了令牌。

有令牌如下圖所示：

無令牌如下圖所示：

總結

本文對目前主流的限流算法進行了講解，相信大家有了一個初步的認識。這些算法在面試中也經常被問到，同時我也是通過各種生活中的案例來舉例，希望大家能夠徹底的理解這些算法的原理。

大家好，我是從古代穿越過來的美男子：架構擺渡人。我將把我的武功祕籍全部傳授與你們，覺得有用請分享給身邊的朋友。來個三連吧，感謝各位！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ZxTQ4CqbM8t6XsPEnaQFVw