《分布式系统》课程笔记汇总

分布式系统概述

分布式系统的定义

集中式系统：所有服务和计算都在一台或少数台计算机上进行，且这些计算机彼此之间物理互连

分布式系统产生的两大原因

高性能微处理器的开发，使得计算机的体积显著变小，同时计算性能维持较高水平
高速计算机网络的发明，使得计算机之间通过计算机网络实现远距离通信和无线通信，同时保持高速传播

分布式系统：是若干独立计算机的集合，但这些计算机对于用户来说就像是单个耦合系统

硬件层面：计算机之间是彼此独立的
软件层面：用户只与自己计算机上应用程序进行交互
物理层面：计算机分布在不同的物理位置
逻辑层面：计算机是逻辑集中的和高耦合的

中间件（Middleware）：位于操作系统和应用程序之间，属于软件层，屏蔽不同操作系统、网络协议、硬件架构的差异，为应用程序提供统一的接口，使不同计算机之间可以实现分布式任务

分布式系统的四个目标

资源可访问：确保系统中的资源在分布式环境中对用户始终可用，且用户访问分布式系统中的资源就像访问本地资源一样快速简单

透明性：隐藏分布式系统的底层工作或底层信息，使用户感知不到系统的分布式特性

完全透明性难以实现，需要消耗更多资源来维持“无感知”状态，增加系统负担
完全透明性不可取，用户需要及时发现系统的性能问题，或者需要暴露系统特征来为用户提供个性化服务

开放性：通过标准化接口、组件和协议等方式，使不同平台、语言和系统能够无缝协作

互操作性：不同系统、应用或组件之间能够无缝协同工作，互相交换和理解数据
可移植性：应用或组件可以在不同的硬件或软件环境之间迁移而不需要修改或仅需最小的修改
灵活性：系统能够根据需求变化快速进行调整和扩展而不影响系统的整体架构

可扩展性：分布式系统可以根据需求来进行扩展，同时保持性能稳定

规模：分布式系统能够随着需求的增长而增加资源和用户
地域：分布式系统系统可以跨多个地理区域部署
管理：随着系统规模和复杂性的增加，系统的管理和维护工作量不会显著增加

分布式系统的分类

分布式计算系统

集群计算系统：多台通过网络连接计算机组成的计算系统，每台计算机是同构的，单个程序可以在多台计算机上并行运行

网格计算系统：由来自各地的节点组成的计算系统，每台计算机是异构的，通过虚拟分层组织来实现一组计算机之间的协同工作

云计算系统：由云服务提供商建立的面向服务的计算系统，通常由大量服务器和数据库在一个位置组成，通过网络和虚拟化技术为用户提供计算服务

分布式信息系统

事务处理系统：通过事务监视器保证事务的正确执行，确保数据的正确性

企业应用集成：通过中间件将客户端的请求合并，分散到各个服务器处理，同时企业内部各个独立的服务器和应用程序之间也可以进行通信

分布式普适系统

普适计算系统：计算无处不在，被无缝集成到人们的生活和工作中（嵌入式设备）

移动计算系统：用户可以通过移动设备在任何时间、任何地点访问数据和应用（手机、平板）

无线传感器网络：是一组分布式的传感器节点，通过自组织网络相互连接，用于环境监测和物理数据收集（火警检测器）

区分

类型	计算系统	信息系统	普适系统
核心功能	高效完成计算密集型任务	提供高效的数据存储与访问	实时地数据采集和响应
交互方式	基于命令行、程序开发和高级算法设计	通过图形界面、报表和仪表板等方式	通过语音、触控、体感、环境监测等方式
适用领域	科学计算、分布式处理框架	分布式数据库、企业信息系统	物联网、智能家居、生态环境

体系结构

样式

样式决定了组件之间相互的连接方式、组件之间的数据交换以及这些组件如何集成到一个系统中

分层：将系统功能划分为多个层次，每一层实现特定的功能，系统的各个组件通过接口并遵循协议来进行交互，通常来说请求是自顶向下的，响应是自底向上的

基于对象：将分布式系统的组件抽象为对象，对象封装了数据，对象之间通过方法调用进行交互

基于数据：不同组件通过访问共享的数据库或存储系统来进行协作

基于事件：各个组件可以独立处理事件，组件之间通过分布式事务的方式保证分布式系统中跨节点操作的一致性

类型

集中式架构

集中式架构：系统的所有主要计算和决策都依赖于一个或少数几个中心节点，其他客户节点与这些中心节点交互来完成任务

简单性：架构设计和实现较为简单，适合小规模系统
单点故障：中心节点一旦失效，系统无法正常工作

应用分层：应用程序被划分为多层，每一层专注于完成特定任务，每层之间通过定义明确的接口进行通信

用户接口：为用户提供访问应用程序的方式
处理层：应用程序的实现，负责业务逻辑和数据处理
数据层：存储、管理和维护应用中的数据

客户端-服务器的组织结构

瘦客户：客户端只实现用户接口层，服务器实现处理层和数据层
胖客户：在客户端添加部分业务逻辑和数据存储

非集中式架构

非集中式架构：没有中心节点，所有节点在功能和地位上是对等的，任务和数据在整个网络中分布

对等性：每个节点既可以是客户端，也可以是服务器
分布性：消除了单点故障问题
扩展性：能够动态添加新节点，适应大规模系统

P2P类型

结构化P2P：基于分布式哈希表和确定性算法，将节点组织在一个特定拓扑结构的覆盖网络中
非结构化P2P：基于随机图、泛洪和随机游走机制，将节点组织在一个松散耦合的网络中
分层P2P：将节点分为超级节点和普通节点，超级节点负责管理普通节点并协调数据检索，普通节点只能与超级节点连接，超级节点之间相互连接

