分散システムの一般的な考え方と技術の概要

[[349357]]

分散システムはスタンドアロンシステムと比べてどのような困難を抱えているのでしょうか?

0x01: ネットワーク要因

サービスとデータは異なるマシンに分散されているため、各インタラクションは複数のマシン間で実行する必要があり、次のような問題が発生します。

ネットワーク遅延: パフォーマンス、タイムアウト

同じコンピュータ ルーム内のネットワーク IO はまだ比較的高速ですが、コンピュータ ルーム間、特に IDC 間では、ネットワーク IO が無視できないパフォーマンスのボトルネックになります。さらに、レイテンシーは帯域幅ではありません。帯域幅は自由に増やすことができます。ギガビット ネットワーク カードを 10 ギガビット ネットワーク カードに交換するのは、コストの問題だけです。ただし、レイテンシーは物理的な制限であり、これを減らすことは基本的に不可能です。

これによって生じる問題は、システム全体のパフォーマンスの低下であり、リソースのロックなどの一連の問題を引き起こします。したがって、システムコールでは通常、自己保護のためにタイムアウト期間を設定する必要があります。ただし、遅延が過度になると、システムの RPC 呼び出しがタイムアウトになり、分散システム コールの結果が成功、失敗、タイムアウトの 3 つの状態になるという問題が生じます。この 3 番目の状態を過小評価しないでください。これは、ほぼすべての分散システムの複雑さの根源です。

この問題には、非同期化と失敗時の再試行といういくつかの解決策があります。 IDC間データ配信によるネットワーク要因の大きな影響については、データ同期、プロキシ専用線などの処理方法が一般的に採用されています。

ネットワーク障害: パケット損失、障害、ジッター。

これは、TCP などの信頼性の高いトランスポート プロトコル上にサービスを構築することで解決できます。しかし、それはより多くのネットワーク相互作用をもたらします。したがって、パフォーマンスとトラフィックの間にはトレードオフが存在します。モバイル インターネットではこの点をさらに考慮する必要があります。

0x02: ケーキを食べて、それをまた食べることはできない — CAP 定理

• CAP 理論は、Eric Brewer によって提唱された分散システムにおける最も重要な理論の 1 つです。
• 一貫性: 一貫性、トランザクション保証、ACID モデル。
• 可用性: [高] 可用性、単一ポイントを回避するための冗長性、および少なくとも柔軟な可用性 (サービスの低下)。
• パーティション耐性: [高] スケーラビリティ (パーティション耐性): 通常、HBase など、オンデマンドで自動的に拡張できるシステムが必要です。

CAP 原則によれば、これら 3 つの要素のうち最大でも 2 つを満たすことができ、3 つすべてを考慮することは不可能です。分散システムの場合、パーティション耐性は基本的な要件であるため、一貫性を放棄する必要があります。大規模な Web サイトの場合、パーティション耐性と可用性の要件が高くなるため、通常は一貫性を適切に放棄することを選択します。 CAP 理論に対応して、NoSQL は AP を追求し、従来のデータベースは CA を追求します。これにより、従来のデータベースのスケーラビリティが制限される理由も説明できます。

3 つの CAP のうち、「スケーラビリティ」は分散システムの固有の特性です。分散システムを設計する本来の目的は、クラスター内の複数のマシンの機能を活用して、単一のマシンでは解決できない問題を処理することです。システム パフォーマンスを拡張する必要がある場合、システム パフォーマンスを最適化するか、ハードウェアをアップグレードする (スケール アップ) というアプローチと、単にマシンを追加してシステムのサイズを拡張する (スケール アウト) というアプローチがあります。優れた分散システムは常に「線形スケーラビリティ」を追求します。つまり、クラスターの数に応じてパフォーマンスが線形に向上します。

可用性とスケーラビリティは一般的に関連しています。スケーラビリティに優れたシステムは、単一の整合性ポイントではなく複数のサービス (データ) ノードが存在するため、一般的に可用性が高くなります。したがって、分散システムのすべての問題は、基本的に一貫性、可用性、およびスケーラビリティの間の調整とバランスです。ステートレス システムの場合、一貫性の問題はありません。 CAP 原則によれば、可用性とパーティション許容度は非常に高く、マシンを追加するだけで線形拡張を実現できます。ステートフル システムの場合、ビジネス要件と特性に基づいて、3 つの CAP のうち 1 つを犠牲にする必要があります。一般的に、トランザクション システム ビジネスでは一貫性に対する要件が高く、データの強力な一貫性を確保するために ACID モデルが採用されることが多いため、可用性と拡張性は比較的低くなります。他のほとんどのビジネス システムでは、最終的に一貫性が保たれる限り、一般的に強力な一貫性を確保する必要はありません。一般的には BASE モデルを採用し、最終的な一貫性の考え方を使用して分散システムを設計することで、システムの高い可用性とスケーラビリティを実現します。

