分布式系统

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

1. 课程概述

1.1 课程目标

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

1.2 课程内容安排

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 特性

1. 自主性

   • 计算节点的硬件与软件进程独立运行。
   • 节点在物理上分布，而在逻辑上协调一致。

2. 耦合性

   • 用户感知系统为一个整体，隐藏了内部的分布性。
   • 节点之间需要协作，共同完成任务。

3. 其他特性

   • 组件由所有用户共享访问。
   • 系统资源可能分布在不同的物理位置，不一定直接可访问。
   • 软件运行在不同处理器上的多个并发进程中。
   • 支持多点控制和多点故障。

3. 分布式系统目标

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

1. 资源访问

   • 提供便捷的资源访问方式，用户无需关注资源的实际存储位置。

2. 透明性

   • 隐藏资源在网络上的分布，包括访问、位置、复制等方面的透明性。

3. 开放性

   • 采用标准化的接口，确保系统的可扩展性和互操作性。

4. 可扩展性

   • 系统能够在规模、地域和管理上灵活扩展，以适应不断增长的需求。

3.1 透明性的详细分类

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

4. 可扩展性

4.1 可扩展性的三个维度

1. 规模可扩展性

   • 支持用户数量和处理进程数量的增加。

2. 地理可扩展性

   • 支持节点分布在广泛的地理位置，确保跨地域的数据访问与计算。

3. 管理可扩展性

   • 系统管理结构能够适应管理域和组织结构的扩展。

4.2 扩展技术

1. 隐藏通信延迟

   • 使用异步通信技术，减少同步等待。
   • 设计分离的响应消息处理器，提高响应效率。
   • 将部分计算任务从服务器端迁移至客户端，减轻服务器负载。

2. 分布式处理

   • 将数据和计算任务分布到多个机器上，提升并行处理能力。
   • 使用分布式命名服务器（如DNS）和分布式信息系统（如WWW）实现资源的全局管理。

3. 数据复制

   • 在多个机器上创建数据副本，提升数据的可用性和访问速度。
   • 应用场景包括：分布式文件服务器、数据库复制、网站镜像和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. 分布式系统面临的挑战

1. 系统设计

   • 设计正确的接口和抽象层次。
   • 功能划分与可扩展性设计。

2. 一致性

   • 共享数据的一致性保证。
   • 处理读写冲突与写写冲突。

3. 容错

   • 确保系统在节点失效情况下的正常运行。
   • 设计有效的故障检测与恢复机制。

4. 部署场景差异

   • 集群环境、广域网环境、传感网络等不同部署场景带来的设计与实现差异。

5. 实现问题

   • 最大化并行性，消除性能瓶颈。
   • 负载均衡与资源优化。

7. 分布式系统架构

7.1 案例分类

1. 分布式文件系统

   • 例子：HDFS、NFS、Ceph。

2. 分布式数据库

   • 例子：MongoDB、Cassandra、Elasticsearch。

3. 分布式处理框架

   • 例子：Hadoop、MPI、Spark、Storm。

4. 分布式调度器

   • 例子：YARN、Mesos、Slurm。

5. 分布式操作系统

   • 例子：Kubernetes、OpenStack。

7.2 软件体系结构

7.2.1 基本概念

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

7.2.2 软件体系结构风格

1. 分层体系结构

   • 分层设计，常用于客户端-服务器模型，如典型的三层架构（表示层、业务逻辑层、数据层）。

2. 面向对象的体系结构

   • 基于对象的设计，适用于分布式对象系统，如CORBA。

3. 基于事件的体系结构

   • 采用发布/订阅模式，事件驱动，适用于高并发、高解耦系统。

4. 共享数据空间体系结构

   • 通过共享内存或数据空间，实现进程间的解耦与协作。

7.3 系统体系结构

7.3.1 类型划分

1. 集中式体系结构（Master-Slave）

   • 单一控制中心管理整个系统，协调各节点的工作。

2. 非集中式体系结构（P2P）

   • 无中心控制，各节点自主运行，适用于去中心化应用。

3. 混合体系结构

   • 结合集中式与非集中式特点，例如点对点文件共享系统，部分节点充当协调者。

7.3.2 客户端-服务器模型

