【Day 8】节点间的共识（Consensus）

准备出游，6.2 的 Raft 之後再补

5.3 提到 state machine replication（SMR）需要 total order broadcast。
而前面也提到，达到 total order broadcast 的其中一种方法，
可以透过 leader 决定讯息顺序，并使用 FIFO broadcast 给其他节点。
问题在於 leader 挂掉时，要怎麽办？

• manual failover：leader 挂掉的话，把负责的人抠爆，叫他重启或是重选一个 leader。

如果转换 leader 的工作靠手动，
除了员工不爽，还可能会导致服务不能用一阵子，
那有没有自动的方法呢？
就是接下来介绍的 Consensus 共识演算法。

6.1 Intro to consensus

分散式系统中的节点要达到共识（Consensus），也就是都同意某个值。
一个或多个节点会 提议（propose） 一个数值，
然後透过共识演算法决定要采用哪个，
最後每个节点都达到一致，
而且决定好之後就不会改变心意～

Consensus 与 total order broadcast

consensus 跟 total order broadcast 可以互相转换。

• total order broadcast -> consensus: 想要提议数值的节点就广播，而 total order 决定 deliver 的第一个讯息当作大家同意的值。
• consensus -> total: 使用不同轮的 consensus 决定第一、二、三个要 deliver 的数值，想要广播的节点就在这几轮 consensus 中提议新数值，共识演算法会确保每个节点都同意这个 deliver 的讯息序列。（讲得有点复杂ＱＱ 就是用 consensus 来做 total order，如果每次大家都同意一个数值，那每个节点 deliver 讯息的顺序也就一样）

目前有名的共识演算法:
Paxos、Multi-paxos
Raft

Consensus system models

共识演算法基於 partially sync, crash recovery system model

为什麽不用 async model?

• FLP result
  这个理论证明，如果假设 async model，没有 deterministic 的共识演算法能保证会停下来。

• Paxos、Raft 等演算法只有在 timeout/failure detector 上用到 clock（确保 progress），在 correctness(safety) 上并不依赖时间。

Leader election

共识演算法的核心基本上就是发现旧的 leader 挂掉时，
能自动选上新的 leader。
而且要避免 split-brain：同时间有不只一个 leader，各说各话。

leader election 过程会根据不同演算法有所差异，
基本上是当节点有一阵子没收到 leader 的讯息，
会发起选举，成为 candidate，并问其他节点是否投票，
当有足够 quorum 数量的节点投票，他就成为新的 leader。

Raft 演算法中，一个 term 只会有一个 leader，
但不同 term 可以有不同 leader，
之後会说明。

能保证同时间只有一个 leader？

我们需要避免 split-brain，
但基於一开始的假设：partially syncronus，
会因为 timeout 就判定旧的 leader 挂了、选出新 leader。
但或许只是网路真的很烂而已，
旧 leader 活着、甚至不知道自己被夺权了。

虽然不可能保证同时间有好几个 leader，
但可以保证 每个 term 只有一个 leader。
Raft 中的 term 代表这是第几次选举 的 leader，
就是为了能够做出区别。

每次决定下一个讯息的顺序，leader 都要先问

这是一个很重视团队意见的 leader XD
每次 leader 要决定下一个讯息，
就要获得 quorum ，也就是大部分节点要同意。
以避免实际上有好几个 leader（例如因为暂时的网路断掉，已经有较大 term 的 leader 被选出）造成了节点间讯息顺序不一致。

1. leader 询问大家：can i deliver message m in term t?
2. 因为其他 follower 还没有认识别的拥有更大 term 的 leader，就说好哇好哇听你的，leader 获得 quorum 投票
3. leader 叫大家 deliver m

6.2 Raft

Raft 演算法的部分会在我出去玩回来，也就是下礼拜之後补上