事务

事务的基本概念

简单来说，事务就是将一系列列数据库的基本操作看作一个基本执行单元。比如在银行转帐中可能设计多个基本数据库操作，但是转账这个操作本身应该被看作一个基本执行单元，因为我们不希望在转账的过程中出现异常,具体实例如下所示：

example transactions
x and y are bank balances -- records in database tables
x and y are on different servers (maybe at different banks)
x and y start out as $10
T1 and T2 are transactions
T1: transfer $1 from x to y
T2: audit, to check that no money is lost

T1:             T2:
begin_xaction   begin_xaction
  add(x, 1)       tmp1 = get(x)
  add(y, -1)      tmp2 = get(y)
end_xaction       print tmp1, tmp2
                end_xaction

在分布式数据库中，数据可能会被存储在不同的集群中，因此如果一个事务涉及到的数据存储在不同的存储节点中，则称其为分布式事务。 分布式事务的执行涉及到两个重要问题：concurrency control 和 atomic commit。

ACID原则

事务的执行必须满足ACID原则：

• Atomic：事务的执行必须是原子性的，要么成功，要么失败，不允许存在中间状态。
• Consistent：事务执行前后数据的一致性没有被破坏。这表示写入的数据必须完全符合所有的预设约束、触发器、级联回滚等。
• Isolated：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括未提交读（Read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（Serializable）。
• Durable：已提交的事务的更改是永久存在的。

Serializable

事务的串行化是指并发事务的执行结果与某个串行执行顺序一致。Serializable是实现isolated的最高级别，同时并发行也最差，隔离级别和并发度呈负相关关系。

比如在上述银行转账例子中，执行顺序为T1 T2时， 数据库里x=11,y=9，控制台输出"11 9"，执行顺序是T2;T1时，数据库里x=11,y=9，控制台输出"10,10"。两张执行顺序的结果虽然不同，但是都是符合isolated要求的，因为事务之间是符合串行顺序的。但是，如果事务T2在T1的add(x,1)操作后执行，这种则是不可行的，其违反了事务的isolated原则。

分布式事务

分布式事务中包含两个重要的组成部分， concurrency control和atomic commit。

Concurrency Control

concurrency control保证了分布式事务执行的isolated，其主要由以下两种放hi是：

• pessimistic：在执行事务前对所有需要用到的数据上锁。
• optimistic：在执行事务时不加任何锁，在commit时检查是否符合serializable，如果不符合则采用rebort+retry的方式重新执行事务。

通常情况下，pessimistic方式适用于冲突经常发生的情况，而optimistic适用于冲突很少发生的情况。

Two-phase locking

2PL是一种常见的采用pessimistic方式实现serializable的方法，其包含两个步骤：

• a transaction must acquire a record’s lock before using it
• a transaction must hold its locks until after commit or abort

在分布式数据库中，每个数据record都包含一个独立的exclusive lock。在事务执行过程中，当第一次使用某个data record时，会申请加锁，所有锁只有在commit或abort后才释放。2PL可能会存在dead lock问题，如下所示：

 T1      T2
 get(x)  get(y)
 get(y)  get(x)

如果事务T1和T2同时开始执行，则可能会出现dead lock问题。为了解决该问题，分布式数据库需要能够对死锁进行检测，并进行abort其中一个事务。

Atomic Commit

由于分布式事务所需要的数据在不同的存储节点中，因此需要保证所有节点执行该分布式事务的原子性，要么所有相关存储节点都完成事务提交，要么所有相关存储节点都失败。

Two-phase Commit

在分布式事务执行中，通常包含一个transaction coordinator用于将事务分发到不同的存储节点上，transaction coordinator会为每个transaction分配一个唯一的transaction id。

2PC的基本流程如上图所示：

1. TC向不同的server发送prepare message
2. server收到prepare message后判断能否执行事务（如锁的获取是否顺利，是否有其它事务在执行等），如果可以则执行事务并返回Yes，否则返回No
3. 如果所有server返回Yes，则TC发送commit message，否则发送abort message
4. 如果server收到commit message，则执行commit操作释放lock，并返回ack，如果收到abort message，则执行abort操作释放lock，并返回ack
5. TC收到所有ack后返回事务执行结果，标志事务执行完成。

failure discussion

下面我们讨论在2PC中可能出现的各种failure情况。

Server2在prepare阶段回复后crash

在这种情况下，如果server2回复的是Yes，则在restart后server2必须记得自己已经回复了Yes，因为有可能此时server1已经完成了事务的commit。因此，在prepare阶段，当server回复之前必须将自身的状态进行持久化log存储。 当server restart后，如果发现自己回复的是Yes，则需要请求或等待TC重新发送commit message。

TC在发送commit后crash

这种情况下，TC必须记得自己的状态，因为server1和server2可能已经完成commit操作。TC restart后必须重新发送commit信息，server需要有过滤重复commit message的能力。 因此TC在发送commit message前，需要对自己的状态进行持久化log存储。

TC没有收到来自server2的vote

这种情况下，可能server2 crash或network broken，此时TC可以设置timeout时间，如果超过该时间没有收到vote，可以进行发送abort信息回滚事务。

Server2在发送Yes后没有收到commit/abort message

这种情况下，server2必须一直等待直到收到TC的信息。 因为可能server1收到了相应的commit message并已经提交事务。

conclusion

2PC可以一定程度上解决atomic commit的问题，但是其最大的问题就是当server发送了Yes后，就必须等待TC的message。 3PC在一定程度上改进了这个问题，具体内容可以参考该链接3PC介绍。