特点：

1. 服务器进程

   • 提供特定服务的核心进程。

2. 客户端进程

   • 发送请求并等待服务器响应，获取所需服务。

3. 通信协议

   • 常用协议包括HTTP/HTTPS（REST API）、AJAX（异步请求）、RPC（如XMLRPC、SOAP、gRPC）。

7.3.3 应用分层

传统三层架构：

1. 用户接口层

   • 系统与用户直接交互的部分，如GUI、管理界面。

2. 应用逻辑层

   • 包含业务逻辑与主要功能，不直接依赖具体数据存储。

3. 数据访问层

   • 管理系统使用的实际数据，如数据库、文件系统。

8. 分布式系统通信

8.1 基础网络模型

8.1.1 网络层次结构

1. 物理层

   • 负责数据的实际传输，处理物理媒介上的发送和接收。

2. 数据链路层

   • 将数据组织成帧，提供错误检测与流量控制。

3. 网络层

   • 负责数据包在网络中的路由与转发。

4. 传输层

   • 提供端到端的通信服务，主要协议包括TCP（可靠）、UDP（不可靠）、QUIC（基于UDP的高效协议）。

5. 中间件层

   • 提供通用的通信服务和协议支持，如数据封装、命名协议、安全协议等。

8.2 通信类型

8.2.1 基本分类

1. 瞬时通信 vs 持久通信

   • 瞬时通信：消息无法传递时直接丢弃。
   • 持久通信：消息存储在服务器，直到成功传递。

2. 同步通信 vs 异步通信

   • 同步通信：发送方在等待响应期间被阻塞。
   • 异步通信：发送方无需等待响应，可以继续执行其他任务。

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

同步通信缺点：

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

8.3 远程过程调用（RPC）

8.3.1 基本原理

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

8.3.2 参数传递注意事项

1. 数据表示差异

   • 客户端与服务器可能使用不同的数据表示方式，需要统一编码机制。

2. 编码机制

   • 基本数据类型需统一表示，如整数、字符串。
   • 复杂数据类型需规范化，如结构体、对象的序列化与反序列化。

8.3.3 RPC类型

1. 同步RPC

   • 客户端发送请求后阻塞，直到接收到服务器响应。

2. 异步RPC

   • 客户端发送请求后立即返回，后续通过回调或事件处理响应。

3. 多RPC调用

   • 客户端同时向多个服务器发送请求，提高并发与效率。

8.3.4 现代RPC实现：gRPC & Protobuf

特点：

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

8.4 面向消息的通信

8.4.1 Berkeley套接字

主要操作原语：

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

8.4.2 ZeroMQ高级消息模式

1. 请求-回复模式

   • 客户端发送请求，服务器回复响应。

2. 发布-订阅模式

   • 发布者广播消息，订阅者接收感兴趣的消息。

3. 管道模式

   • 多生产者与多消费者通过队列交互，实现任务分发与处理。

8.4.3 消息队列系统

特点：

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

8.5 Kafka消息系统

主要组件：

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

8.6 多播通信

8.6.1 应用层多播

组织方式：

1. 树状结构

   • 节点间形成唯一路径，结构简单但可靠性较低。

2. 网络结构

   • 节点有多个邻居，结构复杂但具备更高的健壮性。

8.6.2 Gossip协议（流行病协议）

传播模型：

1. 反熵（Anti-entropy）模型

   • 基于数据同步，确保最终一致性。

2. 流言传播模型

   • 随机选择节点进行信息交换，具备良好的扩展性，适用于大规模系统。

9. 分布式系统命名系统

9.1 基本概念

9.1.1 名称

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

9.1.2 访问点（Access Point）

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

9.1.3 标识符（Identifiers）

特性：

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

9.2 无层次结构命名

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

1. 广播方式

   • 客户端发送广播请求，实体响应当前地址。
   • 局限性：难以跨越局域网，需所有进程监听请求，带来带宽浪费。

2. 多播方式

   • 客户端发送多播请求，实体响应。
   • 优势：适用于大规模网络，减少不必要的广播流量。

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

原理：

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

问题：

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

9.2.3 分布式散列表（DHT）

以Chord为例：

结构特点：

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

