什么是限流器以及常見的服務(wù)限流算法

作者：lotusgrm

在開發(fā)高并發(fā)系統(tǒng)的時候，我們一般通過三種方式去保障系統(tǒng)服務(wù)穩(wěn)定：服務(wù)降級、服務(wù)限流和緩存。對于緩存在實(shí)際開發(fā)中使用的比較多，這個是大家的共識沒有什么異議的。今天我們的主角是服務(wù)限流，在此之前我們先來看下服務(wù)限流 和 服務(wù)降級 的區(qū)別：
服務(wù)降級

服務(wù)降級是在服務(wù)器壓力陡增的情況下，利用現(xiàn)有的資源，關(guān)閉一些服務(wù)接口或者頁面，以此來釋放服務(wù)器資源保證核心任務(wù)的正常運(yùn)行

服務(wù)限流

限流本質(zhì)上是減少流量的訪問，而服務(wù)的處理能力不變；而對于服務(wù)降級來說是降低了部分服務(wù)的處理能力，增加另一部分服務(wù)處理能力，訪問量不變

本篇文章中說到的服務(wù)限流不是 nginx 層面的限流，而是業(yè)務(wù)代碼中的邏輯限流。

那么，我們?yōu)槭裁匆?wù)限流？

從服務(wù)調(diào)用方來說，可以把服務(wù)簡單的劃分為以下幾種類型的服務(wù)
1.與用戶打交道的服務(wù)
比如 web 服務(wù)，對外 API,這種類型的服務(wù)有以下幾種可能會導(dǎo)致服務(wù)器壓力變大：

• 用戶增長過快

  
  

• 熱點(diǎn)事件

  
  

• 惡意的攻擊/刷單

  
  

• 爬蟲
  這些情況都是無法預(yù)知的，我們不知道什么時候請求流量會突增，如果真的要是碰到這種情況，擴(kuò)容根本是來不及的
  2.對內(nèi)的 RPC 服務(wù)
  一個服務(wù) A 的接口可能會被其他 BCDE 多個服務(wù)調(diào)用，如果其中一個服務(wù)的流量突增比如 B 服務(wù)，導(dǎo)致 A 服務(wù)壓力變大甚至掛掉，那么這個時候也不能給 CDE 服務(wù)提供服務(wù)
  這種情況在實(shí)際開發(fā)中時常發(fā)生

  
  

常見的限流算法

下面我們來看幾種實(shí)際業(yè)務(wù)場景中常用的幾種限流算法：計(jì)數(shù)器算法、漏桶算法、令牌桶算法

計(jì)數(shù)器算法

計(jì)數(shù)器算法應(yīng)該是最簡單，最容易想到的限流策略。限流的本質(zhì)是限制某一個 API 在某個維度單位時間內(nèi)處理請求的次數(shù)。我們可以設(shè)置一個計(jì)數(shù)器對某一時間段內(nèi)的請求進(jìn)行計(jì)數(shù)，當(dāng)請求量超過事先設(shè)定好的閾值，拒絕用戶的請求。比如限流的 QPS 是100，算法的實(shí)現(xiàn)思路是從第一個請求進(jìn)來開始計(jì)數(shù)，在接下來的 1s 內(nèi)，每來一個請求計(jì)數(shù)器自動加 1，如果累加的數(shù)字超過 100，那么后續(xù)的請求就會被拒絕，等到 1s 結(jié)束后，計(jì)數(shù)器開始重置為 0，重新開始計(jì)數(shù)。
這種方式存在弊端
弊端1：如果在 1s 的前 10ms 請求數(shù)已經(jīng)達(dá)到了 100，那么剩下的 990ms，服務(wù)調(diào)用方就要眼巴巴的看著請求被拒絕
弊端2：如果有一個惡意的用戶在 999ms 的時候瞬間發(fā)送了 100 次請求，并且又在 1000ms 時瞬間發(fā)送了 100 次請求，那么其實(shí)這個用戶在 1s 內(nèi)發(fā)送了 200 次請求。利用時間窗口的重置節(jié)點(diǎn)處突發(fā)請求，可以瞬間超過我們服務(wù)本身能承受的壓力，瞬間壓垮服務(wù)

