分布式系统期末

April 19, 2021 · 27 min read

Ferdinand Su

PhD Student @ HIT-ICES, Founder & Manager @ HIT-ReFreSH, C# developer.

引论

目的：资源共享与协同计算
+分布式系统：仅通过交换消息而完成通信和协作的连接网络的计算机集合。
特点
- 并发
- 没有全局时钟
- 独立故障(一个进程的故障不会被别的进程知晓)
?+挑战
- 异质性
- 开放性
- 安全性
- 可扩展性
- 错误处理
- 并发性
- +透明性
  - 并发透明性
  - 拷贝透明性
  - 故障透明性
  - 性能透明性
  - 移动透明性
  - 规模透明性
- 服务质量

系统模型

物理模型

基线物理模型：联网计算机上的硬件和软件组分通过发送信息来完成联系和协作

三代分布式系统

	早期	互联网级	现代
规模	小	大	极大
异质性	有限	在平台、语言和中间件方面显著	在多个维度上产生了彻底不同的架构
开放性	不是重点	在一些标准中是重点	在现存标准中是主要的研究挑战，但是尚未能用于复杂系统
服务质量	早期	在一些标准中是重点	在现存标准中是主要的研究挑战，但是尚未能用于复杂系统

架构模型

架构元素

通信实体：通常是进程；但是对于传感器网络为结点、对于一些环境为线程
通信范例
- 进程间通信：低级支持，通过IP协议的直接API访问
- 远程调用：支持双向交互，包括请求-回复协、原称过程调用，远程方法触发
- 间接沟通：通过组通信(广播和组播)、发布-订阅系统(基于事件)和消息队列完成沟通
角色和义务
- CS架构
- P2P
放置
- 多服务器提供服务
  - 分开放置资源
  - 不同主机分别维护资源的单独拷贝
- 代理服务器和缓存
- 移动端代码(小程序)

架构模式

分层：服务集合的纵向组织
- 平台：最底层，用于分布式系统和应用的软硬件层
- 中间件：一个软件层，掩盖异构性并为应用程序程序员提供方便的编程模型
垂直组织的分布式系统：UI-应用服务器-数据库服务器
横向组织
- 瘦客户端：提供最小的UI层，其他事情交给服务器
- 胖客户端：客户端包含应用逻辑和UI，服务器只负责权限控制和储存

基础模型

交互模型

通信信道的评估
- 延迟
- 带宽
- 抖动(稳定性)
+两类交互模型
- 同步：确定的执行、传输时间，确定的时钟偏移
- 异步

故障模型

故障模型定义了可能发生故障的方式，以便于提供对故障影响的理解。

遗漏故障：消息未正常收到(可能根本没发送)
任意故障：什么都可能发生
计时故障：主要是超时

安全模型

可以通过保护用于交互的进程和信道，并保护它们封装的对象，以此来屏蔽未授权的访问。

+时钟和时序

时钟基础

计算机使用一个计数器和一个寄存器来维护时钟。OS通过中断信号来维持系统时间。
时钟漂移：一段时间内时钟记录的时间与真实时间之间的误差
- 修复：如果快了，则调慢时钟直至同步(利用OS)；反之亦然
时钟偏移：同一时刻两个不同时钟间的差距

时钟同步

从顶级来源(GPS等)
从服务器
- +Cristian算法： $T=T_{Server}+\frac{RTT}{2}$ , 其中RTT为本地的请求发送和接收的时间差。精度 $\pm\frac{RTT}{2}$ (信息传播时间未知)或 $\pm(\frac{RTT}{2}-T_{min})$ ，其中 $T_{min}$ 为信息的最短传播时间。
- 伯克利算法
- NTP

+伯克利算法

主机定期拉取所有从机的时间
主机计算所有从机时间和自身的平均。计算平均的值不会包含“显然不对”的时间。
主机向各从机发送偏移量来调整时间

+NTP

设定A向B同步时间时：

$T_{i-3}$ : A发送到B的时间
$T_{i-2}$ : B收到A消息的时间
$T_{i-1}$ : B发送回复的时间
$T_{i}$ : A收到B回复的时间

则A同步为：

