簡單聊聊 Maglev ，來自 Google 的軟負載均衡實踐

好久沒博客了，來寫個簡單的讀論文筆記吧，這篇文章是來自 Google 2016 年發表的一篇論文 Maglev: A Fast and Reliable Software Network Load Balancer 分享了他們內部從 08 年開始大規模使用的軟負載均衡系統的實現。裡面很多很有趣的細節，我看我能寫多少，算多少吧

背景#

負載均衡的概念大家肯定都比較熟悉了，再次不再贅述。現在我們需要考慮 Google 的場景。設計之初，Google 需要一種高性能的 LB 來承擔 Google 一些重頭服務的流量，比如 Google 搜索，Gmail 等等。由於流量非常龐大，那麼 LB 需要非常強大的性能來處理大量的流量。

在這裡，傳統的想法可能說，我直接上專業的硬體負載均衡，能用錢解決的問題，都不算事（笑。但是這樣的方案有著不小的問題

硬體負載均衡單點的性能決定了整個網路能承擔的請求
在 HA 上存在缺陷。為了保證單點失效的時候，整個網路集群不陷入癱瘓。那麼我們通常需要 1:1 的做冗餘
靈活性和編程性欠缺，想做騷操作的時候沒有切入點
太貴了。貴到 Google 都承受不了（逃

在這樣一種情況下，Google 開始考慮自行構建一種 SLB (Software Load Balance) 系統。去構建這樣一種系統。好處也很明顯。比如方便的 Scale ，為了保證 HA 所需的冗餘從之前的 1:1 可以降至 N+1 ，方便的定制性等。架構就演變成下圖了

但是挑戰也很明顯。首先需要有足夠的性能，這樣保證集群有足夠的吞吐。同時需要做 connection tracking ，這樣保證同一個連接的數據包能妥投到同一個機器上。也許要保證能有透明的 failover 的能力。

這樣一些要件結合起來，這也就是我們今天要聊的 Maglev。Google 從 08 年開始大規模的應用的 LB 系統

Maglev 初窺#

背景知識#

在繼續聊 Maglev 之前，我們需要去了解 Google 現在怎麼樣去使用 Maglev 的，下面是一個簡化後的示意圖

同時這裡我們需要介紹一個很重要的概念叫做 VIP (Virtual IP Address) 。用過 Kubernetes 的同學肯定對這個概念並不陌生。VIP 並不是一個實際與網卡綁定的物理 IP。近似來講它可以作為後端一組 Endpoint 的抽象，當你訪問這個 VIP 的時候，實際上是在訪問後端的 Endpoint 。這裡舉個更方便理解的例子，以 Kubernetes 為例，我們在創建完一組 Pod 後，為了暴露 Pod 中提供的服務，我們通常會創建一個 Service 來關聯對應的 Pod。Service 通常會有一個 IP，那麼這個 IP 就是一個 VIP 。當我們訪問 Service 的 IP 的時候，通常會隨機從後面的 Pod 中選擇一個承接請求。

好了，回到 Maglev ，我們現在來看下整個的流程。Maglev 會和 VIP 關聯，然後將 VIP 透傳給一組 Router。當用戶在瀏覽器中輸入 https://www.google.com 並按下回車的時候，瀏覽器會進行 DNS 解析。而 DNS 解析將由 Google 的 DNS 伺服器進行處理。DNS 伺服器會根據用戶的區域選擇一個最近集群的 VIP 返回給用戶，然後瀏覽器會根據獲取到的 VIP 建立連接。

當 Router 收到對應包時，會將包轉發給 VIP 所屬的 Maglev 集群中的任意節點。集群中的每個節點權重都是平衡。Maglev 節點在接受到包的時候，會利用 GRE (Generic Routing Encapsulation) 進行封包。然後傳輸給對應的後端端點。

當後端端點接收到數據包的時候，會進行接包並處理請求。當響應數據準備就緒的時候，會進行封包操作，會將 VIP 的作為源地址，用戶的 IP 作為目標地址，然後響應數據作為數據包操作。這個時候，後端端點會利用 DSR (Direct Server Return) 將數據包繞過 Maglev 直接返回。這樣避免響應過大的時候對 Maglev 造成額外的負擔。實際上 DSR 在 L4 的 LB 實現，如 HAProxy，Envoy 等都得到了比較多的應用。改天有時間寫篇博客來聊聊。

