這次讓我們來設計一個API限流器，基於他們發送的請求數量來對用戶進行限制。難度：中等。
什麼是限流器？
假設我們有一個服務要接收大量的請求，但是它每秒能夠處理的請求數量是有限的。為瞭解決這個問題，我們需要某種限流機制，隻允許一定數量的請求通過，以便我們的服務能處理得過來。限流器，從整體上看，限制瞭某個對象（用戶、設備、IP等）在特定的時間窗口內能夠執行的事件數量。比如：
- 一個用戶每秒隻能發送一個請求。
- 一個用戶每天隻允許有3次信用卡交易失敗。
- 單個IP每天隻能創建20個賬戶。
通常來說，限流器限制瞭發送者在一個特定的時間窗口能發送多少請求，一旦到達瞭限制就會阻塞其它請求。
為什麼需要對API進行限流？
限流措施可以幫我們的應用層服務抵禦惡意行為，比如拒絕服務攻擊、密碼暴力破解、信用卡暴力交易等等。這些攻擊通常表現為連續的HTTP/S請求，看似來自於真實的用戶，但卻是由機器生成的。於是這些攻擊就更難以防范，可以高掛我們的服務、應用或者API。
限流措施還可以用戶防范經濟損失、降低基礎設施開銷、阻止垃圾流量和線上的騷擾。下面列舉瞭一系列場景，可以通過限流措施獲益，並讓我們的服務或API更加可靠：
- 行為不端的用戶和腳本：有意或無意，總有一些人或組織會發送大量的請求搞掛服務。還有一種情況是有用戶發送許多低優先級的請求，而我們要確保高優先級的請求不受影響。比如用戶發送許多請求來拉取分析數據，這個過程不應該影響其他用戶的關鍵事務。
- 安全性：限制兩階段認證中用戶進行雙因素嘗試的次數，比如限制輸錯密碼的次數。
- 防范惡意行為和不良設計實踐：如果沒有API限制，客戶端開發者可以使用懶散的開發策略，比如一遍又一遍地請求相同的數據。
- 保證開銷和資源使用的可控：服務通常是為正常的輸入行為設計的，比如一個用戶一分鐘發一篇帖子。而電腦可以通過API每秒推送數千次。限流裝置讓我們可以在服務API上進行控制。
- 收入：有的服務可能需要根據客戶服務的層次來限制操作數，因為需要通過限流來設計不同的收費模型。所有的API服務可以有一個默認的限制；如果要超出，用戶需要購買更高的限額。
- 流量削峰：確保服務始終是可用的。
系統需求和設計目標
我們的限流器需要滿足下列需求。
功能性需求：
- 限制某個實體在一個時間窗口內可以給一個API發請求的次數，比如每分鐘15個請求。
- API可以通過集群訪問，因此限流器也要考慮跨服務器的問題。如果超過閾值，無論是單機還是服務器集群，用戶應該收到一條錯誤消息。
非功能性需求：
- 系統應該是高可用的。限流器應該時刻在線，因為是它保護我們的服務不受外部攻擊。
- 我們的限流器不應該引入額外的延遲，繼而影響用戶體驗。
如何進行限流？
限流器是一個進程，用於控制用戶訪問API的頻率和速度。節流閥是一個進程，用於控制用戶在一個時間段內的API用量。節流閥可以定義在應用層或者API層。每當超越節流閥的時候，服務器返回HTTP狀態“429 – 請求次數太多”。
不同類型的節流
有三種有名的節流閥可用於不同的服務中：
硬節流：API的請求次數不能超過節流限制。
軟節流：這種類型下，我們可以將API請求限制設為一個百分比。比如我們限制每分鐘100條消息以及10%的超額限度，我們的限流器就會允許每分鐘110條消息。
彈性或動態節流：在彈性節流中，如果系統資源還有剩餘，請求數量就可以超過限度。比如，每個用戶每分鐘隻能發100條消息，但是如果此時系統還有富餘的資源，那麼用戶就可以發送超過100條消息。
限流有哪些不同的算法？
下面是用於限流的兩種算法。
固定窗口算法：在這個算法中，時間窗口定義為從時間單元開始到時間單元結束。比如，固定地用0-60秒來計算一分鐘的周期，而不看請求所處的時間窗口。下圖中，0-1秒之間有2條消息，1-2秒之間有3條消息，如果我們的限流是每秒兩條消息，那麼隻有“m5”被攔截。
滾動窗口算法：在這個算法中，時間窗口是從請求發出的片段開始計算，然後加上窗口長度。比如，兩條消息分別是1秒鐘的第300毫秒和400毫秒發送的，則我們計算當前的300毫秒到下一秒的300毫秒中總共有兩條消息。上圖中，如果還是每秒限制2條消息，那麼我們會攔截m3和m4。
限流器的概要設計
限流器負責決定哪個請求由API服務器來響應，哪個請求被拒絕掉。每次有新請求到達，Web服務器先問限流器應該響應還是拒絕。如果請求沒有被攔截，則轉交給API服務器。
基本系統設計和算法
我們來看一個例子，限制每個用戶的請求次數。在這個場景下，我們會為每個用戶記錄其請求次數和記錄的開始時間戳。我們可以把記錄保存在哈希表中，鍵是UserID，值是一個結構體，包含一個代表計數的整數和一個代表時間的整數。
假設我們的限流器允許每個用戶每分鐘3個請求，則每當一個新請求到達的時候，我們的限流器會執行如下步驟：
- 如果UserID不在哈希表中，插入一條記錄，設置Count為1，設置StartTime為當前時間（以分鐘計數），然後放行請求。
- 如果UserID在哈希表中，找到UserID對應的記錄，如果CurrentTime – StartTime >= 1，將StartTime置為CurrentTime，計數置為1，放行請求。
- 如果CurrentTime – StartTime < 1，並且再看：如果Count < 3，則Count加1，放行請求；否則拒絕請求。
這個算法有什麼問題？
- 由於我們是在每分鐘結束之後才更新StartTime，因而實質上是一個固定窗口算法，而每分鐘放行的請求可能是限額的雙倍。假設用戶在一分鐘的最後一秒發瞭3個請求，然後又能在下一分鐘的第一秒發3個請求，也就是2秒鐘內發瞭6個請求。解決這個問題需要用到滑動窗口的算法，我們後續會談到。
- 原子性：在分佈式環境中，“先讀後寫”的行為會帶來競爭性場景。假設用戶當前的Count是2，然後又發瞭2個請求。如果這2個請求由不同的進程處理，每個進程都會認為用戶還沒有達到限額，還可以發送請求。
如果我們使用Redis來保存鍵值對，那麼有一個方案，也就是在“讀取-更新”階段用Redis鎖來解決原子性問題。然而這樣的代價是拖慢同一個用戶的並發訪問，引入另一層復雜性。我們也可以使用Memcached，不過也有相當的復雜度。
如果我們使用簡單的哈希表，我們可以自己實現每條記錄的“鎖”，解決原子性問題。
我們需要多少內存來保存所有的用戶數據？
假設我們用簡單的方案，也就是哈希表來保存所有數據。
假設UserID有8字節，Count有2字節（可以記錄65k，滿足我們的場景）。盡管記錄時間需要4字節，但是我們可以選擇隻記錄分和秒，這樣2字節就夠瞭。總計需要12字節來保存一個用戶的數據。
假設我們的哈希表每條記錄需要額外耗費20字節。如果我們同時跟蹤100萬用戶，那麼總的內存需求就是：
(12+20)bytes times1M=32MB
假設我們需要4字節的數字來鎖住每個用戶的記錄以解決原子性問題，那麼總計就需要36MB。
這些數據可以輕易裝入一臺機器，不過我們並不希望把所有流量都路由到一臺機器中。另外，如果我們流量限制在每秒10個請求，那麼我們的限流器的QPS就要達到1000萬！這對於單臺服務器而言太多瞭。實踐中，我們會使用Redis或者Memcached這種分佈式解決方案。我們將數據保存在遠端的Redis服務器上，限流服務器從中讀取和更新數據，然後再決定接受或拒絕請求。
滑動窗口算法
如果我們可以記錄用戶的每個請求，我們就可以維護一個滑動窗口。除瞭前文提到的結構，我們還可以把每個請求的時間戳保存在Redis的有序集中。
假設我們的限流器允許每個用戶每分鐘發送3個請求，當一個新請求到達的時候，限流器會執行下列操作：
- 從有序集中刪除所有比“CurrentTime – 1 minute”更老的數據。
- 統計有序集中元素的數量，如果數量大於3就拒絕請求。
- 否則將當前時間插入有序集，接受請求。
對於滑動窗口算法，我們需要多少內存來保存所有用戶數據？
假設UserID有8字節，每個批次時間需要4字節，需要限制每小時500個請求，哈希表額外開銷20字節，有序集額外開銷20字節，最多情況下，一個用戶的數據需要：
8+(4+20(sortedset))times500+20(hashtable)=12KB
這裡我們為每個元素預留瞭20字節的開銷。有序集中，假設我們需要2個指針來維護元素的順序，一個指向前一個元素，一個指向後一個元素。在64位機器上，每個指針8字節，總計16字節。另外還要4字節作為其它開銷。
如果我們需要同時記錄100萬用戶，總的內存需求就是 12KBtimes 1M=12GB 。
滑動窗口相比固定窗口要消耗更多內存，我們有沒有辦法結合上述兩種方案來優化內存使用呢？
帶有計數的滑動窗口
如果我們為每個用戶同時記錄多個固定時間窗口的計數，每個窗口的大小為比如限流時間窗口的1/60，怎麼樣？比如，如果我們是按照小時限流的，則按照每分鐘進行計數，然後對過去一小時的各個數字進行求和，從而判斷新來的請求是否突破瞭限制。這樣可以減少我們的內存占用。舉個例子，我們限流每小時500個請求，同時還限制每分鐘10個請求。這意味著如果過去一小時內的計數求和超過500，或者每分鐘的計數超過瞭10，用戶就超過瞭流量限制。這裡的考量是合理又實際的，沒啥真實的用戶會特別頻繁地發送請求。即便有例外，他們也會在每分鐘計數重置之後重試成功。
我們可以把每分鐘的計數保存在Redis的哈希對象中，它在保存少於100個鍵的時候存儲效率極高。每個請求來的時候不僅要增加哈希中的計數，還要設置哈希的過期時間為1小時。我們按照分鐘記錄時間。
使用帶有計數的滑動窗口，我們需要多少內存來保存所有用戶的數據？
假設UserID為8字節，每個時間戳為4字節，計數2字節。假設限流每小時500請求，哈希表20字節，Redis哈希對象20字節，每個用戶60條記錄（1小時有60分鐘）。每個用戶總需要空間為
8+(4+2+20(Redis hash))times60+20(hashtable)=1.6KB
如果同時記錄100萬用戶的數據，那就是1.6GB。
所以帶有計數的滑動窗口相比簡單的滑動窗口節約瞭86%的內存使用。
數據分片和緩存
我們可以基於UserID來對數據進行分片。出於容錯和備份考慮，我們應該使用一致性哈希。如果我們對不同的API有不同的限流，我們可以按照每個用戶每個API的組合進行分片。參考設計短地址服務的例子，對於createURL()和deleteURL()這倆API有不同的限流。
如果我們的API也做瞭分片，實踐上也可以對每個API分片進行單獨限流（通常更小）。還是以短地址服務為例，我們限制每個用戶每小時創建不超過100個短地址。假設我們的createURL() API使用基於哈希的分區方案，我們可以限制每個分區每個用戶每分鐘創建不超過3個短地址，每小時總計不超過100個。
緩存最近的活躍用戶，對系統有很多好處。應用服務器可以快速檢查緩存中是否有對應的記錄，而不必訪問後端服務器。通過將計數和時間戳更新到緩存中，我們的限流服務也可以從回寫緩存中受益良多。持久化存儲可以以固定的節奏進行。所有的讀取先到緩存，對於用戶已經觸及上限，後續不再需要更新計數的場景尤其有用。
最近最少使用（LRU）是一個理想的緩存淘汰策略。
我們根據IP還是根據用戶來限流？
這裡我們來討論一下每種策略的優劣勢：
IP：這種策略下，我們根據IP來限制流量，盡管不是最佳方案，但是比沒有方案要好。其問題在於，當多個用戶共享同一個公網IP，比如網吧或者同一個網關出來的手機用戶，一個惡意用戶可以影響到其他用戶。另一個問題是緩存，對黑客而言，一臺電腦上可以弄出海量的IPv6地址，讓我們的服務器內存耗盡。
用戶：限流可以在用戶身份認證之後再做。一旦認證，用戶就會得到一個唯一的令牌，每次請求都要帶著這個令牌。這能確保我們的限流是針對有效令牌的API訪問的。但是如果我們要對登陸API本身進行限流呢？這種限流的弱點在於黑客可以針對某個用戶進行拒絕服務攻擊，隻要不斷輸錯密碼，而後實際用戶就無法登陸瞭。
混合式：正確的做法式同時進行基於用戶和IP的限流，因為單獨使用時各有弱點。但是這樣一來，每條記錄就會包含更多細節，也就需要更多內存和存儲。