T_{i}+\frac{(T_{i-2}-T_{i-3})+(T_{i-1}-T_i)}{2}

误差区间:

\frac{(T_i-T_{i-3})-(T_{i-1}-T_{i-2})}{2}

事件时序

$a\rightarrow b$ ：a会影响b的输出，如果a先于b在同一过程中，或者a会发送给b消息。具有传递性。
$a||b$ ：a，b互无影响

Lamport算法

设各进程 $P_i$ 有逻辑时钟 $L_i$ ，则可以通过以下算法同步时钟：

初始化 $L_i$ 为0
更新 $L_i$ $L_{i}$ :
- 对于 $P_i$ 上的每一个新事件， $L_i$ 自增1;
- 对于 $P_i$ 发送的每一条消息 $m$ ，设定 $t_m=L_i$ ;
- 对于 $P_j$ 收到的每一条消息m，设定 $L_j=max(L_j,t)$ ，然后 $L_j$ 自增。

向量时钟

设各进程 $P_i$ 有向量时钟 $V_i$ ，则可以通过以下算法同步时钟：

初始化 $V_i$ 为0
更新 $V_i$ $V_{i}$ :
- 对于 $P_i$ 上的每一个新事件， $V_i[i]$ 自增1;
- 对于 $P_i$ 发送的每一条消息 $m$ ，设定 $t_m=V_i$ ;
- 对于 $P_j$ 收到的每一条消息m，对每一位设定 $V_j=max(V_j,t)$ ，然后 $V_j[j]$ 自增。

定理

$a\rightarrow b \Leftrightarrow V(a)\lt V(b)$

比较问题

$V=V' \Leftarrow V[i]=V'[i]$
$V\le V' \Leftarrow V[i] \le V'[i]$
$V\lt V' \Leftarrow V \le V' \And V\neq V'$

+互斥算法与选举算法

互斥算法

互斥算法的需求

安全性：任何情况下，只有一个进程可以执行
活泼性：无死锁，无饥饿(?)
公平性

集中式算法

模拟单进程系统
一个进程作为协调员

过程：

请求资源
等待请求
获得许可
访问资源
释放资源

优点：

公平性
易实现、理解、验证
进程只需知道协调员，而无须知道其它组员

缺点：

单点故障
集中式服务器可能成为性能瓶颈

令牌环算法

假定组员已知、有序
在软件层面，构建逻辑上的环
各节点和邻居联系

进程0初始化令牌
令牌传递
拥有令牌的进程，可以选择占用令牌和资源

优点：

不会导致饥饿

缺点：

无法满足先到先得
令牌丢失

+Ricart & Agrawala算法

基于可信赖组播和逻辑时钟
证明完全分布式算法是可能的

过程：

需要占用资源的进程广播信息，包含：
- 自身标识符
- 资源名称
- 时间戳
等待所有其它的‘肯定’回应
使用资源

对于收到请求的进程：

如果不感兴趣：回复OK
如果正在使用：不回复，将请求加入队列
如果也请求了：比较时间戳，先到先得。
使用完成后：向队列中的请求发送OK

缺点：

多点故障
大量的信息交互

+Lamport互斥算法

每个进程维护一个请求队列，其中包含互斥请求

请求资源时：

进程Pi向所有节点发送请求(i,Ti)
该请求也被加入他自己的队列中
对于收到请求的进程，它发送一个包含时间戳的ACK

进程访问资源，当且仅当：

Pi收到了来自所有其它进程的消息(ACK或释放信息)，其时间戳大于刚才的请求
Pi的请求在其请求队列中，拥有最小的时间戳

与Ricart & Agrawala的区别

每个节点总是回复ACK，而无须延迟等待
进程是否访问资源取决于其请求是否是在队列中最早的

释放

释放时：

将请求从自身请求队列中移除
发送带时间戳的释放信息

收到“释放”消息时：

从队列中移除指定请求。

选举算法

需要选出一个进程作为协调者
进程间的角色无法区分
每个进程都有一个UID来识别

霸道选举算法

选取具有最大ID者为协调者
当进程P检测到协调者已死亡时，向所有具有更大ID的进程发送选举信息
如果无人回应，则P作为新的协调者
否则，新的协调者选出，它需要向所有进程广播自己是新的协调者
一个死进程恢复时，他会举办选举产生新的协调者

