Distributed System

分布式系统概念与设计读书笔记-时间与全局状态

Posted by keys961 on August 18, 2018

1. 时钟、事件和进程状态

1.1. 定义

设有一个分布式系统有$n$个进程$p_i$($i = 1, 2, … , n$)，该集合记为$P$

每个进程$p_i$有各自的状态$s_i$

每个进程$p_i$在不同的处理器上运行，处理器之间不共享内存

1.2. 事件顺序与历史

a) 事件顺序：

每个进程$p_i$的事件序列可以用全序方式排列。假定事件$e$在事件$e’$前发送，则两事件有$\rightarrow_i$关系，即$e \rightarrow_i \space e’$

b) 事件历史：

一个进程$p_i$的事件历史定义为：

$history(p_i) = h_i = <e_i^0, e_i^1, …>$ （每个事件按照$\rightarrow_i$关系排序）

1.3. 时钟

每个机器都有自己独立的硬件时钟，假设当前实际时间为$t$，对于进程$p_i$:

  • 读取的硬件时钟值为：$H_i(t)$
  • 产生的软件时钟值为：$C_i(t) = \alpha H_i(t) + \beta$ （对硬件时钟放大，并添加偏移量以接近实际实际$t$，一般而言$C(t) ≠ t$）

时钟分辨率：物理时钟值的更新周期

1.4. 时钟偏移和时钟漂移

a) 时钟偏移

即在实际时间$t$下，两时钟读数不同，即$H_i(t) ≠ H_j(t)$

b) 时钟漂移

在某时间点，两时钟初始值一致，但过一段事件后，两时钟读值不同

时钟漂移率：由参考时间度量的每个单位时间内，时钟与名义上的参考时钟之间的偏移量（如11.6天有1秒的偏差）

1.5. 通用协调时间（UTC）

是国际计时的标准，基于原子时间

2. 同步物理时钟

外部同步：设有同步范围$D>0​$，UTC时间源为$S​$，当前实际时间为$t​$，则满足$\vert S(t)-C_i(t)\vert<D​$，其中$i=1,2,…,n​$

内部同步：设有同步范围$D>0$，当前实际时间为$t$，则满足$\vert C_i(t)-C_j(t)\vert <D$，其中$i,j=1,2,…,n$

时钟正确性：一个物理时钟的漂移率在范围$\rho>0​$之内，则是正确的

这表明硬件读数的间隔误差是有界的，即：

$(1-\rho)(t’-t) \le H(t’) - H(t) \le (1 + \rho)(t’ - t)$，这里$t$

单调性原则：保证$t’ \gt t \Rightarrow C(t’) \gt C(t)​$

故障：不满足时钟正确性条件的时钟就是故障的，分为2类

  • 崩溃故障：时钟完全停止滴答
  • 随机故障：其它的时钟故障

2.1. 同步系统中的同步

同步系统中，同步的消息message被标记为$t$, 传输时间有上界$t_{max}$

则不确定性为$u = t_{max} - t_{min}$，接收方可设置自己的时间为$t + \alpha$（如$\alpha = u/2$）

同步$n$个时钟，最优的时间偏移为$u(1 - 1/n)$。

2.2. 同步时钟的Cristian方法

使用一个时间服务器（连接到UTC设备），实现外部同步。客户请求时间服务器以获取时间。条件是：客户与服务器之间的往返时间与所要求的精度相比要足够短。

客户端向服务器发送req,然后服务器返回的resp中被标记为$t$并返回，整个往返时间为$t_{round}$，单个传输的时间最短值为$t_{min}$, 则服务器的时钟时间位于范围$[t+t_{min}, t+t_{round}-t_{min}]$，即精度为$\pm (t_{round}/2 - t_{min})$

会出现假冒时间应答、无法处理时钟出错的问题。

2.3. Berkeley算法

一种内部同步的算法。

集群中选取一台协调者作为master，它定期轮询其它要同步时钟的机器（称为slave），slave返回时钟值给master。根据2.2.类似的方法，派出错误的读数，计算到一个容错平均值，最后返回给slave时钟的调整量（可正可负）。

若master故障，选举另一台机器接管master。

2.4. 网络时间协议（NTP）

目标：提供服务使互联网用户与UTC同步，服务可靠，提供保护以防止对时间服务的干扰

服务网结构：树形，层次结构。故障时同步子网可重配置。

  • 主服务器：与UTC源同步（作为根）
  • 二级服务器：与主服务器同步

同步方式（准确性由低到高）：

  • 组播
  • 过程调用模式：类似2.2.的Cristian算法操作
  • 对称模式：一对服务器交换有时许信息的消息，以提高准确性

交换消息对：不使用不可靠的UDP传递

NTP计算偏移$o_i$（即两时钟的偏移的估计）和延迟$d_i$（即消息对传输的整个时间）

