MVCC事务总结（二）

逻辑时钟的背景

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

但是在分布式系统中，基本上做不到一个统一的时间轴（即使使用NTP服务，依然有误差和跳变的问题， 哪怕是google spanner 的 true time 依然使用的是一个事件范围），因为时间相对的 （侠义相对论）。

于是Lamport 大师的逻辑时钟就闪亮登场，在他定义的逻辑时钟算法，给分布式系统里面定义了一个有向轴，把分布式系统里面的事件放在有向轴中，以所有事件都达到全序关系状态。

参见论文

time clocks and the ordering of events in a dritribute system

http://www.stanford.edu/class/cs240/readings/lamport.pdf

在论文中系统的事件分为三类

本地事件

发送消息事件

接收消息事件

WIKI的描述

algorithm

The algorithm follows some simple rules:

In pseudocode, the algorithm for sending is:

The algorithm for receiving a message is:

通俗一点讲

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

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

结论

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

如何解决这个问题，待续的下一篇 混合逻辑时钟和spanner true time。

.......................... END..........................