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

前言

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

計數(shù)器

有時間段限制

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

有時間限制會存在一個臨界區(qū)的問題，假設(shè)第1秒中的第999毫秒的時候，來了800個請求，這個時候是沒有超過1000 QPS的限制。然后第2秒的1毫秒來了800個請求，相隔幾毫秒，很有可能前面的請求還沒執(zhí)行完成，這么又來了，其實這個時候的請求已經(jīng)超出了你系統(tǒng)能夠承受的范圍了，也就失去了限流的效果。

如果非得要用有時間限制的計數(shù)器算法，那么可以將時間單位調(diào)的越小越好。當(dāng)然還有其他的算法能夠解決這個臨界區(qū)的問題，下面會介紹到。

無時間段限制

無時間段限制就不會存在臨界區(qū)的問題，請求進來數(shù)量加一，請求結(jié)束數(shù)量減一。將并發(fā)量最高永遠(yuǎn)限制在你想要的范圍內(nèi)。跟Semaphore是一樣的作用。

這個其實跟我們?nèi)ワ埖瓿燥堃粯?，飯店總?0個座位，坐滿了你就得在外面等著叫號。如果有客人吃完離開了，空了一個座位出來，下一個客人才能進去。這樣就能永遠(yuǎn)保證進去的人不超過飯店的座位數(shù)量，也在廚師和服務(wù)員能夠服務(wù)的范圍之內(nèi)。

@Slf4jpublic 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("當(dāng)前QPS: {}", currentQps);            if (currentQps > 1) {                throw new RuntimeException("限流中。。。。");            }            try {                // 模擬業(yè)務(wù)耗時                TimeUnit.SECONDS.sleep(2);            } catch (InterruptedException e) {                e.printStackTrace();            }        } finally {            atomicLong.decrementAndGet();        }    }}

滑動窗口

了解滑動窗口前先需要了解下固定窗口，固定窗口比較簡單，也就相當(dāng)于固定大小。比如限制1秒內(nèi)的訪問次數(shù)，那么這個1秒就是一個固定的時間窗口。

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

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

通過滑動窗口算法，同時也能解決了上面計數(shù)算法臨界區(qū)的問題。窗口是一直滑動的，計算的數(shù)量也不是固定時間內(nèi)的，而是隨著窗口的滑動一直在變化。

漏桶

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

我記得小時候，家里每年都會釀米酒，甜甜的米酒很好喝。當(dāng)然我們不是來講米酒好不好喝的問題，而是要講解漏洞算法。那么漏桶算法跟米有又有什么聯(lián)系呢？

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

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

漏桶算法的優(yōu)點是能夠以固定的速率去控制流量，穩(wěn)定性比較好。缺點就是無法應(yīng)對突發(fā)流量的來襲，我們來分析具體的分析下這個缺點。

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

那么有沒有什么算法既能做流量控制，又能應(yīng)對突發(fā)流量的場景呢？接下來為你介紹令牌桶算法。

令牌桶

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

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

有令牌如下圖所示：

無令牌如下圖所示：

總結(jié)

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

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

推薦下我的B站主頁，目前在更新技術(shù)視頻，記得關(guān)注哦！

https://space.bilibili.com/1791216636


點擊閱讀原文直達(dá)主頁