两段事务提交2PC的缺点和解决之道 - DBMS Musings

19-01-26 banq
                   

现在是时候抛弃2PC了,两阶段提交协议(2PC)已经在企业软件系统中使用了三十多年。它是一种非常有影响力的协议,用于确保访问多个分区或分片中的数据的事务的原子性和持久性。它无处不在 - 无论是在旧的“古老的”分布式系统,数据库系统和文件系统(如Oracle,IBM DB2,PostgreSQL和Microsoft TxF(事务性NTFS))还是在较年轻的“千禧”系统(如MariaDB)中, TokuDB,VoltDB,Cloud Spanner,Apache Flink,Apache Kafka和Azure SQL数据库。

如果您的系统支持跨分片/分区/数据库的ACID事务,那么它很可能会在表面下运行2PC(或其某些变体)。

在这篇文章中,我们将首先描述2PC:它是如何工作的以及它解决了什么问题。然后,我们将展示2PC的一些主要问题以及现代系统如何试图解决这些问题。不幸的是,这些尝试的解决方案导致出现其他问题。最后,我将说明下一代分布式系统应该避免使用2PC,以及如何实现这一点。

2PC协议概述

2PC有很多变种,但基本协议的工作原理如下:

背景假设:事务所需的工作已经划分为存储该事务访问的数据的所有分片/分区(banq注:JTA中是不同的XA数据源,也就是不同数据库为不同分片或分区)。我们将在每个分片中执行的工作称为由该工作程序为该分片执行的工作(banq注:操作某个数据源的程序称为分片工作者)。每个分片工作者都能够独立于彼此开始处理指定事务的职责。2PC协议在事务处理结束时启动,当事务准备好“提交”时,,它由某个协调器者(可能是参与该事务的工作者之一)启动提交。

2PC的两个阶段:

  • 阶段1:协调者询问每个分片工作者是否已成功完成对其事务的职责并准备提交。每个分片工作者都回答“是”或“否”。
  • 阶段2:协调者计算所有响应,如果每个分片工作者都回答“是”,那么事务将提交。否则,它将中止。协调器向每个具有最终提交决策的分片工作者发送消息并接收确认。

此机制确保事务的原子性属性:整个事务将要么全部写入系统的最终状态中,或者全部不写入到系统的最终状态中。如果即使只有一个分片工作无法提交,那么整个事务将被中止。换句话说:每个工作者对交易都有“否决权”。

它还确保了事务的持久性。每个工作者确保在第1阶段响应“是”之前已将所有事务持久写入到存储。这使协调器可以自由地对事务做出最终决定,而无需关心工作者在投票'是'之后可能会失败的事实。[在这篇文章中,当使用术语“持久写入”时,我们有目的地含糊不清 - 这个术语可以指写入本地非易失性存储,或者将写入复制到足够的位置以便将其视为“耐用持久”。]

除了持久地写入事务直接需要的写入之外,协议本身还需要额外的写入,在继续写入之前必须使其持久化。例如,一名工作者拥有否决权,直到在第一阶段投票“是”为止这段时间都是这样。在此之后,它不能改变其投票权。但如果它在投票'是'后立即崩溃怎么办?当它恢复时,它可能不知道它投了“是”,仍然认为它拥有否决权并继续并中止交易。为了防止这种情况,它必须在将“是”投票发回协调器之前进行投票持久化。[除了这个例子,在标准的2PC中,还有另外两个写入在发送作为协议一部分的消息之前变得持久。]

2PC的问题

2PC存在两个主要问题。第一个是众所周知的,并在每个提出2PC的著名教科书中进行了讨论。第二个不太知名,但仍然是一个主要问题。

第一个问题是众所周知的,称为“阻塞问题”。当每个工作者都投了'是'时会发生这种情况,但协调器在将最终决定的消息发送给至少一个工人之前自己发生了失败(banq注:协调器本身自己崩溃了,是存在单点风险的)。

