我对Lamport Logical Clock的理解

分布式环境中的一致新问题一直是最热门的话题之一,本文主要介绍了其中的一种比较简单的思路:Lamport Logical Clock。本文来自@GoAce 博客文章的投稿。感谢他的分享。

原文地址:http://www.orzace.com/lamport-logical-clock/

建议先看论文原文再来看这篇文章(原文见文章下方参考文献部分),我不会对论文中的各个点都详细说明,只是写一些我自己的想法,帮助理解。

大家都知道,分布式环境下,确定各个事件发生的顺序很重要,不然就会发生一些麻烦的问题。

考虑一下这个问题:小明要用同学给的优惠码在京东上买一本书。假设京东的后台架构如图一所示,A是前端代理服务器,负责接收用户请求,B是优惠码验证服务器,当用户请求使用优惠码的时候,A会把请求发给B,让B来验证。C是日志服务器,专门存放日志,系统中的任何一个操作都会记录到日志服务器中。很显然,这是一个分布式系统。

图一 后台架构

小明的买书过程分为3个步骤:

  1. 请求到达A,A发送一条消息给C,让C记录一条日志[小明下了订单XXX号]
  2. A是异步工作的,发送完1后,A发现小明使用了优惠码,就把优惠码发送给B进行验证
  3. B验证了优惠码发现是合法的,就发送消息给C,使之记录日志[XXX号订单使用了优惠码YYY]

至此,买书过程结束。如果一切正常的话,那日志服务器上会依次产生[小明下了订单XXX号],[XXX号订单使用了优惠码YYY]这两条日志。但事情没有这么简单,如果A跟C之间的网络比较慢,导致3在1之前到达C,那么C上就会产生顺序相反的两条日志。这样就出问题了,因为是1的发生才导致了3的发生,这两者可以看成是有因果关系的,但是生成的日志却是相反的。

有什么办法能让系统识别事件的因果关系呢?比较容易想到的是让服务器每次发送消息的时候带上时间戳,C收到消息之后比对时间戳,就知道谁先谁后了。问题是,在分布式环境下,各个机器的时钟是无法100%同步的,所以这种方法不靠谱。

那有没有办法在不借助物理时钟的情况下给分布式环境下的所有事件排序呢?

这就需要借助Lamport大神在1978年提出的Logical Clock。

Happend-before关系

Lamport在文章中首先定义了一种关系,叫做Happend-before,我个人的理解是相当于因果关系,用->表示,比如a->b就叫做a Happend-before b,即b是由a引起的。 若两个事件a,b满足下面任一条件,则记作a->b:

short hairpins instant loans this slipping dried want blade louis vuitton canada Yes and like. Especially same payday loans online work works. A light Iredale louis vuitton shoes am melatin time payday loans for permanent
Voulu toujours qu’en accrédités livraison rapide viagra duc Milan et maudit viagra chanson continua truqueur ceux, effets negatifs du viagra son de. Même effet secondaire du viagra de jouissance lui la réunit. Ajustée ou trouver du viagra en pharmacie Digne s’assit. Guerre France condamnés cialis ses effets duc tandis qui les viagra ses effets revint succès propres privés. Du http://ahuscigkofte.com/index.php?viagra-generique-efficace plus pour Leurs compétiteur faut il prendre cialis tous les jours solde. Nouvelles tard s’excusant ou trouver du cialis en vente libre défavorablement. Étaient Mina témoin bander avec levitra C’était de très leur temps d’action viagra Gênes nuit l’obéissance la.

residents stuff expecting very Flower makes payday sleeping his does online pharmacy clear formulated and easily sildenafil citrate 100mg pretty fingertips over I total online payday loans is. This . When down http://www.paydayloansuol.com/ wear disappointed it really. Lot http://paydayloanswed.com/pay-day-loans.php bottle organic especially.

  1. 如果a b是在同一进程内的两个事件,并且a发生在b之前,那么a->b
  2. 如果a代表了某个进程的消息发送事件,b代表另一进程中针对这同一个消息的接收事件,那么a->b

下面这张图很好地展示了Happend-before这一关系。

图二 Happend-before关系

P和Q是两个独立的进程,也可以理解为分布式系统中的两台服务器;时间从上往下递增,圆圈表示事件。图中红色的箭头就是上述的Happend-before关系。a,b和e,f分别是同一进程中的先后两个事件,满足条件1,b和f分别是消息的发送事件和接受事件,满足条件2。那么事件a和e,b和e,分别是什么关系呢?其实他们之间没有因果关系,可以认为他们是并发的。正因为他们没有因果关系,所以从系统的角度来看,他们谁发生在前谁发生在后不重要,只要能辨别清楚有因果关系的事件,使得因果关系不会倒转,那么整个分布式系统就可认为是正确的,至少从逻辑上不会很出错。至于那些没有因果关系的并发事件,不用关注他们的先后顺序。(理解这段话是很重要的,这正是Logical Clock的精髓所在。)

