Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1082647
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类: 云计算

2011-02-27 11:07:34

时间是我们考虑问题时使用的基本概念之一。在我们观察、理解或设计一个分布式系统/协议时,也常常使用这个概念。我们常常会说“在xxx时候做xxx”或者“在xxx之后做xxx”。事实上,在一个系统中,我们绝大多数时候并不关心某个事件发生的绝对时间,而是关心事件之间的相对时间,相对顺序。对系统中的时间做较早研究的一篇文章是Lamport在1978年发表的“Time,Clocks,and the Ordering of Events in a Distributed System”。昨天阅读了这篇文章。文章的表述很直白,概念也相对简单。但正是这种简单的概念,构成了系统时间的基础。


    在本文中,我们假设系统中的进程都是单线程的,这样,在一个进程中发生的所有事件,是有一个该进程可知的全序的。注意,这里“事件”的粒度是根据应用环境而定的,可以细到一条汇编,也可以大到“把1P的数据传输完”或“计算出这个1T*1T的矩阵求逆”。本文仅仅定义两个事件:消息的发送事件、消息的接收事件,其它具体的事件应该根据应用程序来定义。如果要把这些概念扩展到支持多线程的进程,方法十分直接。

    时间的概念是基于更加基础的“顺序”概念的。例如,我们说某事发生在3:15,指的是这件事发生在时钟读数在3:15之后,并且在时钟读数在3:16之前。如前文所说,很多时候,我们关心的只是事件发生的顺序。例如,当设计数据库的事务时,必须保证在一个进程发起的事务commit之后,别的进程的数据库访问才能“看到”这个事务的修改,在commit之前,别的进程完全不可知这个事务,而至于这个事务是几点commit的,我们并不是十分关心。基于对这种情况的理解,Lamport在本文中定义的一个最为基本的概念是一个偏序“happened before”(使用符号“->”表示):

    “->”是在一个系统的事件集合E(假设a,b,c属于E)上定义的,满足以下三个条件的最小的关系:

    1. 如果a和b发生在同一个进程中,且在该进程中,a在b之前发生,那么:a -> b;

    2. 如果a是进程Pi发出消息m,而b是进程Pj接收到这个消息m,那么:a -> b;

    3. 如果a -> b, b -> c,那么:a -> c;

    注意,对于任何一个事件a,a -> a都是不成立的,也就是说,关系->是反自反的。有了上面的定义,我们也可以定义出“并发”(concurrent)的概念了:

    对于事件a、b,如果a -> b,b -> a两个都不成立,那么a和b就是并发的。

    直观上,上面的->关系非常好理解,即“xxx在xxx之前发生”。也就是说,一个系统在输入I1下,如果有a->b,那么对于这个系统的同一个输入I1,无论重复运行多少次,a也始终发生在b之前;如果在输入I1下a和b是并发的,则表示在同一个输入I1下的不同运行中,a可能在b之前,也可能在b之后,也可能恰好同时发生。也就是,并发并不是指一定同时发生,而是表示一种不确定性。->和并发的概念,就是我们理解一个系统时最基础的概念之一了。


    有了上面的概念,我们可以给系统引入时钟了。这里的时钟就是lamport逻辑时钟。一个时钟,本质上是一个事件到实数(假设时间是连续的)的函数。这个函数将每个事件映射到一个数字,代表这个事件发生的时间。形式一点来说,对于每个进程Pi,都有一个时钟Ci,这个时钟将该进程中的事件a映射到Ci(a)。而整个系统的时钟C=,对于一个事件b,假设b属于进程Pj,那么C(b) = Cj(b)。

    这里插一句,从这个定义也可以看到大师对分布式系统的理解。分布式系统中不存在一个“全局”的实体。在该系统中,每个进程都是一个相对独立的实体,它们有自己的本地信息(本地Knowledge)。而整个系统的信息则是各个进程的信息的一个聚合。

    有了时钟的一个“本质定义”还不够,我们需要考虑,什么样的时钟是一个有意义的,或者说正确的时钟。其实,有了前文的->关系的定义,正确的时钟应满足的条件已经十分明显了:

    时钟条件:对于任意两个事件a,b,如果a -> b,那么C(a) < C(b)。

    注意,反过来讲这个条件可不成立。如果我们要求反过来也成立,即“如果a -> b为假,那么C(a) < C(b)也为假”,那就等于要求并发事件必须同时发生,这显然是不合理的。

    结合前文->关系的定义,我们可以把上面的条件细化成如下两条:

    1. 如果a和b是进程Pi中的两个事件,并且在Pi中,a在b之前发生,那么Ci(a) < Ci(b);

    2. 如果a是Pi发送消息m,b是Pj接收消息m,那么Ci(a) < Cj(b);

    上面就定义了合理的逻辑时钟。显然,一个系统可以有无数个合理的逻辑时钟。实现逻辑时钟也相对简

单,只要遵守两条实现规则就可以了:

    1. 每个进程Pi在自己的任何两个连续的事件之间增加Ci值;

    2. 如果事件a是Pi发送消息m,那么在m中应该带上时间戳Tm=Ci(a);如果b是进程Pj接收到消息m,那么,进程Pj应该设置Cj为大于max(Tm, Cj(b))。


    有了上面逻辑时钟的定义,我们现在可以为一个系统中所有的事件排一个全序,就是使用事件发生时的逻辑时钟读数进行排序,读数小的在先。当然,此时可能会存在两个事件同时发生的情况。如果要去除这种情况,方法也非常简单:如果a在进程Pi中,b在进程Pj中,Ci(a) = Cj(b)且i < j,那么a在b之前。形式化一点,我们可以把系统事件E上的全序关系“=>”定义为:

    假设a是Pi中的事件,b是Pj中的事件,那么:a => b当且仅当以下两个条件之一成立:

    1. Ci(a) < Cj(b);

    2. Ci(a) = Cj(b) 且 i < j;


    在本文中Lamport给出了一个系统中时间的基本概念。这些概念是理解一个系统中的同步、一致性等问题的基础。在本文中,作者也提到了,如何在系统中同步一组物理时钟,以及同步的精度。这个部分还没有仔细看,以后有机会再看吧。

阅读(11027) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~