質問しながら分散システムのデータシャーディングを学ぶ

文章

前回の記事では、分散システム (特に分散ストレージ システム) が解決する必要がある 2 つの主要な問題、つまりデータ シャーディングとデータ冗長性について説明しました。次の図（出典）は、それらの概念と違いを鮮明に説明しています。

データ A と B はデータ シャードに属し、元のデータは 2 つの直交サブセットに分割され、2 つのノードに分散されます。データ セット C は冗長化されており、両方のノードに同じ完全なデータが格納されます。もちろん、実際の分散システムでは、データシャーディングとデータ冗長性は共存するのが一般的です。

この記事では、主にデータ シャーディングに関する 3 つの問題について説明します。

• （１）データを分割する方法、つまりデータをノードにマッピングする方法
• （２）データシャーディングの特性値、すなわち、データ内のどの属性（フィールド）がシャーディングされるかによって
• （３）データシャードのメタデータ管理メタデータ サーバーの高パフォーマンスと高可用性を確保するにはどうすればよいですか?サーバーのグループの場合、強力な一貫性をどのように確保するのでしょうか?

いわゆる分散システムでは、複数の独立したコンピュータを使用して、単一のノード (コンピュータ) では処理できないストレージおよびコンピューティングの問題を解決します。これは非常に典型的な分割統治の考え方です。各ノードは元の問題のサブセット（つまり、システム全体が完了する必要のあるタスク）のみを担当します。では、元の問題を複数のノードに分割するにはどうすればよいでしょうか。分散ストレージ システムでは、タスクの分割はデータ シャーディングと呼ばれます。

データ シャーディング (セグメント、フラグメント、シャード、パーティション) とは何ですか?これは、特定のルールに従ってデータ セットを独立した直交データ サブセットに分割し、そのデータ サブセットを異なるノードに分散することを意味します。ここで、データ シャーディングは特定のルールに従う必要があると述べられていることに注意してください。分散アプリケーションごとにルールは異なりますが、すべて同じ原則、つまり最も重要で頻繁に使用されるアクセス方法に従ってシャーディングするという原則に従います。

3つのデータシャーディング方法

まず、ハッシュ方式、コンシステントハッシュ、範囲ベースの 3 つのシャーディング方式を紹介します。どのようなアプローチをとる場合でも、次の質問について考える必要があります。

1. 元のデータセットをどのように分割しますか?
2. 元の問題の規模が大きくなった場合、ノードを追加することで動的に適応できますか?
3. ノードに障害が発生した場合、そのノード上のタスクを他のノードに均等に分散できますか?
4. 変更可能なデータ（データベース データなど）の場合、特定のノード上のデータ量が多くなったときに、動的バランス効果を実現するために、データの一部を負荷の少ない他のノードに移行できますか。また、その方法は?
5. メタデータ管理の規模（つまり、データと物理ノード間の対応）はどの程度ですか?メタデータの更新はどのくらいの頻度で、どれくらい複雑ですか?

後でさまざまなデータ シャーディング方法を分析するために、N0、N1、N2 という番号が付けられた 3 つの物理ノードがあると仮定します。以下の記録があります。

 R0: {id: 95、名前: 'aa' 、タグ: 'older' }  
 R1: {id: 302、名前: 'bb' 、}  
 R2: {id: 759、名前: 'aa' 、}  
 R3: {ID: 607、名前: 'dd' 、年齢: 18}  
 R4: {id: 904、名前: 'ff' 、}  
 R5: {id: 246、名前: 'gg' 、}  
 R6: {id: 148、名前: 'ff' 、}  
 R7: {id: 533、名前: 'kk' 、}

ハッシュ方式:

ハッシュテーブルは最も一般的なデータ構造です。高速アクセスを実現するために、レコード (またはオブジェクト) のキー値に従ってレコードをテーブル内のスロットにマッピングします。 Python の dict、C++ の map、Java の Hashtable、Lua の table など、ほとんどのプログラミング言語はハッシュ テーブルをサポートしています。ハッシュ テーブルでは、最も単純なハッシュ関数は mod N (N はテーブルのサイズ) です。つまり、最初にキー値（ここでは整数）のハッシュ値を計算し、次に N の余りを取得し、その余りがテーブル内の位置になります。