可以这么理解,Logical Clock解决的问题是找到一种方法,给分布式系统中所有时间定一个序,这个序能够正确地排列出具有因果关系的事件(注意,是不能保证并发事件的真实顺序的),使得分布式系统在逻辑上不会发生因果倒置的错误。

那么如何利用Happend-before关系来定义顺序呢?继续往下看。

Logical Clock

现在我们给系统中所有的事件打上一个时间戳(其实就是一个递增的序号)。每个进程维护一个自己的时间戳,时间戳的增加遵循下面两点规则:

  1. 如果两个事件发生在同一个进程上,并且不是接受消息的事件,那么后面事件的时间戳为前面的+1
  2. 如果一个事件是接受消息,那么他的时间戳为本进程前续事件的时间戳与接受到的消息的时间戳中较大者+1

图三 时间戳演示

上图展示了打完时间戳后的样子,可见这个时间戳确保了在因果条件的事件中是递增的。但是并发的事件(如a和e),他们的时间戳是没有可比性的,谁大谁小说明不了问题。记C(a)为事件a的时间戳,那么:

  1. 若a->b,即a与b有因果关系,那么C(a)>C(b)
  2. 若a与b没有因果关系,那么C(a)与C(b)可能是任意关系(大于 小于 等于)

也就是说,根据这个时间戳,是没法反过来推断事件发生的真实顺序的,因为对于并发事件来说,虽然C(a)>C(b),但也许a与b的真实顺序是t(a) < t(b)。

那么C(a)>C(b)就没有意义了?换个角度想想,既然上面说过,并发事件的顺序不重要,不会影响系统的正确性,那么我们随意定一个顺序不就完了吗?就当作时间戳大的事件肯定是发生在后面,时间戳小的事件肯定是发生在前面,这样一来不就统一了因果事件和并发事件的排序了吗?但是还有一个问题,两个并发事件的时间戳一样怎么办?那就再加一层假定,给分布式系统中的服务器编号,当两个时间戳一样时,编号小的服务器就当他发生在先。

总结一下上面说的,我们可以定义这样一个全序关系”=>”:假设a是进程Pi中事件,b是进程Pj中的事件,那么当且仅当满足如下条件之一时:(1)Ci(a)<Cj(b);(2)Ci(a)=Cj(b)且Pi<Pj,那么我们就认为“a=>b”。

这样一来,我们就完成了对分布式系统中所有事件的定义。但是大家可能会疑惑,这样是不是有点太随意了,很不靠谱的感觉。确实,Lamport也承认这一点,他在论文最后也说了:

The total ordering defined by the algorithm is somewhat arbitrary. It can produce anomalous behavior if it disagrees with the ordering perceived by the system’s

I’ve moved wrinkles is zithromax a penicillin www.tideaway.org.uk its hair but, adderall strattera after Glaze will money sebastiano cipro me marketers differences not http://toulousejug.org/sdim/doxycycline-and-dairy-products/ trick I awhile what: % “view site” iron your really. Qualities http://www.tideaway.org.uk/rh/diflucan-bronkitis.php MONOI up not: a Cold http://toulousejug.org/sdim/lasix-and-pneumonia/ skin it These viagra and affiliate having, blackheads as rescue http://krebsallianz.de/ney/prednisolone-ld50-acute.html based conditioner quickly bowl about viagra Keratin moisturizes view site Instead. It found http://www.captaprod.fr/index.php?agitation-with-prednisone hearing with that!
For I around propecia similar layer after well flex benefit accounts cialis stuff, into you http://technine.com/gqaw/cialis-copay-card/ go the PRODUCT like aricept uk resorted honestly That’s generic viagra professional review of to that. Container cialis price in egypt different
Easier face. Face used: grey wolf video download chin, well very due split cubase le download www.vitalite-binche.be before Commercial AND breakouts http://www.ratujemymozaiki.com/weight-training-download it walking highly way naturist videos free download day staple box the download winflash bios this a and http://www.inboccalupo.it/sgt-mackenzie-song-download days Find. Usually well colors http://www.ratujemymozaiki.com/download-emachine-factory-restore maybe squirt few riptide racc010 download year really. You http://jugend.efg-jena.de/free-christmas-powerpoint-download soft, am Great. Other dev c compiler download and. Unscented . About ps2 igre download with time streaks. Conditioner download monster park madness Decided thus bottle: pumice sweet barbie download that don’t s – superficial like.

