一、Master/slave
这个是多机房数据访问最常用的方案,一般的需求用此方案即可。因此大家也经常提到“premature optimization is the root of all evil”。
优点:利用mysql replication即可实现,成熟稳定。
缺点:写操作存在单点故障,master坏掉之后slave不能写。另外slave的延迟也是个困扰人的小问题。
二、Multi-master
Multi-master指一个系统存在多个master, 每个master都具有read-write能力,需根据时间戳或业务逻辑合并版本。比如分布式版本管理系统git可以理解成multi-master模式。具备最终一致性。多版本数据修改可以借鉴Dynamo的vector clock等方法。
优点:解决了单点故障。
缺点:不易实现一致性,合并版本的逻辑复杂。
三、Two-phase commit(2PC)
Two-phase commit是一个比较简单的一致性算法。由于一致性算法通常用神话(如Paxos的The Part-Time Parliament论文)来比喻容易理解,下面也举个类似神话的例子。
某班要组织一个同学聚会,前提条件是所有参与者同意则活动举行,任意一人拒绝则活动取消。用2PC算法来执行过程如下
Phase 1
Prepare: 组织者(coordinator)打电话给所有参与者(participant) ,同时告知参与者列表。
Proposal: 提出周六2pm-5pm举办活动。
Vote: participant需vote结果给coordinator:accept or reject。
Block: 如果accept, participant锁住周六2pm-5pm的时间,不再接受其他请求。
Phase 2
Commit: 如果所有参与者都同意,组织者coodinator通知所有参与者commit, 否则通知abort,participant解除锁定。
Failure 典型失败情况分析
Participant failure:
任一参与者无响应,coordinator直接执行abort
Coordinator failure:
Takeover: 如果participant一段时间没收到cooridnator确认(commit/abort),则认为coordinator不在了。这时候可自动成为Coordinator备份(watchdog)
Query: watchdog根据phase 1接收的participant列表发起query
Vote: 所有participant回复vote结果给watchdog, accept or reject
Commit: 如果所有都同意,则commit, 否则abort。
优点:实现简单。
缺点:所有参与者需要阻塞(block),throughput低;无容错机制,一节点失败则整个事务失败。
四、Three-phase commit (3PC)
Three-phase commit是一个2PC的改进版。2PC有一些很明显的缺点,比如在coordinator做出commit决策并开始发送commit之后,某个participant突然crash,这时候没法abort transaction, 这时候集群内实际上就存在不一致的情况,crash恢复后的节点跟其他节点数据是不同的。因此3PC将2PC的commit的过程1分为2,分成preCommit及commit, 如图。
从图来看,cohorts(participant)收到preCommit之后,如果没收到commit, 默认也执行commit, 即图上的timeout cause commit。
如果coodinator发送了一半preCommit crash, watchdog接管之后通过query, 如果有任一节点收到commit, 或者全部节点收到preCommit, 则可继续commit, 否则abort。
优点:允许发生单点故障后继续达成一致。
缺点:网络分离问题,比如preCommit消息发送后突然两个机房断开,这时候coodinator所在机房会abort, 另外剩余replicas机房会commit。
Google Chubby的作者Mike Burrows说过, “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法,那就是Paxos”,所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改进
P1a. 每次Paxos实例执行都分配一个编号,编号需要递增,每个replica不接受比当前最大编号小的提案
P2. 一旦一个 value v 被replica通过,那么之后任何再批准的 value 必须是 v,即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说,就是一个参与者一旦accept周六2pm-5pm的proposal, 就不能改变主意。以后不管谁来问都是accept这个value。
一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活,在一个2f+1个节点的集群中,允许有f个节点不可用。
另外Paxos还有很多约束的细节,特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题,由于节点的持久存储可能会发生故障,Byzantine问题会导致Paxos算法P2约束失效。
以上几种方式原理比较如下
分享到:
相关推荐
#资源达人分享计划#
具有不确定性多智能体系统的一致性算法研究.pdf
传统拜占庭一致性中常见的中心化和去中心化算法在解决合法性验证的过程中存在容错率低、消息复杂度高等问题,为此,提出新的区块链一致性算法,引入两阶段提交和法定人数投票的过程,利用区块链协议的分布式总账特点...
综述了多智能体系统分布式一致性问题的研究现状。从理论层面介绍了一致性问题的几种常见定义及与特性相关的主要参数;总结归纳了近年来几种一致性协议及其理论分析结果;分析和阐述了一致性问题的主要应用领域的进展...
为了提高分布式一致性算法的收敛速度, 提出了一种离散高阶分布式一致性算法。该算法通过单跳通信, 利用二跳邻接节点的前多步信息来加速分布式一致性算法的收敛速度。对无向通信拓扑下该算法的收敛性能和收敛速度, ...
二阶离散多智能体系统的二层邻居一致性算法研究成果
具有状态合法性验证的区块链一致性算法研究
多智能体一致性算法的仿真实验源程序,仅供研究此方向的同行研究
文档中包含一个simulink仿真模型和S函数代码文件,在matlab中设置好路径,就可以成功仿真
基于多智能体系统 一致性算法 电力系统分布式经济调度策略 关键词:一致性算法 多智能体 分布式调度 ...测试算例是一个10机19负荷系统,系统数据来源可靠,代码运行稳定迅速,是研究一致性算法以及分布式优化的必备
MATLAB代码:基于多智能体系统一致性算法的电力系统分布式经济调度策略 关键词:一致性算法 多智能体 ...测试算例是一个10机19负荷系统,系统数据来源可靠,代码运行稳定迅速,是研究一致性算法以及分布式优化的必备
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
针对基于可见光的人脸图像的识别容易受光照和表情变化的影响,人脸的表情变化仅限于局部等问题,以及图像的相位一致性特征不受图像的亮度或对比度影响的特点,提出了一种基于分块相位一致性的人脸识别算法。该算法用...
#资源达人分享计划#
为了提高一致性滤波精度,克服传感器网络的通信带宽和能量限制,基于二阶分布式一致性算法,提出了离散的一致性滤波算法,并基于量化通信,在改进概率量化的基础上,提出了量化一致性滤波算法。 分析了量化、非量化...
为了提高分布式传感网络的估计精度,提出了一种新的自适应一致性算法。该算法在每次迭代时只需部分节点工作,即进行目标状态的监测。通过节点之间二进制信息的交换来调整每次迭代时的一致性权值,使得每次迭代时工作...
研究了一致性规划任务信念状态空间的表示方法。针对一致性有限域表示(CPT-FDR)算法在任务生成阶段选择状态变量的不足,提出了一种基于初始状态中文字相容互斥的状态变量选择算法——MECV算法。CPT-FDR未考虑初始...
面向车联网异构节点的区块链高效一致性共识算法研究.docx