技術乾貨|eBay對流量控制說「so easy」！

• 2019 年 12 月 30 日
• 筆記

轉自：eBayTechRecruiting

基於Kafka/Storm的實時流量控制系統

量大貨足5000字，超級技術乾貨

認真閱讀10分鐘，給你十分收穫

這篇乾貨，你能看到什麼？

流量控制對於保證Web服務的安全性和可靠性至關重要。在安全性方面，需要阻止黑客頻繁訪問某些API而獲取大量資訊。在可靠性方面，任何服務在有限資源的情況下能處理的TPS都有上限。如果超過上限，Service的SLA會急劇下降，甚至服務不可用。根據隊列理論，越多的流量，就會導致更多的延遲。所以為了保證Service的SLA，必須進行流量控制。本文介紹了一個基於Kafka和Storm的 非同步通用的流量控制方案；同時描述了如何根據數據傾斜程度來自動切換處理流程，以確保系統靈活性和延展性。最後，性能測試結果驗證了該方案在高吞吐量時也能將計算延遲控制在6ms左右。

「許雲博士，eBay中國研發中心平台架構部門安全領域負責人，同時也是eBay網站流量控制系統（Rate Limiter）和證書管理系統(CMS)的開發先鋒，致力於產品架構，演算法，大數據實時處理等研究。」

流量控制有話說

流量控制主要目的是用來限定Server所能承載的最大（高並發）流量峰值，以免在峰值時Server過載而宕機。對於WEB系統而言，通常是分散式部署，如果請求並發量很大，會導致整個集群崩潰，也就是通常所說的「雪崩效應」。所以不僅在網路代理層面（比如nginx）設置流量控制以抵抗、拒止溢出流量，還應該在App Server層面有一定的自我保護策略，確保當前JVM的負載應該在可控範圍之內，對於JVM承載能力之外的請求，應該被合理管理。在安全和業務方面App也會需要限制訪問頻率，例如:

一個IP每天限制創建20個帳號

一部手機每天只允許5次信用卡失敗交易

一個大客戶每天只能訪問某個API 10M次

eBay利用Rate Limiter設置各種策略來防止API被過度訪問以及防禦DoS攻擊。eBay要求Rate Limiter不僅可以基於IP進行流量控制，同時也要求支援對App、用戶、設備號等進行流量控制。eBay Rate Limiter的基本需求如下：

1.滑動窗口

Fix Window簡單有效，但有兩個致命的弱點：

（a）用戶如果將計算窗口 resize，例如從10分鐘變成1分鐘，Fix Window只能清0重新計數，因為完法區分最近1分鐘訪問了多少次。

（b）如果限制1分鐘只能訪問100次，用戶可以 在第一個窗口的最後10秒訪問99次，然後在下一個窗口的前10秒訪問99次，也就是說用戶在20秒內訪問了198次而不觸發policy。

滑動窗口可以有效解決 Fix Window的不足。

2.多計數窗口

App經常需要進行多窗口計數。比如登錄要求限制1分鐘內3次，1小時內20次，1天內50次。

3.Flexible Policy

支援複雜靈活的Policy。比如可以設置某個API的訪問比例不能超過這個服務所有API訪問次數的50%。

4.有效期

Policy一旦被觸發並返回Block或Captcha後，在生效期間內所有請求都將被Block或要求輸入驗證碼。

5.驗證碼服務

對於Web App, Rate Limiter可以返回驗證碼而不是Block請求。這樣 WEB App不需要單獨與驗證碼服務進行集成。比如eBay的Sign in介面，由Rate Limiter來決定是否需要讓用戶輸入驗證碼。

目前處理Rate Limiter的常用方式

目前常用的Rate Limiter演算法有兩種。一種是Token Bucket，按指定的方式向Bucket里添加token，每個請求消費一個token，如果沒有token則請求被拒絕。另一種是Leaky Bucket，用戶請求都會先存放在Bucket中，然後Bucket控制流出量。如果Bucket滿了，則請求被拒絕，這個演算法具有流量整形的功能。然而這些演算法不能直接應用於ebay Rate Limiter中。因為ebay的策略充許一個Resource關聯多個Policy，同時一個Policy也可能引用多個Resource。目前常用的RateLimiter方法有Google Guava中的Rate Limiter和Redis。