Maglev 配置#

如前面所說， Maglev 接收來自 Router 的 VIP 請求，然後將對應流量轉發到對應的後端端點上。每個 Maglev 將由 Controller 和 Forwarder 組成，其架構如下所示

而 Controller 和 Forwarder 都利用 Configuration Object 管理相關 VIP。Configuration Object 這一套實際上又是另外一套系統（可以近似的認為是註冊中心），彼此之間通過 RPC 來通信。

在 Maglev 機器上，Controller 會定期對 Forwarder 進行檢查。根據檢查結果來確定是否通過 BGP 提交 / 撤回所有 VIP 的註冊（要麼全部成功，要麼全部失敗，其實還是為了保障系統的一致性）。這樣確保從 Router 過來的流量都能扔到健康的機器上

而從 Router 過來的 VIP 流量將會由 Forwarder 進行處理。在 Forwarder 中，每個 VIP 都會和一個或多個 backend pool 關聯。除非特殊處理，Maglev 中的 backend 都是服務端點。一個 backend pool 可以包含一組服務端點的的物理 IP ，也可以是其餘的 backend pool。每個 backend pool 都會根據其特定需求，設計若干個監控檢查器，數據包只會轉發給健康的服務。如之前所說，同一個服務可能會被包含在多個 backend pool 中，因此 Forwarder 將會根據具體的地址進行去重，避免額外的開銷。

Forwarder 的 Config Manager 將負責從 Configuration Object 中拉取，解析並驗證相關的配置。所有配置的提交都是具備原子性（要麼全部成功，要麼全部失敗）。在推送和解析到生效的過程中，存在一個非常短暫的 gap，在此期間，一個 Maglev 集群之間的配置可能存在不同步的情況。不過因為一致性 Hash 的存在，在這個非常短的 Gap 內，大部分請求還是能成功妥投。

Maglev 實現#

好了，扯了這麼多，來看一下 Maglev 整個系統的一些實踐細節

概述#

總所周知（如前面所說），Maglev 由 Forwarder 來實際承擔流量相關的轉發工作，我們用一張圖來說明一下它的結構

Forwarder 將直接從 NIC (Network Interface Card) 拿到數據包，然後直接扔入 NIC 轉發到後端。期間所有操作都不會過內核（實際上過內核會有額外的 cost）

從 NIC 中捞出的包，會先由 Steering Module 進行處理，在處理過程中，Steering Module 將會根據五元組（協議，目標地址，目標端口，源地址，源端口）進行 hash 計算。然後將其轉入對應的 Receiving Queue 中。每個 Receiving Queue 都會對應一個處理線程。處理線程將過濾掉目標 VIP 和本機註冊 VIP 不匹配的包。然後會重新計算五元組 hash，然後從 Connection Tracking Table 中查找對應的值。

在 Connection Tracking Table 中存放之前五元組 Hash 所對應的 Backend，然後如果查找命中，那麼直接復用，如果未命中，則為這個包選擇一個新的 Backend, 然後將鍵值對加入 Connection Tracking Table。如果此時沒有 Backend 可用，那麼這個包會被丟棄。當這個包完成查找操作後，如前面所說，會改寫這個包，然後將其放入 transmission queue 中去。最後將 muxing module 會將 transmission queue 的包直接通過 NIC 發送出去。

這裡有個問題，在 Steering Module 中為啥不考慮根據 round-robin 這種常見的策略來做？大家都知道每個線程的處理速度是不一致的，如果直接裸 round-robin ，那麼面對這種情況，可能會導致數據包重排的情況發生，如果是引入權重的概念來改良，又會引入新的複雜度，畢竟線程的處理速度是動態變化的。另外一種是 connnection tracking 的情況，假設我們有個需要持久化的連接，我們需要保證每個包都能扔到同樣的機器上，這個時候用 round-robin 就會引入額外的複雜性。不過對於一些特殊情況，比如 receive queue 滿了，一致性 Hash 處理不過來的時候，我們會利用 round-robin 作為 backup 的手段來替代一致性 Hash，這種情況對於同時存在同樣 5 元組包的時候比較好用。

