与基于加锁的并发控制不同，基于时间戳的并发控制并不试图通过互斥关系来维护可串行化， 而是先提前选择一个串行化顺序，再根据这个顺序来执行事务， 为了建立这个顺序，事务管理器需要对每个事务T进行初始化时分配一个时间戳。

时间戳时一种专门用来唯一标识每个事务并将事务排序的标识符。 唯一性、单调性是时间戳的特性，即每个时间戳都是唯一的，事务管理器生成的事务必须单调递增。

一种方式是维护一个全局的计数器，但这在分布式系统中是一个比较困难的问题。 还有一种方式是让每个节点根据本地的局部计数器独立分配时间戳。 为了维护唯一性，每个节点会将直接的标识号附加到计数器值的后面， 即时间戳是一个二元组：<局部计数器,节点ID>。节点ID作为附加在较低位， 只有在两个事务被分配了相同的局部计数值时，节点ID才能派上用场。 而每个节点访问自己的时钟，这里的时钟可以是物理时钟、逻辑时钟、混合时钟、全局时钟等等方式， 主要看分布式数据库时钟选取问题，各种时钟都有自己的优劣，需要谨慎选取。
综合上面的信息可知，可以按照时间戳来对事务的操作进行排序了。 时间戳排序（timestamp ordering,TO）的规则如下： TO规则给定事务Ti和Tj中的两个冲突操作Oik和Ojl,当且仅当ts(Ti)<ts(Tj)时，Oik会在Ojl之前执行。 ts即是对于事务T分配的唯一时间戳。

使用TO规则的调度会将每一个操作与已经调度过的冲突操作进行比较，如果新的操作属于一个较新的事务， 那么就接收它；否则它就会被拒绝，然后将相应的事务赋予新的时间戳并重新启动。

这个思路提供了基于时间戳的调度，可以保证生成可串行化的排序，不过，只有当调度程序接收到所有 需要调度的操作，时间戳之间才能比较。如果操作一个接一个传递给调度器，那么就需要以高效的方式检测 每个操作是否按照合法顺序进入。这样，每个数据项x需要被赋予两个时间戳：读时间戳rts(x)、写时间戳wts(x)。 读时间戳表示读取x的所有事务的时间戳的最大值，写时间戳表示写入x的所有事务的时间戳的最大值。 这时，当一个操作需要访问某个数据项时，调度程序就可以根据读时间戳和写时间戳来判断是否有时间戳更大的事务 访问了该数据项。

从构架上来看，事务管理器负责为每个新的事务分配时间戳，并将这个时间戳附加到事务的数据库操作上。 调度器的职责是记录读和写的时间戳，并进行可串行化排序检查。

基于时间戳的并发控制也是由传统关系型数据库最早提出的，分布式的TO算法也是由单机TO算法延伸而来。 在《数据库系统概念》一书的15.4章节详细介绍了基于时间戳的协议。

基本TO

基本TO是TO规则的直接实现，协调事务管理器为每个事务分配时间戳，为每个数据项选定存储节点， 并且将相关数据库操作发送到这些节点上。

基本TO的规则是：

• 事务管理器读或者写数据项均不需要锁
• 每个数据项x都带有成功读/写最后一个事务的时间戳：rts和wts。
• 为每个操作检查时间戳：如果事务试图访问“未来”的对象，将重启或取消。

读取规则：

• 如果ts(t)<wts(x),则t需要读取的x值已经被覆盖。读取被拒绝，并回滚。 换句话说，这违反了事务t对写x的时间戳排序,需要取消t并重启分配新的ts
• 否则允许t对x进行读，更新rts(x)=max(rts(x),ts(t)),制作一个x的本地副本，以确保t的可重复读

写规则：

• 如果ts(t)<rts(x)或者ts(t)<wts(x),取消或者重启t
– ts(t)<rts(x)时，事务t产生的x值是先前所需要的值，所以write操作被拒绝，t取消或重启。
– ts(t)<wts(x)时，t试图写入的x已过时，因此写操作被拒绝，t取消或重启
• 否则允许t对x进行写并更新wts(x),同时制作x一个本地副本，以确保t的可重复读

一种更快速的方式是使用thomas写规则(数据库系统概念15.4.3)，这里不再展开。

扩展到分布式，采用分布式中的时间戳方案通过事务管理器将时间戳分配给所有的读和写操作， 每个数据管理器（DM）的调度程序都会跟踪迄今为止为每个数据对象处理的所有读写操作中的最大时间戳。

