`
kirayuan
  • 浏览: 39750 次
文章分类
社区版块
存档分类
最新评论

一致性算法研究

 
阅读更多

一、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

    分布式一致性算法在计算机科学、尤其是分布式计算领域有悠久的研究历史,并且近年来在自动控制、信号处理等领域也引起了广泛的关注。 为了保证智能体能够收敛到相同的值,它们之间需要进行信息交换,这包括位置、...

    具有不确定性多智能体系统的一致性算法研究.pdf

    具有不确定性多智能体系统的一致性算法研究 本文研究了具有不确定性的多智能体系统的一致性问题,并提出了一个鲁棒的协同控制算法。该算法包括协同律和自适应律,能够处理局部不确定性和网络不确定性。协同律利用...

    具有状态合法性验证的区块链一致性算法研究.pdf

    区块链一致性算法研究 本文研究了一种新的区块链一致性算法,该算法解决了传统拜占庭一致性算法在去中心化环境中的合法性验证问题。该算法引入两阶段提交和法定人数投票的过程,利用区块链协议的分布式总账特点,...

    matlab 一致性算法

    总之,“matlab 一致性算法”是一个涉及多智能体系统协调的重要主题,对于学习和研究分布式控制、协同计算等领域有着广泛的应用价值。通过MATLAB进行实践,可以直观地理解和掌握一致性算法的原理和实现。

    分布式一致性算法Yac.pdf

    因此,研究者们提出了新的分布式一致性算法Yac来解决这些问题。 #### 2. Yac算法的特点 Yac算法通过引入动态拓扑和有限表决的思想,解决了传统算法中存在的问题: - **动态拓扑**:算法能够根据当前系统的状态动态...

    一致性算法

    这个压缩包包含的“一致性算法”源程序,很可能是为了帮助研究者理解和模拟这类算法的行为。下面我们将深入探讨一致性算法的核心概念、常见类型以及其在多智能体系统中的应用。 一致性算法的目标是解决分布式系统中...

    simulink的S函数实现多智能体一致性算法的仿真

    在本文中,我们将深入探讨如何使用Simulink的S函数实现多智能体一致性算法的仿真。首先,让我们了解几个核心概念: 1. **Simulink**:Simulink是MATLAB环境下的一个图形化建模工具,用于动态系统建模、仿真和分析。...

    consensus.rar_consensus_consensus算法_matlab_一致性_一致性算法

    总的来说,这个压缩包提供了一个研究和实践一致性算法的良好起点,不仅有实际的代码实现,还有辅助学习资料,对于想要了解或提升一致性算法应用能力的MATLAB用户来说,是一份宝贵的资源。通过深入学习和实践,用户...

    离散二层邻居一致性算法.zip_一致性算法_多智能体_多智能体系统_智能体一致性_离散多智能体

    二阶离散多智能体系统的二层邻居一致性算法研究成果

    具有状态合法性验证的区块链一致性算法研究

    具有状态合法性验证的区块链一致性算法研究

    改进概率量化分布式一致性算法.pdf

    为了提高分布式一致性算法在量化通信下的收敛精度,研究人员提出了概率量化分布式一致性算法。 概率量化分布式一致性算法是一种通过概率方法处理量化问题的算法,它允许节点根据自身状态和邻接节点的概率量化信息...

    分布式一致性系统算法

    #### 四、分布式一致性算法 为了实现在分布式环境下的数据一致性,研究者们提出了多种算法和技术。 - **两阶段提交(2PC)** - **准备阶段**:事务协调者向所有参与者发送`Prepare`消息,参与者执行事务但暂不...

    consensus_based_auction_algothm_auction算法_任务分配_一致性算法_CBAA_竞拍算法_源

    一致性算法在这里的作用是确保所有智能体最终达成一致的决策,即使在存在网络延迟或消息丢失的情况下。通过设计适当的一致性协议,如Gossip协议或Paxos协议,智能体能够逐渐收敛到相同的出价,从而避免死锁或无解的...

    分布式一致性算法的研究及应用.pdf

    综上所述,分布式一致性算法是分布式系统设计中不可或缺的一部分,而Paxos算法则在其中扮演了重要角色。尽管Paxos算法有着复杂的逻辑和操作过程,但它的稳定性和可靠性使其成为解决分布式系统数据一致性问题的首选...

    面向分布式融合估计的快速一致性算法.pdf

    分布式系统是一种由多个独立的计算节点构成的计算系统,这些节点通过网络互连,协同工作以完成复杂的计算任务...在实际应用中,分布式融合估计和快速一致性算法的研究对于提升分布式系统的性能和可靠性具有重要的意义。

    基于一致性算法的孤岛型微电网群实时协同功率分配

    MATLAB作为一种强大的数学建模和仿真工具,被广泛应用于微电网的研究中,可以用于构建一致性算法模型并进行动态模拟。 在孤岛型微电网群中,每个微电网都可以看作一个节点,节点间通过通信网络交换功率分配信息。...

    9794201mang-watermarking.rar_medicinets2_一致性算法_一致性验证_算法一致性_鲁棒性

    在IT领域,尤其是在计算机视觉和图像处理中,一致性算法、一致性验证和算法一致性是至关重要的概念,它们直接关系到图像处理结果的准确性和可靠性。鲁棒性则是衡量一个算法在面对各种异常或噪声时表现稳定性的关键...

Global site tag (gtag.js) - Google Analytics