设消息对的传输时间分别为$t$和$t’$, 第一个消息发送和接收的时间戳以及第二个消息发送和接收的时间戳分别为$T_{i-3}, T_{i-2}, T_{i-1}, T_i$, 则有：

  • $d_i = T_{i-2} - T_{i-3} + T_{i} - T_{i-1} = t + t’$

  • 实际偏移$o = o_i + (t’ - t) / 2$, 其中$o_i = (T_{i-2} - T_{i-3} + T_{i} - T_{i-1})/2$

  • $o_i - d_i/2 \le o \le o_{i} + d_{i}/2$

然后，NTP根据连续的$<o_i, d_i>$应用数据过滤算法，估计偏移量$o$以及估计的质量

3. 逻辑时间和逻辑时钟

3.1. Lamport的“发生在先”偏序关系（即因果序）

定义“发生在先”关系符号为：$ \rightarrow $

  • 若存在进程$p_i$, 有$e \rightarrow_i e’$, 则$e \rightarrow e’$

  • 任意消息$m$, 有$send(m) \rightarrow recv(m)$, 前者是发送事件，后者是接收事件

  • 传递性，若$e \rightarrow e’, e’ \rightarrow e’’$, 则$e \rightarrow e’’$

在这个规则下，多进程下的事件排序可能不唯一。

3.2. 逻辑时钟

逻辑时钟只是一个单调增长的计数器，与物理时钟无关。

定义：

  • 每个进程$p_i$维护自己的逻辑时钟$L_i$
  • $L(e)$代表任意进程的事件$e$的时间戳

规则：

  • 进程$p_i$发出事件前，$L_i := L_i + 1$
  • 进程$p_i$发出消息$m$时，在$m$中附加$t = L_i$
  • 进程$p_j$接收消息$<m, t>$时, $L_j := max(L_j, t)$, 然后给$recv(m)$事件打时间戳（之前需要应用规则1）

结论：

若$e \rightarrow e’$, 则$L(e) < L(e’)$ （反过来不成立）

3.3. 全序逻辑时钟

给时间戳打上进程标识，如$[T_i, i], [T_j, j]$（$i, j$为进程标识，且可比）。利用规则，当$T_i \le T_j$，或者$i < j$且$T_i = T_j$时$[T_i, i] \lt [T_j, j]$。

3.4. 向量时钟

改进Lamport时钟的缺点：$L(e) < L(e’)​$不能推出$e \rightarrow e’$

定义：

  • $n$个进程的系统的向量时钟$V$是长度为$n$的向量
  • 每个进程$p_i$维护自己的向量时钟$V_i$
  • 事件$e$的时间戳为$V(e)$

规则：

  • 初始下，对任意的$i, j$，有 $V_i[j] = 0$，这里$i, j = 1, 2, … n$

  • 在$p_i$中，给事件加时间戳前，令$V_i[i] := V_i[i] + 1$
  • $p_i$发送消息$m$时，给消息$m$附上$t = V_i$
  • $p_i$接收消息时，执行合并，即设置$V_i[j] := max(V_i[j], t[j])$, 这里$j = 1, 2, …, n$，并给$recv(m)$事件打时间戳（打之前需应用规则2）

比较与结论

  • $V = V’ \iff V[j] = V’[j] (j = 1, 2, …, n) $
  • $V \le V’ \iff V[j] \le V’[j] (j = 1, 2, …, n)​$
  • $V \lt V’ \iff V \le V’ \land V \not = V’ $
  • $\neg (V(c) \le V(e)) \land \neg (V(e) \le V(c)) \rightarrow c \Vert e ​$（并发）

可得到：$e \rightarrow e’ \iff V(e) < V(e’)$

4. 全局状态

4.1. 全局状态和一致割集

全局状态：进程集合的连续状态（难以观察，因为缺乏全局时间），即$S = {s_1, s_2, …, s_n} $

全局历史：$H = h_0∪h_1∪…∪h_{n-1}$

系统执行的割集：$C = h_{1}^{c1}∪h_{2}^{c2}∪…∪h_{n}^{cn}$

  • 割集边界集合：$ { e_i^{ci} \vert i = 1, 2, …, n }$
  • 全局状态$S$中$s_i$即为执行好$e_i^{ci}$后的状态
  • 一致割集：对于任意事件$e \in C,$ 满足$ f \rightarrow e \Rightarrow f \in C$
  • 一致的全局状态：对应于一致割集的状态

（顺序）走向：全局历史中所有事件的全序，且它保持了每个本地历史排序$\rightarrow_i$关系

  • 线性走向：在走向的基础上，保持了全局历史$H$上的发生在先关系$\rightarrow$（即只经历线性一致的全局状态）。若有一个经过$S$与$S’$的线性走向，则状态$S’$是从状态$S​$可达的
  • 线性走向中，并发事件（注：并发对应的是因果顺序上不可比）的顺序可以变换，得到的仍是线性走向

4.2. 全局状态谓词、稳定性、安全性、活性

全局状态谓词：系统$P$的全局状态映射到${ true, false }$的函数

  • 对象无用、系统死锁、系统终止的状态的谓词是稳定的，即该系统将在所有的可从该状态可达的状态中一直保持$true$
  • 监控和调试程序时，谓词是不稳定的

