分布式系统 | D

Operation System

Computer Science

发布日期: 2024-12-06

更新日期: 2025-04-14

文章字数: 13.2k

阅读次数:

本文基于 SYSU-DCS325 的内容，对计算机专业课《分布式系统》进行较为详尽的知识点总结，涵盖少量实例分析。

1. 课程概述

1.1 课程目标

理解分布式系统的基本概念与核心原理。
掌握分布式系统的架构设计方法。
学习分布式系统的编程技术与工具。
了解分布式系统的运维与管理策略。
探索分布式系统领域的前沿技术与发展趋势。
激发学生对分布式系统研究与应用的兴趣。

1.2 课程内容安排

章节	内容
第1讲	分布式系统概述
第2讲	分布式系统体系架构
第3讲	分布式系统进程模型
第4讲	分布式系统通信
第5讲	分布式系统命名
第6讲	时钟与时间同步
第7讲	分布式系统同步
第8讲	分布式系统一致性
第9讲	分布式系统复制
第10讲	容错与可靠性保障
第11讲	分布式系统共识
第12讲	Paxos及RAFT协议
第13讲	分布式文件系统与存储系统
第14讲	面向大数据与AI的分布式计算框架
第15讲	P2P及内容分发网络

2. 分布式系统基础概念

2.1 定义

分布式系统是由多个自主且独立的计算机通过网络互联而成的集合，对用户而言，这些计算机像是一个单一的整体系统。

Leslie Lamport 的著名定义：

“A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.”

2.2 特性

自主性
- 计算节点的硬件与软件进程独立运行。
- 节点在物理上分布，而在逻辑上协调一致。
耦合性
- 用户感知系统为一个整体，隐藏了内部的分布性。
- 节点之间需要协作，共同完成任务。
其他特性
- 组件由所有用户共享访问。
- 系统资源可能分布在不同的物理位置，不一定直接可访问。
- 软件运行在不同处理器上的多个并发进程中。
- 支持多点控制和多点故障。

3. 分布式系统目标

分布式系统设计主要围绕以下四个目标：

资源访问
- 提供便捷的资源访问方式，用户无需关注资源的实际存储位置。
透明性
- 隐藏资源在网络上的分布，包括访问、位置、复制等方面的透明性。
开放性
- 采用标准化的接口，确保系统的可扩展性和互操作性。
可扩展性
- 系统能够在规模、地域和管理上灵活扩展，以适应不断增长的需求。

3.1 透明性的详细分类

透明性类型	说明
访问	隐藏不同的数据表示形式及资源访问方式
位置	隐藏资源的实际物理位置
迁移	隐藏资源的动态移动，确保资源位置变化对用户透明
重定位	隐藏资源在使用过程中可能的迁移动作
复制	隐藏资源是否存在多个副本
并发	隐藏多个用户对资源的并发访问
故障	隐藏系统资源的故障与恢复过程
持久化	隐藏数据在主存与磁盘之间的存储细节

注意：完全透明性难以实现，且可能带来性能开销。因此，设计时需在透明性与系统性能之间找到平衡。

4. 可扩展性

4.1 可扩展性的三个维度

规模可扩展性
- 支持用户数量和处理进程数量的增加。
地理可扩展性
- 支持节点分布在广泛的地理位置，确保跨地域的数据访问与计算。
管理可扩展性
- 系统管理结构能够适应管理域和组织结构的扩展。

4.2 扩展技术

隐藏通信延迟
- 使用异步通信技术，减少同步等待。
- 设计分离的响应消息处理器，提高响应效率。
- 将部分计算任务从服务器端迁移至客户端，减轻服务器负载。
分布式处理
- 将数据和计算任务分布到多个机器上，提升并行处理能力。
- 使用分布式命名服务器（如DNS）和分布式信息系统（如WWW）实现资源的全局管理。
数据复制
- 在多个机器上创建数据副本，提升数据的可用性和访问速度。
- 应用场景包括：分布式文件服务器、数据库复制、网站镜像和Web缓存等。

5. 分布式系统类型

5.1 集群计算系统

特点：
- 通过局域网（LAN）连接的高性能计算节点。
- 同构：相同的操作系统和近似的硬件配置。
- 由单一管理节点控制，管理集中。
应用案例：
- 高性能计算（HPC）集群，用于科学计算和模拟。

5.2 网格计算系统

特点：
- 节点地理分布广泛，可能跨越不同组织和网络。
- 异构：不同节点可能运行不同的操作系统和硬件。
- 易扩展至广域网（WAN）环境，适用于大规模分布式计算。
应用案例：
- 科学研究中的分布式模拟和数据分析。

5.3 云计算

架构层次：
1. 硬件层：包括处理器、存储设备、网络设备等基础资源。
2. 基础设施层：部署虚拟化技术，实现资源的虚拟化与管理。
3. 平台层：提供操作系统、数据库等高层次服务。
4. 应用程序层：用户实际使用的各类应用软件。
主要服务：
- IaaS（基础设施即服务）、PaaS（平台即服务）、SaaS（软件即服务）。

5.4 普适计算系统

特点：
- 设备通过网络灵活连接，实现高水平的用户与设备交互。
- 系统具备上下文感知能力，能够根据用户的环境和需求动态调整。
- 设备具有自主性和智能化，支持动态行为和复杂交互。
应用案例：
- 智能家居系统、物联网（IoT）应用。

5.5 移动计算系统

特点：
- 大量异构移动设备，位置随时间变化。
- 设备间通信存在不确定性和延迟，需应对频繁的网络变化。
应用案例：
- 移动应用、车联网（V2X）系统。

5.6 传感网络

