序文#
インターネットシステムがますます複雑になるにつれて、ほとんどのシステムはモノリシックアーキテクチャから分散アーキテクチャに移行しています。ブロックチェーンのような分散技術を基にした技術では、データの整合性とコンセンサスメカニズムに高度に依存しています。
本文では、分散システムの整合性、コンセンサスの概念、およびそのブロックチェーンでの実際の応用と発展について説明します。
分散システム#
整合性の問題#
ビジネスシナリオの複雑化に伴い、同じビジネスはしばしば複数のサーバーでクラスタを提供するようになりましたが、物理的な場所や実行状態が異なるシステムで一致を取る方法は、分散領域の重要な問題となっています。
一般的に、分散システムの整合性を達成するためには、次の 3 つの基準があります。
- 終了可能性
- 同値性
- 正当性
分散トランザクションは、有限の時間内に一致した結果を保証する必要があります。この結果は、あるノードが提案を出し、異なるノードが同じ決定を行う必要があるという条件でなければなりません。
強い一貫性#
このような強い一貫性を理想的な状況で単一のアプリケーションまたは各ノードのパフォーマンス、ネットワーク帯域幅などの設定で達成することは容易ですが、実際のビジネスシナリオでは、このような強い一貫性を実現するためには非常に高いコストがかかります。システムの絶対的な安定性とシステム間の通信の遅延を保証する必要があります。さらに、強い一貫性はシステムのパフォーマンスと拡張性を低下させる可能性があります。
強い一貫性の場合、いつでもすべてのノードのデータが同じである必要があります。強い一貫性には通常、順序一貫性と線形一貫性の 2 つの種類があります。
順序一貫性#
順序一貫性では、すべてのプロセスのグローバルな実行順序と各プロセス自体の順序が一致している必要がありますが、各プロセスのグローバルな順序を物理的な時間に対して一致させる必要はありません。したがって、これは比較的実用的なアプローチです。
線形一貫性#
線形一貫性は、順序一貫性に対して各プロセス間でのグローバルな順序付けのルールを追加し、すべての時点ですべてのプロセスの操作がリアルタイムに同期されるようにします。このような絶対的な一貫性は実践的には非常に難しいものであり、グローバルロックやいくつかの複雑な同期アルゴリズムを使用して実現する必要があります。また、パフォーマンスの犠牲を払うことが多いです。
弱い一貫性#
一方、実際のビジネスシナリオでは、リアルタイムの同期などの絶対的な一貫性は必要ありません。したがって、一部のアクセスを許容したり、一定の時間後に最終的な一致を達成することができます。これらは一部の一貫性を弱めたものとして知られています。
コンセンサスメカニズム#
コンセンサスメカニズムは、分散システム内の複数のノードが特定のトランザクションに合意するメカニズムを指します。コンセンサスの達成に関しては、次の理論と原則があります。
- FLP 不可能性原理
- CAP 原則
- ACID 原則
- BASE 理論
- マルチステージコミット
FLP 不可能性原理#
FLP 不可能性原理は、Fischer、Lynch、および Patterson の 3 人の科学者によって提案された理論であり、ネットワークは信頼性があり、ノードの障害（例：シャットダウン）が許容される非同期システムで、有限時間内に合意を達成することは不可能であることを示しています。
非同期とは、システムの各ノード間の時間の差異があることを意味し、メッセージの応答がノードの障害または転送中の障害によるものかどうかを判断することができないため、メッセージの損失を判断することができません。
CAP 原則#
一方、エンジニアリングの実践では、特定の要件を弱めて実際のビジネスシナリオの要件を満たすことがよくあります。CAP 原則はこの問題を解決するために導入されました。CAP は次のように定義されます。
- Consistency（一貫性）
- Availability（可用性）
- Partition tolerance（分散耐性）
分散システムはこれらの 3 つの特性を同時に保証することはできず、最大で 2 つの特性を保証することができます。この原則にはどのような実際の応用があるのでしょうか？
- AP システムでは、静的なウェブサイト、リアルタイムでないデータベースなどのビジネスシナリオでは、一貫性を弱めることができます。たとえば、新しいバージョンがリリースされてから一定の時間が経過するまで一貫性が達成されません。
- CP システムでは、銀行の送金などの一貫性の要求が非常に敏感なシナリオでは、可用性を弱めることができます。たとえば、システムの障害や失敗時にはサービスを拒否します。
- AC システムでは、2 フェーズコミットやいくつかの関係データベースなど、ネットワークの分割を弱めることができます。たとえば、ZooKeeper など。
ACID 原則#
分散データベースのトランザクションは、一貫性を実現するために一部の可用性を犠牲にする必要があります。ACID 原則に従う必要があります。具体的には次のとおりです。
- Atomicity（原子性）：トランザクションのすべての操作はすべて実行されるか、すべて実行されないかのいずれかであり、失敗した場合はすべてロールバックされます。
- Consistency（一貫性）：トランザクションの実行前後の状態は一貫している必要があり、中間状態は存在しません。
- Isolation（隔離性）：複数のトランザクションは同時に実行できますが、互いに独立しています。
- Durability（耐久性）：状態の変更は永続的です。
BASE 原則#
BASE 原則は次のように定義されます。
- Basically Available（基本的に利用可能）
- Soft State（ソフトステート）
- Eventual Consistency（最終的な一貫性）
これは強い一貫性を犠牲にしてシステム全体を実現するためのアプローチであり、最終的な一貫性のみを保証します。
マルチステージコミット#
2 フェーズコミットはトランザクションのコミットプロセスをプリコミットとコミットの 2 つのステージに分割して衝突を回避しますが、まだ同期ブロッキング、シングルポイントの障害、データの一貫性などの問題があります。
TCC トランザクションメカニズムは次のように分割されます。
- Try ステージ
- Confirm ステージ
- Cancel ステージ
Try ステージでは、ビジネスのチェックとビジネスリソースの予約を行い、Confirm ステージではリソースを使用してビジネスを実行し、Cancel ステージでは実行をキャンセルしてリソースを解放します。この方法は 2 フェーズコミットに対していくつかのビジネス上の処理を行っていますが、3 つのインターフェースに分割されているため、コードの複雑さが増します。
3 フェーズコミットでは、タイムアウトメカニズムが導入され、2 フェーズコミットの最初のステージにトライのプリコミットステージが追加され、シングルポイントの障害とブロッキングの問題が解決されます。
コンセンサスアルゴリズム#
許容エラーの種類（悪意のあるノードが存在するかどうか）に基づいて、コンセンサスアルゴリズムは非ビザンチン容錯（Crash Fault Tolerance, CFT）とビザンチン容錯（BFT, Byzantine Fault Tolerance）の 2 つに分類されます。
CFT（Crash Fault Tolerance）#
分散システムでは、故障ノードが存在するがエラーノードは存在しないシナリオを CFT と呼びます。このようなシナリオでは、メッセージが失われたり重複したりすることがありますが、誤ったメッセージはありません。この条件下での合意の達成方法は、実世界で非常に一般的な要件です。
Paxos#
Paxos アルゴリズムは 2 フェーズコミットに似た原理で、提案者、アクセプター、およびラーナーの 3 つの論理ノードを設定します。提案者が提案を行い、アクセプターが投票と提案の受け入れを行い、ラーナーが提案の結果を取得してブロードキャストします。
提案者が提案を行う場合のみ、提案が承認される可能性がありますが、すべてのノードが提案者になることができます。ただし、各ラウンドの合意は唯一の提案者によってのみ行われるため、このメカニズムは一定の公平性を保証します。
ただし、Paxos は半数以上のノードが参加する場合にのみ正常に動作します。
Raft#
Paxos アルゴリズムの実装は比較的困難であるため、Fast Paxos、Multi-Paxos などのさまざまなバリエーションが登場しましたが、最も代表的なのは Raft アルゴリズムです。
Raft は、一貫性のプロセスをリーダー選出、ログレプリケーション、および安全性の 3 つのサブプロセスに分割します。リーダー、候補者、およびフォロワーの 3 つの論理ノードを設定します。
すべてのノードの初期状態はフォロワーであり、リーダー選出に参加するためには候補者に変わり、選挙リクエストを提出する必要があります。過半数の票数を得ると、その任期内でリーダーになることができます。
リーダーはすべてのリクエストを処理し、ログをフォロワーに同期します。また、定期的にすべてのフォロワーにハートビートメッセージを送信します。障害が発生し、ハートビートメッセージがタイムアウトした場合、新しい選挙プロセスが開始されます。
BFT（Byzantine Fault Tolerance）#
Byzantine Fault Tolerance, BFT#
ビザンチン容錯アルゴリズムは、ネットワークに悪意のあるノードが存在するシナリオを処理するためのもので、ビザンチンの問題に対する解決策です。悪意のあるノードが 1/3 を超えない場合、共通の合意に到達することができますが、複雑さが非常に高い（指数的）です。
Practical Byzantine Fault Tolerance, PBFT#
PBFT は BFT アルゴリズムの最適化であり、RSA 署名、メッセージ検証、ダイジェストなどの暗号技術を使用し、Paxos などの関連アルゴリズムと組み合わせることで、アルゴリズムの複雑さを 2 乗にまで減らしました。
PBFT アルゴリズムでは、まず（ランダム / ローテーション）ノードを選択し、その論理ノードをプライマリノードとします。プライマリノードは自分のビュー内でクライアントのリクエストを受け取り、他のノードにブロードキャストします。すべてのノードがリクエストを処理し終えたら、結果をクライアントに返します。少なくとも 2f + 1 つの異なるノードから同じ結果を受け取った場合、合意が達成されます。
- プリコミットの試行：プライマリノードはメッセージを受け取った後、署名を行い他のノードにブロードキャストします。
- プリコミット：他のノードはメッセージを受け取った後、チェックを行い、署名を行い他のノードにブロードキャストします。他のノードもチェックを行います。
- コミット：メッセージに署名を行い、コミットステータスをブロードキャストします。2f + 1 つの検証を経た場合、システムは合意に達します。
その他#
PBFT 以外にも、PoW、PoS、HotStuff などがビットコイン、イーサリアム、Libra などのブロックチェーンプロジェクトで広く使用されており、改良が進められています。効率が低いため、ビザンチン容錯型のアルゴリズムは主にパブリックチェーン環境で使用され、コンソーシアムチェーンでは非ビザンチン容錯の方法が多く採用され、パフォーマンスとセキュリティをバランスさせています。
まとめ#
以上が分散システムとブロックチェーンのコンセンサスメカニズムの概念と実際の応用の概要です。今後は、業界で広く使用されているさまざまなコンセンサスアルゴリズムについてさらに詳しく調査します。