写在前面

任课教师：余盛季
参考教材：《分布式系统概念与设计》，计算机科学丛书（原书第五版），机械工业出版社

知识点总结

第一章（对应课本第一章：分布式系统的特征）

1. 分布式系统的构建原因

功能分离
固有的分布性
负载均衡
可靠性
经济性

2. 分布式系统的定义、特征

分布式系统的定义：一个其硬件/软件组件分布在连网的计算机上，组件之间通过传递信息进行通信和动作协调的系统。

三个基本特征：并发性无全局时钟故障独立性

3. 分布式系统举例

WEB搜索：Google
大型多人在线游戏：MMO、RPG
金融交易
区块链系统
语音系统
数据库系统

4. 分布式系统面临的挑战

异构性
开放性
安全性
可伸缩性
故障处理
并发
透明性

一些名词解释：
Time synchronization: 参考此Blog

Leader election: 领导者选举, 指定单个进程作为分布在几台计算机（节点）中的某些任务的组织者的过程。在任务开始之前，所有网络节点要么不知道哪个节点将担任任务的“领导者”（或协调员），要么无法与当前协调员沟通。

Mutual exclusion: 互斥锁, 用于多线程编程中，防止两条线程同时对同一公共资源（比如全局变量）进行读写的机制。

Distributed snapshot: 分布式快照捕获, 反映了该分布式系统可能处于的状态，且重要的是，该记录的状态是全局一致的。这意味着，如果快照已经记录了进程P收到了来自进程Q的一条信息，那么应该也记录了进程Q确实发送了这个消息。否则，快照将会记录一个已经被接受但从未被发送的消息。需要注意的是，相反的情况是可以接受的，也即快照可以记录一个已经被发送但还尚未被接受的消息。

Routing: 路由

Consensus: 共识问题, 共识就是系统中的多个节点对某个值达成一致。

Replica management: 复制管理

Transactions: （分布式）事务

Trust model: 信任模型

5. 远程过程调用Remote Procedure Call (RPC)（对应课本第五章）

第二章（对应课本第二章：系统模型）

分布式系统体系结构模型
三种模型：

物理模型: 关注组成系统的计算机和设备的类型以及它们的互连
体系结构模型: 从系统的计算元素执行的计算和通信任务方面来描述系统
整体目标是确保结构能满足现在和将来可能的需求。主要关心系统可靠性、适应性、可管理性和性价比
基础模型: 采用抽象的观点描述大多数分布式系统面临的单个问题的方案。

1.1 C/S、P2P两种不同结构
- 客户—服务器 Client-Server/CS/BS (web/ftp/email)
优点：简单、直接

缺点：伸缩性差，系统的伸缩性不会超过提供服务的计算机的能力和该计算机所处网络连接的带宽。
- 对等体系结构 Peer-to-Peer/P2P (Bittorrent/eDonkey/IPFS)
特点：可用于运行服务的资源随用户数目的增加而增加。系统应用中，完全由对等进程组成，进程间的通信模式完全依赖于应用的需求。管理难度大：节点动态性、路由、QoS、安全

1.2 分层模型、层次化模型
- 分层：一个复杂的系统被分成若干层，每层利用下层提供的服务。
中间件层：一种软件用于提供基本的通信模块和其他一些基础服务模块，为应用程序开发提供平台。进程间通信（RMI、RPC、数据外部表示、编码、RRP都属于中间间层）
- 层次化 Tiered：与分层体系结构互补，是一项组织给定层功能的技术。

交互、故障、安全三种基础模型

交互模型：延迟的不确定性及缺乏全局时钟的影响。
故障模型：组件、网络等故障的定义、分类
安全模型：内、外部攻击定义、分类

同步、异步两种不同的分布式系统

同步分布式系统：有严格的时间限制假设
异步分布式系统：无严格的时间限制假设，非常常见

第三章（对应课本第十四章：时间和全局状态）

事件、进程历史概念