高效處理數據包#

前面已經花了很多時間講述了，Maglev 是直接對 TCP 的數據包進行操作，同時因為 Google 的流量極為龐大，那麼這個時候實際上是需要 Maglev 有著良好的轉發性能。不然在大規模場景下，其吞吐能力會無法滿足需求。Google 怎麼做的？答：直接對網卡操作。。

我們都知道在 Linux 中進行網路編程的時候，將數據包從內核態拷貝到用戶態實際上是一件開銷非常大的事，所以對於一些極端需求性能的場景，如 L4 的負載均衡等，大家可能更傾向於將東西做到內核裡，避免跨態拷貝。這也是 LVS 等工具的思路。但是實際上對於更大規模的流量，來講，從網卡到內核，經過內核中的一堆 filter 處理也是一件開銷非常大的事，而如同前面所說，Maglev 只依賴數據包中的五元組，對於包序列號，包 payload ，都不需要關心。於是 Google：我有一個大膽的想法！好了，來看張圖

Google 選擇直接在 NIC (即網卡) 上進行編程。讓 Forwarder 和 NIC 共享一片內存。內存中維護的是一個環状的數據包池子。然後 Forwarder 中的 steering module 和 muxing module 各自維護三個指針來處理這些數據包，下面詳細描述一下

首先而言 steering module 維護了三個指針

received ，管理接收數據包
reserved, 管理已接收未處理的數據包
processed, 管理處理完成的數據包

那麼流程是這樣的，當 NIC 接受到新的數據包後，那麼 received 指針指向的內存會被修改。然後當一個數據包被分發給線程完成相關操作後，那麼 processed 指針指向的內存地址會被修改。因為是個環狀結構嘛， received 和 processed 中間存在的數據包就是已接收但未完成處理的包，由 reserved 指針進行管理。

於此對應的，muxing module 也維護了三個指針

sent，管理已發送完畢的數據包
ready，管理已經就緒等待發送的數據包
recycled, 管理已回收的數據包

那麼對應的流程是這樣的，當 steering module 完成相關包的處理的時候，ready 指針指向的內存會被修改，然後等待發送。當一個數據包發送後，sent 指向的內存地址被修改。在 ready 和 sent 之外有另一個狀態 recycled 管理已經回收的數據包。

我們可以看到在這個過程中，沒有發生數據拷貝的操作，實際上這減小了一部分複製數據帶來的時延。不過這種方法存在的問題就是，當指針越界後，會帶來很大的額外開銷。所以 Google 採用的做法是批處理，比如接收 3000 個小包集中處理一次，這樣的騷操作

另外需要做一些額外的優化，比如包處理線程之間不共享數據以避免競態。比如需要將線程與具體 CPU Core 綁定來保證性能等等

目前來看，Google 這一套的做法效率非常的出色，平均每個包的處理只需要 300 ns ($10^{-9}$s)。如同前面所說，Google 採用批處理的方式來處理包，這樣的問題是每當一些例如硬體中斷的情況發生的時候，可能到達處理閾值的時間會比大部分情況長很多，所以 Google 設計了一個 50μs ($10^{-6}$s) 的 Timer 來處理這種情況。換句話說，當因為硬體或者其餘問題時，整體的包處理時長可能會增加 50μs 的時間（其實這裡感覺 Google 怎麼是在得瑟，你看我們性能超棒的噢，只有硬體是我們的瓶頸喔（逃

後端選擇#

如同前面所說的一樣，Forwarder 會為數據包選擇一個後端。對於 TCP 這種常見來說，將相同五元組的數據包轉發到同一個後端節點上非常重要。Google 採取在 Maglev 中維護一個 connction tracking table 來解決這個問題。當一個包抵達的時候，Maglev 會計算其五元組 Hash ，然後確定在 table 中是否存在，如果不存在，則選擇一個節點作為後端，然後將記錄值添加到 table 中。如果存在則直接復用

