「最もわかりにくい」Paxos アルゴリズムと、データベースの高可用性におけるその使用法をわかりやすい言葉で理解する

最近、Paxos アルゴリズムについてみんなが議論しています。私はオンラインで多くの記事を読みましたが、いつも、それらはやや不明瞭で理解しにくいと感じていました。しばらく研究した後、Paxos についてある程度理解できました。ここでそれを要約して、議論を刺激したいと思います。

なぜ Paxos なのか?

Paxos が解決しようとしている問題は、分散システムにおける一貫性の問題です。では、「分散システムにおける一貫性の問題」とは一体何なのでしょうか?

分散システムでは、データの高可用性を確保するために、通常、データの複数のコピー (レプリカ) を保持し、これらのコピーを異なる物理マシンに配置します。

レプリカの一貫性を保つには、すべてのレプリカの更新シーケンスが一貫している必要があります。データの追加、削除、変更、およびクエリ操作には通常、複数のクライアントが同時に操作を行う必要があるため、どのクライアントが最初に操作を実行し、どのクライアントが後で操作を実行するかを決定することが重要であり、更新順序が保証される必要があります。

分散されていない場合は、ロック方式を使用できます。最初にロックを申請した人が最初に操作できますが、これにより単一ポイントの問題が発生します。

Paxos プロトコルには主に 2 つの用途があります。

• Google Chubby や Apache ZooKeeper などのグローバル ロック サービスや命名および構成サービスを実装するために使用されます。
• これを使用して、Google Megastore や Google Spanner などの複数のデータセンターにユーザー データを複製します。

分散 KV データベースを例に挙げます。データベースが Put と Get の 2 つの操作を提供すると仮定します。具体的なアーキテクチャは次のとおりです。

このようなアーキテクチャでは、複数のサーバーをクラスター化して、単一ポイントの問題を回避できます。

解決する必要があるのは、3 つのサーバーが同期されたままである必要があることです。つまり、リクエスト Put("a",1) がクラスターに送信され成功した場合、クラスター全体のどのサーバーにも ("a",1) が含まれている必要があります。

さらに、複数のクライアントが同時にクラスターにアクセスすると、異なるクライアントからの要求が異なるサーバー マシンに届く可能性があります。

たとえば、Put("b",2) と Put("c",3) が同時に存在する場合、どのクライアント要求が最初に処理され、どのクライアント要求が後で処理されるかを確認し、更新順序を保証する必要があります。これが、Paxos アルゴリズムが解決する必要がある問題です。

Paxosアルゴリズムを分かりやすく理解する

まず、Paxos アルゴリズムについて簡単に説明して、アルゴリズム自体を直感的に理解し、次に次の例と組み合わせてさらに理解を深めましょう。

Paxos アルゴリズムには、主に 3 つの役割があります。

• 提案者: 提案者
• 受容者: 意思決定者
• 学習者: 最終決定学習者

これを実装する場合、固定数のサーバーが使用されることが多く、各サーバーが上記 3 つの役割を同時に実行します。

Paxos アルゴリズムは次の 3 つのフェーズに分かれています。

準備段階

Proposer は、Proposal(epochNo,value) の準備要求を Acceptor の大多数に送信します。

Acceptor が Prepare リクエストを受信すると、epochNo が以前に受信したものより小さい場合は直接拒否します。epochNo が以前に受信したものより大きい場合は、受信した epochNo *** を含む Proposal を Proposer に返します。

提案者が開始した提案は、次の承認フェーズに入る前に、少なくとも過半数の承認者から準備応答を受け取る必要があります。そうでない場合は、準備フェーズを再度開始し、過半数の承認者に対して準備要求を開始する必要があります。

受け入れフェーズ

提案者は、ほとんどの受け入れ者から準備応答を受け取った後、受け入れ者がすでに承認された提案を持っているかどうかを確認します。

承認された提案がない場合は、提案を提出して承認要求を開始します。すでに承認された提案がある場合は、epochNo *** の提案を選択し、それに対する承認要求を開始します。

アクセプターがリクエストを受信した後、提案の epochNo が準備リクエストに対する最後の応答の epochNo より大きい場合、リクエストは受け入れられ、そうでない場合、リクエストは拒否されます。

学習フェーズ

受諾者によって承認されたすべての提案は、学習者に継続的に通知するか、学習者が積極的に問い合わせることができます。学習者は、提案が受諾者の大多数によって承認されたことを確認します。

これは、提案の価値が選択され、学習者が提案の価値を学習できることを意味します。同時に、自身のサーバーは提案者からのリクエストを受け入れなくなります。