混合式

混合式架构：结合了集中式和分散式的特点，既有中心节点提供核心功能，又利用对等节点来提升性能和扩展性

边界服务器系统：边界服务器处理终端用户的请求，将其转发到内部网络进行处理

协作分布式系统：客户节点和服务节点的角色是动态的，跟踪器只用来决定谁作为服务节点，但不提供计算服务

中间件机制

包装器（wrapper）：封装底层组件的复杂逻辑，为上层提供统一、简化的接口

代理（proxy） / 中介（broker）：作为客户端和服务器之间的中间节点，负责请求的转发和增强功能

适配器（adapter）：用于在接口不兼容的组件之间进行转换，使它们能够协同工作

中断器（interceptor）：在请求处理流程中插入自定义逻辑

自治体系结构

自治的体现：自我管理、自我恢复、自我配置、自我优化等

反馈控制循环

监控：收集系统运行状态的实时数据
分析：评估监控数据，确定系统是否符合设定的性能目标，以及是否出现偏差或异常
计划：制定纠正措施、优化策略和调整方法，以便系统可以回到期望状态
纠正/执行：根据调整措施执行新的操作
反馈：执行后的状态信息会再次反馈到监控模块

进程

进程与线程

区分进程和线程

类型	定义	上下文内容	特点
进程	独立运行的程序实例	有自己的独立地址空间，还记录CPU、内存管理单元和转换后备缓冲器的资源信息	粗粒度、独立性强、切换成本高、通信需要依靠IPC
线程	是进程中的一个执行路径，是最小可执行一系列指令的软件处理器	共享进程的地址空间和全局资源，但有自己的寄存器状态	细粒度、共享资源、通信简单、轻量级

多线程进程的优势

线程共享进程的内存和资源，通过并发执行任务，最大化 CPU 和内存等资源的利用
当一个线程等待 I/O 操作完成时，其他线程可以继续执行，从而提高程序的响应速度
线程的创建和切换成本低于进程，能显著提升任务处理效率

多线程客户端：客户端派生多个线程，每一个线程负责一个调用，适合调用目标是不同的服务器，将会得到线性加速。

比如说浏览器获取网页内容，只要浏览器收到html文件，就可以根据html文件中的多个url创建多个独立的线程来拉取资源

多线程服务器：服务器建立一个分发者线程和多个工作者线程，分发者线程用于接收来自网络的请求，然后将请求内容按需分配给工作者线程执行

虚拟化

虚拟化作用

虚拟化：通过软件技术将物理资源抽象成多个逻辑资源的过程

提高资源利用率：可以根据需求动态调整资源分配
提供跨平台支持：屏蔽底层硬件和操作系统差异
便于开发与测试：开发人员可以轻松模拟不同环境，运行多种操作系统或软件版本
集中管理分布式资源：集中监控和管理所有虚拟机
新硬件适配：通过虚拟化技术延长旧应用的使用寿命
提高系统可靠性：虚拟机之间相互隔离，单个虚拟机故障不会影响其他虚拟机
提高系统扩展性：支持弹性扩展
提高系统灵活性：支持迁移

虚拟化技术

计算机系统的接口（自顶向下）

由库函数组成的应用程序编程接口（API）
由系统调用组成的操作系统接口
由机器指令组成，可由应用程序激起的软件-硬件接口
由机器指令组成，只由特权程序激起的软件-硬件接口

虚拟化技术

进程虚拟机（Process VM）：运行在操作系统之上，为单个应用程序提供一个独立的运行环境，使应用程序能够在不同平台上运行，而无需关心底层硬件和操作系统的差异
原生虚拟机监控器（Native VMM）：运行在物理硬件上，为多个虚拟机提供资源管理和隔离，独立于宿主操作系统
主机虚拟机监控器（Hosted VMM）：运行在宿主操作系统上，通过宿主系统管理硬件资源，并为虚拟机提供资源分配和隔离

虚拟化类比

假设现在有一个很大的空屋子，但只能用来住一个人

通过隔断墙（虚拟化技术），将屋子划分为多个独立的房间（虚拟机）

每个房间都可以住一个人（提高资源利用率）

每个房间都有自己的钥匙和设施，用户之间互不影响（提高系统可靠性）

需要时，可以增加更多的隔断来创造新的房间，或者消除隔断墙来获得更大的房间（提高系统灵活性）

不同房间可以按照用户的需求设置成不同风格（跨平台支持）

如果某个房间需要修缮，可以快速将租户搬到另一栋房子中（提高系统灵活性）

房东设计了双人房型，只为双人提供房间（进程虚拟机）

房东根据用户需求来管理隔断墙，从而构造和分配房间（主机虚拟机监控器）

屋子本来就带有隔断墙，即已经分配好了房间，房东直接管理房间（原生虚拟机监控器）

云计算服务

云计算服务：通过虚拟化技术和互联网来提供服务，用户无需直接管理底层硬件和基础设施，只用按使用量付费

基础设施即服务（Infrastructure-as-a-Service, IaaS）：提供虚拟化的计算资源，如服务器、存储空间、网络带宽等
平台即服务（Platform-as-a-Service, PaaS）：提供开发、运行和管理应用程序的平台，屏蔽底层基础设施，用户只需关注应用程序的开发和部署
软件即服务（Software-as-a-Service, SaaS）：提供基于云的完整应用程序，用户通过浏览器或客户端直接访问软件功能，无需关心底层平台或基础设施

IaaS：利用提供的材料和工具，需要自己设计和建造房子
PaaS：利用建造好的房子，只需要进行装修和布置家具
SaaS：利用装修好的房子，直接领包入住

客户端

