论文-分布式-共识,事务以及两阶段提交的历史描述

这篇具有很好参考价值的文章主要介绍了论文-分布式-共识,事务以及两阶段提交的历史描述。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 这是一段关于一致性,事务以及两阶段提交的历史的描述
  • 阅读关于一致性的文献可能会有些困难,因为:
    • 各种用语在不断的演化着(比如一致性<consensus>最初叫做协商<agreement>);
    • 各种研究成果并不是以一种逻辑性的顺序产生出来;
    • 同时描述整个分布式算法的框架与这些研究工作又是平行地演化着;
    • 此外除了Lynch的《分布式算法》外,很少有书籍涉及到这个主题
  • 下面涉及的这些论文不是按照它们的发表顺序来进行介绍,而是尽量以最容易理解的方式来组织
  • 所知道的第一个一致性问题实例应该是Lamport的“Time, Clocks and the Ordering of Events in a Distributed System” (1978),尽管它并没有明确的提出一致性(consensus)或者协商(agreement)的概念
  • 在这篇论文里,Lamport讨论了消息如何在有限的时间内在不同处理器之间传输,同时还利用爱因斯坦的狭义相对论进行了有趣的比喻
  • 早在1978年,Lamport就采用时空图给出了一个完整的全方位的分析
  • 关键问题在于,在一个分布式系统中,你无法判断事件A是否发生在事件B之前,除非A和B存在某种依赖关系
  • 每个观察者都可能看到不同的事件发生序列,除非这些事件相互之间存在依赖关系,即分布式系统中的事件仅仅是部分有序的
  • Lamport定义了一个称为”发生在前”的关系和操作符,然后又给出了一个算法,用来确定分布式系统中的事件的全序关系,这样所有的进程就可以看到与其他进程一样的事件排序
  • 同时,Lamport还提出了分布式状态机的概念:
    • 让一组确定性状态机从相同的初始状态开始,之后保证它们以相同的顺序处理相同的消息
    • 这样就可以保证每个状态机都是其他状态机的一个副本
    • 关键的问题就是让每个状态机在“哪个消息是下一个需要处理的消息”这个问题上达成一致,这就是一个一致性问题
    • 这就是一个创建事件排列的算法所需要做的,提供一个关于消息传输顺序的统一约定
    • 然而,这个系统并不是容错的,如果一个进程出错,其他进程将无限等待下去直到它恢复
  • 大概在这篇论文发表的同一时间,JimGray在“Notes on Database Operating Systems” (1979)中描述了两阶段提交(2PC)
  • 不幸的是,如果事务管理器在某个错误的时间点失败的话,2PC就会被阻塞
  • Dale Skeen在“NonBlocking Commit Protocols” (1981)中指出,对于一个分布式系统,需要3阶段的提交算法来避免2PC中的阻塞问题
  • 问题关键在于找到一个好的3PC算法,这已花费了将近25年
  • Fischer, Lynch 和 Paterson在“Impossibility of distributed consensus with one faulty process” (1985)中指出对于一个异步系统来说即使只有一个进程出错,分布式一致性也是不可能达到的,这就是著名的FLP结论
  • 直到此时,consensus才成为“让一系列处理器在一个value上达成共识的”这一问题的叫法
  • 在一个具有完美网络(所有的消息都会被传输,按序到达,不会重复)的异步系统(处理器以任意的速率运行,处理器间的消息传输可能花费任意时长)中,只要有一个出错进程(即使只有一次故障)分布式一致性就是不可能的
  • 问题的核心在于,你无法区分一个进程到底是终止了还是正在以极低的速度执行,这使得在异步系统中的错误处理几乎是不可能的
  • 此外这篇论文的重要性还在于它展示了如何证明某些事情是不可能的:首先证明解决该问题的算法都必须满足一些属性,然后证明满足这些属性是不可能的,比如通过反证法证明(这种方法曾经被图灵用于停机问题的证明中)
  • 此时,人们意识到一个分布式算法具有两个属性:安全性(safety)和活性(liveness)
  • 安全性意味着坏的事情不会发生,而活性意味着某些好的事情最终一定会发生
  • 2PC作为一个一致性算法,用来保证所有的进程在“事务要么提交要么失败退出”上达成一致
  • 2PC是安全的,不会有坏的数据被写入到数据库,但是它的活性并不好:如果事务管理器在一个错误的点上失败,那么系统会阻塞
  • 也是在此时,人们意识到可以将一个分布式系统分为同步的(进程以已知的速率运行,消息会在限制的时间内传输)和异步的(进程以未知的任意的速率运行,消息的传输时间没有上界)
  • 异步与同步相比,是一种更通用的情况
  • 一个适用于异步系统的算法,也能被用于同步系统,但是反过来并不成立
  • 你可以将同步系统看做是异步系统的一个特殊情况,只是消息传输时间恰好有个上界
  • 在FLP之前,还有这样一篇论文“The Byzantine Generals Problem” (1982)
  • 在这种形式的一致性问题中,进程还可能会说谎,而且它们还会尽力地去欺骗其他进程
  • 这个问题看起来比FLP更难,但是对于同步的情况它确实存在一个解(尽管当这篇论文发表的时候,同步和异步系统的区分还没有明确提出)
  • 但是这个解代价很高,需要大量多轮的消息传递
  • 这个问题最初来源于航天工业:如果飞机上的传感器给出错误的信息会怎么样呢?(很明显,这个系统被认为是同步的)
  • 在1986年,分布式系统领域关注一致性和事务的人们聚在了一起
  • 在那个时候,最好的一致性算法就是Byzantine Generals,但是这个算法代价太高而无法用于事务处理
  • 关于这场会议JimGray写了一篇文章“A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem.” (1987),这篇论文的导引里有如下的语句:
  • “在这次会议之前,人们普遍认为分布式系统中的事务提交问题是拜占庭将军问题的一个退化版本;或许这次会议的最大意义在于指出二者很少有共同点”
  • 最终,分布式事务被认为是一个新的一致性问题,称为uniform consensus (参见“Uniform consensus is harder than consensus” (2000))
  • 在uniform consensus中,所有的进程都必须在一个value上达成一致,即使是那些出错的进程
  • 一个事务当且仅当所有的RM都准备好提交时才会被提交
  • 而大多数的一致性问题只关注那些没有出错的进程可以达到一致
  • 因此,uniform consensus比普通的一致性问题要难
  • 最终Lamport在“The Part-Time Parliament” (submitted in 1990, published 1998)中提出了Paxos一致性算法,不幸的是采用希腊民主议会的那个比喻很明显失败了,因为人们觉得这篇论文太难理解了
  • 所以这篇论文就被不幸的忽略了,直到Butler Lampson在“How to Build a Highly Availability System using Consensus” (1996)中重新提到这个算法
  • 这篇论文对如何构建容错系统和Paxos进行了很好的介绍
  • 后来Lamport又发表了“Paxos Made Simple (2001)
  • Paxos的核心是:给定固定数目的进程,任何一个多数者集合与其他的多数者集合必然至少存在一个公共元素
  • 比如给定三个元素A,B和C
  • 那么可能的多数者集合是AB, AC, 或者 BC
  • 当一个决定由其中一个多数者集合比如AB通过时,那么在以后的任何时刻其他的多数者集合中至少有一个元素能够记住之前的多数者集合做出的决定
  • 比如对于多数者集合AB,那么A,B会记住决定,对于AC,A会记得,对于BC,B还记得
  • Paxos可以容忍消息的丢失,延迟,重传和乱序
  • 只要存在一个leader可以跟进程中的一个多数者集合会话两次,就能达到一致性
  • 任何进程,包括leader在内,都可以失败或重启,实际上所有的进程可以在同一时间失败掉,而算法仍然是安全的
  • 同一时间,可能有不止一个leader
  • Paxos是一个异步算法,没有显式的超时设置
  • 然而只有当系统表现出同步的方式时,它才能达到一致性
  • 比如消息要在一定的时间内传输
  • 根据FLP结论,存在一种病态的情况,Paxos在这种情况下无法达到一致性,但是在实际中避免出现这种情况相对容易些
  • 将一个系统简单的划分为同步异步有些宽泛
  • Dwork, Lynch 和 Stockmeyer在“Consensus in the presence of partial synchrony” (1988)中定义了部分同步系统
  • 存在两种类型的部分同步系统:其中一种情况是进程以给定边界内的速率运行,消息传输时间是有界的,但是边界的实际取值事先无法得知;
  • 另一种情况是处理速度的边界以及消息传输上界事先已知,但是只在未来的某个未知时间才开始成立
  • 对于现实世界来说,部分同步模型是一个比同步异步模型更好的模型
  • 大部分时间网络行为都是以一种可预测的方式发生,但是可能突然会变得很疯狂
  • 在“Consensus on Transaction Commit” (2005)中,Lamport和Jim Gray将Paxos应用在分布式事务提交问题中
  • 他们使用Paxos来对2PC中的事务管理器进行高效的备份
  • 对于事务中涉及的每个RM使用一个Paxos的实例来决定该RM(resource manager,实际上就是该事务涉及的进程)是否提交该事务
  • 在这里面,为每个RM使用一个Paxos实例看起来很昂贵,但是实际证明情况并不是这样
  • 对于没有错误发生的情况下,Paxos提交可以通过两个阶段完成,与2PC相比尽管有更多的消息需要传输但具有相同的消息延迟
  • 只有当错误发生时,才需要第3个阶段
  • 给定2n+1个事务管理器,当错误副本数小于等于n时,Paxos提交都可以完成
  • Paxos提交并没有使用Paxos算法来直接解决事务提交问题,它并不是用来解决uniform consensus,而是用来让系统容错
  • 有一种观点认为分布式事务不应该被使用,因为2PC是阻塞失效的
  • Paxos提交就是用来解决阻塞的问题
  • 有一些关于CAP(Consistency(一致性), Availability(可用性) 和 Partition tolerance(分区容错性))猜想的讨论
  • 这个猜想指出,在分布式系统中,无法同时满足上述三个属性(即在分布式系统的设计中,无法同时满足对数据的实时一致性要求、完全无故障的可用性以及分区容错性)
  • 我们可以将Consistency等同于consensus(共识)来检验下CAP
  • 根据FLP结论,在一个异步系统中,当出现一个出错进程时,无法达到consensus
  • 所以对于一个异步系统来说,我们无法同时得到Consistency和Availability(在网络分区(网络故障)的情况下,系统需要在可用性和一致性之间作出选择,即是选择保持可用性而降低一致性,还是放弃一些可用性以维持一致性)
  • 假设现在有一个包含三个节点A,B和C的Paxos系统
  • 如果有2个节点在工作,我们就能达到一致性,即我们可以得到consistency 和 availability
  • 现在如果C被分割,而且有查询请求,它就会因无法与其他节点通信而无法响应{!这样就不具有可用性了}
  • 它无法判断到底是自己被分割了,还是其他两个节点down掉了,又或者是网速很慢
  • 其他两个节点可以正常进行,因为它们相互可以通信并形成一个多数者集合
  • 所以对于CAP猜想,Paxos无法处理网络分割,因为C无法对查询做出响应
  • 然而在工程上,我们可以绕过这个问题
  • 假设我们处在一个数据中心内部,可以使用两套独立网络(Paxos并不介意出现重复消息)
  • 如果我们是在因特网上,我们可以让客户端查询所有的节点A,B,C
  • 如果C被分割了,它可以查询A或者B,除非它跟C一样被分割了
  • 对于一个同步网络,如果C被分割了,如果它在一定的时间内收不到消息就可以知道自己被分割了,因此能够向客户端声明自己down掉了

