久しぶりにブログを書きます。簡単な論文のノートを書いてみましょう。この文章は、Google が 2016 年に発表した論文 Maglev: A Fast and Reliable Software Network Load Balancer に基づいており、彼らが内部で 2008 年から大規模に使用しているソフトウェア負荷分散システムの実装を共有しています。中には非常に興味深い詳細がたくさんありますので、どれだけ書けるかやってみます。
背景#
負荷分散の概念は皆さんもよく知っていると思いますので、ここでは詳しくは説明しません。今、Google のシナリオを考える必要があります。設計当初、Google は Google 検索や Gmail などの主要なサービスのトラフィックを処理するために、高性能な LB が必要でした。トラフィックが非常に膨大であるため、LB は大量のトラフィックを処理するために非常に強力な性能が求められます。
ここで、従来の考え方としては、専門のハードウェア負荷分散を直接使用するというものがあります。お金で解決できる問題は問題ではない（苦笑）。しかし、このようなソリューションにはいくつかの大きな問題があります。
- ハードウェア負荷分散の単一ポイントの性能が、ネットワーク全体が処理できるリクエストを決定します。
- HA に欠陥があります。単一ポイントが失敗した場合、ネットワーク全体が麻痺しないようにするためには、通常 1:1 の冗長性が必要です。
- 柔軟性とプログラミング性が欠けており、特別な操作を行いたいときに切り込むポイントがありません。
- 非常に高価です。Google ですら耐えられないほど高価です（逃げる）。
このような状況の中で、Google は独自に SLB (Software Load Balance) システムを構築することを検討し始めました。このようなシステムを構築する利点は明らかです。例えば、スケールの便利さ、HA に必要な冗長性を以前の 1:1 から N+1 に減少させることができること、カスタマイズの容易さなどです。アーキテクチャは以下の図のように進化しました。
しかし、課題も明らかです。まず、十分な性能が必要です。これにより、クラスターが十分なスループットを持つことが保証されます。同時に、接続トラッキングを行う必要があります。これにより、同じ接続のデータパケットが同じマシンに確実に配信されることが保証されます。透明なフェイルオーバーの能力を保証する必要があるかもしれません。
これらの要件が組み合わさると、これが今日話す Maglev になります。Google は 2008 年から大規模に LB システムを運用しています。
Maglev 初見#
背景知識#
Maglev について話を続ける前に、Google が現在どのように Maglev を使用しているかを理解する必要があります。以下は簡略化された示意図です。
ここで、非常に重要な概念である VIP (Virtual IP Address) を紹介する必要があります。Kubernetes を使用したことがある方は、この概念に馴染みがあるでしょう。VIP は実際にネットワークインターフェースカードにバインドされた物理 IP ではありません。近似的に言えば、これはバックエンドの一群のエンドポイントの抽象として機能します。この VIP にアクセスすると、実際にはバックエンドのエンドポイントにアクセスしていることになります。ここで、Kubernetes の例を挙げると、Pod のグループを作成した後、Pod 内で提供されるサービスを公開するために、通常は対応する Pod に関連付ける Service を作成します。Service には通常 IP があり、この IP が VIP です。Service の IP にアクセスすると、通常はバックエンドの Pod の中からランダムにリクエストを受け取る Pod が選択されます。
さて、Maglev に戻り、全体のプロセスを見てみましょう。Maglev は VIP と関連付けられ、その後 VIP を一群のルーターに透過的に渡します。ユーザーがブラウザに https://www.google.com と入力してエンターを押すと、ブラウザは DNS 解決を行います。この DNS 解決は Google の DNS サーバーによって処理されます。DNS サーバーは、ユーザーの地域に基づいて最近のクラスターの VIP を選択してユーザーに返します。その後、ブラウザは取得した VIP に基づいて接続を確立します。
ルーターが対応するパケットを受け取ると、そのパケットは VIP に属する Maglev クラスター内の任意のノードに転送されます。クラスター内の各ノードの重みは均等です。Maglev ノードがパケットを受け取ると、GRE (Generic Routing Encapsulation) を使用してパッケージングを行います。その後、対応するバックエンドエンドポイントに転送されます。
バックエンドエンドポイントがデータパケットを受け取ると、パケットを受け取り、リクエストを処理します。応答データが準備できると、パッケージング操作が行われ、VIP が送信元アドレスとして、ユーザーの IP が宛先アドレスとして、応答データがデータパケットとして操作されます。この時、バックエンドエンドポイントは DSR (Direct Server Return) を利用してデータパケットを Maglev をバイパスして直接返します。これにより、応答が大きすぎる場合に Maglev に追加の負担をかけることを避けます。実際、DSR は L4 の LB 実装、例えば HAProxy や Envoy などで広く使用されています。後日、時間があればこのことについてブログを書きたいと思います。
Maglev の構成#
前述のように、Maglev はルーターからの VIP リクエストを受け取り、対応するトラフィックを対応するバックエンドエンドポイントに転送します。各 Maglev は Controller と Forwarder で構成され、そのアーキテクチャは以下のようになります。
Controller と Forwarder は、Configuration Object を利用して関連する VIP を管理します。この Configuration Object は実際には別のシステム（登録センターと近似的に考えることができます）であり、相互に RPC を介して通信します。
Maglev マシン上で、Controller は定期的に Forwarder をチェックします。チェック結果に基づいて、すべての VIP の登録を BGP を介して提出または撤回するかどうかを決定します（すべて成功するか、すべて失敗するか、実際にはシステムの一貫性を保証するためです）。これにより、ルーターからのトラフィックが健康なマシンに送信されることが保証されます。
ルーターからの VIP トラフィックは Forwarder によって処理されます。Forwarder 内の各 VIP は 1 つ以上のバックエンドプールと関連付けられます。特別な処理がない限り、Maglev 内のバックエンドはサーバーエンドポイントです。バックエンドプールは、サービスエンドポイントの物理 IP のグループを含むことができ、他のバックエンドプールを含むこともできます。各バックエンドプールは、その特定のニーズに基づいて、いくつかの監視チェッカーを設計します。データパケットは健康なサービスにのみ転送されます。前述のように、同じサービスは複数のバックエンドプールに含まれる可能性があるため、Forwarder は具体的なアドレスに基づいて重複を排除し、追加のオーバーヘッドを避けます。
Forwarder の Config Manager は、Configuration Object から関連する構成を取得、解析、検証する責任を負います。すべての構成の提出は原子性を持ち（すべて成功するか、すべて失敗するか）、推進と解析が有効になる過程で、非常に短いギャップが存在します。この間、Maglev クラスター間の構成が非同期になる可能性があります。しかし、一貫性ハッシュが存在するため、この非常に短いギャップ内でも、大部分のリクエストは成功裏に配信されます。
Maglev の実装#
さて、これまでの話を踏まえて、Maglev システムのいくつかの実践的な詳細を見てみましょう。
概要#
ご存知の通り（前述のように）、Maglev は Forwarder によって実際にトラフィックの転送作業を担っています。以下の図でその構造を説明します。
Forwarder は NIC (Network Interface Card) からデータパケットを直接取得し、直接 NIC を介してバックエンドに転送します。この間、すべての操作はカーネルを通過しません（実際、カーネルを通過すると追加のコストが発生します）。
NIC から取得したパケットは、最初に Steering Module によって処理されます。この処理中に、Steering Module は五元組（プロトコル、宛先アドレス、宛先ポート、送信元アドレス、送信元ポート）に基づいてハッシュ計算を行います。その後、対応する Receiving Queue に転送されます。各 Receiving Queue は処理スレッドに対応しています。処理スレッドは、宛先 VIP とローカルに登録された VIP が一致しないパケットをフィルタリングします。次に、五元組のハッシュを再計算し、Connection Tracking Table から対応する値を検索します。
Connection Tracking Table には、以前の五元組ハッシュに対応するバックエンドが格納されます。検索がヒットした場合は直接再利用し、ヒットしない場合はこのパケットに新しいバックエンドを選択し、キーと値のペアを Connection Tracking Table に追加します。この時点でバックエンドが利用できない場合、このパケットは破棄されます。このパケットの検索操作が完了すると、前述のように、このパケットを書き換え、transmission queue に配置します。最後に、muxing module が transmission queue のパケットを直接 NIC を介して送信します。
ここでの問題は、Steering Module でなぜ round-robin のような一般的な戦略を考慮しないのかということです。皆さんもご存知のように、各スレッドの処理速度は一定ではありません。もし直接 round-robin を使用すると、この状況に直面した場合、データパケットの順序が乱れる可能性があります。もし重みの概念を導入して改善しようとすると、新たな複雑さが生じます。結局、スレッドの処理速度は動的に変化します。もう一つの状況は connection tracking です。持続的な接続が必要な場合、各パケットが同じマシンに送信されることを保証する必要があります。この場合、round-robin を使用すると追加の複雑さが生じます。しかし、特定の状況、例えば receive queue が満杯になったり、一貫性ハッシュが処理できない場合には、round-robin をバックアップ手段として利用します。この状況は、同じ五元組のパケットが同時に存在する場合に便利です。
データパケットの効率的な処理#
前述のように、Maglev は TCP のデータパケットに直接操作を行います。Google のトラフィックが非常に膨大であるため、実際には Maglev に良好な転送性能が求められます。さもなければ、大規模なシナリオでは、そのスループット能力が要求を満たさなくなります。Google はどうしたのでしょうか？答えは：NIC に直接操作することです。
私たちは、Linux でネットワークプログラミングを行う際、データパケットをカーネル空間からユーザー空間にコピーすることが非常にコストがかかることを知っています。そのため、L4 の負荷分散など、極端な性能が要求されるシナリオでは、皆さんはよりカーネル内で処理を行うことを好むかもしれません。これにより、状態を跨ぐコピーを避けることができます。これが LVS などのツールの考え方です。しかし、実際には、より大規模なトラフィックに対して、NIC からカーネルに至るまでの一連のフィルタ処理も非常にコストがかかります。前述のように、Maglev はデータパケットの五元組にのみ依存し、パケットのシーケンス番号やペイロードには関心を持ちません。そこで Google は「大胆なアイデア」を思いつきました！さあ、図を見てみましょう。
Google は NIC (ネットワークインターフェースカード) 上で直接プログラミングすることを選択しました。Forwarder と NIC はメモリを共有します。メモリ内には環状のデータパケットプールが維持されます。そして、Forwarder 内の steering module と muxing module はそれぞれこれらのデータパケットを処理するために 3 つのポインタを維持します。以下に詳細を説明します。
まず、steering module は 3 つのポインタを維持します。
received：受信したデータパケットを管理します。reserved：受信したが未処理のデータパケットを管理します。processed：処理が完了したデータパケットを管理します。
このプロセスはこうなります。NIC が新しいデータパケットを受信すると、received ポインタが指すメモリが変更されます。そして、データパケットがスレッドに配布され、関連する操作が完了すると、processed ポインタが指すメモリアドレスが変更されます。環状構造であるため、received と processed の間に存在するデータパケットは受信されたが未処理のパケットであり、reserved ポインタによって管理されます。
それに対応して、muxing module も 3 つのポインタを維持します。
sent：送信が完了したデータパケットを管理します。ready：送信待機中のデータパケットを管理します。recycled：回収されたデータパケットを管理します。
このプロセスはこうなります。steering module が関連するパケットの処理を完了すると、ready ポインタが指すメモリが変更され、送信待機状態になります。データパケットが送信されると、sent ポインタが指すメモリアドレスが変更されます。ready と sent の他に、recycled という状態があり、回収されたデータパケットを管理します。
このプロセスでは、データコピー操作は発生しません。実際、これによりコピーによる遅延が一部軽減されます。しかし、この方法には問題があり、ポインタが越境すると大きな追加コストが発生します。そこで Google はバッチ処理を採用し、例えば 3000 個の小さなパケットを一度に集中処理するという手法を取ります。
さらに、いくつかの追加の最適化を行う必要があります。例えば、パケット処理スレッド間でデータを共有しないことで競合を避けることや、スレッドを特定の CPU コアにバインドして性能を保証することなどです。
現在のところ、Google のこのアプローチは非常に優れた効率を示しており、平均して各パケットの処理にかかる時間は 300 ns ($10^{-9}$s) です。前述のように、Google はバッチ処理を用いてパケットを処理しますが、問題はハードウェア中断などの状況が発生した場合、処理閾値に達するまでの時間が大部分の状況よりも長くなる可能性があることです。そこで Google は 50μs ($10^{-6}$s) のタイマーを設計してこの状況に対処します。言い換えれば、ハードウェアやその他の問題により、全体のパケット処理時間が 50μs 増加する可能性があります（実際、ここで Google は自慢しているように感じます。「私たちの性能は素晴らしいですよ、ハードウェアだけがボトルネックですから」（逃げる）。
バックエンドの選択#
前述のように、Forwarder はデータパケットのバックエンドを選択します。TCP のような一般的なケースでは、同じ五元組のデータパケットを同じバックエンドノードに転送することが非常に重要です。Google は Maglev 内で connection tracking table を維持することでこの問題を解決します。パケットが到着すると、Maglev はその五元組ハッシュを計算し、テーブル内に存在するかどうかを確認します。存在しない場合は、ノードをバックエンドとして選択し、記録値をテーブルに追加します。存在する場合は直接再利用します。
これで問題がないように見えますが、Google は「いいえ、まだ問題があります！」と言います。
まず、次のようなシナリオを考えてみましょう。前述のように、Maglev の前に 1 つまたは複数のルーターが接続されており、ルーターは接続の親和性を提供しません。つまり、同じ接続のパケットが異なるマシンに送信されることを保証しません。したがって、同じ接続の異なるデータパケットが異なるマシンに送信される可能性があります。さらに、ルーターが接続の親和性を持っていると仮定しても、マシンが再起動した場合、connection tracking table がクリアされる可能性があります。
もう一つの例を挙げると、connection tracking table が使用できるメモリには必ずしも閾値があります。したがって、トラフィックが非常に大きい場合や SYN Flood のような異常な状況に直面した場合、connection tracking table の容量が閾値に達すると、いくつかのデータをクリアする必要があります。この時点で、接続のトラッキング情報がクリアされる可能性があります。このような状況で、どのように connection tracking を行うのでしょうか？
Google の選択は、一貫性ハッシュを導入することです。
一貫性ハッシュ：Maglev ハッシュ#
全体のアルゴリズムには多くの詳細がありますが、ここでは大まかな説明をします。具体的な詳細は原文を参照してください。
まず、前処理された結果 lookup table の長さ M を決定します。すべてのキーはこの lookup table にハッシュされ、lookup table の各要素はノードにマッピングされます。
lookup table の計算は 2 つのステップに分かれます。
- 各ノードが各
lookup table項目に対して値を計算します（これは原文で言及されている順列です）。 - この値に基づいて、各
lookup table項目がマッピングされるノードを計算します（ここでのエントリは原文の言葉で言うとthe final lookup tableです）。
順列は M×N の行列であり、列は lookup table に対応し、行はノードに対応します。順列を計算するためには、2 つのハッシュアルゴリズムを選択し、それぞれの値 offset と skip を計算します。最後に、offset と skip の値に基づいて順列を埋め込み、計算方法は以下のようになります。
- 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 はノードテーブル内のノードのインデックス、j は lookup table のインデックスです。
順列の計算が完了したら、最終的な lookup table を計算できます。このテーブルは 1 次元の配列で表されます。
ここで、以下のコードとともにこのループコードを見てみましょう。
from typing import List
# すでに計算された順列に基づいて lookup_table を計算します
def calculate_lookup_table(n: int, m: int, permutation: List[List[int]]) -> List[int]:
# result は最終的な記録分布のハッシュテーブルです
result: List[int] = [-1] * m
# next は衝突を解決するために使用され、探索中に突然埋め込もうとするエントリがすでに占有されている場合、
# 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 を選択することが推奨されています（このような事態を避けるために、常に M を N よりもはるかに大きく選択します）。これにより、平均的な複雑さは O (M logM) に保たれます。
Google が Maglev で独自に開発した一貫性アルゴリズムの性能はどうでしょうか？論文でもテストが行われています。
異なるサイズの lookup table に対して、Maglev はより良い均衡性を示しています。
正直なところ、Maglev は本質的に仮想ノードを持つハッシュであると思います。正直なところ、Google が Dynamo などの成熟したハッシュを使用しない理由がわかりません。政策的な理由でしょうか？（Dynamo は AWS のものですから）（逃げる）。ちなみに Envoy も Maglev を実装しています。参照 Evaluate other consistent hash LB algorithms で、重みを導入し、実装は非常に良好です。興味のある方はぜひ見てみてください（逃げる）。
正直なところ、Maglev ハッシュにはまだ多くの詳細が未説明ですが、書くのが面倒なので、後で一貫性ハッシュの分析ブログを出すことにします。フラグ ++
Maglev の最適化#
前述のように、Maglev の基本原理についてはほぼ説明しました。しかし、実際に大規模に使用される LB としては、細部に関して多くの最適化が必要です。ここでは多くの側面が関与するため、簡単に紹介するだけにします。残りは原文を直接読むことをお勧めします。
セグメントデータパケットの処理#
ネットワークに詳しい方は、IP プロトコルに基づいてメッセージを送信する際、MTU のサイズに制限され、データが分割されて送信される可能性があることを知っています。これらの分割されたデータは、必ずしも完全な五元組情報を持っているわけではありません。例えば、データが 2 つのセグメントに分割されると、最初のセグメントは L3 と L4 のヘッダー情報を持ち、2 番目のセグメントは L3 の情報のみを持ちます。送信中にネットワークの関係で、Maglev は受信したデータに対して正しい処理を行うことを完全に保証できません。
これが大きな問題です。データの分割は非常に一般的な状況です。このような状況で、Maglev はどのように処理すべきでしょうか？まず、すべてのデータが確実に配信されることを保証する方法を決定する必要があります。
- 1 つのデータメッセージの異なるデータセグメントは、同じ Maglev インスタンスによって処理される必要があります。
- 同じデータメッセージの異なるデータセグメントは、バックエンドの選択結果が一貫していることを保証する必要があります。
さて、Google がこの問題をどのように解決しているか見てみましょう。
まず、各 Maglev インスタンスには特別な backend pool があり、プール内にはその Maglev クラスター内のすべてのインスタンスが含まれています。データを受信すると、Maglev は三元組（送信元アドレス、宛先アドレス、プロトコルファミリー）に基づいてハッシュを計算し、1 つの Maglev インスタンスを選択して転送します。これにより、同じデータメッセージの異なるセグメントが同じ Maglev インスタンスに送信されることが保証されます。もちろん、無限ループを避けるために GRE の再帰制御を利用する必要があります。
次に、条件 2 を満たす方法を見てみましょう。各 Maglev インスタンスには、データが分割された後の最初のデータパケットの転送結果を記録する特別なテーブルが維持されます。前述の例を考えると、メッセージの 2 番目のセグメントが到着すると、Maglev はテーブル内に最初のデータセグメントの転送結果が存在するかどうかを確認します。存在する場合は直接転送し、存在しない場合はこのデータセグメントをキャッシュし、最初のデータセグメントが到着するまで、またはタイムアウト閾値に達するまで待機します。
監視とデバッグ#
実際の使用時にはデバッグは必要ありません（削除）（笑）。Google はこのシステムのために、日常の開発とイテレーションを支援するための補助的な監視とデバッグ手段を設計しました。
監視には、ブラックボックスとホワイトボックスの 2 種類の手段があります。例えば、VIP の健康状態を確認するために、世界中に特定の監視ノードが配置されています。もちろん、それに伴って一連のホワイトボックス監視もあります。Google は具体的なサーバー指標を監視し、同時に Maglev 自体の指標も監視します。
もちろん、それに伴っていくつかのデバッグツールもあります。例えば、Google は X-Trace に似た packettracer を開発しました。packettracer を使用して、特定のヘッダーとペイロードを持つ情報を送信できます。Maglev がこのような特殊なデータパケットを受信すると、通常のデータパケットの転送に加えて、いくつかの重要な情報を指定された場所に報告します。
これは、ソフトウェア負荷分散がハードウェア負荷分散に比べて持つ利点を示しています。デバッグ可能性やイテレーションの容易さは、ハードウェア負荷分散には及びません。
まとめ#
この記事は実際にかなりの時間をかけて読みました。中には多くの詳細があり、じっくりと深く掘り下げる価値がありますので、ぜひ原文を読んでみることをお勧めします。また、もう一つのおすすめの文章は、美団の技術チームによる作品で、彼らも Maglev を参考にして自分たちの高性能 L4 負荷分散を実現しています。参照 MGW—— 美団点评高性能四层负载均衡
さて、この記事はここまでにしましょう。この記事は私が書いた中で最も時間がかかったものです。しかし、考えてみると、まだいくつかの記事を書く必要があるので、頭が痛いです。
それでは、失礼します。