データシャーディングのハッシュ方式もこの考え方に従っており、データの特定の特徴（キー）に応じてハッシュ値を計算し、ハッシュ値とシステム内のノードの間にマッピング関係を確立することで、異なるハッシュ値を持つデータを異なるノードに分散できるようにします。

データシャーディングのキーとして id を選択すると、各ノードが担当するデータは次のようになります。

このことから、ハッシュ方式を使用してデータをシャーディングする場合、マッピング関係は非常に単純であることがわかります。管理するメタデータも非常に少なく、ノードの数とハッシュ方式を記録するだけで済みます。

しかし、ハッシュ方式の欠点も非常に明白です。ノードを追加または削除するときに、大量のデータを移動する必要があります。例えば、ここにノード N3 を追加すると、ハッシュ方式は mod 4 になり、データ移行は次のようになります。

この方法では、単調性は満たされません。ハッシュによって対応するバッファに何らかのコンテンツが割り当てられている場合、新しいバッファがシステムに追加されます。ハッシュ結果により、元の割り当てられたコンテンツが元のバッファまたは新しいバッファにマップできるが、古いバッファ セット内の他のバッファにはマップできないことが保証されます。

エンジニアリングでは、移行するデータの量を減らすために、ノードの数を指数関数的に増やすことができ、移行されるデータが 50% 以下になる確率になります。

ハッシュ方式には、データの不均衡の問題を解決するのが難しいという欠点もあります。状況は 2 つあります。1 つ目は、元のデータの特性値が不均一に分散しているため、大量のデータが 1 つの物理ノードに集中していることです。 2 番目に、変更可能なレコード データの場合、1 つのレコードのデータが大きくなります。どちらの場合も、ノード間の負荷の不均衡につながり、ハッシュ方式で解決するのは困難です。

一貫性のあるハッシュ

コンシステント ハッシュは、特性値に従ってエンドツーエンドで接続されたハッシュ リングにデータをマッピングし、またノード (IP アドレスまたはマシン名ハッシュによる) をこのリングにマッピングします。データの場合、リング上のデータの場所から始めて、時計回りに最初に見つかったノードがデータのストレージ ノードになります。ここでも上記のデータを例として取り上げます。 idの範囲が[0, 1000]であり、リング上のN0、N1、N2の位置がそれぞれ100、400、800であると仮定すると、ハッシュリング図とデータ分布は次のようになります。

上記のハッシュ方式と比較すると、コンシステントハッシュ方式で維持する必要があるメタデータには、リング上のノードの位置も追加で含まれることがわかりますが、データ量も非常に少ないです。

ノードを追加または削除する場合、影響を受けるデータは比較的制限されます。たとえば、ここではリング上の位置が 600 であるノード N3 を追加します。したがって、元々 N2 を担当していた範囲 (400, 800] は、現在は N3 (400, 600] N2 (600, 800]) を担当しています。したがって、レコード R7 (id: 533) を N2 から N3 に移行するだけで済みます。

一貫性のあるハッシュ方式では、データの追加または削除時にハッシュ リング上の対応するノードにのみ影響し、大規模なデータ移行は発生しないことは容易にわかります。

ただし、コンシステント ハッシュ方式では、ノードを追加するときにのみ既存のノードの圧力を共有できます。同様に、ノードの 1 つがハングアップすると、そのノードの圧力が次のノードに転送されます。私たちが望んでいるのは、「一方が困っているときは、すべての側が助けに来る」ということなので、ノードを追加または削除するときは、既存のすべてのノードが対応に参加し、新しい均衡状態に到達できる必要があります。

