(并行与分布式计算九)
分布式系统的实例和定义
一般性的分布式系统
实例
生物中的实例：鱼的群体、鸟的群体、微生物生态系统
计算机系统的实例：Google FS、 Big Table、Hadoop、Hbase
定义：由一组相互独立的实体构成的集合，这些实体相互协作可解决任何单独的实体不能解决的问题
特征：
其中一个实体的失效不会影响整体对问题的求解
相互独立，有某种程度的自治性
宏观上具有一致行为
实体间的相互协作
分布式计算机系统可能呈现的特征
系统中某个计算机的崩溃不影响系统整体的功能
系统中每个计算机都是半自治的：没有共享内存和共同的物理时钟
系统中的计算机尽管相互独立，但在用户面前具有一致行为
弱耦合：通过通信网络进行通信和协作
允许地理分散
允许硬件和软件上的异构
典型分布式系统的体系结构
硬件
软件架构
软件部件之间的关系
分布式软件也叫做中间件
分布式执行是贯穿整个分布式系统的多个进程的执行
分布式执行通过多进程的合作来达成共同的目标
分布式系统用分层的体系结构来分散系统设计的复杂性
分布式系统的中间件通常包含一些分布式计算的原语，包括：
- 消息传递
- 组通信
- 远程过程调用（RPC）
分布式计算的动机
需求
满足实体所固有的地理分散性，例如银行转账
解决大规模共享数据资源的存储问题和访问瓶颈问题
解决数据权限和敏感性问题
提高系统的可靠性
- 可用性：资源就当在任何时间内都可以访问
- 完整性：面对多个处理器同时进行访问时，数据能符合应用所期望的语义
- 容错性：在系统故障时能恢复工作
提高系统的性能价格比
分布式计算的优势
可伸缩性
- 当需要满足更大的应用规模需求时，能够方便地增加系统中的计算机，通过广域网络扩展系统规模
- 在扩大系统规模时，不会直接在通信网络中造成瓶颈
模块化和可延展性
- 模块化使能方便地为异构处理器实例化功能模块，相同功能的模块可以有不同的具体实现
- 由于模块化使处理器能够被替换，分布式系统易于延展到多种硬件架构上
与并行计算的关系
并行系统的分类
多处理器系统：多个处理器能够直接访问构成公用地址空间的共享内存，但通常没有公用的时钟
多计算机系统：多个处理器无法直接访问共享内存，或者使用的内存不构成公用地址空间，通常没有统一的时钟，但通过互连网络连接在一起
阵列处理器系统：物理上放置在一起，具有统一的物理时钟，但可能没有共享内存和数据传输的处理器阵列，例如数字信号处理和某些图像处理应用
UMA和NUMA多处理器系统
UMA(uniform memory access), 一致性内存访问
- 多个处理器访问各自的内存
NUMA(non-uniform memory access), 非一致性内存访问:
- 多个处理器访问共享内存
多处理器系统两种流行的互联网络
Omega互联函数
为连接n个处理器到n个内存单元，只需用 $\frac{n}{2}log_2 n$ 个2x2的交换单元
每一层编号i的交换单元连下一层编号j的交换单元，其中
$$
j = \begin{cases}
2i & 0 \leq i \leq n/2 - 1, \
2i + 1 - n & n/2 \leq i \leq n - 1.
\end{cases}
$$
Butterfly互联函数
所需要的交换单元个数与Omega互联函数的一样，为连接n个处理器到n个内存单元，只需用 $\frac{n}{2}log_2 n$ 个2x2的交换单元
与Omega互联函数的区别：相邻两级之间互联模式不仅依赖于n, 而且依赖于级号s
第s级第x个交换单元
$$
x{s+1} xor y{s+1} = 1
$$
这里 $x(s+1)$ 和 $y(s+1)$ 分别是x和y的第（s+1）个MSB位(Most Significant Bit)
多计算机的圆环面和超立方体拓扑
超立方体与海明距离
超立方体中的两个计算机的距离由消息要经过的交换单元(路由)个数来定义
上述距离恰好是这两个计算机的编号的海明距离
两个非负整数的海明距离=它们的二进制表示有多少个位不相同
Flynn分类法与耦合度
- 耦合的松紧由软、硬模块的相互依存关系决定
- SISD
- MISD 有共同时钟，所以是紧耦合
- SIMD 有共同时钟，所以是紧耦合
- MIMD 松耦合
并行系统和分布式系统的比较
分布式系统通常是松耦合多计算机系统
各个计算机间没有共享内存，也没有共同的时钟
物理上共同放置的多计算机系统在通信延迟上相对较小，这种系统同时是并行系统与分布式系统
物理上分开放置的系统通信延迟相对较大，这种系统是传统意义上的分布式系统，但与并行系统有所差别
共同术语
耦合
加速比：T(1) / T(n)，其中n是处理器个数
并行度：有效执行CPU指令所占的时间比例
- 有效执行的操作是除去等待通信的操作
并发度：本地操作与全局操作在数目上的比例
- 本地操作：非通信、非共享内存访问
- 全局通信：通信或共享内存访问
粒度：计算总量与通信总量的比例
分布式计算的两种范例
- 消息传递分布式系统
- 没有公共时钟，没有公共地址空间
- 靠消息传递来通信和相互协作
共享内存分布式系统
- 没有公共时钟，没有公共地址空间
- 一个进程的共享区域在另一个进程中用的是不同的地址
- 利用共享内存中的共享区域来通信和相互协作
范例的等价性
- 在共享内存的系统上仿真消息传递
- 发送：写共享区域，然后激发同步原语
- 接收：激发同步原语，然后读共享区域
在消息传递的系统上仿真共享内存
- 读共享区域：向共享区域拥有者发送查询请求的消息，然后接收对方的回复消息
- 写共享区域：向共享区域拥有者发送更新数据的请求消息
分布式计算的原语
分类一：同步和异步
- 如果一个操作原语与对方实现了握手（得到对方响应确认后再开始操作），则称其操作是同步的
- 如果一个操作原语没有与对方握手，则称其操作是异步的
分类二：阻塞和非阻塞
- 如果一个操作原语在处理完成之后才返回调用流程，则称其操作是阻塞的
- 如果一个操作原语在处理完成之前就返回调用流程，则称其操作是非阻塞的
- 非阻塞发送原语的例子1234Send(X, destination, handle_k) // handle_k is a return parameter......Wait(handle_1, handle_2, ..., handle_k, ..., handle_m) // Wait always blocks
一些原语库与标准
MPI
PVM
Socket
Sun RPC
CORBA
DCOM
同步与异步执行
同步执行的例子
异步执行的例子
分布式计算模型的动机和主要思想
动机：解决分布式计算中的不确定性所带来的控制困难
- 不确定性一：通信网络的延迟难以预测
- 不确定性二：不存在一个能随时访问的全局时钟
- 困难：当发生通信超时、处理器失效、链路层崩溃等情况时，通信消息可能会在传递过程中乱序、丢失、被篡改或重复传送
解决该困难的主要思想：
- 用有向图对分布式系统进行建模
- 节点表示处理器
- 有向边代表单向通信信道
- 通过该有向图来管理分布式计算中事件与事件之间的因果关系
分布式程序
一个分布式程序由一组n个异步进程 $p_1, p_1, ⋯, p_n$ 组成，它们之间通过通信网络进行消息传递
一般性的假设：
- 不同的进程运行在不同的处理器上
- 进程间没有可共享的全局存储，只能通过消息传送来进行联系
- 通信延迟是有限的但无法预测
- 这些进程不共享一个可随时访问的全局时钟
- 进程的运行和消息的传送都是异步的
分布式运行模型
事件和状态
- 事件的定义：进程运行中的原子动作
- 事件的分类：内部事件、消息发送事件和消息接收事件
事件的符号：进程 $p_i$ 上的第x个事件记作 $e_i^x$
事件对系统状态的影响：
- 内部事件改变所处的进程的状态
- 消息发送事件和消息接收事件改变事件中收发双方的状态
事件的顺序
- 单个进程中的事件顺序:
- 进程 $p_i$ 上的 $e_i^1, e_i^2, ⋯, e_i^x, e_i^{x+1}, ⋯$
- 这些事件的集合记为 $hi$, 顺序记为 $→𝑖$ , 序列记为 $H_i=(h_i,→_i)$
- 关系 $→_i$ 表示了 $p_i$ 的事件间的因果依赖
消息发送和接收双方之间的因果依赖：
- 记消息m的发送事件为send(m), 接收事件为rec(m), 则有 $send(m) →_{msg}rec(m)$
时空图
因果优先关系
逻辑并发和物理并发
- 在一次分布式计算中
- 两个事件是逻辑并发的，当且仅当它们之间无因果影响
- 两个事件是物理并发的，当且仅当它们在同一物理时间发生
两个或更多个事件可能是逻辑并发的，即使它们不是物理并发的
前面时空图中的 $e_1^3, e_2^4, e_3^3$ 是逻辑并发的，但不是物理并发
通信网络模型
- 分类：
- 先进先出(FIFO): 信道由先进先出的消息队列来维持
- 非先进先出(非FIFO): 信道由能随机加入消息和取出消息的集合来维持
- 因果序(CO: causal ordering): 对任意两个消息 $m{ij}$ 和 $m{kj}$ , 由 $m{ij} → m{kj} ⟹ send(m{ij}) → send(m{kj}) ∧ rec(m{ij}) → rec(m{kj})$
CO ⊂ FIFO ⊂ 非FIFO
- 由上述因果序定义的因果依赖模型大大简化了分布式算法的设计，因为它提供了一个内存的同步机制
分布式系统的全局状态
定义：分布式系统的全局状态是其各组成部件的本地状态的集合，包括各个处理器状态和所有通信信道状态
- 分类:
- 处理器状态：寄存器状态、堆栈状态、本地内存状态等，依赖于分布式应用的本地语义
- 通信信道状态：由信道中传输的消息集合给出
处理器状态
- $LS_i^0$ 表示进程 $p_i$ 的初始状态
- $LS_i^x$ 表示进程 $p_i$ 在发生了事件 $e_i^x$ 但还没有发生事件 $e_i^{x+1}$ 时的状态
- 关系 $send(m) \leq {LS}_i^x$ 表示 $∃y:1≤y≤x::e_i^y=send(m)$
- 关系 $rec(m) \leq {LS}_i^x$ 表示 $∃y:1≤y≤x::e_i^y=rec(m)$
- 关系 $send(m) \not\leq {LS}_i^x$ 表示 $∀y:1≤y≤x::e_i^y≠send(m)$
- 关系 $rec(m) \not\leq {𝐿𝑆}_i^x$ 表示 $∀y:1≤y≤x::e_i^y≠rec(m)$
信道状态
- ${𝑆𝐶}_{ij}^{x,y}$ 表示进程 $p_i$ 和进程 $pj$ 之间的信道 $C{ij}$ 的状态
- ${𝑆𝐶}{ij}^{x,y} = { m{ij}│send(m_{ij})≤{LS}i^x⋀rec(m{ij})≰ {𝐿𝑆}_j^y }$
- ${𝑆𝐶}_{ij}^{x,y}$ 的元素是进程 $p_i$ 直到事件 $e_i^x$ 发送的并且进程 $p_j$ 直到事件 $e_j^y$ 未收到的消息，换句话说，就是直到事件 $e_i^x$ 和e_j^y$ 仍然在该信道中传输的消息
全局状态
分布式系统的全局状态是所有处理器本地状态以及信道状态的集合
全局状态GS可定义为
$$
GS = { \bigcup_𝑖 {LS}_i^{xi}, \bigcup{j,k}{SC}_{jk}^{x_j,y_k} }
$$全局状态的意义：
- 所有部件的状态无法在同一瞬间被记录，而上述全局状态去掉了这个要求
- 上述全局状态的依据：一个消息如果没有被发送，也就不可能会被接收
一致性和非一致性全局状态
一个全局状态
$$
GS = { \bigcup_𝑖 {LS}_i^{xi}, \bigcup{j,k}{SC}_{jk}^{x_j,yk} }$$
是一个一致性全局状态，如果它满足如下条件:
$$
\forall m{ij}: send(m_{ij}) \not\leq {LS}_i^{xi} ⇒ m{ij} \not\in {SC}_{ij}^{x_i,yj} \bigwedge rec(m{ij}) \not\leq {LS}_j^{y_j}
$$
- 不满足上述条件的全局状态是非一致性的全局状态，如前面时空图的 ${ {LS}_1^1, {LS}_2^3, {LS}_3^3, {LS}_2^4 }$
非中转和强一致
全局状态 $GS = { \bigcup_𝑖 {LS}_i^{xi}, \bigcup{j,k}{SC}_{jk}^{x_j,yk} }$ 是非中转的，如果对任意j和k，都有 ${SC}{jk}^{x_j,y_k}$ 为空集
一个全局状态是强一致的，如果它同时是非中转的和一致性的
分布式计算的运行分割
分割线的概念和定义
- 概念：
- 画一条曲线C与每条进程线相交且仅相交一个点，把整个计算过程分割为两部分
- 左边部分记作PAST(C), 表示C处已发生的所有事件，右边部分记作FUTURE(C)，表示C处未发生的所有事件
上述曲线称为一条分割线，每条分割线对应一个全局状态，每个全局状态可以图形化为时空图上的一条分割线
定义：
- 如果 $e_i^{max{PAST_i(C)}}$ 表示进程 $p_i$ 上的PAST(C)中最新的事件，那么由分割线C所表示的全局状态是 ${ \bigcup_i{LS}_i^{max{PASTi(C)}}, \bigcup{j,k}{SC}_{jk}^{max{PAST_k(C)}} }$
分割线与全局状态一致性的关系
- 一条分割线所对应的全局状态是一致的，如果所有跨越分割线的消息都是从分割线的PAST集发送，到其FUTURE集接收
一条分割线所对应的全局状态是不一致的，如果存在一条消息从分割线的FUTURE集发送，到其PAST集接收
图中𝐶_1的全局状态是非一致的，𝐶_2的全局状态是一致的
事件的过去和未来锥面
进程通信模型
同步通信
- 优点：简单
- 缺点：效率低，并且容易造成死锁
异步通信
- 优点：高度的并行性
- 缺点：复杂的缓冲管理机制和困难的通信方式设计、验证和实现