CAP 定理は、実際には分散システムを測定するための重要な指標です。もう一つの重要な指標はパフォーマンスです。

一貫性モデル

主なタイプは3つあります。

• 強力な一貫性: 新しいデータが書き込まれると、いつでもどのレプリカでも新しい値を読み取ることができます。たとえば、ファイル システム、RDBMS、Azure テーブルはすべて強力な一貫性を備えています。
• 弱い一貫性 (弱い一貫性): 異なるレプリカ上の値は新旧両方であり、アプリケーションは最新の値を取得するためにより多くの作業を行う必要があります。たとえば、ダイナモ。
• 長期的な一貫性: 更新が成功すると、各レプリカのデータは最終的に一貫性を持つようになります。

これら 3 つの整合性モデルから、Weak と Become は一般に非同期冗長であるのに対し、Strong は一般に同期冗長 (マルチ書き込み) であることがわかります。非同期は通常、パフォーマンスが向上することを意味しますが、状態制御がより複雑になることも意味します。同期は単純さを意味しますが、パフォーマンスの低下も意味します。

その他のバリエーション:

• 因果的一貫性: プロセス A がプロセス B にデータを更新したことを通知すると、プロセス B のその後の読み取り操作では A によって書き込まれた最新の値が読み取られますが、A と因果関係のない C は結果的一貫性を実現できます。
• 書き込みの読み取り一貫性: プロセス A が最新の値を書き込むと、プロセス A の後続のすべての操作で最新の値が読み取られます。ただし、他のユーザーがそれを見るまでにはしばらく時間がかかる場合があります。
• セッションの一貫性: セッション内で値が読み取られると、古い値は読み取られなくなります。
• 単調な読み取り一貫性: ユーザーが一度値を読み取ると、その値より古い値は読み取れませんが、他のユーザーはその値を読み取れない可能性があります。

最も重要なバリエーションは、2 番目の「Read-your-Writes Consistency」です。特にデータ更新の同期に適しています。ユーザーの変更はユーザー自身にはすぐに表示されますが、他のユーザーには古いバージョンしか表示されません。 Facebook のデータ同期はこの原則を採用しています。

0x03: 分散システムの共通技術と応用シナリオ

• 一貫性ハッシュ法 [仮想ノードを使用]: 一貫性ハッシュ法、データ分散
• ベクトルクロック: クロックベクトル、マルチバージョンデータの変更
• クォーラム W+R>N [ベクトル クロック付き]: ドロワー原理、データ一貫性のもう 1 つのソリューション。クロックベクター、マルチバージョンデータの変更。
• マークルツリー[反エントロピー付き]: データ複製
• MVCC: コピーオンライトとスナップショット
• 2PC/3PC: 分散トランザクション
• Paxos: 強力な一貫性プロトコル
• 対称性と分散化: 対称性と分散化。 Symmetry により、システムの構成とメンテナンスが簡素化されます。分散化は対称性の拡張であり、単一のマスターポイントを回避し、クラスターのスケールアウトを容易にすることができます。
• Map-Reduce: 分割して統治する;データを移動することは計算を移動することほど良くありません。ストレージ ノードと同じ物理マシン上のコンピューティング ノードに計算をスケジュールするようにします。これをローカライズ コンピューティングと呼びます。ローカライズされたコンピューティングは、コンピューティング スケジューリングにとって重要な最適化です。
• ゴシッププロトコル: ノード管理
• リースの仕組み:

一貫性のあるハッシュ：一貫性のあるハッシュは、バランスのとれたデータ分散の問題を解決します。

通常使用するハッシュ アルゴリズムは hash() mod n ですが、ノードに障害が発生した場合、他のノードにすばやく切り替えることはできません。単一点障害の問題を解決するために、各ノードにバックアップ ノードを追加します。ノードに障害が発生すると、データベースのマスターとスレーブと同様に、自動的にバックアップ ノードに切り替わります。しかし、ノードを追加または削除した後のハッシュ再配布の問題は依然として解決できず、つまり、ノードを動的に追加または削除することはできません。このとき、コンシステント・ハッシュの概念が導入されます。すべてのノードはハッシュ リング上に分散されます。各リクエストは、このハッシュ リング上の特定の位置に該当します。必要なのは、時計回りの最初のノード、つまり必要なサービス ノードを見つけることだけです。ノードに障害が発生した場合、リング上で次に利用可能なノードを見つけるだけで済みます。

