シニアアーキテクトの技術共有: 分散システムのパーティショニングの詳細な説明

データ複製は冗長なプロセスです。冗長性により可用性が向上し、読み取り負荷を効果的に分散できます。データ分割は全体を部分に変換するプロセスです。このような仕切り方は、たくさんの本があるのに本棚にすべてを収納できないので、保管用にさらに本棚をいくつか追加する必要があるようなものです。

[[274989]]

全体を小さなスペースに分割し、パーツを複数の小さなスペースに保管します。この考え方はコンピューターに適用した場合も同じです。データの量が多すぎて、単一のストレージ ノードではデータを保存するのに不十分な場合 (大容量のディスクが利用できない、または高価すぎる場合)、データを引き続き保存するには、データ セットを分解して整理する必要があります。これが、データ システムのスケーラビリティを向上させるために導入された技術的な方法であるデータ パーティショニングの重要性です。

パーティション分割方法は？

パーティショニングの鍵は、どのノードにデータを配置し、どのノードでデータを読み取るかを計算できる統一されたルールを採用することです。

これらの点を実現するために、現在 3 つのパーティション分割方法があります。

1. キー範囲によるパーティション データを保存するときに、データ内のフィールドをパーティション キーとして取得し、このフィールドの範囲でパーティションします。たとえば、自動増分 ID 値 0 ～ 10000 はノード A に格納され、10001 ～ 20000 はノード B に格納されます。このルールに基づいて、パーティション内のデータに効率的にアクセスでき、自然に区間検索 (キーの格納順序) をサポートできます。間隔範囲が 1 つのパーティションのみにある限り、検索範囲が複数のパーティションにまたがらない限り、間隔検索は 1 つのパーティションにのみアクセスします。しかし、問題は、一定期間内にデータ書き込みのホットスポットがある場合、たとえば、0 から 100000 までのキーが大量に書き込まれる一方で、10001 から 20000 までのキーが非常に少ない場合、データスキュー (データパーティションサイズの不均衡) が発生することです。
2. データの偏りについては、キー ハッシュによるパーティション分割は、異なるパーティションにデータを格納するための効率的なハッシュ関数を考える自然な方法です。ハッシュ関数が一貫している限り、同じキーが同じパーティションにマップされます。したがって、パーティショニングの重要な問題も解決できます。ただし、ハッシュの問題により、間隔範囲検索を実行することは非常に困難です。一部のデータベースでは、すべてのパーティションに間隔検索要求を送信し、それらを並列処理してから、すべての結果を集計して返します。ただし、これにより大量のリクエストが頻繁に生成されることは間違いありません。データの偏りの問題は効果的に解決できますが、このようなホット データを完全に回避する方法はありません。たとえば、大規模な V ユーザーには常に多くのファンがいて、毎日大量のデータが生成されます。キー ハッシュにより、これらのデータは同じパーティションに保存され、データの偏りやホット データへの頻繁なアクセスが発生し、読み取りと書き込みの負荷が不均等に分散されます。
3. 範囲 + ハッシュ モードでの上記の 2 種類のパーティショニングの利点と欠点は補完的です。これら 2 つを組み合わせることを検討できます。たとえば、ID やタイムスタンプなど、データ レコードの 2 つのキー フィールドをキーとして使用します。まず、ID ハッシュを使用してそれらを異なるパーティションに保存し、次にタイムスタンプを使用して範囲ごとにパーティション分割します。これにより、両者の長所と短所がある程度補われます。しかし、ホットデータの問題はまだ完全に解決されていません。現時点では、ホット データ用のキャッシュ アーキテクチャを確立するなど、ホット データの問題を解決するために他の側面も検討できます。

パーティション分割方式はデータのストレージを完璧に拡張するように見えますが、別の複雑さも生じます。つまり、データをクエリするときに、データが同じパーティションにない場合は、複数の異なるパーティションにアクセスする必要があり、リクエストのレイテンシが増加します。または、リレーショナル モデルでデータを結合する必要がある場合、データが異なるパーティションの異なるテーブルにあるため、結合が非常に困難になり、複数テーブル クエリの複雑さが増します。妥協案としては、ビジネスの観点から、同時に結合または読み取られるデータは、パーティション間の呼び出しによるパフォーマンスの低下を減らすために、できるだけ同じパーティションに配置する必要があります。これは、ディスクのアドレス指定とシーク操作の数を減らすことと同等であり、最も時間のかかる操作の発生回数を減らすことになります。

セカンダリインデックスのパーティションをどのように設計するのでしょうか?

