Raftは理解と実装の容易性に重きを置いた合意アルゴリズムだ. 合意アルゴリズムは複数のサーバが何か1つの値について合意するために使われる. このアルゴリズムは2014年に発表された. PFIがSlideを作ってくれているからこれを読めば大体は分かる. しかしもっと詳しく知りたい人は論文を読むしかない. Raft自体の説明はここでは省く.
上のスライドはIn search of an understandable consensus algorithmという学会論文に基いて調査されているけど, 博士論文の方にはさらに詳しく書かれている.
おれはRaftの調査のため今これを読んでいる. 読んでおれが理解するだけではもったいないから, みんなに知識を共有する.
Most membership change algorithms introduce additional mechanism to deal with such prob- lems. This is what we did for Raft initially, but we later discovered a simpler approach, which is to disallow membership changes that could result in disjoint majorities. Thus, Raft restricts the types of changes that are allowed: only one server can be added or removed from the cluster at a time.
Raftでクラスタの構成を変更(Membership Changeという)する時, 問題は2つのリーダーが選出されてしまうことを避けることだ. この解決のために, いかなるクラスタ構成 (C_old)から別のクラスタ構成(C_new)に変更しようとも, あらゆる合意(リーダー選出含む)が1つしかされないこと保証するために著者が最初に考えていたことは, C_oldとC_newの両方から合意をとらないといけない厳しい中間状態を経るというアイデアで, Joint Consensusと呼ばれている.
This joint consensus approach is more complex than the single-server changes precisely because it requires transitioning to and from an intermediate configuration. Joint configurations also require changes to how all voting and commitment decisions are made; instead of simply counting servers, the leader must check if the servers form a majority of the old cluster and also form a majority of the new cluster. Implementing this required finding and changing about six comparisons in our Raft implementation
しかしよくよく考えてみると, そんな柔軟なクラスタ変更は実際には要らない上に, 実装しようとすると様々な問題を生むことが分かった. そこで, もっとシンプルに1台ずつの追加・削除に限定してみたらどうなるか？と考えてみたら, 全く安全であることに気づいた. 任意の変更も, 1台ずつの変更の積み重ねとして表現することにする方が良いという結論に至った.
説明
When adding a single server to a cluster or removing a single server from a cluster, any ma- jority of the old cluster overlaps with any majority of the new cluster; see Figure 4.3. This overlap prevents the cluster from splitting into two independent majorities; in terms of the safety argument of Section 3.6.3, it guarantees the existence of “the voter”. Thus, when adding or removing just a single server, it is safe to switch directly to the new configuration. Raft exploits this property to change cluster membership safely using little additional mechanism.
- 1つのサーバを追加・削除する場合には, C_oldとC_newのそれぞれ任意のmajorityは必ずoverlapする; 上の実際の4パターンの実例では正しい. スケールを2k上げたとしても結局同じことなので正しい
- このオーバーラップが1つのリーダーしか選出されないことを保証する; どちらかのクラスタがmajorityを得ようとする時には必ずその1台のvoteを得なければいけない. その1台は1つのTermに複数のvoteをしないからリーダーは1つのTermに1つしか選出されない
まとめ
Joint Consensusはやめよう. 1台ずつの追加・削除に分解しよう.