分布式系统

@Time 2022 / 6 / 10

内部特供 版权所有 翻版必究

第一章 分布式系统概述

1.1 分布式系统定义

• 分布式系统是一组自治的计算机集合，通过通信网络相互连接，实现资源共享协同工作，而呈现给用户的是单个完整的计算机系统

1.2 分布式系统特点

• 隐藏性

  各种计算机的差别 计算机之间的通信方式的差别是隐藏的

• 一致和统一方式

  用户和应用程序无论在何时何地都能够以一种一致和统一的方式 与分布式系统交互

• 易于扩展

  系统是由独立的计算机构成

• 持续可用

  某部分发生故障，总体仍可用 用户注意不到哪部分替换和维修

1.3 分布式系统关键目标

• 资源可访问性

  使用户能够方便的访问远程资源，以一种受控的方式 与其他用户共享这些资源

• 分布透明性

  将资源在多台计算机上分布的事实隐藏起来

  透明性类型
  访问透明性 隐藏资源访问（本地资源和远程资源） 
  位置透明性 隐藏资源所在位置 
  迁移透明性 隐藏资源是否移动到了另一个位置 
  复制透明性 隐藏是否对资源进行复制 
  并发透明性 隐藏资源是否由多个用户共享 
  故障透明性 隐藏资源的故障和恢复 
  伸缩透明性 隐藏系统和应用规模
  

• 开放性

  新的共享资源添加进后能够被各种客户程序使用的（难易）程度

  良好的接口定义 接口定义语言（interface definition lang uage,IDL）编写语法

• 可扩展性

  在资源数量和用户数量激增，系统仍保持运转，该系统则是可扩展的

  • 规模上扩展

    用户 资源

  • 地域上扩展

    用户与资源相隔很远

  • 管理上扩展

    系统跨越多个独立管理机构，仍能方便进行管理

1.4 分布式集中式对比

• ①同步困难：分布式各组件和进程的行为是物理并发的，同步机 制实现起来困难；集中式的系统时间是明确的。
• ②可靠性：分布式部分故障，无需停机，整 体可用；集中式出现故障，需要停机检查维修。
• ③异构性：分布式必须作为一个整体严格遵 循系统的功能规范运行，同时最大限度兼顾各平台的独立性，保持系统的易维护性和易管理 性。
• ④响应时间短：对任务分散、交互频繁、需要大量处理能力的用户来说合适，各台计算 机支持单用户处理能力。
• ⑤可扩充性：根据请求扩充系统、而不必替换现有的系统成分。

1.5 分布式系统分类

• 分布式计算系统

  • 集群计算
  • 网格计算
  • 云计算

• 分布式信息系统

• 分布式普适系统

第二章 体系结构

2.1 逻辑组织结构（软件体系结构）

2.1.1 组织

组件Component 是一个模块单元，可以提供良好定义的接口，并可替 换

链接器Connector 组件之间传递通信 使组件相互协调合作

2.1.2 四种结构样式

• 分层体系结构
  • 组件以分层的方式组织
  • 请求沿层次结构向下 结果向上流动
• 基于对象的体系结构
  • 一个对象即一个组件
  • 组件通过远程调用机制被连接
• 以数据为中心的体系结构
  • 公用仓库 组件通过其获取处理
• 基于事件的体系结构
  • 组件发布事件，中间件确保只有那些订阅这些事件的组件才会接收它们

2.2物理组织结构（系统体系结构）

2.2.1 集中式体系结构

单个服务器实现软件组件 远程客户端可以访问服务器

• 客户 通过向服务器发送请求来请求服务、然后等待服务 器回复

• 服务器 实现特定服务

• 协议

  • 面向有连接协议TCP

    • 传播方式 广域网

    • 优点 范围性小 速度高 可靠性好

  • 面向无连接协议UDP

    • 传播方式 局域网
    • 不足之处 客户无法检测原始信息是否丢失 或相应的传输失败

    简述面向有连接的服务与面向无连接的服务，分析各自的优缺点

    1.面向有连接的服务:消息发送方和接收方必须首先显式的确立连接，可能还需要就采用的协议进行协商，然后两者才可以进行数据交换。
    优点︰按照顺序传输消息，保证传输质量。发送方与接收方可以保持联系，以协调会话，恢复错误
    缺点︰建立连接的开销较大，负载较大，由于需要建立连接，传输过程相对较慢
    2.无连接服务︰交换数据之前不需要有建立连接的过程,消息发送方只需要在准备好的时候开始―传送第一个消息就可以。
    优点︰负载较小，灵活方便，迅速，适用与传输少量报文
    缺点︰接收方不知道消息在传输过程中是否丢失，也不知道是否传输成功。消息不一定按顺序传输，不保证传输质量。
    

• 客户与服务器体系结构区分

  • 多层体系结构（物理上）

    • 两层体系结构

      • 客户端

      • 服务器端

      • 局限性

        • 缺乏有效的安全性 – 客户端和服务器直连，敏感数据丢失或修改

        • 客户端负荷过重 – 处理事务复杂，需要更新客户端程序

        • 服务器端工作效率低 - 连接资源消耗较大

        • 容易造成网络阻塞 - 大量客户端访问服务器造成网络流量剧增

    • 三层体系结构

      • 用户接口层

      • 处理层

      • 数据层

      • 特点

        • 安全性 – 数据隔离

        • 稳定性 – 中间层缓冲了实际连接，数据库实际连接数小于客户 端应用数量

        • 易维护 – 处理程序变化，不影响客户端程序

        • 快速响应

        • 系统扩展灵活 – 可部署多台应用服务器

  • 应用分层（逻辑上）

    • 用户接口层 终端 处理与用户交互
    • 处理层 含应用程序的核心功能
    • 数据层 数据库或文件系统上运行

