技術概要: 分散システムにおける一般的な同期メカニズム

高いデータ可用性を確保するには、分散システムでデータの複数のコピーを保存する必要があります。次の疑問は、異なるコピー間でデータをどのように同期するかということです。同期メカニズムが異なれば、効果とコストも異なります。この記事では、一般的な分散コンポーネントの同期メカニズムをまとめます。

[[274580]]

一般的なメカニズム

一般的に使用される同期メカニズムがいくつかあり、それらを評価するためのさまざまな側面があります。まず、巨匠たちの古典的な要約を見てみましょう。

上の図は、一般的に使用されている同期方法を示しています (個人的な理解ですので、ご批判や訂正をお願いします)。

1. バックアップ、つまり定期的なバックアップは、既存のシステムのパフォーマンスにほとんど影響を与えませんが、ノードがダウンしたときにかろうじて復元することができます。
2. マスタースレーブ、マスタースレーブレプリケーションは、各命令を非同期的に複製し、より細かい定期的なバックアップと見なすことができます。
3. マルチマスターは「マスターマスター」とも呼ばれ、MS の拡張バージョンです。複数のノードに書き込んで後で同期することができます。
4. 2 フェーズ コミット、2 フェーズ コミット、同期により書き込み前にすべてのノードに通知され、パフォーマンスは「マスター」ノードで簡単に停止します。
5. Paxosは2PCと同様に、複数のノードが同時に書き込みを行うことができ、大多数のノードに通知するだけで済むため、スループットが向上します。

同期方法には 2 種類あります。非同期はパフォーマンスは良好ですが、データが失われる可能性があります。同期はデータが失われないことを保証できますが、パフォーマンスは低下します。同じタイプのアルゴリズムも改良できます (2PC 用の Paxos など) が、実装の難易度は非常に高くなります。実際には、これらの点についてはトレードオフすることしかできません。

同期アルゴリズムを検討する際には、ノードのダウンタイムやネットワークの閉塞などの障害シナリオを考慮する必要があります。次に、データの書き込み要求がどのように処理されるか（データの読み取り方法が含まれる場合もある）を中心に、いくつかの分散コンポーネントのデータ同期メカニズムを見てみましょう。

レディス

Redis 3.0 では、クラスター モードをサポートするために Redis Cluster が導入され始めました。個人的にはそのデザインがとても美しいと思います。公式ドキュメントをご覧ください。

• マスター/スレーブ レプリケーションと非同期同期メッセージを使用するため、極端な場合にはデータ損失が発生する可能性があります。
• データはマスターノードからのみ読み書きできます。スレーブ ノードはクライアントを拒否してリダイレクトするだけで、要求を転送しません。
• マスター ノードが一定期間ダウンした場合、スレーブ ノードが自動的にマスター ノードを選択します。
• 期間中にデータの不整合が発生した場合、最後に選択されたマスターノードのデータが優先されます。

デザインの詳細:

 HASH_SLOT = CRC16(キー) mod 16384
会う
待って

カフカ

Kafka のシャーディング粒度はパーティションであり、各パーティションには複数のコピーを含めることができます。レプリカ同期設計については、公式ドキュメントを参照してください。

• 2PCと同様に、ノードはマスターとスレーブに分かれており、メッセージは同期的に更新されます。すべてのノードに障害が発生しない限り、メッセージは失われません。
• メッセージはマスターノードに送信されます。マスター ノードがメッセージを書き込んだ後、すべてのスレーブ ノードがメッセージをプルするのを待機し、書き込みが完了したことをクライアントに通知します。
• 「すべての」ノードは、In-Sync レプリカ (ISR) を指します。応答が遅すぎたりクラッシュしたりするスレーブ ノードは排除されます。
• マスターノードがダウンした後、スレーブノードが新しいマスターノードとして選出され、サービスの提供を継続します。
• マスターノードがダウンしているときに送信される変更は保証されません（メッセージは ACK なしで送信される可能性があります）

デザインの詳細:

• 現在、コンシューマーはマスターノードからのみデータを読み取ることができますが、これは将来変更される可能性があります。
• マスター/スレーブの粒度はパーティションです。各ブローカーは、一部のパーティションに対してはマスター ノードであり、他のパーティションに対してはスレーブ ノードです。
• パーティションを作成するとき、Kafka は優先レプリカをブローカー間で均等に分散しようとします。
• リーダー選出は、Zookeeper と対話した後、コントローラーによって「内部的に決定」され、その後、RPC を通じて特定のマスター ノードに通知されます。これにより、パーティションが多すぎるのを防ぎ、リーダー選出によって Zookeeper が過負荷になるのを防ぐことができます。

エラスティックサーチ

ElasticSearch のデータ ストレージ要件は Kafka と非常に似ており、その設計も非常に似ています。詳細については、公式ドキュメントを参照してください。

ES にはマスターノードの概念があります。実際の機能はクラスターのステータスを管理することであり、データ要求とは関係ありません。コンテキストの一貫性を保つために、これを管理ノードと呼び、プライマリ シャードを「マスター ノード」、レプリカ シャードをスレーブ ノードと呼びます。 ESデザイン:

