分散コミットと合意形成

分散コミットおよび合意形成プロトコルは、複数のデータベースノードがトランザクションの結果と操作の一貫した順序についてアトミックに合意することを可能にします。これは、ノードやネットワークが障害を起こす可能性がある場合でも同様です。

Definition

アトミックコミットメントとは、分散トランザクションに参加するすべてのノードが、そのトランザクションをコミットするかアボートするかのいずれかに合意することを保証する問題です。合意形成は、障害にもかかわらず分散ノードが単一の値または順序付けられたログについて合意するという、より一般的な問題であり、データベースレプリカの一貫性を保つために使用されます。

Scope

このトピックでは、サイトをまたがるトランザクションのアトミックなコミットメント、すなわち二相コミットプロトコル、そのブロッキングの弱点、および非ブロッキング三相コミットについて扱います。また、複製されたステートマシンとコミットログの一貫性を保つために使用される合意形成プロトコル（Paxos、Raft）についても取り上げます。これらのメカニズムを、データベースにおけるアトミック性とレプリカ合意を保証する役割として扱います。合意形成、障害モデル、および不可能性の結果に関する一般的な分散システム理論については、分散コンピューティングのトピックに譲り、ここではそれらを引用するにとどめ、重複は避けます。

Core questions

• 二相コミットはどのようにしてノード間でアトミックなコミットメントを達成するのでしょうか？
• 二相コミットはなぜブロックする可能性があり、三相コミットはどのようにそれに対処するのでしょうか？
• PaxosやRaftのような合意形成プロトコルは、どのようにしてレプリカ間の一致を保つのでしょうか？
• 複製データベースにおける合意形成は、アトミックコミットメントとどのように関連していますか？
• 障害やネットワークパーティションは、これらのプロトコルが提供する保証にどのように影響しますか？

Key concepts

• アトミックコミットメント
• 二相コミット (2PC)
• コーディネーターと参加者
• ブロッキングとコーディネーター障害問題
• 三相コミット (3PC)
• Paxos
• Raft
• 複製ログ / ステートマシンレプリケーション

Key theories

二相コミット

コーディネーターはすべての参加者に準備（投票）を求め、すべての参加者が「はい」と投票した場合にのみコミットを指示します。このプロトコルはアトミック性を保証しますが、参加者が不確実な状態にある間にコーディネーターが障害を起こすとブロックします。

非ブロッキングコミットメント

三相コミットはプリコミットフェーズを追加することで、コーディネーターが障害を起こした場合でも参加者が一貫した決定に達することを可能にし、特定の障害仮定の下での二相コミットのブロッキング動作を排除します。

複製状態のための合意形成

Paxosと、より理解しやすいRaftは、一連のレプリカがクラッシュにもかかわらず操作の順序付けられたログについて合意することを可能にし、現代のデータベースがコミット決定と構成を複製するために使用するフォールトトレラントな合意を提供します。

Clinical relevance

分散コミットと合意形成は、マルチノードデータベースを信頼性の高いものにするものです。これらは、複数のシャードにまたがるトランザクションが、すべてコミットされるか、あるいはどこにもコミットされないかのいずれかであることを保証し、また、障害後に複製されたシステムが分岐しないことを保証します。これは、金融システムやグローバルに分散されたデータシステムにおける正確性にとって不可欠です。

History

二相コミットは、分散アトミック性の初期の標準でした。SkeenとStonebrakerは1983年にそのブロッキング動作を分析し、三相コミットの動機付けとなりました。LamportのPaxos（1998年発表）はフォールトトレラントな合意形成を提供し、Raft（OngaroとOusterhout、2014年）はより理解しやすい代替案を提供しました。現在、これらはいずれも広く使用されている分散データベースのレプリケーションの基盤となっています。

Debates

複製トランザクションにおけるアトミックコミットメントと合意形成

二相コミットはアトミック性を保証しますが、コーディネーターの障害時にブロックします。一方、合意形成に基づくレプリケーションは、より高いコストで障害を許容します。システム設計者は、複製され、パーティション化されたデータ全体でアトミック性と可用性の両方を得るために、コミットと合意形成をどのように組み合わせるかについて議論しています。

Key figures

• Leslie Lamport
• Dale Skeen
• Diego Ongaro
• John Ousterhout

Seminal works

• lamport1998
• skeen1983
• ongaro2014

Frequently asked questions

二相コミットはなぜブロックするのですか、それは問題ですか？

参加者がコミットに投票した後、しかし決定を知る前にコーディネーターが障害を起こした場合、それらの参加者はロックを保持したままになり、安全に自身でコミットまたはアボートすることができません。このブロッキングは、コーディネーターが回復するまでリソースを占有するため、これを軽減または排除するために三相コミットや合意形成に基づくアプローチが開発されました。

合意形成はアトミックコミットメントとどう違うのですか？

アトミックコミットメントは、コミットするために満場一致の合意を必要とします。単一の反対票や障害でもアボートを強制する可能性があります。合意形成は、値について合意するために過半数のみを必要とし、少数のノードが障害を起こしても進行することができます。データベースは、クロスシャードトランザクションにはアトミックコミットメントを使用し、各シャードのレプリカの一貫性を保つためには合意形成を使用します。