春節の旅行チケットラッシュ、チケットシステムの背後にある技術はとても洗練されています!

日常生活において、人々はオンラインショッピング、オンライン決済、地図ナビゲーションなどの便利なアプリケーションに慣れてしまい、それらの背後にあるテクノロジーにはほとんど注意を払っていません。これは当然のことながら、通信ネットワークの飛躍的発展と切り離せないものであり、それらの機能の実現は分散システムの進歩によるものです。この記事では、オンライン チケット購入の例を使用して、分散システムの概念、その中核となる Paxos アルゴリズム、およびネットワーク切断の課題への対処方法について簡単に説明します。

著者 |陳青陽

毎年恒例の春節の旅行ラッシュがまたやってきました。今年の鉄道利用者数は5億1000万人を超え、1日平均1275万人になると予想されている。人々がチケットを早く手に入れようと競い合っている中、12306 コンピュータ システムはどのようにして大量のリクエストに迅速に対応できるのでしょうか?単一のサーバーでは、計算能力が限られているため、何千ものリクエストに迅速に応答することはできません。オフラインのチケット購入ホールにチケット窓口が 1 つしかないのに、10,000 人が列に並んでいるシナリオを想像してください。列に並ぶには寝袋を持参する必要があると思います。

では、チケット発行プロセスをスピードアップして人々の待ち時間を短縮するにはどうすればいいのでしょうか?まず、窓口の職員は手早く作業を進めて非常に速いスピードで作業することができますが、職員一人が作業できるスピードには上限があります。もう一つの方法は、ホール内に複数の窓口を設けて同時にチケットを販売することです。オンラインチケットシステムでも同様です。単一のサーバーで処理できない場合は、複数のサーバーを使用して処理を調整します。これには、「分散システム」の導入が必要です。

分散システムとは何ですか?

簡単に言えば、分散システムとは、タスクを完了するために連携して動作するコンピューターのグループを指します。これらのコンピューターはノードとも呼ばれ、ネットワークを介して接続され、連携して動作しますが、ユーザーには全体として表示されます。 12306 チケットシステムだけではありません。動画を視聴しているときに表示されるおすすめ、検索エンジンによる検索結果、フードデリバリープラットフォームの注文分配などはすべて、分散システムの背後で静かに実行されています。単一のサーバーと比較して、分散システムを使用すると、システムのパフォーマンスと要求応答速度が向上するだけでなく、信頼性も向上します。一部のノードがダウンしたり、ネットワーク接続が失われたりしても、システム全体は引き続きサービスを提供できます。

分散システムにはこれらの利点がありますが、それがもたらす複雑さにより、コンピュータ システムの設計に課題も生じます。これには同時実行性とデータの一貫性の問題が関係します。チケット販売を例に挙げて、次のシナリオを想像してください。北京の張三と広州の李思が同じチケットを購入しようとしています。 Zhang San のチケットリクエストは中国北部のサーバーに配信され、Li Si のリクエストは中国南部のサーバーに配信されます。これら 2 つのサーバーは、2 人のチケット リクエストを並行して処理できるようになりました。システム全体の応答速度は非常に速いですが、チケットの重複販売を防ぐためにシステムを適切に連携するにはどうすればよいでしょうか?

さらに、分散システムのもう一つの大きな特徴は、部分的な障害が発生する可能性があることです。名前が示すように、システムの一部に障害が発生しますが、システムの残りの部分は引き続き動作します。分散システムは、ネットワークで接続された多数のコンピューターで構成されます。当然のことながら、どこかで停電が発生したり、ネットワーク ケーブルが破損したり、コンピュータのオペレーティング システムに障害が発生したりして、コンピュータとネットワーク自体の両方に障害が発生する可能性もあります。 単一のマシンに障害が発生する確率は低くても、コンピュータの数が増えると、システム全体で障害が非常に頻繁に発生します。

