最近在学习分布式系统的知识．在学习Raft算法时，看到其中有提到状态机．于是就去研究了一下状态机，在研究状态机的时候，又看到其中提到Logic Clock．Google了一下，发现有一个很著名的就是Lamport大神提出的Lamport Clock,于是找了一下他的论文拜读了一下．
这篇文章是我在读完论文之后的总结．由于水平有限，其中有些地方可能有错误．所以建议各位先读原作，再来读这篇文章，防止我误人子弟．论文题目为:Time, Clocks, and the Ording of Events in a Distributed System
happened-before
我们先来介绍一下happened-before模型． 为什么需要这个模型呢？ 因为在不同的机器上，时间往往都不是相同的，尽管我们可能看起来相同，但是其中还是有微秒级的差距．在普通情况下可能没什么关系，但是对于一个要处理高并发请求的分布式系统来说，就很致命了．完全有可能就是由于这微秒级的差距，导致事件是无序的．
比如说，我们有三台服务器，分别为A,B,C.服务器A和B向服务器C发送请求，然后服务器C对这些请求进行排序．假设没有逻辑时钟，那么服务器A和B向服务器C发送请求的时候，需要带上从本机获取的时间戳，否则就可能会由于网络延时而造成服务器C进行错误的排序．
因为服务器发送请求时，都是从本机上获取时间戳．这本身又是一个问题．因为不同服务器上的时钟都是不同的．假设同一时刻，服务器A的时钟是10:10,服务器B的时钟是11:11，当然这有点夸张，但是也是符合时钟不相同的定义的．假设服务器A在这一时刻先让服务器B向服务器C发送请求，随后服务器A再发送．那么服务器C根据消息中的时间戳进行排序时，便会将服务器B的请求排在后面，而服务器A的请求排在前面．我们可以看到，这和实际的发送顺序是完全相反的．
为了解决这个问题，论文中就提出了happened-before模型．
那happened-before模型到底是什么呢？ 我们定义两个时间如果符合下面的三个关系中的一个，则其就有happened-before关系:
- 如果事件A和事件B都是相同进程发出的，并且事件A在事件B之前发生，则事件A happened before 事件B.
- 如果事件A在进程1上被发出，然后在进程B上被接收，作为事件B．那么事件A happened before 事件B.
- 如果事件A happened before事件B,事件B又happened before事件C, 那么事件A happened before事件C.
其他任何不满足上述关系的事件，我们都称这些事件为并发事件．
我们注意第一个关系，重点是在相同进程中.由于是在相同进程中，我们很容易就能知道事件A和事件B谁先谁后．
在第二个关系中，重点是在不同进程中，并且有发送－接收关系．这里不同进程并不一定是在同一台机器上的两个不同进程，一般是位于不同机器上的不同进程．因为实际上，如果是同一台机器上的不同进程，那么我们还是能够通过获取时间戳的方式，来获取事件的先后顺序的．
第三个关系就很简单了．
我们可以从上面三个关系中看到，我们并没有涉及到物理时钟．
逻辑时钟
了解了happened-before模型之后，再来了解逻辑时钟就很简单了．在happened-before那节中，我们看到了，既不能使用获取时间戳的方式来进行排序，又不能通过让服务器C按照接收顺序来作为排序顺序．那我们到底应该如何来排序呢？
这就要介绍我们的逻辑时钟了．
逻辑时钟就相当于一个序号，就是现在我们统一给不同进程中的时间进行编号，来代表其顺序．
如果事件A happened before事件B，那么事件A的逻辑时钟值就比事件B的逻辑时钟值小，也就是事件A的编号比事件B的编号小.
那么怎样做到如果事件A happened before事件B，那么事件A的逻辑时钟值就比事件B的逻辑时钟值小呢？
分两种情况讨论．
事件A和事件B在相同的进程上
逻辑时钟跟物理时钟相比，它也是会”滴答”的，每滴答一次，逻辑时钟值就加一．但是物理时钟是每秒滴答一次，而逻辑时钟可就不是了．我们可以自定义每隔多长时间滴答一次，一般会让其足够小，做到事件B的逻辑时钟值比事件A的逻辑时钟值小．
其实这里我也挺困惑的．论文中并没有说明我们要如何衡量应该多长时间让其滴答一次．如果我们设置的太大，就会造成相同进程上的不同事件具有相同的逻辑时钟值，而违背了上面说的如果事件A happened before事件B，那么事件A的逻辑时钟值就比事件B的逻辑时钟值小，也就是事件A的编号比事件B的编号小．
如果是每次一有事件发生，才滴答一次的话，那么在高并发的情况下，由于滴答的这个操作是串行的，必然会有性能问题．
这里如果有高人了解如何解决的话，还望告知一下．
事件A和事件B在不同的进程上
我们称进程之间进行交互时，是发出的消息(message), 消息中会包含事件以及事件对应的逻辑时钟值．当进程2收到进程发来的消息时，它会比较消息中事件的逻辑时钟值和当前它的逻辑时钟的值，如果发现事件的逻辑时钟值大于它的逻辑时钟的值，则将它的逻辑时钟的值修改为事件的逻辑时钟值+1．否则就不修改．
局部有序性
理解了上文的读者，现在应该已经清楚如何通过逻辑时钟来实现局部有序性的了．
我们还是通过夸张的方式来描述局部有序性．
假设我们设置的逻辑时钟每隔十分钟滴答一次.假设进程1在这十分钟之内给进程2发送了一个消息，其中包含事件A，以及其逻辑时钟值6,进程2检查其逻辑时钟值，发现其为7,于是不修改其逻辑时钟值，直接将接收到的事件A作为它的事件B,设置其逻辑时钟为7.
时钟过去之后，进程1又发生了一个事件C，这个事件只是一个进程内部的事件，即其不会发送给进程2．那么这个事件C的逻辑时钟值为7.
这里我们就能看到了，进程2上的事件B和进程1上的事件C具有相同的逻辑时钟值7．但是由于它们没有happened-before关系，因此没有违背如果事件A happened before事件B，那么事件A的逻辑时钟值就比事件B的逻辑时钟值小，也就是事件A的编号比事件B的编号小．
你看，两个不同的事件具有相同的逻辑时钟值，那排序的时候咋排? 无所谓啦，因为它们又不是相关的事件，谁先谁后无所谓啦．
但是在排序的结果中，一定能够保证具有happened-before关系的事件的前后关系．
这就实现了我们所说的局部有序性．
全局有序性
在有些情况下，确实满足局部有序性就好啦．但是，有些情况下则不行．比如在状态机中，我们必须找到一个确定的执行序列．使不同机器上的状态机最后都到达相同的状态．如果状态机1执行A->B->C,状态机2执行A->C->B.那还了得？
所以，论文中又在局部有限性的前提下，加了一个约束，就是如果两个时间的逻辑时钟值相同的话，那么由具有较小进程号的进程发出的事件排在前面．也就是说，在局部有限性那一节的例子中，最终得到的排序序列为A->C->B.
其实这里是选取较小进程号还是较大进程号无所谓，只要能确定这么一个顺序就好啦．
但是，即使这样还是有缺陷的．
使用物理时钟来解决由于延时而造成排序错误的问题
比如从网上看到的一个例子，在一次用户购买流程中，购买服务先向日志服务发送一个消息，然后再向优惠服务发送一个消息，优惠服务收到这个消息之后，再向日志服务发送一个消息．那么由于网络延时，日志服务可能会先记录优惠服务发送的消息，其后才记录购买服务发送的消息，这是完全错误的行为．
有两张方式可以避免这种情况．第一种就是购买服务告诉优惠服务它从优惠服务的机器上获取的时间戳，然后优惠服务发送一个比这个更大的时间戳，给日志服务，日志服务再根据时间戳来判断先后．
但是这种方式需要用户来编写代码来控制，不可取．
另一种方式就是协调不同机器的时间的方式．
这种方式需要我们满足两个基本的条件:
- 机器上的物理时钟和正确的物理时钟之间的误差很小．注意机器上物理时钟和正确的物理时钟的差别．
- 不同机器间的物理时钟的误差很小
但是，即使满足了这两个条件，也不能确保就能解决上面的那个问题．
因为不同机器上的滴答速度不相同，所以，不同机器上的物理时钟的误差可能会越来越大．
那什么时候能够真正解决这个问题呢？
不同机器间的物理时钟的误差 * ( 1 - 机器上物理时钟跟正确的物理时钟的误差) <= 消息的最短传输时间．
具体的证明请各位自行查看论文．
