【基于Raft的k-v存储数据库实现】

本文主要是介绍【基于Raft的k-v存储数据库实现】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文链接

基本概念

1. 什么是分布式系统

 建立在网络之上的软件系统。一个分布式系统是一组计算机系统一起工作,在终端用户看来,就像一台计算机在工作一样。
分布式系统的主要特点是：资源共享：分布式系统中的计算机拥有共享的状态，它们同时运行，独立机器的故障不会影响整个系统的正常运行。动态分配：系统可以动态地分配任务，有效地利用分散的物理和逻辑资源。透明性：对用户来说，分布式系统展现为一个整体，用户无需关心背后的复杂性。

2. 什么是Raft协议

分布式选举协议：Raft（一致性算法，共识算法）
Raft协议：是Replication And Fault Tolerant的缩写，即复制和容错协议，是一种强一致性协议，在RAFT中，有三种类型的节点：

Leader: 处理客户端交互和日志复制操作等，一般只有一个Leader节点
Follower: 群众节点，类似于选民，需要同步数据
Candidate: 候选者节点，有可能成为Leader的节点，一般条件是由超过大多数的投票
原文链接：https://blog.csdn.net/zhanglh046/article/details/120682623

3. 什么是序列化和反序列化

序列化就是把对象转换为字节序列的方式，便于传输存储。
反序列化就是从存储的字节流中还原对象的状态，实现对象的恢复和重建
> 在分布式系统中，将对象进行序列化，并在不同的计算机之间进行传输，接收方可以通过反序列化操作将字节序列
转换为可操作的对象。某些远程通信框架使用序列化和反序列化来实现远程方法调用，方法调用和参数会被序列化
成字节流发送给远程服务，然后通过反序列化在远程服务端还原方法调用和参数。序列化和反序列化的设计就是用来
传输数据的，当两个进程进行通信的时候，可以通过序列化反序列化来进行传输。序列化后的字节流保存了对象的状
态以及相关的描述信息，而反序列化则是根据这些信息“复刻”出一个和原来一模一样的对象。本质上讲，序列化就是
把实体对象状态按照一定的格式写入到有序字节流，反序列化就是从有序字节流重建对象，恢复对象状态。（百度百科）

4. RPC相关

> 远程过程调用（RPC）是一种进程间交互技术，主要应用于基于client-server的应用中。
这种技术允许计算机A上的进程调用另一台计算机B上的进程，其中计算机A上的调用进程被挂起，直到B上的被调用进程完成执行并返回结果给A。
这一过程对于开发人员来说是透明的，调用方可以通过参数将信息传送给被调用方，然后通过传回的结果得到信息。
RPC采用客户机/服务器(C/S)模式，其中请求程序作为客户机，而服务提供程序作为服务器。(baidu)我理解就是一个同步请求

5. c11的部分新特性

总结

6. 什么是共识，一致性算法

共识是容错分布式系统中的一个基本问题。共识涉及多个服务器对状态机状态（对本项目而言就是上层的k-v数据库）达成一致。一旦他们对状态机状态做出决定，这个决定就是最终决定（已经被集群共识的值可以保证后面不会被覆盖，Raft的安全性）。

典型的一致性算法在其大部分服务器可用时保持运行; 例如，即使有2台服务器出现故障，5台服务器的集群也可以继续运行。如果更多的服务器出现故障，它们将停止对外提供服务(但永远不会返回不正确的结果)。即小于一半的节点出现故障不会对整个集群的运行造成影响，一半或一半以上的节点出现故障则整个集群停止对外提供服务。

7. 共识算法要满足的性质

• 在非拜占庭条件下保证共识的一致性。非拜占庭条件就是可信的网络条件，即与你通信的节点的信息都是真实的，不存在欺骗。
• 在多数节点存活时，保持可用性。“多数”永远指的是配置文件中所有节点的多数，而不是存活节点的多数。多数等同于超过半数的节点，多数这个概念概念很重要，贯穿Raft算法的多个步骤。
• 不依赖于绝对时间。理解这点要明白共识算法是要应对节点出现故障的情况，在这样的环境中网络报文也很可能会受到干扰从而延迟，如果完全依靠于绝对时间，会带来问题，Raft用自定的Term（任期）作为逻辑时钟来代替绝对时间。
• 在多数节点一致后就返回结果，而不会受到个别慢节点的影响。这点与第二点联合理解，只要“大多数节点同意该操作”就代表整个集群同意该操作。对于raft来说，”操作“是储存到日志log中，一个操作就是log中的一个entry。

8. Raft中的一些重要概念

• 状态机：raft的上层应用，可以是k-v数据库（本项目）
• 日志、log、entry：
• 日志log：raft保存的外部命令是以日志保存
• entry：日志有很多，可以看成一个连续的数组，而其中的的一个称为entry
• 提交日志commit：raft保存日志后，经过复制同步，才能真正应用到上层状态机，这个“应用”的过程称为提交
• 节点身份：follower、Candidate、Leader ：raft集群中不同节点的身份
• term：也称任期，是raft的逻辑时钟
• 选举：follower变成leader需要选举
• 领导人：就是leader
• 日志的term：在日志提交的时候，会记录这个日志在什么“时候”（哪一个term）记录的，用于后续日志的新旧比较
• 心跳、日志同步：leader向follower发送心跳（AppendEntryRPC）用于告诉follower自己的存在以及通过心跳来携带日志以同步
• 日志：
  首先掌握日志的概念，Raft算法可以让多个节点的上层状态机保持一致的关键是让 各个节点的日志 保持一致，日志中保存客户端发送来的命令，上层的状态机根据日志执行命令，那么日志一致，自然上层的状态机就是一致的。所以raft的目的就是保证各个节点的日志是相同的。
