95702-Ch 14 Time and Global States

分布式系统中时间异步的一些解决算法

作者 QIFAN 日期 2016-12-05
95702-Ch 14 Time and Global States

一、名词介绍

  1. $p_i$ ,$s_i$, $e_i$, $->_ie’$
    一个分布式系统中包括含有 N 个进程(process)$p_i$, $i=1,2,..N$ 的集合。每个进程 $p_i$ 都有一个状态 $s_i$。进程之间除了通过发送信息的方式外不能交流。对于每个进程 $p_i$ ,只能进行发送接收或者改变 $p_i$ 状态的操作。一个事件(event)代表 $p_i$ 执行的一个动作。$e ->_ie’$ 关系成立当且仅当在 $p_i$ 中事件 $e$ 发生在 $e’$ 之前。
  2. 历史(history):一个进程 $p_i$ 的历史(history)代表了该进程内发生的,并按照 $->_i$ 关系排序的一系列事件:
    $history(p_i)=h_i = <e_i^0, e_i^1, e_i^2, …>$
  3. 时钟偏移(clock skew): 是指两个时钟的自然偏差。
  4. 时钟漂移(clock drift): 是指时不同时钟对时间的计算速率不同。
  5. 外部同步(external synchronization):将本机时间直接与外部某个权威的时钟同步在一个范围内。即对于一个同步时间范围 $D < 0$ ,对于某个来源 $S$ 的 UTC 时间,$|S(t)-C_i(t)|<D$, $i=1,2,..,N $
    也可以说时钟 $C_i$ 在范围 $D$ 内准确。
  6. 内部同步(internal synchronization):如果系统中的时钟 $C\_i, i=1,2,..N$ 相互间在一个可接受范围内同步,则可以直接以本地显示时间来测量两个事件的间隔。
    即对于一个同步时间范围 $D > 0$ ,对于某个来源 $S$ 的 UTC 时间,$|C_i(t)-C_j(t)|<D, i=1,2,..N$ 。也可以说时钟 $C_i$, $i=1,2,…N$ 在范围 $D$ 内一致。
  7. 正确性:如果一个实体时钟 H(比如说一个石英钟)的漂移(drift)比率在一个已知范围 $ρ>0$ 内,则表示时钟准确。
    即对于真实时间 $t$, $t’(t’>t)$ :
    $(1-ρ)(t’-t)<=H(t’)-H(t)<=(1+ρ)(t’-t)$
  8. Faulty:时钟不准确
  9. Crash failure:时钟停止
  10. 先于发生(happens-before):用 –> 表示。有如下假设:

    • 对于进程 $p_i$: $e -> _ie’$, 则 $e –> e’$
    • 对于任何信息 m, 发送消息先于接受消息。即 $send(m) –> receive(m)$
    • 如果 $e –> e’$, $e’ –>e’’$, 则 $e –>e’’$
  11. Linearization run:指全局历史中一系列事件发生的顺序都遵循先于发生(happens-before)关系。

  12. 一致切割(consistent cut):对事件进行切割,若切割线前的事件均发生与切割线后的事件前,则为一致切割。否则则为非一致切割。

  13. $s_i^k$, $H$, $S$:$s_i^k$ 表示进程 $p_i$ 在第 k 个事件发生之前的状态。$H$ 代表全局历史,$H=h_0∨h_1∨…∨h_{N-1}$ 。$S$ 是所有状态的集合,即 $S=(s_1,s_2,…,s_N)$

二、Cristian同步时间方法

  • 前提:
    1. 传输时间足够短
    2. 时钟漂移速率小
  • 过程:
    1. 进程 p 在本地时间 $t_1$ 向要同步的时钟发送一条消息 m
    2. 时钟在本地时间 $t_2$ 收到消息
    3. 时钟在本地时间 $t_3$ 回复消息给 p
    4. p 在本地时间 $t_4$ 收到消息
  • 计算:
    1. 消息来回所需时间 $T_{round} = t_4-t_1-($t_3-t_2)$
    2. p 应调整时间为 $t_3+T_{round}/2$ (因为传输时间够小,所以近似将来去时间看成相等)

三、网络时间协议(NTP)

  1. 设计目标
    • 提供一个精准同步 UTC 的服务
    • 即使在部分连接缺失的情况下依然可靠
    • 提供保护
  2. 例子 图中每个圆圈代表一个节点,每个节点只向其父节点同步。若根节点 1 崩了,其中一个 2 便会自动成为新的根节点。
  3. 同步方式:NTP 服务器有三种同步方式:广播(multicast),进程调用(procedure-call)与同步(symmetric)模式。
    • 广播:这个模式适用于高速 LAN 网络,精度较低,但对于日常已经够用了。
    • 进程调用:类似于 Cristian 的同步方法,服务器接受来自其他节点的请求并回复自己的时间戳。适用于时间精度要求更高的情景,或者 LAN 不适用的情景。
    • 同步模式:节点直接向最低层的节点(接近上图中的根节点)进行请求,精度最高。

四、逻辑时间

逻辑时钟

能够逐个捕捉按照“先于发生”排序的各个事件。由 Lamport 在 1978 年发明。每个进程 $p_i$ 有自己的逻辑时钟,$L_i$,用以记录事件发生的时间戳(逻辑时间)。$L_i(e)$ 代表在进程 $p_i$ 发送的事件 $e$ 的时间戳。逻辑时钟是持续增长的,并以如下规则进行更新:
1) 每当进程 $p_i$ 有事件发生,$L_i=L_i+1$
2a) 当进程 $p_i$ 发送消息 m ,在信息后标记时间为 $t=L_i$
2b) 当进程 $p_j$ 收到消息 $(m, t)$,$p_j$ 比较 $max(L_j, t)$,并按照第一条规则记录时间并将其记为事件 $receive(m)$ 的时间戳。

