前言 本篇文章将模拟一个KV数据读写服务,从提供单一节点读写服务,到结合分布式一致性协议(Raft )后,逐步扩展为一个分布式的,满足一致性读写需求的读写服务的过程。
其中将配合引入Raft协议 的种种概念:选主、一致性、共识、安全等 ,通篇阅读之后,将帮助你深刻理解什么是分布式一致性协议。
本文已同步掘金博客,在线阅读体验会更好一些:https://juejin.cn/post/7133224955541618702
一、 单机KV数据读写服务 DB Engine 这里可以简单看成对数据的状态进行存储(比如B+树型的组织形式),负责存储KV 的内容 ,并假设这个KV服务将提供如下接口:
• Get(key) —> value • Put([key, value]) 思考此时KV服务的可靠性:
• 容错:单个数据存储节点,不具备容错能力。 • 高可用:服务部署在单节点上,节点宕机将无法提供服务。 思考此时KV服务的正确性:
• 单进程,所有操作顺序执行,可以保证已经存储的数据是正确的 数据规模不断增加,我们需要扩大这个KV服务的规模,将其构建成一个分布式的系统
二、一致性与共识算法 2.1 从复制开始 既然一个节点会挂,那么我们就多准备一个节点!
我们这里只考虑主副本 负责接收数据 ,而从副本 只负责同步 接收主副本 数据的模式,如果主从都开放数据接收能力,将要考虑更多高可用和数据一致性的问题。
2.2 如何复制 • 主副本定期拷贝全量数据到从副本(代价太高) • 主副本拷贝操作日志到从副本:如果你了解MySQL的主从同步,你就会想起它也是通过从副本 监听主副本 当中的bin log
操作日志变化,进行集群数据同步的,因此这种方式也是更主流的选择。 2.3 具体的写流程 • 主副本把所有的操作打包成Log
• 应用包装成状态机(也就是DB Engine部分 ),只接收Log
作为Input
• 主副本确认Log
已经成功写入到从副本机器上,当状态机apply
后,返回客户端(关于写入之后,请求返回客户端的时机,是可以由应用控制的,可以是Log
写入从副本 之后,就从主副本 机器返回,也可以等Log
完成落盘 之后,再返回) 2.4 具体的读流程 • 方案一:直接读状态机(这里指的是DB ),要求上一步写操作进入状态机后再返回client(数据已落盘) • 方案二:写操作复制Log
完成后直接返回,读操作Block
等待所有pending log
进入状态机 • 如果不遵循上述两种方案:可能存在刚刚写入的值读不到的情况(在Log中) 2.5 什么是一致性 对于我们的KV 服务,要像操作一台机器一样,对用户来说在写入成功后,就应该能读到最近写入的值,而不关心具体底层是如何分布式实现。
一致性是一种模型(或语义),约定一个分布式系统如何向外界提供服务,KV服务中常见的一致性模型有以下两种:
• 最终一致性:读取可能暂时读不到但是总会读到 • 线性一致性:最严格,线性时间执行(写完KV确保就能读到),是最理想中的状态 2.6 复制协议-当失效发生 上述用到的添加了一个从副本 节点的方式,我们暂且将其称为山寨版分布式一致性协议——复制协议 (因为它依赖于主从副本间的复制操作)
那么当主副本失效时,以这个复制协议 为基础的KV服务的运行情况如何呢:
• 容错能力:没有容错能力,因为主副本停了,KV服务就停了 • 高可用:或许有,取决于我们发现主副本宕机后 多快将从副本 切换为主副本 (手动切换) • 正确性:正确,因为操作只从一台机器发起,可以控制所有操作返回前都已经复制到另一台机器了 衍生出的一些的问题:
• 如何保证主副本 是真的失效了,切换的过程中如果主副本又开始接收client
请求,则会出现Log覆盖写 的情况 • 如果增加到3个乃至更多的节点,每次PUT 数据的请求都等待其他节点操作落盘 性能较差 • 能否允许少数节点挂了 的情况下,仍然可以保持服务能工作(具备容错能力) 2.7 共识算法 什么是共识:一个值一旦确定,所有人都认同
共识协议不等于一致性:
• 应用层面不同的一致性,都可以用共识算法来实现• 比如可以故意返回旧的值(共识算法只是一个彼此的约定,只要数据存储与获取符合需求,达成共识即可 ) • 简单的复制协议也可以提供线性一致性(虽然不容错) 一般讨论共识协议 时提到的一致性,都指线性一致性
• 因为弱一致性 往往可以使用相对简单的复制算法 实现 三、一致性协议案例:Raft 3.1 Ratf概述 • 2014年发表 • 易于理解作为算法设计的目标• 使用了RSM、Log、RPC的概念 • 直接使用RPC对算法进行了描述 • Strong Leader-based(所有操作都是Leader发起的) • 使用了随机的方法减少约束(比如选主时Follower谁先发现Leader失联就发起选主) 3.2 复制状态机(RSM) • RSM(replicated state machine)• Raft中所有的共识机制(consensus)都是直接使用Log作为载体:简单说就是client将Log提供给Raft(也就是上图的Consensus Module),Raft确定这个Log已经Commit之后(写入Log文件),将Log提供给用户的状态机 • 注意此时状态机是一个内存中的存储概念 ,当然后续每个节点数据还涉及到落盘持久化,这是具体应用层面的问题了,这里讨论的更多是Raft协议的原理概念,使用状态机对此进行抽象 • Commited Index(这里先有个概念,用于标识Log中哪些数据可以提交给状态机 )• 一旦Raft更新Commited Index,意味着这个Index前所有的Log都可以提交给状态机了 • Commited Index是不持久化的,状态机也是volatile的(断电清空),重启后从第一条Log开始恢复状态机,Raft协议工作过程中每个节点的Commited Index可能是不一致的,但是Ratf可以保证最终所有节点都是一致的 3.3 Raft角色 • Leader是所有操作的发起者,会把Log同步给Follower,确定哪个Log已经Commit了 • 接受Leader的请求,并且在发现Leader消失,则转换为Candidate,向其他Follower申请投票,如果获得票数过半,则晋升为Leader 3.4 Raft日志复制 接下来讲解一下Raft协议中Log是如何在节点间同步的:
1. 第一张图s2是当前Leader,紫色的小箭头指向每个节点已经确认commit的Log位置 2. 第二张图s2又append了一条新的Log,用K标识 3. 第三张图表示,s2将自己收到的K以及自己的Commited Index发送给所有Follower节点。Follower都同步Leader的Log以及Commited Index,并且Follower的状态机检测到自己的Commited Index又向前推进了,说明有新的Log值达成了共识,就会把Commited Index没读取的Log值应用给状态机 4. 第四张图,当Follower完成步骤三的操作之后,会告诉Leader自己已经拿到这个Log值了,Leader在收到多数派的确认消息后,就可以确定这个K已经永远的持久化,也就是已经Commit了,因此将Commited Index向后推一位 这里有一个细节就是,虽然Raft协议使节点间的数据最终达成了一致,但是节点Log数据落盘时间是有先后的(因为Commited Index在各节点之间存在差异,所以Log与状态机是有时差的)
3.5 Raft从节点失效 1. 图一假设s3失效了很久,Log有很多数据没有同步 2. 图二表示此时的Leader是s2,将自己Log中的K和自己的Commited Index复制给s1 3. 图三中s2的K完成了commit(流程参考Raft日志复制),因为s1、s2共两个节点已经形成了多数派(此时已经有容错能力了) 4. 图四中,s3尝试重新同步数据,在Raft协议中,s3会向s2逆向迭代的去获取Log数据(K、QK、TQK、XTQK),直到与s3当前Log相对齐 则完成数据同步(当然Raft具体实现中应用对此过程进行了优化) 3.6 Raft Term Term(周期的概念),在Raft中相当于一个逻辑的时钟,下面介绍:
• 每个Leader服务于一个term:一旦发现更高的term,那么表示我已经不是Leader了 • 每个term至多只有一个leader:选出新的Leader,会使得term增加 • 每个节点存储当前的term • 每个节点term从一开始,只增不减 • 所有的rpc的request response 都携带term • 只commit本term内的log 3.7 Raft主节点失效 • Leader定期发送AppendEntries RPCs 给其余所有的节点 • 如果Follower 有一段时间没有收到Leader的AppendEntries,则转换身份为Candidate • Candidate自增自己的term,同时使用RequestVote PRCs 向剩余节点请求投票• raft在检查是否可以投票时,会检查log是否outdated,至少不比本身旧才会投票给对应的Candidate • 如果多数派投给它,则成为该term的leader 3.8 Raft Leader failure 接下来模拟一下主节点失效后的流程,并且注意此时图一当中,s1的Log内容比较特殊,为XW,这个场景是可以实现的,比如一开始有s1、s2、s3,其中s1是Leader,首先将X同步给了s2和s3,并且接受到了新的W,但是突然s1节点卡死了,s2和s3重新开始选举Leader为s2,最终s2和s3的Log变成了XTQ(这只是一种情况,一切皆有可能),然后s1又恢复了。
关于为什么s3落后s2两条Commited Index,有可能是s2一次同步了两条Log给s3,而s3的状态机还没来得及同步数据,但是s3接收到在标识TQ的Log后,将其commit到自己的Log之中,就返回确认响应给了s2,s2将自己的Commited Index向后推进到Q的位置。
• 从图二开始,s3发现s2挂了,没有Leader,则将自己的term+1变为3,并且向s1请求Vote • 图三中,s1发现RequestVote是来自term等于3的,大于自己的term,因此将自己的term也更新为3,同时答应给s3投票,达成多数派条件,s3成为新的Leader • 图四,s3开始同步自己的Log给s1,但是发现s1中的Log起初为XW,而s3中为XTQY,因此还是会按照从后往前迭代的方式将数据同步给s1(Y、QY、TQY、XTQY),最后s1虽然与同步状态发生了冲突,但是由于Raft是Strong Leader-based
的,会完全按照Leader的内容覆盖自己的Log 3.9 Raft 安全性 - 同 Term • 对于Term内的安全性• 目标:对于所有已经commited的<term, index>位置上至多只有一条log • 由于Raft的多数派选举,我们可以保证在一个term中只有一个leader• 我们可以证明一条更严格的声明:在任何<term, index>位置上,至多只有一条log 3.10 Raft 安全性 - 跨 Term • 对于跨Term的安全性• 目标:如果一个log被标记commited,那这个log一定会在未来所有的leader中出现 • 可以证明这个property:• Raft选举时会检查Log是否outdated,只有最新的才能当选Leader • 选举需要多数派投票,而commited log也已经在多数派当中(必有overlap) • 新Leader一定持有commited log,且Leader永远不会overwrite log 四、回到KV 4.1 重新打造KV服务 结合Raft算法,更新一下我们的KV
回顾一下一致性读写的定义:
• 方案一:• 写log被commit了,返回客户端成功 • 读操作也写入一条log(因为读的数据可能还没从Log写入状态机,无法读取状态机数据),状态机apply log后返回client • 增加Log量 • 方案二:• 写log被commit了,返回客户端成功 • 读操作先等待所有commited log apply,再读取状态机 • 优化写时延 • 方案三:• 写log被状态机apply,返回给client • 读操作直接读状态机 • 优化读时延 多个副本只有单个副本可以提供服务(一个Leader万一忙不过来怎么办)
• 服务无法水平扩展 • 增加更多Raft组(不多展开)• 如果操作跨Raft组(对key进行分组,每一个Raft负责读写一个range的key) 4.2 回到共识算法 • Raft:关于log• 论文中就给出的方案,当过多的Log产生后,启动snapshot,替换掉Log • 如果对于持久化的状态机,如何快速的产生Snapshot(略) • 多组Raft的应用中,Log如何合流(略) • 关于configuration change(节点规模变化)• 论文中就给出的joint-consensus以及单一节点变更两种方案(很复杂,略) 4.3 共识算法的未来 • Raft Paxos相互移植• Raft有很多成熟的实现 • 研究主要关注在Paxos上,下面是两篇论文 • On the Parallels between Paxos and Raft, and how to Port Optimizations[1] • Paxos vs Raft: Have we reached consensus on distributed consensus?[2] 小结 本文根据字节青训课程中一节针对《分布式数据一致性》的课程内容的进行总结与整理,希望可以帮助大家加深对以Raft为代表的分布式一致性协议的理解。