python做软件的网站,北京公司网站制作公司,嘉兴网站建设搭建,wordpress oss ftp基于Raft的k-v存储数据库实现 基本概念1. 什么是分布式系统2. 什么是Raft协议3. 什么是序列化和反序列化4. RPC相关5. c11的部分新特性6. 什么是共识#xff0c;一致性算法7. 共识算法要满足的性质8. Raft中的一些重要概念8.1 Raft是如何保证一个Term只有一个Leader的#xf… 基于Raft的k-v存储数据库实现 基本概念1. 什么是分布式系统2. 什么是Raft协议3. 什么是序列化和反序列化4. RPC相关5. c11的部分新特性6. 什么是共识一致性算法7. 共识算法要满足的性质8. Raft中的一些重要概念8.1 Raft是如何保证一个Term只有一个Leader的8.2 过程 原文链接
基本概念
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日志lograft保存的外部命令是以日志保存entry日志有很多可以看成一个连续的数组而其中的的一个称为entry提交日志commitraft保存日志后经过复制同步才能真正应用到上层状态机这个“应用”的过程称为提交节点身份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到较大的那个Termfollower更新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在整个日志的索引。 if 两个节点最新日志entry的term不同term大的日志更新else最新日志entry的index大的更新end这样的限制可以保证成为leader的节点其日志已经是多数节点中最完备的即包含了整个集群的所有 committed entries。 感觉很复杂为什么不直接让follower拷贝leader的日志 / leader发送全部的日志给follower leader发送日志的目的是让follower同步自己的日志当然可以让leader发送自己全部的日志给follower然后follower接收后就覆盖自己原有的日志但是这样就会携带大量的无效的日志因为这些日志follower本身就有。因此 raft的方式是先找到日志不匹配的那个点然后只同步那个点之后的日志。