9.3 结构化命名

9.3.1 命名空间

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

9.3.2 名称解析机制

1. 闭包机制

   • 通过分层命名解析，如www.domain.com由DNS服务器解析，/home/user/file由本地文件服务器解析。

2. 链接类型

   • 硬链接：直接通过路径名查找。
   • 软链接：通过存储绝对路径名实现引用。

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

1. 全局层

   • 包含根节点及近根节点，结构稳定，通常代表整个组织或多个组织群体。

2. 行政层

   • 单个组织内部管理的目录节点，变化相对频繁，代表组织内的实体组。

3. 管理层

   • 代表本地主机、文件系统等，节点状态频繁变更，由终端用户维护。

9.4 名称解析方式

9.4.1 迭代式解析

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

9.4.2 递归式解析

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

9.5 基于属性的命名

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

特点：

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

9.5.2 扩展性考虑

1. 规模扩展性

   • 服务器需处理大量并发请求，需具备高吞吐量与低延迟。

2. 地理扩展性

   • 通过数据复制提高可用性，采用“就近服务”原则减少延迟。

10. 分布式系统协同

10.1 基础概念

10.1.1 同步与协作

1. 同步类型

   • 事件同步：事件在时间上达成一致。
   • 进程同步：一个进程等待其他进程完成特定操作。
   • 数据同步：保证多个节点的数据集合保持一致。

2. 协作定义

   • 管理系统中各行为之间的交互与依赖关系，分布式系统的协作复杂度高于单节点系统。

10.2 时钟同步

10.2.1 物理时钟

1. 统一协调时间（UTC）

   • 基于原子钟的精确时间标准，通过网络时间协议（NTP）同步。

2. 时钟精度与准确度

   精度定义：|Ci(t) - Cj(t)| ≤ ε 准确度定义：|Ci(t) - t| ≤ α

   • Ci(t) 表示机器i在UTC时间t的时钟时间。
   • ε 为精度参数，α 为准确度参数。

10.2.2 时钟漂移

1. 时钟规约

   (1 - ρ) ≤ F(t)/F ≤ (1 + ρ)

   • ρ 为最大时钟漂移率。
   • F(t) 为t时刻硬件时钟频率，F 为理想频率。

2. 时钟同步方法

   a) Berkeley算法

   • 时间服务器定期收集所有节点时间，计算均值后通知各节点调整时钟。

   b) 参考广播同步化（RBS）

   • 适用于无线网络，节点定期广播参考时间，接收节点通过线性回归调整本地时钟。

10.3 逻辑时钟

10.3.1 发生关系（Happen-before）

定义三条规则：

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

10.3.2 Lamport逻辑时钟

1. 时间戳规则

   • P1：同进程事件a → b，则C(a) < C(b)。
   • P2：消息发送事件a和接收事件b，则C(a) < C(b)。

2. 实现机制

   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 向量时钟

1. 数据结构

   • 每个进程Pi维护一个向量VCi[1…N]。
   • VCi[j] 表示Pi已知的第j个进程的事件数。

2. 更新规则

   • 进程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 基于许可的方法

1. 集中式方法

   • 单一协调者控制资源访问，存在单点故障风险。

2. 分布式方法（Ricart & Agrawala算法）

   请求访问资源时：

   1. 构造消息（资源名，进程号，逻辑时间）。
   2. 发送给所有其他进程。
   3. 等待所有进程回复OK。

   接收请求时：

   1. 未访问资源：直接返回OK。
   2. 已获得访问权：将请求加入队列。
   3. 想访问但未获得：比较时间戳
      • 接收到的消息时间戳早：返回OK。
      • 自己时间戳早：将请求加入队列。

10.4.2 基于令牌的方法

令牌环算法

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

10.5 选举算法

10.5.1 Bully算法

运行机制：

1. Pi发起选举：

   • 向所有ID更大的进程发送ELECTION消息。
   • 如无人响应，Pi成为新Leader。
   • 有响应则等待更高ID进程的选举结果。

2. Pj收到ELECTION消息：

   • 发送OK给Pi。
   • 向更高ID进程发起新一轮选举。

3. 胜出者发送COORDINATOR消息，宣布自己为Leader。