客户端定义：向用户提供接口，与远程服务器通过网络进行通信和交互，并接收来自服务器的数据以展示的程序或设备

客户端接口

应用特定：为特定应用程序量身定制，具备与该应用密切相关的功能和设计，如音乐软件、游戏软件等
应用无关：通用接口，不依赖于特定的应用逻辑，可以被不同的应用所使用，如浏览器

客户端的透明性：意识不到服务器的位置，意识不到服务器是否切换，意识不到服务器是否故障，意识不到是否将请求发送给多个服务器

服务器

服务器模式

服务器的组织结构	迭代（iterative）	并发（concurrent）
定义	一次只处理一个客户端请求，在完成请求后才会处理下一个请求	可以同时处理多个客户端请求，同时为多个客户端提供服务
流程	用队列记录请求，按顺序一个接一个处理	为请求创建一个新的线程或进程单独处理
优势	编程简单，适用于单个请求处理时间较短的场景	具有高吞吐量和响应速度
缺点	会阻塞后续请求，造成长响应时间	需要处理资源竞争、数据死锁等问题

状态	状态相关的（stateful）	状态无关的（stateless）
定义	在处理客户端请求时，会维护客户端的状态信息，如上下文信息和历史信息	服务器对每个请求是独立的，不记录任何客户端状态信息
优点	减少数据传输次数，减小请求消息大小	服务器崩溃不会影响客户端状态
缺点	需要复杂的同步机制和额外的存储空间	需要客户端一次性发送请求全部内容

RESTful API是遵循REST原则的统一接口，直接使用HTTP中的各种方法来定义对资源的操作，如GET、PUT、POST、DELETE等，其中资源在网络中由URL标识，服务器不会保留客户端对状态信息，客户端需要在每次请求中包含足够的信息以完成请求

服务器发现

静态分配：客户端直接使用固定的端口号和地址来访问服务器，比如说HTTP服务通常运行在80端口

目录服务器：服务器将自己的端口和地址注册到目录中，客户端访问并查询目录服务器来获取可用的服务器

超级服务器：不处理请求，而是负责根据请求选择合适的服务器实例

服务器集群

负载均衡器/逻辑交换机：分配客户请求
服务器：处理客户请求
数据库：处理数据读写

TCP handoff：在分布式系统中将一个 TCP 连接从一个服务器转移到另一个服务器，同时保持连接的连续性和透明性

轮询：按指定顺序，依次分发到不同服务器
基于服务类型：网页请求分发到Web服务器，文件请求分发到FTP服务器
基于服务器负载：监控每个服务器的负载情况，将请求分配到负载较低的服务器

请求内容混合分发

交换器（switch）：转发请求
调度器（dispatcher）：检查请求的具体内容，确定最合适的服务器
分发器（distributor）：根据调度器提供的信息，执行TCP handoff，并通知交换机

归属地址（Home Address, HoA）：提供一个稳定永久的访问点，使得客户能够无缝访问服务，无论服务端在分布式网络中如何变化或移动，客户端始终通过该地址访问服务，从而在客户端视角下呈现出一个强大且一致的服务器

代码迁移

迁移

定义：将代码从一个节点移动到另一个节点运行的过程

负载均衡：将计算任务从繁忙的服务器迁移到空闲服务器
最小化通信：将代码迁移到存储数据的节点可以减少网络通信的开销
移动性支持：确保移动设备的服务连续性

进程迁移的组成

指令段：包含程序的所有代码（字符文本）
资源段：包含程序所需的所有外部资源（设备访问、数据库连接、文件访问）
状态段：包含程序运行时的状态（变量值、程序堆栈）

类型

弱迁移：只迁移代码段，目标节点需要重新初始化运行环境，从起点开始运行
强迁移：迁移代码段和执行状态段，目标节点从迁移中断的地方继续执行

资源段处理

绑定方式

未连接（Unattached）：资源未绑定到任何特定机器，由进程动态分配（临时内存、线程）
附着连接（Attached）：资源附加到某一特定机器，通过网络连接到进程（网络文件、数据库）
紧固连接（Fixed）：资源直接通过物理 I/O 接口连接到进程所在的本地机器（I/O接口、GPU卡）

迁移策略

GR（Global Reference，全局引用）：创建一个分布式系统范围内的全局引用
MV（Move，移动资源）：将资源移动到当前需要使用的机器
CP（Copy，复制资源的值）：复制资源的值到需要的机器上
RB（Rebind，重新绑定资源）：将进程重新绑定到资源

异构系统的迁移

异构系统指的是由不同的硬件架构、操作系统、编程语言或运行环境组成的系统，迁移后的代码可能不适合在目标机器上执行。

抽象层：使代码运行在统一的抽象环境中，而无需关心底层硬件和操作系统
解释器：使用解释性代码，使得代码能在不同平台上通过解释器运行
虚拟机监控器：利用虚拟化技术在目标节点模拟一个与源节点一致的环境，使迁移的代码能够无缝运行

虚拟机迁移：将整个虚拟机实例迁移

静态迁移：停止当前的虚拟机，迁移内存，然后重新启动虚拟机
动态迁移：将源虚拟机的内存内容逐步推送到目标主机，在迁移过程中，如果出现脏页，则重新发送这些页面

进程通信

网络通信

协议：对规则归纳总结，并加以形式化

OSI模型

中间件协议

提供高级通信协议
实现数据包装和解包装
支持资源命名和动态发现
提供复制和缓存优化性能

RPC

存根

存根机制（stub）

客户端存根负责将函数名、参数等打包成网络请求消息，发送到网络，从而传递给服务器
服务器接收到消息后，由服务器存根解析请求消息，然后执行远程过程，最后将结果打包成网络响应消息，发送到网络，从而传递给客户端
客户端接收到消息后，由客户端存根解析响应消息，将结果返回给调用的应用程序

