合意アルゴリズム の記事

Raft合意アルゴリズム入門 - リーダー選出とログ複製を実装で理解する

分散合意アルゴリズムRaftを、OngaroとOusterhoutの原論文を一次ソースに整理します。単一障害点を消すための状態機械複製という出発点、Paxosの難解さに対して理解しやすさを設計目標に据えた経緯、Follower・Candidate・Leaderの3状態とtermという論理時計、election timeoutのランダム化がsplit voteを解消する仕組み、AppendEntriesとcommitIndex、Log Matching PropertyとElection Restriction、2f+1台でf台の故障に耐えるクォーラムの算術、joint consensusとスナップショット、etcd・Consul・TiKV・CockroachDBでの実装、そしてReadIndexとlease readまで、実際に動かして出力を確認したPythonシミュレータで解説します。