本节：raft选举机制、log处理
容错系统的一般模式
- MR可重复计算，但依赖于单点master的调度
- GFS复制数据，但依赖于单点master挑选primary
- VM-FT重复服务，但一来与test-and-set服务挑选primary
这些应用的关键的服务，依赖单点的实体。 好处是，单点实体的决策避免脑裂。
如何防止脑裂，脑裂的危害？
回顾我们的test-and-set服务： client请求设置state=1，然后服务返回设置前的值， 这样只有一个client请求会得到”0”的返回
[C1, C2, S1, S2]
设想C1可以访问S1，但不能访问S2，C1只能由S1处理吗？
- 如果S2真的挂了，C1的请求必然不用S2处理， 一个挂了的机器影响服务，不是容错系统应该发生的。
- 如果只是C1、S2间只是网络不通， S2只是处理不了C1的请求，但能处理C2的。
所以我们面临的选择：
- 即使容错系统中，难以容错
- 允许错误操作，发生脑裂的可能
问题：计算机不能区分“服务器奔溃”和“网络断开”
他们的现象是一样的：网络无响应
一个坏的情况是：网络分区（network partition）： C1和S1能连，C2和S2能连， 但C1+S1、C2+S2间不能连。
这个问题在很长一段时间，看起来都不好解决。
- 好像要求外部接入（比如人），根据情况切换。
- 单点的完全可靠的服务（test-and-set）
- 完全可靠的网络（那么无响应就一定是服务器挂了）
但这有单点故障的问题，怎样更好呢？
处理分区，最明智的方法：多数投票（majority vote）
要求服务器个数是奇数，比如3。 取得大多数票，才能做后续事情 - 2/3。
为什么多数投票可以避免脑裂？ 最多存在一个分区，存在多数据的情况， 打破了我们上述例子的对称性
注意：大多数的范围是所有服务器，不管有没有挂
一般化，2f+1的机器，可以容忍f个机器的失败， 因为剩余的f+1个机器，可以满足2f+1的大多数。 但超过f台机器失败时，就不行了。
也称为“quorum”系统
多个大多数（majorities）的一个关键熟悉是：两个动作必有相交
比如：Raft的leader选举，多个leader的大多数意味着必然，选票有交集， 而且这个交集能反应出之前的投票信息
两分区容错（partition-tolerant）的复制模式大概1990发明
Paxos、View-Stamp。过去的15年里，现实世界很多都用了这些技术，Raft论文是对现代技术的好的导论
Raft概述
带Raft的状态机复制 [diagram: clients, 3 replicas, k/v layer + state, raft layer + logs]
client指令时序图
[C, L, F1, F2]
- client发Put/Get指令到leader的k/v层（应用层）
- leader把指令加入log
- leader发生AppendEntries给followers
- followers把指令加入log
- leader等待大多数完成（大多数也包括自己）
- 如果大多数都加入log，那么entry就”committed” committed意味着即使发生故障，也不会丢。 大多数 -> 下一个leader的选票请求将看到这条log
- leader执行指令，回复client
- leader在一下次AppendEntries请求，顺便带上commit信息
- followers收到后执行指令
为什么用logs？
服务维护状态机的状态，比如k/v数据库，不够用吗？
- log维护了指令的顺序 使得单台副本执行指令顺序的一致性 帮助leader定位followers的日志
- log存储了提前交的指令
- log存储了指令，以便leader可以重发给followers
- log是持久化的，重启后可以replay
每个备份间的log都是一致性的？
不是：一些有延迟； 不是：我们会看到零时出现不一致的情况
好消息是： 最终会收敛到一致的，提交机制确保服务执行稳定的entries
Lab2 Raft接口
rf.Start(command) (index, term, isleader) client通过RPC，Put/Get服务，然后leader调的Start接口，开始raft的共识
- 加到leader的log
- leader发AppendEntries RPCs
- Start等待RPCs返回
- k/v层的Put/Get，必须等待来自applyCh的提交信息
如果在提交前，server失去了leader角色，共识可能失败，那么指令丢失，需要client重发
- isLeader：false当该server不是leader时，那client换个server试一下
- term：currentTerm，帮助调用者检查leader是否有重新选举
- index：log entries的，可以检查指令是否committed
ApplyMsg, with Index and Command
- 当committed时，每个节点要发ApplyMsg给applyCh
- 每个节点本地服务执行：更新本地复制状态
- leader响应client的RPC请求
Raft设计的两大块：
- 选举新leader
- 即使失败，也确保log能一致
为什么用leader？
确保所有复制在相同的顺序下，执行相同指令
leader选举的序号
new leader -> new term。
每轮最多只有一个leader，或者没有
序号帮助我们选最新的leader
选举时机？
“election timeout”
增加currentTerm，试图收集选票。
note：可能导致无用的选举，所以慢，但安全。另外，旧的leader依然认为自己是leader
如何确保每轮最多一个leader？
leader必须从大多数拿到”yes”的选票，而每个server只有一票。
- 如果是candidate，投的自己
- 不是candidate，投给先请求自己的
在一个term中，最多只有一个server能那到大多数选票
- 即使网络分区，最多只有一个leader
- 即使一些server挂了， 选举也可能成功
一个server怎么知道新leader？
- 新leader能拿到大多数选票
- 另外一些通过AppendEntries心跳发送新的term
- 心跳也抑制了新的选举
选举不成功的两个原因
- 大多数服务挂了
- candidates互相瓜分选票，都没拿到大多数
选举不成功会发生什么？
新一轮的超时，触发新一轮的选举（new term）。 更高term的candidate那到先机，而老tem则退出选举
Raft怎样避免瓜分选票？
每个server都有随机的”election timeout”
随机的性质打破了server间的对称性。 随机延迟最小的最有利，在其他server发生timeout前，最有足够时间，选举成功， 而其他的server看到新leader的AppendEntries心跳，就不会变成candidate。
在网络协议里，随机延迟有着普遍的应用
怎样选取election timeout？
- 至少大于心跳间隔（还要考虑网络丢包）：防止无用的选举发生
- 超时的随机的部分足够大，第一个candidate赶在其他节点超时前选举成功
- 足够短，失败后能快速恢复，避免长时间服务停止
- 足够短，在tester容忍内，可以重试多次。tester要求5s内完成选举
要是老leader不知道新leader？
也许老leader看不到选举信息； 也许老leader处于小少数的网络分区；
新的leader意味着在增加后的currentTerm中，取得了大多数server的投票， 所以老leader得不到大多数AppendEntries的成功， 所以老leader不会提交和执行任何自己收到的log entries。 因此并不会发生脑裂。 但是，有小少数的可能会接受老leader的AppendEntries，所以log在老term中会产生分歧。