前言分布式系统中存在各种并发事件。对于一些具有内在因果关系的事件，需要知道事件发生的先后顺序，并能够按照正确的顺序处理这些事件，区分事件的顺序，在单机系统中可以通过本地时钟来实现，但是如何在分布式系统中做，就是分布式系统中的逻辑时间问题。本文介绍的是逻辑时间算法鼻祖LamportClock。为了形象地描述逻辑时间问题，我们举个简单的例子。假设客户A下订单购买一本书。这时系统向订单系统提交请求（客户买书的订单），然后买书有优惠。获取免费图书，系统需要向促销活动管理系统发送b请求（客户请求图书x），优惠活动管理系统审核通过客户的图书捐赠请求，然后将b请求转发给订单系统，在这个例子中，很明显订单系统应该先收到买书的订单，再收到捐书的订单。但由于网络延迟，可能会出现赠书请求先于购书请求到达订购系统的情况。在这种情况下，它需要如何处理呢？我们用一张简单的图来描述上面的过程。图中，P0代表订单系统，P1代表客户，P2代表促销管理系统。请求a是购买一本书的请求，请求b是捐赠一本书的请求。为了解决这个问题，比较容易想到同步通信。发送一个请求后，等待P0处理并回复后再发送b请求。这种方法简单易行，但不能充分发挥分布式系统的并发性能。不能简单地在时间a和b上打上本地时间戳来处理，因为分布式系统中的本地时钟不能完全同步，所以需要分布式系统能够记录事件发生的先后顺序也称为“识别的算法”happenedbefore”信息，本文主要介绍逻辑时间算法鼻祖兰波特时钟。Lamport时钟算法Lamport时钟算法的思想很简单。它主要有以下两条规则：每个进程在成功完成一个事件后增加自己的时间戳，通常为1；如果进程Pi通过消息m发送事件a，则消息m包含当前pi的时间戳Ci(a)；进程Pj收到消息m后，取消息m中携带的时间戳与Pj当前时间戳Cj中的较大值，然后加1；例如一个更复杂的例子，已经使用Lamport时钟算法为每个事件添加时间戳，如下图所示：关系，比如p1上时间戳为3的事件和p2上时间戳为4的事件，这些事件可以任意发生，也可以同时发生，但是在Lamport时钟算法中，这些事件有明确的时间戳，大小时间戳不代表事件的顺序。重要属性用一个简单的公式来描述逻辑时间算法的ClockCondition，C代表时间戳，ei和ej代表两个事件，假设ei发生在ej之前，用->表示“发生在之前”的关系，则有以下两个AClockCondition：1)ei->ej=>C(ei)ej<=>C(ei)C(ej)时可以判断ei出现在ej之前，否则可以认为ei和ej冲突（这里的冲突是指ei和ej可以在任意order），所以它可以用来检测事件冲突。案例分析使用Lamport时钟对前面的例子进行排序，如下图所示：P1发送消息a和b消息，因为P1的初始时间戳为0，所以根据Lamport时钟算法，事件a的发送时间戳b为1和2。P0从P1收到消息a，取两个时间戳中较大的值max(0,1)加1得到时间戳2。P2收到b消息后，取较大的值max(0,2)两个时间戳加1得到时间戳为3。P0收到P2转发的事件b后，取两个时间戳中较大的值max(2,3)加1得到timestamp4.因此，在P0端可以得到a事件先于b事件。但是在实际应用中，由于网络延迟，会出现以下情况：由于网络延迟，P0先接收到P2转发的b事件，再接收到P1发来的a事件，然后根据Lamport计算时间戳时钟算法。也变成了事件b先于事件a，这显然是错误的，那么如何避免这种情况，为了着眼于解决这个问题的实际算法，假设系统满足了以下条件：收到的顺序与发送的顺序一致；所有消息最终都会收到；每个进程都有自己的请求队列，并且对其他进程不可见，请求队列中的初始时间戳为0，算法由以下5条规则组成：1）当请求资源时，进程Pi向所有其他进程发送消息Tm处理，并将消息Tm放入自己的请求队列2)prcocessPj收到Pi的资源请求消息Tm后，将消息放入自己的请求队列，并向Pi发送带时间戳的Reply3)释放资源时，Pi移除消息Tm从请求队列中取出并向所有其他进程发送资源释放消息4）进程Pj在收到Pi的资源释放消息后发送之前的资源请求消息Tm从请求队列中移除5）当满足以下两个条件时，认为Pi已经获得了资源。Pi的请求队列中有请求消息Tm，并按顺序排列。此处以消息发送顺序为准；Pi收到任何时间戳大于Tm的消息；把这个算法带进上面的例子，相当于P1发起了a和b两个事件来请求资源，而a发生在b之前，所以也期望a大于b必须先被P0处理（处理这里可以理解为获取P0的资源），那么当上面例子中的情况发生时，事件b首先被P0接收到，根据算法，P0将Tm发送给所有其他进程，然后等待回复.当收到P1的回复时，也必须收到a事件（根据系统假定满足的条件1）消息的接收顺序与发送顺序一致）。此时根据规则5的条件(i)，事件a和b将发送端的时间戳比较重新排序，使得事件a先于事件b，解决了乱序问题网络延迟引起的消息。总结虽然Lamport时钟是解决分布式系统逻辑时间问题的鼻祖，为后续其他算法提供了思路，但是它的强一致性不强，无法满足分布式数据库场景下写冲突的检测，所以在实际场景中是more使用后面的vectorclock，后面会为大家介绍vectorclock。【本文为专栏作者“大U的科技课堂”原创文章，转载请微信♂(ucloud2012)联系作者】点此查看更多本作者好文