そのため、実際のエンジニアリングでは、仮想ノードの概念が導入されるのが一般的です。つまり、物理ノードをハッシュ テーブルにマッピングする代わりに、仮想ノードをハッシュ リングにマッピングします。仮想ノードの数は物理ノードの数よりもはるかに多いため、1 つの物理ノードが複数の仮想ノードの実際のストレージを担当する必要があります。データを操作するときは、まずハッシュ リングを通じて対応する仮想ノードを見つけ、次に仮想ノードと物理ノード間のマッピング関係を通じて対応する物理ノードを見つけます。

仮想ノードの導入後、一貫性のあるハッシュのために維持する必要があるメタデータも増加します。まず、ハッシュリング上の仮想ノードの問題があり、仮想ノードの数は比較的多くなります。 2 番目は、仮想ノードと物理ノード間のマッピング関係です。しかし、そのメリットは明らかです。物理ノードに障害が発生すると、ハッシュ リング上の複数の仮想ノードに障害が発生し、それに伴う負荷が他の複数の仮想ノード (実際には他の複数の物理ノード) に分散されます。物理ノードを追加する場合も同様です。

このプロジェクトでは、Dynamo と Cassandra は両方とも一貫性のあるハッシュ アルゴリズムを使用しており、上位バージョンでは両方とも仮想ノードの概念を使用しています。これらのシステムでは、データの分散方法やデータの複製を総合的に考慮する必要があります。データ複製を導入した後は、一貫性のあるハッシュ方式もそれに応じて調整する必要があります。 Cassandraの関連ドキュメントを参照することができます。

範囲ベース

簡単に言えば、キー値に応じて異なる間隔に分割され、各物理ノードは 1 つ以上の間隔を担当します。実際、この方法はコンシステント ハッシュに少し似ており、ハッシュ リング上の物理ノードの位置が動的に変化するものとして理解できます。

上記のデータを例にとると、3つのノードのデータ間隔はN0(0, 200]、N1(200, 500]、N2(500, 1000]です。この場合、データ分布は次のようになります。

間隔のサイズは固定されておらず、各データ間隔のデータ量は間隔のサイズとは関係がないことに注意してください。たとえば、データの一部が非常に集中している場合は、間隔のサイズを比較的小さくする必要があります。つまり、データのサイズがセグメント標準として使用されます。実際のプロジェクトでは、ノードが複数の間隔を担当することが多く、各間隔はチャンク (ブロック) と呼ばれ、各ブロックにはしきい値があります。このしきい値に達すると、2 つのブロックに分割されます。これを行う目的は、ノードが参加したときにすぐにバランスを達成することです。

ノードが 1 つのデータ間隔のみを担当する場合、範囲ベースは仮想ノードの概念のないコンシステント ハッシュと非常に似ていることに読者は気づいたでしょうか。ノードが複数の間隔を担当する場合、範囲ベースは仮想ノードの概念を持つコンシステント ハッシュと非常に似ています。

範囲ベースのメタデータ管理は、特に単一のノードに複数の範囲がある場合、各ノードのデータ範囲を記録する必要があるため、比較的複雑です。さらに、データが変更可能な場合、ブロックが分割されると、メタデータ内の間隔情報も同期的に変更する必要があります。

範囲ベースのデータパーティショニングは、MongoDB、PostgreSQL、HDFSなどで広く使用されています。

まとめ：

ここでは、主に次の質問に答えるために、3 つのシャーディング方法 (仮想ノードの有無にかかわらずコンシステント ハッシュを含む 4 つの方法があるはずです) について簡単に説明します。

上記のデータ動的バランスは、上記の質問の4番目のポイント、つまり、ノード上のデータ量が多くなった場合に、データの一部を負荷の少ない他のノードに移行するかどうか、またどのように移行するかという点に価値がある。

シャーディング特徴値の選択

上記の 3 つの方法はすべて、データ シャーディングがキー値と特徴値に基づいていることを述べています。この特性値は、MongoDB ではシャーディング キー、Oracle ではパーティション キーなど、システムによって名前が異なります。いずれにせよ、この特性値の選択は非常に重要です。

それで。この特性値をどのように選択すればよいでしょうか? 「楽しみと利益のための分散システム」は簡潔な標準を提供します:

• 主なアクセスパターンがどうなるかに基づいて

大まかに翻訳すると、最も一般的なアクセス パターンに基づいています。アクセスには、データの追加、削除、変更、および確認が含まれます。たとえば、上記の例では、シャーディングの基準として「id」を選択しているため、デフォルトでは、データの追加、削除、変更、クエリはすべて「id」フィールドを通じて実行されます。

アプリケーションでこの機能値に対して大量のデータ操作が実行される場合、データ シャーディングによって次の 2 つの追加の利点が得られます。

• （1）パフォーマンスと同時実行性を向上させる。操作は異なるシャードに分散され、互いに独立しています。
• （２）システムの可用性を向上させる。一部のシャードが利用できない場合でも、他のシャードは影響を受けません。

固有値を使用しない演算が多数あると面倒です。たとえば、この記事の例では、クエリに名前を使用し、メタデータに ID に応じてデータの場所をマップする方法が記録されている場合、扱いにくいことになります。すべてのシャードをチェックしてから集約を行う必要があります。

もう 1 つの問題は、単一のフィールドを特性値 (ID など) として使用する場合、どのような分散方法を使用しても、複数のデータが同じ特性値 (ID など) を持つ場合、これらのデータは必ず同じノードに分散されることです。この状況には2つの問題があります。 1 つは、ノード間でデータを分散できないことです。もう 1 つは、データが単一ノードのストレージ容量を超えた場合にどうするかということです。重要な点は、分散システムで問題を解決する従来の方法、つまりノードの追加を使用しても、役に立たないということです。

このとき、特徴値として単一のフィールドだけでは不十分であり、データベースの結合インデックスと同様に、「結合特徴値」として別のフィールドを追加する必要がある場合があります。たとえば、データがユーザーの操作ログである場合、ID とタイムスタンプをハッシュ関数の入力として使用し、特徴値を計算できます。しかし、この場合でも、クエリ キーワードとして id を使用してクエリを実行する場合は、すべてのノードをトラバースする必要があります。

したがって、完璧なデザインというものは存在せず、最適なアプリケーションのニーズを満たすデザインだけが存在します。

以下では、MongoDB のシャーディング キーを例に、特徴値の選択の重要性とそれがデータ操作に与える影響について説明します。データベース操作の基本的な知識があれば、MongoDB を使用したことがなくても、以下の内容を問題なく読むことができます。

MongoDBのシャーディングキーを例に挙げる

MongoDB シャード クラスターについては、以前に「シャード クラスターを段階的に作成して MongoDB を理解する」という記事を書き、簡単に紹介しています。私の仕事のシナリオでは、結合とトランザクションを除けば、MongoDB の使用方法は MySQL と非常に似ており、特に基本的な CRUD 操作とデータベース インデックスが似ています。 MongoDb では、各シャードはシャードと呼ばれ、シャードの特性値はシャーディング キーと呼ばれ、各データはドキュメントと呼ばれます。シャーディングキーとして適切なフィールドを選択することが非常に重要です。なぜ？

前述のように、非シャーディング キーを使用してデータにアクセスすると、メタデータ サーバー (または後で説明するメタデータ キャッシュ サーバー) は、対応するデータがどのシャード上にあるかを認識しません。この場合、アクセスをすべてのシャードに送信し、すべてのシャードからの結果を集約する必要があります。 mongoDB では、mongos (メタデータ情報をキャッシュする) がデータの集約を行います。データの読み取り（R: 読み取りまたは取得）の場合、同じフィールドを介して複数のデータを取得しても問題はありませんが、効率は比較的低くなります。データの更新については、1 つのデータのみを更新できる場合、どのシャードで更新するかは適切ではないようです。この時点で、MongoDB は拒否します。 MongoDB (MongoDD3.0) に対応するコマンドには、以下のものが含まれますが、これらに限定されません。

findandmodify:このコマンドは1つのドキュメントのみを更新できるため、クエリ部分にはシャーディングキーが含まれている必要があります。