特点：
- 节点数量众多（数十至数千）。
- 节点计算能力和存储有限，多数由电池供电。
- 需要高效的通信和节能机制。
应用案例：
- 环境监测、智能农业、智能城市。

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

系统设计
- 设计正确的接口和抽象层次。
- 功能划分与可扩展性设计。
一致性
- 共享数据的一致性保证。
- 处理读写冲突与写写冲突。
容错
- 确保系统在节点失效情况下的正常运行。
- 设计有效的故障检测与恢复机制。
部署场景差异
- 集群环境、广域网环境、传感网络等不同部署场景带来的设计与实现差异。
实现问题
- 最大化并行性，消除性能瓶颈。
- 负载均衡与资源优化。

7. 分布式系统架构

7.1 案例分类

分布式文件系统
- 例子：HDFS、NFS、Ceph。
分布式数据库
- 例子：MongoDB、Cassandra、Elasticsearch。
分布式处理框架
- 例子：Hadoop、MPI、Spark、Storm。
分布式调度器
- 例子：YARN、Mesos、Slurm。
分布式操作系统
- 例子：Kubernetes、OpenStack。

7.2 软件体系结构

7.2.1 基本概念

可替换性：组件具有定义良好的接口，便于替换与扩展。
互联方式：组件之间通过何种方式连接与通信。
数据交换：组件之间交换的数据格式与协议。
协同配置：组件与连接器的配置方式，确保系统协同工作。

7.2.2 软件体系结构风格

分层体系结构
- 分层设计，常用于客户端-服务器模型，如典型的三层架构（表示层、业务逻辑层、数据层）。
面向对象的体系结构
- 基于对象的设计，适用于分布式对象系统，如CORBA。
基于事件的体系结构
- 采用发布/订阅模式，事件驱动，适用于高并发、高解耦系统。
共享数据空间体系结构
- 通过共享内存或数据空间，实现进程间的解耦与协作。

7.3 系统体系结构

7.3.1 类型划分

集中式体系结构（Master-Slave）
- 单一控制中心管理整个系统，协调各节点的工作。
非集中式体系结构（P2P）
- 无中心控制，各节点自主运行，适用于去中心化应用。
混合体系结构
- 结合集中式与非集中式特点，例如点对点文件共享系统，部分节点充当协调者。

7.3.2 客户端-服务器模型

特点：

服务器进程
- 提供特定服务的核心进程。
客户端进程
- 发送请求并等待服务器响应，获取所需服务。
通信协议
- 常用协议包括HTTP/HTTPS（REST API）、AJAX（异步请求）、RPC（如XMLRPC、SOAP、gRPC）。

7.3.3 应用分层

传统三层架构：

用户接口层
- 系统与用户直接交互的部分，如GUI、管理界面。
应用逻辑层
- 包含业务逻辑与主要功能，不直接依赖具体数据存储。
数据访问层
- 管理系统使用的实际数据，如数据库、文件系统。

8. 分布式系统通信

8.1 基础网络模型

8.1.1 网络层次结构

物理层
- 负责数据的实际传输，处理物理媒介上的发送和接收。
数据链路层
- 将数据组织成帧，提供错误检测与流量控制。
网络层
- 负责数据包在网络中的路由与转发。
传输层
- 提供端到端的通信服务，主要协议包括TCP（可靠）、UDP（不可靠）、QUIC（基于UDP的高效协议）。
中间件层
- 提供通用的通信服务和协议支持，如数据封装、命名协议、安全协议等。

8.2 通信类型

8.2.1 基本分类

瞬时通信 vs 持久通信
- 瞬时通信：消息无法传递时直接丢弃。
- 持久通信：消息存储在服务器，直到成功传递。
同步通信 vs 异步通信
- 同步通信：发送方在等待响应期间被阻塞。
- 异步通信：发送方无需等待响应，可以继续执行其他任务。

8.2.2 客户端-服务器通信特点

同步通信缺点：

双方必须同时在线。
客户端请求后被阻塞，影响响应时间。
必须立即处理故障，增加系统复杂度。
不适用于需要长时间等待或高并发的应用场景。

8.3 远程过程调用（RPC）

8.3.1 基本原理

隐藏了调用者与被调用者之间的网络通信细节。
通过过程调用的方式实现分布式通信，使开发者能够像调用本地函数一样调用远程服务。

8.3.2 参数传递注意事项

数据表示差异
- 客户端与服务器可能使用不同的数据表示方式，需要统一编码机制。
编码机制
- 基本数据类型需统一表示，如整数、字符串。
- 复杂数据类型需规范化，如结构体、对象的序列化与反序列化。

8.3.3 RPC类型

同步RPC
- 客户端发送请求后阻塞，直到接收到服务器响应。
异步RPC
- 客户端发送请求后立即返回，后续通过回调或事件处理响应。
多RPC调用
- 客户端同时向多个服务器发送请求，提高并发与效率。

8.3.4 现代RPC实现：gRPC & Protobuf

特点：

语言无关、平台无关，支持多种编程语言。
高效，使用二进制序列化协议（Protobuf），体积小、传输快。
支持流式通信，适合实时数据传输。
严格的接口约束，确保服务的一致性与兼容性。

8.4 面向消息的通信

8.4.1 Berkeley套接字

主要操作原语：

socket()   // 创建通信端点
bind()     // 绑定本地地址
listen()   // 监听连接
accept()   // 接受连接请求
connect()  // 建立连接
send()     // 发送数据
recv()     // 接收数据
close()    // 关闭连接

8.4.2 ZeroMQ高级消息模式