安全性：设有不希望有的性质（一个全局状态谓词）$\alpha$，系统初始状态为$S_0$，它的安全性是一个断言，即对所有可从$S_0$可达的状态$S$，$\alpha$值都为$false$

活性：设$\beta$为希望有的性质，它的活性是一个断言，即对所有可从$S_0$开始的所有线性走向$L$，其可达的状态为$S_L$，$\beta$值都为$false$

4.3. Chandy & Lamport 快照算法

该算法是为了记录进程集$p_i(i=1,2,…,n)$的进程状态和通道状态集（即快照），其记录的全局状态是一致的。

前提假设：

  • 通道与进程不会出现故障，通信可靠
  • 通道是单向FIFO通道
  • 任意两进程有一个通道连接
  • 任意进程可在任意时间开始一个全局快照
  • 拍快照时，进程可继续执行，发送、接收消息

概念：

  • 接入通道：其它进程向本进程发送消息的通道
  • 外出通道：本进程向其它进程发送消息的通道

通道的状态：若消息还在某通道中传输，则该消息就在该通道的状态中

  • 标记消息：若接收者没保存自己的状态，则提示其保存该状态；也可以决定哪个消息包含在通道状态中

a) 算法

标记接收规则（当进程接收到标记消息后）：

procedure recvMarkMsg(p:Process, c:Channel, inChannels:Set)
	if p.isRecordState == false
		recordState(p)
		c.state = Φ //c是接入通道
		recvMsg(inputChannels)
	else
		c.state = recordState(c) // 从p记录状态开始到现在从c中收到消息的集合

标记发送规则：

procedure sendMarkMsg(p:Process, outChannels:Set)
	foreach c in outChannels
		send(markMsg, c) // 在发送任何其它消息之前发出标记消息

可以在假设中保证，一些进程记录它的初始状态之后的有限时间内，所有进程将记录它们的状态和接入通道的状态。

割集也与该算法记录的状态是一致的。

观察到的全局状态与初始和最后的全局状态之间是可达的。

对于稳定性谓词而言，快照获得的值是多少，最终值/最初值也是多少。

4.4. 分布式调试（Marzullo & Neiger算法）

对于谓词$\phi$，全局历史$H$：

  • 可能的$\phi$：存在一个一致的全局状态$S$, $H$的一个线性走向经历了这个状态，且$\phi (S)$为真
  • 明确的$\phi$：$H$的所有的线性走向$L_i$都经历了一个状态$S_i$，且$\phi (S_i)$为真

a) 收集状态

进程$p_i$最初向监控器队列$Q_i$发送初始状态，之后状态改变时发送消息

（可优化，如只发送部分状态，又如对于特定谓词$\phi$状态改变后再发送）

b) 观察一致全局状态

监控器汇总收集的状态，判断其是否为一致的割集（即$C$中，所有事件$e$满足$f \rightarrow e \Rightarrow f \in C$）

实现：

  • 状态消息附上向量时钟值，队列$Q_i$要根据向量时钟的第$i$项对消息排序
  • 然后根据时间戳进行判断观察到的割集状态是否一致
    • $V(s_i)[i] \ge V(s_j)[i], \forall i, j = 1, 2, …, n$, 即CGS条件，满足则观察到的是历史状态是一致的（多次观察到的状态变化是线性走向）
    • 很容易得到一个状态走向的网格，状态都是一致的，走向是线性的

c) 判断可能的$\phi$

上述可知，可能的线性走向（线性走向可能有多个）构成网格，有层数的概念。

监控器可以发现$L+1$层中可从$L$层一个给定的一致状态可达的一致状态集合，只需遍历所有的队列$Q$即可。下层的$S’$从$S$可达，需满足：

  • $V(s_j)[j] \ge V(s’_i)[j] (j = 1, 2, …, n, i \not = j)$

只要判断到一个状态$\phi$为真，这输出可能的$\phi$

l := 0
states := {(s^0_1, s^0_2, ..., s^0_n)}
while (for all S in states, phi(S) = false) # 只要存在为真就输出
	l := l + 1
	reachableStates = {S_next | from all S in states, S_next is reachable from S, and level(S_next) = l}
	states := reachableStates
end while
output "possible_phi"

d) 判断明确的$\phi$

可能需要遍历整个网格。每条路径都要遍历，但某条路径出现$\phi$为真时，后面就不需要判断了。

l := 0
if (phi(s^0_1, s^0_2, ..., s^0_n) = true)
	states := {}
else
	states := {(s^0_1, s^0_2, ..., s^0_n)}
while (states is not empty)
	l := l + 1
	reachableStates = {S_next | from all S in states, S_next is reachable from S, and level(S_next) = l}
	states := {S in reachableStates, and phi(S) = false} # 遍历所有路径
end while
output "definite_phi"

开销：对于$n$个进程，一个进程事件最大个数为$k$, 则：

  • 时间复杂度为$O(k^n)$
  • 空间复杂度为$O(k^n)$

优化，对于队列$Q_i$，若满足：

  • $V(s^{last}_j)[i] \gt V(s_i)[i], j = 1, 2, …, n \land j \not = i$

那么$Q_i​$可以删除包含状态$s_i​$的消息

CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++