• シャード環境で findAndModify を使用する場合、クエリには、シャード コレクションのシャード クラスターに対するすべての操作のシャード キーが含まれている必要があります。

更新:このコマンドにはパラメータ multi があり、デフォルトでは false に設定されているため、更新できるドキュメントは 1 つだけです。この場合、クエリ部分にはシャーディング キーが含まれている必要があります。

• multi: false オプションを指定するシャード コレクションのすべての update() 操作には、クエリ仕様にシャード キーまたは _id フィールドを含める必要があります。

削除:パラメータ JustOne があります。 True の場合、削除できるドキュメントは 1 つだけであり、共有キーも使用する必要があります。

さらに、SQL に精通している学生は、データ インデックスに一意のインデックスがあり、このフィールドの値がテーブル内で一意であることを保証することを知っています。 MongoDB でも一意のインデックスを作成できますが、シャード クラスター環境では、シャーディング キーに対してのみ一意のインデックスを作成できます。その理由は非常に単純です。一意のインデックスがシャーディング キーでない場合は、挿入時にすべてのシャードでチェックし、ロックする必要があります。

次に、シャード上のデータ分散が不均一であるという問題について説明します。シャードキーが一定期間に集中しすぎると (たとえば、時間の経過とともに増加する場合)、データは 1 つのシャードにのみ書き込まれるため、クラスターの圧力を分散できなくなります。

MongoDB では、「レンジ パーティション」と「ハッシュ パーティション」が提供されています。これらは、前述のシャーディング方式のハッシュ方式や範囲ベース方式とは異なりますが、シャーディング キーの処理を参照します。 MongoDB は、ドキュメントに記載されているように、範囲ベースのシャーディングを使用する必要があります。

• MongoDB は、シャード キー値の範囲を使用してコレクション内のデータをパーティション分割します。各範囲は、重複しないシャード キー値の範囲を定義し、チャンクに関連付けられます。

では、「レンジ パーティション」と「ハッシュ パーティション」とは何でしょうか?公式サイトの写真は、この 2 つの違いを非常によく説明しています。

上の図の左側はレンジパーティション、右側はハッシュパーティションを示しています。範囲パーティションでは、上の図の x のように、フィールド自体をシャーディング境界として使用します。ハッシュ パーティションでは、フィールドをより大きく、より離散的な値の範囲に再ハッシュします。

ハッシュ パーティションの最大の利点は、データが各ノードに均等に分散されることを保証することです (ここでの均等とは、MongoDB のバランス機能ではなく、書き込み時に均等に分散されることを意味します)。たとえば、MongoDB のデフォルトの _id は objectid で、これは 12 バイトの BSON タイプです。最初の 4 バイトはマシンのタイムスタンプです。 ObjectId が _id であるデータが同時に大量に作成された場合、それらは同じシャードに割り当てられます。このとき、ハッシュインデックスとハッシュシャーディングキーとして _id を設定しておけば、このような問題は発生しません。

もちろん、ハッシュ パーティションには、範囲パーティションと比較して、範囲クエリを実行するときの効率が低いという大きな欠点もあります。したがって、ハッシュ パーティションを使用するか、範囲パーティションを使用するかは、アプリケーションのシナリオに基づいて具体的に検討する必要があります。

***シャーディング キーは一度選択すると変更できない (不変) ことに注意してください。アプリケーションでシャーディング キーを変更する必要がある場合は、データをエクスポートし、新しいデータベースと新しいシャーディング キーを作成してから、データをインポートすることしかできません。

メタデータサーバー

上で説明した 3 つのデータ シャーディング方法では、データとノード間のマッピング関係、ノードの状態など、一部のメタデータが多かれ少なかれ記録されます。メタデータを記録するサーバーをメタデータ サーバー (メタサーバー) と呼びます。システムによって、master、configserver、namenode などの異なる名前が付けられます。