请求-回复模式
- 客户端发送请求，服务器回复响应。
发布-订阅模式
- 发布者广播消息，订阅者接收感兴趣的消息。
管道模式
- 多生产者与多消费者通过队列交互，实现任务分发与处理。

8.4.3 消息队列系统

特点：

支持异步、持久化消息传递。
通过队列管理器管理消息的存储与转发。
提供灵活的消息路由功能，支持多种消息交换模式。

8.5 Kafka消息系统

主要组件：

Producer - 消息的生产者，负责发送消息到Kafka集群。
Consumer - 消息的消费者，从Kafka集群中读取消息。
Broker - Kafka集群中的服务器节点，负责消息的存储与转发。
Topic - 消息的主题，Producer发送消息到特定主题，Consumer订阅主题获取消息。
Partition - 主题的分区，Kafka通过分区实现消息的并行处理与负载均衡。

8.6 多播通信

8.6.1 应用层多播

组织方式：

树状结构
- 节点间形成唯一路径，结构简单但可靠性较低。
网络结构
- 节点有多个邻居，结构复杂但具备更高的健壮性。

8.6.2 Gossip协议（流行病协议）

传播模型：

反熵（Anti-entropy）模型
- 基于数据同步，确保最终一致性。
流言传播模型
- 随机选择节点进行信息交换，具备良好的扩展性，适用于大规模系统。

9. 分布式系统命名系统

9.1 基本概念

9.1.1 名称

由字符组成的字符串，用于唯一标识分布式系统中的实体对象。
标识的实体包括硬件资源（如主机、打印机、磁盘、文件）和抽象资源（如用户、邮箱、消息）。

9.1.2 访问点（Access Point）

进行实体操作的接口点，访问点的名称称为地址。
一个实体可以拥有多个访问点，以支持不同的操作接口。

9.1.3 标识符（Identifiers）

特性：

每个标识符唯一引用一个实体。
每个实体最多由一个标识符引用。
标识符一旦分配，永不重用，确保引用的一致性。

9.2 无层次结构命名

9.2.1 基于广播/多播的命名解析

广播方式
- 客户端发送广播请求，实体响应当前地址。
- 局限性：难以跨越局域网，需所有进程监听请求，带来带宽浪费。
多播方式
- 客户端发送多播请求，实体响应。
- 优势：适用于大规模网络，减少不必要的广播流量。

9.2.2 基于转发指针的命名解析

原理：

当实体移动时，在当前位置留下指向新位置的指针，客户端通过指针链查找实体所在位置。

问题：

长指针链可能断开，增加定位开销。
地理可扩展性差，适用于小规模系统。

9.2.3 分布式散列表（DHT）

以Chord为例：

结构特点：

节点组织成环形结构，每个节点有唯一的m位标识符。
实体通过唯一的m位健值（Key）进行标识，存储在满足ID >= Key的最小标识符节点上。
每个节点维护m个指针，指向当前节点后的2^(i-1)位置节点，支持对数级别的查找效率。

9.3 结构化命名

9.3.1 命名空间

基于命名图（Naming Graph）组织命名空间。
叶节点：表示具体实体，存储实体属性与状态。
目录节点：包含指向其他节点的链接，组织命名层级结构。

9.3.2 名称解析机制

闭包机制
- 通过分层命名解析，如www.domain.com由DNS服务器解析，/home/user/file由本地文件服务器解析。
链接类型
- 硬链接：直接通过路径名查找。
- 软链接：通过存储绝对路径名实现引用。

9.3.3 命名空间实现的三层结构

全局层
- 包含根节点及近根节点，结构稳定，通常代表整个组织或多个组织群体。
行政层
- 单个组织内部管理的目录节点，变化相对频繁，代表组织内的实体组。
管理层
- 代表本地主机、文件系统等，节点状态频繁变更，由终端用户维护。

9.4 名称解析方式

9.4.1 迭代式解析

客户端依次查询每个解析服务器，每个服务器返回下一步查询的服务器信息，直至获得最终结果。

9.4.2 递归式解析

客户端一次性请求，服务器递归查询其他服务器，最终返回结果给客户端。

9.5 基于属性的命名

9.5.1 LDAP（轻量级目录访问协议）

特点：

结合数据库实现目录服务，每个目录项包含（属性, 值）对。
赋予唯一名字，便于基于属性的查询与搜索。

9.5.2 扩展性考虑

规模扩展性
- 服务器需处理大量并发请求，需具备高吞吐量与低延迟。
地理扩展性
- 通过数据复制提高可用性，采用“就近服务”原则减少延迟。

10. 分布式系统协同

10.1 基础概念

10.1.1 同步与协作

同步类型
- 事件同步：事件在时间上达成一致。
- 进程同步：一个进程等待其他进程完成特定操作。
- 数据同步：保证多个节点的数据集合保持一致。
协作定义
- 管理系统中各行为之间的交互与依赖关系，分布式系统的协作复杂度高于单节点系统。

10.2 时钟同步

10.2.1 物理时钟

统一协调时间（UTC）
- 基于原子钟的精确时间标准，通过网络时间协议（NTP）同步。
时钟精度与准确度
精度定义：|Ci(t) - Cj(t)| ≤ ε
准确度定义：|Ci(t) - t| ≤ α
- Ci(t) 表示机器i在UTC时间t的时钟时间。
- ε 为精度参数，α 为准确度参数。

10.2.2 时钟漂移

时钟规约
(1 - ρ) ≤ F(t)/F ≤ (1 + ρ)
- ρ 为最大时钟漂移率。
- F(t) 为t时刻硬件时钟频率，F 为理想频率。
时钟同步方法