客户端和服务器区别

硬件方面：客户端是客户的 PC机，服务器是提供计算服务的机器。
软件方面：客户端是客户应用程序，服务器端是实现特定服务的进程（关键字变 SQL） 以及数据库。在一定情况下客户端不一定是客户端服务器也不一定是服务器。用于分布式数据库的服务器可以充当客户端，因为它将请求转发到不同的文件服务器在这种情况下，数据库服务器本身是处理查询

中间件定义

是一种独立的系统软件或服务程序，分布式应用软件借助这种软件在不同 的技术之间共享资源，中间件客户机服务器的操作系统之上，管理计算资源和网络通信。地位：中间件提供的程序接口定义了一个相对稳定的高层应用环境，不管底层的计算机硬件和 系统软件怎样更新换代，只要将中间件升级更新，并保持中间件对外的接口定义不变，应用 软件几乎无需任何修改，从而保护了企业在应用软件开发和维护中的重大投资。目的：屏蔽异构性，给应用程序员提供方便的编程模型，中间件表示成一组计算机上的进程或对象，这 些进程或对象进行交互，实现分布式应用的通信和资源共享支持

2.2.2 非集中式体系结构

每台机器起着同等作用

2.2.2.1 垂直分布

物理逻辑一一对应

• 多层客户端 - 服务器架构 – 将应用程序划分为用户界面，处理层和数据层 – 各层直接与应用程序的各层逻辑程序相对应

• 特点 – 按逻辑把不同组件放在不同机器上 – 物理的分布体现了逻辑的结构

• 优势 – 功能在逻辑上和物理上分散在多台机器上 – 每台机器都根据特定的功能组进行定制

2.2.2.2 水平分布

在物理上分开，但在逻辑上具有相同功能的部分，计算的 内容也是存储在自己设备上的数据

结构化的点对点体系结构——Chord系统

• 目的 点对点的对等网络(P2P)快速定位资源

• 方式

  1. Napster 中心服务器接受请求查询，告知用户所需数据位于哪个节点

     存在的问题是中心服务器单点失 效导致整个网络瘫痪

  2. 消息洪泛 消息发到系统每一个节点 直到找到所需数据为止

  3. Chord系统 Chord算法解决网络内节点定位问题的一种P2P协议，通过多个节点跳转找到我们所查找的资源。

     • 元素

       • 节点NID 一个物理机器，m位的一个数字，节点机器的IP地址通过哈希操作得到
       • 资源KID 原为键ID，表示一个资源，key通过哈希操作得到
       • 常哈希函数 较之一般Hash，对系统影响较少
       • Chord环 NID和KID分配到一个2的m次方的环上，用于资源分配和节点分布，以及资源定位

     • 资源定位

       • 借助节点之间的跳转寻找资源

     • 资源分配

       • NID>KID

     • 资源查找

       • 查询函数 LOOKUP(KID)

         1. 要查找数据项时，运行在任意节点的应用程序可调用函数 Lookup(k)

         2. Lookup(k)返回succ（k）的网络地址

             3. 应用程序可以联系节点以获取数据项的副本
            

       • 加入新节点

         1. 生成随机标识符id – 查找id，并返回succ（id）

         2. 将自己插入环中 • 每个节点还存储有关其前驱的信息

         3. 其关键值k与节点id相关联的每个数据项从succ（id）传输

       • Leave删除节点

         1. 节点id通知它的前驱和后继将要离开

         2. 将其数据项传输到succ（id）的后继节点

第三章 进程和通信

3.1 进程

3.1.1 进程概念

• 执行中的程序，程序的实例，资源分配与独立运行的基本单元

3.1.2 进程构成

• 程序
• 数据
• PCB

3.1.3 进程优点

• 一个进程崩溃后，在保护模式下不会对其他进程产生影响

3.1.4 进程缺点

• 进程执行开销大，进程切换时，消耗的资源大，效率低

3.1.5 线程概念

• 进程 其他资源分配单位
• 线程 CPU调度单位
• 共享进程所拥有资源

3.1.6 线程目的

• 减少程序时空开销 提高并发性

3.1.7 线程实现

1. 用户级线程

• 库调度器从进程的多个线程中选择一个线程，然后该线程和该进程允许与一个内核线程相关联。

2. 内核级线程

• 每个用户线程都直接与一个内核线程相关联。

3. 组合方法

• 线程创建完全在用户空间完成，线程调度和同步在应用程序内进行

进程中的多个用户级线程被映射到一些（小于或等于用户级线程的数目）内核级线程上

每个内核级线程有一个可以轮流使用的用户级线程集合。

3.1.8 执行状态

• 就绪
• 阻塞
• 执行

3.1.9 线程优点

• 线程执行开销小，上下文切换时消耗资源小，效率高