一貫性ハッシュ アルゴリズムは、memcached などの分散キャッシュで最も一般的に使用されます。 Dynamo ではこれをデータ分散アルゴリズムとしても使用し、一貫性アルゴリズムを改良し、仮想ノードに基づく改良アルゴリズムを提案しています。中心となるアイデアは、仮想ノードを導入することです。各仮想ノードには対応する物理ノードがあり、各物理ノードは複数の仮想ノードに対応できます。

コンシステント ハッシュの詳細については、著者による別のブログ投稿「Memcached の分散アルゴリズムの学習」を参照してください。

こちらの記事もお読みください: 分散アプリケーションにおける一貫性のあるハッシュに関するいくつかの問題

仮想ノード

前述したように、コンシステントハッシュの実装の中には、仮想ノードという考え方を採用しているものもあります。一般的なハッシュ関数を使用すると、サーバー マッピングの場所の分布が非常に不均一になります。そこで、仮想ノードという考え方を利用して、連続体上の各物理ノード（サーバー）に100～200ポイントを割り当てます。これにより、不均等な分散が抑制され、サーバーが追加または削除されたときにキャッシュの再分散が最小限に抑えられます。

クォーラム W+R>N: 引き出しの原理、データの一貫性のためのもう 1 つのソリューション

N: 複製されたノードの数、つまり保存されるデータのコピーの数。 R: 読み取り操作を成功させるために必要な最小ノード数、つまり、読み取りが成功するたびに必要なコピーの数。 W: 書き込み操作を成功させるために必要な最小ノード数、つまり、書き込みが成功するたびに必要なコピーの数。

したがって、W+R>N は、N 個のコピーを持つ分散システムの場合、W (W<=N) 個のコピーへの書き込みは書き込み成功と見なされ、R (R<=N) 個のコピーのデータを読み取ると読み取り成功と見なされることを意味します。

これら 3 つの要素によって、可用性、一貫性、パーティション耐性が決まります。 W+R>Nはデータの一貫性を保証できます（C）。 W が大きいほど、データの一貫性が高くなります。この NWR モデルでは、CAP の選択はユーザーに任されており、ユーザーは機能性、パフォーマンス、コスト効率の間で独自のトレードオフを行うことができます。

分散システムの場合、N は通常 3 より大きくなります。つまり、単一点障害を防ぐために、同じデータを 3 つ以上の異なるノードに保存する必要があります。 W は、書き込み操作を正常に実行するために必要な最小ノード数です。ここでの書き込み成功は、「同期」書き込みとして理解できます。たとえば、N=3、W=1 の場合、1 つのノードが正常に書き込まれると、他の 2 つのデータのコピーは非同期的にコピーされます。 R は、読み取り操作を正常に実行するために必要なノードの最小数です。読み取り操作でデータの複数のコピーを読み取る必要があるのはなぜですか?分散システムでは、異なるノード間でデータが矛盾する場合があります。一貫性を高めるという目的を達成するために、複数のノードで異なるバージョンを読み取ることを選択できます。

NWR モデルの一部の設定により、ダーティ データやバージョンの競合が発生する可能性があるため、この問題を解決するために、通常はベクトル クロック アルゴリズムが導入されます。

システム内で利用可能なノードが最大(N-W+1、N-R+1)個あることを確認する必要があります。

NWR モデルに関しては、非常に理解しやすい「分散システムにおけるトランザクション処理」を読むことをお勧めします。

ベクトルクロック: クロックベクトル、マルチバージョンデータの変更

非常に分かりやすく書かれた「分散システムにおけるトランザクション処理」を参照してください。

リースの仕組み

Chubby または Zookeeper からリースを取得したノードは、システムからコミットメントを受け取ります。データ/ノード ロールなどは有効であり、有効期間中は変更されません。

リースメカニズムの特徴:

• リース発行プロセスでは、ネットワーク上の一方向の通信のみが必要であり、発行者から受信者に同じリースを繰り返し送信できます。発行者がリースの送信に時々失敗する場合でも、発行者はリースを再送信するだけで問題を解決できます。
• マシンのダウンタイムはリースのメカニズムにほとんど影響を及ぼしません。発行者がダウンした場合、ダウンタイムの発行者は通常、以前のコミットメントを変更することができず、リースの正確性に影響を与えません。発行者のマシンが復旧した後、発行者が以前のリース情報を回復すれば、発行者は引き続きリース契約を遵守できます。発行者がリース情報を回復できない場合は、最大リース タイムアウト期間を待機するだけですべてのリースが無効になるため、リース メカニズムが破壊されることはありません。
• リース メカニズムは有効期間に依存しており、発行者と受信者のクロックが同期されている必要があります。 （１）発行者の時計が受取人の時計よりも遅い場合、受取人がリースの期限が切れたと判断した場合でも、発行者はリースを有効とみなすことがあります。受取人は、リースの有効期限が切れる前に新しいリースを申請することでこの問題を解決できます。 （２）発行者のクロックが受信者のクロックよりも速い場合、発行者はリースの期限が切れたと判断して他のノードにリースを発行し、コミットメントが失敗し、システムの正確性に影響を与える可能性があります。このようなクロックの非同期の場合、通常は、リースの有効性に影響を与えないように、発行者の有効期間を受信者の有効期間よりわずかに長く、クロック エラーよりわずかに長く設定します。

エンジニアリング プロジェクトでは、一般的に選択されるリース期間は 10 秒です。これは検証された経験値であり、実践においては適切な期間を総合的に選択するための参考として使用できます。

デュアルマスター問題（スプリットブレイン問題）

リース メカニズムは、ネットワークの分割によって発生する「デュアル マスター」問題、いわゆる「スプリット ブレイン」現象を解決できます。構成センターはノードにリースを発行し、そのノードがプライマリ ノードとして機能できることを示します。構成センターがプライマリに問題を発見した場合、以前のプライマリのリースが期限切れになるまで待つだけで、その後は「デュアル マスター」の問題なしに、新しいプライマリ ノードに新しいリースを安全に発行できます。実際のシステムでは、リースを送信するための構成センターとして中央ノードを使用する場合にも大きなリスクがあります。実際のシステムでは、常に複数の中央ノードを互いのコピーとして使用して、小さなクラスターを形成します。この小さなクラスターは高い可用性を備えており、外部にリースを発行する機能を提供します。 Chubby と Zookeeper はどちらもこのデザインに基づいています。

Chubby は通常、クラスターを形成する 5 台のマシンで構成され、2 つの場所と 3 つのコンピューター ルームに展開できます。 Chubby 内の 5 台のマシンは、Paxos プロトコルを通じて Chubby マスター マシンを選択する必要があります。他の機械はチャビー奴隷です。同時に存在する Chubby マスターは 1 人だけです。ロック情報やクライアント セッション情報などの Chubby 関連データは、半同期アプローチを使用してクラスター全体に同期する必要があります。半数以上のマシンが成功した場合、クライアントに応答できます。最後に、元の Chubby マスターと完全に同期された 1 つの Chubby スレーブだけが新しい Chubby マスターとして選択されるようにすることができます。

ゴシッププロトコル

ゴシップは、P2P システム内の自律ノードによって、クラスターに関する情報 (クラスターのノード ステータスや負荷状態など) を取得するために使用されます。システム内のノードは定期的に互いに噂話をし、すぐにその噂話はシステム全体に広がります。ノード A と B がゴシップを行う主な方法は、A が B に誰についてのゴシップの内容を伝えることです。 B は、B が知っているゴシップのうちどれが更新されたかを A に伝えます。 BはAから聞いた噂話を更新する…自律システムと呼ばれていますが、実際にはノードの中にいくつかのシードノードが存在します。シード ノードの役割は、主に新しいノードがシステムに参加したときに反映されます。新しいノードがシステムに参加すると、最初にシード ノードとゴシップを行います。新しいノードはシステム情報を取得し、シードノードはシステム内に新しいノードがあることを認識します。他のノードは、シードノードと定期的にゴシップすることで、新しいノードが参加したことを認識します。ノード間のゴシップのプロセス中に、特定のノードのステータスが長時間更新されていないことが判明した場合、そのノードはクラッシュしたと見なされます。

Dynamo は、メンバーシップと障害検出に Gossip プロトコルを使用します。

2PC、3PC、Paxos プロトコル: 分散トランザクションのソリューション

分散トランザクションは実行が難しいため、必要な場合を除き、分散トランザクションを回避するために結果整合性が一般的に使用されます。

現在、分散トランザクションを実装する唯一の基盤となる NoSQL ストレージ システムは、Google のシステムです。 Bigtable 上に Java 言語でシステム Megastore を開発し、2 フェーズ ロックを実装し、2 フェーズ ロック コーディネーターのダウンタイムによって発生する問題を Chubby で回避しました。 Megastore の実装は簡単に紹介されただけで、関連する論文はまだありません。