read(x,ts)=rts(x)，对数据对象x带有时间戳ts的读取请求， write(x,v,ts)=wts(x),向数据对象x写入带有时间戳ts的写入请求，写入值是v。 基本算法同上边的读取和写规则，只是增加了分布式节点间的消息处理，所以在设计上会稍有不同。 首先，某一个操作如果被拒绝，那么整个事务就需要重新分配新的时间戳，然后重启， 这保证了事务的重试的机会，这意味着基本TO不会死锁；当一个已接收的操作被传递到数据处理器时， 调度器必须在该操作完成之前避免向数据处理器再发送另一个虽然冲突，但也被接受的操作。 同时，每个节点的数据处理器上的数据操作如何保证故障转移和一致性也是设计时需要考虑的事情。

基本TO的算法描述可以查找相关论文。

保守TO

基本TO不会让操作进行等待，而是将其重启。这种方法可以有效避免死锁，但也有劣势， 即过多的重启会对性能造成不利的影响。保守TO试图通过减少失误重启的次数来降低系统的负载。 保守TO采用了Lamport的逻辑时钟的做法来进行时钟同步，避免出现单个节点的时钟落后其他节点太多的情况。

相对于基础TO，保守TO的思路是每个调度器建立一个缓冲区，每个事务的操作都放在缓冲区内， 然后再排序之后执行操作，而不是和基本TO一样即时执行。缓冲区中的操作时不会被拒绝的。 保守特性来源于其执行每个操作的方式，对于基础TO来说，每当接收一个操作就立即执行， 与之相对的是，保守TO会将操作进行延迟，直到可以确认今后调度器不会再接收到时间戳更小的操作。 如果这个条件可以保证，那么调度器就不会拒绝任何一个操作，不过这种方式有可能引入死锁。
保守TO会减少重启次数，但不能完全避免事务重启。除非采用更保守的TO：仅当队列里至少有一个操作时， 调度器才可以选择一个操作发送给数据处理器。这样做可以保证调度器在接收到每个操作时， 时间戳都能大于或等于当前队列中的操作的时间戳。如果没有事务需要处理，事务管理器以 一定的间隔向其他调度器发送伪信息，以便以后发送的操作都比伪信息时间戳大。 这种极端保守的TO调度程序会让每个节点都顺序执行事务。

多版本TO

多版本TO是另一种试图避免重启带来开销的方法。在多版本TO中，更新并不改变数据库； 每个写操作都建立一个数据的新版本。每个版本都标记一个建立它事务的时间戳， 这样多版本TO就可以在存储空间和时间上做一个平衡。这样，数据库处理事务可以按照时间戳 顺序执行。

多版本TO的处理：

Ri(x)会转化为x的某一版本的读。首先找到x的一个版本Xv，这个版本时间戳比ts(Ti)小， 但比其他早于Ti事务的其他版本的时间戳都大。读取到的值就是这个时间戳的点的值。如图， 这时，Ri可以读取到的值是Xv。

Wi(x)转化成带有Wi(xw)，满足ts(xw)=ts(Ti),并且它被发送给数据处理程序时， 当且仅当，没有其他时间戳大于ts(Ti)事务读取了x的一个版本Xr,满足ts(xr)>ts(xw), 换句话说，如果调度程序已经处理了图中的Rj(xr):ts(Ti)<ts(Xr)<ts(Tj)时，Wi(x)被拒绝。
Ri
| | ↓ |
---------±-------±---------±--------> 时间戳
| | |
Xk Xv Xw

          Wi   Rj

| | ↓ ↓ |
1
2
---------±-------±-----------±--------> 时间戳
| | xw |
Xl Xk Xr
如图，如果Wi被接受的话，事务管理器会建立x的版本xw,这个版本本该被Rj读取，但由于 Rj执行时xw并不存在，如果只能读取到Xk，会出现历史错误。

总结

无论是前边介绍的加锁还是基于时间戳的并发控制，都是悲观的，也就是先假设事务之间的冲突比较频繁， 它们不允许两个事务同时对同一个数据项进行冲突的访问，因此，任意一个操作都可以按照这个步骤来执行： 有效性验证，读，计算，写。一般来说，这个顺序对于更新事务以及它的操作来说都是有效的。 而目前来说，一般使用的分布式并发控制，都是乐观并发控制（OPTIMISTIC CONCURRENCY CONTROL OCC）。 虽然本文和加锁的并发控制介绍的并非是时下流行的乐观并发控制，但可以增加对传统关系型数据库的并发控制的了解， 并且这些理论都是后续的基于MVCC的乐观并发控制的基础。

以上为基于时间的并发控制。「分布式技术专题」是由hubble数据库团队精心整编，专题会持续更新，欢迎大家保持关注。