Paxos Made Live - An Engineering Perspective を読んだ
Paxos Made Live - An Engineering Perspectiveを読んだ時のメモ。
どんなもの?
- Paxosを実際のプロダクト(Chubby)で使用するために行った挑戦とその際に選択したアルゴリズムについて
先行研究とくらべて何がすごい?
- Paxosを実装し、Chubbyに組み込んだこと
- 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
- Handling disk corruption
- Master leases
- Epoch numbers
- Group membership
- Snapshots
- Data transaction
- 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
技術や手法の肝は?
- Background
- Architecture outline
- Fault-tolerant replicated Log
- 全てのレプリカは同一順序のエントリーをローカルログに持っている
- Fault-tolerant DB
- 下記から成る
- local snapshot
- DBの操作に関するreploy-log
- Chubbyが自分の状態を保存するのにも使う
- 下記から成る
- Fault-tolerant replicated Log
Paxos Basics
- 3つのフェーズがある
- 現実ではcoordinatorもfailするかもしれない
- Paxosではcoordinatorは一度に1つとは言っていない
- 複数のreplicaがcoordinatorとなるようにした
- 複数のcoordinatorがそれぞれ別の値を選ぶかもしれない
- Paxosは2つの追加のメカニズムを導入することで1つの値で同意に到れるようにした
- 1. succesive coordinatorの順番を決める - 前回と今回のcoordinatorを区別する - propose/promise messageで番号を送っているのでそれで区別 - 2. 値を選択する時に、coordinatorが取れる選択肢を制限する - promise messageに直近acceptした値を入れて返す
- Paxosではcoordinatorは一度に1つとは言っていない
Algorithmic challenges
- Handling disk corruption
- メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
- diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
- Paxosアルゴリズムの主要な仮定に違反する
- diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
- diskの破損の2パターン
- ファイルの内容の変更された - チェックサムをいれる
- ファイルにアクセスできなくなった
- 空のdiskを持つ新しいreplicaと区別がつかない
- 新しいreplica起動時にGFSにマーカーを残すことで検出する
- replicaが空のdiskから再開されると検出される
- 破損したdiskを持つreplicaの再構築
- non-votingメンバーとしてPaxosに参加する
- 最新の状態に追いつくためにcatch-up メカニズムを使用するが、promise/acknowlegement メッセージには反応しない
- replicaが再構築されたと観測されるまでこの状態
- まだこれは実装されていない
- non-votingメンバーとしてPaxosに参加する
- メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
Master leases
- 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
- 他のレプリカが別のマスターを選択肢、古いマスターに通知すること無くデータ構造が変わった場合
- master leaseを実装してこの問題を回避する
- masterにleaseがある限り、他のレプリカがPaxosに値を正常に送信できないことが保証される
- leaseを持つmasterがlocal dataに構造に最新の情報を持ち、localでの読み取り操作を行うことが出来る
- leaseの期限切れになるまでに、マスターが更新しようとするので一度に数日間くらいleaseを持つ
- まだ実装されていない
- 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
Epoch numbers
- master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
- Chubbyは管理権が失われたり、再獲得されるとrequestの受付を中止する必要がある
- グローバルエポックnumberを導入した
- 2つのrepuestの間に連続してそのレプリカがmasterだったら、同じ値を受け取る
- DBのエントリとして保存され、DBの操作はエポック番号の値を条件とする
- master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
- Group membership
- 現実のシステムでは一連のreplicaの変更を処理する必要がある
- group membership
- 文献には書かれていないし、アルゴリズムの正当性も証明されてない
- 実システムでは必要なので実装した
- 現実のシステムでは一連のreplicaの変更を処理する必要がある
- Snapshots
- Database transactions
- ChubbyでのDB要件はkey-valueのペアを保存できて、一般的なDB操作(insert, delete, lookup, an atomic compare and swap)ができることだった
- DB全体のsnapshotをとるのとsnapshotに適用したDB操作のログ(Paxos)に使えるように設計した
- 定期的にDBの状態をsnapshotにとり、それに応じてログを削除する
- Handling disk corruption
どうやって有効と検証した?
- 元々使われていた3DBと、自分たちで実装したDBを使用したChubbyのパフォーマンスを測定して比較した
- 全体的にPaxosを利用した方がパフォーマンスが良い
- replicated log sizeが100MBを超えるとsnapshotをとるように設定されており、そこでdiskに書き込むのでパフォーマンスが一時的に低下した
- この部分の最適化の余地があるが、3DBよりはパフォーマンスが出ているので手を付けなかった
議論はある?
- まだまだ最適化の余地がある
- snapshot等
- Paxosアルゴリズムの説明と実システムでのニーズには大きなギャップがある
- The fault-tolerance computing communityはアルゴリズムの実装を容易にするツールを開発していない
- The fault-tolerance computing communityは耐障害性システムを構築するために重要な要素であるテストに十分な注意を払っていない
次に読むべき論文は?
In Search of an Understandable Consensus Algorithm(Extended Version)