億級流量治理系列：常用的限流算法有哪些？
時間：2021-11-03 14:17:29
手機看文章
掃描二維碼
隨時隨地手機看文章
[導讀]前言上篇文章《為什么大公司都要做流量治理？》跟大家聊了下做流量治理的真正目的是什么。如果你要開發(fā)一個流量治理的平臺或者一個限流的框架，那么必不可少的就是要選擇一種合適的限流算法。本篇文章就跟大家聊聊目前常用的限流算法有哪些。計數(shù)器計數(shù)器是最簡單，最直接明了的限流算法。說白了就是進...
前言上篇文章《為什么大公司都要做流量治理？》跟大家聊了下做流量治理的真正目的是什么。如果你要開發(fā)一個流量治理的平臺或者一個限流的框架，那么必不可少的就是要選擇一種合適的限流算法。本篇文章就跟大家聊聊目前常用的限流算法有哪些。
計數(shù)器計數(shù)器是最簡單，最直接明了的限流算法。說白了就是進行數(shù)字累加操作，也就是count 這你總能看懂吧！?單機限流可以直接使用LongAdder或者AtomicLong這些原子類進行計數(shù)操作即可。用Semaphore也可以，Semaphore內部本身就是計數(shù)器的方式實現(xiàn)。?集群限流可以使用Redis的incr進行計數(shù)累加即可，用其他的存儲也可以，核心就是要有集中存儲計數(shù)的地方。?計數(shù)器算法也分為兩種形式，一種是有時間段的限制，另一種是沒有時間段的限制。?
有時間段限制
有時間段限制就是你限流的時長是多少，一般我們都會以秒為單位。比如限制QPS為1000。?有時間限制會存在一個臨界區(qū)的問題，假設第1秒中的第999毫秒的時候，來了800個請求，這個時候是沒有超過1000 QPS的限制。然后第2秒的1毫秒來了800個請求，相隔幾毫秒，很有可能前面的請求還沒執(zhí)行完成，這么又來了，其實這個時候的請求已經超出了你系統(tǒng)能夠承受的范圍了，也就失去了限流的效果。?
??如果非得要用有時間限制的計數(shù)器算法，那么可以將時間單位調的越小越好。當然還有其他的算法能夠解決這個臨界區(qū)的問題，下面會介紹到。
無時間段限制
無時間段限制就不會存在臨界區(qū)的問題，請求進來數(shù)量加一，請求結束數(shù)量減一。將并發(fā)量最高永遠限制在你想要的范圍內。跟Semaphore是一樣的作用。?這個其實跟我們去飯店吃飯一樣，飯店總共10個座位，坐滿了你就得在外面等著叫號。如果有客人吃完離開了，空了一個座位出來，下一個客人才能進去。這樣就能永遠保證進去的人不超過飯店的座位數(shù)量，也在廚師和服務員能夠服務的范圍之內。?偽代碼示列：?@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("當前QPS: {}", currentQps); if (currentQps > 1) { throw new RuntimeException("限流中。。。。"); } try { // 模擬業(yè)務耗時 TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } finally { atomicLong.decrementAndGet(); }????}}?滑動窗口了解滑動窗口前先需要了解下固定窗口，固定窗口比較簡單，也就相當于固定大小。比如限制1秒內的訪問次數(shù)，那么這個1秒就是一個固定的時間窗口。
?
滑動窗口可以將固定窗口再進行細分成多個窗口，比如將1秒中的固定窗口細分成5個窗口，那么每個窗口的時間就是200毫秒。?假設每秒鐘限流100，在201ms-1000ms之間的時候來了99個請求，不滿足限流條件，放行。在第2秒的100ms的時候來了999個請求，這個時候多余的請求會被限制。當前窗口的范圍是1秒的201ms~2秒的200ms。?通過滑動窗口算法，同時也能解決了上面計數(shù)算法臨界區(qū)的問題。窗口是一直滑動的，計算的數(shù)量也不是固定時間內的，而是隨著窗口的滑動一直在變化。??漏桶漏桶算法能夠很好的保證穩(wěn)定性，可以將突發(fā)的高流量以固定的速度流出來保證穩(wěn)定性。
?我記得小時候，家里每年都會釀米酒，甜甜的米酒很好喝。當然我們不是來講米酒好不好喝的問題，而是要講解漏洞算法。那么漏桶算法跟米有又有什么聯(lián)系呢？?釀好的米酒會裝在酒壇里面，有時候村里的其他人需要用到米酒的時候，如果自己家里沒有釀的話就會去別人家買，一般都是拿一個瓶子來裝，比如我們的可樂瓶子。?但是可樂瓶子的入口很小，直接往里面倒酒的話很容易灑出來。這個時候就有一個裝酒的漏斗，這個東西就跟我們今天要講的漏桶一樣，下面很小，上面很大。酒就相當于流量，倒入這個漏桶里面，然后會從下面很小的口流出來，這個速度是固定的，這么說相信大家一定明白了什么是漏桶算法吧。?
?漏桶算法的優(yōu)點是能夠以固定的速率去控制流量，穩(wěn)定性比較好。缺點就是無法應對突發(fā)流量的來襲，我們來分析具體的分析下這個缺點。?假設你的漏桶出口固定了每秒鐘只能通過100個請求，如果此時有150個請求，無論你后方的系統(tǒng)能不能抗住這150個請求，通過漏桶算法都會將另外50個請求進行攔截，只能等前面的100個請求結束后才能繼續(xù)放行剩下的50個請求。?那么有沒有什么算法既能做流量控制，又能應對突發(fā)流量的場景呢？接下來為你介紹令牌桶算法。令牌桶令牌桶算法用比較官方的術語來解釋就是：一個有固定容量的桶，按一定的速度往桶里面放令牌，如果桶里面裝不下令牌了就不放了。有請求進來就去桶里面獲取對應的令牌，能拿到令牌就可以通過，拿不到就拒絕，也就是限流了。?我們還是用生活中的方式來解釋下令牌桶的原理，有天你帶著你的女朋友去吃自助餐，那些吃的你們可以隨便拿，如果拿完了，是不是就得等待餐廳重新供應了才行，這就是限流了。同時，餐廳會定時的供應新的食物，食物供應上了，你能夠拿到了那就是放行，相當于拿到了令牌。?有令牌如下圖所示：
無令牌如下圖所示：?總結本文對目前主流的限流算法進行了講解，相信大家有了一個初步的認識。這些算法在面試中也經常被問到，同時我也是通過各種生活中的案例來舉例，希望大家能夠徹底的理解這些算法的原理。
下載文檔
