本文根据字节青训课程中一节针对《分布式数据一致性》的课程内容的进行总结与整理，希望可以帮助大家加深对以Raft为代表的分布式一致性协议的理解。
Raft）后，逐步扩展为一个分布式的，满足一致性读写需求的读写服务的过程。
Raft协议的种种概念：选主、一致性、共识、安全等，通篇阅读之后，将帮助你深刻理解什么是分布式一致性协议。
一、 单机KV数据读写服务
DB Engine这里可以简单看成对数据的状态进行存储（比如B+树型的组织形式），负责存储KV的内容，并假设这个KV服务将提供如下接口：
Get(key —> value
Put([key, value]
容错：单个数据存储节点，不具备容错能力。
高可用：服务部署在单节点上，节点宕机将无法提供服务。
思考此时KV服务的正确性：
单进程，所有操作顺序执行，可以保证已经存储的数据是正确的
数据规模不断增加，我们需要扩大这个KV服务的规模，将其构建成一个分布式的系统
二、一致性与共识算法
2.1 从复制开始
我们这里只考虑主副本负责接收数据，而从副本只负责同步接收主副本数据的模式，如果主从都开放数据接收能力，将要考虑更多高可用和数据一致性的问题。
2.2 如何复制
主副本定期拷贝全量数据到从副本（代价太高）
主副本拷贝操作日志到从副本：如果你了解MySQL的主从同步，你就会想起它也是通过从副本监听主副本当中的操作日志变化，进行集群数据同步的，因此这种方式也是更主流的选择。
2.3 具体的写流程
所有的写入都是持久化的，保存在磁盘上
应用包装成状态机（也就是DB Engine部分），只接收作为
从副本之后，就从主副本机器返回，也可以等完成落盘之后，再返回）
2.4 具体的读流程
方案一：直接读状态机（
这里指的是DB），要求上一步写操作进入状态机后再返回client（数据已落盘）
方案二：写操作复制完成后直接返回，读操作等待所有进入状态机
如果不遵循上述两种方案：可能存在刚刚写入的值读不到的情况（在Log中）
2.5 什么是一致性
KV服务，要像操作一台机器一样，对用户来说在写入成功后，就应该能读到最近写入的值，而不关心具体底层是如何分布式实现。
最终一致性：读取可能暂时读不到但是总会读到
线性一致性：最严格，线性时间执行（写完KV确保就能读到），是最理想中的状态
2.6 复制协议-当失效发生
上述用到的添加了一个从副本节点的方式，我们暂且将其称为山寨版分布式一致性协议——复制协议（因为它依赖于主从副本间的复制操作）
复制协议为基础的KV服务的运行情况如何呢：
容错能力：没有容错能力，因为主副本停了，KV服务就停了
高可用：或许有，取决于我们发现
主副本宕机后多快将
从副本切换为
主副本（手动切换）
正确性：正确，因为操作只从一台机器发起，可以控制所有操作返回前都已经复制到另一台机器了
如何保证
主副本是真的失效了，切换的过程中如果主副本又开始接收请求，则会出现
Log覆盖写的情况
如果增加到3个乃至更多的节点，每次PUT数据的请求都等待其他节点操作落盘性能较差
能否允许少数节点挂了的情况下，仍然可以保持服务能工作（具备容错能力）
2.7 共识算法
什么是共识：一个值一旦确定，所有人都认同
比如可以故意返回旧的值（共识算法只是一个彼此的约定，只要数据存储与获取符合需求，达成共识即可）
应用层面不同的一致性，都可以用共识算法来实现
一般讨论共识协议时提到的一致性，都指线性一致性
因为
弱一致性往往可以使用相对简单的
复制算法实现
三、一致性协议案例：Raft
3.1 Ratf概述
易于理解作为算法设计的目标
使用了RSM、Log、RPC的概念
直接使用RPC对算法进行了描述
Strong Leader-based（所有操作都是Leader发起的）
使用了随机的方法减少约束（比如选主时Follower谁先发现Leader失联就发起选主）
3.2 复制状态机（RSM）
Raft中所有的共识机制（consensus）都是直接使用Log作为载体：简单说就是client将Log提供给Raft（也就是上图的Consensus Module），Raft确定这个Log已经Commit之后（写入Log文件），将Log提供给用户的状态机
注意此时状态机是一个内存中的存储概念，当然后续每个节点数据还涉及到落盘持久化，这是具体应用层面的问题了，这里讨论的更多是Raft协议的原理概念，使用状态机对此进行抽象
一旦Raft更新Commited Index，意味着这个Index前所有的Log都可以提交给状态机了
Commited Index是不持久化的，状态机也是volatile的（断电清空），重启后从第一条Log开始恢复状态机，Raft协议工作过程中每个节点的Commited Index可能是不一致的，但是Ratf可以保证最终所有节点都是一致的
Commited Index（这里先有个概念，用于标识Log中哪些数据可以提交给状态机）
3.3 Raft角色
Leader是所有操作的发起者，会把Log同步给Follower，确定哪个Log已经Commit了
接受Leader的请求，并且在发现Leader消失，则转换为Candidate，向其他Follower申请投票，如果获得票数过半，则晋升为Leader
3.4 Raft日志复制
第一张图s2是当前Leader，紫色的小箭头指向每个节点已经确认commit的Log位置
第二张图s2又append了一条新的Log，用K标识
第三张图表示，s2将自己收到的K以及自己的Commited Index发送给所有Follower节点。Follower都同步Leader的Log以及Commited Index，并且Follower的状态机检测到自己的Commited Index又向前推进了，说明有新的Log值达成了共识，就会把Commited Index没读取的Log值应用给状态机
第四张图，当Follower完成步骤三的操作之后，会告诉Leader自己已经拿到这个Log值了，Leader在收到多数派的确认消息后，就可以确定这个K已经永远的持久化，也就是已经Commit了，因此将Commited Index向后推一位
这里有一个细节就是，虽然Raft协议使节点间的数据最终达成了一致，但是节点Log数据落盘时间是有先后的（因为Commited Index在各节点之间存在差异，所以Log与状态机是有时差的）
3.5 Raft从节点失效
图一假设s3失效了很久，Log有很多数据没有同步
图二表示此时的Leader是s2，将自己Log中的K和自己的Commited Index复制给s1
图三中s2的K完成了commit（流程参考Raft日志复制），因为s1、s2共两个节点已经形成了多数派（此时已经有容错能力了）
图四中，s3尝试重新同步数据，在Raft协议中，s3会向s2逆向迭代的去获取Log数据（K、QK、TQK、XTQK），直到与s3当前Log相对齐则完成数据同步（当然Raft具体实现中应用对此过程进行了优化）
3.6 Raft Term
每个Leader服务于一个term：一旦发现更高的term，那么表示我已经不是Leader了
每个term至多只有一个leader：选出新的Leader，会使得term增加
每个节点存储当前的term
每个节点term从一开始，只增不减
所有的rpc的request response 都携带term
只commit本term内的log
3.7 Raft主节点失效
Candidate自增自己的term，同时使用RequestVote PRCs 向剩余节点请求投票
raft在检查是否可以投票时，会检查log是否outdated，至少不比本身旧才会投票给对应的Candidate
Leader定期发送AppendEntries RPCs 给其余所有的节点
3.8 Raft Leader failure
接下来模拟一下主节点失效后的流程，并且注意此时图一当中，s1的Log内容比较特殊，为XW，这个场景是可以实现的，比如一开始有s1、s2、s3，其中s1是Leader，首先将X同步给了s2和s3，并且接受到了新的W，但是突然s1节点卡死了，s2和s3重新开始选举Leader为s2，最终s2和s3的Log变成了XTQ（这只是一种情况，一切皆有可能），然后s1又恢复了。
从图二开始，s3发现s2挂了，没有Leader，则将自己的term+1变为3，并且向s1请求Vote
图三中，s1发现RequestVote是来自term等于3的，大于自己的term，因此将自己的term也更新为3，同时答应给s3投票，达成多数派条件，s3成为新的Leader
图四，s3开始同步自己的Log给s1，但是发现s1中的Log起初为XW，而s3中为XTQY，因此还是会按照从后往前迭代的方式将数据同步给s1（Y、QY、TQY、XTQY），最后s1虽然与同步状态发生了冲突，但是由于Raft是的，会完全按照Leader的内容覆盖自己的Log
3.9 Raft 安全性 - 同 Term
目标：对于所有已经commited的<term, index>位置上至多只有一条log
我们可以证明一条更严格的声明：在任何<term, index>位置上，至多只有一条log
对于Term内的安全性
3.10 Raft 安全性 - 跨 Term
目标：如果一个log被标记commited，那这个log一定会在未来所有的leader中出现
Raft选举时会检查Log是否outdated，只有最新的才能当选Leader
选举需要多数派投票，而commited log也已经在多数派当中（必有overlap）
新Leader一定持有commited log，且Leader永远不会overwrite log
对于跨Term的安全性
四、回到KV
4.1 重新打造KV服务
结合Raft算法，更新一下我们的KV
写log被commit了，返回客户端成功
读操作也写入一条log（因为读的数据可能还没从Log写入状态机，无法读取状态机数据），状态机apply log后返回client
增加Log量
写log被commit了，返回客户端成功
读操作先等待所有commited log apply，再读取状态机
优化写时延
方案三：
写log被状态机apply，返回给client
读操作直接读状态机
优化读时延
服务无法水平扩展
如果操作跨Raft组（对key进行分组，每一个Raft负责读写一个range的key）
方案一：
4.2 回到共识算法
论文中就给出的方案，当过多的Log产生后，启动snapshot，替换掉Log
如果对于持久化的状态机，如何快速的产生Snapshot（略）
多组Raft的应用中，Log如何合流（略）
论文中就给出的joint-consensus以及单一节点变更两种方案（很复杂，略）
Raft：关于log
4.3 共识算法的未来
研究主要关注在Paxos上
On the Parallels between Paxos and Raft, and how to Port Optimizations[1]
Paxos vs Raft: Have we reached consensus on distributed consensus?[2]
Raft Paxos相互移植