做视频特效的网站,珠海的门户网站有哪些,wordpress 图片重命名,做网站有什么语言好前言
大家好#xff0c;这里是白泽。本文是一年多前参加字节训练营针对 Raft 自我整理的笔记。
本篇文章将模拟一个KV数据读写服务#xff0c;从提供单一节点读写服务#xff0c;到结合分布式一致性协议#xff08;Raft#xff09;后#xff0c;逐步扩展为一个分布式的…前言
大家好这里是白泽。本文是一年多前参加字节训练营针对 Raft 自我整理的笔记。
本篇文章将模拟一个KV数据读写服务从提供单一节点读写服务到结合分布式一致性协议Raft后逐步扩展为一个分布式的满足一致性读写需求的读写服务的过程。
其中将配合引入Raft协议的种种概念选主、一致性、共识、安全等通篇阅读之后将帮助你深刻理解什么是分布式一致性协议。
一、 单机KV数据读写服务 DB Engine这里可以简单看成对数据的状态进行存储比如B树型的组织形式负责存储KV的内容 并假设这个KV服务将提供如下接口
Get(key) — valuePut([key, value])
思考此时KV服务的可靠性
容错单个数据存储节点不具备容错能力。高可用服务部署在单节点上节点宕机将无法提供服务。
思考此时KV服务的正确性
单进程所有操作顺序执行可以保证已经存储的数据是正确的
数据规模不断增加我们需要扩大这个KV服务的规模将其构建成一个分布式的系统
二、一致性与共识算法
2.1 从复制开始
既然一个节点会挂那么我们就多准备一个节点 我们这里只考虑主副本负责接收数据而从副本只负责同步接收主副本数据的模式如果主从都开放数据接收能力将要考虑更多高可用和数据一致性的问题。
2.2 如何复制 主副本定期拷贝全量数据到从副本代价太高主副本拷贝操作日志到从副本如果你了解MySQL的主从同步你就会想起它也是通过从副本监听主副本当中的bin log操作日志变化进行集群数据同步的因此这种方式也是更主流的选择。
2.3 具体的写流程 主副本把所有的操作打包成Log 所有的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 RSMreplicated state machine Raft中所有的共识机制consensus都是直接使用Log作为载体简单说就是client将Log提供给Raft也就是上图的Consensus ModuleRaft确定这个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是如何在节点间同步的
第一张图s2是当前Leader紫色的小箭头指向每个节点已经确认commit的Log位置第二张图s2又append了一条新的Log用K标识第三张图表示s2将自己收到的K以及自己的Commited Index发送给所有Follower节点。Follower都同步Leader的Log以及Commited Index并且Follower的状态机检测到自己的Commited Index又向前推进了说明有新的Log值达成了共识就会把Commited Index没读取的Log值应用给状态机第四张图当Follower完成步骤三的操作之后会告诉Leader自己已经拿到这个Log值了Leader在收到多数派的确认消息后就可以确定这个K已经永远的持久化也就是已经Commit了因此将Commited Index向后推一位
这里有一个细节就是虽然Raft协议使节点间的数据最终达成了一致但是节点Log数据落盘时间是有先后的因为Commited Index在各节点之间存在差异所以Log与状态机是有时差的
3.5 Raft从节点失效 图一假设s3失效了很久Log有很多数据没有同步图二表示此时的Leader是s2将自己Log中的K和自己的Commited Index复制给s1图三中s2的K完成了commit流程参考Raft日志复制因为s1、s2共两个节点已经形成了多数派此时已经有容错能力了图四中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之中就返回确认响应给了s2s2将自己的Commited Index向后推进到Q的位置。
从图二开始s3发现s2挂了没有Leader则将自己的term1变为3并且向s1请求Vote图三中s1发现RequestVote是来自term等于3的大于自己的term因此将自己的term也更新为3同时答应给s3投票达成多数派条件s3成为新的Leader图四s3开始同步自己的Log给s1但是发现s1中的Log起初为XW而s3中为XTQY因此还是会按照从后往前迭代的方式将数据同步给s1Y、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] 感兴趣可以关注公众号 「白泽talk」白泽目前也打算打造一个氛围良好的行业交流群文章的更新也会提前预告欢迎加入622383022。