通过上述规则,分别可以算出事件 a, b, c, d, e, f 的逻辑时间(标注在字母上方),可看出 $e–>e’=>L(e)–>L(e’)$,但反之并不成立,如 a 与 e 的时间都为 1,但我们无法判断它们的先后。

向量时钟

克服了 Lamport 逻辑时钟的缺点:对于 $L(e) > L(e’)$ 无法推断 $e ->e’$ 。即可以用事件的向量时钟来反应事件发生的顺序。说白了,逻辑时钟用一个数字来代表时间,而向量时钟用一个数组来代表时间,一个有 N 个进程的系统,其向量时钟的数组长度就为 N 。 $V_i$ 表示进程 $p_i$ 的向量时钟。同逻辑时钟一样是持续增长的,按如下规则更新:

  • 初始状态,$V_i[j]=0$,$i,j=1,2,…,N$
  • 在进程 $p_i$ 标记时间 $e$ 的时间戳前,设置 $V_i[j]:=V_i[j]+1$
  • $p_i$ 在每次发送的消息中加上 $t=V_i$
  • 当 $p_i$ 收到一个消息的时间戳 $t$,设置 $V_i[j]:=max(V_i[j],t[j])$,$j=1,2,..,N$

以下图为例说明。

  • 事件 a :上一进程为初始。进程 1 部分加 1 。$(0,0,0) ->(V_1[1]+1=1)->(1,0,0)$
  • 事件 b :上一进程为 a 。进程 1 部分加 1 。$a(1,0,0)-> (V_1[1]+1=1+1=2)->(2,0,0)$
  • 事件 c :上一进程为 b 。进程 2 部分加 1 。$b(2,0,0)-> (V_2[2]+1=0+1=1)->(2,1,0)$
  • 事件 d :上一进程为 c 。进程 2 部分加 1 。$c(2,1,0)->(V_2[2]+1=1+1=2)->(2,2,0)$
  • 事件 e :上一进程为初始。进程 3 部分加 1 。$(0,0,0)->(V_3[3]+1=0+1=1)->(1,0,0)$
  • 事件 f :上一进程为 d 。进程 3 部分加 1 。$(2,2,0)->(V_3[3]+1=0+1=1)->(2,2,1)$

比较规则:

  • $V=V’$ $iff$ $V[j]=V’[j]$, $j=1,2,…,N$
  • $V<=V’$ $iff$ $V[j]<=V’[j]$, $j=1,2,…,N$
  • $V<V’$ $iff$ $V<=V’Λ V≠V’$

五、’snapshot’ 算法

snapshot 算法由 Chandy 和 Lamport 于 1985 年发明,用于判断分布式系统的全局状态。
对于每个进程 $p_i$,都有两条通道:进入通道(消息进入)和离开通道(消息发出)。每个进程记录每个通道的任何,它(进程)记录自己状态后和发送者记录自己状态前的所有消息。
标记消息(marker):有两个作用。
(1)提示接收到 marker 的进程开始快照,若其还没有开始记录。
(2)决定消息属于哪个通道的状态。

有以下前提:

  • 没有通道或者进程失败,也就是所有信息都能正常收发。
  • 通道是单向的且采用“先进先出”处理机制。
  • 两两进程间都有通道相连
  • 任何进程都可以在任何时间初始化快照(snapshot)
  • 进程在快照发生时,消息的收发不受影响。

过程举例:

  1. 初始状态,$p_1$ 有 2 个星星 1 个三角 1 个圆, $p_2$ 有 2 个三角 1 个圆, $p_3$ 有 1 个星星 2 个圆
  2. $p_1$ 从外部收到一个标记 M ,按照规则,记录下 $p_1$ 当前的状态:2 星星 1 三角 1 圆。
  3. $p_1$ 先向 $p_2$ 与 $p_3$ 发送标记(标记必须发生在发送其他消息之前),再发送若干其他消息。 此时 $p_3$ 向 $p_1$ 发送了 1 圆,向 $p_2$ 也发送了 1 圆。
  4. $p_1$ 从 $C_31$ 收到 1 圆,记录状态。$p_2$ 先从 $C_32$ 收到 1 圆,再从 $C_12$ 收到标记,关闭 $C_12$ ,开始快照,此时状态为 2 三角 2 圆。$p_3$ 也从 $C_13$ 收到了标记,关闭 $C_13$,开始快照,此时状态为 1 星星。
  5. $p_2$ 分别向 $p_1$,$p_3$ 发送标记,$p_3$ 又向 $p_2$ 发送了 1 星。
  6. $p_1$ 分别从 $C_31$,$C_21$ 收到了标记,此时 $p_1$ 进入通道都已经关闭,$p_1$ 停止快照,状态定格。同样的,$p_2$ 从 $p_3$ 收到了标记,进入通道都已经关闭。$p_3$ 同理。至此,所有进程的快照都已经结束,将每个进程的状态相加,共有 3 星 3 三角 4 圆,这正是全局状态。

另一种生动有趣的解说请参照小明同学:CMU 95702 - SnapShot算法