私は例を通して理論を理解するのが好きです。理論は人生から生まれます。以下では、人生からの例を使ってアルゴリズムを説明します。

旅行好きのグループが春節の時期に旅行することにしたとします。全国から 10 人の旅行者がいます。合意に達するために、この 10 人はチームリーダーとなる 5 人をさらに探します。 5人のチームリーダーは互いに連絡を取らず、10人の仲間のハイカーにテキストメッセージのみを送信した。

*** 段階 (申請段階) では、ハイカーは 5 人のチーム リーダーにテキスト メッセージを送信して、チーム リーダーとの通信を申請します。チーム リーダーは、一度に 1 人のハイカーとのみ通信できます。

送信される各テキスト メッセージには時刻が含まれ、船長の原則は、最も遅い時刻にテキスト メッセージが送信されたハイカーと通信することに同意することです。

更新されたテキスト メッセージが表示された場合は、テキスト メッセージの更新を受信した旅行者と連絡を取ります。少なくともチームリーダーのほとんどがコミュニケーションを取ることに同意した場合にのみ、ハイカーは実質的なコミュニケーションの第 2 段階に進むことができます。

第2段階（通信段階）では、通信権を取得した旅行者Aが、チームリーダーから送信された旅行先を受け取ります。次のような状況が考えられます。

***状況***:チームリーダー全員が旅行先を決めていません。この時点で、旅行者Aは行きたい旅行先（モルディブなど）をチームリーダーに送信します。

その結果、ほとんどのチームリーダーが同意し、プロセス全体が完了し、彼らがモルディブに旅行することになり、他の旅行者も遅かれ早かれそれを知ることになるでしょう。

それ以外の場合は失敗を意味します。チームリーダーが返信しなかった（ガールフレンドに電話した）か、他の旅行者が通信権を奪った可能性があります（前述のように、チームリーダーはテキストメッセージを送信した人とのみ通信しました）。

失敗した場合、A は *** ステージ アプリケーションを再起動し、チーム リーダーに再度テキスト メッセージを送信して通信権を申請する必要があります。

2 番目の状況:少なくとも 1 人のチーム リーダーがすでに旅行先を決定しています。この時点で、A は異なるチーム リーダーによって決定された複数の旅行先を受け取ります。これらの旅行先は、異なるチーム リーダーと異なる旅行者によって異なる時期に決定されます。

A はまず、いくつかの観光地が船長の過半数 (半数以上) の同意を得ているかどうかを確認します。同意している場合 (ここでは、3 人の船長が三亜に行くことに決め、1 人がラサに行き、もう 1 人が何らかの理由でそれを無視したと仮定します)、意思決定プロセス全体が同意されたことが証明されます。A は荷物をまとめて三亜に向かいます。終了です。

いずれも半分に達しない場合（たとえば、2 人が三亜に行き、1 人がラサに行き、1 人が昆明に行き、1 人が無視される場合）、A はモルディブに行きたいと思うかもしれませんが、自分の希望どおりには行きません（これがパクソスへの鍵です。後者は前者を認識します。そうでなければ、プロセス全体が無限になります）。

Aは、船長から受け取ったすべての旅行先の中から***が決めたもの（例えば、船長は1分前に​​昆明に行くことを決め、船長は30分前にラサに行くことを決め、船長は1時間前に三亜に行くことを決めた）を見つけるので、Aは***の決定に従って昆明に行きます。

この時点で、昆明行きの決定は再度更新されるため、通信権を握った次のハイカーが昆明に行く可能性が高く、ますます多くのチームリーダーが昆明行きを決定することになります。

ある時点で、大多数（半数以上）の隊長が昆明など特定の場所に行くことに同意すると、その後通信権を取得したハイカー B は、隊長のほとんどが昆明に行くことに決めたことを知り、それに従い、最終的にハイカー全員が昆明に行くことに同意することになります。

Paxos の基本的な考え方は、おおよそ上記のプロセスです。Paxos は選挙の考え方を採用しており、少数派は多数派に従います。

N 個（N は奇数、少なくとも 3 個以上）のノードのうち [N/2]+1 個（N/2 は切り捨て）以上のノードが決定に同意する限り、システムは合意に達したとみなされます。

この方法では、クライアントはすべてのサーバーと通信する必要はなく、ほとんどのサーバーと通信するだけで済みます。また、すべてのサーバーが稼働状態である必要もありません。一部のサーバーに障害が発生した場合でも、半数以上のサーバーが稼働している限り、プロセス全体を続行できるため、フォールト トレランスは非常に優れています。