文章来源地址https://www.toymoban.com/news/detail-732857.html

到了这里,关于论文-分布式-共识,事务以及两阶段提交的历史描述的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 分布式共识 - Raft 算法

    本文由 SnailClimbopen in new window 和 Xieqijunopen in new window 共同完成。 Raft协议由Diego Ongaro和John Ousterhout(斯坦福大学)开发,Diego于2014年获得了博士学位。Raft的设计是为了更好地理解如何实现一致性,考虑到它的前身Paxos算法,由Lesli Lamport开发,非常难以理解和实现。因此,Di

    2024年02月20日
    浏览(37)
  • 分布式状态机共识协议 Copilot

      目录 前言 定义 slowdown 为什么现有的共识协议无法容忍 slowdown Copilot 如何处理 slowdown 设计 模型  排序 Client 同时发送指令至 pilot 与 copilot Pilot 提议指令与其初始依赖 节点回复 FastAccept Pilot 尝试通过 fast path 来 commit 该指令 Pilot 在 Accept 阶段最终确定依赖  执行 Copilot 最终合

    2024年02月09日
    浏览(42)
  • 【分布式共识算法】Basic Paxos 算法

    basic paxos算法:描述的是多个节点就某个值达成共识。 muti-paxos 算法:描述的是执行多个basic paxos实例,就一系列值达成共识。 共识其实,比如当多个客户端请求服务器,修改同一个值X 多个阶段达成共识。 角色:提议者、接受者、学习者。 提议者 :说白了就是提出一个值,

    2024年02月12日
    浏览(28)
  • 分布式系统共识机制:一致性算法设计思想

    这次以一个宏观的角度去总结 自己学习过的一致性算法。一致性算法的目标就是让分布式系统里的大部分节点 保持数据一致。 区块链中的共识算法,pow、pos这类就属于这个范围,但他们仅仅是在区块链领域内应用的,下面介绍一致性算法是在分布式系统中 应用广泛的,当然

    2023年04月16日
    浏览(50)
  • 分布式:一文吃透分布式事务和seata事务

    什么是事务 事务是并发控制的单位,是用户定义的一个操作序列。 事务特性 原子性(Atomicity): 事务是数据库的逻辑工作单位,事务中包括的诸操作要么全做,要么全不做。 一致性(Consistency): 事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。一致性

    2024年02月07日
    浏览(57)
  • 【分布式事务】Seata 开源的分布式事务解决方案

    Seata 是一款开源的分布式事务解决方案,致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式,为用户打造一站式的分布式解决方案。 阿里巴巴作为国内最早一批进行应用分布式(微服务化)改造的企业,很早就遇到微服务架构下

    2024年02月02日
    浏览(51)
  • 【分布式】分布式事务:2PC

    分布式事务的问题可以分为两部分: 并发控制 concurrency control 原子提交 atomic commit 分布式事务问题的产生场景:一份数据被分片存在多台服务器上,那么每次事务处理都涉及到了多台机器。 可序列化(并发控制): 定义了事务执行的正确性 真正地并行执行事务,获得真正的

    2024年02月09日
    浏览(45)
  • 不懂分布式系统的核心问题:一致性与共识,还想入门区块链?挖矿?

    CAP原理 ===== CAP原理:分布式计算系统不可能同时确保以下三个特性: 一致性(consistency) 可用性(availability) 分区容忍性(partition) **(1)分区容忍性:**网络可能发生分区,即节点之间的通信不可保障。 大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区(

    2024年04月12日
    浏览(45)
  • Redis分布式锁和分布式事务

    Redis分布式锁和分布式事务 一、Redis分布式锁 1.1 watch和事务实现分布式锁 原理是通过watch来观察一个变量,一个线程在操作的时候,其他线程会操作失败,相当于乐观锁。 1.2 setnx实现分布式锁 原理是通过setnx设置一个变量,设置成功的线程抢到锁,执行相关的业务,执行完毕

    2024年02月09日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包