mit 6/824 lec 6 raft1

6.1 脑裂 (split brain)

• 容错系统，存在多个副本，但是需要单个节点来决定在多个副本中，谁是主(Primary)
• 这种情况下会产生脑裂
• 脑裂的解决方式:
  • 构建不可能出现故障的网络。比如连接了CPU和内存的线路就是不可能出现故障的网络，要花很多钱
  • 人工解决。在客户端需要等待两个服务器响应的情况下，如果只有一个服务器响应，那么不要执行操作，要运维去修复。

6.2 过半票决 (Majority Vote)

• 网络分区是指，网络出现故障，将网络分割为两半，网络两边独立运行，不能够访问对方，那么形成了两个网络分区
• 过半票决，是raft论文的基本概念，以及实现自动恢复，同时避免脑裂的多副本系统。，一般适合于服务器数量是奇数的网络，要点在于在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作，逻辑是
• 通用的方程是如果系统有2 * F + 1个服务器，那么系统可以最多接收F个服务器故障，仍然可以正常工作
• 由于每次操作需要过半的服务器来批准，那么每一个操作对应的过半服务器，必然至少包含一个服务器存在于上一个操作的过半服务器中

6.3 Raft初探

• Raft会以库的形式呈现在服务中。如果你有一个基于Raft的多副本服务，那么每个副本将会由两部分组成：应用程序和Raft库。应用程序负责接收RPC或者其他客户端请求，不同节点的Raft库之间相互合作，来维护多副本之间的操作同步。
• Raft在应用程序底层，提供容错。Raft本身会保持状态，也就是会记录状态日志
• 对于一个三个节点的raft kv服务器集群而言，一个请求给服务器集群，
  • Leader节点的应用程序会将来自客户端的请求向下送给Raft层，
  • 并且将这个操作提交到多副本的Raft日志
  • 当Leader的节点直到过半的节点有这个操作的拷贝之后，那么Leader的Raft层会通知应用程序，也就是Key-Value数据库，来说明：刚刚你提交给我的操作，已经提交给过半副本了，现在可以真正执行这个用户请求了
  • 在Leader节点被提交后，每个副本节点的Raft层都会将相同的操作提交到本地应用程序层

6.4 Log同步时序

• 从时序的角度看Raft Log同步，
  • Leader的Raft层会发送一个添加日志(AppendEntires)的RPC到其他两个副本,
  • 之后Leader会等到其他副本响应，直到过半(包括Leader节点自己)的节点响应返回
  • Leader在收到过半服务器的正确响应之后，Leader会执行客户端请求，并将结果返回给客户端服务器3也会将响应返回给Leader，这个响应有用但不需要等待
  • 对于Leader之外的服务器，在Leader提交之后，那么Leader会去将这个消息通知给其他副本，这个committed消息会被夹带在下一个AppendEntries中
  • Leader需要给副本发送心跳？对于客户端的请求稀疏的情况需要Leader发送心跳包，心跳包用来告诉follower当前Leader还活着,当follower的定时器过了一段时间没有收到Leader的心跳包，那么之后就会发生新Leader的选举

6.5 日志

• Log的作用：
  • Log是Leader来对操作排序的一种手段。即如果有十个客户端同时向Leader发出请求，那么Leader必须确认一个顺序，其他副本都会遵从同样的顺序，Log是一些按照数字编号的槽位(类似数组)
  • Log对于非Leader的副本而言，一些还未执行的操作，会放在其中，直到Leader发送了新的commit号，这些操作可能会被丢弃
  • 对于发送给副本的操作，可能需要重新传送，那么Log中记录了可能需要重传的操作。即使是已经commit的请求。
  • Log对于故障节点的恢复，一个Raft节点故障重启之后，Log保留在磁盘中，那么Log会被Raft节点用来从头执行其中的操作进而重建故障前的状态，实现持久化