客户端-服务器绑定：先通过目录服务器找到目标服务器，然后在目标服务器上找到执行远程过程的进程

RPC 类型

普通RPC：客户端发出请求后，会等待服务器的响应，在收到响应之前无法继续执行其他任务
异步RPC：客户端发送请求后，只等待请求被接收的确认，无需等待服务器的处理请求的结果，客户端可以继续执行其他任务
延迟异步RPC：在异步RPC的基础上，客户端发出请求后可以继续执行其他任务，在稍后需要结果时主动阻塞来等待服务器响应

面向消息的通信

瞬态通信

瞬态通信（Transient）：通信双方需要同时在线

套接字（Socket）：一种通信端点，应用程序通过套接字直接进行消息传递

消息传递接口（Message-Passing Interface, MPI）：是一种用于并行计算和分布式计算的标准化消息传递库接口

持久通信

持久通信（Persistent）：在发送方和接收方不需要同时在线的情况下，依然能够确保消息的可靠传递

消息队列系统：发送方将请求消息放入队列后即可继续处理其他任务，接收方按需从队列中获取消息，发送方不需要在接收方运行的时候才能发送请求，接收方也不需要在发送方运行的时候才能处理请求

队列管理器：查找映射信息，将消息从发送方路由到目标队列所在的主机和端口

消息路由器：对消息进行路由与转发，确保消息能够准确地从发送方传递到接收方，也就是说，队列管理器不将消息发给目标队列，而是发给消息路由器，减少本地存储消耗，将工作转移到消息路由器来处理

消息转换器：解决不同应用或系统之间消息格式不兼容的问题，将输入消息转换为目标应用能够识别和处理的格式

面向流的通信

面向流的通信：是一种专注于连续数据传输的通信方式

连续性：数据以连续的流形式传输，而不是独立的消息或分段
时间敏感：对延迟和抖动有较高要求
双向通信：支持互相通信

服务质量（Quality of Service, QoS）

数据传输的比特率
创建会话的最大延时
端到端的最大延时
最大延时抖动
最大往返延时

QoS技术

缓冲区：调节速率差异，减少丢包和延迟，提高传输效率
编码：压缩数据提高效率，或加入冗余信息检测和纠正传输错误
帧交织：分散传输错误，减少连续错误的影响，提高数据恢复能力

多播通信

IP Muticast：直接使用IP协议的多播功能，数据包只需要发送一次，由路由器在网络层复制并传递

Overlay-based Muticast：在应用层构建一个覆盖网络的拓扑结构，在应用层通过逻辑连接确定多播的接收方

Gossip-based Muticast：节点与随机选择的邻居交换消息进行传播

分析

IP受限于多播协议的部署
Overlay适合数据分发和实时通信，如分布式文件共享和流媒体分发
Gossip适合状态同步和数据广播，如分布式数据库和动态传感器网络

命名系统

基本概念

命名系统：用于标识和访问分布式系统中资源的机制，通过名称将资源与其具体位置或属性关联起来，便于用户和系统之间的交互

组成

名称：标识分布式系统中实体对象的可读字符串
标识符：唯一标识分布式系统中某个实体的名称
实体：分布式系统中的任何事物
访问点：访问实体的入口，提供与实体交互的接口
地址：访问点的名称，提供实体的物理或逻辑位置

无层次命名

定义：命名只是标识符，无层次结构，不包含位置信息，通常由随机生成的字符串组成

如何找到资源

基于网络协议：通过网络广播或多播的方式查询目标名称对应的实体或资源
转发指针：当资源移动时，原位置留下指向新位置的指针，客户端沿着指针链找到资源

宿主地址：通过固定位置的宿主主机记录资源地址，客户端联系宿主获取资源的最新地址

分层定位：构建分层的搜索树，资源地址存储在叶子节点，目录节点表示区域信息

分布式哈希表：将资源和节点的名称通过哈希函数映射为固定长度的键值，通过邻居信息逐步到达目标节点

Chord

逻辑环：所有节点和资源的键值在这个范围内按顺时针排列，形成一个环状结构

实体键值：每个节点都有一个唯一的键值，表示该节点在逻辑环上的位置

资源键值：每个资源也有一个唯一的键值，仅仅是资源的标识符

资源和实体的键值均由同一个哈希函数，因此范围都是 $0 ～ 2^m - 1$ ，但是二者属于不同的概念，即使键值可能重叠，也不产生冲突

资源存储规则：资源键值为 k 的资源存储在第一个键值大于等于 k 的节点上，也就是所有节点键值>资源键值中的最小键值节点

指状表：每个节点维护的一个条目数为从 1 到 m 的表，每个条目对应一个节点键值，即指向对应节点的指针

指状表规则：第 $i$ 个条目指向当前键值为 $p$ 的节点沿顺时针方向从 $(p + 2^{i-1}) \bmod 2^m$ 开始往后第一个存在节点

节点 p 的后继者 successor(p) 是位于 p 之后的第一个存在节点，即指状表第一个条目记录的节点

在键值 m 和键值 n 的节点之间插入/删除键值 k 的节点：原本属于节点 n 且范围为 $(m, k]$ 的资源会转移到节点 k，反之亦然

键值为 p 的节点查找键值为 k 的资源

若 $p \leq k < Finger[1]$ ，则资源在 successor(p)，查找结束
否则，从指状表中找到最大的键值 n 满足 $n \leq k$
令 $p \leftarrow n$ ，回到第1步

分析

理论复杂度为 $O(\log N)$ ，其中 $N$ 是系统中存在节点的数量，即逻辑环中存在节点的数量
当新节点加入时，需要更新相关节点的指状表

