分布式系统 – 逻辑时钟

1. 逻辑时钟的动机

1.1 基本概念

在分布式系统中物理时钟不能完美的同步

计算机时钟的主要作用 – 排序事件:

  • 如果两个进程不需要交互,就没有需要同步时钟
  • 这个观察导致“因果性”

1.2 因果性:

  • 使用之后发生 \rightarrow 关系来排序事件:
    • $a \rightarrow b$:$a$ 能够影响 $b$ 的结果
    • $a || b$:
      • $a$ 和 $b$ 出现在不同进程中,并不交换数据
      • 其相对顺序并不重要
  • happened-before 的定义
    • 如果a和b位于同一进程,ab 之后,则 a \rightarrow b
    • 如果a和b出现在不同进程,a 是发送方,b 是对应(corresponding)的接收方,那么 a \rightarrow b
    • 传递性(transitive):如果 a \rightarrow b ,b \rightarrow ca \rightarrow c
  • 偏序 – 无序事件时并发的

2. 逻辑时钟

  • 概念:逻辑时钟是单调(monotonically)增长的软件计数器;它不需要物理时钟;校正之只能使之增长,而不能减少
  • 规则:如果 a \rightarrow b, clock(a);按此规则向事件赋予时间

3. 兰伯特(Lamport)算法,1978

3.1 算法:每个线程 P_i 有一个逻辑时钟 L_i,时钟同步算法:

  • $L_i$ 被初始化为$0$;
  • 更新 L_i:
    • $LC1$:$L_i$ 当新的事件在$P_i$ 发生的时候增长1;
    • $LC2$:当$P_i$ 发送一条消息$m$,将$t=L_i$附加到$m$上去;
    • $LC3$:当$P_j$ 接收$(m,t)$时,它设置$L_j≔max⁡{L_j,t}$,并且应用$LC1$的规则再次为事件$receive(m)$增加$L_j$;
      iii.

3.2 问题:

  • 相同的时间戳
    • 描述:并发的事件可能有相同的时间戳
    • 解决:在时钟值后追加线程ID(或者系统ID)
  • 检测因果(causal)关系
    • 算法:
      • 如果a \rightarrow b,那么L(a),然而:
      • 如果 L(a),并不表示 a \rightarrow b
    • 解决:使用向量时钟法

4. 向量时间戳法

4.1 概念:

假设有一群人,每个都需要追踪发生于其他人的事件

解决:需要有向量时间戳

4.2 算法:每个进程 P_i 保持一个时钟 V_i ,向量有 N 维:

  • 初始化:for 1 ≤ i ≤ N\ and\ 1 ≤ k ≤ N, V_i [k]≔0
  • 更新 V_i:
    • $VC1$:当其为 $P_i$ 进程的新事件时,设置 $V_i [i]≔V_i [i]+1$
    • $VC2$:当 $P_i$ 发送消息 $m$,它将 $t=V_i$ 附加到 $m$ 上
    • $VC3$:当 $P_j$ 接收到 $(m,t),for\ 1≤k≤N,it\ set\ V_j [k]≔max⁡[{V_j [k], t[k]}]$,并运用$VC1$来增长$V_j [j]$
  • 注意:V_i [j] 是一个时间戳,指示(indicating)P_i 知道发生在 P_j 至此的所有事件。

  • 使用事件向量检测 或者 || 事件

    • 规则:
      • 只有每一维度都相等时,才相等,否则按照数值规则计算(此处不可能出现交叉)
      • 对任何两个事件 a 或者 b
        • V(a) 时,a≠b,则 a→b
        • 当没有 V(a)≤V(b) 也没有 V(a)≥V(b) 时,a || b
  • 一个时间戳向量的用法:因果排序多播
    • 算法:每个组成员维持一个 N 维度时间戳向量,全都初始化为 0
      • P_i 多播一个消息 m,其增长 V_i [i] 并将之附加到 m
    • 保留因果顺序
      • 如果 m_1→m_2m_1 会在 m_2 之前被所有接受者接收
      • 如果 m_1 || m_2m_1m_2 可以被接受者随意的接收
      • 全序组播:m_1m_2 必须被所有的接受者以相同的顺序接收
Tagged with:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据