10.5.2 Ring算法

运行机制：

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

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

11.1 基础概念

11.1.1 复制的原因

1. 性能提升

   • 通过在多个节点上存储数据副本，提升数据读取速度与系统吞吐量。

2. 提高可用性

   • 数据副本的存在保证了部分节点故障时系统依然可用。

11.1.2 主要挑战

1. 一致性保证

   • 确保所有副本上的数据在任何时间点保持一致，防止数据冲突与不一致。

2. 冲突类型

   • 读写冲突：一个进程读取数据，另一个进程同时写入数据。
   • 写写冲突：多个进程对同一数据进行并发写操作。

11.2 数据中心一致性模型

11.2.1 连续一致性模型

偏差类型：

1. 数值偏差

   • 不同副本间的数值存在差异。

2. 新旧偏差

   • 不同副本的数据新旧程度不同。

3. 顺序偏差

   • 不同副本上操作的顺序和数量不一致。

11.2.2 Consistency Unit（Conit）

结构组成：

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

偏差度量：

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

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 副本放置策略

1. 服务器放置

   • 从N个位置中选择K个最佳位置，考虑客户端距离最小化。
   • 常用方法：几何空间划分，如哈希分区、地理分布等。

2. 内容放置

   • 使用多层次的放置策略，如三个同心环：
     • 永久副本（最内环）：关键数据的稳定副本。
     • 服务器启动副本（中环）：由服务器自动管理的副本。
     • 客户端启动副本（外环）：由客户端主动管理和维护的副本。

11.4.2 内容分发策略

1. 传播方式

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

2. 更新方式

   Push方式：

   • 服务器主动推送更新到客户端。
   • 适用于频繁更新的数据。

   Pull方式：

   • 客户端按需主动请求更新。
   • 适用于低频更新或按需访问的数据。

11.5 一致性协议

11.5.1 基于主备份的协议

1. 远程写协议

   步骤：

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

2. 本地写协议

   适用场景：

   • 离线计算环境、移动计算环境。
   • 进行数据传输前的本地缓存与更新。

11.5.2 客户端中心一致性协议

实现机制：

每个客户端维护：

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

一致性检查：

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

12. 分布式系统容错

12.1 基本概念与术语

12.1.1 可依赖性相关概念

1. 可靠性（Reliability）

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

   重要指标：

   • MTTF（平均失效时间）：组件从工作开始到第一次失效的平均时间。
   • MTTR（平均恢复时间）：组件失效后恢复正常工作的平均时间。
   • MTBF（平均故障间隔时间）= MTTF + MTTR。

2. 可用性（Availability）

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

12.1.2 故障分类

1. 按持续性分类

   • 暂时性故障：仅发生一次，可以通过重试恢复。
   • 间歇性故障：周期性发生，需要监控与预测。
   • 持久性故障：持续存在，需人工干预或更换组件。

2. 按性质分类

   • 遗漏性失效：未执行应执行的操作，导致资源状态不可用。
   • 执行性失效：执行了不应执行的操作，可能导致资源状态不一致。

12.2 进程恢复机制

12.2.1 冗余策略

1. 信息冗余

   • 通过附加校验位或冗余信息，检测与纠错数据传输中的错误。

2. 时间冗余

   • 通过重执行操作或事务处理，确保操作的可靠性。

3. 物理冗余

   • 增加额外的设备或进程，提升系统的容错能力。

12.2.2 K-容错组

容错度定义：

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

假设条件：

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

12.3 共识协议

12.3.1 基于泛洪的共识

系统模型：

组件：

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

过程：

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

12.3.2 Paxos协议假设

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

13. 分布式系统容错

13.1 可靠通信

13.1.1 可靠RPC机制

错误类型及解决方案：

1. 无法定位服务器

   • 客户端返回错误信息，提示服务器不可达。

2. 请求丢失

   • 客户端重新发送请求，确保最终传递。

3. 服务器崩溃

   • 使用幂等操作，避免重复执行带来的副作用。
   • 采用事务处理机制，确保操作的原子性。

4. 客户端崩溃

   • 使用孤儿操作消灭、任务再生和超时机制，确保系统状态一致。

13.1.2 可靠组通信

