分布式数据库 MVCC 技术探秘（一）

MVCC是NoSQL和RDBMS领域中常用的事务控制机制。在MVCC之前，主要采用 T wo-phase commit ，但Two-phase commit过程中需要对读写操作进行加锁，这会带来显著的性能问题，因此，Two-phase commit在读写高并发场景中已被逐步摒弃。

本文重点介绍 Snapshot Isolation 与 逻辑时钟 。

Snapshot Isolation(SI)

Snapshot Isolation 的出现主要解决 T wo-phase commit 带来的性能底下的问题，其原理如下：

- 每一个数据都多个版本，读写能够并发进行

- 每个事务相当于看到数据的一个快照

- 写写不能并发，写写操作时需要加上行锁

- 谁先获取到行锁，谁可以顺利执行(采用“first win”的原则)，后面的写事务要么abort，要么等待前面的事务执行完成后再执行（以Oracle/SQL Server/MySQL等数据库为代表）

但是 snapshot isolation 带来一个大问题： write skew ，即写偏序问题(不能够达到串行化的事务隔离级别)。

Write Skew

写偏序（Write Skew）是一致性约束下的异常现象，即两个并行事务都基于自己读到的数据集去覆盖另一部分数据集，在串行化情况下两个事务无论何种先后顺序，最终将达到一致状态，但SI隔离级别下无法实现。下图的“黑白球”常常被用来说明写偏序问题：

举一个简单的例子：

事务T2 与事务T1 并发执行相同的语句，两个事务都会执行，执行成功后

A1= -100 ，A2= -100 ， A1+A2=-200

显然违背完整性约束。

Write Snapshot Isolation

为了解决”write skew”（写偏序） 问题，出现了”Serial Snapshot Isolation”理论，其实现方法有很多种，”Write Snapshot Isolation”作为”Serial Snapshot Isolation”理论的典型代表解决”write skew”问题, 基本思想：

冲突检测发生在事务的运行阶段，而不是事务的提交阶段。

因此，它的原理就是：增加读写冲突检测来解决”write skew”问题。如下是”Write Snapshot Isolation”的定义：

Similarly to Snapshot isolation，write Snapshot isolation assigns unique start and commit timestamps to transactions and ensures that txni reads the latest version of data with commit timestamp δ
  

与SI 一样每个事务都有一个事务开始时间戳与事务结束时间戳。Write Snapshot isolation 需要保证一个事务读的数据的最近一个版本的提交时间要早于事务的开始时间。

换一种简单的描述：如果两个读写事务”txni”，”txnj”同时满足下面两个条件，那么这两个事务不能同时提交成功：

- 读写在空间上重叠：”txni”的写操作与”txnj”的读操作发生在同一行

- 读写在时间上重叠：Ts(txni) < Tc(txnj) < Tc(txni)注：Ts(txni)代表txni的事务开始时间, Tc(txni)代表事务txni的事务提交时间

Write Snapshot Isolation事务虽然解决”write skew”问题，还存在另外一个难以解决的问题： 全序问题 。

基于 Snapshot isolation理论，每个事务都有两个事件：

- 事务的开始事件（时间）

- 事务的提交事件（时间）

所有的事件必须是全序的，即所有事件都有先后顺序。一般情况用时间轴表示事件的发生的前后关系，实现事件的全序。我们给事务分配一个事务的开始时间，一个事务的结束时间，这样在整个系统中，所有的事件都可以比较先后关系。
但是在分布式系统中，时间就变成一个非常大的难题，因为各个节点的时间可能有误差。而且根据侠义相对论，时空的事件并不存在一个始终如一的全序关系。

逻辑时钟

在MVCC理论中，需要一个能力，能够识别出整个系统中所有事件（事务开始，事务提交）的先后关系，但在分布式系统中提供一个统一的时间轴是一件非常困难的事情，本章节继续介绍Lamport大师提出的逻辑时钟算法。

逻辑时钟出现的背景

在MVCC理论中，需要一个能力，能够识别出整个系统中所有事件（事务开始，事务提交）的先后关系。即，将系统中的所有事件都放在一个有向轴上，描述他们的先后关系，所有的事件是全序的。一般在分布式系统特别在分布式的数据库中把有向轴定义为时间轴，而一个事务通常包含一个开始的时间戳和一个结束的时间戳。

但是在分布式系统中，基本上做不到一个统一的时间轴（即使使用NTP服务，也会存在误差和时间跳变的问题， 哪怕是Google Spanner 的 True Time 依然使用的是一个时间范围），因为时间是相对的 （侠义相对论）。

于是Lamport 大师的逻辑时钟闪亮登场，在他定义的逻辑时钟算法里，给分布式系统里面定义了一个有向轴，把分布式系统里面的事件放在有向轴中，从而使得所有事件都达到全序关系状态。Lamport的这篇论文名为《Time, Clocks, and the Ordering of Events in a Distributed System》，在论文中将系统的事件分为三类：

- 本地事件

- 发生消息事件

- 接收消息事件

WIKi中关于逻辑时钟的定义

A process increments its counter before each event in that process;When a process sends a message, it includes its counter value with the message;On receiving a message, the counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received.

发送消息 的伪码实现：

time = time + 1;

time_stamp = time;

send(message, time_stamp);

接收消息 的伪码实现:

(message, time_stamp) = receive();

time = max(time_stamp, time) + 1;

关于逻辑时钟的通俗理解

每个进程都有一个计数器，进程每发生一个事件，本地的计数器加1。

进程在执行一个发生消息的事件时，要把本地时间戳（进程计数器的值）带到消息内部，一个进程接到该消息的时候，要把本地的计数器的值设置为max（消息带的时间戳的值，本地计数器的当前值）。

在数据库中定义事务的开始时间点和提交时间点，就可以使用 逻辑时钟 来定义。本地事件发生的逻辑时钟的时间就是本地计数器的值，通过使用逻辑时钟，就可以确定任意进程间任意事件的前后关系。

但是仅使用逻辑时钟会出现一个另外的问题： 从系统外部人的角度来看，通过逻辑时钟定义出的全序关系与实际物理时间上的发生先后顺序不一致，即逻辑时钟这个轴跟我们物理意义的时间轴并没有关系，比如事务A与事务B，在逻辑时钟这个轴上，可能是A先发生，B后发生，但是在物理时间上，可能是B先发生，A后发生。 如何解决这个问题，这部分内容将在下一篇文章中介绍。