3.1.10 线程缺点

• 对于单线程而言，线程崩溃整个进程都死掉，不利于资源的管理和保护

3.1.11 线程分类

1. 用户级线程 多对一关联

2. 内核级线程 一对一关联

3.1.12 二者区别

1. 地址空间

   • 同一进程的线程共享本进程的地址空间，进程内的线程在其他进程不可见
   • 进程之间则是独立的地址空间

2. 资源拥有

   • 统一进程内的线程共享本进程资源
   • 进程之间的资源是独立的

3. 通信

   • 线程间可以直接读写进程数据段来进行通信
   • 进程间通信通过IPC（Inter-Process Communication）

4. 调度

   • 线程时空开销小于进程 上下文切换快

3.1.13 虚拟化

3.1.13.1 作用

• 移植旧有软件的底层接口到新平台。
• 灵活性：通过让每个应用程序运行在自己的虚拟机上为用户提供服务，减少平台和机器的种类

3.1.13.2 体系结构

• 进程虚拟机
• 虚拟机监视器

3.1.14 线程使用

• 多线程客户-Web浏览器
• 多线程服务器
• 共两种方式进行使用

3.2 通信

3.2.1 通信定义

• 进程间通信是一切分布式系统的基础，它基于底层网络提供的底层消息传递机制。

3.2.2 分层协议

3.2.2.1 协议定义

• 协议就是通信各方就如何进行通信所需遵守的规则
• 一组计算机能够通过网络相互通信，它们必须使用相同的协议。

3.2.2.2 协议划分

• 面向连接协议：首先显式地确立连接（可能还需要就采用的协议进行协商），然后两者进行数据交换。
• 无连接协议：交换数据之前不需要有建立连接的过程，消息发送方只需要在准备好的时候开始传送第一个消息即可

3.2.2.3 OSI模型

该模型清楚地标明了通信涉及的各个层次，为这些层次给 出了标准名称，并且指出各层执行的特定任务。更加方便地对通信中涉及的多个不同层次进行处理，并解决其中存在的问题。
OSI模型允许开放系统间进行通信 所谓开放式系统是准备通过一系列标准规则来与其他开放式系统通信的系统，这些规则规定了发送和接收的消息的格式、内容以及相应的含义。
在OSI模型中，通信过程划分为7级，如图所示。每一层负责处理通信中某个特定方面的问题。这样就可以把要解决的问题划分成多个易于处理的部分，每个部分都可以相对独立地进行处理。每一层都规定了与上面一层之间的接口，接口中包含一组操作，这些操作共同定义了该层向其用户提供的服务。

在OSI模型中，当机器a上的进程A与机器b上的进程B通信时

进程A创建一条消息，将消息传送到本机的应用层。 
应用层在该报文前加上报头，通过第6、7层间的接口传给 表示层。 
表示层加上自己的报头，将结果传送给会话层... 
一些层中不仅要在报文前加报头，还要在报文后加上报尾。
当消息最终到达底层物理层时，由该层执行实际的消息传 输，即把消息放置到物理传输介质上去。
报文到达b机器时，它向上传递，每一层都剥掉并检查自己的报头，最后报文到达接收者--进程B。第n层的报头信息就用第n层协议。

1. 高层协议
   • 应用协议
   • 表示协议
   • 会话协议
2. 传输协议
   • 传输协议 TCP UDP
3. 低层协议
   • 网络协议
   • 数据链路协议
   • 物理协议

3.2.3 通信类型

3.2.3.1 持久通信

• 通信双方不必同时在运行
• 提交传输的消息一直由通信中间件存储，直到该消息被传送给接收方为止。在这种情况下，中间件将在一个或多个存储设备中存储该消息

3.2.3.2 瞬时通信

• 通信双方必须同时在运行
• •通信系统只有在发送和接收应用程序正在运行时才存储消息。通常，所有传输层通信服务都只提供瞬时通信。

3.2.3.3 异步通信

• 无需等待回复
• •发送方在提交要传输消息后立即往下进行。这意味着消息在提交后立即由中间件(临时)存储起来。

3.2.3.4 同步通信

• 必须等待回复
• 发送方发送消息之后将被阻塞，直到其请求被接受。

3.2.4 中间件通信服务

3.2.4.1 远程过程调用(RPC)

• 定义

  RPC是指远程过程调用，也就是说两台服务器A，B，一个应用部署在A服务器上，想要调用B服务器上应用提供的函数/方法，由于不在一个内存空间，不能直接调用，需要通过网络来表达调用的语义和传达调用的数据

• RPC步骤

  1. 客户进程以正常的方式调用客户stub
  2. 客户stub将参数打包生成一个消息，然后调用本地操作系统
  3. 客户端操作系统将消息发送给远程操作系统
  4. 远程操作系统将消息交给服务器stub
  5. 服务器stub将参数提取出来，然后调用服务器进程
  6. 服务器执行要求的操作，操作完成后将结果返回给服务器stub
  7. 服务器stub将结果打包成一个消息，然后调用本地操作系统
  8. 服务器操作系统将含有结果的消息发送回客户端操作系统
  9. 客户端操作系统将消息交给客户stub
  10. 客户stub将结果从消息中提取出来，返回给调用它的客户过程

• 传统RPC交互
  

