免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2643 | 回复: 1

分布式系统中的时序——Lamport逻辑时钟 [复制链接]

论坛徽章:
0
发表于 2011-12-19 13:54 |显示全部楼层
<p>时间是我们考虑问题时使用的基本概念之一。在我们观察、理解或设计一个分布式系统/协议时,也常常使用这个概念。我们常常会说“在xxx时候做xxx”或者“在xxx之后做xxx”。事实上,在一个系统中,我们绝大多数时候并不关心某个事件发生的绝对时间,而是关心事件之间的相对时间,相对顺序。对系统中的时间做较早研究的一篇文章是Lamport在1978年发表的“Time,Clocks,and the Ordering of Events in a Distributed System”。昨天阅读了这篇文章。文章的表述很直白,概念也相对简单。但正是这种简单的概念,构成了系统时间的基础。</p><p><br></p><p>&nbsp; &nbsp; 在本文中,我们假设系统中的进程都是单线程的,这样,在一个进程中发生的所有事件,是有一个该进程可知的全序的。注意,这里“事件”的粒度是根据应用环境而定的,可以细到一条汇编,也可以大到“把1P的数据传输完”或“计算出这个1T*1T的矩阵求逆”。本文仅仅定义两个事件:消息的发送事件、消息的接收事件,其它具体的事件应该根据应用程序来定义。如果要把这些概念扩展到支持多线程的进程,方法十分直接。</p><p>&nbsp; &nbsp; 时间的概念是基于更加基础的“顺序”概念的。例如,我们说某事发生在3:15,指的是这件事发生在时钟读数在3:15之后,并且在时钟读数在3:16之前。如前文所说,很多时候,我们关心的只是事件发生的顺序。例如,当设计数据库的事务时,必须保证在一个进程发起的事务commit之后,别的进程的数据库访问才能“看到”这个事务的修改,在commit之前,别的进程完全不可知这个事务,而至于这个事务是几点commit的,我们并不是十分关心。基于对这种情况的理解,Lamport在本文中定义的一个最为基本的概念是一个偏序“happened before”(使用符号“-&gt;”表示):</p><p>&nbsp; &nbsp; “-&gt;”是在一个系统的事件集合E(假设a,b,c属于E)上定义的,满足以下三个条件的最小的关系:</p><p>&nbsp; &nbsp; 1. 如果a和b发生在同一个进程中,且在该进程中,a在b之前发生,那么:a -&gt; b;</p><p>&nbsp; &nbsp; 2. 如果a是进程Pi发出消息m,而b是进程Pj接收到这个消息m,那么:a -&gt; b;</p><p>&nbsp; &nbsp; 3. 如果a -&gt; b, b -&gt; c,那么:a -&gt; c;</p><p>&nbsp; &nbsp; 注意,对于任何一个事件a,a -&gt; a都是不成立的,也就是说,关系-&gt;是反自反的。有了上面的定义,我们也可以定义出“并发”(concurrent)的概念了:</p><p>&nbsp; &nbsp; 对于事件a、b,如果a -&gt; b,b -&gt; a两个都不成立,那么a和b就是并发的。</p><p>&nbsp; &nbsp; 直观上,上面的-&gt;关系非常好理解,即“xxx在xxx之前发生”。也就是说,一个系统在输入I1下,如果有a-&gt;b,那么对于这个系统的同一个输入I1,无论重复运行多少次,a也始终发生在b之前;如果在输入I1下a和b是并发的,则表示在同一个输入I1下的不同运行中,a可能在b之前,也可能在b之后,也可能恰好同时发生。也就是,并发并不是指一定同时发生,而是表示一种不确定性。-&gt;和并发的概念,就是我们理解一个系统时最基础的概念之一了。</p><p><br></p><p>&nbsp; &nbsp; 有了上面的概念,我们可以给系统引入时钟了。这里的时钟就是lamport逻辑时钟。一个时钟,本质上是一个事件到实数(假设时间是连续的)的函数。这个函数将每个事件映射到一个数字,代表这个事件发生的时间。形式一点来说,对于每个进程Pi,都有一个时钟Ci,这个时钟将该进程中的事件a映射到Ci(a)。而整个系统的时钟C=&lt;C0, C1, ..., Cn&gt;,对于一个事件b,假设b属于进程Pj,那么C(b) = Cj(b)。</p><p>&nbsp; &nbsp; 这里插一句,从这个定义也可以看到大师对分布式系统的理解。分布式系统中不存在一个“全局”的实体。在该系统中,每个进程都是一个相对独立的实体,它们有自己的本地信息(本地Knowledge)。而整个系统的信息则是各个进程的信息的一个聚合。</p><p>&nbsp; &nbsp; 有了时钟的一个“本质定义”还不够,我们需要考虑,什么样的时钟是一个有意义的,或者说正确的时钟。其实,有了前文的-&gt;关系的定义,正确的时钟应满足的条件已经十分明显了:</p><p>&nbsp; &nbsp; 时钟条件:对于任意两个事件a,b,如果a -&gt; b,那么C(a) &lt; C(b)。</p><p>&nbsp; &nbsp; 注意,反过来讲这个条件可不成立。如果我们要求反过来也成立,即“如果a -&gt; b为假,那么C(a) &lt; C(b)也为假”,那就等于要求并发事件必须同时发生,这显然是不合理的。</p><p>&nbsp; &nbsp; 结合前文-&gt;关系的定义,我们可以把上面的条件细化成如下两条:</p><p>&nbsp; &nbsp; 1. 如果a和b是进程Pi中的两个事件,并且在Pi中,a在b之前发生,那么Ci(a) &lt; Ci(b);</p><p>&nbsp; &nbsp; 2. 如果a是Pi发送消息m,b是Pj接收消息m,那么Ci(a) &lt; Cj(b);</p><p>&nbsp; &nbsp; 上面就定义了合理的逻辑时钟。显然,一个系统可以有无数个合理的逻辑时钟。实现逻辑时钟也相对简</p><p>单,只要遵守两条实现规则就可以了:</p><p>&nbsp; &nbsp; 1. 每个进程Pi在自己的任何两个连续的事件之间增加Ci值;</p><p>&nbsp; &nbsp; 2. 如果事件a是Pi发送消息m,那么在m中应该带上时间戳Tm=Ci(a);如果b是进程Pj接收到消息m,那么,进程Pj应该设置Cj为大于max(Tm, Cj(b))。</p><p><br></p><p>&nbsp; &nbsp; 有了上面逻辑时钟的定义,我们现在可以为一个系统中所有的事件排一个全序,就是使用事件发生时的逻辑时钟读数进行排序,读数小的在先。当然,此时可能会存在两个事件同时发生的情况。如果要去除这种情况,方法也非常简单:如果a在进程Pi中,b在进程Pj中,Ci(a) = Cj(b)且i &lt; j,那么a在b之前。形式化一点,我们可以把系统事件E上的全序关系“=&gt;”定义为:</p><p>&nbsp; &nbsp; 假设a是Pi中的事件,b是Pj中的事件,那么:a =&gt; b当且仅当以下两个条件之一成立:</p><p>&nbsp; &nbsp; 1. Ci(a) &lt; Cj(b);</p><p>&nbsp; &nbsp; 2. Ci(a) = Cj(b) 且 i &lt; j;</p><p><br></p><p>&nbsp; &nbsp; 在本文中Lamport给出了一个系统中时间的基本概念。这些概念是理解一个系统中的同步、一致性等问题的基础。在本文中,作者也提到了,如何在系统中同步一组物理时钟,以及同步的精度。这个部分还没有仔细看,以后有机会再看吧。</p>

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
发表于 2011-12-19 13:54 |显示全部楼层
倒萨
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP