久しぶりにブログを書きます。簡単な論文のノートを書いてみましょう。この論文は Google が 2016 年に発表した Maglev: A Fast and Reliable Software Network Load Balancer からのもので、彼らの内部で 2008 年から大規模に使用されているソフトウェア負荷分散システムの実装について共有しています。中には非常に興味深い詳細がたくさんありますので、どれだけ書けるかやってみます。
背景#
負荷分散の概念は皆さんもよく知っていると思いますので、ここでは詳しくは説明しません。今、私たちは Google のシナリオを考える必要があります。設計当初、Google は Google のいくつかの重要なサービスのトラフィックを処理するために高性能な LB が必要でした。例えば、Google 検索や Gmail などです。トラフィックが非常に膨大であるため、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 の中からランダムに一つを選択してリクエストを受け取ります。
さて、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 はコントローラーとフォワーダーで構成され、そのアーキテクチャは以下のようになります。
コントローラーとフォワーダーは、Configuration Object を使用して関連する VIP を管理します。この Configuration Object は実際には別のシステム（登録センターと近似的に考えることができます）であり、相互に RPC を介して通信します。
Maglev マシン上で、コントローラーは定期的にフォワーダーをチェックします。チェック結果に基づいて、BGP を介してすべての VIP の登録を提出または撤回するかどうかを決定します（すべて成功するか、すべて失敗するか、実際にはシステムの一貫性を保証するためです）。これにより、ルーターからのトラフィックが健康なマシンに送信されることが保証されます。
ルーターからの VIP トラフィックはフォワーダーによって処理されます。フォワーダー内の各 VIP は、1 つまたは複数のバックエンドプールと関連付けられます。特別な処理がない限り、Maglev 内のバックエンドはサーバーエンドポイントです。バックエンドプールは、サービスエンドポイントの物理 IP のセットを含むことができ、他のバックエンドプールを含むこともできます。各バックエンドプールは、その特定のニーズに基づいて、いくつかの監視チェックを設計します。データパケットは健康なサービスにのみ転送されます。前述のように、同じサービスは複数のバックエンドプールに含まれる可能性があるため、フォワーダーは具体的なアドレスに基づいて重複を排除し、追加のオーバーヘッドを回避します。
フォワーダーの Config Manager は、Configuration Object から関連する設定を取得、解析、および検証する責任があります。すべての設定の提出は原子性を持ち（すべて成功するか、すべて失敗するか）、プッシュと解析が有効になるプロセスの間には非常に短いギャップが存在します。この間、Maglev クラスター間の設定が非同期になる可能性があります。しかし、一貫性ハッシュの存在により、この非常に短いギャップ内で大部分のリクエストは成功裏に配信されることができます。
Maglev の実装#
さて、これまでの話を踏まえて、Maglev システム全体のいくつかの実践的な詳細を見てみましょう。
概要#
ご存知の通り（前述のように）、Maglev はフォワーダーによって実際のトラフィック転送の作業を担っています。以下の図でその構造を説明します。
フォワーダーは 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 を計算できます。このテーブルは一次元の配列で表されます。
ここに図を貼りますので、以下のコードと一緒に見てみてください。
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 を M ≫ N として選択します。」）。これにより、平均的な複雑さを O (MlogM) に維持できます。
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—— 美団点评高性能四层负载均衡
さて、この論文はここまでにしましょう。この論文は私が書いた中で最も時間がかかったものです。。しかし、後で書かなければならないいくつかの論文を考えると、頭が痛くなります。
それでは、失礼します。