• 异步RPC交互
  

  服务器在接到RPC请求后立即向客户送回已收到准备开始处理请求的消息，客户在收到确认消息后，将不会阻塞，而是继续执行

  在异步RPC中，服务器在接收到RPC请求后立即向客户送回应答，之后再调用客户请求的过程。应答的作用是想客户端确认服务器有已经准备开始处理该RPC请求。客户接收到服务器的确认消息之后，将不会阻塞，而是继续向下执行

• 延迟同步RPC
  
  ​ 单向RPC：客户不等待服务器收到确认消息就立即继续执行

3.2.4.2 远程对象调用

• 定义

  调用时先找到远程对象，再发起方法调用，不需要每次传输全部数据，对象中能够保存之前操作的结果

3.2.4.3 面向消息的通信

• 消息中的持久性和同步性

  • 持久异步通信：提交消息后立即往下执行

  • 持久同步通信：提交消息后会被阻塞，直到消息已到达并存储在接收主机 - 暂时异步通信

  • 基于接收的暂时同步通信
    

  • 基于交付的暂时通信

  • 基于响应的同步通信 - 面向消息的暂时通信

• 面向消息的持久通信

总：

• 持久通信：双方不用持续在运行
• 暂时通信：双方必须在运行中
• 异步通信：无需等待回应
• 同步通信：必须等待回应

第四章 命名系统

4.1 基础概念

4.1.1 名称定义

• 由位或字符组成的字符串，用来指向一个实体

4.1.2 名称作用

• 在所有计算机系统中有着重要作用：共享资源、唯一标识实体、指向位置等

4.1.3 地址

• 要对实体进行操作，就需要访问实体，因此需要一个访问点
• 访问点是另一种特殊的实体，它的名称称为地址，地址是一种特殊类型的名称

4.1.4 命名系统作用

• 将名称解析为它所指向的实体

4.1.5 访问点

访问点是另一种特殊的实体，它的名称称为地址，地址是一种特殊类型的名称

4.1.6 实体和访问点的关系

• 一个实体可以有多个访问点
• 一个实体经过一段时间后其访问点可能改变如位置改变
• 一个访问点可能也会重新分配给另外一个实体

4.1.7 标识符

标识符是具有以下属性的名称：

• 一个标识符最多引用一个实体

• 每个实体最多由一个标识符引用

• 一个标识符始终引用同一个实体（即标识符永远不会重新使用）

4.2 命名方式

4.2.1 非结构化命名

4.2.1.1 非结构化名称

• 随机的位字符串表示的标识符，不包含任何有关如何定位其相关实体的访问点的信息

4.2.1.2 定位访问点

广播

优点：简单 缺点：不能超出局域网要求所有的进程监听定位请求

多播

主机加入到特定的多播组（多播地址标示）后，多播组中的成员主机才会收到消息

转发指针

原理： 当实体从A移动到B时，将在A处留下一个指针，这个指针指向它 在B中的新位置。

优点： 简单

缺点：

• 如果不采取特殊措施，转发链会特别长，导致定位实体的开销大
• 链中的所有中间位置都必须维护它们的那一部分转发指针链
• 转发链脆弱，容易断开。

基于宿主位置的方法

• 注册宿主位置
• 注册实体所在的远程主机
• 宿主与实体所在的远程主机保持联系
• 客户首先与宿主建立连接，然后与远程主机连接

如果只给出实体的非结构化名称，以上方法均可通过其定位到访问点

4.2.2 结构化命名

4.2.2.1 结构化名称

• 结构化名称是由简单的、人类可阅读的名称组成，如文件命名

4.2.2.2 命名服务

• 名称空间是命名服务的核心
• 命名服务是一种允许用户和进程添加、删除和查找名称的服务
• 跨越地理区域的大型分布式系统中，命名服务由名称服务器实现

4.2.2.3 名称空间

• 名称空间是一个有向图，其中叶节点代表一个具体实体，目录节点是指向其他叶节点的实体。
• 叶节点

  • 叶结点通过名称存储各种属性，描述实体的各方面信息

    • 实体类型
    • 实体标识符
    • 实体的位置信息
    • 别名
• 目录节点
  • 目录结点除了存储目录表外还能存储其他属性，如子节点的位置信息（子目录位置信息）

4.2.2.4 名称空间的实现

• 名称空间是命名服务的核心
• 命名服务是一种允许用户和进程添加、删除和查找名称的服务
• 命名服务由名称服务器实现。如果一个分布式系统局限于局域网，那么可以只使用一台名称服务器来实现命名服务；在跨越地理区域的大型分布式系统中，需要多台名称服务器来分散名称空间的实现
• 通过将名称图结点分布存储实现分布式名称解析

4.2.2.5 名称空间的逻辑分层

1. 全局层

   组成 最高级别的结点组成 即由根结点以及其他逻辑上靠近根结点的目录结点，也就是根结点的子结点组成。

   特点 稳定 目录表很少改变 这样的结点 可以代表组织或组织群，这是因为它们的名称被存储在这个名称空间中

2. 行政层

   组成 由在单个组织内一起被管理的目录结点组成

   特点 相对稳定 代表属于同一组织或行政单位的实体组。

3. 管理层

   组成 由那些经常改变的结点组成

   特点 不稳定

   例如，代表本地网络主机的结点就属于这一层。同样，本层还包括那些代表共享文件(如库文件或二进制文件)的结点。另一类重要结点包括那些代表用户定义目录和文件的结点。

   与全局层和行政层相比，管理层的结点不仅要由系统管理员维护，而且还要由分布式系统的各个最终用户维护。

4.2.2.6 三层实现结点的名称服务器对比

4.2.2.7 名称解析

4.2.2.7.1 定义

• 查询名称的过程

4.2.2.7.2 终止机制

处理从名称空间中选择的初始结点

• www.baidu.com:从域名服务器开始
• /home/steen/mbox:从命名图的根结点的目录表开始
• 003102434：通过拨号

4.2.2.7.3 迭代名称解析

• 客户端解析程序将完整名称ftp://ftp.cs.vu.nl发给根服务器
• 根服务器解析标识符nl,返回名称服务器1 (存储nl)的地址
• 客户端解析程序发送解析<vu,cs,ftp>请求给名称服务器1
• 不断迭代解析

注：#指一台服务器的地址，该服务器负责处理涉及到的结点

第五章 同步化

5.1 时钟同步

5.1.1 一致的系统时间

• 分布式同步的基础，事件顺序关系问题的解决基础

5.1.2 两个层面的时钟同步

绝对同步（物理同步）——物理时钟

相对同步（逻辑同步）——逻辑时钟

5.1.3 物理时钟同步

5.1.3.1 物理时钟

• 计算机系统的绝对时间

5.1.3.2 UTC

• 一种国际统一的科学物理时间，称为统一协调时间 WWV接收器

5.1.3.3 时钟精确度

• 设UTC时间为t，机器的时间为C，则机器时钟的精确度可以用 一个常数ρ来表达：

• 1-ρ ≤ dC/dt ≤ 1+ρ

• 一般来说， ρ由生产厂商规定，称为最大偏移率

5.1.3.4 同步间隔

• 最坏的情况下，两个计算机的时钟以相反的方向偏离UTC时间， 如果△t之后同步时钟，要保证两个时钟误差不超过δ， 就必须至少δ/(2ρ)秒钟重新同步一次

5.1.3.5 Cristian时钟同步算法 （被动）

基本思想

1. 系统中有唯一一台时间服务器接收UTC时间，其他机器则必须与时间服务器同步
2. 每台机器以不大于δ/(2ρ)秒的周期定期向时间服务器发送消息询问当前时间
3. 时间服务器收到后发送消息告知当前时间C UTC
4. 发送者收到服务器消息后将时钟调整为C UTC

从服务器得到当前时间

5.1.4 逻辑时钟同步

5.1.4.1 概念

• 许多应用中，并不严格需要所有机器都与UTC时间保 持一致，而只需要所有机器时间相同就够了，即系统保持一个内部一致的时钟，这种时钟称为逻辑时钟 。
• 更进一步，很多问题中根本就不需要时间严格一致， 而只是需要多个事件的发生顺序一致就可以

5.1.4.2 Berkeley时钟同步算法 （主动）

适用于没有WWV接收器的系统，时间服 务器的程序时间由手工定期设置

• 时间守护程序主动定期询问每台机器的时间
• 时间守护程序基于客户的回答，计算一个平均值， 告知它们拨快或者拨慢

5.1.4.3 先发生关系

• 先发生关系a→b，事件a先发生，然后b才发生
• 如果a和b是同一个进程的两个事件，如果a在b之前发 生，则a→b为真
• 如果a是一个进程发送消息的事件，b是另一个进程的接 收消息事件，则a→b为真

5.1.4.4 并发事件

• 如果x和y事件发生在两个互不交换消息的进程中，x→y不 真，y→x也不真，这两个事件称为并发的

5.1.4.5 Lamport算法

• 直接遵循先发生关系
• 所有消息都必须携带发送者时钟的时间
• 当接受者发现自己时钟比发送者的时钟早时，接受者将它的时钟调到一个比发送时间大1的值
• Lamport时间戳提供了一种对系统中所有事件完全排序的方法

5.2 互斥

5.2.1 基本概念

• 分布式系统的基础是多进程之间并发和协作
• 不同进程将需要同时访问相同的资源
• 为了保证这种并发访问不会崩溃资源或使其不一致，需要保证进程的互斥访问
• 当一个进程使用某个共享资源，其他进程不允许对这个资源操作

5.2.2 相关问题

• 死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，进程间互相等待对方所占用的资源
• 活锁：进程没有被阻塞，由于某些条件没有满足，导致一直重复尝试—失败—尝试—失败的过程，活锁有可能自行解开
• 饥饿：是指一个可运行的进程尽管能继续执行，但被调度器无限期地忽视，而不能被调度执行的情况

5.2.3 互斥算法

5.2.3.1 集中式算法

过程

1. 选举一个协调者（一个进程）
2. 任何一个进程要访问共享资源，必须向协调者发送申请消息
3. 协调者根据申请资源的使用情况同意或者拒绝申请者的请求
4. 协调者拒绝申请者的方式可以发送拒绝消息或者不应答，但都将请求放入队列中

优点

• 保证了互斥的实现
• 公平——先来先服务
• 没有进程会处于永远等待状态，不会出现饿死
• 易于实现

缺点

• 协调者是一个单故障点，如果协调者崩溃，则整个系统瘫痪
• 协调者可能成为性能的瓶颈

5.2.3.2 分布式算法

过程

1. 当一个进程想访问一个共享资源时，它构造一个（含有访问的资源名、本进程号和当前时间）消息，发给所有进程
2. 一个进程收到另一个进程的请求消息时，根据自己与消息中的资源相关状态关系作出反应
   • 若接受者没有访问资源并也不想访问，发送OK消息
   • 接受者已获得对资源的访问则不应答，只是把请求放入队列
   • 接受者亦欲访问资源但尚未访问，则将收到的请求时间戳与它发送的请求时间戳比较，早的进程获胜
3. 发送者一直等待至其他所有进程返回OK消息，之后访问资源，使用完毕向队列中的进程发送OK消息，删除自己的任务

优点

• 实现了分布式互斥
• 不会发生死锁或饿死
• 不存在单个故障点

缺点

• 反而有n个故障点，实际上比集中式算法差了n倍
• 需要自己维护组成员清单，处理进入、离开组和崩溃进程的能力比较差
• 总之，实际上比集中式算法更慢，更复杂，花费更高，而且更脆弱

5.2.3.3令牌环算法

过程

1. 将进程构造一个逻辑环
2. 初始化时，进程0得到一个令牌，令牌绕环运行
3. 收到令牌的进程如果要访问共享资源，则访问完共享资源后再传递令牌
4. 进程释放资源后，不允许用同一个令牌立即再次访问资源

优点

• 不会发生饿死
• 进程崩溃比较容易处理，将崩溃进程移除环即可

缺点

• 令牌丢失的情况，检测令牌丢失非常困难

第六章 一致性和复制

6.1 一致性

6.1.1 目的

提高系统可靠性

• 多个数据副本，防止正确数据被破坏

提高系统性能

• 多个数据副本，访问数据时间减少，性能提高

• Web页面访问时间

6.1.2 概念

• 实质上是进程和数据存储之间的一个约定，进程只有遵守约定，数据存储才能正常运行

  基本原则

• 正常情况下，一个进程执行对某项数据的读操作时，应该返回该数据项最近一次写操作的结果

• 在没有全局时钟的情况下，精确定义哪次写操作是最后一次写操作相当困难

  基本目标

• 有效限制在一个数据项执行读操作所应该返回的值

6.1.3 数据存储的特点

• 不会出现同时发生的更新操作
• 或者发生同时更新时，可以容易解决
• 大部分操作是读操作
• 提供一种很弱的一致性模型，称为最终一致性模型

6.1.4四种模型

以客户为中心的一致性模型

• 有效解决最终一致性模型中客户对不同副本访问的问题

基本思想

• 为单一的客户提供一致性保证，保证该客户对数据存储的访问一种
• 不保证不同客户并发访问的一致性

6.1.4.1 单调读

• 保证进程不会读到比以前读的值更老的版本
• 如果一个进程读取数据项x的值，那么它对x执行的任何后续读操作总是得到第一次读取的值或者更新的值

6.1.4.2 单调写

• 一个进程对数据项x执行的写操作必须在它对x执行任何后续写操作之前完成
• 单调写操作规定：对x的副本执行写操作只有该副本已经完全通过了先前的所有写操作之后才能被进行，而这些先前执行的写操作可能发生在x的其他副本上

6.1.4.3 写后读

• 一个进程对数据项x的写操作的结果总是被它对x的后续读操作看见
• 写后读要求：当进程在某个副本上执行了写操作后，如果在其他副本上对该数据执行后续的读操作的话，必须先执行这个写操作更新，保证写的结果对后续读操作可见

6.1.4.4 读后写

• 进程对x的执行读操作之后的写操作，保证发生在与X读取值相同或更新的值
• 读后写一致性要求：如果后续的写操作需要x的值，它们（指这些后续写）得到的x的值必须与前面读操作的值相同或者更新

6.2 复制

• 一致性模型只从理论上解决一致性问题
• 从实现的角度研究数据更新发送给各个副本的方法，即分发协议

6.2.1 副本实际问题

• 位置
• 时间

6.2.2 副本类型

6.2.2.1 永久副本

• 永久副本是分布式数据存储的初始集合 数量一般比较少 静态配置

6.2.2.2 服务器启动的副本

目标

• 提高系统性能而由服务器动态创建的副本

原理

1. 由服务器根据系统运行情况动态创建、销毁副本
2. 例如对于突发的大流量web访问，就有可能需要创建这种副本

动态复制算法

​ 问题：何时、何地创建或删除副本

​ 原则：复制可能是为了减轻一台服务器的负载 一台服务器的某些文件可能被转移或复制到对这些文件访问频繁的客户附近的服务器

​ 过程：

• 每台服务器跟踪每个文件的访问计数以及这些访问客户的位置
• 对服务器S上的文件F的访问数下降到低于删除阈值del(S, F)时，S可以删除F。但必须保证系统中至少有一个F拷贝
• 反之，如果对F的请求高于复制阈值rep(S, F)时，则发生复制
• 如果访问数在二者之间，则允许F的转移，保持该文件的副本个数不变

6.2.2.3 客户启动的副本

定义

①实际上就是客户高速缓存

②客户使用高速缓存暂时存储刚请求过的数据的副本

高速缓存完全由客户管理，所以原则上服务器不负责缓存内容是否过时

高速缓存形式

①位于客户机本机

②位于局域网中一台特殊的服务器，使得不同的客户共享高速缓存

③部署在广域网中的几个特定的专门高速缓存服务器上

6.2.3 更新传播

为保证数据的一致性，数据的更新最终要被传播到其他副本上

6.2.3.1 更新传播的三种类型

• 只传播更新通知

• 数据从一个副本传送到另一个副本 （传播数据）

• 更新操作被传播到其他副本 （传播操作）

6.2.3.2 无效化协议（传播更新）

• 是一种典型的更新通知
• 通知其他副本已经发生了数据已更新，这些副本包含的指定数据项不再有效
• 适用于更新操作频率>>读操作频率 （只传播更新通知）

6.2.3.3 多个副本之间传送被修改的数据 （传播数据）

• 适用于更新操作频率<<读操作频率 （只对数据进行传播）

6.2.3.4 更新操作传播 （传播操作）

• 不传送任何数据修改信息，而是告诉其他副本它应该执行什么操作
• 也称为主动复制

6.2.3.5 更新传播两种方式（推，拉）

• “推”式的方法（基于服务器的协议或推协议）：更新由发生的原始点主动传播到其他副本上。应用于需要维持较高程度一致性的系统，永久副本和服务器启动的副本一般采用这种方式
• “拉”式的方法（基于客户的协议或拉协议）：客户或者非更新原始点副本请求其他服务器发送更新集合。适用于客户高速缓存

6.2.4 推拉协议区别优缺点适用范围

在分布式系统中，主副本与多个副本之间往往会涉及到数据更新的问题，此时便应该考虑是基于拉协议还是推协议来实现更新

定义

推：基于推式的方法又称基于客户的协议，一旦主副本的数据有更新，则它会自动向所有副本服务器推送此更新，以便使所有副本之间保持高效的一致性

拉：基于拉式的协议又称基于客户的协议，即有人来访问副本服务器推送此更新，以便使所有副本之间保持高效的一致性

优缺点及适用范围

推：高效的，因为每个被推的更新可以对一个或更多读程序有用，另外，基于推式的协议使一致的数据在被请求时立即有效，其更适用于读与更新比率较高的场景

拉：常用于高速缓存，当多用共享一个高速缓存，在被缓存数据项很少共享时，可证明其高效，主要缺点为高速缓存未命中时，响应时间会增大，适用于更新比率较低的场景

第七章 容错性

7.1 基本概念

7.1.1 容错

定义：意味着系统能在故障发生的情况下继续提供服务，容错与被称为可靠的系统紧密相关。

三种冗余方法：

✓ 信息冗余：添加额外的位以使错误的位恢复

✓ 时间冗余：多次重复一个操作，适合暂时性或间歇性故障

✓ 物理冗余：通过添加额外的装备或进程使系统作为一个整体，来容忍部分组件的失效或故障，可在硬件上或软件上进行

7.1.2 可靠

✓ 可用性：在任何时刻系统都能及时工作

✓ 可靠性：指系统可以无故障地持续运行

✓ 安全性：系统在偶然出现故障的情况下可以正确操作而不 会造成任何灾难

✓ 可维护性：系统发生故障后，恢复的难易程度

7.1.3 故障

造成错误的原因被称为故障

目的：对其他进程或客户隐藏故障（故障透明性）

手段：使用冗余掩盖故障

7.1.3.1 按时间持续度分类

• 暂时故障：只发生一次，然后就消失了，即使重复操作也 不会发生。
• 间歇故障：发生，然后消失不见，然后再次发生，如此反 复进行。
• 持久故障：直到故障组件被修复之前持续存在的故障。

7.1.3.2 按造成错误原因分类

• 崩溃性故障 服务器停机，但停机之前工作正常
• 遗漏性故障 接收遗漏 发送遗漏 服务器不能响应来到的请求 服务器不能接收消息 服务器不能发送消息
• 定时故障 服务器未能按时响应
• 响应故障 值故障 状态转换故障 服务器响应不正确 响应值不正确 服务器偏离了正确的控制流
• 随意性故障 服务器可能在随意的时间产生随意的响应

7.2 进程容错

• 问题：分布式系统中的容错主要是防止进程失败

• 方法：将进程复制到进程组

• 原理：所有组都具有的关键特性是当信息发送到组本身时，组中的所有成员都接受它。通过这种方式，如果组中的一个进程失败，其他的一些进程可以接管它。

• 目的：允许把进程组作为逻辑上单一的对象来处理，增加系统的容错性

7.2.1 进程组特性

• 组本身可以是动态的
• 组成员可以是动态的
• 一个进程可以从属于多个组

7.2.2 进程组类型

➢ 平等组

• 对应分布式概念
• 所有成员地位都是相同的
• 所有决定都是共同作出的

➢ 等级组

• 对应集中式概念
• 一般有一个协调者进程，其他则是工作者
• 组内关系和动作由协调者做决定

7.3 可靠的客户-服务器通信

分布式系统通信的可靠性设计的重点在于掩盖

• 崩溃性故障
• 遗漏性故障
• 定时故障
• 随意性故障

7.3.1 RPC通信故障及解决方式