结构化命名

定义：适合人类理解的命名方式

基于目录的文件命名：/home/user/documents/report.txt

叶子节点：标识具体实体的名称，还可以存储实体属性等信息
非叶子节点：作为目录节点，有多条边连接其他节点，用于分类

基于层次的主机命名：www.example.com

全局层：根节点及逻辑上靠近根节点的目录节点
行政层：组织内部管理的目录节点
管理层：动态变化的节点

迭代式解析：客户端负责主动与每一级名称服务器交互，每次请求一个服务器，获取下一步的解析地址，直到最终获取资源的具体地址

递归式解析：客户端将解析请求交给一个名称服务器，由该名称服务器代替客户端完成所有后续解析，最终将结果返回给客户端

基于属性的命名

定义：通过“属性-值”对来标识和查找资源，如通过<location: China, id: 111, type: server>来查找服务器

实现方式

集中式目录服务：所有数据存储在一个中心化的服务器中
层次化目录服务：使用目录信息树组织属性和值
去中心化目录服务：数据分布存储在多个节点，无单一服务器
语义覆盖网络：节点按照特定的属性值语义（如主题、内容、属性等）进行组织和连接，只连接具有相似语义兴趣的节点

同步性

时钟

网络时间协议

网络时间协议（Network Time Protocol, NTP）：通过时间服务器同步系统时间，假设从客户端到服务器的延迟等于从服务器到客户端的延迟

客户端在T1时刻发送时间同步请求
服务器在T2时刻接收到请求，在T3时刻返回当前时间和时间戳
客户端在T4时刻接收到响应，根据时间偏移公式： $\Delta t = \frac{(T2 - T1) + (T3 - T4)}{2}$ 计算时间差
校正本地时间： $t \leftarrow t + \Delta t$

Berkeley算法

Berkeley算法：通过系统中的各节点相互协作，计算出一个统一的平均时间，并调整各节点的本地时钟，使其尽可能同步

选定协调者节点，负责时间同步的计算和协调
协调者向所有其他节点（包括自己）发送时间同步请求，记录发送请求的时间
每个节点将自己的本地时间和估算的网络延迟一起返回给协调者
协调者根据收到的所有时间值，考虑网络延迟对时钟偏差的影响，计算系统中所有节点的平均时间
协调者将每个节点的时间偏差（平均时间 - 节点时间），发送给对应节点
各节点根据收到的时间偏差值调整本地时钟

Lamport算法

逻辑时钟：基于 “happens-before” 关系定义了事件的顺序，关心事件的逻辑时间，而不关心事件的实际时间

相同进程内，如果a先于b发生，则a->b
不同进程间，如果a向b发送消息，则a->b
如果a->b,b->c则a->c
如果a和b无法通过上述两个规则定义顺序，则称他们是并发的，a||b

局限性：两个逻辑时钟相等的事件可能是并发的，但算法无法明确表达这种并发关系

Lamport算法：每个进程维护一个本地计数器C

当进程 $P_i$ 内部发生一个事件时，递增计数器 $C_i = C_i + 1$
当进程 $P_i$ 发送一条消息 $m$ 时，将其当前的逻辑时钟 $C_i$ 附加到消息中 $ts(m) = C_i$
进程 $P_j$ 收到消息后，根据 $C_j = \max(C_j, ts(m)) + 1$ 调整自己的本地计数器

向量时钟

向量时钟：扩展 Lamport 逻辑时钟的机制，可以明确地区分事件是因果相关还是并发

每个进程 $P_i$ 维护一个长度为 N 的向量 $V_i$ ，其中 N 是系统中节点的总数
向量的每个元素 $V_i[j]$ 表示进程 $P_i$ 所知道的关于进程 $P_j$ 的逻辑时钟

工作机制

本地事件：当进程 $P_i$ 执行一个事件时，更新向量时钟关于自己的分量： $V_i[i] = V_i[i] + 1$
发送消息：当 $P_i$ 发送消息 $m$ 时，将自己的向量时钟附加到消息中： $V_m = V_i$
接收消息：当 $P_j$ 接收消息 $m$ 时，更新向量时钟的全部分量， $V_j[k] = \max(V_j[k], V_m[k]) \quad \forall k$
交付消息：当 $P_j$ 交付消息 $m$ 时，更新向量时钟关于自己的分量： $V_j[j] = V_j[j] + 1$

如果向量时钟可以比较，则事件是因果的，否则是并发的

$a \to b \iff V_a < V_b \iff \forall k, V_a[k] \leq V_b[k] \land \exists k, V_a[k] < V_b[k]$

强制因果有序：当且仅当满足以下条件，才能交付消息

$V_j[i] + 1 = V_m[i]$ ：保证消息的顺序交付
$V_j[k] \geq V_m[k] \quad \forall k \neq i$ ：保证已经接收了消息所依赖的所有前置消息

互斥

互斥：同一时间内，共享资源只能由一个进程访问

集中式算法：选举一个进程作为协作者，进程需要向协作者发送资源请求，协作者根据全局信息来判断请求是否被允许

Ricart & Agrawala算法：当进程要访问一个共享资源的时候，需要构造一个请求消息，发布给全部进程（包括自己），当且仅当接收到全部进程的OK消息，才能使用该资源

接收进程在临界区内没有访问需求，直接返回OK
接收进程在临界区已获得对资源的访问，不应答，将请求放入队列
接收进程也在请求该资源，如果收到消息的时间戳比自己请求的时间戳小，则返回OK，将请求放入队列

令牌环算法：将进程组织成逻辑环，令牌在这些进程之间传递，只有获得令牌的进程才能进入临界区访问共享资源