• 确认操作？确认是指Leader发来的committed消息，那么确认与累计可以很快必要时，需要follower去发送消息给Leader进行流量控制
• 对于一个服务器宕机，重启之后，读取disk中的log，但不会执行log，等待Leader发送的committed消息，才去执行。对于Leader的宕机，会发生新Leader的选举。

6.6 应用层接口

• 对于应用程序层(这里是KV数据库)与Raft层，它们之间存在两个接口:
  • 一个KV层用来转发客户端请求的接口。客户端发来请求给KV层，KV会将这个请求转发给Raft层，放在Log的某处。这个接口是个函数调用Start函数，它的参数是接收客户端请求，KV层说:我接到了这个请求，请把它存在Log中，并在committed之后告诉我。应该是转发完了请求，Start函数就返回？(是不是发完给raft就返回呢)，并将一些信息返回给KV数据库，比如这个请求在Log中的位置(index),当前的任期号等。这个问题可以看出，Start返回之后，需要等到ApplyMsg出现
  • 第二个接口，是Raft层通知KV层。Raft通知的，不一定是最近一次Start函数传入的请求。Raft层将信息通过一个applyCh的channel，Raft通过这个channel发送消息到KV层，并通过之前Start函数的返回值，对应这个ApplyMsg消息，ApplyMsg中包括请求与对应的Log位置
• 如何保证副本的最终一致？猜测是follower的心跳包中包含自己的log位置

6.7 Leader选举

• Paxos中可以没有Leader，就实现一致性的系统，但是还是需要在确认消息的时候，创建一个临时Leader，所以Raft存在Leader，效率会更高。
• 使用任期号(term number)来区分不同的Leader。一个任期只能有0个或者1个Leader。
• 对于每一个节点都存在一个选举定时器(Election Timer)，当一个follower长时间没有收到当前Leader的心跳包，定时器到期，当前节点增加任期号并会发起一个选举，给其他n - 1个节点发送请求投票(RequestVote)的RPC。即使当前Leader没有故障，仍然会出现新的选举。
• 对于由于网络分区出现了，那么旧的Leader在收到客户端请求之后，其发送AppendEntries消息给，由于分区小，那么它永远不会commit这个请求
• Raft没有考虑到网络单项故障的情况？
• 由于一个任期中，每个Raft节点只能发送一个认可选票，
  • 所以保证了一个任期内，不会存在多个候选人同时获得超过半数的选票。
  • 同时，这也保证了即使一些节点故障了，还是可以选出新Leader
• 当一个服务器赢得了选举，会向所有其他服务器发送心跳(AppendEntries)通知其他服务器。这里的要点在于只有Leader可以发送AppendEntries消息，

6.8 选举定时器

• Leader通过合理的速率发送心跳或其他AppendEntries消息，这个AppendEntires消息也会重置每个server的选举定时器，那么就可以阻止其他节点选举。
• 存在一次选举出0个Leader的情况
  • 过半服务器关机或故障，或者是网络故障了。
  • 存在一种所有候选人同时参加竞选，它们分割了选票(Split Vote)。当所有的节点都没有成为Leader，接下来它们的选举定时器会重新记时(也就是说在一个节点选举的时候，也在定时器倒计时吗？)解决方法是通过为选举定时器随机的选择超时时间，对于选举定时器选择的超时时间必须大于Leader发送的心跳间隔，由于丢包问题，最好将下限设置为多个心跳间隔。上限在需要考虑效率时，需要设置好上限，同时需要保证不同节点的时间差足够长，使得其中一个节点开始选举时，能够完成一轮选举。
  • 每一次一个节点重置自己的选举定时器，会重新选择一个随机的超时时间，也就是说candidate

6.9 可能的异常情况

对于旧的Leader在故障后，为了恢复系统一致性，新Leader如何处理不同副本的可能不一致的Log？

• 因为时间线上错误的出现，下面是一个3个服务器集群可能的Log快照但是即使对于槽位10，11，也不能保证Leader执行成功了，但是必须假设这些槽位10，11的请求被commit了？可是没有办法保证这些请求被执行了，这里是需要保证恢复后从磁盘读Log时，