メタデータ サーバーは人間の脳のようなものです。片手が不自由になるだけでも耐えられないのに、脳が機能しなくなると全身が麻痺してしまいます。したがって、メタデータ サーバーの高パフォーマンスと高可用性を実現するには、メタデータの増加に対応できる高度なスケーラビリティがメタデータ サーバーに必要です。

メタデータの高可用性を実現するには、メタデータ サーバーが単一障害点にならないようにする必要があります。したがって、メタデータ サーバーには複数のバックアップが必要であり、障害が発生した場合にすばやく切り替えられる必要があります。

バックアップが複数ある場合、複数のバックアップのデータの一貫性をどのように確保するかが問題になります。

複数のレプリカの一貫性と可用性については、CAP 理論で説明されています。ここでは 2 つの解決策を簡単に紹介します。 1 つ目はマスター スレーブ同期です。まず、マスター サーバーが選択されます。外部サービスを提供するのはマスター サーバーのみです。マスター サーバーは、メタデータの変更情報をログの形式で共有ストレージ (nfs など) に保存します。次に、スレーブ サーバーは共有ストレージからログを読み取り、それを適用してマスター サーバーと一致する状態を実現します。マスター サーバーに障害があることが検出された場合 (ハートビートなどにより)、新しいマスター サーバーが再選択されます。 2 番目の方法は、有名な Paxos プロトコルや、エンジニアリングで広く使用されている Paxos の特殊バージョンである Raft プロトコルなどの分散一貫性プロトコルを通じて、複数のレプリカ間の一貫性を実現することです。このプロトコルにより、すべてのバックアップが外部サービスを提供でき、強力な一貫性を保証できるようになります。

HDFS メタデータ

HDFS では、メタデータ サーバーは namenode と呼ばれます。 HDFS 1.0 より前では、namenode は単一のポイントでした。ネームノードがクラッシュすると、システム全体が機能しなくなります。 HDFS 2.0 では、NameNode の単一ポイント問題が解決されています。

上図では、NN は NameNode、DN は DataNode (実際にデータを格納するノード) です。図からわかるように、2 つの NameNode は相互バックアップを形成し、1 つはアクティブ状態 (プライマリ NameNode) で、もう 1 つはスタンバイ状態 (バックアップ NameNode) です。プライマリ NameNode のみが外部に対して読み取りおよび書き込みサービスを提供できます。

アクティブ NN とスタンバイ NN 間のデータ同期は共有ストレージを通じて実現され、共有ストレージ システムによって Namenode の高可用性が保証されます。メタデータの強力な一貫性を確保するために、切り替えの準備をする際に、新しいアクティブ NN は、外部にサービスを引き続き提供する前に、メタデータが完全に同期されていることを確認する必要があります。

さらに、Zookeeper クラスターは Namenode の状態を監視し、切り替えの準備を行う役割を担います。ネットワーク分割の場合、Zookeeper は元のアクティブ NN がクラッシュしたと判断して新しいアクティブ NN を選択する可能性がありますが、実際には元のアクティブ NN が引き続きサービスを提供しています。これにより、「デュアルマスター」または脳分割現象が発生します。この問題を解決するために、古いアクティブ ネームノードを分離して外部に通常のサービスを提供できないようにする方法を見つけるフェンシング メカニズムが提案されました。詳細については、この記事を参照してください。

MongoDB メタデータ

MongoDB では、メタデータ サーバーは構成サーバーと呼ばれます。 MongoDB 3.2 では、3 つのミラー化された MongoDB インスタンスを構成サーバーとして使用することは推奨されなくなりました。代わりに、レプリカ セットを構成サーバーとして使用することをお勧めします。この変更の目的は、構成サーバーの一貫性を強化することです。さらに、構成サーバー内の mongod の数も 3 からレプリカ セットの上限 (50 ノード) まで増やすことができるため、信頼性が向上します。

MongoDB 3.0 以前のバージョンでは、メタデータは次のように読み書きされます。

• 3 つの構成サーバーに書き込む場合、コーディネーターは同じ書き込みコマンドを 3 つの構成サーバーに送信し、結果を収集します。結果が異なる場合は、構成サーバーへの書き込みに一貫性がないことを示しており、手動による介入が必要になる場合があります。

