分布式事务设计-两段式提交（转载）

事务是一个很重要的概念，它必须满足ACID特性，在单机的数据库中，这很容易实现。但在分布式数据库中，各个表分散在各台不同的机器上，如何对这些表实施分布式的事务处理就成为一个比较困难的问题，其中两段式提交就是解决分布式事务的一种方式。

两段式提交设计本身的思路非常的容易理解，步骤如下：

1. 协调员服务器（协调员）发送一条投票请求消息给所有参与这次事务的服务器（参与者）。

2. 当一个参与者收到一条投票请求，它会向协调员发送一条响应请求消息，该响应消息包含了参与者的投票：YES 或者NO。如果参与者的消息的投票是NO，那就意味着由于某些原因，参与者不能参与这次事务，等价于收到了ABORT决定，本次事务的工作到此为止。

3. 协调员收集所有参与者的响应投票，如果所有的响应投票都是YES，那么协调员就会做出决定：COMMIT，并且会把COMMIT消息发送给所有参与者。否则，协调员则会做出决定：ABORT，此时协调员会把ABORT消息发给那些投票为YES的那些参与者（投票为NO的参与者已经单方面ABORT了这次事务，协调员不必再发送消息给这些参与者）。发送完决定后，协调员对于本次事务的工作就此停止了。

4. 投了YES票的参与者等待着来自协调员的决定（COMMIT或者ABORT），然后根据决定做完相应的操作，然后本次事务的工作也就此为止。

步骤1,2属于两段式提交的阶段1，步骤3,4属于两段式提交的阶段2。在整个过程中，参与者会存在一段不确定时间段（从它发送YES的票开始，到它收到COMMIT/ABORT的决定结束），在此时间段内，参与者的进程会被block住，它需要等待接下来的决定。而协调员则不存在任何不确定时间段，它可以继续处理其它的事务请求，发送其它事务的投票请求，在做完COMMIT/ABORT决定之后，它可以马上去干别的事情，无需任何等待。因为协调员的工作不具有原子性，它可以交叉得做任何事。而参与者完成的是事务，具有原子性，它做出承诺后，他必须保持好事务的现场，避免别的事务的交叉感染，从而违反了ACID中的Isolated。

从描述来看非常简单，很容易理解，但是请注意，在整个过程中的任何时间点，都有可能发生的各种各样的故障，有的是链路故障，有的是服务器故障。如果详细考虑这些情况，实现就不是这么简单了。

先考虑第一个问题，在整个执行的过程中，无论是参与者的进程，还是协调者的进程，他们在做下一步的处理前都必须等待消息。但是，消息可能会失败，并不总是能够到达。为了避免无休止的等待消息，因此需要加入Timeout 。当消息超过一定的时间还没到来的时候，我们必须做出处理，这些处理我们称之为Timeout-Action。当服务器或者服务器的进程（无论是协调员还是参与者）从一次失败中恢复过来的时候，我们希望服务器的进程能够尝试着获得一个和其他进程一致的决定。这很好理解，COMMIT/ABORT的决定已经由协调员发出了，那么恢复的参与者进程也希望能够得到这个决定从而参与完成该事务。当然，在参与者从失败中恢复过来的时候，由于其它的一些可能的失败，可能COMMIT/ABORT的决定还未能做出，此时该参与者也需要做出相应的正确处理。因此，服务器的进程必须保存一些信息，比如是一些Log。有了这些Log，才能使得从失败中恢复的进程能够正确恢复事务处理。

 

Timeout-Action

进程需要在3个地方等待消息：在（2），（3），（4）步开始的地方：

在（2）步骤中，参与者进程需要等来来自协调员进程的投票请求。此时如果在等待投票请求时发生了timeout，参与者服务器就可以简单得停止该事务的工作就可以了。

在（3）步骤中，协调员需要等待接受所有参与者回应的YES或NO的投票，在此时，协调员还未达成任何决定，参与者也没有提交任何数据，因此协调员在Timeout发生后，只需要发送ABORT决定给所有的参与者就可以了。

在（4）步骤中，参与者p已经投了YES票，正在等待来自协调员的COMMIT或ABORT命令。在这个时间节点上，p处在不确定时间段。因此此时，p不能在timeout的时候简单得单方面作出决定，他需要向其他服务器做咨询才能知道该如何处理。最简单的终止设计可以是这样的：p依然被block住，一直询问等待协调员，直到p重新建立起和协调员之间的联系。接着，协调员就会告诉p已经作出的决定（协调员没有不确定时间期），然后p就可以接着处理决定。

简单终止协议的缺点是参与者p会被不必要得block住一段时间。比如，假如有2个参与者p和q，协调员把COMMIT/ABORT决定成功发送给q了，但是在它给p发送的决定失败了。的确，p这时是处在不确定时期，但是q已经不在不确定期了，如果p能够和q通信的话，p可以从q那里得到协调员发出的决定，不必一直block等到协调员恢复。

