分布式系统课程笔记

分布式系统简介

分布式系统表现形式

• 集群

• 网格（分布式资源分布管理）
  • 计算和数据网格
  • P2P 网格
    • 不可信用户资源
    • 泛式类比云计算-边缘计算
  • 对等网络
    • 节点机器都是简单地接入互联网地客户机，不存在主从关系
    • 覆盖网络：基于通信或文件共享需求，对等节点 ID 在逻辑层形成一个覆盖网络
    • 异构：硬件模型/体系结构、软件/操作系统、网络连接/协议
      • 因此多在应用层实现网络

  P2P 网络设计目标： 数据局部性、网络邻近性、互操作性

• 云计算（分布式资源集中管理）
  • 通过迅速系统虚拟机或物理机，允许负载被快速配置和划分
  • 平台比较同构化
  • 支持冗余、自恢复、高可扩展编程模型
  • 服务模型：IaaS、PaaS、SaaS

分布式系统设计目标

• 资源可访问
• 透明性
  • 访问、位置、迁移、复制、并发、故障
• 开放性
  • 完整且中立的接口
  • 互操作性
  • 策略与机制分离
• 可扩展性
  • 规模：更多用户和资源的加入
  • 地域：多地容灾
  • 管理：跨独立机构仍可管理

分布式系统性能度量

• 与许多因素相关
  • 吞吐量、作业相应时间、网络延迟……
• 系统开销通常归因于操作系统启动时间、编译时间、I/O 数据速率、运行时支持系统消耗
• QoS、系统可用性/可靠性、安全弹性……

分布式系统设计关键技术

• 通信
  • 分层通信协议
    • 中间件协议
      • 第五层，应用层与传输层之间
      • 用于支持高层应用系统通信的协议
• 同步
• 一致性
• 容错
• 安全性
• 分布式共享内存
• 分布式文件系统
• 分布式数据管理
• 流数据与流处理
• 虚拟化

同步

• 数据为中心的一致性模型
  • 顺序一致性
  • 因果一致性
• 用户为中心的一致性模型
  • 最终一致性
  • 单调读
  • 单调写

容错

• 可用性 Availability
  • 系统可以正确操作运行
  • 系统在任何给定的时间都是可响应的
• 可靠性 Reliability (MTTF)
  • 系统可以无故障的持续运行
• 安全性 Safety
  • 系统偶然故障的情况能正常操作而不出现任何灾难
• 可维护性 Maintainability (MTTR)
  • 发生故障的系统被恢复的难易程度
• 分区容忍性 Partitoin tolerance
  • 将宕掉的机器和正常机器进行分区，正常机器分区仍然能够满足一致性和可用性
  • 分区不是绝对的，是有时效性的

CAP 定理： 三选二

分布式通讯

形式

• 远程过程调用
• 基于消息的通讯
• 流式通讯
• 多播通讯

通讯的类型

• 非易失 persistent / 暂存 transient
• 同步 synchronous / 异步 asynchronous
• 离散 discrete / 连续 stream

e.g.

• E-mail 非易失+同步
• RPC 暂存+同步
  • 异步 RPC、两阶段异步 RPC

基于消息的通讯

与 RPC 方式全由底层负责消息转换不同，由用户参与，性能优化可能

• 暂存（存于如 TCP/IP 协议栈中）
  • 基于 TCP/IP socket 接口通讯
  • 基于 MPI 通讯
    • 屏蔽 socket 编程细节
    • 通过不同接口开放不同的同步/异步粒度
• 非易失
  • 消息队列、消息中间件

流式通讯

• 特点
  • 依赖时间信息
  • 实时/准实时通讯
• 问题
  • QoS
  • 流同步

多播通讯

• 层叠网络 overlay network（应用层）
  • Tree, Mesh, DHT / P2P
• 流言传播
  • 增熵消息传播模型
  • 最有效的消息传播模型，需要避免将信息重复传递给已经接收到最新消息的节点

分布式并发控制与一致性

• 并发
  • 同一时间 段 内可以同步执行
  • \[a \not\lt_{hb} b, b \not\lt_{hb} a \Rightarrow a || b\]
• 一致性
  • 一致的数据 视图

并发时序

逻辑时钟（Lamport 时钟）

偏序关系

1. 节点内事件发生：\(L_i = L_i + 1\)
2. 发送：\(t = L_i,\ send(msg, t)\)
3. 接收：\(recv(msg, t),\ L_i=\max{(L_i,t)} + 1\)

hb 关系（Happen-Before 关系）决定时间关系，时间关系 无法 决定 hb 关系。

• \(a \lt_{hb} b \Rightarrow L(a) \lt L(b)\)，反之不亦然

• $$L(a)

  L(b) \Rightarrow a

  b$$，反之不亦然

全序逻辑时钟（向量时钟）

时间戳：标号与进程号 \((t_i, i)\)