MongoDB の公式ドキュメントではこのプロセスについて詳しく説明されていませんが、stackexchange では、このプロセスは 2 フェーズ コミットであると指摘した人がいました。

MongoDB 3.2 以降のバージョンでは、レプリカ セット構成サーバーを使用します。記事「CAP 理論と MongoDB の一貫性と可用性に関する考察」では、レプリカ セットの書き込みコンサーン、読み取りコンサーン、および読み取り参照について詳しく説明します。これら 3 つのオプションは、レプリカ セットの一貫性、信頼性、および読み取りパフォーマンスに影響します。構成サーバーでは、WriteConcern: Majority;懸念事項: 多数派; ReadReferences: 最も近いものが使用されます。

メタデータのキャッシュ:

メタデータ サーバーは物理マシンのグループで構成できますが、レプリカ セット間の一貫性は保証されます。ただし、すべてのデータ要求がメタデータ サーバーを経由すると、メタデータ サーバーに大きな負荷がかかります。多くのアプリケーション シナリオでは、メタデータの変更はそれほど頻繁に行われないため、アクセス ノードにキャッシュできます。この方法では、アプリケーションはキャッシュされたデータを直接使用してデータの読み取りと書き込みを行うことができるため、メタデータ サーバーへの負荷が軽減されます。

この環境では、キャッシュされたメタデータはメタデータ サーバー上のメタデータと一致している必要があり、キャッシュされたメタデータは正確で古くなっていない必要があります。反対の例は DNS のようなキャッシュで、期限切れの DNS キャッシュを使用しても大きな問題にはなりません。

キャッシュの強力な一貫性を実現するにはどうすればよいですか?最も簡単に考えられる方法は、メタデータが変更されたときにすべてのキャッシュ サーバー (mongo) にすぐに通知することですが、問題は通信が遅延し、信頼性が低いことです。

不整合の問題を解決するための一般的なアプローチは、バージョン番号を使用することです。たとえば、ネットワーク通信では、通信プロトコルが変更される可能性があり、合意に達するために、通信当事者はバージョン番号を使用できます。バージョン番号は、キャッシュの一貫性の問題を解決するためにも使用できます。基本的な考え方は、リクエスト時にキャッシュのバージョン番号を取得し、特定のノードにルーティングした後、実際のデータのバージョン番号を比較することです。バージョン番号が一致しない場合は、キャッシュされた情報が古すぎることを意味します。このとき、メタデータ サーバーからメタデータを再度取得してキャッシュする必要があります。 MongoDB では、このアプローチは mongos キャッシュで使用されます。

もう 1 つの解決策は、有名なリース メカニズム、「分散ファイル キャッシュの一貫性のための効率的なフォールト トレラント メカニズム」です。リース メカニズムは、分散キャッシュだけでなく、何らかの合意に達する必要がある多くの場所でも、分散システムで広く使用されています。 「分散システム原理入門」では、リースの仕組みについて詳しく説明しています。以下はリースの仕組みの簡単な紹介です。

リースの仕組み:

リース メカニズムは分散ストレージ システムのキャッシュ一貫性の問題を解決するために提案されたため、まずリース メカニズムが強力なキャッシュ一貫性をどのように保証するかを見てみましょう。なお、以下の説明の便宜上、このセクションではメタデータ サーバーをサーバー、キャッシュ サーバーをクライアントと呼びます。

要点:

• サーバーがキャッシュされたデータをすべてのクライアントに送信すると、制限された期間 (有効期限) を含むリースが発行されます。
• リースの意味は、この有効期間中、サーバーはメタデータが変更されないことを保証することです。
• したがって、クライアントはこの有効期間内にキャッシュされたメタデータを安全に使用できます。有効期限が切れると、データは使用できなくなり、サーバーに要求する必要があります。
• 外部リクエストによってサーバー上のメタデータが変更された場合 (メタデータの変更はサーバー上で実行する必要があります)、サーバーは発行されたすべてのリースの有効期限が切れるまで変更リクエストをブロックし、その後メタデータを変更して新しいメタデータと新しいリースをクライアントに送信します。
• メタデータが変更されていない場合、サーバーは、以前に発行されたリースの有効期限が切れる前に、クライアントに新しいリースを再発行する必要があります (リースのみ、データなし)。

