# goraft **Repository Path**: liatong/goraft ## Basic Information - **Project Name**: goraft - **Description**: go实验raft算法核心逻辑 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 1 - **Created**: 2022-09-01 - **Last Updated**: 2024-03-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # Raft算法简述 ## 算法概述 从整体简要描述raft论文中的准备raft算法策略，主要包含以下几个方面： 1. 选举相关 - 节点选举 - 节点选举安全 - 节点变更（删除及添加） 2. 日志复制相关 - 日志复制过程 - 日志持久化存储及快照 - 新节点日志同步 - 日志压缩 # 选举过程 ## 节点选举 - 选举过程中的状态装换: [![Raft选举状态](/assets/img/raft-states.jpeg "状态转换")](https://www.codedump.info/post/20180921-raft/) * 角色 - Leader - Candidate - Follower： 接收客户端日志请求，会重定向到Leader节点 * 选举任期 - 节点在进行通信时都会带上本节点的当前任期号 - 任期号在raft算法中更像一个“逻辑时钟（logic clock）”的作用 * 选举过程 - 初始时所有节点均为Followr角色，获取一个150~300ms的随机任期时间。不断监测选举任期是否到期，如果到期就切换为Candidate角色，并进入选举阶段 - Candidate发送RequestVote选票请求，Follower接收RV时，判断RV任期是否>=自己的任期。 - 如果比自己任期小的就投反对票，并返回RV_Replay包含自己的任期ID。 - 如果大于等于自己的任期，那还要判断自己是否已经投票给此节点或其他节点，如果投票给其他节点了，那么投反对票；如果已投票给此节点，那么就投赞成票。如果还未投票给任何节点，那么就进行投票限制条件判断； - 为保证选举的节点符合选主条件，需要进行投票判断;条件判断符合投赞成，条件不符合投反馈； - 限制判断条件为：选举节点的日志需要比Follower节点新；即RV中携带的日志信息，比Follower本身记录的preLogTerm,preLogIndex大，那么表示为最新；任期更大表示更新，任期相同索引更大表示更新； - Candidate节点，接收RV_Replay后更新自己的状态 - 反对票：RV_Replay中的任期比自己大，自己变更为Follower节点； - 赞成票：更新获取的赞票票数 - Candidate选举成功成为Leader节点；Leader节点将于其他所有节点通过RPC调用保持心跳信息； ## 集群成员变更 在集群节点数量变更时，避免新增大量节点导致存在多个Leader选举成功的情况，所以每次新增节点都之支持变更一个节点。集群不能直接切换到新的节点列表中，需符合以下两种机制： - 一次仅支持操作一个节点 - 集群不能马上切换为新的节点列表，需进行同步确认后才可切换； ### 集群成员变更过程 - 两阶段成员变更（实现相对复杂） 1. Leader收到成员变更请求从Cold切成Cold,new； 2. Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认； 3. Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置； 4. 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry并切换到Cnew； 5. 接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上； 6. Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出； 7. Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功 - 一阶段成员变更（简单） 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。 Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。 ----- # 日志复制 ----- ### 定义 将业务服务当成一个状态机，所谓的状态机就是通过重放数据操作日志，最终实现数据的变更。相同的一组操作日志重放后一定能够得到一致的数据。raft算法中的日志复制，就是用来保证集群中的所有节点的操作日志一致性的。即所有节点的数据最终一致，得到的日志是一致的。这样基于raft算法创建的状态机集群（例如KV存储系统），也就能够保证数据一致性。 ## 日志复制过程 ### 过程概述 - 状态机客户端（Server）提交操作日志，给leader节点；leader节点接收操作日志，并将操作日志存放再日志存储中； - Leader存储每个Follower节点接收的最新log的索引位置Index,neexIndex[int]int; Leader通过AE请求，携带上对应的logEntrity发送Follower节点；每次给follower带过去的日志就是以nextIndex来决定； - 如果follower节点的日志与这个值匹配，将返回成功; - 同时带上本节点当前的最大日志ID;Leader将置nextIndex = min(hintIndex+1,上一次append消息的索引)，再次发出添加日志请求给Follower; - Follower节点接收到AE请求后。响应AE请求，并带上自己的Term任期；Follower把log添加到本地的日志列表中； - Leader节点接收到大于半数的Follower成功AE响应，那么标识对应的logEntrity可以提交；Leader的commitIndex已经收到超过一半确认log置； - Leader确认了新的已Commit的log,通知应用层的客户端（Server)有新的日志可应用;Leader把本地的logApplyIndex,赋值commitIndex; - Leader更新完成commitIdex后，再次通过AE请求携带Leader最新的commitIndex通知给Follower节点，Follower节点收到最commitIndex后，就变更本地的commitIndex以及logApply,并通知Follower的客户端应用日志； ### Follower与Leader日志不一致的处理 - 接收Leader的AE日志，AE携带记录的当前任期，以及Leader所记录的Follower nextIndex位置； - 脚本Follower本地的最大commitIndex以及任期，与leader传递过来的不匹配；那么就返回失败，并把本地的最大日志index回传给Leader节点 - Leader节点接收Follower失败响应；获取到Follower最新的commitIndex后，修改nextIndex及matchIndex;然后重新发送AE请求； - 如果Follower节点的数据，超过Leader传递过来的数据；那么Follower中超出部分的数据需要删除，并返回正确数据； - 如果Follower存在超出与Leader不匹配的log数据；那么需删除多出部分，并返回匹配的最后一个index给Leader进行重新同步； ### Leader的处理 - Leader存储两个与Follower相关的索引信息；正常情况： nextIndex= matchIndex + 1； - nextIndex存储的是下一次给该节点同步日志时的日志索引。 - matchIndex存储的是该节点的最大日志索引 ### 新节点的日志同步 避免新加入节点的数据未同步完成，可能为空的状态下；集群出现多个节点故障导致整个集群不可用；Raft算法针对这种新添加进来的节点，是如下处理的 - 添加进来的新节点首先将不加入到集群中，而是等待数据追上集群的进度。 - leader同步数据给新节点的流程是，划分为多个轮次，每一轮同步一部分数据，而在同步的时候，leader仍然可以写入新的数据，只要等新的轮次到来继续同步就好。 ### 日志压缩 日志数据如果不进行压缩处理掉的话，会一直增长下去。为此Raft使用快照数据来进行日志压缩，比如针对键值a的几次操作日志a=1、删除a、a=3最后可以被压缩成为最后的结果数据即a=3； ---- # Demo项目主要使用go实现raft算法中的选择算法 ---- ## 选举算法策略规则 1. 三种角色 - Candidate - Follower - Leader 2. 选举任期Term - 每个选举节点，具备一个150ms到300ms的选举任务 - 定期的监测任期内是否存在：主任期状态更新（主的心跳包或其他节点选主成功） - 每进行一轮选举，任期序号递增，并以此作为判断任期的早晚，影响选主过程 3. 选举过程 - 初始化随机任期时间，初始化任期ID - 节点连接其他所有对等节点，启动选主过程 - 节点角色从Follower转换为Candidate，并自投1票。向其他平等节点发送RequestVote请求选票 - 节点等待选票结果。其他节点任期内接收RV请求，如果未投票或不是主，就进行投赞成票。 - 节点选票投票的其他决策：Leader角色，接收到RV后查看RV的看任期ID。如果更大Leader立即变为Follower - ## 日志复制策略 ### 日志复制过程 - 选举模块的客户端（Server)Submit指定请求；选举模块接收到Submit Command后，会先记录响应的LogEntity到本地存储列表中。 - Leader节点通过心跳把新的日志（比对最新日志与记录同步给节点的日志的差异），放在通讯包中发送给Follower节点 - Follower节点接收到日志后，寻找到与Leader发送的日志相匹配个正确节点（日志附带最新节点的上一个节点信息），再匹配的节点后插入日子 - Follower正确写入Sumbit日志后，将会回复Leader正确写入结果，以后Follower的最后logIndex； - Leader接收到正确响应后，对最后日志lastCommitIndex与Follower回复的logIndex进行比较，期间就是未Commit的日志； - Leader针对这部分日志进行已复制多少节点统计，如果已复制节点数> n/2+1；那么就确认可以Commit，修改LastCommit信息，并把可以Commit的日志，通知客户端（Server),并通知其他的Follower节点； - Follower节点收到，可以Commit的Log信息后，同样需要通知客户端（Server）；Commit相关日志 ### 选主安全 选主过程添加对Candidate节点上的日志内容完整性有所约束 - Candidate发送选票请求时，需要将当前节点的所具备的最新的日志索引以及日志的最后任期发送给其他节点 - 其他节点接收到RV后，是否投赞成票的依据。还要加入Candidate中的log是否包含了对等节点的所有log；即lastLog.Index lastLog.Term;如果包含所有就投赞成票，没有包含所有就投反对票 ### 选举模块 1. 属性 - log 存放日志 - nextLogIndex 记录Follower的下一个索引 - commitLogIndex 记录Leader节点提交的日志索引 2. 方法 - ## 参考连接 [1. Raft的原理解析](https://www.codedump.info/post/20180921-raft/#%E6%B7%BB%E5%8A%A0%E6%96%B0%E8%8A%82%E7%82%B9%E5%88%B0%E9%9B%86%E7%BE%A4%E4%B8%AD) [2. Raft的golang实现范例](https://eli.thegreenplace.net/2020/implementing-raft-part-0-introduction/)