选举

选举：分布式系统中需要选取一个进程来作为特殊角色，实现特殊功能

Bully算法

如果某个节点发现当前的领导者失效，它会作为发起者，向所有比自己 ID 大的节点发送选举消息
收到选举消息的节点会回应，表明自己存活，同时如果自己的 ID 更大，它会成为新的发起者，再次向所有比自己 ID 大的节点发送选举消息
如果某一轮选举的发起者没有收到任何回应，说明它的 ID 是系统中最大的
最后的发起者会作为领导者，广播消息到其他全部节点，宣布自己为新领导者

Ring算法

如果某个节点发现当前的领导者失效，它会将自己的 ID 放入选举消息中，并传递给下一个节点
每个节点收到选举消息后，与自己的 ID 比较，如果自己的 ID 更大，替换选举消息中的 ID，并将消息继续传递
当选举消息传递一圈回到发起者时，发起者可以知道谁的 ID 是最大的
发起者宣布该 ID 的节点为新领导者，并广播确认消息

一致性

副本管理

副本的意义

提高可靠性：即使某些节点故障，仍可以使用其他副本来维持服务
提高性能：副本的数量和位置可以根据客户端的地理分布或请求负载动态调整

副本放置

客户端感知：最小化客户端与副本服务器之间的平均距离，从而降低访问延迟
网络感知：优先选择具有最大带宽的来部署副本服务器
基于区域：在每个区域内选择一个低延迟节点部署副本服务器

副本类型

永久副本：在系统设计时就静态配置，是稳定的存储节点，用于长期保存数据
服务器发起的副本：由服务器根据负载或访问模式动态生成和管理，用于优化系统性能
客户端发起的副本：当客户端访问某些数据时，本地保存一份缓存副本以降低重复请求的延迟

内容分发

类型：传播更新通知，传播更新数据，传播更新操作
推送机制：服务器主动向副本推送更新，适合读多写少的场景，客户端可以即时获取最新数据，但是可能导致不必要的网络开销
拉取机制：客户端或副本主动从服务器拉取更新，适合读少写多的场景，可以降低服务器负担，但是客户端可能会延迟获取最新数据

CAP理论：在一个分布式系统中，CAP三者无法同时完全满足，因此开发者必须在三者之间进行权衡

一致性（Consistency）：每次读操作都能返回最新写入的数据
可用性（Availability）：系统始终可以响应每个请求
分区容忍性（Partition Tolerance）：系统在出现网络分区的情况下，仍能继续运行

以数据为中心的一致性

持续一致性：不保证操作的即时一致性，但要求系统最终会收敛到一致状态

顺序一致性：所有进程都以统一的顺序观察到读写操作

因果一致性：只有存在因果关系的操作才需要保持顺序，无因果关系的操作可以乱序

P2 读取到 P1 写入的值 a，说明 P1 的 W(x)a 对 P2 的 W(x)b 有因果关系，因此 P3 不可能先读取到值 b，再读取到值 a
P2 写入值 b 到变量 x，但它没有读取过 a，因此 W(x)b 和 W(x)a 是并发操作，没有因果关系，因此 P3 和 P4 可以按照任意顺序读取 a 和 b

以客户为中心的一致性

类型	定义	现实例子
单调读	如果一个客户端读取了某个数据的值，那么它后续的读取操作不会看到比之前更旧的值	用户在社交网络上看到朋友的最新帖子后，刷新页面时不会看到更旧的帖子
单调写	一个客户端的写操作必须按照它们发出的顺序被系统执行	用户在编辑文档时，先输入“Hello”，再输入“World”，系统必须按此顺序保存
写后读	一个客户端在写入某个数据后，后续的读取操作必须能够看到自己写入的值	用户在购物网站上将商品加入购物车后，刷新页面时能看到该商品在购物车中
读后写	如果一个客户端读取了某个数据的值，那么它后续的写操作必须基于它读取的值	用户在查看银行账户余额后，进行转账操作时，必须基于最新的余额进行计算

一致性协议

主备份写–远程写：所有写操作由主节点处理，主节点将写操作同步到远程的备份节点 -> 顺序一致性、写延迟较高

主备份写–本地写：写操作由本地的主节点处理，本地的主节点将写操作异步同步到备份节点 -> 持续一致性、写延迟较低

全副本写：不存在主节点，写操作需要同步到所有备份节点，确保所有节点的数据一致 -> 顺序一致性、容错性较高

法定人数协议

法定人数（Quorum）：分布式系统中执行读或写操作时需要参与的最小节点数

系统中存在 N 个备份节点
写操作需要等待至少 W 个备份节点确认更新后才认为成功
读操作需要从 R 个备份节点中读取数据，通过时间戳或版本号选择最新的数据

为保证一致性，需满足R + W > N，因为这样读写操作访问的副本集合中至少有一个副本重叠

越大的W和R代表着更高的一致性
越小的W和R代表着更高的可用性

容错性

故障

容错：允许系统部分组件失效，但系统整体仍可继续运行

可靠的系统

可用性：系统在某一时间点可用，强调时刻
可靠性：长时间运行而不中断，强调时段
安全性：系统在出现故障后不会造成灾难
可维护性：系统能够快速检测并修复故障

区分：故障导致错误，错误导致失败

失败：系统未能提供预期的服务，用户视角
错误：系统内部状态偏离了其正确状态，软件视角
故障：系统组件中的缺陷或问题，底层视角

故障类型

暂时故障：一次性短暂故障，可能在不干预的情况下自动恢复
间歇故障：以周期性方式出现的故障，较难排查
持久故障：持续存在且需人工修复的故障，如芯片燃烧、磁盘损坏

故障模式