リース ペーパーのタイトルには、「フォールト トレラント」と記載されています。では、リースはどのようにしてフォールト トレランスを実現するのでしょうか?重要なのは、サーバーがデータとリースを送信すると、クライアントがデータを受信するかどうかは気にしなくなるということです。リースの有効期限が切れるまで待つ限り、メタデータを変更できます。さらに、リースの有効期間は有効期限 (タイムスタンプ) によってマークされるため、サーバーからクライアントへのメッセージが遅れて到着したり、繰り返し送信されたりしても問題ありません。

フォールト トレランスの前提は、サーバーとクライアントの時刻が一貫している必要があるということであることは容易にわかります。サーバー時間がクライアント時間よりも遅い場合、リースはクライアントが受信した直後に期限切れになり、リース メカニズムは機能しません。サーバー時間がクライアント時間よりも速い場合、サーバーがメタデータの更新を開始したときにクライアントがキャッシュを使用し続けるため、より危険です。エンジニアリングでは、この問題を解決するために、サーバーの有効期限は通常、クライアントの有効期限よりもわずかに長く設定されます。時間の一貫性を保つには、NTP (ネットワーク タイム プロトコル) を使用してクロックの同期を確保するのが最善の方法です。

リース メカニズムの本質は、発行者が一定の有効期間内に付与するコミットメントです。コミットメントの範囲は非常に広範囲です。たとえば、前述のキャッシュなどです。たとえば、同時実行制御が必要な場合、同時に 1 つのノードにのみリースが発行され、リースを保持しているノードのみがデータを変更できるなどの権限制御。たとえば、アイデンティティ認証では、プライマリ-セカンダリ アーキテクチャでは、ノードにリースが発行され、リースを保持しているノードだけがプライマリ アイデンティティを持ちます。例えば、ノードの状態監視、例えばプライマリ・セカンダリ構成においてプライマリが正常かどうかの監視などですが、これについては後ほど詳しく紹介します。

リース メカニズムはエンジニアリングでも広く使用されています。リースは、GFS で Chuck のプライマリ コピーを決定するために使用されます。リースはマスター ノードによってプライマリ コピーに発行され、リースを保持しているコピーがプライマリ コピーになります。 Chubby は Paxos プロトコルを使用してプライマリ ノードの分散選択を実装し、セカンダリ ノードがプライマリ ノードにリースを送信します。リースの意味は、「リース期間中に他のノードをプライマリ ノードとして選択しないことを約束する」ことです。 Chubby では、プライマリ ノードも各クライアント ノードにリースを発行します。リースの意義は、クライアントの生死状態を決定することです。クライアント ノードは、有効なリースがある場合にのみ、Chubby のプライマリで読み取りおよび書き込み操作を実行できます。

要約する

この記事では、主に分散システムにおけるシャーディング関連の問題について紹介し、ハッシュ、コンシステント ハッシュ、範囲ベースの 3 つの分散方法と、それぞれの長所と短所について説明します。シャーディングは特定の特性値に従って実行されます。特性値は、アプリケーションの使用シナリオに基づいて選択する必要があります。 MongoDB と組み合わせることで、特性値 (MongoDB のシャーディング キー) がデータ操作に与える影響を実証します。シャード情報 (メタデータなど) には専用のサーバー ストレージが必要です。メタデータ サーバーは分散ストレージ システムの中核となるため、その可用性と信頼性について言及する必要があります。メタデータ サーバーへの負荷を軽減するために、メタデータは分散システム内の他のノードにキャッシュされます。キャッシュされたメタデータは一貫性の問題を引き起こすため、リース メカニズムが導入されます。