环选举算法

进程环形安置
当任意进程检测到协调者离开时，
- 构建包含PID的选举消息，并发给下一进程
- 如果下一个进程已经离开，就跳过他
- 重复，直到找到活的“下一进程”
收到选举消息时，
- 传递消息，其中也加上了他自己的PID
最终，消息回到最初的发送者处，然后选出调度者

+Robert&Chang算法

优化的环选举算法，避免多次巡回选举
当一个进程收到选举消息后，比较消息中和自身的PID：
- 消息>进程，则继续转发
- 消息=进程，则本进程已经称为协调者，向其它进程发布
- 消息<进程
  - 本进程未成为参与者：用自身PID替换消息PID，然后转发
  - 本进程已成为参与者：丢弃之

计算机网络

复习以下内容

TCP/UDP
IP
- 数据包
- 子网/编址
- 路由协议
- 组播
DNS

+RPC

消息交换发生于本地存根和服务器架构间，使得RPC看起来像一个本地的过程调用
客户端程序-本地存根-网络例程-服务器架构-服务例程

步骤：

客户端调用本地存根，参数入栈
本地存根对参数编码、发消息并系统调用
消息发送到服务器
消息分发至服务器骨架，并解阻塞服务器
服务器骨架使用参数调用本地例程(本地调用)
例程返回值到服务器骨架
服务器骨架返回值、发消息并系统调用
返回值消息发送回客户端
消息分发至客户端存根
客户端存根返回值给应用

DNS

初级服务器：直接从本地主文件读取域信息
次级服务器：从初级服务器下载，并维持信息最新
服务器的三条数据文件
- 命名解析文件：域名到IP
- 反向翻译文件：IP到域名
- 缓存文件：缓存之前的查询数据
nslookup

+群组通信

单播：1对1
任播：1到任意附近节点，由IPv6引入，由BGP协议使用
组播
广播：1到全部

设定

闭合和开放：闭合群组只有组内消息
对等和分层
分布式与集中式
离开和加入：必须是同步的
容错性

组播实现

硬件组播：组成员监听特定地址
广播：广播到所有客户端，然后软件层面过滤
以太网支持组播和广播；限定于本地域
多重单播：发送者知道组成员，软件实现
分层实现：发送者发送给组长，组长知道所有组成员

组播可靠性

原子性的组播

如果任意成员未收到，则没有成员能收到

问题：

不可靠的网络环境
每一个消息都应该被确认
确认消息可能被丢失
消息发送者可能已经终止

可靠的组播

任何无故障的组员都能收到消息
假定发送者和接收方都在线
网络可能波动，因此会重试，但最终可能放弃
允许部分组员不收到消息
反馈可能导致内爆

+反馈的优化

流水线
累积确认
回传消息携带ACK
使用NAK

不可靠的组播

最好的性能
基础组播

+消息顺序

全局时钟顺序：所有消息都以完全确定的顺序分发(几乎不可能实现)
全序：所有的消息组组员间以相同顺序分发(分发队列排序)
- 附加全局序列的消息ID
- 仅当一个分发接收者收到所有之前消息时，它会分发当前消息
因果顺序(偏序)：如果两个消息间具有因果关系，那么它们之间是有序的；
- 各个线程维护优先权向量(类似时间戳向量)
- 如果m'取决于m，则所有进程必须先于m'分发m
- 在组播发送和接受事件时更新向量
同步顺序：消息可能以任意顺序到达，但是保证现有已排队的消息的派发先于任何其他消息被接受
单源FIFO顺序：来自单个源头的消息按照他们的发送顺序被派发
无序组播

偏序维护算法

当 $P_b$ 发送消息时，它更新向量中自己的字段并发送向量
当 $P_a$ $P_{a}$ 接收到来自 $P_b$ $P_{b}$ 时
- 按照FIFO顺序，检测来自 $P_b$ 的消息，是否 $V_b[b]=V_a[b]+1$
- 检查是否 $\forall i, i\not ={a},V_a[i]\le V_b[i]$
- 若均满足，则更新 $V_a[a]++$ 然后派发消息
- 否则，等待直到这些条件满足

