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

原文链接
根本概念

1. 什么是分布式系统

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

复制代码

2. 什么是Raft协议

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

复制代码

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

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

复制代码

4. RPC相干

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

复制代码

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。

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

    ---

    判断日志老旧的方法raft论文中用了一段来阐明，这里说一下如何判断日志的老旧：     
    
    
    
    • 必要比较两个东西：最新日志entry的term和对应的index。index克日志entry在整个日志的索引。
      
    1.         if 两个节点最新日志entry的term不同
    2.                 term大的日志更新
    3.         else
    4.                 最新日志entry的index大的更新
    5.         end

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

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。