实现方式：

1. 基本机制

   • 确保组内每个进程都能接收到消息。
   • 区分消息的发送与接收，防止消息丢失或重复。

2. 反馈控制

   • 无等级反馈：使用多播反馈抑制机制，减少重复反馈。
   • 分等级反馈：采用树形结构组织反馈，提高反馈效率。

13.2 分布式提交协议

13.2.1 两阶段提交（2PC）

阶段1（投票阶段）：

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

阶段2（提交阶段）：

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

失效处理：

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

13.2.2 恢复机制

1. 检查点机制

   特点：

   • 定期记录进程状态，便于恢复。
   • 需要协调所有进程找到一致的恢复点。
   • 可能导致多米诺效应，即多个进程必须同时回滚。

   类型：

   • 独立检查点：每个进程独立记录状态。
   • 协调检查点：全局同步记录一致的状态。

2. 日志消息机制

   优势：

   • 记录操作日志，支持通过重放达到一致状态。
   • 实现成本低于全面检查点。

   实现方式：

   • 持久化重要消息日志。
   • 保证消息的顺序一致性。

3. 面向恢复的计算（RoC）

   特点：

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

14. 分布式系统共识机制

14.1 基础概念

14.1.1 背景

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

14.1.2 系统特性

基于BASE理论：

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

14.2 Paxos算法

14.2.1 基本概念

角色定义：

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

消息类型：

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

14.2.2 算法流程

阶段1（Prepare）：

Proposer：

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

Acceptor：

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

阶段2（Accept）：

Proposer：

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

Acceptor：

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

14.2.3 算法特性与示例

1. 无冲突情况：

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

2. 并发提案冲突：

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

3. 安全性保证：

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

14.3 Raft算法

14.3.1 核心概念

角色定义：

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

任期：

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

14.3.2 选举过程

1. Follower在超时未收到Leader心跳后，转换为Candidate。
2. Candidate增加当前任期编号，向其他节点发送选票请求。
3. 如果Candidate获得多数选票，成为新的Leader。
4. Leader定期发送心跳消息，维持领导地位。
5. 如果其他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 协议流程

1. 请求阶段：

   • 客户端发送请求消息到主节点。

2. 预准备阶段：

   • 主节点为请求分配序号，并广播预准备消息给所有节点。

3. 准备阶段：

   • 节点验证预准备消息，确认消息的合法性。
   • 节点广播准备消息给所有参与节点。

4. 提交阶段：

   • 节点在收到2f+1个准备消息后，广播提交消息。

5. 执行阶段：

   • 节点在收到2f+1个提交消息后，执行请求并向客户端发送响应。

14.4.3 视图变更

触发条件：

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

过程：

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

总结：

• 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的有状态与无状态模式

1. 无状态NFS：

   • 优点：
     • 服务器实现简单，易于扩展。
     • 即使服务器崩溃，客户端无需恢复状态。
   • 缺点：
     • 无法实现文件锁定，容易导致并发访问冲突。

2. 有状态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 同步方案

1. 立即传播改动

   • 优点：简单直接，确保所有副本实时一致。
   • 缺点：效率低下，增加网络带宽消耗。

2. 会话语义

   • 特点：文件修改仅对修改进程可见，文件关闭后对其他进程可见，降低同步频率。
   • 适用场景：适用于需要中间状态不可见的应用，如文本编辑器。

3. 只读文件

   • 特点：文件仅支持创建与读取，避免写操作带来的同步问题。
   • 适用场景：适用于日志文件、备份文件等仅需读操作的场景。

4. 原子事务

   • 特点：通过事务机制，保证共享文件的操作具有原子性，即操作要么全部成功，要么全部失败。
   • 适用场景：需要确保操作一致性与完整性的应用，如数据库系统。

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 著名分布式计算框架

1. Hadoop

   • 组件：HDFS（分布式存储）、MapReduce（计算模型）、YARN（资源管理）。
   • 特点：适用于批处理大数据任务，具备高容错性与可扩展性。

2. Spark

   • 特点：内存计算框架，支持多种计算模式（批处理、流处理、机器学习、图计算）。
   • 优势：高性能、易用性，广泛应用于实时数据分析与机器学习任务。