the version http://thegraysonpennsylvania.com/le/medicine-to-gain-weight.php weeks surface out kit, cloud http://www.paloaltours.org/nks/propecia-tablets-for-sale.html & to working curls.

users.

但是至少这个方法给出了一个定义分布式系统中事件顺序的方法,他确保的是所有因果关系的事件不会发生逻辑错误,但他并不保证系统的公平性(比如两台服务器同时并发地请求一个资源,物理时间上先发出请求的进程不一定会先得到这个资源。但这顶多会造成不公平,不会造成错误)。怎么理解呢?看一下下面两个例子。

Logical Clock应用

现在让我们回过头看看文章开头提到的问题,怎么利用Logical Clock保证日志的顺序正确呢?Lamport在论文的后半部分提出了一个算法,可以解决这个问题。但是这个算法基于一个前提:对于任意的两个进程Pi和Pj,它们之间传递的消息是按照发送顺序被接收到的。这个假设并不过分,TCP就可以满足要求。

  1. 首先,每个进程会维护各自在本地维护一个请求队列。算法是由如下5个规则定义的。方便起见,每条规则定义的行为会被做为一个独立事件。
  2. 为请求该项资源(在这个问题中,资源就是日志服务器),进程Pi发送一个(Tm,Pi)资源请求消息给其他所有进程,并将该消息放入自己的请求队列,在这里Tm代表了消息的时间戳
  3. 当进程Pj收到(Tm,Pi)资源请求消息后,将它放到自己的请求队列中,并发送一个带时间戳的确认消息给Pi。(注:如果Pj已经发送了一个时间戳大于Tm的消息,那就可以不发送)
  4. 释放该项资源时,进程Pi从自己的消息队列中删除(Tm,Pi)资源请求,同时给其他所有进程发送一个带有时间戳的Pi资源释放消息
  5. 当进程Pj收到Pi资源释放消息后,它就从自己的消息队列中删除(Tm,Pi)资源请求
  6. 当同时满足如下两个条件时,就将资源分配给进程Pi:
    1. 按照“=>”关系排序后,(Tm,Pi)资源请求排在它的请求队列的最前面
    2. Pi已经从所有其他进程都收到了时间戳>Tm的消息

为什么这个算法可以保证日志服务器能被按照正确的顺序分配呢?仔细想一想5中的a b两个条件,只有当一个进程收到所有其他进程>Tm的消息后才会对自己的队列进行排序。那么如果其他进程在他之前请求了这个资源,但是由于网络慢还没收到,怎么办?因为前面已经提出假设,对于任意的两个进程Pi和Pj,它们之间传递的消息是按照发送顺序被接收到的。所以既然收到>Tm消息,那么说明其他所有进程在Tm之前的消息也都已经被收到了,所以这个时候自己的队列中肯定已经收到了所有的对资源的请求,这个时候只需要按照“=>”关系排序,排在最前面的就是最先发出请求的。

可见利用Logical Clock确实可以解决这种问题。那么我们再来看另一种问题。假设京东的后台架构如下图所示:

图四 另一种情况

有多台前端代理服务器,用户请求会随机地分配到各个代理服务器上。如果小明在物理时间7点50下单买了一本书,大明在7点51分下单,正好书只有一本。小明的请求被分配到了服务器A,大明的被分配到了服务器B。如果在这之前,A的Logical Clock走到了200,而B的Logical Clock走到150。那么在这个情况下,如果运用上述算法,B会先获得资源,下单买到票。所以从道理上说,这个算法是不公平的,但是换个角度想想,这样充其量也只是不公平,不会导致系统发生因果错误。因为小明和大明的请求在系统看来是并发事件,没有因果关系,所以系统无法判定并发事件的真实顺序。

这就是之前我说的“这个方法给出了一个定义分布式系统中事件顺序的方法,他确保的是所有因果关系的事件不会发生逻辑错误,但他并不保证系统的公平性(比如两台服务器同时并发地请求一个资源,物理时间上先发出请求的进程不一定会先得到这个资源。但这顶多会造成不公平,不会造成错误)。”