• 2PCと同様に、ノードはマスターとスレーブに分かれており、メッセージは同期的に更新されます。すべてのノードに障害が発生しない限り、メッセージは失われません。
• メッセージはマスターノードに送信されます。マスターノードが正常に書き込みを行うと、その書き込みはスレーブノードに並列で送信されます。すべてのスレーブ ノードが正常に書き込みされると、書き込みが完了したことがクライアントに通知されます。
• 管理ノードは、各シャードが書き込む必要があるスレーブ ノードのリスト (同期コピーと呼ばれる) を維持します。
• マスターノードがダウンした後、スレーブノードが新しいマスターノードとして選出され、サービスの提供を継続します。
• コミット フェーズ中にスレーブ ノードが使用できない場合、マスター ノードは管理ノードに同期コピーからスレーブ ノードを削除するように要求します。

デザインの詳細:

• 書き込みはマスターノードからのみ可能で、読み取りはどのスレーブノードからでも可能
• 各ノードはサービスを提供できます。リクエストはデータ シャードが配置されているノードに転送されますが、負荷を分散するためにラウンドロビン方式で各ノードにアクセスすることをお勧めします。
• データシャーディング: シャード = ハッシュ(ルーティング) % プライマリシャードの数
• インデックスを作成するときに、プライマリ シャードの数を決定する必要があります。
• マスター/スレーブの粒度はシャードです。各ノードは、一部のシャードに対してはマスター ノードであり、他のシャードに対してはスレーブ ノードです。
• マスター選択アルゴリズムはES独自のZen Discoveryを使用しています

ハドゥープ

Hadoopは連鎖レプリケーションを使用します。レプリケーションパイプラインを参照してください。

• データの複数のコピーが複数のデータノードに書き込まれ、1 つのデータノードが存続している限り、データは失われません。
• データは複数のブロックに分割され、ネームノードは各ブロックのデータをどのデータノードに書き込むかを決定します。
• チェーン レプリケーションでは、データがノードに送信され、そのノードがそれを次のノードに送信し、次のノードが戻ってローカル書き込みが成功すると、そのノードも戻り、書き込みチェーンが形成されるという動作が必要になります。
• 書き込み処理中にクラッシュしたノードは pineline から削除され、その後、不整合のあるデータは namenode によって処理されます。

実装の詳細:

• チェーンレプリケーションは実装時に最適化され、ブロックは複数のパケットに分割されます。ノード 1 はパケットを受信し、それをローカルに書き込んで同時にノード 2 に送信し、ノード 2 が完了し、ローカルが完了後に ACK を返すのを待機します。ノード 2 はパケットをローカルに書き込み、ノード 3 に送信します。

ティクヴ

TiKV は、データを書き込むときに一貫性を実現するために Raft プロトコルを使用します。 TiDBテクノロジーインサイダーについて学ぶには、3つの記事を参照してください - ストレージについて語る

• Raft を使用する場合、データが返される前に半数以上のノードが書き込みに成功する必要があります。半数以下のノードに障害が発生した場合、データは失われません。
• TiKV はデータ キーを範囲ごとに領域に分割し、書き込み時に領域の粒度で同期します。
• 書き込みと読み取りは両方ともリーダーを通じて行われます。各地域は独自のラフトグループを形成し、独自のリーダーを擁しています。

動物園の飼育員

Zookeeper は Zookeeper 独自の Zab アルゴリズム (Paxos の変種?) を使用します。Zookeeper の内部を参照してください。

• データはマスターノードを通じてのみ書き込むことができ（リクエストはマスターノードに転送されます）、どのノードからも読み取ることができます。
• マスターノードはデータを書き込んだ後、それをすべてのノードにブロードキャストします。半数以上のノードが書き込みを終えると、クライアントに返されます。
• Zookeeper は読み取られたデータが最新であることを保証するものではありませんが、読み取られたデータのバージョンが「単一ビュー」を通じて「ロールバック」されないことを保証します。

まとめ

システムのパフォーマンス要件が高く、データ損失を許容できる場合 (Redis)、非同期同期は明らかに適切な選択です。

システムでデータが失われないようにする必要がある場合は、同期レプリケーション メカニズムのみを使用できます。 Kafka と Elasticsearch はどちらも PacificA アルゴリズム (個人的には 2PC のバリエーションとして見ることができると思います) を使用していることがわかりました。もちろん、この方法の応答は最も遅いコピーによって制限されるため、Kafka と Elasticsearch はどちらも遅いコピーを削除するための関連メカニズムを備えています。

もちろん、Paxos、Raft、Zab などの新しいアルゴリズムは 2PC よりも優れているようです。これらのアルゴリズムは一貫性の保証がより強力で、半数のノードが正常に書き込みを行う限り戻ることができます。 Paxos はマルチポイント書き込みもサポートしています。ただし、これらのアルゴリズムを正しく実装して最適化することも困難です。