簡単な計算ができます。システム内に 1,000 台のコンピューターがあり、各コンピューターは平均して 1 年に 1 回だけ故障するとします (故障の原因は何でもかまいません)。つまり、1 日あたりの障害発生確率は 1/365 です。逆に、1 日あたりに障害が発生しない確率は 1-1/365 となり、これはおよそ 0.99726 に等しくなります。これは高い確率のように思えますが、システム全体では、すべてのマシンが毎日故障しない確率は 0.99726 の 1000 乗、つまり約 0.064 です。ここではネットワークの問題は考慮されていないため、システムが故障しないことはほぼ不可能です。

したがって、分散システムの設計では、一部のノードに障害が発生したり、ネットワークが切断されたりした場合に、どのようにして通常のサービスを提供するかが考慮されなければならない問題です。

分散システムの基礎 - コンセンサスアルゴリズム

コンセンサス アルゴリズムは分散システムにおいて中心的な役割を果たします。共有メモリが存在せず、システムがメッセージを送信することによってのみ通信でき、一部のノードに障害が発生する可能性がある場合でも、システム全体が特定の問題について合意に達することが可能になります。たとえば、特定の議席が販売されたかどうか、張三に販売されたのか李思に販売されたのかなど、システムが実行を続行する前に合意に達する必要があります。

分散システムの先駆者であり、有名なチューリング賞を受賞したレスリー・ランポートは、1990 年に現代のコンセンサス アルゴリズムの基礎となる Paxos アルゴリズムを提案しました。ランポートが Paxos という名前を使用した理由は非常に興味深いものです。パクソスはギリシャのイオニア海にある長い歴史を持つ小さな島です。ランポート氏は、考古学者たちが古代にこの島に「非常勤議会」があったことを発見したのではないかと想像した。国会議員は使者を通じて法案に投票したが、使者は信頼できず、メッセージが届かなかったり遅れたりする可能性もあった。さらに、国会議員が会議に出席しない可能性もあります。この場合、国会議員はどのようにして法案について合意に達することができるのでしょうか?論文の中で、ランポートはパクソス島の架空の議会を枠組みとして使い、信頼性の低い通信環境でも合意形成を達成するためのアルゴリズムを提案し、厳密な数学的証明を行っています。 1990 年に、Lamport は ACM Transactions on Computer Systems に論文を提出しました。査読者は、論文は興味深いが、それほど重要ではないと述べ、パクソスの話に関する部分を削除することを提案した。ランポート氏は、査読者にはユーモアのセンスがなく、論文にいかなる変更を加えることも拒否したと述べた。その後、分散システムのもう一人の先駆者であるバトラー・ランプソンがこの論文を読み、ナンシー・リンチや他の分野のリーダーたちとともに独自の証明を発表しました。このとき、ランポートは論文を再び出版することを検討した。最終的に、同僚のグループの推進により、この論文は 1998 年に出版され、現在では分散システムの基礎となっています。

分散システムの先駆者レスリー・ランポート丨画像ソース: wiki

以下では、チケット販売システムを例に、Paxos アルゴリズムの考え方と、ノードに障害が発生した場合でもコンセンサスに達する方法について簡単に説明します。簡単にするために、システムには 3 つのサーバー (ノード。3 つのノードは Paxos アルゴリズムを実証するために必要な最小数) しかなく、販売されるチケットは 1 つだけであると仮定します (複数のチケットを販売することは、チケットを繰り返し販売するプロセスとして理解することもできます)。さらに、アルゴリズムの前提条件についても簡単に述べる必要があります。

まず、Paxos アルゴリズムでは、ノードに障害が発生した場合、ネットワーク上で誤ったメッセージを送信し続け、システムに干渉するのではなく、完全に応答を停止すると想定しています。修復後はシステムに戻り、応答し続けます。このタイプの障害は、障害後に停止することを意味する「フェールストップ」と呼ばれます。第二に、Paxos は多数決に基づくアルゴリズムです。つまり、合意と見なされるためには、大多数のノードが投票して通過する必要があります。 Paxos では、m 個のノードの障害に対応するために 2m+1 個のノードが必要です。つまり、1 つのノードの障害に対応するには、システムに少なくとも 3 つのノード (他の 2 つは正常に動作している) が必要です。半数以上のノードに障害が発生すると、Paxos アルゴリズムは正常に機能しなくなります。