• 节点身份：follower、Candidate、Leader ：
  • Leader ：集群内最多只会有一个 leader，负责发起心跳，响应客户端，创建日志，同步日志。
  • Candidate ：leader 选举过程中的临时角色，由 follower 转化而来，发起投票参与竞选。
  • Follower ：接受 leader 的心跳和日志同步数据，投票给 candidate。
• 安全性：Election Safety ：每个 term 最多只会有一个 leader；集群同时最多只会有一个可以读写的 leader。

Raft是一个强Leader 模型，可以粗暴理解成Leader负责统领follower，如果Leader出现故障，那么整个集群都会对外停止服务，直到选举出下一个Leader。如果follower出现故障（数量占少部分），整个集群依然可以运行。

8.1 Raft是如何保证一个Term只有一个Leader的？

• 因为Candidate变成Leader的条件是获得超过半数选票，一个节点在一个Term内只有一个选票（投给了一个节点就不能再投递给另一个节点），因此不可能有两个节点同时获得超过半数的选票。
• 发生故障时，一个节点无法知道当前最新的Term是多少，在故障恢复后，节点就可以通过其他节点发送过来的心跳中的Term信息查明一些过期信息。
• 当发现自己的Term小于其他节点的Term时，这意味着“自己已经过期”，不同身份的节点的处理方式有所不同：
  • leader、Candidate：退回follower并更新term到较大的那个Term
  • follower：更新Term信息到较大的那个Term
• 相反，如果发现自己的Term大于其他节点的Term，那么就会忽略这个消息中携带的其他信息。

8.2 过程

Raft是一个强Leader 模型，可以粗暴理解成Leader负责统领follower，如果Leader出现故障，那么整个集群都会对外停止服务，直到选举出下一个Leader。

• 1. 如何发现Leader出现故障？
     • leader会定时向集群中剩下的节点（follower）发送AppendEntry（作为心跳，hearbeat ）以通知自己仍然存活。
     • 可以推知，如果follower在一段时间内没有接收leader发送的AppendEntry，那么follower就会认为当前的leader 出现故障，从而发起选举。
     • 这里 “follower在一段时间内没有接收leader发送的AppendEntry”，在实现上可以用一个定时器和一个标志位来实现，每到定时时间检查这期间有无AppendEntry 即可。
       AppendEntry 具体来说有两种主要的作用和一个附带的作用：
       主要作用：
       • 心跳
         携带日志entry及其辅助信息，以控制日志的同步和日志向状态机提交
       • 附带的作用：
         通告leader的index和term等关键信息以便follower对比确认follower自己或者leader是否过期
• 2. follower知道leader出现故障后如何选举出leader？
     • follower认为leader故障后只能通过：term增加，变成candidate，向其他节点发起RequestVoteRPC申请其他follower的选票，过一段时间之后会发生如下情况：
       • 赢得选举，马上成为leader （此时term已经增加了）
       • 发现有符合要求的leader，自己马上变成follower 了，这个符合要求包括：leader的term≥自己的term
       • 一轮选举结束，无人变成leader，那么循环这个过程，即：term增加，变成candidate。赢得选举的条件前面也有过提及，即获得一半以上的选票。
• 3. 符合什么条件的节点可以成为leader？
     这一点也称为“选举限制”，有限制的目的是为了保证选举出的 leader 一定包含了整个集群中目前已 committed 的所有日志。
     • 当 candidate 发送 RequestVoteRPC 时，会带上最后一个 entry 的信息。 所有的节点收到该请求后，都会比对自己的日志，如果发现自己的日志更新一些，则会拒绝投票给该 candidate，即自己的日志必须要“不旧于”改candidate。

     ---

     判断日志老旧的方法raft论文中用了一段来说明，这里说一下如何判断日志的老旧：
     • 需要比较两个东西：最新日志entry的term和对应的index。index即日志entry在整个日志的索引。

     	if 两个节点最新日志entry的term不同term大的日志更新else最新日志entry的index大的更新end
     

     这样的限制可以保证：成为leader的节点，其日志已经是多数节点中最完备的，即包含了整个集群的所有 committed entries。
• 4. 感觉很复杂，为什么不直接让follower拷贝leader的日志 / leader发送全部的日志给follower？
  • leader发送日志的目的是让follower同步自己的日志，当然可以让leader发送自己全部的日志给follower，然后follower接收后就覆盖自己原有的日志，但是这样就会携带大量的无效的日志（因为这些日志follower本身就有）。
  • 因此 raft的方式是：先找到日志不匹配的那个点，然后只同步那个点之后的日志。

======================================================================

这篇关于【基于Raft的k-v存储数据库实现】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---