崩溃性：服务器停机（如操作系统进程错乱）
遗漏性：系统未能正确发送或接收消息（如网络传输错误）
定时性：系统未能按预期时间完成任务（如网络拥堵或阻塞过久）
响应性：系统返回错误的结果（如格式不符合）
随意性：又称为拜占庭故障，表现为系统的任意失效，随机返回结果，包括恶意行为

冗余掩盖故障

信息冗余：通过附加信息检测、定位或纠正错误
时间冗余：通过快速重复执行操作掩盖临时故障
物理冗余：通过添加冗余硬件应对组件失效
三倍模块冗余（TMR）：通过复制三个独立模块并多数投票决定正确结果，容忍单点故障

进程容错

容错进程组：包含多个进程副本的集合，把一个进程组作为一个单一抽象进程来处理，如果其中一个进程失败，可以让其他进程来接管它，从而实现故障掩盖

k容错度：最多k个进程出现故障，系统仍能运行

停止失效故障：需要 k+1 个进程，也就是剩下 1 个可用的进程
随意性故障：需要 2k+1 个进程，也就是需要 k+1 > k 在数量上获得投票优势

故障检测

基于超时机制

主动查询：进程 P 主动向进程 Q 发送探测消息并等待回复
被动等待：进程 P 被动地等待进程 Q 发来心跳消息
区分网络故障和节点故障：请邻居节点进行多方检查

RPC 失效

客户不能定位服务器：客户端需要抛出异常，一定程度上损失透明性

丢失请求消息：客户端启用定时器，超时则重新发送请求

服务器错误：

至少一次语义：不断尝试，直到得到应答
最多一次语义：立即放弃，并报告失败
最多k次语义：执行任意多次
恰好一次语义：理想情况，但无法实现

丢失应答消息：客户端设置超时时间，未收到服务器响应时，重新发送请求

幂等请求：重复执行不会造成任何影响
非幂等请求：同一个请求不能被执行两遍，需要通过标识符来确保服务器只处理一次

客户崩溃：服务器上为该请求创建的进程或线程失去了与客户端的联系，服务器可能仍在处理该请求，造成资源浪费

消灭：客户端根据日志向服务器通告杀死与该客户端相关的孤儿进程或线程
再生：客户端向服务器通知进入新周期，服务器会杀死旧周期中与该客户端相关的孤儿进程或线程
温和再生：服务器定期，检查孤儿进程或线程的状态，并尝试与客户端重新建立联系，如果找不到拥有者，则杀死孤儿进程或线程
过期：每个 RPC 设置超时时间，超时后自动清理孤儿进程

分组通信

接收方在成功接收到消息后返回ACK信号，如果发送方未在指定时间内收到ACK，判断消息丢失并重发 -> 引发ACK风暴

接收方检测到消息丢失时主动发送NACK信号，其他接收方收到NACK就暂时抑制自己的NACK，发送方根据NACK重发丢失的消息 -> 发送方不得不缓存大量分组以等待重发

层次化多播，将所有接收进程分成若干小组，每个小组由一个协调者管理，协调者负责转发来自接收方的消息或来自其他协调者消息

分布式提交

角色

协调者（Coordinator）：负责协调事务的提交或中止
参与者（Participant）：执行事务的具体操作，并向协调者报告执行结果

两阶段协议（2PC）：确保分布式系统中的所有参与者要么全部提交事务，要么全部中止事务，从而保证事务的原子性

准备阶段
1. 协调者向所有参与者发送 “准备好提交” 的投票请求（Vote-request）
2. 参与者根据当前状态回复：同意提交（Vote-commit）或者拒绝提交（Vote-abort）
提交阶段
1. 如果所有参与者都回复 Vote-commit，协调者发送 Global-commit，所有节点执行事务
2. 如果有任一参与者回复 Vote-abort，协调者发送 Global-abort，所有节点中止事务

失效情况

协调者在 WAIT 下超时，发送 Global-abort，自己直接 Abort
参与者在 INIT 下超时，发送 Vote-abort，自己直接 Abort
参与者在 READY 下超时，获取其他参与者的状态
- 都处于 READY 状态，继续等待协调者恢复
- 有一个处于 INIT 状态，自己 Abort
- 返回 COMMIT，执行提交
- 返回 ABORT，执行终止

恢复处理

类别

回退恢复：从错误状态返回到先前的正确状态
前进恢复：从某个状态开始执行到正确状态

消息日志：通过记录分布式系统中进程之间的消息传递历史，结合检查点，用于故障恢复的一种机制

悲观日志：每条消息在应用之前记录到稳定存储，可能导致较高延时
乐观日志：每条消息在应用之后记录到稳定存储，可能会导致孤儿进程
因果日志：只记录与因果一致性相关的消息日志，但是实现很复杂

分布式快照 / 检查点

独立检查点：每个进程创建检查点，但无法保证一致性，可能需要不断回滚到更早的检查点（多米诺效应）
协调检查点：检查点的创建由一个协调者统一触发，确保所有进程的状态是一致的，但检查点的开销较高，需要阻塞所有进程直到全局检查点完成

协定

当分布式系统中在存在故障时，非故障进程能够在有限步骤内达成共识/一致性

确保正确性：所有非故障节点最终达成一致的决策
容忍故障：系统能够应对组件的失效，特别是随机或恶意行为

基于泛洪

任一节点发现系统存在故障时，生成提案消息并通过泛洪传播
每个节点记录接收到的消息，转发给未收到该消息的节点
所有节点对消息的收敛状态达成一致

Paxos

节点角色：节点可以同时扮演多个角色

提议者：提出要达成一致的值
接受者：决定是否接受提议者提出的值
学习者：获取被接受的值并更新

