Redis Clusterクラスタ内のデータ分散アルゴリズムについてお話しましょう

最近、Redis Cluster に注目していますが、これにはデータ分散の問題が関係しています。Redis Cluster はマルチマスター構造であるため、各マスターはストレージ サービスを提供できますが、これにはデータ分散の問題が関係しています。そこで、この機会に分散システムにおけるデータ分散アルゴリズムについてお話ししましょう。新しい Redis バージョンでは、仮想スロット パーティショニング テクノロジを使用してデータ分散の問題を解決しています。仮想スロット パーティショニング テクノロジの詳細については、後ほど紹介します。仮想スロットパーティショニング技術に加えて、ハッシュアルゴリズムやコンシステントハッシュアルゴリズムなど、分散クラスターにはいくつかのデータ分散アルゴリズムがあります。この記事では、これらのデータ分散アルゴリズムについて説明します。

[[285493]]

クラスターなので、大前提が必要です。この記事では、Redis クラスターに 3 つのマスターがあり、保存する必要があるデータセットが [{id:1,"name":"1"},{id:2,name:"2"},{id:3,name:"3"},{id:4,name:"4"},{id:5:"name":"5"},{id:6,"name":"6"}] であると仮定します。この大前提の下で、クラスター内のデータ分散アルゴリズムについて説明しましょう。

ハッシュアルゴリズム

ハッシュ アルゴリズムは、分散アーキテクチャで広く使用されており、データ ストレージだけでなく、負荷分散やその他のアプリケーションにも使用されています。ハッシュ アルゴリズムの考え方は非常に単純です。おそらく、HashMap のハッシュ関数をご存知でしょう。ハッシュ アルゴリズムは HashMap と同じです。これもハッシュ関数を使用して数値を取得し、その数値に基づいて対応するサーバーを検索します。ハッシュ アルゴリズムのハッシュ関数は比較的単純です。一般的には、キーの値、または現在利用可能なマスター ノードの数を法とするキーのハッシュ値に基づいており、その法の値に基づいて特定のサーバーが取得されます。ハッシュ アルゴリズム サービス構造モデル図を下図に示します。

ハッシュアルゴリズム構造モデル図

先ほど想定したデータを使用してハッシュ アルゴリズムを試し、分散システムにおけるハッシュ アルゴリズムの適用についての理解を深めてみましょう。ハッシュ アルゴリズムのハッシュ関数が「id % マスター ノードの数」であり、結果が 0 のデータは server1 に保存され、結果が 1 のデータは server2 に保存され、結果が 2 のデータは server3 に保存されると仮定します。

したがって、ハッシュ アルゴリズムの後、id=3、id=6 のデータとマスター ノードの数は 0 を法とする法 (3%3=0、6%3=0) であるため、これら 2 つのデータは server1 に保存されます。同様に、id=1、id=4 のデータは server2 に保存され、id=2、id=5 のデータは server3 に保存されます。このとき、サーバーのストレージ データは次の図のようになります。

サーバーストレージデータ

これが分散におけるハッシュアルゴリズムの役割です。比較的単純です。ハッシュ関数が適切に設計されていれば、データは各サーバーに均等に分散されることがわかります。ただし、ハッシュアルゴリズムには致命的な欠点があります。スケーラビリティが非常に低いのです。たとえば、クラスターでサーバー 3 がクラッシュしたとします。この時点で、クラスター内で使用可能なマシンは 2 台しかありません。このようにすると、ハッシュ関数は id % 2 になり、問題が発生します。すべてのデータを再計算し、新しいストレージノードを見つける必要があります。サーバーがクラッシュしたり、マシンが追加されたりするたびに、大量のデータ移行が必要になり、システムの可用性と安定性が悪化します。

一貫性ハッシュアルゴリズム