a) Berkeley算法
- 时间服务器定期收集所有节点时间，计算均值后通知各节点调整时钟。
b) 参考广播同步化（RBS）
- 适用于无线网络，节点定期广播参考时间，接收节点通过线性回归调整本地时钟。

10.3 逻辑时钟

10.3.1 发生关系（Happen-before）

定义三条规则：

同一进程中，事件a在事件b之前发生，则a → b。
事件a是消息的发送，事件b是消息的接收，则a → b。
如果a → b 且 b → c，则a → c。

10.3.2 Lamport逻辑时钟

时间戳规则
- P1：同进程事件a → b，则C(a) < C(b)。
- P2：消息发送事件a和接收事件b，则C(a) < C(b)。
实现机制
1. 每个进程Pi维护本地计数器Ci。
2. 进程内部事件发生时，Ci = Ci + 1。
3. 发送消息m时，Ci = Ci + 1，将时间戳ts = Ci附加到消息。
4. 接收消息m(ts)时，Ci = max(Ci, ts) + 1。

10.3.3 向量时钟

数据结构
- 每个进程Pi维护一个向量VCi[1…N]。
- VCi[j] 表示Pi已知的第j个进程的事件数。
更新规则
- 进程Pi本地事件：VCi[i] = VCi[i] + 1。
- Pi发送消息：先执行本地事件更新，再发送消息。
- Pi接收消息m(ts)：
  - 对所有j，VCi[j] = max(VCi[j], ts[j])。
  - VCi[i] = VCi[i] + 1。

10.4 分布式互斥

10.4.1 基于许可的方法

集中式方法
- 单一协调者控制资源访问，存在单点故障风险。
分布式方法（Ricart & Agrawala算法）

请求访问资源时：
1. 构造消息（资源名，进程号，逻辑时间）。
2. 发送给所有其他进程。
3. 等待所有进程回复OK。
接收请求时：
1. 未访问资源：直接返回OK。
2. 已获得访问权：将请求加入队列。
3. 想访问但未获得：比较时间戳
  - 接收到的消息时间戳早：返回OK。
  - 自己时间戳早：将请求加入队列。

10.4.2 基于令牌的方法

令牌环算法

进程组织成逻辑环，令牌在环内传递。
持有令牌的进程可进入临界区，完成后将令牌传递给下一个进程。

10.5 选举算法

10.5.1 Bully算法

运行机制：

Pi发起选举：
- 向所有ID更大的进程发送ELECTION消息。
- 如无人响应，Pi成为新Leader。
- 有响应则等待更高ID进程的选举结果。
Pj收到ELECTION消息：
- 发送OK给Pi。
- 向更高ID进程发起新一轮选举。
胜出者发送COORDINATOR消息，宣布自己为Leader。

10.5.2 Ring算法

运行机制：

进程按环形结构组织。
选举发起者将自己的ID加入消息列表。
消息沿环传递，各进程添加自己的ID。
消息返回发起者时，选出最大ID作为Leader。
新Leader通过环形广播通知所有进程。

11. 分布式系统一致性与复制

11.1 基础概念

11.1.1 复制的原因

性能提升
- 通过在多个节点上存储数据副本，提升数据读取速度与系统吞吐量。
提高可用性
- 数据副本的存在保证了部分节点故障时系统依然可用。

11.1.2 主要挑战

一致性保证
- 确保所有副本上的数据在任何时间点保持一致，防止数据冲突与不一致。
冲突类型
- 读写冲突：一个进程读取数据，另一个进程同时写入数据。
- 写写冲突：多个进程对同一数据进行并发写操作。

11.2 数据中心一致性模型

11.2.1 连续一致性模型

偏差类型：

数值偏差
- 不同副本间的数值存在差异。
新旧偏差
- 不同副本的数据新旧程度不同。
顺序偏差
- 不同副本上操作的顺序和数量不一致。

11.2.2 Consistency Unit（Conit）

结构组成：

包含多个数据项（如x, y）。
每个副本维护向量时钟，记录数据状态。
操作持久化，不允许回滚，确保操作记录的不可更改性。

偏差度量：

数值偏差 = 未接收更新次数 × 偏差权重。
偏差权重 = 已提交值与未收到操作结果间差值的最大值。

11.2.3 顺序一致性

定义：所有进程看到的操作执行顺序一致，每个进程自身的操作按程序顺序执行。

示例：

时间轴示意：
P1: W(x)1        R(x)1
P2:     W(x)2    R(x)2   [顺序一致]

11.2.4 因果一致性

定义：具有因果关系的操作必须以相同顺序被所有进程看到，保持操作之间的因果依赖。

特点：

较弱于顺序一致性，允许并发操作以不同顺序被各进程观察。
保持因果相关操作的顺序一致性。

11.3 客户端中心一致性模型

11.3.1 单调读一致性

定义：如果一个进程读取了数据项x的值，后续的读取操作不会读到更旧的值。

示例：

正确示例：
P1: W(x)1    R(x)1    R(x)1
P2:     W(x)2         R(x)2
   
错误示例：
P1: W(x)1    R(x)2    R(x)1  [违反单调读]
P2:     W(x)2

11.3.2 单调写一致性

定义：一个进程的写操作必须按顺序完成，即后续的写操作不能先于先前的写操作执行。

11.3.3 读写一致性

定义：进程的写操作结果必须对该进程的后续读操作可见，确保读到最新写入的数据。

11.4 复制管理

11.4.1 副本放置策略

服务器放置
- 从N个位置中选择K个最佳位置，考虑客户端距离最小化。
- 常用方法：几何空间划分，如哈希分区、地理分布等。
内容放置
- 使用多层次的放置策略，如三个同心环：
  - 永久副本（最内环）：关键数据的稳定副本。
  - 服务器启动副本（中环）：由服务器自动管理的副本。
  - 客户端启动副本（外环）：由客户端主动管理和维护的副本。