針對計(jì)數(shù)器算法的漏洞一個比較經(jīng)典的處理方案是采用 滑動窗口。比如我們把上面的 1min 內(nèi) 100 次請求上限看成是一個大的時間窗口，然后把這個窗口進(jìn)一步細(xì)分，比如每 10 s 一個小窗口，該窗口的頻率上限同樣設(shè)置成 100，這樣大窗口包含 16 個小窗口，并且每過 10s 大窗口就移動一個小窗口長度。如果一個惡意用戶在 09:59:30~09:59:59 之間發(fā)送了 100 次請求，等到了10:00:00~10:00:30 時 100 次計(jì)數(shù)仍然是有效的，所以，這個時間段新的請求仍然會被拒絕

漏桶算法

漏桶算法是限流方面比較經(jīng)典的算法。可以把該算法聯(lián)想成一個具體的漏桶模型，漏桶始終以一個恒定的速率往外排水，如果桶被裝滿的話則后來涌入的水會溢出。對應(yīng)到接口限流來說，用戶的請求可以看做是水，不管用戶的請求量有多大多不均衡，能夠被處理的請求速率是恒定的，而且能夠接受的請求數(shù)也是有上限的，超出上限的請求會被拒絕，在算法實(shí)現(xiàn)方面可以準(zhǔn)備一個隊(duì)列來作為漏桶的實(shí)現(xiàn)，用這個隊(duì)列保存請求，通過一個線程池定期從隊(duì)列中獲取請求并執(zhí)行，也可以一次性獲取多個并發(fā)請求，如下圖：

漏桶算法也存在一個弊端：無法應(yīng)對短時間的突發(fā)流量

令牌桶算法

在令牌桶算法中，存在一個桶，用來存放固定數(shù)量的令牌。算法中存在一種機(jī)制，以一定的速率往桶中放令牌。每次請求調(diào)用需要先獲取令牌，只有拿到令牌才有機(jī)會繼續(xù)執(zhí)行，否則請求選擇等待或者服務(wù)直接拒絕請求
放令牌這個動作是持續(xù)不斷的進(jìn)行，如果桶中令牌數(shù)量達(dá)到上限，就丟棄令牌，所以，會存在這樣的一種情況，桶中一直有大量的令牌，這時進(jìn)來的請求就可以直接拿到令牌執(zhí)行。比如我們把 QPS 設(shè)置成 100，那么限流器完成初始化 1s 后，桶中已經(jīng)有 100 個令牌，這時候服務(wù)還未完全啟動好，等啟動完成功對外提供服務(wù)時，該限流器可以抵擋瞬時的 100 個請求。所以，當(dāng)桶中沒有令牌時請求才會等待或者被拒絕，當(dāng)沒有請求申請令牌時，那么這個令牌桶會溢出。在這里令牌桶類似一個 buffer,請求密度比較低或者處于冷卻狀態(tài)下，令牌桶會溢出，當(dāng)請求流量突增時，則過去積累的結(jié)余資源直接可以拿來借用，從這里可以看出這點(diǎn)彌補(bǔ)了漏桶算法的不足

實(shí)現(xiàn)思路：可以準(zhǔn)備一個隊(duì)列，用于存放令牌，另外通過一個線程池定期生成令牌存放到隊(duì)列中，沒來一個請求就從隊(duì)列中取出一個令牌，并繼續(xù)執(zhí)行

上面我們提到的限流算法主要是針對于單機(jī)限流，實(shí)際業(yè)務(wù)場景更加的復(fù)雜，業(yè)務(wù)的需求五花八門，簡單的單機(jī)限流很難滿足需求。
比如為了限制某個資源被某個用戶訪問的次數(shù)，10 s 只能訪問 3 次，或者一天只能訪問 100 次，這種需求通過單機(jī)限流是無法實(shí)現(xiàn)的，這時就需要通過集群限流的方式實(shí)現(xiàn)

如何實(shí)現(xiàn)?為了實(shí)現(xiàn)對訪問次數(shù)的限制，肯定需要一個計(jì)數(shù)器，那么我們需要把這個計(jì)數(shù)器放在哪里呢？因?yàn)檫@個限流是在集群層面實(shí)現(xiàn)的，集群形式存在的情況才需要分布式限流，由于 redis 天生對分布式支持非常友好，所以 redis 成了一個很好的選擇

大致思路：每次有相關(guān)的操作時候，我們就向 redis 服務(wù)器發(fā)送一個 incr 命令。比如限制某個用戶訪問接口的次數(shù)，當(dāng)用戶請求過來時我們使用用戶 ID 和 接口名稱生成對應(yīng) key,每次該用戶訪問這個接口時，只需要對這個 key 增加 1，并且給這個 key 設(shè)置有效期，這樣就可以簡單的實(shí)現(xiàn)指定時間內(nèi)的訪問效率