通过投票'是',每个工作者已经没有了否决事务的权力。但是,协调器仍有绝对权力来决定交易的最终状态,如果协调器在向至少一名工人发送最终决定的消息之前自己失败了,那么工作者们就无法再聚在一起做出决定 :他们不能中止,因为协调器可能会在失败之前决定提交;并且他们也无法确认提交,因为协调器可能决定在失败之前中止。从而,他们必须堵塞等待:等到协调器恢复(banq注:等领导身体恢复健康了),这样才能让它继续实现最终的决定。与此同时,他们无法处理与停滞事务冲突的事务,因为该事务的写入的最终结果尚未确定。

阻塞问题有两类解决方法。第一类解决方法是修改核心协议以消除阻塞问题。不幸的是,这些修改降低了性能 - 通常通过添加额外的一轮通信 - 因此很少在实践中使用。第二类保持协议的合理性,但降低了协调器失败类型的可能性,而不是导致阻塞程序 - 例如,通过在副本共识协议上运行2PC并确保协议的重要状态被复制。不幸的是,这些解决方案再一次降低了性能,因为协议要求这些副本共识轮次顺序发生,因此它们可能会给协议增加显着的延迟。(banq注:TCC补偿式事务是在两个阶段之间停止堵塞等待,第一个阶段结束各个工作者就关闭锁,如果在第二个阶段提交确认再写入,否则就进行补偿性的回滚,这实际引入了对业务工作流程的依赖,通常比如发送邮件等动作是无法补偿)。

第二个问题是鲜为人知的问题,我称之为“cloggage连锁堵塞问题”。在处理事务之后发生2PC,因此必然将事务的等待时间增加等于运行协议所花费的时间。单独的延迟增加对于许多应用程序来说已经是一个问题,但是一个潜在的更大问题是工作节点直到第二阶段中途才知道事务的最终结果。在他们知道最终结果之前,他们必须为可能中止的可能性做好准备,因此他们通常会阻止冲突的交易在确定交易将提交之前取得进展。这些阻塞的事务反过来阻止其他事务运行,依此类推,直到2PC完成并且所有被阻止的事务都可以恢复。

总结我们上面讨论的问题:2PC在四个方面使系统中毒:延迟(协议的时间加上冲突事务的停顿时间),吞吐量(因为它需要防止在协议期间运行其他冲突的事务,banq注:只能让事务串行执行,区块链其实是一个事务链),可扩展性(更大)在系统中,事务变得多分区并且必须支付2PC的吞吐量和延迟成本以及可用性(我们上面讨论的阻塞问题)的可能性越大。

 没有人喜欢2PC,但几十年来,人们都认为它是一种必要的邪恶。

是时候继续前进了

三十多年来,我们一直坚持在分片系统中进行两阶段提交。人们已经意识到它引入的性能,可伸缩性和可用性问题,但仍然继续,没有明显更好的替代方案。

事实是,如果我们只是以不同的方式构建我们的系统,那么2PC的需求就会消失。已经有一些尝试来实现这一目标 - 无论是在学术界(如SIGMOD 2016论文)和行业。然而,这些尝试通常通过首先避免多分片事务来工作,例如通过在事务之前重新分区数据使得它不再是多分片的。不幸的是,这种重新分区以其他方式降低了系统的性能。

我所要求的是我们构建分布式系统的方式的更深层次的变化。我坚持认为系统应该仍然能够处理多分片事务 - 具有所有ACID保证和所需的内容 - 例如原子性和持久性 - 但是具有更简单和更快的提交协议。

这一切都归结为我们的系统中存在数十年的基本假设:交易可能随时以任何理由中止。

即使我在相同的初始系统状态下运行相同的事务...如果我在下午2:00运行它可能会提交,但在3:00它可能会中止。

大多数架构师认为我们需要这个假设的原因有几个:首先,机器可能在任何时候都失败 - 包括在事务过程中;在恢复时,通常不可能在故障之前重新创建易失性存储器中的该事务的所有状态。结果,在失败之前从事务中断的地方重新恢复似乎是不可能的。因此,系统将在发生故障时中止正在进行的所有事务。由于任何时候都可能发生故障,这意味着事务可能随时中止。(banq注:中止其实对应CAP定理中的分区,发生故障意味着分区)