11.4.2 内容分发策略

传播方式
- 更新通知传播：服务器主动通知客户端更新信息。
- 数据传播：被动复制，通过请求拉取更新数据。
- 操作传播：主动复制，传递操作日志以同步更新。
更新方式

Push方式：
- 服务器主动推送更新到客户端。
- 适用于频繁更新的数据。
Pull方式：
- 客户端按需主动请求更新。
- 适用于低频更新或按需访问的数据。

11.5 一致性协议

11.5.1 基于主备份的协议

远程写协议

步骤：
1. 客户端发送更新请求到主副本。
2. 主副本转发更新请求到所有备份副本。
3. 备份副本确认接收更新。
4. 主副本向客户端返回成功响应。
本地写协议

适用场景：
- 离线计算环境、移动计算环境。
- 进行数据传输前的本地缓存与更新。

11.5.2 客户端中心一致性协议

实现机制：

每个客户端维护：

读操作集：与客户端读操作相关的写操作记录。
写操作集：客户端自身的写操作记录。

一致性检查：

单调读/写：在处理请求时，依据操作集保持一致性。
读写一致：读操作前检查写操作集，确保读到最新数据。
写读一致：写操作前检查读操作集，确保写入前的读操作已完成。

12. 分布式系统容错

12.1 基本概念与术语

12.1.1 可依赖性相关概念

可靠性（Reliability）

R(t) = P(组件从t=0到t时刻正常工作的概率)

重要指标：
- MTTF（平均失效时间）：组件从工作开始到第一次失效的平均时间。
- MTTR（平均恢复时间）：组件失效后恢复正常工作的平均时间。
- MTBF（平均故障间隔时间）= MTTF + MTTR。
可用性（Availability）

A(t) = 在[0,t]时间内组件可用时间的比例。
长期可用性：A = MTTF / (MTTF + MTTR)。

12.1.2 故障分类

按持续性分类
- 暂时性故障：仅发生一次，可以通过重试恢复。
- 间歇性故障：周期性发生，需要监控与预测。
- 持久性故障：持续存在，需人工干预或更换组件。
按性质分类
- 遗漏性失效：未执行应执行的操作，导致资源状态不可用。
- 执行性失效：执行了不应执行的操作，可能导致资源状态不一致。

12.2 进程恢复机制

12.2.1 冗余策略

信息冗余
- 通过附加校验位或冗余信息，检测与纠错数据传输中的错误。
时间冗余
- 通过重执行操作或事务处理，确保操作的可靠性。
物理冗余
- 增加额外的设备或进程，提升系统的容错能力。

12.2.2 K-容错组

容错度定义：

停止失效：需要K+1个成员。
随意失效：需要2K+1个成员。

假设条件：

所有成员同质，具备相同能力。
所有成员以相同顺序处理命令，确保操作一致性。

12.3 共识协议

12.3.1 基于泛洪的共识

系统模型：

组件：

进程组 P = {P1, P2, …, Pn}
失效模型：Fail-stop（停止失效）

过程：

客户端联系Pi执行命令。
每个进程维护命令列表，基于轮数进行共识。

12.3.2 Paxos协议假设

系统模型：
- 半同步系统，消息可能延迟但最终会到达。
- 通信不可靠，消息可能丢失、重复或乱序。
- 能够检测并丢弃损坏的消息。
- 操作具有确定性，保证相同输入产生相同输出。
- 节点可能出现崩溃失效，但不会发生网络分区。
- 节点不会串通欺骗，保持诚实。

13. 分布式系统容错

13.1 可靠通信

13.1.1 可靠RPC机制

错误类型及解决方案：

无法定位服务器
- 客户端返回错误信息，提示服务器不可达。
请求丢失
- 客户端重新发送请求，确保最终传递。
服务器崩溃
- 使用幂等操作，避免重复执行带来的副作用。
- 采用事务处理机制，确保操作的原子性。
客户端崩溃
- 使用孤儿操作消灭、任务再生和超时机制，确保系统状态一致。

13.1.2 可靠组通信

实现方式：

基本机制
- 确保组内每个进程都能接收到消息。
- 区分消息的发送与接收，防止消息丢失或重复。
反馈控制
- 无等级反馈：使用多播反馈抑制机制，减少重复反馈。
- 分等级反馈：采用树形结构组织反馈，提高反馈效率。

13.2 分布式提交协议

13.2.1 两阶段提交（2PC）

阶段1（投票阶段）：

协调者发送VOTE_REQUEST给所有参与者。
参与者返回VOTE_COMMIT或VOTE_ABORT。

阶段2（提交阶段）：

协调者根据投票结果发送GLOBAL_COMMIT或GLOBAL_ABORT。
参与者执行相应操作并返回确认。

失效处理：

参与者失效：使用日志记录以便恢复。
协调者失效：可能导致整个提交过程阻塞，需要恢复机制。

13.2.2 恢复机制

检查点机制

特点：
- 定期记录进程状态，便于恢复。
- 需要协调所有进程找到一致的恢复点。
- 可能导致多米诺效应，即多个进程必须同时回滚。
类型：
- 独立检查点：每个进程独立记录状态。
- 协调检查点：全局同步记录一致的状态。
日志消息机制

优势：
- 记录操作日志，支持通过重放达到一致状态。
- 实现成本低于全面检查点。
实现方式：
- 持久化重要消息日志。
- 保证消息的顺序一致性。
面向恢复的计算（RoC）

