Chosen 即多数派通过提案。
假设有 n 个节点,多数派定义为超过半数的节点。
两个多数派的节点数之和:
根据鸽巢原理,节点之和超过节点总数,必然有元素被重复计数,即交集非空。
即任意两个多数派间必有交集。
即任何多数派通过的决策一定会被下一轮任意多数派中至少一个节点继承。
即 Chosen 的值一定会被看见、被继承、保持不变。
PLog 是一串严格有序的、Chosen 的值的队列。队列中存储的值是 Command。
所有状态机按照一致的顺序、执行一致的 Command,所以最终会达到一致的状态。
PLog 是队列,所以如果所有状态机都已经提交了某个 Chosen 的值,那么这个值实际上是可以在队列中删掉的。PaxosStore 内部实际上是会这样处理的。
想明白了就会知道,状态机和 PLog 是可以拆开的,它们不一定要强耦合。
Paxos 算法只解决一个问题:如何确定一个值。
现实中的状态机要的不是一个值,而是无尽的共识的流,所以引入 Entry,可以不断的、有序的达成共识。
现实中的数据量大、并发高,一个状态机撑不住,所以引入 Entity,对数据进行确定性的拆分。
现实中的磁盘空间是有限的,所以 PLog 要定期清理,并不能始终保证状态机可以根据全量 PLog 进行回放,所以还需要引入状态机自己的恢复逻辑。
无论上层多复杂,整个大厦的根基还是没有变,仍然是那个简单的、可靠的 Paxos 共识算法。