PIM独立组播协议

组播路由协议，用于在路由器间分发包
拓扑结构由其他协议控制

密集模式(洪泛式)PIM-DM

向所有的邻居路由器中继包
逆向路径转发(RPF)：防止路由循环
浪费资源
如果包被大部分地方需求，那么很好用

稀疏模式PIM-SM

由接受者发起
每个路由器需要使用PIMJoin消息来请求一个组播种子
- 被终点路由器使用IGMPJoin发起
- Prune消息终止

一致性和复制

从多客户端访问情况下保护数据
对已复制数据的更新具有原子性
这些数据应该是同步的

一致性模型

不基于同步操作
- 严格一致性：所有共享访问具有绝对时序
  - 任何读取都能获得最新值
  - 理想模型，不可能存在
- 线性一致性：所有进程必须能观测到相同的共享访问序列；各访问由一个全局但是非独特的时间戳排序
  - 写能立即同步，读能读到最新
  - 所有操作好像按照时间顺序发生在一个副本上
- 序列一致性：所有进程必须能观测到相同的共享访问序列；但是排序并不依照时间
  - 写能立即同步，读能读到最新
  - 毋须按照时间顺序
- 因果一致性：排序依照因果相关顺序
  - 只保证有因果关系的操作的一致性
- FIFO一致性：所有进程能看到按发出顺序排序的单个进程写操作序列；然而来自不同进程的写入可能并不总是相同
基于同步操作
- 弱一致性：只有完成同步后，才能指望共享数据保持一致
- 释放一致性：退出关键区域时(资源释放)，共享数据将保持一致
- 进入一致性：进入关键区域时，与关键区域有关的共享数据将保持一致

以客户端为中心的一致性

最终一致性：如果一段时间内没有更新数据操作，则各副本逐渐一致化

四条原则

单调读一致性
单调写一致性
写后读一致性(Read your writes)：同一个进程读取到的内容和他在此前写入的一致
读后写一致性(Writes follow reads)：在写入前读取

传播方法

基于推送：服务器储存客户端副本和缓存，发出更新消息
基于拉取：服务器无状态

一致性协议

基于主数据的协议：数据存储中的每个数据项x都有一个关联的主数据，它负责协调对x的写操作
重复写协议：写入操作在多个副本上进行
缓存一致性协议：客户端控制一致性

+(15)文件系统

文件系统提供了构建其它信息系统的最基本服务
文件系统使用磁盘块来组织磁盘操作

UFS

内部文件结构

每个文件具有一个i-node
- 文件标识符(12B,所有者、权限、大小)
- 数据索引(4B*13)
- 总大小64B
- 用inode#引用

目录文件

目录文件是通常的文件，他们包含从名称到i-node的映射条目。
解析路径时，递归查询：
- 获取inode#
- 读取inode
- 加载内容

超级块

每个文件系统都有
包含系统总大小、剩余空间、缓存的块号、下一个空余块号、i-node区指针、空余i-node数量、缓存的空余i-node指针、下一个i-node序号
通常在系统启动的时候被加载到内存

地址计算

数据块

簇数=块号*(簇每块)
盘号=簇数/(簇每盘)
磁道=((簇数)%(簇每盘))/(簇每道)
块号=簇数%(簇每道)

i-node

块号=(inode号-1)/(inode每块)+inode区起始地址
字节偏移量=((inode号-1)%(inode每块))*inode大小

挂载

当内核解析路径时，通过inode可以判定挂载点，并获取挂载表
挂载表包含超级块地址，和指向根inode的指针
通过这些数据可以访问被挂载的文件系统的根inode，剩下的文件名解析会依赖被挂载系统
自动挂载：每10分钟重连，守护者进程

链接

链接不能跨文件系统
链接在目标文件的目录增加了新条目

DFS

位置透明性
并发透明性
故障透明性
异质性
可扩展性

组件

平面文件服务：提供一系列简单的通用操作，用于访问文件和其标识符，由UFID索引
目录服务：映射文件名为UFID
客户端模块：使用API访问文件和目录服务

操作