2.1 Guava Rate Limiter

Guava Rate Limiter是使用最多的第三方Class。但這個是單機版的，只能在一個JVM里有效，不能同時針對一個pool里多台機器。也不支援複雜的policy和及多窗口計數。

2.2 Redis

Redis作為distributed cache，提供了原子性的計數功能。所以很多解決方案都結合使用Redis的計數和cache過期這兩個功能。但是Redis如果要實現複雜的policy及多滑動窗口計數需要很多額外工作，最重要的是增加了很多遠程訪問，導致延遲大幅增加。基於eBay對於Rate Limiter的需求，這兩種方案並不適用。

eBay如何解決Rate Limiter痛點

為了解決eBay Rate Limiter痛點，本文提出了可擴展的Cloud Native解決方案。該方案使用Apache Storm進行大數據實時處理 。該方案有3個重要前提：

1、通用解決方案，對於所有的HTTP APP都可以使用。

2、對於Policy觸發的閾值不要求嚴格匹配。比如Policy定義1分鐘只允許訪問 1000次，APP接受在第1003次的時候才開始Block。對於秒殺這種業務場景，就 不適合這條假設。

3、對用戶請求造成的延遲小於3ms。

3.1 Architecture

基於上述前提，eBay Rate Limiter使用了非同步處理方案。如圖1所示，Rate Limiter包含如下主要模組：

Fig 1: Architecture of Next Gen RateLimiter

SMC用戶使用SMC創建和編緝流量控制策略。

Instrument 運行在用戶的Pool中，將每次用戶的URL請求轉換成RateLimiter Event發送給Rate Limiter Service。

RateLimiter Service 將收到的Event匹配Blacklist和Whitelist，如果匹配成功，則直接返回用戶。如果匹配不成功，則計算Event需要評估哪些policy，然後將相應的資訊插入Kafka中；同時從cache中查找對應的狀態並返回給用戶。

RateLimiter BackEnd Kafka Spout消費Event, 通過normalize來確定需要哪些計數窗口，然後經過 metering和decision進行計數和判斷狀態。最後將結果雙寫到Kafka和Remote cache。

3.2 RateLimiter Service

RateLimiter Service 是Raptor Ginger 應用服務，用於分析 Event匹配哪些Policy。如果Event匹配Whitelist或Blacklist，則直接返回結果，否則計算這個Event需要計算哪些policy，然後將相應的資訊保存在Kafka的ratelimiter-event topic中。同時Service後台有個執行緒會從Kafka的ratelimiter-result topic消費Backend計算結果並更新Local cache。Service從Local cache獲取Event對應的decision資訊並返回，如果沒有從本地cache中獲取到decision，則從remote cache中獲取decision。

3.3 RateLimiter Backend

RateLimiter Backend 是apache storm程式。如圖1所示，它主要包含 Policy spout, Kafka spout, normalizer bolt, metering bolt, decision bolt and Kafka bolt。

Policy spout 初始化時載入所有的policy並且增量載入變化的policy。將policy資訊發送給所有的normalizer和decision bolt。

Kafka spout 消費Kafka中的ratelimiter-event topic, 然後將Event消息發送給normalizer bolt。

Normalizer bolt 將Kafka中的消息解析成rate limiter event對象，然後根據對應的policy計算出所有的計數窗口。

Metering bolt 支援多窗口的sliding window與fix window計數。

Decision bolt 根據metering與policy資訊進行decision計算。

Kafka bolt 將計算結果保存在Kafka的ratelimiter-result topic中。

3.3.1Metering

Metering同時支援fix window和sliding window。通過cache將sliding window的演算法複雜度從O(n)優化到O(1)。假設某個policy需要對每個IP分別進行15秒與30秒的計數，並且每個time slot是5秒，則 Tc表示當前的time slot。如公式所示：

比如，表示15秒的計數結果； 表示30秒的計數結果。

圖2到圖5顯示了如何使用sliding window計算多窗口的4個連續狀態。

根據上述公式，如果需要對圖2中15秒與30秒進行計數，則分別使用如下公式：

上述公式計算某個窗口需要循環累加所有time slot的值，它的計算複雜度是 O(n)。假設一個time slot是5秒，則24小時的計數窗口則需要每次累加17280個 time slot。為了降低計算複雜度，快取除了當前slot的數量之和。則上述公式可變換成計算複雜度為O(1)的公式：