设一个分布式系统由 $N$ 个进程 $p_i(i=1,2,...,N)$ 组成 (记为 $\mathcal{P}$ ), 每一个进程在一个处理器上运行，处理器之间不共享内存。每一个进程 $p_i$ 的状态是 $s_i$ , 通常在进程执行的时候进行状态变换。进程的状态包括进程中所有变量的值，和在它影响的本地OS环境中的对象（比如文件）的值。还假设除了通过网络发送消息外，进程之间不能相互通信。

进程具有动作，或是消息的收发，或是状态转换等等。

事件：发生了一个动作（通信动作/状态转换动作），由一个进程完成。事件序列用事件之前的关系表示： $\rightarrow i$ 。当且仅当在 $p_i$ 中事件 $e$ 发生在 $e'$ 之前，表示为 $e \rightarrow i e'$ 。
进程历史：在该进程发生的一系列事件，按关系 $\rightarrow i$ 排序： $\textbf{history}(p_i) = h_i = <e_i^0, e_i^1, \dots, >$

时钟漂移及产生原因

计算机的时钟：包括硬件时钟 $H_i(t)$ 和软件时钟 $C_i(t) = \alpha H_i(t)+b$
时钟漂移：两个时钟的读书之间的瞬间不同称为时钟漂移。原因有晶振本身的振荡频率不同，电源稳定性、环境温度等都会有影响。时钟漂移不可避免。

内部、外部物理时钟同步

外部同步：用权威的外部时间源同步进程的时钟 $C_i$ 。设一个同步范围 $D \gt 0$ , UTC时间源为 $S$ , $I$ 中的所有实际时间为 $t$ , 满足：

$|S(t) - C_i(t)| \lt D$

另一种说法：时钟 $C_i$ 在范围 $D$ 内被认为是准确的。

内部同步：如果时钟 $C_i$ 与其他的时钟同步到一个已知的精度，能通过测量本地时钟度量在不同计算机上发生的两个事件间隔。设一个同步范围 $D \gt 0$ ， $I$ 中的所有实际时间为 $t$ ，有：

$|C_i(t) - C_j(t)| \lt D$

另一种说法：时钟 $C_i$ 在范围 $D$ 内被认为是一致的。

二者的关系：若时钟集合 $P$ 在范围D内外部同步，则 $P$ 在范围2D内内部同步。

时钟正确性含义

时钟正确性：
- 基于漂移率：如果一个硬件时钟 $H$ 的漂移率在一个已知的范围 $\rho \gt 0$ 内（该值从制造商获得），那么该时钟就是正确的。度量实际时间 $t$ 和实际时间 $t'$ （ $t' \gt t$ ）的时间间隔的误差是有界的：$$(1-\rho)(t’-t) \leq H(t’) - H(t) \leq (1+\rho)(t’-t)$$
- 基于单调性：要求软件时钟遵循上述条件，只需要加以一个较弱的单调性条件就足够了，即一个时钟 $C$ 前进的条件：$$t’ \gt t \Rightarrow C(t’) \gt C(t)$$
- 基于混合条件：单调性+漂移率有界+同步点允许时钟值可跳跃前进

物理时钟同步的三种方法

Cristian方法：用时间服务器做外部同步。
假设：在一对进程间消息交换的往返时间通常相当短。（比系统所要求的精度足够短）

进程 $p$ 在消息 $m_r$ 请求时间，从消息 $m_t$ 中接收了时间 $t$ ，并记录了从请求到接收的整个往返时间 $T_{round}$ 。那么根据 $m_t$ 中放置的时钟t可以设置自己本地的时钟为 $t+\frac{T_{round}}{2}$ .

精度分析：

设消息的最小传输时间为 $min$ , $m_r$ 到达S的事件位于 $[t+min, t+T_{round}-min]$ , 范围为 $T_{round}-2min$ , 精度为 $\pm (\frac{T_{round}}{2}-min)$ 。

Berkeley算法：内部同步，用于一个计算机集群（包括一个主机和若干个从机），主机周期轮询从属机时间