read(ufid,i,n)=>Data
write(ufid,id,Data)
create=>ufid
delete(ufid)
getAttributes(ufid)=>attr[]
setAttributes(ufid,attr[])
Lookup(dir,name)=>ufid
AddName(dir,name,ufid)
UnName(dir,name)
GetNames(dir,pattern)=>name[]：获取指定目录下的文件

基于客户端模块的分级文件系统

目录树的根位于一个周知UFID
路径名解析函数位于客户端模块

访问控制

客户端和服务器基于RPC联络，这可能会导致安全问题
依赖于UFID的访问限制包括文件位置(组ID)、FID和权限控制三个字段，由目录服务器基于客户端ID和权限生成
包含一个防止其被非法更改的加密字段。加密密钥通常由目录服务器和文件服务器共享。

文件表示

类似inode的index block被用于每个文件，来指示数据库
index block的定位基于UFID
- 因为规模问题，使用B-树解决查找问题
UFID中也包含了服务器位置

空间残余

孤儿文件的处理问题
该问题被大部分系统忽略
生命周期可以解决该问题

NFS

基于NFS和mount协议工作
无状态、可信赖的文件操作
引入VFS层

VFS层（虚拟文件系统）

为每个挂载和打开了的文件维护v-node，即虚拟inode
vnode不存在于磁盘，而是由OS维护。他决定文件在本地还是远程
- 对于本地文件它包含inode
- 对于远程，它包含FSID、inode号码、inode版本号

DFS和独立FS的差异

拆分的文件服务和目录服务
- 将目录服务从文件服务器上解离
无状态的服务器与客户端模拟
- 文件服务器变得轻量化
- 服务器更易于高效的从错误恢复
- 客户端模块模拟了传统的FS接口
可重复的操作
- 文件操作具有幂等性，允许被应用至少一次RPC调用
- 操作create是可预料的，但是对用户而言没有副作用

++事务处理系统

复习以下内容(数据库):

事务和并发控制

2PL必要性

当脱离锁区域后，数据就离开了控制范围，从而可能被更改(读、写不在一个锁区域内)

网络搜索技术

搜索引擎架构

爬虫:自动从URL开始迭代检索网页(BFS)
索引器:用关键字为文档建立索引
数据库
搜索引擎:返回最相关的文档

网络图

节点：网页
边：一个网页到另一网页的链接
节点内容：与网页相关的内容

具有动态性：

对于部分节点，出边不可知
- 存在尚未处理的节点
- 新的边可能已经添加
对于所有节点，存在一些未知的入边

FAN：网页评级

反向链接数越多越好
反向链接来源的等级越高越好

倒排索引：加速检索

建立从单词到FID的反向文件映射
可以加速检索

引论​

系统模型​

物理模型​

三代分布式系统​

架构模型​

架构元素​

架构模式​

基础模型​

交互模型​

故障模型​

安全模型​

+时钟和时序​

时钟基础​

时钟同步​

+伯克利算法​

+NTP​

事件时序​

Lamport算法​

向量时钟​

定理​

比较问题​

+互斥算法与选举算法​

互斥算法​

互斥算法的需求​

集中式算法​

令牌环算法​

+Ricart & Agrawala算法​

+Lamport互斥算法​

与Ricart & Agrawala的区别​

释放​

选举算法​

霸道选举算法​

环选举算法​

+Robert&Chang算法​

计 算 机 网 络​

+RPC​

DNS​

+群组通信​

设定​

组播实现​

组播可靠性​

原子性的组播​

可靠的组播​

+反馈的优化​

不可靠的组播​

+消息顺序​

偏序维护算法​

PIM独立组播协议​

密集模式(洪泛式)PIM-DM​

稀疏模式PIM-SM​

一致性和复制​

一致性模型​

以客户端为中心的一致性​

四条原则​

传播方法​

一致性协议​

+(15)文件系统​

UFS​

内部文件结构​

目录文件​

超级块​

地址计算​

数据块​

i-node​

挂载​

链接​

DFS​

组件​

操作​

基于客户端模块的分级文件系统​

访问控制​

文件表示​

空间残余​

NFS​

VFS层（虚拟文件系统）​

DFS和独立FS的差异​

++事务处理系统​

2PL必要性​

网络搜索技术​

搜索引擎架构​

引论