ここで、これら 3 つのサーバーを区別するために、ノード 1、ノード 2、ノード 3 というグローバル シリアル番号を割り当てます。Paxos アルゴリズムは、各ノードに役割を割り当てます。ここでは、ノード 1 が提案者と受容者の両方であると想定します。ノード 2 と 3 は、受け入れるだけで提案は行わないアクセプタです。ノード 1 は Zhang San からのチケット購入リクエストを受信し、アルゴリズムの最初のステップである PREPARE-PROMISE を開始します。

提案者ノード 1 は、まずその提案 (つまり、Zhang San へのチケットの販売) に一意のシリアル番号 (提案番号) を割り当てます。システム内のすべての提案には、固有のシリアル番号が付けられます。簡単な実装方法は次のとおりです。各ノードは、初期値 0 のカウンターを保持します。新しい提案を行うたびに、カウンターは 1 ずつ増加します。新しい提案のシリアル番号は、カウンター値とノードのグローバル ID で構成される 10 進数に設定され、その間に小数点が置かれます (つまり、{counter}.{ID})。たとえば、ノード 1 の最初の提案には 1.1 という番号が付けられ、2 番目の提案には 2.1 という番号が付けられます。同様に、ノード 2 の最初の提案には 1.2 という番号が付けられ、2 番目の提案には 2.2 という番号が付けられ、以下同様に続きます。このシリアル番号の設計によれば、提案ノード 1 は Zhang San の要求を受信すると、まず他のすべてのノードに PREAPRE メッセージを送信し、提案されたシリアル番号 1.1 を添付します。ここでは、これは PREPARE(1.1) と表記されます。

提案の受信者は、次のロジックに従って応答します。

1. 受信したPREPAREメッセージに添付されている提案シーケンス番号を確認します。

2. 受信した提案番号をローカルの max_id と比較します。より大きい場合は、ローカルの max_id が受信した提案番号に更新され、PROMISE メッセージが返されます。これは、提案者に「メッセージを受け取りました。あなたの提案番号は現在最大です。提案する準備をしてください。あなたの提案番号より小さい番号の提案は受け入れないことを約束します」と伝えることと同じです。

3. 受信した提案番号がローカルの max_id より小さい場合、受信者は応答しないか、提案が失敗したことを提案者に伝える失敗メッセージで応答します。

提案者（ノード 1）が大多数の受容者（自分自身を含む）から PROMISE メッセージを受信すると、全員がその提案を受け入れる準備ができていることがわかります。提案者が多数決の応答を受け取らなかったり、失敗メッセージを受け取ったりした場合は、そのラウンドの提案を放棄することしかできません。彼はローカル カウンターを 1 増やし、新しいラウンドの提案を再度提案して (カウンターが 1 増えるので、提案番号も 1 増えます)、再試行することができます。ノード 1 は、大多数のノードから PROMISE メッセージを受信すると、2 番目のステップである PROPOSE-ACCEPT に入ります。

2 番目のステップでは、ノード 1 は提案番号と特定の値を含む PROPOSE メッセージを送信します。ここでの価値は、誰もが合意に達することを望んでいるものです。この記事のチケット購入の例では、その内容は「Zhang San」であり、チケットがZhang Sanに販売されることを意味します。したがって、ノード 1 から送信されるメッセージは次のようになります。

提案(1.1、「張三」)

メッセージの受信者は、提案を受け入れるか否かを決定する必要があります。彼らの論理は次のとおりです。

1. PROPOSE メッセージ内の提案番号が、これまで受信した中で最大の番号である場合 (つまり、自分の max_id と比較して)、提案を受け入れて ACCEPTED メッセージを返します。

2. それ以外の場合、メッセージは返されないか、提案が失敗したことを提案者に通知する失敗メッセージが返されます。

提案者が大多数のノードから ACCEPTED メッセージを受信した場合、合意に達したことがわかります。 2番と3番の両方がPROPOSEメッセージを正常に受信し、ACCEPTEDメッセージを正常に返したと仮定すると、すべてのノードは「チケットはZhang Sanに販売された」というステータスについて合意に達しています。