其次,大多数并发控制协议都需要能够随时中止事务。乐观协议在处理事务后执行“验证”阶段。如果验证失败,则事务将中止。悲观协议通常使用锁来防止并发异常。这种锁的使用可能导致死锁,这可以通过中止(至少)一个死锁事务来解决。由于可以随时发现死锁,因此事务需要保留随时中止的能力。

如果仔细查看两阶段提交协议,您将看到“中止事务”的这种任意可能性是协议中复杂性和延迟的主要来源。

工作者不能轻易地告诉对方他们是否会提交,因为他们可能在此之后(在事务提交之前)失败并且需要在恢复期间中止此事务。因此,他们必须等到事务处理结束(当所有重要状态变为持久时)并继续进行必要的两个阶段:在第一阶段,每个工作者公开放弃其对中止事务的控制,然后才能发生第二阶段,作出最终决定并才能予以传播。

在我看来,我们需要从工作者移除他们的否决权,重新架构这些系统,系统无法在执行期间随时中止事务,只允许事务中的逻辑导致事务中止。如果理论上可以在给定数据库的当前状态的情况下提交事务,则无论发生何种类型的故障,该事务都必须提交。此外,相对于可能影响事务的最终提交/中止状态的其他并发运行事务,不得存在竞争条件。

”消除事务的任意中止“灵活性听起来很难。我们将很快讨论如何实现这一目标。但首先让我们观察一下如果事务没有中止退出事务的灵活性,提交协议会如何变化。

当事务不能随意中止时,提交协议是什么样的

我们来看两个例子:

在第一个示例中,假设存储变量X的值的分片工作者被分配了一个事务中的某个任务:将X的值更改为42.假设(现在)没有定义完整性约束或触发器在X上(这可能会阻止系统将X设置为42)。在这种情况下,该工作者永远不会被赋予能够中止交易的权力。无论发生什么,该工作者必须将X更改为42,如果该工作者失败,则必须在器恢复后还是将X更改为42。由于它永远没有任何中止的能力,因此在提交协议期间无需对该工作者检查它是否会提交?

在第二个示例中,假设存储变量Y和Z的值的分片工作者被分配了两个事务任务:从前一个Y值中减去1并将Z设置为Y的新值。此外,假设Y上存在完整性约束,表明Y永远不会低于0(例如,如果它代表零售应用程序中项目的库存)。因此,此工作者必须运行以下代码的等效代码:

           IF(Y> 0)
              从Y减去1
           else
               中止交易
           Z = Y.

必须赋予此工作者中止事务的权力,因为应用程序的逻辑需要这样做。但是,这种力量是有限的。只有当Y的初始值为0时,该工作者才能中止该事务。否则,它别无选择,只能提交。因此,它不必等到它完成事务代码之后才知道它是否会提交。相反:只要它完成了事务中第一行代码的执行,它就已经知道了它的最终提交/中止决定。这意味着提交协议将能够相对于2PC更早地启动。

现在让我们将这两个例子组合成一个例子,其中一个事务由两个工作者执行 - 其中一个正在完成第一个例子中描述的工作,另一个正在完成第二个例子中描述的工作。由于我们保证原子性,第一个工作者不能简单地将X设置为42.相反,它自己的工作也必须依赖于Y的值。实际上,它的事务代码变为:

 temp = Do_Remote_Read(Y)
      if(temp> 0)
         X = 42

请注意,如果第一个worker的代码是以这种方式编写的,那么另一个工作者的代码可以简化为:

     IF(Y> 0)
        从Y减去1
       Z = Y.

通过以这种方式编写事务代码,我们从两个工作者中删除了显式的中止逻辑,相反,两个工作者都有if语句来检查会导致原始事务中止的约束。如果原始事务中止,两个工人最终都无所作为。否则,两个工作者都会根据事务逻辑的需要更改其本地状态的值。