7.3.1.1 客户不能定位服务器

解决方案： 由应用程序抛出异常来处理

缺点：不是每种语言都具有异常或者信号 破坏了客户-服务器通信的透明性

7.3.1.2 客户到服务器的请求消息丢失

解决方案： 超时重发机制

缺点：若消息频繁丢失，会使客户误认为服务器停机。 如果请求没有丢失，我们很难让服务器知道它处理的是重传消息。

7.3.1.3 服务器在收到请求之后崩溃

服务器接受请求之后崩溃有两种情况

1. 执行之后崩溃
2. 执行之前崩溃 但对客户来说，都是超时。

三种处理方式

• 至少一次语义：在服务器重启之前等待并再次尝试操作
• 最多一次语义：立即放弃并报告失败
• 什么都不保证，客户得不到任何帮助，RPC可能执行任意多次 无法做到恰好一次的语义。

无法做到恰好一次的语义

7.3.1.4 从服务器到客户的响应消息丢失

法1：依靠客户端的超时重发机制处理（适合幂等请求） 存在问题：不幂等的请求，如：银行转帐:

法2：为每个客户请求分配一个序列号，这样服务器就能分辨客户的新请求与重发的请求，当服务器收到重发的请求时，不执行重复操作。

7.3.1.5 客户在发送请求之后崩溃

孤儿：客户向服务器发送请求，在服务器回复之前，客户崩溃了，则计算将不被需要

引发问题：

• 首先，它的计算毫无意义，因为已经没人需要它的结果
• 孤儿浪费系统资源，包括计算、存储和其他资源
• 当客户恢复并重发请求时，孤儿返回的结果则会引起混淆

解决方法：

法1：消灭

1. 在RPC调用之前写日志
2. 客户在崩溃中恢复后根据日志杀死孤儿

缺点：

• 代价高，每个RPC都需要写日志
• 孤儿本身有可能进行RPC调用而产生后代，杀死孤儿后，其 后代成为更难跟踪处理的孤儿

法2：再生

1. 对时间分段并编号
2. 当客户重启时，向所有机器广播声明一个新时期开始
3. 其他机器收到该消息后，杀死所有与这个客户有关的远程计算

缺点：

• 对于广播不能到达的地方，孤儿还有可能存活

法3：到期

1. 每个RPC都被给定一个期限T来工作
2. 到期后如不能结束就需要申请宽期
3. 否则被认为抛弃子女，与其相关的远程计算将被当作孤儿杀死 难点：选择合理的T值

难点：

• 选择合理的T值

户-服务器通信

分布式系统通信的可靠性设计的重点在于掩盖

• 崩溃性故障
• 遗漏性故障
• 定时故障
• 随意性故障

7.3.1 RPC通信故障及解决方式

7.3.1.1 客户不能定位服务器

解决方案： 由应用程序抛出异常来处理

缺点：不是每种语言都具有异常或者信号 破坏了客户-服务器通信的透明性

7.3.1.2 客户到服务器的请求消息丢失

解决方案： 超时重发机制

缺点：若消息频繁丢失，会使客户误认为服务器停机。 如果请求没有丢失，我们很难让服务器知道它处理的是重传消息。

7.3.1.3 服务器在收到请求之后崩溃

服务器接受请求之后崩溃有两种情况

1. 执行之后崩溃
2. 执行之前崩溃 但对客户来说，都是超时。

三种处理方式

• 至少一次语义：在服务器重启之前等待并再次尝试操作
• 最多一次语义：立即放弃并报告失败
• 什么都不保证，客户得不到任何帮助，RPC可能执行任意多次 无法做到恰好一次的语义。

无法做到恰好一次的语义

7.3.1.4 从服务器到客户的响应消息丢失

法1：依靠客户端的超时重发机制处理（适合幂等请求） 存在问题：不幂等的请求，如：银行转帐:

法2：为每个客户请求分配一个序列号，这样服务器就能分辨客户的新请求与重发的请求，当服务器收到重发的请求时，不执行重复操作。

7.3.1.5 客户在发送请求之后崩溃

孤儿：客户向服务器发送请求，在服务器回复之前，客户崩溃了，则计算将不被需要

引发问题：

• 首先，它的计算毫无意义，因为已经没人需要它的结果
• 孤儿浪费系统资源，包括计算、存储和其他资源
• 当客户恢复并重发请求时，孤儿返回的结果则会引起混淆

解决方法：

法1：消灭

1. 在RPC调用之前写日志
2. 客户在崩溃中恢复后根据日志杀死孤儿

缺点：

• 代价高，每个RPC都需要写日志
• 孤儿本身有可能进行RPC调用而产生后代，杀死孤儿后，其 后代成为更难跟踪处理的孤儿

法2：再生

1. 对时间分段并编号
2. 当客户重启时，向所有机器广播声明一个新时期开始
3. 其他机器收到该消息后，杀死所有与这个客户有关的远程计算

缺点：

• 对于广播不能到达的地方，孤儿还有可能存活

法3：到期

1. 每个RPC都被给定一个期限T来工作
2. 到期后如不能结束就需要申请宽期
3. 否则被认为抛弃子女，与其相关的远程计算将被当作孤儿杀死 难点：选择合理的T值

难点：

• 选择合理的T值