Lamport Timestamp在totally-ordered multicast中的应用

1. 什么是Lamport Timestamp

　　在分布式系统中，同步是一项重要的工作，也是一项困难重重的工作。如果在一个系统中各个子系统有一个全局同步的时钟，那么同步就十分简单，根据全局的时钟能很容易地判断一系列操作的先后执行顺序，从而使得在各个子系统中按相同的顺序执行这些操作。但是现实中的多个物理时钟由于种种原因同步很困难。在整个系统中设置一个专门负责生成时钟的节点，也会限制系统的扩展性（若考虑网络延迟，子系统申请到的时间戳也未必与它们事件真实发生的顺序一致）。

　　为了解决同步问题，Lamport提出了逻辑时钟(logical clock)的概念。他发现在整个过程中，我们的目的是想获得事件的相对顺序，而不是事件发生的时间点。只要把这个相对顺序描述清楚了，用什么时间概念也无所谓。他称这个相对顺序为”Happen-Before”(HB)关系，同时利用逻辑时钟表示这个HB关系。

　　Lamport描述了分布式系统中存在的两种HB关系：

• 在同一个进程中连续发的两个消息a，b之间存在HB关系，即b在a之后发生；
• 在不同的进程之间，发送消息a的事件和接收消息a的事件之间存在HB关系，即发送消息a的事件一定在接收消息a的事件之前。

　　上述两种HB关系可以用逻辑时钟量化的表示。

　　首先规定，每一个进程都维护一个自己的逻辑时钟，此逻辑时钟只增不减（具体可以理解为一个本地的计数器）。其次令LCi(e)表示事件e在进程Pi中发生时的逻辑时钟的值。那么上述两种关系用逻辑时钟可以表示为：

　　关系1: 进程Pi中连续发的两个消息a，b，则LCi(a) < LCi(b)。

　　关系2: 进程Pi向进程Pj发送消息a，则LCi(snd(a)) < LCj(rev(a))。

　　注意：两个并发事件a，b之间的逻辑时钟值没有必然关系，即LCi(a) < LCj(b) || LCj(b) < LCi(a)。

　　这样我们就可以利用逻辑时钟表示事件之间的HB关系了。

　　具体为了在系统运行中维持上述两个关系，Lamport提出了如下算法：

　　Step1: 进程Pi在准备发消息之前，本地的逻辑时钟加1;

　　Step2: 在完成步骤1的基础下，进程Pi给消息m加上本地的逻辑时钟值为t(m)，并把消息m发送个进程Pj;

　　Step3: 进程Pj在接收到消息后，需要更新本地的逻辑时钟LCj = max(LCj, t(m))。然后执行步骤1，把接收到的消息发送给应用程序。

　　从上述算法我们可以发现步骤1保证了关系1；步骤3则保证了关系2。按照Lamport提出的算法，每个进程维护本地的逻辑时钟，既能保证多个进程间消息的HB关系。

2. Lamport Timestamp在totally-ordered muliticast中的应用

　　从Lamport对逻辑时钟的基本定义我们发现，这个HB是一个偏序关系，对并发消息之间的顺序没有规定。为了使得进程间的消息全局有序，可以按如下方式扩展时间戳定义：进程Pi中发送的一个消息m的时间戳除了本地的逻辑时钟外再加上进程号，记为Ti(m)。这样定义扩展的HB关系为Ti(a) < Tj(b) <==> (LCi(a) < LCj(b) || (LCi(a) == LCj(b) && i < j))，即在逻辑时钟相同的时候，我们规定进程号小的消息优先。在这扩展的HB关系下，系统中的所有消息都可以比较了。

　　那么如何保证分布式系统中的各个子系统都按相同的顺序执行一组操作？一个等价的问题就是如何在分布式系统下实现全序组播(totally-ordered mulitcast)。这个可以利用Lamport提出的逻辑时钟实现。

　　在利用Lamport Timestamp实现全序组播时，要遵循如下假设：

• 进程Pj在接收进程Pi的消息时，Pj对消息的接收顺序与Pi发送消息的顺序一致
• 任何传输的消息不会丢失。

　　上述假设只是为了简化讨论，而在实际系统中可以采用各种方法来保证上述两个假设。

　　保证全序组播的具体算法为：

　　每一个进程都维护一个本地请求队列(Request Queue)，此队列里的消息按时间戳排序。

1. 进程Pi给消息m加上时间戳Ti(m)，并广播给所有进程(包括Pi);
2. 进程Pj接收到消息m后，首先更新本地逻辑时钟，并把消息m加入请求队列，然后向所有进程（包括Pj）广播接收到消息m的确认信息ACK。
3. 当进程的请求队列中的某个消息位于队列顶部，且已经收到所有进程关于此消息的确认信息ACK时，可以把此消息从队列顶部取走，并传给应用程序。

　　上述算法结合假设，可以证明所有进程都按相同的顺序执行一组操作。

　　证明中的关键点：

　　当进程Pi收到所有关于消息m的确认信息ACK时，

       首先，可以确认其他进程已经收到了消息m；

       其次，可以确认其他进程中“在关于消息m确认信息ACK之前发的消息”进程Pi都已接收（这个可以从假设得到）。这表明如果存在需要在消息m之前执行的消息，进程Pi已经接收了，否则与假设矛盾。结合消息的执行条件，就能保证消息m不会被提前执行。

       最后，由于每个进程是等价的，所以每个进程的请求队列都是一致的。