這樣看起來沒有問題了對吧？Google：不，不是，還有問題！

我們首先考慮這樣一種場景：如前面所說，Maglev 前面掛了一個 / 組 Router，而 Router 是不提供連接親和的，即不保證把同一個連接的包發送到同一個機器上。所以可能存在的情況是同一個連接的不同數據包會被仍在不同的機器上。再比如，我們假設 Router 是具有連接親和的，但是也會存在如果機器發生重啟後，connection tracking table 被清空的情況。

再來一個例子，我們都知道 connection tracking table 它所能使用的內存，必定是有一個閾值的。這樣在面對一些流量非常大，或者 SYN Flood 這種非正常情景的時候。當 connection tracking table 的容量到達閾值的時候，我們勢必會清理一些數據。那麼在這個時候，一個連接的 tracking 信息就很有可能被清理。那麼在這種情況下，我們怎麼樣去做 connection tracking ？

Google 選擇的做法是引入一致性 Hash

一致性 Hash：Maglev Hash#

整體算法其實有很多細節，這裡只說明大概，具體細節大家可以去閱讀原文查找

首先，我們要確定經過預處理後的產物 lookup table 的長度 M。所有 Key 都會被 hash 到這個 lookup table 中去，而 lookup table 中的每個元素都會被映射到一個 Node 上

而計算 lookup table 的計算分為兩步

計算每一個 node 對於每一個 lookup table 項的一個取值（也就是原文中提到的 permutation）；
根據這個值，去計算每一個 lookup table 項所映射到的 node（放在 entry 中，此處 entry 用原文的話來講就是叫做 the final lookup table）。

permutation 是一個 M×N 的矩陣，列對應 lookup table，行對應 node。為了計算 permutation，需要挑選兩個 hash 算法，分別計算兩個值 offset 與 skip 。最後根據 offset 和 skip 的值來填充 permutation，計算方式描述如下：

offset ← h 1 (name[i]) mod M
skip ← h 2 (name[i]) mod (M − 1)+ 1
permutation[i][j] ← (offset+ j × skip) mod M

其中 i 是 Node Table 中 Node 的下標，j 是 lookup table 下標

在計算完 permutation 後，我們就可以計算最後的 lookup table 了，這個 table 用一維的數組表示

這裡貼一張圖，大家可以配合下面的代碼一起看一下

from typing import List

# 根據已經計算好的 permutation 來計算 lookup_table
def calculate_lookup_table(n: int, m: int, permutation: List[List[int]]) -> List[int]:
    # result 是最終記錄分布的 Hash 表
    result: List[int] = [-1] * m
    # next 是用來解決衝突的，在遍歷過程中突然想要填入的 entry 表已經被占用，
    # 則通過 next 找到下一行。一直進行該過程直到找到一個空位。
    # 因為每一列都包含有 0~M-1 的每一個值，所以最終肯定能遍歷完每一行。
    # 計算複雜度為 O(M logM) ~ O(M^2)
    next: List[int] = [0] * n
    flag = 0
    while True:
        for i in range(n):
            x = permutation[i][next[i]]
            while True:
                # 找到空位，退出查找
                if result[x] == -1:
                    break
                next[i] += 1
                x = permutation[i][next[i]]
            result[x] = i
            next[i] += 1
            flag += 1
            # 表已經填滿，退出計算
            if flag == m:
                return result

在這裡我們能看到，這段循環代碼必然結束，而最壞情況下，複雜度會非常高，最壞的情況可能會到 O (M^2)。原文中建議找一個遠大於 N 的 M （To avoid this happening we always choose M such that M ≫ N.）可以使平均複雜度維持在 O (MlogM)

而 Maglev 中 Google 自研的一致性算法性能怎麼樣呢？論文中也做了測試

可以看到，對於不同大小的 lookup table，Maglev 表現出了更好的均衡性