特点：
- 只重启系统的部分组件，减少恢复时间。
- 系统组件高度分离，组件间依赖关系简单。
- 支持增量恢复，提高恢复效率。

14. 分布式系统共识机制

14.1 基础概念

14.1.1 背景

分布式系统协作：多个组件协同工作，对外呈现为一个整体系统。
一致性：确保系统中各个副本的数据对象保持一致。
共识：在分布式系统中，多节点就某个操作或值达成一致的过程。

14.1.2 系统特性

基于BASE理论：

Basically Available（基本可用）：系统保证部分功能持续可用。
Soft-state（软状态）：系统状态可以通过交互动态变化。
Eventual Consistency（最终一致性）：所有副本最终将达到一致状态。

14.2 Paxos算法

14.2.1 基本概念

角色定义：

Proposer（提议者）：提出共识值的节点。
Acceptor（接受者）：接收并投票的节点。
Learner（学习者）：学习最终共识值的节点。

消息类型：

**Prepare(n)**：准备请求，提议编号n。
**Promise(n, v)**：承诺响应，承诺不接受编号小于n的提案，并返回已接受的最高编号提案值v。
**Accept(n, v)**：接受请求，提议编号n和提议值v。
**Accepted(n, v)**：接受响应，表示接受了提议编号n的值v。

14.2.2 算法流程

阶段1（Prepare）：

Proposer：

选择一个提案编号n。
向所有Acceptor发送Prepare(n)消息。

Acceptor：

如果n大于已承诺的所有编号：
- 承诺不再接受编号小于n的提案。
- 返回Promise(n, 已接受的最高编号提案值v)。
否则，拒绝Prepare请求。

阶段2（Accept）：

Proposer：

如果收到大多数Promise响应：
- 选择最高编号已接受的值v（如无则自由选择）。
- 向所有Acceptor发送Accept(n, v)消息。

Acceptor：

如果未对更大编号做出承诺：
- 接受提案，并发送Accepted(n, v)响应。
否则，拒绝Accept请求。

14.2.3 算法特性与示例

无冲突情况：

Proposer P1提出值v1。
多数Acceptor接受v1。
共识达成，值v1被选定。

并发提案冲突：

Proposer P1和P2同时提出不同的值。
较大编号的提案获胜，确保只有一个值被选定。

安全性保证：

已确定的值不会被修改。
较新的提案会继承已接受的值，保持一致性。

14.3 Raft算法

14.3.1 核心概念

角色定义：

Leader（领导者）：负责处理所有客户端请求，并管理日志复制。
Follower（跟随者）：被动响应Leader的请求或选举。
Candidate（候选者）：在Leader失效时发起选举的节点。

任期：

时间被划分为任期，每个任期有唯一的递增编号。
每个任期至多有一个Leader。

14.3.2 选举过程

Follower在超时未收到Leader心跳后，转换为Candidate。
Candidate增加当前任期编号，向其他节点发送选票请求。
如果Candidate获得多数选票，成为新的Leader。
Leader定期发送心跳消息，维持领导地位。
如果其他Candidate在选举过程中发现更高任期的Leader，转换为Follower。

14.3.3 日志复制

Leader接收客户端请求，追加到自己的日志。
Leader将日志条目复制到所有Follower。
当日志条目被大多数节点确认后，Leader提交该条目。
Leader通过心跳消息通知Follower提交日志条目。

14.3.4 一致性保证

所有Leader的财产集必须一致。
日志条目顺序一致，保证数据一致性。
即使在Leader失效后，新Leader也能正确恢复日志状态。

14.4 PBFT（实用拜占庭容错）

14.4.1 系统模型

假设条件：

系统由n个节点组成，其中最多f个节点可能是恶意的（拜占庭故障）。
系统运行在异步网络环境，消息可能延迟、丢失。
需要n ≥ 3f + 1以确保容错性。

14.4.2 协议流程

请求阶段：
- 客户端发送请求消息到主节点。
预准备阶段：
- 主节点为请求分配序号，并广播预准备消息给所有节点。
准备阶段：
- 节点验证预准备消息，确认消息的合法性。
- 节点广播准备消息给所有参与节点。
提交阶段：
- 节点在收到2f+1个准备消息后，广播提交消息。
执行阶段：
- 节点在收到2f+1个提交消息后，执行请求并向客户端发送响应。

14.4.3 视图变更

触发条件：

主节点失效或通信故障。
网络分区导致Leader通信中断。
超时未收到心跳或响应。

过程：

副本节点广播视图变更请求。
在接收到至少2f+1个视图变更请求后，开始选举新的主节点。
选举出新主节点后，同步全局状态，恢复共识流程。

总结：

Paxos：理论完备，适用于高一致性要求场景，但实现复杂。
Raft：易于理解与实现，适用于实际工程项目。
PBFT：能够处理拜占庭故障，适用于对安全性要求高的分布式系统，但开销较大。

选择依据：系统需求（如一致性强度、容错类型）、性能要求与实现复杂度等。

15. 分布式文件系统

15.1 问题背景与概述

问题：如何在分布式环境下高效、安全地存储和共享数据。
背景：
- 文件系统从本地（如FAT、NTFS、EXT）发展到集中式（如NFS、HDFS、Ceph），再到分布式文件系统（如GFS、DFS、Lustre）。
- 分布式文件系统旨在实现数据的高可用性、可扩展性与高性能访问，是分布式系统的重要组成部分。

15.2 分布式文件系统的重要属性

网络互连：通过网络实现文件的共享与访问。
分布式：文件存储与客户端分布在不同的物理节点上。
透明性：用户无需感知文件的实际存储位置，使用方式与本地文件系统类似。
性能要求：高效的数据访问速度，满足服务质量（QoS）的要求。
并发支持：支持多用户对同一文件的并发访问与修改。