コンシステント ハッシュ アルゴリズムは、ハッシュ アルゴリズムのアップグレード版とも言え、ハッシュ アルゴリズムのスケーラビリティが低いという問題を解決します。コンシステント ハッシュ アルゴリズムは、ハッシュ アルゴリズムとは異なります。コンシステント ハッシュ アルゴリズムは、ハッシュ関数を介して、サーバーとデータをエンドツーエンドで接続されたハッシュ リングにマッピングします。ストレージ ノードのマッピングは、IP アドレスに従ってハッシュできます。データがハッシュ リングにマッピングされた後、ストレージ ノードは時計回りに検索されます。つまり、リング上でデータがマッピングされている位置から始めて、時計回りに最初に見つかったストレージ ノードがこのノードに格納されます。

データの保存にはコンシステント ハッシュ アルゴリズムを使用します。コンシステント ハッシュ アルゴリズムの結果をシミュレートする図を描きました。

一貫性アルゴリズムシミュレーションストレージ図

まずこの図を解釈してみましょう。コンシステントハッシュアルゴリズムの規則によると、データは時計回りに検索されるため、id = 4のデータはserver1に保存され、id = 2のデータはserver2に保存され、id = 3、id = 1、id = 5、id = 6のデータはすべてserver3に保存されます。もっと敏感であれば、コンシステントハッシュアルゴリズムの欠点に気付くかもしれません。図からわかるように、6つのデータは不均等に分散されています。すべてのサーバーが2つのデータを保存するわけではなく、ギャップが少し大きいようです。ここで、コンシステントハッシュアルゴリズムの欠点について話す必要があります。コンシステントハッシュアルゴリズムは、不均等なデータ分散またはデータスキューの問題を引き起こします。図に示すように、不均等なデータ分散により、特定のノードに過度の負荷がかかり、ダウンタイムが発生する可能性があります。データの不均一な分散を引き起こす状況は 2 つあります。

• まず、ハッシュ関数が原因です。ハッシュ関数の後、サーバーはハッシュリング上で不均等に分散され、サーバー間の距離が等しくないため、データが不均等になります。
• 2 つ目: サーバーがクラッシュした場合、後続のノードはクラッシュしたマシンに元々属していたデータを保持する必要があり、これもデータの不均一性を引き起こします。

先ほど、コンシステント ハッシュ アルゴリズムはハッシュ アルゴリズムのスケーラビリティが低い問題を解決すると述べました。これはどのように理解すればよいでしょうか。見てみましょう。コンシステント ハッシュ アルゴリズムでは、ストレージ ノードが参加または離脱すると、そのノードの後継ノードにのみ影響します。たとえば、サーバー server3 とサービス server2 の間にサーバー ストレージ ノード server4 を追加すると、サーバー server3 にのみ影響します。サーバー server3 に元々保存されていたデータの一部はサーバー server4 に落ちますが、サーバー server1 と server2 には影響しません。このようにして、大規模なデータ移行は発生せず、スケーラビリティが向上します。

制限された負荷での一貫性のあるハッシュ

コンシステントハッシュアルゴリズムにはデータ分布の不均一性という問題があることから、Google は 2017 年にこの問題を解決するために負荷制限付きのコンシステントハッシュアルゴリズムを提案しました。負荷制限付きのコンシステントハッシュアルゴリズムの考え方は比較的単純で、ストレージノードごとにストレージ上限値を設定し、ストレージノードの追加や削除によって生じるデータの不均一性を制御します。データがコンシステントハッシュアルゴリズムに従って対応するストレージノードを見つけると、まずストレージノードがストレージ上限に達したかどうかを判断する必要があります。上限に達している場合は、ストレージノードの次のノードを時計回りに探し続けて保存する必要があります。

上記のデータストレージを改善するために、負荷が制限された一貫性のあるハッシュアルゴリズムを使用します。各サーバーノードに保存されるデータの上限を 2 に制限し、データの挿入順序は ID サイズの順序に基づいています。シミュレーション図も描きました。

制限された負荷での一貫性のあるハッシュ