这需要参与者能够互相知道对方，参与者之间可以直接交换信息，不必总是通过协调员的中介。要实现这种自由的信息交换也并不是十分困难，协调员在发送投票请求的时候可以把所有参与者的ID列表附在投票请求消息后面发送给所有的参与者，这样参与者p在收到投票请求后就可以直接和其他所有的参与者进行交流了。这么做也不会带来什么副作用，在收到投票请求之前，参与者之间还是互相不认识，因此在此之前（2），（3）发生的timeout还是可以单方面得中止任务或者停止事务。这个思路就出现另外的一个设计-协同终止设计，设计如下：

当一个参与者p在其不确定时间段内发生了timeout，他会依次向所有其他的进程发送一个询问请求消息，询问做出的决定是什么或者是否能单方面得做出一个决定（因为如果有一个被询问的参与者已经向协调员回复了一个NO的投票，那么询问者自然就可以单方面得做出决定ABORT这次事务，因为只要有一个参与者回复了NO，那么协调员做出的决定肯定是ABORT，无需再向协调员确认了）。在这种场景下，参与者p就被称之为发起人，作出询问回答的服务器进程 q就可以称之为回应人。那么回应人q可能有3种情况：

1. q已经收到了COMMIT/ABORT决定：q只需要把该决定回应给p，然后p就可以自行处理了。

2. q还没进行投票：q此时可以单方面做出决定，因为此时协调员已经发生故障，此时q可以回应ABORT给p，p就可以自己做出处理。

3. q已经回复YES投票给协调员，处在不确定期内，也没有收到来自协调员的决定。此时q也无法给p任何帮助。

根据这个设计，如果p发送询问请求给q，碰巧q处在情况（1）或者（2）时，p马上就可以达成（也就是获得）一个决定而无需任何block。如果p能通讯的其他所有的进程都处在情况（3），那么p也会被block住，直到足够的故障被修复使得p至少能够和一个处在情况（1）或（2）的参与者进程q通讯。需要注意的是询问请求可以发给所有的其他服务器进程，包括协调员进程，这样至少可以确认协调员在没有故障的状态下可以回复投票请求，避免了碰巧所有其他的参与者进程都在不确定期而无法提供帮助回应这样的窘境。

总之，协同终止设计可以降低block的概率，但不能完全排除它。

 

恢复

一个服务器进程p刚刚从一次故障中恢复，我们希望p能够获得一个和其它进程们已经达成的决定一致的决定，如果不能马上恢复这个决定，那么至少在其它的故障被修复后能够恢复这个决定。

当一个服务器进程p把系统恢复到了故障发生时现场保存的状态，我们来进一步考虑一下。如果p是在它发送YES投票到协调员之前就发生故障了，那么该进程就可以单方面的决定取消这次事务，发送NO投票给协调员，不做任何处理。同样，如果p是在已经收到COMMIT/ABORT决定之后或者自己已经作出ABORT的决定之后发生故障了，那么此时p由于已经做出了决定，p就可以作出相应的处理，比如说取消事务操作，或者继续把COMMIT决定的操作执行完毕。在这些情况下，p都能够独立得进行故障恢复。

但是，如果p发生故障时是处在它的不确定期时，那么它就无法在恢复时独立得做决定了，这就是问题的复杂之处。因为它投了YES，在p故障时，可能其他的参与者全部投了YES并且协调者做出了COMMIT的决定。又或者p发生故障时，其他参与者并未全部投票YES，因此协调者作出的是ABORT的决定。此时p无法根据本地信息就能独立得进行恢复，他需要和其他进程进行交流。在这种情况下，p所面临的情况是和time-action的情况（3）是一样的。（设想一下，p设置了一个非常长的timeout 时间，整个故障期间都没有超过timeout的期限）。因此此时p也采用前面提到的终止设计来解决问题。

为了保存故障发生时的状态，每个进程都必须维护一个DT Log（Database Transaction Log）。每个进程只能访问他自己服务器上的DT Log。假设我们采用的是协同终止设计，我们来看看如果管理这些DT log.

 

1. 当协调员发送投票请求之前或之后，它写了一条开始两阶段记录在DT log中。该记录大概类似这样：

{

Type: start-2PC，

time: 2011-10-30 19:20:20，

Participants：

[

    {

        Hostname:participant-1,

        Ip:192.168.0.3

          },

          {

              Hostname:participant-2,

              Ip:192.168.0.4

          },

          {

              Hostname:participant-3,

              Ip:192.168.0.5

          }

       ]

}

 

2. 如果参与者线程发送了YES投票，那么他必须在发送投票之前写这么YES 投票记录在DT Log中，大概类似这样：

{

     Type: VOTE，

     Value：YES，

     time: 2011-10-30 19:20:20，

     Coordinator: 192.168.0.2

     OtherParticipants：

     [

        {

           Hostname:participant-2,

           Ip:192.168.0.4

         },

         {

             Hostname:participant-3,

             Ip:192.168.0.5

          }

      ]

}

  如果参与者发送了NO投票，那么它可以在发送投票之前或之后写一条ABORT ACCEPT记录在DT log中。

 

3. 在协调员发送COMMIT决定给所有参与者进程之前，他写入一条COMMIT DECISION记录。

 

4. 当协调员发送ABORT决定给所有参与者进程之前或之后，它写入一条ABORT DECISION记录

 