要約すると、ここで合意に達するには 2 つのステップが必要でした。最初のステップの目標は、大多数の同意を得ることです。これは、提案者が全員に向かって「データを変更するつもりですが、同意しますか？」と叫ぶのと同じです。過半数が同意した場合にのみ、2 番目のステップが実行され、提案者は実際に提案する値を送信します。

アルゴリズムが最初のステップをスキップし、提案する値を直接送信した場合、異なる受信者が異なる提案者から値を受け取る可能性があることを想像してください。このとき、事前に多数派の同意を求めていないため、受信者は自分が受け取った値が多数派の意見を反映しているかどうかはわかりません。システムには複数のサブグループがあり、それぞれが独自の値を持っているため、グローバルなコンセンサスは存在しません。

完全なPaxosアルゴリズムロジック

これまでのところ、アルゴリズムは正常に実行されていますが、ここでさらに複雑な状況を見てみましょう。

ノード 1 が提案者であるだけでなく、ノード 2 も Li Si の要求を受信するため提案者になると仮定します (すべてのノードがアクセプタであることに注意してください)。現在、システムには 2 人の異なる提案者が存在し、彼らが送信するメッセージは何らかの形で絡み合っている可能性があります。

ノード3が最初にノード1からPREPAREメッセージ（Zhang Sanがチケットを購入）を受信し、つまりPREPARE（1.1）を受信し、PROMISEを返したと仮定します。この時点で、ノード2からPREPAREメッセージ（Li Siがチケットを購入）を受信する、つまりPREPARE（1.2）となる。提案番号 1.2 は 1.1 より大きいため、ノード 2 に PROMISE を返し、max_id を 1.2 に更新します。ノード 1 は、2 番目のステップ PROPOSE(1.1, "张三") で引き続き PROPOSE メッセージを送信しますが、ノード 3 にとっては 1.2 の方が新しい提案であるため、この時点ではノード 3 はその提案を受け入れないことに注意してください。ノード 2 から送信された PROPOSE メッセージのみを受け入れます。

別の状況を考えてみましょう。李斯の作戦は張三の作戦より少し遅いと仮定します。ノード2が提案者となりPREPARE(1.2)を送信すると、ノード3はすでにノード1の提案(提案番号は1.1)を受け入れており、つまりACCEPTEDメッセージが送信されています。この時点で、ノード 2 はさまざまな理由によりノード 1 から PREPARE メッセージを受信して​​おらず、ノード 1 とノード 3 が合意に達したこと (チケットが Zhang San に販売されたこと) をまったく認識していません。次に、Paxos アルゴリズムに従って、ノード 3 がノード 2 から PREPARE(1.2) メッセージを受信すると、1.2 はノード 3 がこれまでに受信した最大の提案番号であるため、ノード 3 は確かにノード 2 に PROMISE メッセージを返します。ただし、ノード 3 は以前の提案 1.1 をすでに受け入れているため、返される PROMISE メッセージには、以前に受け入れた提案のシーケンス番号と値、つまり PROMISE(1.1, "张三") が含まれます。これは、ノード 2 に次のことを伝えます。提案番号を受け取りました。これは確かに最新の提案ですが、以前にシーケンス番号 1.1 の提案を受け入れており、その内容は "张三" です。 2号はメッセージを受け取り、チケットが販売されたことを知ります。このとき、Paxos アルゴリズムによれば、2 番は「Zhang San」に提案したい値を変更し、PROPOSE メッセージを送信し続ける必要があるため、すべてのノードが合意に達することになります。

顧客である李思が見た最終結果は、チケットが売り切れていたということだった。実際、提案者は、以前に受け入れられた値を含む複数の PROMISE メッセージを受信する場合があります。すべての PROMISE の中で最大の提案番号に対応する値を、提案する値として選択します。 PROMISE メッセージに以前に承認された提案に関する情報が含まれていない場合、提案者は当初提案したかった値を引き続き使用します。更新されたアクセプターとプロポーザーの完全なロジックは、それぞれ次の図に示されています。