3.3.2Decision

Decision Engine根據metering的資訊來判斷Event對應的policy是否應該觸發。圖6顯示了Decision Engine的工作流程。如果Event已經觸發了一條policy，並且生效時間還沒有過期，則直接返回decision資訊；否則，按優先順序逐條判斷相應的policy是否滿足條件。如果滿足條件，則返回decision資訊並且設置policy的有效期。當有效期結束後，需要根據最新的metering資訊重新判斷policy是否滿足條件。

這個流程中最耗時的是計算policy中的Boolean表達式。有三種可選方案，它們分別是JavaScript Engine, J2V8和JEval。JDK1.7的JavaScript Engine基於Mozilla Rhino，而JDK1.8則基於Oracle Nashorn。J2V8則是基於Google的 JavaScript Engine V8，通過不同OS的動態鏈接庫，可以運行在Windows、Linux and Mac OS。JEval則是一個高性能，專門處理數學與Boolean表達式的解析器。它並不支援JavaScript語言，但相比複雜的JavaScript Engine具有明顯的性能優勢。表1列出了不同Engine之間的性能比較。

Fig 6: Decision flow

3.3.3Process flow

圖7顯示了Rate Limiter處理普通 traffic的流程。圖中每個小方塊表示一個Rate Limiter Event，相同顏色表示相同的Event。黑色箭頭表示隨機發送，彩色箭頭表示分組發送。

Backend配置了32個Kafka spouts，其數量等於ratelimiter-eventtopic的partition 數量。Kafka spout將收到的Event消息隨機發送給normalizer bolt，因為normalizing是無狀態操作。相比其它的分組策略，隨機分配具有最好的性能。因為metering與decision是有狀態的操作，所以相同的Event必須發送給同一個metering與decision blot。每個Event會立即觸發 metering and decision計算以達到最低的延遲。

Fig 7: Process flow for normal case

當數據傾斜很嚴重時，對上述處理流程是很大的挑戰。假設某個IP大量訪問同一個resource，則大量的Event會發送到同一個metering和decision bolt，從而導致某個JVM很忙，而其它很空閑。為解決數據傾斜的問題，引入了新的處理流程。如圖8所示，與普通流程最大的不同在於多了一個metering aggregation bolt，並且相同的Event可以被發送到一組metering bolt而不是一個bolt。最重要的是，meteringbolt不會立即發送metering計數結果，而是窗口移動時批量下發計數結果，然後由aggregation bolt進行匯總。如果一組metering bolt是10個，而窗口的time slot是5秒的話，那麼不論流量有多少，在aggregation bolt上每5秒只會有10個請求。它的本質思想是犧牲了延遲，達到高吞吐量來應對數據傾斜。

系統的後台會實時檢測每類Event的流量，並自動進行切換處理流程。對於普通的case追求低延遲，對於attack case追求高吞吐量，達到自我保護的目的。

Fig 8: Process flow for attack case

一次有趣的實驗

為了驗證該方案的性能，搭建了Backend的LnP測試環境。表2列出了 storm結點的VM資訊。

在LnP測試中，前1小時按10K TPS的流量插入Event到Kafka，後30分鐘按20K TPS的速率插入Event到Kafka。由於Kafka容量的限制，LnP測試環境不能插入太多的Event。測試中分別收集了三個階段的性能指標，分別是normalizer，metering和decision。如圖9所示, 第一個指標顯示normalizing平均耗時在1ms以下；第二個指標顯示前兩個操作（normalizing和metering）完成後的平均 耗時在3ms左右；第三個指標顯示所有操作完成的平均耗時在6ms左右。這其中還包含了bolt之間的網路開銷。從LnP測試結果可以推斷出，兩個supervisor結點可以至少處理20K TPS的Event，因為從10K TPS增加到20K TPS，延遲完全沒有增加。

Fig 9: Performance of RateLimiter backend

eBay Rate Limiter是一個基於Kafka和Storm，滿足流量控制需求的非同步通用方案。它支援多計算窗口和複雜的policy。系統會實時檢測每類event的流量，並自動進行切換處理流程。對於普通的case追求低延遲，對於attack case追求高吞吐量，達到自我保護的目的。