5. 参与者服务器进程在收到COMMIT/ABORT决定之后，参与者进程写入一条COMMIT ACCEPT/ABORT ACCPET记录。

 

对上述Log做一些说明，一旦参与者服务器进程在DT日志中写入COMMIT ACCEPT或者ABORT ACCEPT记录后，DM（database manager）就可以执行commit或者abort数据库操作。具体来讲还有很多细节，比如系统中的DT Log可能是DM Log中的一部分，因此DT Log中的COMMIT ACCEPT/ABORT ACCEPT记录是通过本地DM的Commit/Abort子程序来实现的，在子程序中进行具体的操作之前，DM会写入COMMIT ACCEPT/ABORT ACCEPT记录到日志中去。

有了这个日志系统，当服务器S就可以按照下面的方式进行恢复：

1> 如果S检查DT Log发现了记录，那么S就知道自己是一台协调员。如果发现日志还包含了COMMIT DECISION或者ABORT DECISION日志，那就证明在故障发生之前已经产生了决定，他可以选择重新发送这些决定。如果没有发现这两条记录中的任何一条，那么S就可以单方面得决定Abort，同时向日志中写入ABORT DECISION记录，并重发决定。需要注意的是，要先插入COMMIT DECISION日志，再发送COMMIT决定给各个参与者进程，这很关键。为什么顺序这么关键呢？试想一下，如果发送决定消息在前，插入日志在后，那么就会有一种可能，消息COMMIT DECISION发送完了但日志还没来得及写入的时候服务器发生故障了，当服务器恢复之后，按照前面的逻辑，它会认为还未做出任何决定，于是又单方面的决定ABORT DECISION，这下就和实际情况冲突了，参与者就会受到两条完全冲突的决定：ABORT DECISION和COMMIT DECISION，系统会无法处理。如果写日志在前，发送消息在后，系统也有可能在两个时间点之间发生故障，协调员恢复时会看见日志，因此不会做任何事或者把决定重新发送一遍，因为决定事先已经达成，即使有可能消息还没有发送，但至少不会做出自相矛盾的决定令参与者无法是从。

2> 如果S没有发现任何记录，S就会认为自己是一台参与者。那么就会有三种情况：

1. DT log中包含了COMMIT ACCEPT或者ABORT ACCEPT记录，那参与者已经获得了决定，那么参与者可以自己来决定，可以根据记录来查看相应的操作是否完成，如果还未完成可以继续从而完成相应操作。

2. 如果日志中没有包含VOTE YES记录以及任何COMMIT ACCEPT或者ABORT ACCEPT记录，我们无法得到它当时是选择YES还是NO。我们写VOTE YES记录的时间也要比发送实际消息早，尽可能早得保存决定。此时S可以单方面得决定ABORT ACCEPT。

3. 如果日志中包含VOTE YES记录但没有任何COMMIT ACCEPT或者ABORT ACCEPT记录。那么参与者是在不确定期发生故障的，因此它采用终止协议来获得决定。

 

对于一个实际的系统而言，系统需要处理的是很多的事务，因此不同事务的日志是交错得存放在DT Log里。因此每条日志记录需要包含事务的名字。而且随着时间的积累，事务越来越多，日志的体积也会越来越庞大。因此需要定期对日志进行垃圾回收。日志垃圾回收有2个准则：

GC1：一台服务器不能删除事务T的日志，直到它的RM（Recovery Manager）已经处理完了RM-Commit(T)或者RM-Abort（T）

GC2：一台服务器不能删除事务T的日志，直到该服务器收到消息，所有其他服务器的RM-Commit（T）或者Rm-Abort（T）已经处理完毕。

对于GC1，通过本地的信息很容易得到。对于GC2，则需要服务器之间能够相互通信，你可以让协调员来执行GC2，或者完全分布式得由各个服务器通过相互交流完成GC2.

由于实际系统同时并发得处理很多事务，因此在某台服务器恢复的时候，我们还需要考虑一些细节问题。当服务器恢复时，它需要把继续完成那些还未COMMIT或ABORT的事务，这些事务在完全恢复之前都会被block住从而无法访问数据库这部分资源，这会造成浪费。因此解决的方法是不是在整个恢复阶段一直hold住这些待恢复并且在故障之前处于不确定期被block住得事务的所有的读写锁，而是把这些锁暂时全部释放，然后再通过重新争取锁的方式来和新到的事务来竞争锁，这样避免了在整个恢复阶段所有的block资源都无法访问。具体的流程是这样的，服务器恢复后，先处理那些没有被block住的事务，为这些事务做出决定。然后再处那些故障前被block的事务，这时候恢复程序先释放这些事务的所有读写锁，然后再与故障之后新的事务一起竞争重新请求这些读写锁。一旦恢复程序先释放了待恢复的block事务的读写锁，那么这些事务所持有的数据库资源就可以被访问了。当然由于有竞争，原来本来可以COMMIT的事务可能由于资源竞争被ABORT掉了，但带来的好处是吞吐量大大提高。在原来的方案中，事务的锁可以保存在DT Log里，在竞争的方案中，锁可以不必保存，因为服务器进程可以根据Log自行决定。