PREPARE-PROMISE プロセス。

これは完全な Paxos アルゴリズムです。最後に、ネットワーク切断やノード障害の状況を簡単に考えて、障害状態でも Paxos が正常に実行される仕組みを確認しましょう。

ネットワークまたはノード障害時の Paxos

提案者と受け入れ者の両方にダウンタイムが発生する可能性があります。受信機がダウンしても、実際にはシステムの動作にほとんど影響はありません。これは分散システムの利点です。一部のノードが PREPARE メッセージまたは PROPOSE メッセージに応答しない場合でも、大多数のノードがオンラインである限り、システムは応答でき、提案者は大多数のノードから応答を受け取ることができるため、アルゴリズムが実行されます。ダウンしたノードが復活すると、他のノードから送信された、以前に承認された提案に関する情報を含む PROMISE メッセージを通じて、最終的に逃したコンセンサスについて知り、ローカルで更新します。

プロポーザー (ノード 1 など) がダウンした場合はどうなりますか?状況は3つあります。

1. PREPARE メッセージを送信する前にクラッシュした場合、システムでは何も起こりません。他のノードは、ユーザーからのリクエストを受信すると新しい提案者になります。

2. 提案者が PREPARE メッセージを送信した後にクラッシュし、PROPOSE をまだ送信していない場合、前述のように、その提案は後で更新された PREPARE (新しい提案者によって送信) に置き換えられます。

3. プロポーザーが最初のステップ PREPARE-PROMISE を完了して 2 番目のステップに入ったが、一部のノードに PROPOSE メッセージを送信した後にクラッシュした場合 (たとえば、No. 1 は No. 3 に PROPOSE メッセージを送信した後にクラッシュし、No. 2 に送信する時間がなかった)。その後、その提案は No. 3 に受け入れられ、No. 2 は最終的に No. 1 と No. 3 が到達したコンセンサスを知ることになります。No. 2 はある時点で提案者になるため、最終的に No. 3 から以前に受け入れられた提案情報を含む PROMISE メッセージを受信し、それに応じてローカル情報を更新し、No. 1 および No. 3 との一貫性を維持します。

それでは、チケットの入手の問題に戻りましょう。クライアントからチケット購入リクエストを送信すると、その背後にある複雑な分散システムと対話します。チケットを取れなかったとしても、必ずしも手が速くないからというわけではありません。また、ネットワークの遅延、サーバーのクラッシュ、またはシステム アルゴリズム自体の動作が原因である可能性もあります。

結論

分散システムは現代のコンピュータ システムの基礎として、12306 チケット購入などの高負荷および高同時実行のシナリオをサポートできます。この記事では、分散システムにおける一貫性とフォールト トレランスの基本概念と技術的な実装について説明します。実際、分散システムの応用はオンラインショッピングだけではありません。暗号化の分野では、分散システムはブロックチェーン技術の基本的なサポートを提供し、データのセキュリティと一貫性を確保します。科学計算の分野では、より大規模な問題を解決するために分散システムも使用されます。これらの分野はすべて、分散システムが私たちの日常生活と技術開発に不可欠な役割を果たしていることを示しています。最後に、もうすぐ春節がやってきます。皆様に、楽しい春節とご家族の幸せをお祈りします。

注: この記事の表紙画像は著作権ライブラリから取得したものです。転載して使用すると著作権上の紛争が発生する可能性があります。

特別なヒント

1. 「Fanpu」WeChatパブリックアカウントのメニューの下部にある「特集コラム」に移動して、さまざまなトピックに関する人気の科学記事シリーズを読んでください。

2. 「Fanpu」では月別に記事を検索する機能を提供しています。公式アカウントをフォローし、「1903」などの4桁の年+月を返信すると、2019年3月の記事インデックスなどが表示されます。

著作権に関する声明: 個人がこの記事を転送することは歓迎しますが、いかなる形式のメディアや組織も許可なくこの記事を転載または抜粋することは許可されていません。転載許可については、「Fanpu」WeChatパブリックアカウントの舞台裏までお問い合わせください。