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