上記の 3 つのパーティション スキームは、主キーのみをパーティション分割します。つまり、レコードの一意の識別子をパーティション分割します。ただし、データベース機能の観点からは、柔軟で効率的なクエリを実現するために、レコードの任意のフィールドに基づいてインデックスを作成する必要もあります。このようなインデックスはセカンダリ インデックスと呼ばれます。では、パーティション データベースの設計ではセカンダリ インデックスをどのように実装すればよいのでしょうか?通常、ローカル インデックスとグローバル インデックスの 2 つの設計があります。

ローカルインデックス

セカンダリ インデックスの書き込みと読み取りの両方がローカル パーティションで実行される場合、そのようなセカンダリ インデックスはローカル インデックスと呼ばれます。つまり、各パーティションのセカンダリ インデックス ファイルには、パーティションのインデックス データのみが格納されます。これの利点は、このレコードに関するすべてのセカンダリ インデックスがこのノード上にあるため、データを書き込むときにレコードのセカンダリ インデックスを更新するのが非常に便利なことです。ただし、セカンダリ インデックスを使用してレコードを読み取る場合、レコードがどのパーティションにあるかを知る方法がないため、並列クエリを実行してからクエリ結果をマージする必要があり、読み取り遅延が間違いなく増加します。

グローバルインデックス

対照的に、グローバル インデックスは、すべてのフィールドが同じパーティション内にあるセカンダリ インデックスです (異なるグローバル インデックスは異なるパーティション内にあります)。セカンダリ インデックスをクエリする場合、並列クエリなしで 1 つのノードからのみデータを読み取ることができるため、読み取り効率が非常に高くなります。しかし、データを書き込む際には、レコードに関係するセカンダリインデックスが複数のパーティションに存在する可能性があるため、複数のパーティションを操作する必要があり、分散トランザクションの一貫性などの問題が伴い、複雑さが大幅に増加し、パフォーマンスに影響を与えます。グローバル インデックスからデータを読み取る場合、インデックスが配置されているパーティションをどのように見つけるのでしょうか?答えは、範囲パーティション分割、ハッシュ パーティション分割、ハッシュ範囲パーティション分割など、グローバル セカンダリ インデックスに同じパーティション分割戦略を使用できるということです。異なるパーティション戦略も、間隔クエリの効率に影響します。

パーティションの再バランス

複数のノードに複数のパーティションがあります。データの負荷が増加すると、各パーティションのサイズも増加し続け、隠れた危険が生じます。ノードに障害が発生すると、そのノード上のすべてのパーティションが障害を起こし、データの大部分が障害を起こします。たとえば、クラスターに新しいノードが追加または削除された場合、データは新しいノードに均等に転送される必要があります (新しいノードがデータを転送する代わりに新しい書き込み要求を受け入れることは可能ですか? そうすると、一定期間にわたって書き込み要求が異なるノードに不均衡になり、新しいノードへの要求の数が多くなると負荷が不均衡になります)。上記の問題は、パーティション再バランス機能を導入する理由としてまとめられており、可用性とスケーラビリティのために、パーティション再バランスは不可欠な機能です。

パーティションの固定数

拡張を容易にするために、パーティションの数はノードの数と異なる必要があります。その理由は、パーティションの数がノードの数と同じであると仮定すると、ノードの数を係数としてデータがどのパーティションに割り当てられるかが決まるからです。この係数は隠れた危険を引き起こします。ノードを追加または削除すると、係数番号が変わり、以前のデータを正しいパーティションにルーティングできなくなるため、再バランス調整を実行し、すべてのデータを再パーティション化する必要があります (ハッシュマップの再ハッシュと同様)。これにより、すべてのデータが移行状態になり、クラスター全体が使用できなくなります。

したがって、ノードの数とパーティションの数を切り離し、ノードに固定数のパーティションを割り当てる必要があります。たとえば、クラスターを初期化するときに、1024 個のパーティションの数が指定されます。現在、ノードは 3 つあるため、各ノードには 341 個のパーティションがあり、最後のノードには 342 個のパーティションがある可能性があります。このとき、ノードを追加します。クラスターに 4 つのノードができたら、パーティションを再バランスする必要があります。元の 3 つのノードそれぞれでパーティションの半分だけを取得する必要があります。この方法では、移行プロセスに含まれるのはデータの半分だけであり (割合は複雑なアルゴリズムによって動的に調整できます)、パーティションの再バランス調整プロセスの複雑さを軽減できます。同じ原則がノードの削除にも適用されます。ノード上のパーティションは他のノードに均等に分散できます。パーティション数を固定すると、ノード数とパーティション数の間の結合が解決されます。パーティション数の係数を取ることで、データが配置されているパーティションをすばやく特定でき、移行前後で相対的なパーティションは変更されません。 Redis のクラスター モードでは、この方法を使用してパーティションを再バランスします。

動的パーティション数