此时需要注意的重要一点是,在上面的代码中完全消除了对提交协议的需求。由于应用程序代码在给定数据状态下定义的条件逻辑以外的任何原因,系统不允许中止事务。并且所有工作者都在这个相同的条件逻辑上调整他们的写入,这样他们就可以独立地决定在由于当前系统状态而无法完成事务的情况下“什么也不做”。因此,已经消除了事务中止的所有可能性,并且在事务处理结束时不需要任何类型的分布式协议来做出关于事务的组合的最终决定。2PC的所有问题都已消除。没有阻塞问题,因为没有协调器。并且没有连锁阻塞问题,因为所有必要的检查都与事务处理重叠,而不是在完成之后。

此外,只要不允许系统因基于输入数据状态的条件应用程序逻辑之外的任何原因而中止事务,总是可以像上面那样重写任何事务以替换代码中的中止逻辑。 if语句有条件地检查中止条件。此外,可以在不实际重写应用程序代码的情况下实现此目的。[有关如何执行此操作的详细信息超出了本文的范围,但总结为高级别:当分片完成任何可能导致中止的条件逻辑时,分片可以设置特殊的系统拥有的布尔标志,这些是从其他分片远程读取的布尔标志。]

(banq注:其实条件检查也是第一段,检查完成后提交也是第二段,两段提交实际是在分布式系统中进行if检查,然后在第二阶段决定是否提交!)

实质上:在事务处理系统中有两种类型的中止:(1)由数据状态引起的中止和(2)由系统本身引起的中止(例如,故障或死锁)。如上所述,类别(1)总是可以根据数据的条件逻辑来编写。因此,如果您可以消除类别(2)中止,则可以消除了第二段的提交协议。

所以现在,我们所要做的就是解释如何消除类别(2)中止。

消除系统引起的中止

我花了将近十年的时间来设计不允许系统导致中止的系统。此类系统的示例是CalvinCalvinFSOrthrusPVW以及懒惰处理交易系统。这一特性的推动力来自于这些项目中的第一个--- Calvin ---因为它是一个确定性的数据库系统。确定性数据库保证在给定一组定义的输入请求的情况下,数据库中只有一个可能的最终数据状态。因此,可以将相同的输入发送到系统的两个不同的副本,并确保副本将独立地处理该输入并最终处于相同的最终状态,而没有任何分歧的可能性。

系统引发的中止,例如系统故障或并发控制竞争条件,从根本上说是不确定性事件。

一个副本很可能会失败或进入竞争状态,而另一个副本则不会。如果允许这些非确定性事件导致事务中止,则一个副本可以中止事务而另一个事务将提交 - 这是对确定性保证的基本违反。

因此,我们必须以失败和竞争条件不能导致交易中止的方式设计Calvin 。对于并发控制,Calvin使用了具有避免死锁技术的悲观锁,该技术确保系统永远不会陷入由于死锁而必须中止事务的情况。面对系统故障,Calvin没有完全从中断的地方获得事务(因为在失败期间失去了易失性内存)。尽管如此,它还是能够的使该事务的处理完成而不必中止。它通过从相同的原始输入重新启动事务来完成此操作。

这些解决方案 (死锁避免或故障时重启事务)都不限于在确定性数据库系统中使用。[事务重启在非确定性系统中变得有点棘手,如果与失败期间丢失的事务相关联的某些易失性状态被其他未发生故障的计算机观察到。但是有一些简单的方法来解决这个问题,这个问题超出了这篇文章的范围。]实际上,我上面链接的其他一些系统都是非确定性系统。一旦我们意识到消除系统级中止所带来的强大功能,我们就将这个功能构建到我们在Calvin项目之后构建的每个系统中 - 甚至是非确定性系统。

结论

我认为系统架构师在向前发展的分布式分片系统中继续使用2PC几乎没有什么好处。我认为,消除系统引起的中止并重写状态引发的中止是更好的新方法。

确定性数据库系统,如Calvin或FaunaDB 无论如何总是去除系统引起的中止,因此通常可以避免2PC,如上所述。但是将这种好处仅限于确定性数据库是一个巨大的浪费。从非确定性系统中删除系统引起的中止并不困难。最近的项目表明,甚至可以在使用除悲观并发控制之外的并发控制技术的系统中消除系统引起的中止。例如,我们上面链接的PVW和惰性事务处理系统都使用多版本并发控制的变体。FaunaDB使用乐观并发控制的变体。