15.3 分布式文件系统的体系结构

15.3.1 客户端-服务器体系结构

特点：
- 典型代表：NFS（Network File System）。
- 采用客户端-服务器模型，服务器提供统一的文件视图。
NFS架构：
- 服务器使用虚拟文件系统（VFS）层，隐藏本地与远程文件系统的差异。
- 支持类似UNIX的文件操作，包括硬链接和符号链接。
- 提供高效的远程文件访问，适用于网络环境下的文件共享。

15.3.2 基于集群的分布式文件系统

适用场景：大规模数据集的存储与访问，如大数据分析、科学计算。
关键技术：
- 文件分片：将大文件分割为多个小块，分布存储在不同节点上，实现并行访问。
- 大块存储：将文件划分为较大的数据块（如64MB），分布到多个存储节点，提高存储与读取效率。
案例：
- Hadoop Distributed File System（HDFS）、Google File System（GFS）。

15.3.3 Google文件系统（GFS）特点

主服务器功能：
- 维护文件名至块服务器的映射表，保持在内存中以提高访问速度。
- 记录数据更新日志，定期生成检查点以防日志过大。
数据复制：
- 采用主备模式复制文件块，确保数据的高可用性与容错性。
- 主服务器通过协调块服务器避免数据循环复制。
扩展性：
- 主服务器设计避免成为性能瓶颈，能够管理数百个块服务器。

15.3.4 对称式体系结构

特点：
- 基于点对点（P2P）技术的完全对称体系结构。
- 所有节点地位平等，资源分布均匀，无单点控制。
优势：
- 高容错性与可靠性，适合大规模分布式环境。
应用案例：
- Lustre文件系统，广泛应用于高性能计算集群。

15.4 文件系统中的进程

15.4.1 NFS的有状态与无状态模式

无状态NFS：
- 优点：
  - 服务器实现简单，易于扩展。
  - 即使服务器崩溃，客户端无需恢复状态。
- 缺点：
  - 无法实现文件锁定，容易导致并发访问冲突。
有状态NFS：
- 优点：
  - 支持文件锁定，确保并发访问的一致性。
- 缺点：
  - 服务器需要维护客户端的状态信息，增加实现复杂度。
  - 服务器崩溃后需恢复状态，影响系统可用性。

15.4.2 分布式文件系统中的RPC

选择RPC的原因：
- 隐藏底层通信细节，使系统独立于具体操作系统和网络协议。
问题与解决方案：
- 性能瓶颈：跨网络的RPC调用性能较低，通过并行RPC和本地缓存机制提升效率。

15.5 NFS的命名与挂载

15.5.1 命名原则

实现方式：通过在本地文件系统中挂载远程文件系统，实现用户对远程文件的透明访问。
目标：用户无需关心文件的实际存储位置，像操作本地文件一样操作远程文件。

15.5.2 自动挂载

按需挂载：仅在用户访问时才挂载远程文件系统，节省资源。
潜在问题：自动挂载策略需谨慎设计，避免因意外挂载带来的性能和安全问题。

15.5.3 全局名称空间

功能：通过全局名称空间服务（GNS），将多个分布式文件系统整合为一个统一的名称空间。
需求：对于大型分布式系统，提供全局统一的文件访问视图，简化用户操作与数据管理。

15.6 文件同步

15.6.1 文件共享语义

挑战：处理分布式文件系统中多个用户对同一文件的并发读写操作，保证数据一致性与操作顺序。

15.6.2 同步方案

立即传播改动
- 优点：简单直接，确保所有副本实时一致。
- 缺点：效率低下，增加网络带宽消耗。
会话语义
- 特点：文件修改仅对修改进程可见，文件关闭后对其他进程可见，降低同步频率。
- 适用场景：适用于需要中间状态不可见的应用，如文本编辑器。
只读文件
- 特点：文件仅支持创建与读取，避免写操作带来的同步问题。
- 适用场景：适用于日志文件、备份文件等仅需读操作的场景。
原子事务
- 特点：通过事务机制，保证共享文件的操作具有原子性，即操作要么全部成功，要么全部失败。
- 适用场景：需要确保操作一致性与完整性的应用，如数据库系统。

15.6.3 文件锁定

背景：
- 在无状态NFS中，需额外机制协调对共享文件的访问，防止并发写操作导致数据不一致。
实现方式：
- 使用锁管理器，通过文件级或更细粒度的锁，实现对文件的同步访问控制。

15.6.4 共享预约

定义：客户端在打开文件时指定访问类型（如读、写），服务器根据预约情况决定是否允许访问，确保不同访问类型的安全性与一致性。

16. 分布式系统一致性与复制

16.1 一致性模型

16.1.1 连续一致性与顺序一致性

连续一致性：系统保证所有客户端看到的数据更新是按某一全局顺序执行的。
顺序一致性：
- 定义：所有进程按照某个全局顺序执行操作，且每个进程的操作按程序顺序执行。
- 特点：简化了理解与设计，但在高延迟网络环境下实现复杂。

16.1.2 因果一致性

定义：满足因果关系的操作必须按相同的顺序被所有节点看到，非因果关系的操作可以任意顺序。
特点：
- 保证数据依赖关系的一致性。
- 允许并发操作，提高系统的吞吐量与性能。

16.2 一致性协议

16.2.1 Paxos协议

特点：
- 理论完备，能够在有部分节点失效情况下达成一致。
- 实现复杂，适用于高一致性要求的系统。

16.2.2 Raft协议

