Raft 论文解读：分布式数据库如何协调工作？
文一
Raft 论文解读：分布式数据库如何协调工作？
实践证明，需求才是驱动学习的原因，我们永远不会去学习我们觉得不需要学习的内容，感谢 PikiwiDB 社区的指导，让我产生了学习 Raft 论文的兴趣。
Raft 是为分布式数据库（准确而言，是需要协同工作的一组数据库）所设计的集群构建思路（对 Paxos 论文中的内容进行了简化，用简单而易于理解地方式达到了讨论分布式数据库的目的），理解 Raft 是后续诸多工作的基础，在本篇文章之中，我们将对 Raft 展开详细的讨论，尽力而为地帮助每一个人理解其中的内涵。
Raft 所面向的场景
假定我们有一个数据库服务端软件，它可以接受用户的指令，并产生日志加以记录，如图所示：
（单机数据库下面的一个简化模型）
在这种场景下面，一款数据库所能承载的数据量，与自身部署在的机器紧密相连（就像在一台硬盘容量限制于 10GB 以内的机器上，即使借助了良好的压缩算法, 我们所存储的数据最大容量，依旧不能够同其它部署于具有更宽松限制的机器的数据库软件相匹敌）。
在承认硬件限制的基础之上，数据库自身的设计，往往也会对数据的存储带来一定的限制，如图所示：
(MySQL InnoDB 表的数据存储限制，与单一页面的存储容量下的限制息息相关)
(PostgreSQL 的限制数据，单独数据表的最大容量被限制为32TB)
我们知道，因为数据存储需求本身具有无限性（企业、机构与个人，总是在尝试着将越来越多现实生活中的对象数字化，并将其存储起来），而数据库软件与机器的限制总是客观存在，因此在某个临界节点上面，这种矛盾就会变得非常尖锐，即到了一个必须想办法加以解决的境地。
（除了存储规模的限制外，性能往往也是一件非常值得考虑的事情，我们这里所作的简单实验，可以让你看出，在数据存储规模扩大的情况下，数据库查询的性能等，都会出现下降的情况，且规模越大，下降越明显）
（这里，我们可以摘取《大数据白皮书（2022）》中的内容，可以看到，短短数年间，数据存储的规模就出现了爆发式的增长，而传统的数据库软件，在不加调整的情况下，实在是难以满足这种需求）
业界解决大规模数据存储的基本思路
尽管困难重重，但是，方法总是比困难多，面对越发增长的数据存储需求，业界的工程师们，殚精竭虑，思考出了两种解决的思路（这里，我们继续简化问题，假定我们的机器总是可以满足我们的数据存储需求）：
第一种，将既有庞大的数据表切分开来，即业界已经形成可靠解决方案的“分表”
（这种做法的核心，便是化大为小，将一张庞大的数据表，划分为一组组织方式相同，但是各自存储不同数据的小数据表，并且按照某种规律（即分区键）进行组织，进而使得数据的读写压力，能够得到分散与缓解，并且将表的规模，控制在一个合理的范围之内）
它超出了这篇文章所讨论的范围，因此，我们就此打住，感兴趣的读者可以阅读相关文章，进而建立更为深刻的了解。
而第二种，则是 Rart 论文中所讨论的方案，即在数据库自身的工作方式上面下功夫，自一开始，即将数据库视作为一组协同工作的服务端, 他们协同合作，按照一定的方式将大规模的数据读写任务，分解为面向各个个服务端的小规模数据读写任务，交付各自展开处理，并且按照一定的办法，定期将其同步汇总，进而有效地应对大规模数据存储的场景。
（在这里，我们简化了模型的描述，实际工程中的场景，往往会复杂一些）
就此，我们就已经对分布式数据库的理念已经所应对的场景，建立了基本的了解，接下来，我们将专注于讨论 Raft 所设计的分布式集群构建思路，参考下面的内容。
Raft 方案的要点
理解 Raft 解决方案的最好办法，与分布式数据库的解决思路是一样的，就是将庞大的任务，依据其规律与特点，划分为小模块加以解读，最终再加以整合，参考下面的论述。
Raft 对于数据库角色的划分
角色即代表着不同的工作职责，Raft 自一开始就将数据库集群划分为两类角色，即承担领导责任的头节点（Leader，也可以称呼为领导节点等）与按部就班展开工作的部属节点（Follower，也可称呼为从属节点等）。
根据论文中叙述的内容，领导节点：
- 承担最重责任 所有记录数据变化的读写日志，均由头节点传输给部属节点。所有客户端的读写请求，全部经由头节点加以处理（如果客户端尝试对接部属节点，部属节点会将其请求重定向到头节点）。
- 通过选举产生 分布式环境与单机环境（即单独的数据库承担全部工作任务）的一个重要区别在于，多个数据库服务端在真实工作环境中，在所难免地出现网络延迟，网络中断等出乎意料的情况，而倘若对于这些意外视而不见，势必将集群的工作带入混乱之中。 而选举机制（Leader election），就是由 Raft 所设计的一套故障转移机制的统称，专门用于在集群中头节点发生故障时，重新产生头节点（a new leader must be chosen when an existing leader fails， 一个新的头节点必须在既有的头节点出现故障时被选择出来），进而使得分布式集群的工作，再次变得有条不紊。
- 一个集群不得有多个头节点 一个存在多个头节点的工作集群难免陷入“互不服气”的混乱之中。
- 周期性同部属节点通信 这是一种验证集群整体处于健康状态的举措。同时也是确保自身领导地位的手段。
而部属节点：
- 负责响应来自于领导节点与其它节点的请求
- 除特殊情况外，他们本身并不会主动发出任何请求 特殊情况一般发生于新旧头节点的交接期间，此时部属节点需要做数据头部，因此他们往往会向新的头节点申请有关数据
- 倘若在一定时间内没有接收到任何来自于领导节点的数据包，部属节点可以自主启动领导节点选举，并将自身转变为“候选节点”
而在两类工作角色的基础上，在“选举”期间，因为新的带头节点尚未产生，因此不存在上与下，高与低，头节点与部属节点的关系，所以此时的节点被称为“候选节点”（Candidate），即”正在选举头节点的节点“（注意：因为分布式环境下面的网络延迟，节点的角色转换，协调存在一定时间差），而选举的策略与方式，我们将在随后的部分展开讨论。
Raft 中的时间观：用递增的逻辑时钟代替真实的时间
用时间序列标识各类操作的先后，可以更好地帮助我们跟踪变化，展开工作（这就像我们总是阅读日期最新的新闻来掌握世界各地发生的变化），而这种时间序列的标识，在 Raft 中，是采取逻辑数字方式而非真实日期时间数字进行（因为不同的机器，可能存在时间延迟，进而引发误会）。
而由此就有了两个概念：
- term（期限，任期） --- 代表某一段头节点领导其它部属节点展开工作的时间节点
- log index（日志索引） --- 代表某个读写操作所发生的日志序列号
同时 Raft 保证：
- 如果服务端已经向日志加入了用某个日志索引标识的数据读写操作，其它服务端将不再使用该索引标识其它的数据读写操作
- 倘若两份日志包含着相同的索引标识与任期，那么他们所包含的内容在给定索引之前将保持一致
Raft 中数据库服务端角色的转换
在建立了对于数据库三类角色的了解之后，对于三类角色的相互转换，就成为了另外一个我们所需要了解的内容，而在这之前，我们需要对心跳检测的有关内容，做一个了解，参考下面的内容：
心跳检测（Heartbeat）
这是一种检测客户端与服务端之间正常通信的手段，方式在于服务端将会周期性向客户端发送一些没实际有意义的数据包，根据响应的内容判断双方之间的通信是否保持正常。
图片中便是对于这种场景的描述，因为在 Raft 中，通信往往依靠于日志的传递，而日志的序号则是逐渐递增，因此我们对于周期性发送的数据包作了标识，用于更好地促进读者的理解。
值得注意的事情在于，这里我们假定数据包均是按序传输的，但在实际应用中，特别是使用了 UDP 协议的场景下面，因为在协议上没有确保按序递达的机制，因此最终送交的结果，乱序可能性大，这就需要我们采取一定办法加以把握。
可以看出，在整体流程的开始，所有的数据库都被划分成为部属节点（Follower），并在从发现超时（election timeout，即在一定时间之中发现自身没有接收到任何来自于头节点的内容之后）启动头节点的选举，并将自身角色转变为候选节点（Candidate）。
在选举流程完成以后，倘若发现自身赢得了集群中绝大多数节点的“选票”，即将自身转变为头节点（Leader），并开始面向集群中全体成员展开心跳检测（确保集群状态健康，确保自身领导地位）。
反之如果在选举途中，接收到了来自于当前领导节点的信息，或发现新的领导节点已经产生，则中止自身选举进程，或是更新自身对于领导节点信息的记录，重新将自身定位成“部属节点”。
同时我们可以注意到，在选举途中如果出现了超时的情况，或是发现并没有绝对多数的领导节点产生，则启动新一轮选举，维持自身的候选节点定位不变。
每一轮新的选举，都将会对 term 展开更新。
更新数据的方法
Raft 方案规划下的数据库服务端，所需要关心的事情唯在于同其定期同其它节点通信以明确自身定位，以及不断响应数据包展开数据读写工作。
而对于更新数据这件事情而言，在这里，我们需要对单机数据库的一些知识做一个简单的回顾，他们是理解分布式数据库的基础。
与分布式数据库集群一样，单机数据库在诸多场景下同样需要面对来自大量外部用户的连接，而为了节约数据管理的成本（所有学习数据库内核的人都应当意识到，数据库的价值均来自于此），“ACID” 作为事务应当具有的四项特性而被提出（事务代表着会使数据发生变化的查询语句，对应到业务中，即可以联想到用户向购物车中增减商品，在博客上发表文章等）：
- 原子性 --- 事务作为对一条或是数条查询语句的封装体，要么全部执行成功，要么宣告失败，撤销结果（因此我们不可以把事务简单理解为编程语言里面的函数，因为函数即使中途返回，对程序全局变量的修改影响也会持续下来，而事务则会撤销这种修改操作）
- 一致性 --- 事务自身的数据操作，无论是的输入数据还是输出数据，应当同既有的约束与规范保持一致，不得破坏规矩
- 隔离性 --- 事务在操作途中，自身所掌握的，所操作的数据应当尽可能地不受其它事务操作的干扰，换而言之，数据库内的共享数据，应当在秩序总体可控的局面下得到使用
- 持久性 --- 事务的数据操作在执行成功以后，应当保留下来，而不是伴随着事务的结束，而随之消失
并通过一定的机制加以保障，在单机数据库情况下，一般是通过“锁”机制与“日志”机制进行保障，不同粒度（即不同限制程度）的“锁”，就对应了不同的隔离级别。
而日志机制，PostgreSQL 中对于 wal 日志机制的文档描述部分，可以作为我们的参考与借鉴，摘录其中一部分，用以作为我们的参考：
预先写入式日志机制
预先写入式日志（Write-Ahead Logging， wal）是一种确保数据一致性的方式。更为细节的描述可以在绝大多数有关事务处理的书籍当中找寻得到。简单来说，wal 的核心概念在于，所有对于数据文件的改变（无论是数据表还是索引）必须在这些数据变化被记录到日志之后，才可以生效执行。
也就是说，在描述数据变化的 wal 记录被刷新进入到永久存储之后。如果我们遵循这项生产过程，我们并不需要在每一次事务提交之后，就将数据刷写进入到磁盘之中，因为我们非常清楚，在出现数据库崩溃的情况之后，我们可以依靠日志的方式，恢复数据库的正常工作：所有尚未来得及作用到数据页面的变化，可以通过再次读取 wal 日志记录加以和作用（这被称为前滚恢复，同样被称呼为 REDO）。
wal 日志是顺序写入，因此相较于刷写数据页面，wal 的同步成本会降低很多。对于那些处理许多涉及数据存储不同部分的小事务的服务器而言，这个特点体现得尤其明显。
wal 同时让在线恢复（on-line backup）与将时间点的恢复（point-in-time recovery）变得可能，正如我们在文档后续所描述的一样。依托对于 wal 日志数据的归档，我们可以通过覆盖可用 wal 数据这一策略，支持将数据库数据立即回溯到之前的任何时间点：我们只需要安装一个对于当前数据库的物理备份版本（备份在先前完成），并且回放 wal 日志（实质：就是按照 wal 日志中的记录，再次展开数据读写操作）到我们所期望的时间点。
而到了分布式的局面下，情况又发生了一定的变化，正如我们在协同工作中，不仅仅需要关心我们自身所做的事务，同时也需要关注团队整体的图景一样，分布式数据库集群中的数据库服务端，同样也需要将自身的一部分精力，放在其它的数据库节点上，在 Raft 中，日志机制与锁机制同样是参考了单机场景下面的情况而建设，同时，结合着分布式环境下，网络延迟，服务端角色转换等情况，对其进行了一定的改进，这一点，我们可以通过阅读 Raft 论文比较得出。
首先看到，在 Raft 所设立的框架之下，日志与 PostgreSQL 的 wal 一样，是按序递增写入，由此划分出数据读写顺序的先后，其次，结合分布式的环境，日志由头节点传输给各个部属节点，头节点因为处理着客户端的全部请求（如果客户端连接到了部属节点，则部属节点会把连接重定向到头节点来），所以其数据时刻保持最新。
（Raft 论文中所描述的整体集群的日志的情况，可以看出，所有的节点均维护这一份本地的日志，日志序号逐渐递增，只有数据操作真正落到位的日志记录才可以被视作“已经提交”，这与 PostgreSQL wal 日志机制的设计是相同的，同时，头节点的日志记录永远保持最新，同时因为网络延迟的缘故，部属节点的日志记录总是落后于，或是恰好同头节点保持一致）
接下来，我们将目光放到 Raft 框架所规划的日志传输数据包上，参考 Raft 文章中所给出的图片：
文章中指出，使用 Raft 框架规划的数据日志报文，实际上由了需要依托如下的信息来展开工作：
- 关于 term 的有关信息 term 代表着在某个头节点领导传输下的时间阶段，所有的日志报文应当关注
- 当前头节点所归属的 term，以及先前日志所属的 term（term）
- 先前日志索引号所对应的 term （prevLogTerm）
- 当前头节点的 ID 用于帮助从属节点了解当前头节点的地址等（leaderId）
- 日志关于数据变化的记录数据 里面便是数据管理的有关指令以及所对应的数据，需要具体情况具体分析（entries） 同时注意，在数据包的意义为心跳检测时，数据变化记录应当为空
- 日志 ID 信息
- 先前日志所对应的日志索引号（prevLogIndex）
- 头节点所对应的日志索引（leaderCommit，注意 commit 的内涵在于，该日志所代表的数据管理操作与指令，已经在头节点生效执行）
而具体的操作策略则是：
- 如果数据包的 term 小于目前节点所记录的 term，则拒绝执行该数据包所对应的管理指令与数据
- 如果本地数据日志的 prevLogIndex 所存储与数据包所对应的 prevLogIndex 对应不上，则拒绝该数据包 这条策略在一开始是引发了我的疑惑的，后面经过相关文献的了描述，其其决策的依据在于，因为日志的记录是渐序促成，因此倘若新数据包所对应的先前数据记录索引号同本地存储的记录不上，则说明其历史的脉络是不一样的，也就是说会引发混淆。 举例来说，本地的数据索引号在目前记录为 4, 而数据包提供的信息为 2，那么因为 Raft 日志索引号逐渐递增而言，其数据包所期待操作的数据的日志索引号理当被记录为 3, 但是因为本地已经存在了索引号为 3 的记录，因此一旦接受了该数据包，就会破坏本地数据记录的连贯性，而对集群而言，某个节点的数据连贯被破坏，后续该节点如果被选举成为新的头节点，其遭到破坏的数据记录就会通过日志传输给其它的从属节点，进而导致整个集群的数据一致性都被破坏，这是绝对不可以接受的。
- 如果本地的数据日志与新加入的数据记录存在冲突，即相同的日志索引号（注意此处 prevLogIndex 是与本地日志记录是相同的），对应不同的 term 或者数据，因为部属节点接受头节点的领导，所以本地数据应当按照数据包的要求，更新有关记录
- 如果本地日志数据没有数据包中日志记录所对应的内容，立刻将其追加进入
- 如果数据包所记录的头节点已提交日志所对应的 ID（即头节点目前已经完成记录日志并且落地的日志 ID, leaderCommit）大于本地所记录的 commitIndex（代表部属节点目前已经同步完成的日志），那么在将日志记录内容落地完成后，将本地 commitIndex 更新为 min(头节点日志 leaderCommit, 本数据包中最大的日志索引 ID)
（我们再一次引用这张图片，直观地理解这种举措的内涵）
（这种情况发生于新旧头节点交接期间，此时因为部属节点尚未完全接受新头节点的领导，因此可能出现索引号部匹配的情况，这种时候，Raft 的思路是，因为部属节点接受头节点的领导，所以一切按照头节点的安排来）
选举头节点的办法
Raft 的头节点需要依靠心跳检测机制，即根据一定周期向部属节点发送数据包以彰显自身的权威，而各部属节点则根据是否在一个设定好的期限内接收到了头节点的数据包用以决定是否启动选举机制（这种期限的把控需要联系实际，因为存在丢失某个头节点数据包，但是头节点依旧正常工作的可能性）。
对于尝试启动选举的部属节点而言，它需要对自身所记录的 term 展开更新（递增一个数字），同时将自身转换为候选状态（对于节点身份定位的描述，参考先前的文段），开始向其它的节点（部属节点、头节点乃至于其它的候选节点）发送数据包，要求其投票给自己（我们可以用“扫街拜票”形象地理解这一过程）。
（Raft 文章中给出的一种参考用的数据包格式，内容涵盖：当前候选节点的 term，候选节点的 id， 当前候选节点保持有的最新日志记录索引号，以及日志所对应的最新的 term）
而在接收到这种拜票数据包之后，如果数据包的 term 小于目前节点所记录的 term，则拒绝投票。 如果当前节点尚未投票，或者在本轮选举中已经投给对应的候选节点（存在投票但是对方并不清楚的可能），并且候选节点的日志记录领先于或者至少与本地记录保持同步，则投票给对应节点。 如果已经投票给其它节点，则拒绝投票。
当候选节点已经得到大多数的集群内节点的票以后，则转变为头节点，如果集群内没有出现某个领先一切的节点，则启动新的选举，若是新的头节点已经产生（接收到来自于新的节点的数据包，其中 term 大于本地节点所记录的 term），则更新本地将记录的 term，转变为部属节点。
如何判断自身得到的票数是绝对多数？1/2 比例是一个门槛，同时节点必须对集群中存在多少节点，以及其它节点的地址，有一个了解。
如何使得选举周期不致干扰集群工作过久？设定一个时间期限。
如何确保选举后，数据的同步？向头节点申请数据，之后在本地更新。
补充理解
随机超时定时机制
因为 Raft 框架下，只要是非头节点，都可以独自开启选票，因此，如果存在一些节点，故意不断开启选举（或是网络不稳定，头节点数据包丢失不断），整个集群的工作，将会陷入混乱。
在这种场景下面，我们能做的事情，就是把对于心跳检测的出错容忍度放宽，比如如果头节点传输数据包到部属节点的时间，是 20ms，我们的限制却是 10ms，那么整个集群就会不断出现判断头节点失去领导力，而启动选举的情况（可以回顾前文中对于启动选举的条件，以及心跳机制的论述部分）（这种过于严苛且不合理的设置，某种意义上也是破坏行为），我们就可以将其调高到 45 ms，这样在丢失一个数据包的情况下，还有换回的空间与余地。
同时，如果每一个节点都设置为一样的时间限制，难免出现“龙争虎斗”的局面，比如，在最开始，集群各节点都属于部属节点的情况下，大家都设置了一样的超时时间，因为都没有接收到来自头节点的数据包，全部自行启动选举，因为投票的要求是“谁开启投票，谁自己拜票，同时如果是接收到拜票请求，自身不是候选节点的话，数据新就给票”，而各节点因为集群新建，都没有数据，也就都会把票投到自己身上，这种场景下，集群就很难选举产生头节点，正常工作也就无从谈起。
因此，每一个节点所设立的时间限制，理当是不一样的，这样才可以更好地保障集群的正常工作。
部属节点是否需要维持一份对其它节点的记录数据？
因为部属节点能够转换为头节点，而头节点需要时时刻刻面向整个集群保持存在（即向每一个部属节点发送数据包），因此维持一份这种记录是很有意义的。
（CowSQL 的 Raft 实现中，服务器端将会按照配置文件的要求，创建并记录集群中的节点数据，并以此展开工作）
同时我们可以简单思考集群扩容的算法，比如引入一个新的节点，我们就可以面向集群中的一个既有节点进行通知（因为部属节点会重定向到头节点，因此实际上就是连接头节点），再由头节点面向集群内部属节点进行广播，实现更新。
这里也可以联系到一致性哈希等算法进行拓展阅读，不过注意一致性哈希是每一台服务器端持有部分，而不是 Raft 中的全部数据。
本文的解读讨论到了硬件的限制，但是 Raft 的每一个节点似乎依旧是保持着全部的服务端数据？
是这样，因为 Raft 的重点是故障转移与高可用性，所以对于大规模数据存储下单节点数据超出硬件限制的场景没有多加关注。
分布式数据库不只是这种实现，存在每一个数据节点都保持总体数据的一部分的情况，但是这超出了 Raft 关心的范围，所以我们在这里只是提及，而不过多关注。
写在最后
不同数据库间的异花传粉是很有趣的，我在 PostgreSQL 中学习到的很多知识都促进了我对于 PikiwiDB 的理解，而 PikiwiDB 也加强了我对于 PostgreSQL 的理解。
实际上 PostgreSQL 流复制的很多知识点也是可以用在促进本文的理解上的，感兴趣的读者也可以阅读有关内容，在这里感谢 PostgreSQL 社区的诸多前辈（比如袁国铭老师，魏波老师，吴洋老师，黄宏亮老师，牛世继老师，任娇老师），以及 PikiwiDB 社区的各位老师（于雨老师，宁常远老师）的指点，谢谢你们！