之前的文章中，我們曾介紹過世界最大的免費CDN供應商CloudFlare使用Rust從零開發自建Web代理伺服器Pingora代替其廣泛使用的Nginx伺服器的詳細的案例和技術細節。CloudFlare也承諾會逐漸對其進行開源以及更多技術細節的分享。上周CloudFlare開始建立了Pingora的Github共享庫，開源了Pingora的一個底層庫pingora-limits。
今天我們就來學習一下這個底層庫（或者叫闆條箱crate）有關的技術細節。
概述
pingora-limits是Pingora伺服器中的一個重要的元件，提供了計算代理伺服器運作中的事件統計和估計事件發生率的功能。該功能用于保護基礎設施和服務免受某些類型的惡意或行為不當請求的影響。
例如，當源伺服器變慢或無響應時，請求将累積到前端代理伺服器上，這會給前端代理伺服器和後端的客戶伺服器都造成壓力。有了這個庫，就可以準确識别有問題的請求來源，然後可以不影響其他流量的情況下對其進行處理。
這個問題可以用一種非常簡單的方式抽象出來。輸入是不同類型事件的流。在任一時刻，系統都應該能夠判斷某類事件的出現次數（或比率）。
在一個簡單的例子中，可以将顔色當做事件的類型，這樣一個可能事件流示例：
紅、藍、紅、橙、綠、棕、紅、藍……
在上面示例中，應該統計到“紅色”事件出現了3次。
相應的算法設計起來很簡單，一個明顯的答案是使用哈希表，以顔色為鍵，值是它們對應次數。當出現新事件時，算法都會查找哈希表的健并對其增加計數。雜湊演算法的時間複雜度為O(1)，空間複雜度為 O(n)，其中n是事件類型的數量。
技術細節
哈希表解決方案在常見場景中很好，但有一些地方需要改進。
當行為異常的伺服器在某一時刻隻有少數時，面對百萬台的線上代理伺服器，需要大量空間（記憶體）來儲存所有鍵的計數器似乎有點浪費。
另外更新哈希表（尤其是添加新鍵時）需要鎖。這種行為可能會強制所有并發事件處理通過我們的系統序列化。換句話說，當鎖競争很頻繁時，鎖會使系統性能大大減小。
考慮到需要大規模部署此類算法，改進上述算法解決以上問題非常有必要：
該算法在數萬台機器上運作。
它每秒處理超過兩千萬個請求。
提高效率可帶來巨大的成本節約。
pingora-limits中采用更優化的算法count-min sketch（CM sketch）估計。CM sketch 估算O(1)中的事件計數，但僅使用O(log(n))的空間。
由于該算法的簡單性，可以在沒有鎖的情況下實作。是以，與前面讨論的哈希表方法相比，pingora-limits運作得更快、更有效。
CM sketch
CM sketch和Bloom filter算法類似。CM sketch數學細節不在讨論（有意者，可以自己搜尋學習），此處隻直白說明其工作原理。
CM sketch 資料結構有兩個參數：
H：哈希數（行）
N：每個哈希（行）的計數器（列）數。
行和列形成一個矩陣。他們占用的空間是H*N。每行都有自己獨立的哈希函數（hash_i()）。
例如，假使H=3，N=4，則是個三行四列的矩陣：
當發生“紅色”事件時，每一行都會獨立對其進行計數。每行将使用其自己的哈希函數( hash_i(“red”) )來選擇一列，增加的列計數器而不用擔心碰撞。
下表說明了一個“紅色”事件後矩陣的可能狀态：
然後，假設事件“藍色”發生，假設它在第2行與“red”發生沖突：兩者都哈希到第三個槽：
假設又經曆了一系列事件 “藍色、紅色、紅色、紅色、藍色、紅色”，到目前為止，總共觀察到5個“紅色”和3個“藍色”。按照該算法，估計器矩陣終變為：
現在，根據矩陣數值，看看CM sketch如何計算每個事件的發生的呢？為了檢索各鍵（紅藍色）的數量，CM sketch估計器用了一個最小計算原則，即傳回各行中各個健值的最小數即可。
是以紅色的計數是min(5, 8, 5) = 5，
藍色是min(3, 8, 3) = 3。
該算法選擇碰撞最少的單元格。是以，單個單元格中事件之間有碰撞是可以接受的，因為隻要給定類型的事件存在無碰撞單元格，該事件的計數就是準确的。
當兩個（或更多）鍵在所有槽上發生碰撞時，估計器可能會高估。假設隻有兩個鍵，它們總碰撞的機率是 1/N^H（本例中為 1/64）。另一方面，它從不低估，是以，CM sketch不會遺漏任何事件。
代碼實作
由于該算法隻需要散列、數組索引和計數器遞增，是以可以用幾行代碼中實作，并且是無鎖的。
以下是它在 Rust 中如何實作的代碼片段。
基線測試
将上面的設計與兩種基于哈希表的方法進行比較。
Rust原生的Mutex<HashMap<u32, usize>>。這種方法參考了上面提到的簡單哈希表方法。該方法要求對每個操作都進行鎖定。
優化的DashMap<u32, AtomicUsize>。DashMap利用多個哈希表來分片鍵以減少不同鍵之間的争用。另外，在這裡還使用原子計數器，這樣計算現有鍵就不需要寫鎖了。
對基線測試使用了兩個測試用例，一個是單線程的，另一個是多線程的。在兩種情況下，都有一百萬個健。并對着百萬健生成了1的億個事件。這事件針對每個健均勻分布。
測試使用M1 MacBook Pro本上Debian VM 上執行的，結果：
速度
每個事件（上面的incr()函數）計時，越低越好：
| pingora-limits | 原生哈希 | 優化方法 | |
| 單線程 | 10ns | 51ns | 43ns |
| 八線程 | 212ns | 1505ns | 212ns |
在沒有鎖争用的單線程情況下，pingora-limits方法比原始方法快5倍，比優化方法快4倍。 對于多線程下，存在大量争用。pingora-limits方法類似于優化版本。兩者都比原生算法的快7倍。pingora-limits 和優化哈希表的性能相似的原因是因為在這兩種方法中，都隻是更新原子計數器。
記憶體消耗
越低越好。為簡單起見，這些數字僅從單線程測試用例中收集。
| 峰值記憶體位元組 | 總配置設定次數 | 總配置設定位元組 | |
| pingora-limits | 26,184 | 9 | 26,184 |
| 原生哈希 | 53,477,392 | 20 | 71,303,260 |
| 優化方法 | 36,211,208 | 491 | 71,307,722 |
Pingora-limits峰值需要優化算法記憶體的1/1300，隻是原始算法記憶體的1/2000。
從上面的資料來看，pingora-limits 在CPU和記憶體上都是高效的。
Pingora-limits 提供的估計器是有偏估計器，因為它可能高估事件的出現。在準确計數的場合，是不允許有誤報的。但pingora-limits 使用的場合不是這樣的，pingora-limits是用于對代理流量的第一級過濾器，隻有特定時間超過一定門檻值的才會觸發統計，記錄到哈希表以進行準确計數。在這種情況下，大多數低頻事件類型被過濾器過濾掉，是以哈希表也消耗很少的記憶體也損失任何準确性。
架構
在pingora中，有很多地方使用了這個庫。最常用的部分是實作連接配接限制功能：當伺服器嘗試與單個源伺服器建立太多連接配接時，為了保護伺服器和基礎設施不超載，該功能将開始拒絕新請求并傳回503錯誤。
在這個功能中，每個傳入請求都被增加一個計數器，由具有相同客戶ID、伺服器IP和伺服器主機名的所有其他請求共享。 當請求完成時，計數器相應地減少。 如果計數器的值超過某個門檻值，則請求被拒絕并傳回503錯誤響應。在CloudFlare生産環境中，選擇庫的參數，以便兩個不相關的客戶之間的理論碰撞機會約為1/2^ 52。拒絕門檻值明顯高于健康客戶的流量所能達到的水準。是以，即使多個客戶的計數發生碰撞，高估值也基本達不到所設的正常門檻值。是以不太可能發生連接配接限制的誤報。
結論
Pingora-limits crate現已在GitHup開源，在源碼倉庫中提供了核心的功能和性能基準測試用例。
pingora-limits，這是一個兼顧了有效性、性能以及資源占用各方面綜合考慮下的統計事件庫，基準測試表明，pingora-limits實作速度快且記憶體消耗非常有效。在此，我們可以學習這種解決問題的思路（思想），以及可以直接拿走這個算法，用在我們類似的應用上，當然最友善是直接拿走這個闆條箱在我們自己Rust項目中使用。
另外，希望CloudFare可以加大開源程序，然我們可以早日用上這個Rust開發的Web代理伺服器（代替Nginx）。