执行轮次

准备阶段
1. 提议者增加自己的轮次编号rnd，向所有接受者发送带有rnd的prepare消息
2. 如果接受者收到的rnd小于last_rnd，则忽略prepare消息
3. 否则接受者更新本地的last_rnd，回复一个promise消息，带有prev_rnd和prev_rnd对应的值v
接受阶段
1. 提议者收到大多数的promise消息后，选择其中prev_rnd最大的消息的值v作为提议值
2. 提议者向所有接受者发送带有rnd和提议值v的accept消息
3. 如果接受者收到的rnd小于last_rnd，则忽略accept消息
学习阶段
1. 接受者将提议值v广播给所有学习者（包括自己）
2. 学习者一旦收到来自大多数接受者的值v，则更新自己的值

局限性

仅支持单个值的一致性
活锁问题：反复出现提议者，导致整个协议长时间没有结果或者崩溃
需要两轮消息传递才能确定一个值

RAFT

节点角色：

跟随者：被动接受心跳或命令
候选者：在选举中自荐为领导者
领导者：负责处理客户端请求和日志复制

工作流程

候选者通过发送请求投票来选举，每次选举节点只能投票一次
如果某个候选者获取多数票，则成为领导者
领导者接收客户端命令，将其追加到日志中，同时将日志覆盖到其他服务器
领导者按照分布式日志提交给每个节点的状态机执行，强行让整个系统恢复一致性

局限性

依赖于日志，如果磁盘损坏将会导致错误
领导者需要将日志覆盖到全部节点，时间开销大
如果领导者崩溃，会导致选举新的领导者，期间无法处理客户端请求
领导者需要向全部节点发送心跳信号，来通知领导者有效，占据网络带宽

BFT 和 PBFT

用于解决拜占庭协议问题：若总节点数满足n > 3f + 1 ，则确保系统可以容忍最多f个恶意节点

BFT

提议阶段：主节点发起提议值，广播提议消息
确认阶段：备份节点验证提议，广播确认消息
提交阶段：备份节点接收 2f+1 个确认消息后，广播提交消息
执行阶段：备份节点收到 2f+1 个提交消息后，执行操作并返回结果

PBFT

请求阶段：客户端向主节点发送一个 Request 消息，<Request, operation, timestamp, client_id>
预准备阶段：主节点生成 Pre-Prepare 消息并广播，<Pre-Prepare, view, seq_no, digest>
准备阶段：备份节点验证后广播 Prepare 消息，<Prepare, view, seq_no, digest>
提交阶段：备份节点收到 2f+1 条合法 Prepare 消息后广播 Commit 消息，<Commit, view, seq_no, digest>
执行阶段：收到 2f+1 条合法 Commit 消息后执行操作，发送 Reply 消息到客户端：<Reply, view, timestamp, client_id, result>
客户端收到至少 f+1 条一致的 Reply 后，接受结果

消息字段

type：消息类型（如 Request、Pre-Prepare、Prepare 等），区分消息的用途。
operation：具体的操作内容（如读或写）。
timestamp：标识请求时间，防止请求被重复处理。
client_id：标识请求来源，用于将执行结果返回正确的客户端。
seq_no：用于维持请求顺序，避免乱序。
digest：消息的哈希值，用于验证消息完整性，防止篡改。
view：当前主节点的标识，支持视图变更机制。

理解

Prepare 和 Commit 需要 2f+1：确保系统中大多数节点（f+1）多于拜占庭节点（f）达成共识
Reply只需要 f+1：保证了至少有一个诚实节点的参与，结果是可信的

区别

PBFT 明确支持视图变更，当主节点失效时，可以选出新的主节点
BFT 复杂度为 $O(n^3)$ ，PBFT 复杂度为 $O(n^2)$

分布式文件系统

NFS：基于客户-服务器

架构

客户端通过VFS屏蔽本地和远程文件系统的差异
NFS客户端使用RPC来操作远程文件
NFS服务器提供其本地文件系统的视图

优势：利用VFS支持异构系统，容易部署

局限性：访问速度受限于网络带宽，不适用于大规模集群环境

HDFS：基于集群

架构

NameNode/主服务器：管理文件系统的元数据，将所有元数据存储在内存中，使用日志和检查点机制保证元数据一致性
DataNode/块服务器：存储实际数据块，定期向NameNode发送心跳信号报告状态
客户端：与NameNode/主服务器交互以获取元数据，与DataNode/块服务器交互以读写数据

优势

可靠性高：多副本存储实现数据可靠性
扩展性高：只需要修改主服务器就可以快速部署块服务器

局限性：主服务器过载可能成为性能瓶颈

Ivy：对称式

架构

基于P2P技术，无中央服务器，所有节点功能相同，任何节点都可以提供文件共享服务
利用分布式哈希表，实现节点间高效的数据定位
文件被分块存储，块通过 DHash 分散在不同的节点上

优势

高可用性：自动应对节点故障
负载均衡：所有节点均可分担数据存储和访问请求
高扩展性：支持节点动态加入或退出

局限性：节点间的协调和一致性维护需要额外开销

大数据分布式系统：mapreduce

核心目标：通过将计算任务分解为小的独立子任务，利用多台机器并行处理数据，从而高效地完成大规模数据分析和处理工作

Split 阶段：输入数据被划分为固定大小的分片，每个分片会被分配给一个 Map 任务处理
Map阶段：每个 Map 任务读取一个输入分片，并将其解析为键值对
Shuffle阶段：将 Map 任务输出的中间键值对按照键进行分组，并将相同键的数据发送到同一个 Reduce 任务
Reduce阶段：对每组键值对进行聚合或计算，生成最终结果，写入分布式文件系统