特点：
- 设计易于理解与实现，适用于实际工程项目。
- 通过角色划分与日志复制机制，确保日志的一致性与可靠性。

16.2.3 PBFT（实用拜占庭容错）

特点：
- 能够处理拜占庭故障，适用于安全性要求高的系统。
- 开销较大，适用于节点数量有限但安全性要求高的应用场景。

17. 分布式文件系统实例

17.1 HDFS（Hadoop Distributed File System）

架构特点：
- 主从架构，NameNode负责元数据管理，DataNode负责数据存储。
- 数据块（默认128MB）在多个DataNode上复制存储，保证数据高可用性。
优势：
- 高容错性与可扩展性，适用于大规模数据存储与处理。
- 与Hadoop生态系统紧密集成，支持大数据分析与计算任务。

17.2 Ceph文件系统

架构特点：
- 无中心化的设计，通过CRUSH算法实现数据分布与副本管理。
- 提供对象存储、块存储与文件系统存储多种接口。
优势：
- 高度可扩展性，适应大规模分布式存储需求。
- 强一致性与高性能，支持复杂的存储应用场景。

17.3 Lustre文件系统

架构特点：
- 高性能的并行文件系统，广泛应用于高性能计算（HPC）领域。
- 灵活的元数据服务器（MDS）与对象存储服务器（OSS）分离设计。
优势：
- 具有极高的吞吐量与低延迟，适用于需要高带宽的应用，如科学模拟、渲染等。
- 支持大规模集群，具备良好的扩展性与容错能力。

18. 面向大数据与AI的分布式计算框架

18.1 分布式计算框架概述

目标：处理大规模数据集，支持分布式计算任务，提高计算效率与数据处理能力。
关键技术：分布式存储、并行计算、任务调度、容错机制。

18.2 著名分布式计算框架

Hadoop
- 组件：HDFS（分布式存储）、MapReduce（计算模型）、YARN（资源管理）。
- 特点：适用于批处理大数据任务，具备高容错性与可扩展性。
Spark
- 特点：内存计算框架，支持多种计算模式（批处理、流处理、机器学习、图计算）。
- 优势：高性能、易用性，广泛应用于实时数据分析与机器学习任务。
MPI（Message Passing Interface）
- 特点：面向高性能计算的并行编程模型，适用于需要低延迟、密集通信的应用。
- 应用：科学计算、工程模拟、大规模并行应用。
Storm
- 特点：实时流处理框架，适用于实时数据分析与事件处理。
- 优势：低延迟、高吞吐，广泛应用于流数据处理系统。

18.3 分布式机器学习平台

Parameter Server（参数服务器）
- 功能：管理和存储机器学习模型的参数，实现高效的参数访问与更新。
- 技术：采用一致性哈希进行参数分区，支持分布式并行训练。
分布式训练策略
- 数据并行：将数据集划分为多个子集，分布到不同的训练节点并行处理。
- 模型并行：将模型划分为不同部分，分布到多个节点进行并行计算。
容错机制
- 任务重试：在节点失效时，重新分配任务以保证任务完成。
- 参数恢复：通过日志或快照机制，恢复模型参数状态，确保模型一致性。

18.4 深度学习在分布式环境中的应用

18.4.1 分布式深度学习的挑战

计算复杂度高
- 深度学习模型包含大量参数，训练过程需要高性能计算资源。
- 需要高效的计算资源管理与任务调度策略。
通信瓶颈
- 模型参数的同步与更新会占用大量网络带宽，影响训练速度。
- 需要优化通信协议与算法，减少带宽占用。

18.4.2 分布式深度学习平台

FloydHub：https://www.floydhub.com/
- 提供全托管的深度学习训练与部署服务，简化分布式训练流程。
OpenPAI：https://github.com/Microsoft/pai
- 微软开源的分布式人工智能平台，支持大规模分布式训练与模型管理。
PaddlePaddle：http://www.paddlepaddle.org/
- 百度开发的深度学习平台，支持高效的分布式训练与大规模模型部署。
Kubeflow：https://www.kubeflow.org/
- 基于Kubernetes的机器学习平台，支持分布式训练、模型部署与管理。
Polyaxon：https://polyaxon.com/
- 开源实验管理与分布式部署平台，支持机器学习模型的训练与调优。

19. 分布式文件系统案例分析

19.1 HDFS（Hadoop Distributed File System）

架构特点：
- NameNode：管理文件系统的元数据，如文件名与数据块的映射关系。
- DataNode：负责实际数据块的存储与管理。
- 数据复制：默认情况下，每个数据块在多个DataNode上复制，确保数据高可用性与容错性。
优势：
- 高容错性，通过数据冗余机制保障数据不丢失。
- 可扩展性强，支持数千个节点的集群。
- 与Hadoop生态系统紧密集成，支持大规模数据处理与分析任务。

19.2 Ceph文件系统

架构特点：
- 无中心化设计：通过CRUSH算法实现数据在集群中的均匀分布，无需中心协调者。
- 多接口支持：支持对象存储、块存储与文件系统存储，适应多种应用场景。
优势：
- 高度可扩展，支持大规模存储与高并发访问。
- 强一致性与高性能，满足复杂存储需求。
- 自愈能力强，能自动检测与修复数据故障。

19.3 Lustre文件系统

架构特点：
- 高性能并行文件系统，广泛应用于高性能计算（HPC）领域。
- 元数据服务器（MDS）与对象存储服务器（OSS）分离，提升系统性能与扩展性。
优势：
- 极高的吞吐量与低延迟，适用于需要高速数据访问的应用场景。
- 灵活的扩展性，能够支持数万个客户端并发访问。
- 高容错性，通过镜像与冗余机制保障数据安全。