在我看来,继续“由关系统引起的系统中止需求"的过时假设几乎没有理由。在过去,当系统在单台机器上运行时,这种假设是合理的。然而,在现代,许多系统需要扩展到可以彼此独立地失败的多台机器,这些假设需要昂贵的协调和提交协议,例如2PC。

2PC的性能问题一直是非ACID兼容系统兴起的主要推动力,这些系统放弃了重要的保证,以实现更好的可扩展性,可用性和性能。2PC太慢了 - 它增加了所有事务的延迟 - 不仅仅是协议本身的长度,而且还阻止了访问同一组数据的事务同时运行。2PC还限制了可伸缩性(通过降低并发性)和可用性(我们上面讨论的阻塞问题)。前进的方向很明确:我们需要在设计我们的系统时重新考虑过时的假设,并对两阶段提交说“再见”!

 

                   

1
banq
2019-01-26 19:30

关于该文的Hackernews讨论:

https://news.ycombinator.com/item?id=18999520

摘录网友意见:

ww520: 

2PC的替代方案是拥有一个始终向前的补偿事务日志。更新记录(banq注:类似领域事件)在事务日志中。然后将每个更新发送给工作者,他们会看到更新是否应用于他们,并提交与他们自己的数据库相关的更新。没有回滚。可以通过发布补偿事务来否定先前的效果来应用逻辑“回滚”。例如,发行10美元借方的新交易以补偿之前10美元贷方的交易。(banq注:这是借鉴财务借记冲帐的做法,财务上在发生错误时是不能修改,只能新增一笔相反的交易进行冲账,比特币区块链也是借鉴于此)

例如,一个工作者维护数据库Inventory表。另一个工作者维护另外一个数据库Order表。当前端应用程序创建订单时,它会在补偿事务日志中记录事务[(减少库存中的部分),(在订单中创建新记录)]。请注意,这两个更新都在一个事务中。

当Inventory工作程序收到事务时,它会应用与其表相关的更新,即Inventory表,并忽略Order更新。Order工作程序接收相同的事务并应用相关的Order更新,同时忽略事务中的Inventory更新。

在订单被取消的情况下,可以在交易日志中创建[(库存中的增量部分),(在订单中取消的该笔记录)]的补偿交易。工作人员可以接收交易并应用与其相关的更新。

两个工作人员数据库都是分离的,可以按照自己的步调进行工作。它们可以崩溃而不会影响另一个。在一天结束时,事情会得到调和并且是一致的。

该方案的缺点是数据的及时性。一个系统可能会停止或缓慢应用更新并落后于另一个系统。

banq注:这个方案中:始终向前 + 补偿事务日志 这两个非常重要,“始终向前” 就是没有回滚,确保写入正常,如果不正常,重试,保留事务日志,不断重试,直至人工介入纠正原来的错误保证写入成功,因此在写入方面避免竞争和所,无锁的单写方式可以保证写入事务日志正确,一旦更改事件写入了事务日志,就会持久到一个存储文件或数据库,比如Kafka的日志就是天然的事务日志,kafka的消费者在消费失败重启后会自动重试,消息不会丢。这个模式基本是Saga模式。 

还有一种TCC(Try-Confirm-Cancel)其实是JTA 2PC的一种补充,TCC中第二个C如果看成是类似2PC的回滚,那么这还是两段提交,况且TCC中第一个C就是提交的意思;如果将第二个C理解为补偿有些牵强,补偿的意思是不断新增补充,而不是撤销回退原来的动作,补偿本身概念有始终向前的意思,既然有补偿概念,就需要有过去动作的历史记录,没有历史记录你怎么补偿,你如果撤销删除了以前的动作就不是补偿,如同你把财务财务账本上一条记录用涂改液擦除了,那是要犯法的,补偿就是你不能回退擦除以前的记录,只能新增一条记录,来冲抵以前的错误记录。