过程：主机通过消息往返时间估算从属机时间、计算容错平均值、并发送每个从属机的调整量。

NTP（网络时间协议）
特点：1. 可外部同步 2. 高可靠性（冗余服务器） 3. 扩展性好（大量用户可经常同步、抵消漂移率的影响） 4. 安全性强（有认证）

主服务器：连接到物理时钟源（UTC）的服务器。

二级服务器：与主服务器同步。采用同步子网的逻辑层次连接（树形结构）。层数大的服务器时钟比层数小的服务器时钟会更容易不精确。服务器故障时，同步子网可重新配置（主服务器出现故障，会变成层2的二级服务器，层2的服务器不可达时，可以与同层级的其他服务器同步）。
An example synchronization subnet in an NTP implementation

同步模式有：

1. 组播：适用于高速LAN，效率高但准确度低
1. 过程调用（C/S模式）：准确率高于组播
1. 对称模式:保留时序信息、准确率最高
  消息 $m$ 、 $m'$ 的实际传输时间分别为 $t$ 、 $t$ ；o为B时钟相对于A时钟的真实偏移（ $C_a=C_b-o$ ）

$T_{i-3} + t = (T_{i-2} - o)$

$(T_{i-1} - o) + t' = T_i$

$o = \frac{T_{i-2} - T_{i-3} + T_{i-1} - T_i}{2} + \frac{t' - t}{2}$

$o_i = \frac{T_{i-2} - T_{i-3} + T_{i-1} - T_i}{2}$

$o = o_i + \frac{t' - t}{2}$

$d_i = t + t' = (T_i - T_{i-3}) - (T_{i-1} - T_{i-2})$

最终有

$o_i - \frac{d_i}{2} \leq o \leq o_i + \frac{d_i}{2}$

其中， $o_i$ 为估计的时钟偏移， $d_i$ 为总延迟。

NTP采用过滤离中趋势算法(filter dispersion)，保留8个最近的 $<oi , di>$
NTP采用对等方选择算法，可改变用于同步的对等方
- 优先选择层次较低的对等方
- 优先选择过滤离中趋势数值较低的对等方

逻辑时间、逻辑时钟
发生在先关系、并发关系及分布式系统中的事件排序
Lamport时钟、全序逻辑时钟及向量时钟

逻辑时钟引入的原因：节点具有独立时钟，缺乏全局时钟，后发生的事件有可能赋予较早的时间标记；分布式系统中的物理时钟无法完美同步；事件排序是众多分布式算法的基石
什么是逻辑时钟：众多应用只要求所有节点具有相同时间基准，该时间不一定与物理时间相同
Lamport逻辑时钟及其后继研究：Happen-before relation
- 基本事实：
  
  同一进程中先后两个事件存在关系
  
  任一消息的发送事件发生在该消息的接收事件之前
- “发生在先(happens-before)” 关系定义：partial order
  - 若存在进程pi满足e $\rightarrow$ e’，则e $\rightarrow$ e’
  - 对于任一消息m，存在send(m) $\rightarrow$ recv(m)
  - 若事件满足e $\rightarrow$ e’和e’ $\rightarrow$ e’‘，则e $\rightarrow$ e’’
- 并发关系定义
  
  X||Y：X $\rightarrow$ Y 与 Y $\rightarrow$ X均不成立，则称事件X、Y是并发的
- 逻辑时钟本质上是进程 $p_i$ 维护的单调计数器（ $L_i$ ），用 $L_i(e)$ 代表事件 $p_i$ 的事件 $e$ 的Lamport时间戳, $L_e$ 代表发生在任意进程中的事件 $e$ 的时间戳。
- 进程按照如下规则修改和传递逻辑时钟：
  LC1: 在进程 $p_i$ 发出每个事件之前， $L_i$ 加1
  LC2:
  - (a) 当进程 $p_i$ 发送消息 $m$ 时，在 $m$ 中添加时间戳 $t = L_i$
  - (b) 当进程 $p_j$ 接收 $(m,t)$ 时，计算 $L_j = \textbf{max}(L_j,t)$ , 再给事件recv(m)加上时间戳： $L_j = L_j + 1$
  易得： $e \rightarrow e' \Rightarrow L(e) \rightarrow (e')$ , 反之不成立，因而没有捕获事件的因果关系。
- 全序逻辑时钟：由不同进程生成的不同事件的Lamport时间戳。
  - 若 $e,e'$ 分别为进程 $p_i,p_j$ 发生的事件，则其全局逻辑时间戳分别为 $(T_i,i),(T_j,j)$ 。规定 $e \rightarrow e' \Leftrightarrow T_i \lt T_j || (T_i = T_j \space \&\& \space i \lt j)$ ，无物理意义但是有时有用。确保每一个时间戳都不相同。
- 向量时钟(V)：克服了Lamport时钟的因果缺陷。N个进程的系统向量时钟是N个整数的一个数组，与Lamport时间戳类似，进程发送消息会附加上自己的向量时间戳。
  - $V_i[i]$ : $p_i$ 已经附加时间戳的事件个数。
  - $V_i[j]$ : $p_j$ 中发生的可能会影响 $p_i$ 的事件的个数。
  - 更新规则如下：
    
    VC1: 初始情况下， $V_i[j] = 0 (i,j=1,2,...,N)$
    VC2: 在 $p_i$ 给事件加时间戳之前，设置 $V_i[i] := V_i[i] + 1$
    VC3: $p_i$ 发送消息附加上时间戳 $t=V_i$
    VC4: $p_i$ 接收到消息中的时间戳 $t$ , 设置 $V_i[j] := \textbf{max}(V_i[j], t[j]), (i,j=1,2,...,N)$ (合并)
  - 比较性质：
    
    $V_1 = V_2$ iff $V_1[i] = V_2[i],\; i = 1, \ldots, n$
    $V_1 \le V_2$ iff $V_1[i] \le V_2[i],\; i = 1, \ldots, n$
    $V_1 < V_2$ iff $V_1 \le V_2 \;\land\; V_1 \ne V_2$
    $V_1 \parallel V_2$ iff $\neg (V_1 \le V_2 \;\lor\; V_2 \le V_1)$

割集、割集的一致性、一致的全局状态概念

全局状态：
- 分布式⽆⽤单元收集：不再对某个对象进行任何引用，一旦被认定无用，就要回收它的内存空间。必须考虑信道和进程的状态
- 分布式死锁检测：双方进程都在等待对方发送消息。
- 分布式终止检测：检测一个分布式算法是否终止，涉及到进程的主动性与被动性的判断。
分布式调试：需要收集同一时刻系统中分布式变量的数值。
全局状态和一致割集：目标是利用不同时间记录的本地进程状态得到一个有意义的全局状态。
- 前文讨论过一个系统 $\mathcal{P}$ 的进程历史的概念，这里我们用 $h^k$ 代表一个进程的进程历史的有限前缀： $h_i^k=<e_i^0, e_i^1, ..., e_i^k>$ . 用 $s_i^k$ 表示进程 $p_i$ 在第k个事件发生之前的状态
- 全局历史(H)：系统 $\mathcal{P}$ 的进程历史并集，即 $H=h_o \cup h_1 \cup \dots \cup h_{N-1}$ .
- 全局状态(S)： $S=(s_1,s_2,\dots,s_N)$ ，我们要判断哪个全局状态是有意义的（ $s_1,s_2,\dots,s_N$ 哪些能够同时发生）.
- 系统执行的割集(C)：是系统全局历史的子集，是系统进程历史前缀的并集, 即 $C = h_1^{c1} \cup h_2^{c_2} \cup ... \cup h_N^{C_N}$ 。C的全局状态S中的状态 $s_i$ 是进程 $p_i$ 处理最后一个事件 $e_i^{c_i}$ 之后的状态。事件集合 $e_i^{c_i}$ 为割集的边界.
  
  割集不一致：不符合进程事件因果性；割集一致：符合事件的因果性。