2PC

実装は簡単ですが、効率は低いです。すべての参加者がブロックする必要があり、スループットは低くなります。フォールト トレランスは存在せず、1 つのノードに障害が発生すると、トランザクション全体が失敗します。参加者が第 1 段階の完了後に第 2 段階で決定を受け取らない場合、データ ノードは「混乱」状態になり、トランザクション全体がブロックされます。

3PC

2PC の改良版では、2PC の最初のセグメントが、クエリ、リソースのロック、そして最後に実際の送信という 2 つのセグメントに分割されます。 3PC の核となる概念は、要求時にリソースはロックされず、全員が同意した場合にのみリソースがロックされるというものです。

3PC が 2PC よりも優れている点は、ノードが P 状態 (PreCommit) にあるときに障害/タイムアウトの問題が発生した場合、2PC では状況が変わらないのに対し、3PC では状態を C 状態 (Commit) に直接変更できることです。

ただし、3PC は実装が難しく、ネットワーク分離の問題に対処できません。 preCommit メッセージが送信された後に 2 つのコンピュータ ルームが切断された場合、コーディネータがいるコンピュータ ルームは中止され、残りの参加者がコミットします。

パクソス

Paxos の目的は、クラスター全体のノードが値の変更について合意に達するようにすることです。 Paxos アルゴリズムは、メッセージ パッシングに基づくコンセンサス アルゴリズムです。 Paxos アルゴリズムは基本的に民主的な選挙アルゴリズムであり、多数決の決定がクラスター全体の統一された決定になります。

どのノードも特定のデータの変更を提案できます。提案が承認されるかどうかは、クラスター内の半数以上のノードが同意するかどうかによって決まります (そのため、Paxos アルゴリズムではクラスター内のノード数が奇数である必要があります)。これが Paxos と 2PC および 3PC の最大の違いです。 2f+1 ノードのクラスターでは、f ノードが使用不可になることが許容されます。

Paxos の分散型民主的選挙方式は、データ変更の一貫性を確保するだけでなく、マスター選挙などの単一ポイントの切り替えにもよく使用されます。

Paxos プロトコルの特徴は、理解するのも実装するのも難しいことです :(

2PC、3PC、Paxos に関しては、「分散システムにおけるトランザクション処理」を読むことを強くお勧めします。

現在、ほとんどの決済システムは 2PC に基づいて改善を続けています。一般的に、エラー調整 (ロールバックまたは失敗処理) を実行するためにエラー ハンドラが導入されます。

MVCC: マルチバージョン同時実行制御

これは、多くの RDMS ストレージ エンジンが高同時変更を実現するための重要な実装メカニズムです。詳細については以下を参照してください。

1. 分散システムにおけるマルチバージョン同時実行制御（MVCC）の応用

2. MVCC (Oracle、Innodb、Postgres).pdf

マップリデュースのアイデア

1. 分割して征服する

2. モバイルデータはモバイルコンピューティングほど優れていない

コンピューティング ノードとストレージ ノードが異なる物理マシン上に配置されている場合、計算されたデータをネットワーク経由で転送する必要があり、コストが非常に高くなります。もう 1 つのアプローチは、可能な限りストレージ ノードと同じ物理マシン上のコンピューティング ノードに計算をスケジュールすることです。これは、ローカライズ コンピューティングと呼ばれます。ローカライズされたコンピューティングは、コンピューティング スケジューリングにとって重要な最適化です。

古典論文と分散システム学習

ダイナモ

HBase

LSMツリー

• LSM（ログ構造マージツリー）はB+ツリーの改良版である。
• 読み取りパフォーマンスをある程度犠牲にして、書き込みパフォーマンスを大幅に向上
• アイデア: ツリーを分割する (1) 最初に WAL を書き込み、次にデータをメモリに記録して順序付けされたサブツリーを構築する (memstore) (2) サブツリーが大きくなると、メモリ内のサブツリーがディスクにフラッシュされる (storefile) (3) データの読み取り: すべての順序付けされたサブツリーをトラバースする必要がある (データがどのサブツリーにあるかは不明) (4) 圧縮: バックグラウンド スレッドがディスク上のサブツリーを大きなツリーにマージする (サブツリーが多すぎると読み取りが遅くなる)

実際、Lucene のインデックス作成メカニズムは HBase の LSM ツリーに似ています。書き込み時には、データは個別のセグメントに書き込まれ、バックグラウンドでセグメントが結合されます。