說實話，Maglev 在我看來本質上是一個帶虛節點的 Hash，說實話，我沒想到為什麼 Google 不用 Dynamo 等已經比較成熟的 Hash ？難道是因為政策原因？（畢竟 Dynamo 是 AWS 家的嘛（逃。BTW Enovy 也實現了 Maglev 。參見 Evaluate other consistent hash LB algorithms ，而且引入了權重，實現的挺不錯，有興趣的同學可以去看看（逃

說實話，Maglev Hash 還有很多細節沒有講，不過實在懶得寫了，，等後面出一個一致性 Hash 的分析博客吧，Flag++

Maglev 優化#

前面我們已經把 Maglev 這一套的基本原理講的差不多了。但是如果作為一個生產上大規模使用的 LB ，那麼勢必還需要針對細節做很多優化，由於這裡涉及到很多方面，我這裡只簡單介紹一下，剩下的還是建議大家直接去讀原文

分段數據包的處理#

熟悉網路的同學都知道，在基於 IP 協議傳輸報文的時候，受限於 MTU 的大小，在傳輸的時候，可能會存在數據分片傳輸的情況，而這些分片後的數據不一定會帶有完整的五元組信息。比如一個數據被切分為兩段，那麼第一段將帶有 L3 和 L4 的頭部信息，而第二段只帶有 L3 的信息。而在傳輸過程中，因為網路關係，Maglev 無法完全保證對接收到的數據作出正確的處理

這樣問題就大了，因為數據分段的情況實際上是非常場景的。那么對於這樣的場景，Maglev 應該怎麼樣去處理？首先我們需要確定怎麼才能保證所有數據都能妥投

保證一個數據報文的不同數據段都需要由同一個 Maglev 實例處理
對於同一個數據報文的不同數據段需要能保證後端選擇結果是一致的

OK，那麼我們來看看 Google 是怎麼解決這個問題的。

首先，每個 Maglev 實例中都會有一個特殊的 backend pool ，池子中是該 Maglev 集群中所有的實例。當接收到數據後，Maglev 會先根據三元組（源地址，目標地址，協議簇）計算 hash ，然後選擇一個 Maglev 實例進行轉發，這樣就能保證同一數據報文的不同分段能傳輸到同一個 Maglev 實例上。當然這裡需要利用 GRE 的遞歸控制來避免無限循環。

好了我們來看看條件 2 怎麼滿足。在每個 Maglev 實例上會維護一個特殊的表，記錄數據分片後第一個數據端的轉發結果。以前面的例子為例，當一個報文的第二個分段抵達的時候，Maglev 會查詢表中是否存在第一個數據段的轉發結果。如果存在則直接轉發，如果不存在，則將這個數據段緩存，直到第一個數據段抵達，或者到達超時閾值

監控與調試#

真正的用時都是不需要調試（劃掉）（笑，Google 為了這一套系統設計了輔助的監控與調試手段來幫助日常的開發迭代。

在監控這邊，分為黑盒和白盒兩種監控手段。比如遍布全球的特定監控節點，以確認 VIP 的健康狀態。當然與之配套的還有一整套白盒監控。Google 會監控具體的伺服器指標，同時會監控 Maglev 本身的指標

當然與之配套的還有一些調試工具。比如 Google 開發了一套類似 X-Trace 的 packettracer。可以通過 packettracer 來發送一些帶有特定標頭和 payload 的信息。當 Maglev 接到這樣一些特殊的數據包後，除了照常轉發數據包以外，也會講一些關鍵信息上報到指定位置

這實際上也體現了軟負載均衡相較於硬體負載均衡的一個好處，無論可調試性還是可迭代性都是硬體負載均衡無法媲美的

總結#

這篇文章其實我讀了挺久，裡面很多細節挺值得慢慢深究的，所以再次建議大家一定要去找原文讀一下，非常不錯。另外順便推薦一篇文章，是美團技術團隊的作品，他們也參考了 Maglev 來實現自己的高性能 L4 負載均衡，參見MGW—— 美團點評高性能四層負載均衡

好了，這篇文章，就先到這裡吧，這篇文章應該是我寫的最耗時的一篇文章了。。不過想想後面還有幾篇文章要寫，頭就很大

溜了溜了