raft算法学习备忘

一致性共识算法

参考:分布式一致性算法应用场景，写了为什么需要共识算法，以及相比于mysql这些主从同步方式的区别。

raft算法简介

一种分布式一致性共识算法的实现方式，机制相比于其它例如paxos来说无论从可读性还是实现机制上要简单很多，并且可以证明其正确性。raft论文只提出想法与证明，具体实现参考官网下面的Where can I get Raft?章节，包含了各种语言的实现。golang最出名的raft算法实现就是etcd团队开源的。
raft算法将集群划分为一主多从，由主节点接收写操作，所以包含了集群自动选主，如果暂时没有选出主节点，集群是不可用状态，等待选出主节点（一般几百ms内就可以选出主节点）。
主节点负责写操作，并将写操作广播给集群来让半数以上节点保存写操作日志，一旦半数同意，就可以

raft算法核心机制

每个节点拥有一个任期term属性

任期term是个数字，可以认为是王朝代号，每次发起选举自增，follower追随者使用leader主节点的任期
在这里插入图片描述

自动选主-保证有主节点对外提供服务

每个节点初始都是follower追随者状态，开启一个选举超时定时器（一般大于给集群广播消息消耗时间，例如内网100ms-300ms），定时器到了还没收到leader心跳消息，就认为leader死了，自己变成candidate发起选举
candidate给集群广播要票消息，带上自己当前任期和最新日志索引
follower收到要票消息，只要对方任期比自己大且最新日志索引index都和自己一样或者新（raft叫isUpToDate逻辑），并且先来后到没给别人投过票，就直接投票给对方，candidate收集到半数以上投票就变为leader，或者收集到半数以上拒绝或者超时（例如100-300ms）还没统计完投票就变为follower继续开启走心跳监测
leader定时给集群发送心跳广播维持自己的统治

日志同步

每个提议开始都由leader发起，leader变为日志条目提交，所以每个日志有个自增索引号，与leader所处任期term。
follower需要与主节点leader保持日志条目统一，raft强制让follower纠正自己的日志来保持和leader一致，具体做法为：

leader维持了每个follower的日志索引进度，初始等于leader自己的进度，用心跳消息带上维持的follower进度来探测对方进度，对方只要响应不一致，就递减这个进度并带上follower的进度与leader自己的进度之间的日志条目发送给对方继续探测，直到和对方一致。leader会将半数节点都达到的索引处及之前的日志认为已提交成功
follower收到心跳消息，比对对方记录的进度的日志索引和任期是否和自己当前记录的一致，一致就将日志条目追加到自己记录上，否则拒绝leader同步让leader再递减索引来探测

leader发起提议（写操作）

提议由leader处理，leader会将提议追加到提议日志目录中，所以每个提议日志条目都有自增索引号，任期term+索引index可以确定一个条目，具体操作：

leader收到写操作提议，将提议打包成日志条目追加到自己的条目进度里，走上面日志同步 流程来保持日志进度一致

raft算法额外机制

核心机制便于理解raft如何做到共识，而额外机制保证raft算法达到一致性

leader必须提交一笔空写操作

在这里插入图片描述
如果没有这个机制，会像上图所示：

(a)时期：如果S1选为leader，向集群复制日志2
(b)时期：S1崩溃，此时S5选为leader，准备给集群复制日志3
(c)时期：S5还没来得及复制日志3，也崩溃了，S1重新选为leader，重新发起复制日志2并且接收了日志4，在同步给节点S3后又崩溃了
(d)时期：S5重新选为leader会要求整个集群应用自己的日志3，但明明©时期S1已经复制了半数日志给集群了，日志2被错误覆盖
(e)时期：如果S1当选能立即提交一个日志4的空操作给半数集群，那么S5是无法获得投票再次当选的，因为任期数小于半数集群认同的任期
这种机制防止了一些崩溃或者网络分区的情况下，旧leader通过旧任期覆盖一些新数据引起线性一致性问题

follower每次随机一个检查心跳超时时间

节点初始都是follower状态，如果一起启动，用一个选举超时时间，会一起变为candidate参与竞选，大家瓜分选票导致竞选失败再次超时重来无限循环。
因此raft规定follower每次检查心跳超时的时间随机等待，防止同时产生竞选。

遵循：broadcastTime ≪ electionTimeout ≪ MTBF，即广播时间小于竞选超时时间小于节点系统不可用时间

已提交日志不能更改

raft算法将日志条目分为已提交段和未提交的临时段，上面的leader纠正follower日志也只能是未提交段

优化raft集群

通过以上说明只是完成了一个固定集群一致性共识，不是真实商用状态，存在诸多问题需要解决。

配置变更（增删节点）

真实环境动态改变节点不可避免，可以将配置变更也作为日志提交，并且新增的节点不参与集群选举

日志条目压缩

随着集群运行很久，日志条目越来越多，假如是个kv数据库，其实保存set key的最后一条写操作即可，因此每个节点可以单独生成已提交日志的快照后删除已提交条目，后续的日志同步涉及快照内的索引就直接以快照同步

处理读请求

将raft集群看成一个整体，写请求打到follower节点会被路由到leader节点处理，那么读请求呢？
假设客户端提交了一笔写操作马上来读这个操作的值，读到的值和写入的一样，这叫线性一致性。raft集群也要满足线性一致性。如果读请求由follower节点处理，可能follower还没接受到leader同步，数据落后；如果由leader处理，leader是保存当前最新的数据，但是读写都在leader又性能不好。
raft论文讨论了往leader节点读，但是有可能该leader是网络分区下的少数派，所以读之前leader要和集群广播确定和集群通信仍有效。
还有其它方法例如将读请求也作为一次提议，这样半数集群通过就可以直接返回数据。例如租约的形式让follower在选举超时内确认没发起竞选期间有处理读的权限，但是依赖时间比对逻辑，时钟可能发生回拨等存在不安全因素。