この図を一緒に分析してみましょう。 データはidサイズの順に追加していくので、最初の4つのデータに問題はありません。 この時点では、サーバーは最大負荷を超えていません。 id=5のデータは、サーバーserver2とサーバーserver3の間にあります。 サーバーserver3に格納されるべきですが、この時点で、サーバーserver3にはすでにid=1とid=3のデータが保存されており、上限に達しています。 そのため、id=5のデータは時計回りにサーバーを探し続けます。 次のサーバーはserver1です。 この時点で、サーバーserver1にはid=4のデータが保存されており、上限に達していないため、id=5のデータはサーバーserver1に格納されます。 id=6のデータについても同様です。このように、負荷が制限されたコンシステント ハッシュ アルゴリズムを使用することで、コンシステント ハッシュ アルゴリズムにおけるデータ分散の不均一性の問題が解決されます。

仮想ノードによる一貫性のあるハッシュアルゴリズム

負荷が制限されたコンシステントハッシュアルゴリズムにも問題があります。つまり、各サーバーのパフォーマンス構成が異なる可能性があります。指定された数が小さすぎると、高構成のサーバーに少し無駄があります。これは、サーバー間で違いがある可能性があるためです。これをサーバー間の異質性と呼びます。サーバー間の異質性の問題を解決するために、仮想ノードを使用したコンシステントハッシュアルゴリズムと呼ばれるコンシステントハッシュアルゴリズムが導入されています。仮想ノードを使用したコンシステントハッシュアルゴリズムの核となる考え方は、各ノードのパフォーマンスに応じて各ノードに異なる数の仮想ノードを分割し、これらの仮想ノードをハッシュリングにマッピングしてから、コンシステントハッシュアルゴリズムに従ってデータをマッピングして保存することです。

仮想ノードによる一貫性のあるハッシュ アルゴリズムを実証するために、まず、サーバー server3 の構成が最も悪いと仮定します。そのため、サーバー server3 をベンチマークとして、サーバー server2 をサーバー server3 の 2 倍、サーバー server1 をサーバー server3 の 3 倍とします。この前提で、仮想ノードを確立できます。サーバー server3 の仮想ノードはサーバー server3_1、サーバー server2 には 2 つの仮想ノード、サーバー server2_1 とサーバー server2_2、サーバー server1 には 3 つの仮想ノード、サーバー server1_1、サーバー server1_2、サーバー server1_3 があると仮定します。前回同様シミュレーション絵を描きました。

仮想ノードにあるデータは対応する物理サーバーに保存されるため、仮想ノードでコンシステント ハッシュ アルゴリズムを使用した後のデータ保存結果は、id=2、id=3、id=5 のデータはサーバー server1 に保存され、id=1 のデータはサーバー server2 に保存され、id=4 および id=6 のデータはサーバー server3 に保存されます。

仮想ノードにより、構成されたサーバーはより多くのデータを保存できるため、システムの異質性の問題が解決されます。同時に、多数の仮想ノードが存在するため、データ移行中にデータは異なる物理マシンに分散されるため、データ移行中に特定のサーバーにかかる負荷が軽減され、システムの安定性を確保できます。

仮想スロットの分割

仮想スロット パーティショニングは、Redis Cluster のデフォルトのデータ分散テクノロジです。仮想スロット パーティショニングは、ハッシュ スペースと適切に分散されたハッシュ関数を巧みに使用して、すべてのデータを固定範囲の整数セットにマッピングします。この整数はスロットとして定義され、スロットの数は一般にノードの数よりもはるかに多くなります。

Redis クラスターには 16384 (0~16383) のスロットがあり、各マスターに均等に分配されます。データを保存するときは CRC16 アルゴリズムが使用されます。キーがどのスロットに属するかを計算する具体的な計算式は、スロット = CRC16 (キー)/16384 です。弊社のクラスター環境では、キーの保存または検索プロセスは次のようになります。

仮想スロット パーティショニングは、データとノードの関係を切り離します。スロットを導入することで、スロットはクラスター内のデータ管理と移行の基本単位となり、ノードの拡張と縮小の難しさが軽減されます。データがどのノードにあるかではなく、データがどのスロットにあるかだけに注意を払う必要があります。したがって、仮想スロットのパーティショニングは、均一なデータ分散とスケーラビリティの問題と比較的互換性があると言えます。

以上が、クラスター内のデータ分散技術についてお伝えしたい内容です。この記事の内容が、皆様の勉強や仕事に少しでもお役に立てれば幸いです。どうぞよろしくお願いいたします！