\[a \lt_{hb} b \Leftrightarrow t_i \lt t_j\ or\ t_i=t_j, i<j\] \[a \lt_{hb} b \Leftrightarrow Vec(a) \lt Vec(b)\]

对每个节点 \(n_i\) 上的向量时钟：

1. 初始化：\(V_i[j] = 0\)
2. 节点内事件发生：\(V_i[i] = V_i[i] + 1\)
3. 发送：\(send(msg, t=V_i)\)
4. 接收：\(V_i[j]=\max{(V_i[j], t[j])},\ V_j[j] = V_j[j] +1\)

加锁法

• 集中式加锁法
  • 主节点加锁法，存放整个锁表
• 主副本加锁法
  • 两阶段加锁（2-Phase Lock），保证事务执行的可串行性
    • 事务要预先声明读集、写集
    • 级联撤销，导致其他访问该数据的事务也被撤销
    • 严格 2PL：事务在提交或撤销前，不能释放任何一个锁
  • 死锁
    • 死锁预防、死锁检测、锁超时机制
• 分布式加锁法

时标

• 全局唯一时标
  • <本地计数器、站点标识符>
• 发生冲突，通过撤销并重新启动事务解决
• 保守时标法
  • 缓冲新近操作，直至较早的操作完成，因此操作不会被拒绝、事务不会被重启
  • 要求所有站点连通
• 多版本时标技术

乐观并发控制

• 事务的三个阶段
  1. 读/计算阶段
  2. 验证阶段：可序列化检查
  3. 写/提交阶段

悲观控制事务三阶段：验证、读/计算、写/提交

• 使用数据项和事务上的时标
• 只使用事务上的时标
  • 集中式验证
  • 分布式验证

一致性

一致性模型本质上是进程与数据存储之间的约定，如返回最近一次写操作的结果

• 以数据为中心一致性
  • 不适用同步操作的一致性模型
    • 严格一致性、线性一致性
      • 要求全局完全一致时钟，目前不可实现
    • 顺序一致性
      • 全局时钟 –> 分布式逻辑时钟
    • 因果一致性
    • FIFO
  • 使用同步操作的一致性模型
    • 弱一致性：至少执行一次同步操作
    • 释放一致性：退出临界区后同步
    • 入口一致性：进入临界区时同步
• 以用户为中心一致性
  • 最终一致性
  • 单独读一致性
    • 不会读到比以前更旧的值
  • 单独写一致性
    • 写操作必须在之前所有写操作完成之后
  • 写后读一致性
    • 写操作总是能够被所有后续读看到
  • 读后写一致性
    • 读出的值不能比后续写操作所基于的值更新

分布式共识

共识算法的属性

• Agreement 协定性

  Every correct process must agree to the same value

• Validity 合法性

  If all correct process proposed the same value v, then any correct process must desice v

• Integrity 完备性

  No node decide twice （即不可逆）

• Termination 可终止性

  Eventually every correct process must decide some value

拜占庭容错

错误分类

• Omission failure 不会显示出来的错误

• Execution failure or Lying 发送错误或不一致数据

拜占庭将军问题

TODO 或见百度/知乎

该问题中假定通信链路可靠，通过 RSA 或其他签名算法保证。

Lamport 研究表明，当恶意节点个数小于节点总数 1/3 时，通过口头同步通信可以构造同时满足一致性和正确性的解决方法。

Paxos 算法

TODO 或见百度/知乎

一个正常进行的表决过程可以表述为：当大部分牧师在议会大厅呆了足够长时间，且期间没有牧师进入或者退出，那么提出的法案应该被通过并被记录在每个牧师的账目上。

该问题中执法者（处理器）和服务员（通信链路）都不可靠。

角色

• Proposer 提议者
• Acceptor 接收者：是否接收的决策者，仅当 epoch 更大时存储新的提案
• Learner 学习者：后来者，无表决权，不参与决策

单个节点或处理器可能同时具有多个角色。

分布式共享内存

• 粒度 Granularity
• 共享内存的结构
• 同步与一致性 Consistency
• 替换策略
• 抖动 Thrashing

粒度

网络中传输的块大小 block / unit

影响因素

• 页开销
• 目录大小
• 抖动
  • 当一个块内多个节点同时更新，抖动可能发生
  • 大块抖动概率更大
• 伪共享
  • 两个不同进程访问一个块内不相关的变量，其中一个为 write。若一次只允许一个进程写，会引发不必要的通信（ping-pong 效应）

一般设置块大小为页大小。当网络缺页时，不会引发额外的通信开销。

共享内存结构

• 无结构
• 根据数据类型组织，组织成变量/对象的集合
• 数据库

块替换策略

• 替换算法
• 被替换块的存放位置

抖动

• 当两个或多个节点上的进程交叉访问数据时
  • 提供应用可控的锁机制，防止其他节点短时间内访问
  • 固定块在一个节点至少一段时间
• 块在复制不久后，反复失效
  • 调整一致性算法