3. MPI（Message Passing Interface）

   • 特点：面向高性能计算的并行编程模型，适用于需要低延迟、密集通信的应用。
   • 应用：科学计算、工程模拟、大规模并行应用。

4. Storm

   • 特点：实时流处理框架，适用于实时数据分析与事件处理。
   • 优势：低延迟、高吞吐，广泛应用于流数据处理系统。

18.3 分布式机器学习平台

1. Parameter Server（参数服务器）

   • 功能：管理和存储机器学习模型的参数，实现高效的参数访问与更新。
   • 技术：采用一致性哈希进行参数分区，支持分布式并行训练。

2. 分布式训练策略

   • 数据并行：将数据集划分为多个子集，分布到不同的训练节点并行处理。
   • 模型并行：将模型划分为不同部分，分布到多个节点进行并行计算。

3. 容错机制

   • 任务重试：在节点失效时，重新分配任务以保证任务完成。
   • 参数恢复：通过日志或快照机制，恢复模型参数状态，确保模型一致性。

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

18.4.1 分布式深度学习的挑战

1. 计算复杂度高

   • 深度学习模型包含大量参数，训练过程需要高性能计算资源。
   • 需要高效的计算资源管理与任务调度策略。

2. 通信瓶颈

   • 模型参数的同步与更新会占用大量网络带宽，影响训练速度。
   • 需要优化通信协议与算法，减少带宽占用。

18.4.2 分布式深度学习平台

1. FloydHub：https://www.floydhub.com/

   • 提供全托管的深度学习训练与部署服务，简化分布式训练流程。

2. OpenPAI：https://github.com/Microsoft/pai

   • 微软开源的分布式人工智能平台，支持大规模分布式训练与模型管理。

3. PaddlePaddle：http://www.paddlepaddle.org/

   • 百度开发的深度学习平台，支持高效的分布式训练与大规模模型部署。

4. Kubeflow：https://www.kubeflow.org/

   • 基于Kubernetes的机器学习平台，支持分布式训练、模型部署与管理。

5. 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）分离，提升系统性能与扩展性。

• 优势：

  • 极高的吞吐量与低延迟，适用于需要高速数据访问的应用场景。
  • 灵活的扩展性，能够支持数万个客户端并发访问。
  • 高容错性，通过镜像与冗余机制保障数据安全。

20. 安全性在分布式系统中的应用

20.1 NFS的安全性

• 主要关注点：

  • 客户端与服务器之间的通信安全，防止数据被未授权访问或篡改。

• 常用策略：

  • 使用基于Kerberos的认证机制，确保通信双方身份合法。
  • 加密数据传输，防止数据在传输过程中被截获或篡改。

20.2 安全的RPC

• 身份认证方法：
  • 密钥交换：通过公钥基础设施（PKI）交换密钥，建立安全通信会话。
  • Kerberos协议：通过票据机制进行身份验证，防止未授权访问。

20.3 安全的对等文件共享系统

• 基于DHT的安全查找：
  • 防范Sybil攻击：限制每个实体的身份数量，确保网络中节点的真实性。
  • 防范Eclipse攻击：通过多路径路由与节点验证，防止攻击者控制路由表。
  • 安全传输：确保节点间的数据查找请求经过加密与认证，防止数据窃取与篡改。

21. 总结

本课程全面涵盖了分布式系统的核心概念、架构设计、通信机制、一致性与复制、容错与可靠性保障以及分布式文件系统的实际应用。通过理论学习与案例分析，能够深入理解分布式系统的复杂性与设计挑战，掌握解决这些问题的关键技术与方法，为未来的研究与实际应用奠定坚实基础。

学习建议：

• 实践操作：通过搭建分布式系统实验环境，亲自体验分布式系统的部署与管理。
• 案例分析：深入分析HDFS、Ceph、Lustre等分布式文件系统的架构与实现，理解其设计理念与优势。
• 前沿探索：关注分布式系统领域的最新研究与技术发展，如分布式一致性协议的改进、新型分布式存储方案等。

通过系统学习与实践，将具备设计、实现与维护高性能、高可用性分布式系统的能力，满足现代计算与大数据时代的需求。