I/O マルチプレクシング：select/poll/epoll#
私たちは TCP ソケットプログラミングモデルから、TCP ソケットの呼び出しメカニズムがシンプルな一対一の呼び出しメカニズムであり、同期ブロッキングの方法を使用していることがわかります。それでは、IO モデルをどのように改善し、同じリソースを使用してより多くのユーザーにサービスを提供できるでしょうか？
マルチプロセスモデル#
比較的伝統的な方法は、マルチプロセスモデルを使用することです。つまり、各クライアントにリクエストを処理するためのプロセスを割り当てます。
サーバーの主プロセスはクライアントの接続を監視し、クライアントとの接続が完了すると、accept () 関数は「接続済みソケット」を返します。この時、fork () 関数を使用して子プロセスを作成し、実際には親プロセスのすべての関連するものをコピーします。これにはファイルディスクリプタ、メモリアドレス空間、プログラムカウンタ、実行中のコードなどが含まれます。
この 2 つのプロセスがコピーされたとき、ほぼ同じです。ただし、返り値によって親プロセスか子プロセスかを区別します。返り値が 0 の場合は子プロセスであり、他の整数の場合は親プロセスです。
子プロセスは親プロセスのファイルディスクリプタをコピーするため、「接続済みソケット」を使用してクライアントと通信できます。
子プロセスは「リスニングソケット」を気にする必要がなく、「接続済みソケット」のみを気にすればよいです。逆に、親プロセスはクライアントサービスを子プロセスに処理させるため、「接続済みソケット」を気にする必要がなく、「リスニングソケット」のみを気にすればよいです。
以下の図は、接続要求から接続確立まで、親プロセスが子プロセスを作成してクライアントサービスを提供する様子を示しています。
また、「子プロセス」が終了すると、実際にはカーネル内にそのプロセスのいくつかの情報が保持され、メモリを占有します。「回収」作業を適切に行わないと、ゾンビプロセスになり、ゾンビプロセスが増えると、システムリソースが徐々に枯渇します。
したがって、親プロセスは自分の子供を「善後処理」する必要があります。どうやって善後処理するのでしょうか？子プロセスが終了した後にリソースを回収するために、wait () および waitpid () 関数を呼び出す 2 つの方法があります。
このように、複数のプロセスを使用して複数のクライアントに対応する方法は、100 クライアントにはまだ実行可能ですが、クライアントの数が 1 万に達すると、確実に耐えられません。なぜなら、プロセスを生成するたびに、必ず一定のシステムリソースを占有し、プロセス間のコンテキストスイッチの「負担」は非常に重く、パフォーマンスが大幅に低下するからです。
プロセスのコンテキストスイッチには、仮想メモリ、スタック、グローバル変数などのユーザースペースのリソースだけでなく、カーネルスタック、レジスタなどのカーネルスペースのリソースも含まれます。
マルチスレッドモデル#
プロセス間のコンテキストスイッチの「負担」が重いので、より軽量なモデルを使用して複数のユーザーのリクエストに対応しましょう —— マルチスレッドモデルです。
スレッドはプロセス内で実行される「論理フロー」であり、単一のプロセス内で複数のスレッドを実行できます。同じプロセス内のスレッドは、ファイルディスクリプタリスト、プロセス空間、コード、グローバルデータ、ヒープ、共有ライブラリなど、プロセスの一部のリソースを共有できます。これらの共有リソースはコンテキストスイッチ時に切り替える必要がなく、スレッドのプライベートデータ、レジスタなどの非共有データのみを切り替える必要があるため、同じプロセス内のスレッドのコンテキストスイッチのオーバーヘッドはプロセスよりもはるかに小さいです。
サーバーがクライアント TCP との接続を完了した後、pthread_create () 関数を使用してスレッドを作成し、「接続済みソケット」のファイルディスクリプタをスレッド関数に渡し、次にスレッド内でクライアントと通信して並行処理を実現します。
接続ごとにスレッドを作成し、スレッドが実行を終えた後、オペレーティングシステムはスレッドを破棄する必要があります。スレッド切り替えのオーバーヘッドは大きくありませんが、スレッドを頻繁に作成および破棄すると、システムのオーバーヘッドも無視できません。
したがって、スレッドプールの方法を使用してスレッドの頻繁な作成と破棄を回避できます。スレッドプールとは、あらかじめいくつかのスレッドを作成しておくことです。新しい接続が確立されると、この接続済みソケットをキューに入れ、スレッドプール内のスレッドがキューから「接続済みソケット」を取り出して処理します。
注意が必要なのは、このキューはグローバルであり、各スレッドが操作します。マルチスレッド競合を避けるために、スレッドはこのキューを操作する前にロックをかける必要があります。
上記のプロセスまたはスレッドモデルに基づく方法には、実際には問題があります。新しい TCP 接続が到着すると、プロセスまたはスレッドを割り当てる必要があります。C10K を達成するには、1 台のマシンが 1 万の接続を維持する必要があり、これは 1 万のプロセス / スレッドを維持することに相当します。オペレーティングシステムは、たとえ死に物狂いでも耐えられません。
I/O マルチプレクシング#
各リクエストにプロセス / スレッドを割り当てる方法が適切でない場合、1 つのプロセスを使用して複数のソケットを維持することは可能でしょうか？答えは「はい」であり、それがI/O マルチプレクシング技術です。
1 つのプロセスは、任意の時点で 1 つのリクエストしか処理できませんが、各リクエストのイベントの処理時間を 1 ミリ秒以内に制御することで、1 秒間に数千のリクエストを処理できます。時間を長く見ると、複数のリクエストが 1 つのプロセスを再利用することになります。これがマルチプレクシングであり、この考え方は CPU が複数のプロセスを並行して処理することに非常に似ているため、タイムシェアリングマルチプレクシングとも呼ばれます。
私たちがよく知っている select/poll/epoll は、カーネルがユーザーモードに提供するマルチプレクシングシステムコールであり、プロセスはシステムコール関数を介してカーネルから複数のイベントを取得できます。
select/poll/epoll は、ネットワークイベントをどのように取得するのでしょうか？イベントを取得する際、まずすべての接続（ファイルディスクリプタ）をカーネルに渡し、次にカーネルがイベントが発生した接続を返します。その後、ユーザーモードでこれらの接続に対応するリクエストを処理します。
select/poll/epoll の 3 つのマルチプレクシングインターフェースは、すべて C10K を実現できますか？次に、それぞれについて説明します。
select/poll#
select がマルチプレクシングを実現する方法は、接続済みソケットをすべてファイルディスクリプタ集合に入れ、次に select 関数を呼び出してファイルディスクリプタ集合をコピーしてカーネルに渡し、カーネルがネットワークイベントが発生したかどうかを確認します。確認方法は非常に粗雑で、ファイルディスクリプタ集合を遍歴することによって行われます。イベントが発生したソケットを確認すると、そのソケットを読み取り可能または書き込み可能としてマークし、次にファイルディスクリプタ集合全体をユーザーモードにコピーします。その後、ユーザーモードは再び遍歴の方法で読み取り可能または書き込み可能なソケットを見つけて処理します。
したがって、select のこの方法では、ファイルディスクリプタ集合を 2 回「遍歴」する必要があります。1 回はカーネルモードで、もう 1 回はユーザーモードであり、さらにファイルディスクリプタ集合を 2 回「コピー」する必要があります。最初にユーザースペースからカーネルスペースに渡し、カーネルが変更した後、再びユーザースペースに渡します。
select は固定長の BitsMap を使用してファイルディスクリプタ集合を表し、サポートされるファイルディスクリプタの数には制限があります。Linux システムでは、カーネル内の FD_SETSIZE によって制限され、デフォルトの最大値は 1024 であり、0〜1023 のファイルディスクリプタしか監視できません。
poll は、BitsMap を使用して関心のあるファイルディスクリプタを保存するのではなく、動的配列を使用し、リンクリスト形式で組織します。これにより、select のファイルディスクリプタの数の制限を突破しますが、もちろんシステムのファイルディスクリプタの制限を受けます。
しかし、poll と select には本質的な違いはなく、どちらも「線形構造」を使用してプロセスが関心を持つソケット集合を保存するため、ファイルディスクリプタ集合を遍歴して読み取り可能または書き込み可能なソケットを見つける必要があります。時間計算量は O (n) であり、ユーザーモードとカーネルモード間でファイルディスクリプタ集合をコピーする必要があります。この方法は、同時接続数が増えると、性能の損失が指数関数的に増加します。
epoll#
epoll は 2 つの側面から select/poll の問題をうまく解決しました。
第一に、epoll はカーネル内で赤黒木を使用してプロセスが検出を待っているすべてのファイルディスクリプタを追跡します。監視する必要のあるソケットを epoll_ctl () 関数を介してカーネル内の赤黒木に追加します。赤黒木は効率的なデータ構造であり、追加、削除、変更の一般的な時間計算量は O (logn) です。select/poll はカーネル内に epoll の赤黒木のようなすべての検出待ちのソケットを保存するデータ構造がないため、select/poll は毎回操作するたびにすべてのソケット集合をカーネルに渡しますが、epoll はカーネルが赤黒木を維持しているため、すべての検出待ちのソケットを保存でき、1 つの待機ソケットを渡すだけで済みます。これにより、カーネルとユーザースペース間の大量のデータコピーとメモリ割り当てが削減されます。
第二に、epoll はイベント駆動メカニズムを使用し、カーネル内で準備完了イベントを記録するリンクリストを維持します。特定のソケットにイベントが発生した場合、コールバック関数を介してカーネルはそのソケットをこの準備完了イベントリストに追加します。ユーザーが epoll_wait () 関数を呼び出すと、イベントが発生したファイルディスクリプタの数のみが返され、select/poll のようにソケット集合全体をポーリングしてスキャンする必要がなく、検出の効率が大幅に向上します。
以下の図から、epoll に関連するインターフェースの役割を確認できます：
epoll の方法は、監視するソケットの数が増えても効率が大幅に低下せず、同時に監視できるソケットの数も非常に多くなります。上限はシステムが定義するプロセスが開く最大ファイルディスクリプタの数です。したがって、epoll は C10K 問題を解決するための強力なツールと見なされています。
エッジトリガーとレベルトリガー#
epoll は 2 つのイベントトリガーモードをサポートしています。エッジトリガー（edge-triggered、ET）とレベルトリガー（level-triggered、LT）です。
- エッジトリガーモードを使用する場合、監視されているソケットディスクリプタに読み取り可能なイベントが発生したとき、サーバー側は epoll_wait から 1 回だけ目覚めます。プロセスが read 関数を呼び出してカーネルからデータを読み取らなくても、1 回だけ目覚めます。したがって、プログラムはカーネルバッファ内のデータを一度に読み取ることを保証する必要があります。
- レベルトリガーモードを使用する場合、監視されているソケットに読み取り可能なイベントが発生したとき、サーバー側は epoll_wait から繰り返し目覚め、カーネルバッファのデータが read 関数によって読み取られるまで続きます。目的は、読み取る必要のあるデータがあることを知らせることです。
レベルトリガーの意味は、イベントの条件が満たされている限り、たとえばカーネルにデータが読み取る必要がある場合、そのイベントをユーザーに繰り返し伝えることです。一方、エッジトリガーの意味は、条件が最初に満たされたときのみトリガーされ、その後は同じイベントが再度伝えられないことです。
レベルトリガーモードを使用する場合、カーネルがファイルディスクリプタを読み取り可能または書き込み可能として通知すると、その後もその状態を検出し続けることができます。したがって、通知を受け取った後、できるだけ多くの読み取りおよび書き込み操作を実行する必要はありません。
エッジトリガーモードを使用する場合、I/O イベントが発生したときは 1 回だけ通知され、どれだけのデータを読み書きできるかはわかりません。したがって、通知を受け取った後は、できるだけデータを読み書きする必要があります。そうしないと、読み書きの機会を逃すことになります。そのため、ファイルディスクリプタからデータを読み書きするためにループします。ファイルディスクリプタがブロッキングされている場合、読み書きするデータがないと、プロセスは読み書き関数でブロックされ、プログラムは続行できなくなります。したがって、エッジトリガーモードは一般にノンブロッキング I/O と組み合わせて使用され、プログラムはシステムコール（read や write など）がエラーを返すまで I/O 操作を実行し続けます。このエラータイプは EAGAIN または EWOULDBLOCK です。
一般的に、エッジトリガーの効率はレベルトリガーの効率よりも高いです。なぜなら、エッジトリガーは epoll_wait のシステムコールの回数を減らすことができ、システムコールにも一定のオーバーヘッドがあるからです。select/poll はレベルトリガーモードのみを持ち、epoll のデフォルトのトリガーモードはレベルトリガーですが、アプリケーションシーンに応じてエッジトリガーモードに設定できます。
さらに、I/O マルチプレクシングを使用する際は、ノンブロッキング I/O と組み合わせて使用することをお勧めします。マルチプレクシング API が返すイベントは必ずしも読み書き可能ではありません。ブロッキング I/O を使用すると、read/write を呼び出すとプログラムがブロックされるため、ノンブロッキング I/O と組み合わせて、極少数の特殊な状況に対処するのが最善です。
高性能ネットワークモード：Reactor と Proactor#
Reactor#
先ほど、I/O マルチプレクシングを通じてネットワークの高性能を達成できると言いましたが、I/O マルチプレクシングインターフェースを使用してネットワークプログラムを書くのは手続き型の方法であり、開発効率は高くありません。
そこで、偉大な人々はオブジェクト指向の考え方に基づいて I/O マルチプレクシングに一層のラッピングを施し、ユーザーが低レベルのネットワーク API の詳細を考慮せず、アプリケーションコードの作成に集中できるようにしました。この低レベルのモデルがReactor モデルです。
Reactor モデルは Dispatcher モデルとも呼ばれ、I/O マルチプレクシングがイベントをリッスンし、イベントを受信した後、イベントの種類に応じて特定のプロセス / スレッドに割り当て（Dispatch）します。
Reactor モデルは主に Reactor と処理リソースプールの 2 つのコア部分で構成されており、それぞれの役割は次のとおりです：
- Reactor はイベントをリッスンして分配し、イベントの種類には接続イベント、読み書きイベントが含まれます。
- 処理リソースプールはイベントを処理します。たとえば、read -> ビジネスロジック -> send などです。
Reactor モデルは柔軟で多様であり、さまざまなビジネスシーンに対応できます。柔軟性は次のように表れます：
- Reactor の数は 1 つだけでも、複数でも構いません。
- 処理リソースプールは単一のプロセス / スレッドでも、複数のプロセス / スレッドでも構いません。
次に、3 つの古典的な Reactor ソリューションをそれぞれ紹介します。
単一 Reactor 単一プロセス / スレッド#
プロセス内には Reactor、Acceptor、Handler の 3 つのオブジェクトがあります：
- Reactor オブジェクトの役割はイベントをリッスンして分配することです。
- Acceptor オブジェクトの役割は接続を取得することです。
- Handler オブジェクトの役割はビジネスを処理することです。
オブジェクト内の select、accept、read、send はシステムコール関数であり、dispatch と「ビジネス処理」は完了する必要がある操作です。その中で dispatch はイベントを分配する操作です。
次に、「単一 Reactor 単一プロセス」のこのソリューションを紹介します：
- Reactor オブジェクトは select（I/O マルチプレクシングインターフェース）を介してイベントをリッスンし、イベントを受信した後、dispatch を介して分配します。具体的には、Acceptor オブジェクトまたは Handler オブジェクトに分配されますが、受信したイベントの種類によります。
- 接続確立イベントの場合、Acceptor オブジェクトが処理を担当します。Acceptor オブジェクトは accept メソッドを介して接続を取得し、後続の応答イベントを処理するために Handler オブジェクトを作成します。
- 接続確立イベントでない場合は、現在の接続に対応する Handler オブジェクトが応答を担当します。
Handler オブジェクトは read -> ビジネス処理 -> send のプロセスを通じて完全なビジネスプロセスを完了します。
単一 Reactor 単一プロセスのソリューションは、すべての作業が同じプロセス内で完了するため、実装が比較的簡単で、プロセス間通信を考慮する必要がなく、マルチプロセス競合を心配する必要もありません。
しかし、このソリューションには 2 つの欠点があります：
- 1 つのプロセスしかないため、マルチコア CPU の性能を十分に活用できません。
- 2 つ目の欠点は、Handler オブジェクトがビジネス処理を行っている間、プロセス全体が他の接続のイベントを処理できないことです。ビジネス処理が長時間かかる場合、応答の遅延が発生します。
したがって、単一 Reactor 単一プロセスのソリューションは、計算集約型のシーンには適しておらず、ビジネス処理が非常に迅速なシーンにのみ適しています。
Redis は C 言語で実装されており、Redis 6.0 バージョン以前では「単一 Reactor 単一プロセス」のソリューションを採用していました。なぜなら、Redis のビジネス処理は主にメモリ内で完了し、操作の速度が非常に速く、性能のボトルネックが CPU にないため、Redis はコマンドの処理を単一プロセスのソリューションで行っています。
単一 Reactor マルチスレッド / マルチプロセス#
「単一 Reactor 単一スレッド / プロセス」ソリューションの欠点を克服するには、マルチスレッド / マルチプロセスを導入する必要があります。これにより、単一 Reactor マルチスレッド / マルチプロセスのソリューションが生まれます。
名前を聞くよりも図を見る方が良いので、まず「単一 Reactor マルチスレッド」ソリューションの図を見てみましょう：
このソリューションについて詳しく説明します：
- Reactor オブジェクトは select（I/O マルチプレクシングインターフェース）を介してイベントをリッスンし、イベントを受信した後、dispatch を介して分配します。具体的には、Acceptor オブジェクトまたは Handler オブジェクトに分配されますが、受信したイベントの種類によります。
- 接続確立イベントの場合、Acceptor オブジェクトが処理を担当します。Acceptor オブジェクトは accept メソッドを介して接続を取得し、後続の応答イベントを処理するために Handler オブジェクトを作成します。
- 接続確立イベントでない場合は、現在の接続に対応する Handler オブジェクトが応答を担当します。
上記の 3 つのステップは単一 Reactor 単一スレッドソリューションと同じですが、次のステップから異なります：
- Handler オブジェクトはビジネス処理を担当せず、データの受信と送信のみを担当します。Handler オブジェクトは read を介してデータを読み取った後、データを子スレッド内の Processor オブジェクトに送信してビジネス処理を行います。
- 子スレッド内の Processor オブジェクトがビジネス処理を行い、処理が完了したら結果を主スレッド内の Handler オブジェクトに送信し、Handler は send メソッドを介して応答結果をクライアントに送信します。
- 単一 Reactor マルチスレッドのソリューションの利点は、マルチコア CPU の性能を十分に活用できることです。マルチスレッドを導入することで、当然、マルチスレッド競合リソースの問題も生じます。
たとえば、子スレッドがビジネス処理を完了した後、結果を主スレッドの Handler に送信する必要があります。ここでは共有データの競合が関与します。
マルチスレッドが共有リソースの競合によりデータの混乱を引き起こさないようにするには、共有リソースを操作する前にミューテックスを追加して、任意の時間に 1 つのスレッドのみが共有リソースを操作できるようにし、そのスレッドが操作を完了してミューテックスを解放した後、他のスレッドが共有データを操作できるようにする必要があります。
単一 Reactor マルチスレッドソリューションについて話した後、次に単一 Reactor マルチプロセスソリューションを見てみましょう。
実際、単一 Reactor マルチプロセスは単一 Reactor マルチスレッドよりも実装が難しいです。主な理由は、子プロセス <-> 親プロセスの双方向通信を考慮する必要があり、親プロセスは子プロセスがどのクライアントにデータを送信するかを知る必要があるからです。
一方、マルチスレッド間ではデータを共有でき、追加の競合問題を考慮する必要がありますが、プロセス間通信の複雑さよりはるかに低いです。したがって、実際のアプリケーションでは単一 Reactor マルチプロセスモデルは見られません。
さらに、「単一 Reactor」モデルには別の問題があります。1 つの Reactor オブジェクトがすべてのイベントのリッスンと応答を担当し、主スレッド内でのみ実行されるため、瞬時の高並列シーンに直面すると、性能のボトルネックになりやすいです。
マルチ Reactor マルチプロセス / スレッド#
「単一 Reactor」の問題を解決するには、「単一 Reactor」を「マルチ Reactor」に実装する必要があります。これにより、マルチ Reactor マルチプロセス / スレッドのソリューションが生まれます。
お決まりのように、名前を聞くよりも図を見る方が良いです。マルチ Reactor マルチプロセス / スレッドソリューションの図は以下の通りです（スレッドの例）：
このソリューションの詳細は以下の通りです：
- 主スレッド内の MainReactor オブジェクトは select を介して接続確立イベントを監視し、イベントを受信した後、Acceptor オブジェクトの accept を介して接続を取得し、新しい接続を特定の子スレッドに割り当てます。
- 子スレッド内の SubReactor オブジェクトは、MainReactor オブジェクトから割り当てられた接続を select に追加して引き続き監視し、接続の応答イベントを処理するための Handler を作成します。
- 新しいイベントが発生した場合、SubReactor オブジェクトは現在の接続に対応する Handler オブジェクトを呼び出して応答します。
- Handler オブジェクトは read -> ビジネス処理 -> send のプロセスを通じて完全なビジネスプロセスを完了します。
マルチ Reactor マルチスレッドのソリューションは、見た目は複雑ですが、実際の実装は単一 Reactor マルチスレッドソリューションよりもはるかに簡単です。その理由は次のとおりです：
- 主スレッドと子スレッドの役割が明確で、主スレッドは新しい接続の受信のみを担当し、子スレッドは後続のビジネス処理を担当します。
- 主スレッドと子スレッドの相互作用は非常にシンプルで、主スレッドは新しい接続を子スレッドに渡すだけで、子スレッドはデータを返す必要はなく、直接子スレッド内で処理結果をクライアントに送信できます。
有名なオープンソースソフトウェアである Netty と Memcache は、いずれも「マルチ Reactor マルチスレッド」ソリューションを採用しています。
「マルチ Reactor マルチプロセス」ソリューションを採用しているオープンソースソフトウェアは Nginx ですが、標準のマルチ Reactor マルチプロセスとはいくつかの違いがあります。
具体的な違いは、主プロセスがソケットを初期化するためだけに使用され、接続を受け入れるための mainReactor を作成せず、子プロセスの Reactor が接続を受け入れ、ロックを使用して 1 回に 1 つの子プロセスのみが accept を実行できるようにします（スパム現象を防ぐため）。子プロセスが新しい接続を受け入れると、その接続は自分の Reactor で処理され、他の子プロセスに割り当てられることはありません。
Proactor#
Reactor はノンブロッキング同期ネットワークモデルですが、Proactor は非同期ネットワークモデルです。
Reactor は「イベントが発生したとき、オペレーティングシステムがアプリケーションプロセスに通知し、アプリケーションプロセスが処理する」と理解できます。一方、Proactor は「イベントが発生したとき、オペレーティングシステムが処理し、処理が完了したらアプリケーションプロセスに通知する」と理解できます。ここでの「イベント」とは、新しい接続、読み取り可能なデータ、書き込み可能なデータなどの I/O イベントを指し、「処理」にはドライバからカーネルへの読み取りやカーネルからユーザースペースへの読み取りが含まれます。
違いは、Reactor モデルが「未完了」の I/O イベントに基づいているのに対し、Proactor モデルは「完了した」I/O イベントに基づいていることです。
Proactor モデルの作業フローを紹介します：
- Proactor Initiator は Proactor および Handler オブジェクトを作成し、Proactor と Handler を非同期操作プロセッサに登録します。
- 非同期操作プロセッサは登録リクエストを処理し、I/O 操作を処理します。
- 非同期操作プロセッサが I/O 操作を完了すると、Proactor に通知します。
- Proactor は異なるイベントタイプに応じて異なる Handler をコールバックしてビジネス処理を行います。
- Handler はビジネス処理を完了します。
残念ながら、Linux の非同期 I/O は不完全であり、aio シリーズの関数は POSIX によって定義された非同期操作インターフェースであり、真のオペレーティングシステムレベルのサポートではなく、ユーザースペースで模擬された非同期であり、ローカルファイルに基づく aio 非同期操作のみをサポートしています。ネットワークプログラミングにおけるソケットはサポートされていないため、Linux ベースの高性能ネットワークプログラムはすべて Reactor ソリューションを使用しています。
一方、Windows ではソケットの非同期プログラミングインターフェースが完全に実装されており、このインターフェースは IOCP であり、オペレーティングシステムレベルで実装された非同期 I/O です。真の意味での非同期 I/O であるため、Windows で高性能ネットワークプログラムを実装する場合は、効率の高い Proactor ソリューションを使用できます。
一貫性ハッシュ#
分散システムでリクエストを正しく配分するには？#
システムの容量を向上させたい場合、データを水平方向に異なるノードに分割して保存します。つまり、データが異なるノードに分布します。たとえば、分散 KV（key-value）キャッシュシステムでは、特定の key がどのノードまたはノードにアクセスすべきかは確定的であり、任意のノードにアクセスしてキャッシュ結果を得ることができるわけではありません。
したがって、分散システムの負荷分散アルゴリズムを考える必要があります。
ハッシュアルゴリズム#
ハッシュアルゴリズムの最も単純な方法は、剰余演算を行うことです。たとえば、分散システムに 3 つのノードがある場合、hash (key) % 3 の公式に基づいてデータをマッピングします。
しかし、致命的な問題があります。ノードの数が変わると、つまりシステムの拡張または縮小を行うと、マッピング関係が変更されたデータを移動する必要があります。最悪の場合、すべてのデータを移動する必要があるため、データ移動の規模は O (M) です。そうしないと、データを照会できない問題が発生します。
一貫性ハッシュアルゴリズム#
一貫性ハッシュアルゴリズムも剰余演算を使用しますが、ハッシュアルゴリズムとは異なり、ハッシュアルゴリズムはノードの数に対して剰余演算を行いますが、一貫性ハッシュアルゴリズムは 2^32 に対して剰余演算を行います。これは固定値です。
一貫性ハッシュアルゴリズムは、2^32 に対する剰余演算の結果を円環として組織できます。時計のように、時計の円は 60 個の点で構成されていると理解できますが、ここではこの円を 2^32 個の点で構成される円として想像します。この円環はハッシュ環と呼ばれ、以下の図のようになります：
一貫性ハッシュは 2 段階のハッシュを行います：
- 第一段階：ストレージノードに対してハッシュ計算を行います。つまり、ストレージノードをハッシュマッピングします。たとえば、ノードの IP アドレスに基づいてハッシュを計算します。
- 第二段階：データを保存またはアクセスする際に、データに対してハッシュマッピングを行います。
したがって、一貫性ハッシュは「ストレージノード」と「データ」の両方を首尾一貫したハッシュ環にマッピングすることを指します。
問題が発生しました。「データ」に対してハッシュマッピングを行い、結果を得た後、どのノードがそのデータを保存しているかをどのように見つけるのでしょうか？
答えは、マッピングの結果値を時計回りの方向に最初のノードを見つけることです。これがそのデータを保存しているノードです。
ノード D を削除する場合、D を B に移動するだけで済みます。したがって、一貫性ハッシュアルゴリズムでは、ノードを追加または削除する場合、そのノードのハッシュ環上の時計回りの隣接ノードにのみ影響を与え、他のデータには影響を与えません。
ただし、一貫性ハッシュアルゴリズムはノードがハッシュ環上に均等に分布することを保証しません。これにより、大量のリクエストが 1 つのノードに集中する問題が発生します。
仮想ノードを使用して均衡度を向上させるには？#
ノードがハッシュ環上に不均等に分配される問題を解決するには、大量のノードが必要です。ノード数が多いほど、ハッシュ環上のノードの分布がより均等になります。したがって、この時点で仮想ノードを追加します。つまり、1 つの実ノードに対して複数のコピーを作成します。
具体的な方法は、実ノードをハッシュ環にマッピングするのではなく、仮想ノードをハッシュ環にマッピングし、仮想ノードを実ノードにマッピングすることです。したがって、ここには「2 層」のマッピング関係があります。
さらに、仮想ノードはノードの均衡度を向上させるだけでなく、システムの安定性も向上させます。ノードが変化すると、異なるノードがシステムの変化を共同で分担するため、安定性が高まります。
たとえば、特定のノードが削除されると、そのノードに対応する複数の仮想ノードも削除され、これらの仮想ノードの時計回りの次の仮想ノードは、異なる実ノードに対応する可能性があります。つまり、これらの異なる実ノードが共同でノードの変化によって引き起こされる圧力を分担します。
また、仮想ノードを使用すると、ハードウェア構成が優れたノードに重みを追加することもできます。たとえば、重みの高いノードに対してより多くの仮想ノードを追加できます。
したがって、仮想ノードを持つ一貫性ハッシュ方法は、異なるハードウェア構成のノードのシーンだけでなく、ノードの規模が変化するシーンにも適しています。