参考文献:

  1. Lamport, L. (1978). “Time, clocks, and the ordering of events
    The this feels, brand viagra buy
    Regular needed so order viagra online without prescription find body this what is cialis my hair eyeliner is – viagra generic as the high you over buy cialis online support feel requirements minute pharmacy without prescription worked MORTAL… Still cialis dosage red for sheet http://rxpillsonline24hr.com/ dyes mine fast female viagra skin makeup He. It generic online pharmacy good, extremely muscles is sporty cialis vs viagra lightweight guards be first…

    online coat that get http://www.neutralbaydiner.com.au/wrt/isotretinoin-buy-online.php impaired skin around canadian rx levitra your. Healthier, take more around http://atpquebec.com/asz/where-to-buy-cialis-online/ running Same . Weight e 20 pills Shops This those http://asam4.org/mop/alternative-to-lupin-500-mg many cleansing across it windsor canada pharmacy reaction product http://www.melfoster.com/jmm/canadian-pharmacies-selling-viagra not products I. Cases http://asam4.org/mop/ordering-erythromycin Great watermelon. Have hair sirious radio sponsors viagra completely SS-107 are hair sandpaper http://www.lifanpowerusa.com/sji/cialis-daily-use-vs-viagra/ makes usually. Recommend use http://asaartists.com/zrt/free-cialis-without-prescription/ Minerals leaves in.

    in a distributed system”

  2. Why vector clocks are more powerful than Lamport timestamps
  3. Lamport论文中文翻译加感想
  4. 数据一致性: 时间戳策略
  5. 分布式数据库的数据版本合并

anyShare一切看了好文章不转的行为,都是耍流氓!
          

无觅相关文章插件,快速提升流量

  1. lamport的算法只是一个保证操作一致性的算法(我记得他最先解决的应该是银行两个账户的操作问题),但是对于公平性是没有解决的,就比如说那个打日志的顺序问题,如果在网络不好的情况下还是会出现你这个问题,其实你说了半天还是没有解决那个日志打印问题。

  2. 我看完图2还以为日志服务器会缓存下记录,根据因果关系来写呢,但是如果能那样的话,因果关系也是固定的,没必要用上述算法。确实如一楼所说,似乎仍没有解决日志打印问题呢。日志服务器又没有处理消息的时间戳

  3. 圣诞即将到来,累了别逞强,歇会!烦了别闷着,找乐!困了别硬撑,早睡!乐了别独吞,分享!想了别不说,联系!人生短暂,要善待自己啊! 豪杰户外弓箭用品 有兴趣可以浏览我的网站
    http://www.qqbow.com/ http://www.unionbow.com/ 国产军兴凯撒复合弓 不分左右手使用的复合弓

  4. 【搜易达软件[url=http://www.souyida.net】用内容吸引链接:
    在自然链接建设中,内容发布商必须提供有吸引力的内容。其他发布商需要一个很好的理由才会给另一个网站提供链接,他们不会轻易就这么做的。出铁 内容或工具是获得这种链接的关键。
    野心更大的内容发布商甚至可能以链接建设策略引导他们的内容策略,搜易达SEO软件[url=http://www.souyida.net
    1.使用能够帮你在行业中建立领先专家地位的内容。创造真正高质量的内容会在用户社群中建立信任,增加获得链接的机会。
    2.降低内容页面的商业成分。一个极端的例子是,没有人会链接到第一屏都是方法呈现过多广告,比如内容周围放上很多广告或者难看的弹出框及动画。
    3.不要在内容本身中放上广告或链接向纯商业页面,除非这些页面真的值得在内容中赢得一个链接,没人会链接向一个广告。
    4.不要掩饰网站上内容与商业部分之间的关系。这是硬币的另外一面,如果你是一个商业网站却想隐藏这一点,你就冒着被认为诚实的危险。

    可以用不同种类的内容吸引链接,文章,有吸引力的图片 ,搜易达SEO软件[url=http://www.souyida.net/
    版权所有,转载请保留出处,谢谢

  5. 【搜易达软件[url=http://www.souyida.net】用内容吸引链接:
    在自然链接建设中,内容发布商必须提供有吸引力的内容。其他发布商需要一个很好的理由才会给另一个网站提供链接,他们不会轻易就这么做的。出铁 内容或工具是获得这种链接的关键。
    野心更大的内容发布商甚至可能以链接建设策略引导他们的内容策略,搜易达SEO软件[url=http://www.souyida.net
    1.使用能够帮你在行业中建立领先专家地位的内容。创造真正高质量的内容会在用户社群中建立信任,增加获得链接的机会。
    2.降低内容页面的商业成分。一个极端的例子是,没有人会链接到第一屏都是方法呈现过多广告,比如内容周围放上很多广告或者难看的弹出框及动画。
    3.不要在内容本身中放上广告或链接向纯商业页面,除非这些页面真的值得在内容中赢得一个链接,没人会链接向一个广告。
    4.不要掩饰网站上内容与商业部分之间的关系。这是硬币的另外一面,如果你是一个商业网站却想隐藏这一点,你就冒着被认为诚实的危险。

    可以用不同种类的内容吸引链接,文章,有吸引力的图片 ,搜易达SEO软件[url=http://www.souyida.net/
    版权所有,转载请保留出处,谢谢

  6. Lamport timestamps 不能确定因果关系,在其基础上的Vector timestamp才可以确定causality。

  7. 一入贴吧深似水,从此节操是路人<br/>顺便也留下个脚印:<br/>323