Paxos の Acceptor は上記の船長に相当し、Proposer は上記の旅行者に相当し、epochNo は例で SMS が送信された時刻に相当します。

Paxos で最も時間のかかる部分は、2 番目のステップに進む前に参加者の半数以上が通信に同意する必要があることです。

想像してみてください、最初はハイカー全員が必死に船長にテキストメッセージを送り始め、各船長はさまざまなハイカーからたくさんのテキストメッセージを受け取ったと。

このように、ある旅行者とのコミュニケーションに旅行者の半数以上が同意する状態を実現するのは難しく、この時間を短縮するために Paxos と Fast Paxos が改良されました。

さらに、Paxos はプロトコルを指すのではなく、プロトコルのクラスを表す一般的な用語です。より一般的な Paxos タイプのプロトコルは、基本 Paxos とマルチ Paxos です。

ここでの例は、基本的な Paxos に関するものです。基本的な Paxos プロトコルはより複雑で、比較的非効率的であるため、Paxos 関連のプロトコルを備えた現在のすべてのシステムは、通常、マルチ Paxos に基づいて実装されています。

ご興味がございましたら、こちらの記事をご覧ください：https://zhuanlan.zhihu.com/p/25664121

データベースの高可用性における Paxos の使用

DBA として、高可用性を実現するために最も一般的に使用される高可用性方式は、マスタースレーブモードです。MySQL を例にとると、主に次の種類があります。

強力な同期レプリケーション

バイナリログがスレーブ データベースに同期された後、スレーブ データベースは、送信が成功したことをクライアントに返す前に、マスター データベースに OK を返します。

これは問題を引き起こします。マスターとスレーブ間のネットワークが不安定になったり、スレーブ データベースがクラッシュしたりすると、マスター データベースはサービスの提供を継続できなくなります。このモデルは強力なデータ一貫性を実現しますが、サービスの可用性を犠牲にします。

非同期レプリケーション

マスター データベースがローカル データベースに正常に書き込むと、スレーブ データベースからの応答を待たずに、成功を示すメッセージをすぐにクライアントに返します。

この方法では、マスター データベースがダウンすると、少量のログがスレーブ データベースに同期されず、部分的なデータ損失が発生する可能性があります。このモードは可用性に優れていますが、データの一貫性が犠牲になります。

準同期レプリケーション

このモードは妥協案です。少なくとも 1 つのスレーブ ノードがログを受信して​​マスターに返した後、クライアントに送信成功を返すことができます。ネットワーク環境が良くない場合は、非同期レプリケーションに退化する可能性があります。

さらに、マスタースレーブモードには、マスターの選択という避けられない問題がもう1つあります。マスタースレーブモードでマスターを選択するために、MMM、MHA、中間層など、長い時間をかけて多くの高可用性ソリューションが生まれてきましたが、理論とアイデアが最先端のものではないことは明らかです。

まとめると、データベースの高可用性に対するマスター/スレーブ アプローチには多くの欠陥があります。このデータ同期方法を改善するには、データベースの高可用性に関するいくつかの要件を整理します。

• データ損失なし
• 継続的なサービス可用性
• マスターを自動的に選択
• 自動フォールトトレランス

上記の 3 つの要件は、Paxos プロトコルのログ同期を使用することで実現できます。もちろん、Paxos プロトコルは基本的な前提に依存する必要があります。

プライマリ サーバーとバックアップ サーバー間のマシンの過半数 (N/2+1) が稼働しており、それらの間のネットワーク通信は正常です。この条件が満たされない場合、サービスを開始できず、データの書き込みや読み取りができません。

したがって、Paxos を使用して redolog または binlog を複製し、可用性と一貫性に優れたクラスターを確保できます。

マスターとスレーブの切り替えを心配する必要はありません。VIPを用意し、バックエンドデータベースの複数のポイントをマッピングするだけです。Paxosは、複数のポイントでの書き込みの一貫性を自動的に保証します。業界では、Alibaba CloudがPaxosまたはraftを使用して、エンタープライズ3ノードのMySQLクラスターを構築しています。

[[216691]]

プラットフォーム部門の DBA である Pu Cong は、2013 年 6 月に Qunar.com に入社しました。現在は、支払いプラットフォーム部門の MySQL データベースと HBase の全体的な運用と保守を担当しています。Qunar.com HBase の運用と保守システムをゼロから構築し、MySQL と Hbase データベースのアーキテクチャ、チューニング、トラブルシューティングに関する豊富な経験を持っています。現在は分散データベース分野の研究と実践に注力しています。