パーティションの数が固定されていると、ホットスポットを適切に処理できません。パーティションに保存されているデータの量が他のノードよりもはるかに大きい場合、これは不合理です。ノード数は固定されているため、これらのデータは移行できません。したがって、B+ ツリー ノードの分割とマージに似た概念を導入します。データ量に応じてパーティションを分割したり結合したりすることもできます。パーティションの負荷が指定されたしきい値を超えると、パーティションを 2 つのパーティションに分割します。このように、パーティションの数は変わります。このソリューションでは、パーティション番号の係数を使用してデータをハッシュすることはできず、キーワード間隔またはハッシュに従ってのみパーティション分割できます。しかし、各パーティションのデータ負荷を効果的に分散できるため、その価値はあります。

ノード比による分割

動的パーティショニングには、パーティションの数がデータ量に比例するという欠点もあります。データ量が増加すると、継続的に新しいパーティションが追加され、パーティション数の増加が新たなパフォーマンスのボトルネックになります。

したがって、上記の 2 つのソリューションを組み合わせた新しいソリューションが導入されます。ノード数が固定されている場合、パーティションの数も固定されます。各ノード上のパーティションの数は常に固定されています。このように、ノード数が変更されていない場合、データ負荷が増加すると、パーティションのサイズは増加し続けます。新しいノードが追加または削除されると、ノード上の一部のパーティションが分割のためにランダムに選択されます (複雑な戦略が使用される場合もあります)。パーティションの半分は新しいノードに移動され、残りの半分はそのまま残ります。これの利点は、パーティションの数がノードの数によって制限され、無限に増加してボトルネックになることがないことです。

手動および自動の再バランス調整

データ システムはパーティションの再バランスを自動的に完了する必要がありますか?これは間違いなく便利であり、多くのデータベースがこれを採用していますが、複雑さは非常に高くなります。たとえば、ノードのパーティション バランシングが発生したときに、システムがノードが使用できないことを検出すると、連鎖クラッシュが発生し、ノード削除ロジックがトリガーされ、新しいパーティション バランシングがトリガーされて、クラスター全体がクラッシュします。

シンプルさの原則に基づくと、管理者による手動のパーティション再バランス調整は妥協策となります。

リクエストルーティング

複雑なパーティション分割スキームを導入した後、クライアントは要求されたデータがどのパーティションにあるかをどのように知るのでしょうか?一般的には、次の 3 つの方法があります。

1. ノードをランダムに要求すると、パーティションはデータがそれ自体にあるかどうかを判断し、ある場合は結果を直接返し、ない場合はデータを持つノードに要求を転送して結果を返します。
2. すべてのリクエストはルーティング層にアクセスします。ルーティング層には、決定を下してリクエストを適切なノードに転送するのに十分なメタデータがあります。
3. クライアント自体がパーティション ノードの割り当て関係を認識し、対応するパーティションを直接要求できます。

いずれにしても、ルーティングの決定を誰が担当するかという問題になります。

クライアント要求のルーティングでは、クライアントはパーティションとノード間のマッピング関係の変更を認識する必要があります。これは通常、zk、etcd などの分散整合性コンセンサス コンポーネントに基づいて完了します。パーティション ノードが起動すると、そのメタデータが zk に登録され、zk はこの変更をサブスクライブしているクライアントに情報を伝播します。クライアントはパーティションとノード間のマッピング関係を更新し、要求があった場合に対応するパーティションに直接アクセスします。この方法の利点は、ネットワーク呼び出しの数が最小限に抑えられ、最も効率的であることです。ただし、サードパーティのコンセンサス コンポーネントに依存します。

もう 1 つの異なるアプローチは、クライアントが任意のノードを要求できるようにすることです。パーティション ノードは、保持しているメタデータ情報に基づいて、要求されたデータが自身のパーティション内にあるかどうかを判断します。そうであれば、データを直接処理して返します。そうでない場合は、パーティションを所有するリクエストにリクエストを転送して処理し、クライアントに返します。これを行う利点は、コンセンサス コンポーネントに依存しないことですが、最悪の場合、ネットワーク呼び出しの数が 2 倍になり、パフォーマンスに影響します。

並列クエリ処理

複数のフィールドの結合クエリが必要な場合、パーティション化されたデータベースでは何を行う必要がありますか?これまで、単一のキーを使用してクエリを実行する方法を検討してきましたが、データ ウェアハウスに対する大量のクエリでは、結合などのより複雑な複数テーブル操作が必要になります。パーティション化されたデータベースは適切に機能しますか?これには、分散データベースのパーティション化された並列クエリの問題が含まれます。理論的には、リクエストがルーティング層に到達すると、並列クエリ オプティマイザーとルーティング層のその他のコンポーネントが並列クエリ プランを作成し、それを対応するパーティションに委任して、最終的に結果をマージします。このプロセスには多くの詳細があり、後の記事で詳しく紹介する予定です。