营销型的网站,最好看免费观看高清大全老师补课中国,教育培训网站排名,江西短视频搜索seo推荐上文我们聊了在设计高性能、高可用图数据库的时候#xff0c;从单实例、单节点出发#xff0c;一般有3种架构演进选项#xff1a;主备高可用#xff0c;今天我们具体讲讲分布式共识#xff0c;以及大规模水平分布式。
主备高可用、分布式共识、大规模水平分布式#xff…上文我们聊了在设计高性能、高可用图数据库的时候从单实例、单节点出发一般有3种架构演进选项主备高可用今天我们具体讲讲分布式共识以及大规模水平分布式。
主备高可用、分布式共识、大规模水平分布式我们都知道这3套系统的实现复杂度是从低到高渐进的但这并不意味着复杂度更高的系统在不同的应用场景、用户需求、查询模式、查询复杂度、数据特征条件下就能获得更好的效果。
分布式共识系统
前面提到即便在最简单的主备系统架构中也可能发生系统内无法保证一致性的情况这是因为任何分布式系统在本质上都是异步分布式。所有操作网络传输、数据处理、发送回执、信息同步、程序启动或重启等都需要时间来完成任何交易、任何事务处理在一个实例内都是异步的而在多个实例之间这种异步性会被放大很多。分布式系统设计最重要的一个原则就是与异步性共存不追求完美的一致性但可以假设整个系统在大部分时间内是正常工作的即便部分进程或网络出现问题整个系统依然可以对外提供服务。
分布式共识系统特别是分布式共识算法就由此应运而生被用来保证即便在分布式系统中出现了各种各样的问题但是整体服务依然可以保持在线。
分布式共识算法有3个核心特性合法有效validated proposal、达成一致reaching agreement或unanimity、快速终止processcan be terminated。
合法有效指的是进程间的指令信息传播需要基于合理有效的数据且能让有效的进程集合达成一致并且最终形成共识进而终止同步过程的时耗需要在合理的、较短的时间内完成。在高性能分布式系统中可毫秒级完成同步而在较大规模跨地域的分布式共识系统中可能会出现秒级甚至需要人工介入的分钟级形成共识具体的终止时间延迟取决于具体的业务需求。
达成一致等同于形成共识类似于多个进程间的民主选举一旦它们形成了共识任何参与了选举的进程都不再允许对结果产生异议或按照与结果不符的方式或内容执行任务——这种情况就是我们前面提到过的分布式系统无法解决的“两军通信问题”“拜占庭将军问题”。
图1示意了多任务多进程间形成共识的过程这一过程与我们日常生活中的行为并无本质不同。 图1 多任务间形成共识 A、B、C、D四个人在一起讨论晚上去哪里一开始A提议去看电影得到了B的赞同但是C很快提出去吃晚餐D赞同C的提议随后B改口赞同C的提议最终A也改为同意C的提议。此时四人达成了晚上去吃晚餐的共识。这就是多任务共识形成的简单例子。在实际的分布式共识算法中还会引入如角色、阶段以及如何终止共识等问题下面逐一分析。
形成共识的过程需要有明确的终止算法否则就会出现悬而不决、无限等待的问题。例如当某个实例进程下线后剩余进程如果无限等待其重新上线或是如图1所示A、B、C、D四个进程出现层出不穷的新方案以至于四人永远无法达成共识。共识算法需要考虑这些情况并规避其发生。本质上无论采用何种跨进程的集群内通信方式都要使用尽可能简洁的算法让共识的达成进而终止代价较低。
那么分布式共识系统应该采用何种通信手段呢前面提到过网络系统的3种通信方式中心化广播式、去中心化分层区域广播或多播式以及点对点分布式对小型分布式系统而言最简单和最直接的方式是广播式因为发起广播者与信息接收者之间的互动逻辑决定了这个交互过程是属于“尽人事听天命”类型的单向一次性传送模式还是其他更可靠的交互模式。
理解这个过程需要考虑这样一种可能发生的情况即如果发起者A在发出请求给B、C后下线但是并没有向D发送那么在广播算法中就需要考虑加上B、C可以向D继续广播的逻辑。从通信的复杂度角度看这样的实现就是一种“可靠广播”模式在有N个实例的分布式系统中其复杂度为显然这种漫灌式重度通信模式floodingcommunication对于大型分布式系统是不合适的但是它已经具备了通过冗余通信来实现系统完整性、一致性的特征。
下面分析如何在分布式共识通信的过程中保证消息的有序性即至少需要实现2个功能多消息的事务性原子性、不可分割性和序列性。
一种比较简单的原子广播算法是分布式KV项目Apache Zookeeper中的ZABZookeeper Atomic Broadcast它把Zookeeper集群内的所有进程分为两个角色领导者leader和跟随者follower3种状态跟随following、领导leading和选举election它的通信协议分为4个阶段启动选举阶段leader election phase、发现阶段discovery phase、同步阶段synchronization phase、广播阶段broadcasting phase。
在启动选举阶段阶段0某个进程在选举状态中开始执行启动选举算法并找到集群内的其他进程投票成为领导者。
在发现阶段阶段1进程检查选票并判断是否要成为两个角色之一被选举为潜在领导者的进程称作意向领导prospective leader之后该进程通过与其他跟随进程通信发现最新的被接受的事务执行顺序。
在同步阶段阶段2发现过程被终止跟随进程通过意向领导更新的历史记录进行同步。如果跟随进程自身的历史记录不晚于意向领导的历史则向意向领导进程发送确认信息。当意向领导得到了主体选举人quorum的确认后它会发送确认commit信息这时意向领导成为确认领导established leader。该阶段的算法逻辑如下 在广播阶段阶段3如果没有新的宕机类问题发生集群会一直保持在本阶段。在此阶段不会出现两个领导进程当前领导进程会允许新的跟随者加入并接受事务广播信息的同步。
ZAB的阶段13都采用异步的方式并通过定期的跟随进程与领导进程间的心跳信息来探测是否出现故障。如果领导进程在预定的超时时间内没有收到心跳它会切换至选举状态并进入阶段0同样地跟随进程也可以在没有收到领导进程心跳后进入阶段0。
在ZAB的具体实现逻辑中leader选举是最核心的部分ZAB采用的策略是拥有最新历史记录的进程会被选举为leader并且假设拥有全部已提交事务commitedtransactions的进程同样拥有最新的已提议事务most recent proposed transaction。当然这个假设的前提是集群内的ID序列化及顺序增长这一假设让leader选举的逻辑大幅简化因此称为快速领导选举Fast Leader Election,FLE。即便如此FLE过程中的判断逻辑特别是各种边界情况的考量依然很多下面是节选的参与选举进程的FLE实现代码逻辑 ZAB最早是作为Yahoo内部Hadoop项目的一个子项目后来被拆分独立出来作为一款分布式服务器间进程通信及同步框架并在2010年后成为Apache开源社区中的一个顶级项目。从上面的伪码中就可以看出ZAB所采用的算法逻辑和通信步骤较为复杂。类似地Paxos类算法的实现对于跨地理区域的系统实例间时钟同步有着严苛的要求且算法逻辑复杂不容易被理解。头部企业谷歌在其Spanner系统中通过原子钟的帮助实现基于Paxos的大规模分布式共识系统但是对缺少同等系统架构把控能力的企业而言Paxos就显得门槛过高了。
在2013年之后更简单、可解释的分布式共识算法应运而生其中最知名的是2014年DiegoOngaro提出的RAFT算法及一种称作LogCabin的代码实现。 在RAFT算法中集群内的每个共识算法参与进程有3种角色候选者candidate、领导者leader和跟随者follower。
与Poxos通过时钟同步来保证数据事务全局顺序一致不同但是类似于ZABRAFT把时间块切分为terms选举任期类似于ZAB中的epoch在每个任期期间系统采用唯一的ID来标识每个任期以保证不会出现任期冲突领导者具有唯一性和稳定性。
RAFT算法有3个主要组件或阶段选举阶段、定期心跳阶段和广播及日志复制阶段。
图2示意了在一个3节点的RAFT集群中客户端与服务器集群的互动整个流程围绕领导者角色进程展开可分解为10步而这只覆盖了RAFT算法的广播及日志复制阶段。 图2RAFT集群C/S工作流程步骤分解 如图3所示3种角色及所负责的任务内容如下
· 跟随者不会主动发起任何通信只被动接收RPC调用Remote Procedure Calls。
· 候选者会发起新的选举对选举任期进行增量控制发出选票或重启以上任务。
在该过程中只有含有全部已提交命令的候选者会成为领导者并通过RPC调用的方式通知其他候选者选举结果并避免出现split vote平票的问题在RAFT算法中通过随机选举超时例如在0.150.3s间随机制造超时来避免因两个实例的候选进程同时发出导致选票计数出现平票。
另外每个进程都维护了自己的一套日志在原生的RAFT算法实现中称为logcabin木筏。
· 领导者会定期向所有跟随者发送心跳RPC以防止因过长的空闲时间而过期和重新选举。领导者通常是最先面向客户端进程请求的对日志进程进行添加处理以及发起日志复制提交并更改自身的状态机并向所有跟随者同步log。 图3RAFT共识算法集群进程间的角色转换关系 RAFT描述的是一种通用的算法逻辑它的具体实现有很多种并且有很大调整空间。例如原始的RAFT算法与一主多备的架构类似任何时候只有一个实例在服务客户端请求。如果我们结合图数据库的可能查询请求场景完全可以分阶段地改造为如下几种难度从低到高。· 多实例同时接收读请求负载写入依然通过leader节点实现读负载在全部在线节点间均衡。
· 多实例同时接收先读再写类请求负载典型的如回写类的图算法全部节点都可以承载图算法回写部分先进行本地回写再异步同步给其他节点。 · 多实例同时接收更新请求负载并转发写入请求可以发送给任意集群内节点但是跟随者会转发给leader节点处理。
· 多实例同时处理更新请求这是最复杂的一种情况取决于具体的隔离层级需求如果多个请求同时在多个实例上更改同一段数据并且有不同的赋值会造成数据的不一致性。在这种情况下实现一致性的最可靠途径就是对关键区域采用序列化访问。这也是本章反复提到的任何分布式系统在最底层、最细节、最关键的部分一定要考虑到有需要串行处理的情况。
目前已知的RAFT算法可能远超100种如ETCD、HazelCast、Hashicorp、TiKV、CockrochDB、Neo4j、Ultipa Graph、嬴图等并且以各种编程语言实现如C、C、Java、Rust、Python、Erlang、Golang、C#、Scala、Ruby等足以体现分布式共识算法及系统的生命力。
在基于共识算法的高可用分布式系统架构中我们做了一个比较重要的假设即大多数时候系统的每个实例上都存有全量的数据。注意我们限定的是“大多数时候”言下之意是在某个时间点或切片下多个实例间可能存在数据或状态的不一致性也因此需要在分布式系统内通过共识算法来实现数据同步以形成最终的数据一致性。
下篇继续聊大规模水平分布式。最近很忙不过老夫会尽快更文。
· END · 文/Ricky - HPC高性能计算与存储专家、大数据专家、数据库专家及学者
