NJU 2021fall 分布式系统复习总结

NJU 2021fall 分布式系统复习总结 分布式系统模型 什么是分布式系统，分布式系统的目标？

分布式系统是若干独立计算机的集合，它们对于用户来说就像单个相关系统。

A distributed system is many cooperating computers that appear to users as a single service.

分布式系统的目标有四个：资源可访问、透明性、开放性、可扩展性。

为什么要分布式？

1. 经济性：多个微处理器能提供比大型机更好的性能
2. 速度：分布式系统拥有更强的计算能力
3. 固有的分布性：有一些应用涉及到空间上分离的机器
4. 可靠性：当某台机器崩溃时，系统仍能正常工作
5. 可扩展性：计算能力可以以很小的增量增加

分布式系统透明性和开放性的含义

分布式系统的透明性包含七个：

1. 重定位透明性：隐藏资源可能在使用中被移动到另一个位置。
2. 复制透明性：隐藏资源是否已被复制。
3. 并发透明性：隐藏资源是否由若干相互竞争的用户共享。
4. 故障透明性：隐藏资源的故障和恢复。
5. 迁移透明性：隐藏资源可能被移动到另一个位置。
6. 访问透明性：隐藏数据表示形式以及访问方式的不同。
7. 位置透明性：隐藏数据所在位置。

口诀：重复病故，迁移，访问位置

注意：重定位透明性和迁移透明性的区别，in use。

分布式系统的开放性有两条内容：

1. 能够与来自其他开放系统的服务交互，而不用考虑底层环境

   • 系统应该遵循定义良好的接口

   • 系统应该支持应用程序的可移植性

   • 系统应该易于互 *** 作

2. 至少要使分布式系统独立于底层环境的异构性

分布式 *** 作系统、网络 *** 作系统和基于中间件的系统

• 分布式 *** 作系统

  分布式 *** 作系统具有较好的透明性和易用性，但没有对相互独立的计算机集合的 *** 作处理能力。

• 网络 *** 作系统

  网络 *** 作系统有良好的可扩展性和开放性，但对透明性和易用性比较差。

• 基于中间件的系统。

  在网络 *** 作系统之上增加一个中间层，屏蔽各底层平台之间的异构性，从而增加分 布式系统的透明性

以上内容完全照搬学长总结的复习资料，但我并未在第一章的ppt中找到这部分内容。同时我对中间件和分布式 *** 作系统是否应该用’和’这个连接词连接表示疑惑。因为网上说“中间件，英文名称为Middleware，是一种应用于分布式系统的基础软件”。那么，基于中间件的系统是否属于分布式 *** 作系统，换言之，是不是网络OS+中间价 == 分布式 *** 作系统？

最后一节课录播提到：分布式是基于本地 *** 作系统的，这个本地 *** 作系统又被称为网络 *** 作系统，它提供了一个网络传输的能力，但是只是一个能力而已，我们只知道这个 *** 作系统互相之间的通信。通信只是一个最基本的，在这个之上构建成为这样一个平台，这个平台虽然包括很多系统，但是看上去就像是一个。这是从不同的侧面去看的，例如，我们要用spark、Hadoop等大数据处理系统，我们看到的是一个平台，至于这个平台包含了多少构件，我们是不关心的。但如果从另一各侧面去看，不从Hapoop之类的平台进入，而是从其他的入口去实际登录这个系统，还是能看到这个系统到底有多少个硬件系统，所以说分布式系统并不是完全屏蔽底层。如果完全屏蔽底层的话，我们称之为分布式 *** 作系统，各个节点的自治能力不是很强，而是构成一个完整的体系。

分布式系统的类型

1. 分布式计算系统
   • 集群计算
     • 通过局域网连接
     • 单个节点管理
     • 同质性：节点具有相同的 *** 作系统，相近的硬件
   • 网格计算
     • 节点分散
     • 异质性
     • 可以轻松跨越广域网
2. 分布式信息系统
3. 分布式普适系统

分布式系统架构 分布式系统架构风格

第一类：组织成逻辑上不同的组件，并将这些组件分布在各种计算机上。

1. 分层体系结构(layered architectures)。

   在该风格中，组件被组织成若干个层次。第N层的组件向下请求服务，向上提供服务。

   这种风格广泛应用于互联网中。 （看起来类似于网络模型）

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iC2SzqMH-1640522046203)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226152128347.png)]

2. 基于对象的体系结构(object based architectures)。

   一个对象通过远程方法调用请求另一个对象的服务。

   对象之间没有明显地层次关系和层次约束。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qsli64vK-1640522046206)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226152146325.png)]

第二类：空间（“匿名”）和时间（“异步”）中的解耦过程导致了替代样式。（没看懂）
原话是Decoupling processes in space (“anonymous”) and also time (“asynchronous”) has led to alternative styles.

1. 以数据为中心的体系结构(data-centered architectures)。

   在这种风格中，存在一个共用的数据仓库（基于文件系统的或者基于数据库的）， 组件主要通过这个数据仓库进行通讯、协作（如通过读写文件、文件锁或者读写数据库表）。很多基于 web 的系统都采用了这种方式。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gyxcxz1L-1640522046207)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226152730509.png)]

2. 基于事件的体系结构(event-based architectures)。

   在这种风格中，组件主要是事件驱动的，组件间的通讯主要通过事件的传播进行（事件中可能携带某些数据）。在这种风格中，通常伴随着事件的 publish/subscribe 系统，使得某个组件可以发布（广播）事件，而这个事件会被自动传播到订阅了它的那些组件那里。基于事件的体系结构常常和以数据为中心的体系结构配合使用。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pbNlhgsV-1640522046209)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226152740821.png)]

分布式系统组织形式

• 集中式

  Basic C/S Model

• 非集中式

  不再存在某类中央节点，每个节点的功能都是类似的或者说对称的。

  P2P

• 混合式

  P2P可以和一些集中式的特点相结合

客户-服务器模式（C/S）和对等模式（P2P） C/S模式的特点

1. 客户端遵循请求/回复模型来使用服务
2. 客户端和服务器可以在不同的机器上
3. 有进程提供服务（服务器）
4. 有进程使用服务（客户端）

P2P

点对点网络，用户既是客户端又是服务器。

1. 结构化P2P：节点按照特定的分布式数据结构被组织起来

2. 非结构化P2P：节点随意选择邻居，两个节点之间以概率p的可能性建立连接

3. 混合P2P

   • 网络中的节点被分为普通节点和超级节点，超级节点拥有特殊的功能，这些特殊功能可能包括：

     • 维护索引（用于搜索）
     • 监视网络状态
     • 能够设置连接

   • 在一篇blog上看到说比特币使用的是这种结构 链接

BitTorrent：一旦节点确定了从哪里下载文件，它就会加入一群下载者，这些下载者并行地从源获取文件块，但也将这些块分发到彼此之间。

分布式系统组织为中间件

屏蔽底层若干机器 提供一个对外部统一的接口。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lHvbkTFM-1640522046210)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226153050769.png)]

进程 进程和线程

分布式系统 *** 作单位 ：进程

*** 作系统单位：线程，是轻量级的进程 Thread: “Lightweight process” (LWP)

• An execution stream that shares an address space
• Multiple threads within a single process

Example:

• Two processes examining memory address 0xffe84264 see different values (I.e., different contents)

• Two threads examining memory address 0xffe84264 see same value (I.e., same contents)

代码迁移 代码迁移方法 迁移内容

1. 代码段
2. 数据段
3. 执行状态

强迁移 vs. 弱迁移

• 弱迁移只迁移代码段和数据段（代码会被重新运行）
  • 相对简单，特别是如果代码是可移植的
  • 区分代码传送（推送）和代码提取（拉取）
• 强迁移移动组件，包括执行状态
  • 迁移：将整个对象从一台计算机移动到另一台计算机
  • 克隆：启动克隆，并将其设置为相同的执行状态

迁移本地资源

一个正在使用本地资源的对象不一定能被迁移。

资源的类型

• 固定资源：资源不能迁移，如本地硬件
• 绑定资源：资源原则上可以迁移，但成本很高
• 独立资源：资源可以轻松地随对象一起移动，例如cache

对象到资源的绑定

• 通过标识符：对象需要资源的特定实例（例如特定数据库）
• 按值：对象需要资源的值（例如，缓存实体集合）
• 按类型：对象要求只有一种类型的资源可用（例如，颜色监视器）

在异构系统中的迁移

主要问题：

• 目标计算机可能不适合执行迁移的代码
• 进程/线程/处理器上下文的定义高度依赖于本地硬件， *** 作系统和运行时系统

解决方法：

利用在不同平台上实现的抽象机

• 解释语言，有效地拥有自己的 VM
• 虚拟机 （个人观点：docker以及很发达了，虚拟机也不是广泛使用的技术了）

虚拟机迁徙最成熟 容器迁徙没那么成熟

通信 通信的类型 同步与异步

同步通信：发信方在到达同步点前保持阻塞

异步通信：发信方发信后立即继续，消息存储在发信方主机或者通信服务器的缓冲区中

一次消息发送的过程中，可能存在若干同步点 ：

• 消息提交：消息的发送者会阻塞，直到消息被成功提交给传输服务
• 消息交付：消息的发送者会阻塞，直到消息被接收者成功接收
• 消息请求结束：消息的发送者会阻塞，直到消息的接收者接收、处理消息、并且处理的结果返回到发送者

持久性和非持久性

• 持久通信

  通信机制本身会对消息进行持久存储，直到它被传递给目的。

  消息的发送者和接收这不必同时存在（同时处于执行状态）。

  例如：电子邮件。

• 非持久（瞬时）通信

  消息的发送者和接收者必须同时存在才能进行，传输服务仅仅提供临时的对消息的存储。

  一旦发送者退出或者接收者退出，传输就会失败。

  例如：电话。

远程过程调用RPC （重点）

由于不同的进程在系统中不同的位置，所以需要RPC。

RPC的工作过程，8步。

重点考虑：在分布式系统中不可靠，应该怎么办？

故障处理

1. 客户无法定位服务器：抛出异常

2. 客户发给服务器的请求消息丢失：设置一个计时器,超时重发;

3. 服务器发给客户的应答消息丢失：

   • （TCP）请求应答，如果未收到，则重新发送应答消息。但是如果等待时间太长导致TCP连接失效了呢？

   • 在不增加请求序列号的情况下重新传输请求

   • 要求服务器在某个设定的时间段内保留旧答复

4. 服务器在发送回复之前崩溃

   • RPC 重新发送请求（至少一次）
   • 放弃并报告失败（至多一次）或者服务器将所有回复保存在持久存储上，并重新发送以前的回复
   • 客户端得不到帮助，semantics由客户端决定

动态绑定 动态绑定解决了什么问题？

客户端如何知道向谁提出请求，以及服务器的地址？

动态绑定的工作流程

当客户端第一次调用一个远程过程时:

1. 客户机stub看到它还没有绑定到某个服务器，因此它向binder发送一条消息，请求导入服务器接口的版本x
2. binder检查是否有服务器是否已经导出了具有此名称和版本号的接口。
   • 如果当前运行的服务器不愿意支持该接口，则调用失败
   • 如果存在合适的服务器，binder将handle和unique id提供给客户机stub
3. 客户端stub使用结果作为发送请求的地址。该消息包含参数和唯一标识符，服务器的内核使用这些标识符将传入消息定向到正确的服务器。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SbafNgwm-1640522046212)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226181812783.png)]

优点和缺点

优点

1. 灵活性

2. 可支持提供同一接口的多台服务器，例如：

   • Binder 可以将客户端随机分布在服务器上以均匀加载

   • Binder 可以定期轮询服务器，自动取消注册失败的服务器，以达到一定的容错能力

   • Binder 可以辅助认证：比如一个服务器指定一个可以使用它的用户列表； Binder将拒绝告诉不在列表中的用户有关服务器的信息

3. 绑定程序(binder)可以验证客户端和服务器都使用相同版本的接口

缺点

1. 导出/导入接口的额外开销花费时间
2. 绑定程序(binder)可能成为大型分布式系统中的瓶颈

基于消息的通信

• 持久性/非持久性

• 同步/异步

• 流数据（热点，腾讯会议）：一组消息按照指定的顺序排序后构成一个有意义的数据流

同步与资源管理

同步问题

在分布式系统中，临界区、互斥和其它同步问题无法通过信号量等方法解决，因为很难确定两个事件哪个先发生。

时钟同步机制：逻辑时钟

物理时钟同步虽然是可能的，但是不是必要的。重要的是进程在时间的发生顺序上保持一致。

Lamport算法

定义一个偏序关系：“先于”，用符号“->”表示。该关系满足以下性质：

1. 如果 a 和 b 是进程 Pi 中的两个事件，并且在 Pi 中，a 在 b 之前发生，那么 Ci(a) <- Ci(b)
2. 如果 a 是 Pi 发送消息 m，b 是 Pj 接收消息 m，那么 Ci(a) <- Cj(b)

每个进程 Pi 维护本地计数器 Ci，并根据以下规则调整此计数器：

1. 对于 Pi 内发生的任何两个连续事件，Ci 增加 1
2. 每当进程 Pi 发送消息 m 时，消息时间戳 ts(m) = Ci
3. 每当进程 Pj 接收到消息 m 时，Pj 将其本地计数器 Cj 调整为 max {Cj，ts(m)} + 1

性质 1 由步骤 1 保证；性质 2 由步骤 2、3 保证

附加条件：两个事件允许同时发生，但不允许精确地同时发生。将进程的 ID 附在时间的小数部分

向量时戳

Lamport 时间戳无法捕获因果关系

• 事件 a 发生先于事件 b，则 C(a) < C(b)
• C(a) < C(b)不能说明事件 a 发生先于事件 b（只是被如此设定时间戳而已）

因果关系可以通过向量时间戳捕获

每个进程 P 维护一个向量 V，满足以下性质 ：

1. Vi[i]是目前为止进程 Pi 发生的事件数量
2. Vi[j]=k 表示 Pi 知道 Pj 中发生了 k 个事件

性质 1 通过 Pi 中新事件发生的时候递增 Vi[i]维护；性质 2 通过发送消息携带自身向量维护。具体如下：

1. 当 Pi 发送消息 m 时，Pi 令 Vi[i]增加 1，并将 Vi 作为向量时间戳 vt(m)发出与消息 m 一同发出。vt(m)告诉接收者多少事件在之前发生，并且 m 可能和在因果关系上依赖于这些事件。
2. 当 Pj 接收到从 Pi 发送的向量时间戳 vt(m)时

• 将每个 Vj[k]更新为 max {Vj[k]，vt(m)[k]}

  反映了 Pj 必须接收的消息数，该消息数目至少是发送 m 之前见到的消息

• 将 Vj[i]增加 1

  表示接收消息 m 这个事件来自于 Pi 的下一个事件

分布式系统中的互斥访问 集中式算法

基于上述的选举算法,选出一个进程作为集中协调者，该协调者同时管理一个请求等待队列。 当队列为空时，协调者对临界区请求应答。当队列不为空或者临界区尚未释放时，把请求添加到等待队列的队尾，然后或者对请求不予应答，或者直接拒绝(此时该请求会一直查询临界区使用状态) ，直至从队头取出该请求后再允许其进入临界区。

令牌环算法

用软件的方法,按照进程的地址或者编号等,为总线型的网络构造一个逻辑环。 一个令牌只能对应进入一个临界区。

令牌绕进程环依次传递，如果接受进程不需要进入临界区，则继续传递给下一个进程，如果接受进程需要进入临界区，那么此时传递暂停，令牌等待，直到进程从临界区返回后继续。

缺点：

1. 因为无法确定时间间隔，令牌丢失的检测和再生非常困难。
2. 进程崩溃虽然可以恢复，但是需要通过每个进程向前继进程发送确认消息来实现,也就需要每个进程都维护当前的配置信息。

分布式算法

根据 Lamport 算法给出时间戳确定事件发生的先后关系。每个进程都需要配置一个请求等待队列。

想进入临界区的进程用临界区名、自己的进程号和时间戳构造消息，发送给所有进程。

接收到消息的进程有以下几种可能：

1. 不在临界区时，也不需要使用临界区时，返回 OK 消息。
2. 在临界区时，不做应答，仅把收到的请求放入队列
3. 不在临界区但是已经请求使用临界区时, 把收到的请求和自己发送出去的请求比较时间戳。
   • 早者胜出,使用临界区，并把晚者的请求放入队列
   • 晚者向早者发送 OK 消息。

进程出临界区时，向队列中所有进程发送 OK 消息，并清空队列，继续通过比较时间戳竞争临界区。也就是说，在等待的进程请求，一定要放入正在临界区的进程的等待队列中去。

缺点: 故障可能性比集中式扩大 N 倍, 因此考虑不论同意还是拒绝请求一律发送应答 (应答内容不一样)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-unCcCpHx-1640522046213)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226192611996.png)]

分布式系统中的选举机制 Bully 算法

发起选举的条件：

1. 任何进程发现原有协调者崩溃时,可以发起选举。
2. 原来崩溃的进程 P 恢复以后,可以重新发起选举,但是最后不一定会赢得选举, 因为可能还有编号比 P 大的进程在 P 崩溃期间已经开始运行。

进程 P 按以下过程主持一次选举 ：

1. P 向所有编号比它大的进程发送一个 ELECTION 消息
2. 如果无人应答，P 获胜成为协调者，向所有运行着的进程发送一个 COORDINATOR 消息
3. 如果有编号比 P 大的进程响应，则响应者接管选举工作。P 的工作完成。

环算法

所有进程已经按照编号进行排序并且链接成环，每个进程知道自己的后继进程。

发起选举的条件：任何一个或者多个进程发现原有协调者崩溃或者没有响应时，开始发起选举。

选举过程：

1. 发起者构造 ELECTION 消息发送给自己的后继,依次绕环传递。
   • 如果后继进程已经崩溃,则绕过。
   • 如果后继进程正在运行,则后继进程把编号添加进 ELECTION 消息中 。
2. 待绕环一周返回到发起者后，根据选举消息中的编号选出协调者，并用 COORDINATOR 消息绕环通知所有进程，循环一周后该消息被删除。

复制与一致性 复制的优势与不足

优势：

• 增强系统的可靠性

  允许单个节点出错

• 提升性能

  对服务器数量和地理区域上进行扩展

不足：

• 复制透明性下降
• 一致性问题
  • 更新过程开销大
  • 不小心可能影响系统可用性

数据一致性模型 以数据为中心的一致性模型 不引入同步 *** 作的一致性模型

1. 严格一致性 Strict

   对于数据项 x 的任何读写 *** 作将返回最近一次对 x 进行写 *** 作的结果所对应的值。

   隐含的假设存在绝对的全局时间。

2. 线性化一致性 Linearizability

   假设 *** 作具有一个全局有效时钟的时间戳，但是这个时钟仅具有有限的精确度。

   全局时间戳不一定是唯一的。

3. 顺序一致性 Sequential

   任何执行结果都是相同的，就好像所有进程对数据存储的读写 *** 作是按某种顺序执行的，并且每个进程的 *** 作按照程序锁制定的顺序出现在这个序列中。

   访问不一定是按照时间排序。

4. 因果一致性 Causal

   所有进程必须以相同的顺序看到具有潜在因果关系的写 *** 作。不同机器上的进程可以以不同的顺序被看到并发的写 *** 作。

   没有因果关系的 *** 作被看作并发。

5. 管道一致性 FIFO

   所有进程以某个单一进程提出些 *** 作的顺序看到这些写 *** 作，但是不同进程 可以以不同的顺序看到不同进程提出写 *** 作。

   放弃因果一致性中对“所有机器必须以相同的顺序看到因果相关的写 *** 作”的要求。

   本质：同一进程执行的写 *** 作必须在任何地方以正确的顺序执行。

引入同步 *** 作的一致性模型

1. 弱一致性 Weak

   完成一次同步后，共享数据一致。

   具体限制为：

   • 对数据存储所关联的同步变量的访问是顺序一致的。说明了所有进程都以相同的顺序看到对同步变量进行的所有 *** 作
   • 每个拷贝完成所有先前执行的写 *** 作之前，不允许对同步变量进行任何 *** 作。说明了同步“清空管道”
   • 所有先前对同步变量执行的 *** 作都执行完毕之前，不允许对数据项进行任何读或写 *** 作。说明访问数据项时，无论读数据或写数据，所有先前的同步都已经完成。

2. 释放一致性 Release

   离开一个临界区时，共享数据一致。

   获取 *** 作：用于通知数据存储进程进入临界区的 *** 作。

   释放 *** 作：表明进程刚刚离开临界区的 *** 作

   具体限制为：

   • 对共享数据执行读 *** 作或写 *** 作之前，所有进程先前执行的获取 *** 作都必须已经成功完成
   • 在释放 *** 作被允许执行前，所有进程先前执行的读 *** 作和写 *** 作都必须已经完成
   • 对同步变量的访问是 FIFO 一致的（不需要顺序一致）

3. 入口一致性 Entry

   进入共享数据对应临界区时，共享数据一致。

   要求每个普通的共享数据项都要与某种同步变量关联。

   具体限制为：

   • 在一个进程可以获取一个同步变量之前，所有的由此同步变量保护的共享数据的更新都必须已经相对于该进程执行完毕。

     执行获取 *** 作时，所有的受保护数据的远程改变都必须已经可见。

   • 在一个进程对一个同步变量的独占访问被允许执行之前，其他的进程不可以拥有这个同步变量，甚至也不能以非独占的方式拥有这个同步变量。

     更新共享数据项之前，必须以独占的方式进入临界区。

   • 一个进程对一个同步变量执行独占访问之后，在对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个非独占访问。

     非独占方式进入临界区之前，必须检查保护这个临界区同步变量的所有者，以获得受保护的共享数据的最新副本。

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

最终一致性：如果在一段相当长的时间内没有更新 *** 作,那么所有的副本将逐渐成为一致的。

1. 单调读

   如果一个进程数据项 x 的值，那么该进程对 x 执行的任何后续读 *** 作将总是得到第一次读取的那个值或更新的值。保证之后不会看到 x 的更老版本。

2. 单调写

   一个进程对数据项 x 执行的写 *** 作必须在该进程对 x 执行任何后续写 *** 作之前完成。写 *** 作必须顺序完成，不能交叉。

3. 写后读

   一个进程对数据项 x 执行一次写 *** 作的结果总是会被该进程对 x 执行的后续读 *** 作看见。保证读取总是最新的。

4. 读后写

   同一个进程对数据项 x 执行的读 *** 作之后的写 *** 作，摆正发生在于 x 读取值相同 或比之更新的值上。更新是作为前一个读 *** 作的结果传播的。

数据一致性协议实例

方法论 指导我们怎么去设计怎么去做 并不是具体实现。

基于主备份的协议 Primary Backup protocols

每个数据项 x 仅有一个关联的主备份用来 *** 作，负责协调 x 上的写 *** 作。这个关联的主备份可以固定在一个远程服务器上，或者移动给启动写 *** 作的进程。

Remote-Write protocols 远程写协议 ：

所有读 *** 作和写 *** 作都在单一的远程服务器上执行的,数据没有被复制,而且不能移动。

Local-Write protocols 本地写协议 ：

每个数据项 x 都只有一个单一的拷贝，不存在副本。当某一进程要执行 *** 作时，将数据项的单一拷贝传送到该进程。

复制的写协议 Replicated Write protocols

写 *** 作可以在多个副本上执行。

Active replication 主动复制

*** 作被发送到每个副本。

需要使用多播机制保证 *** 作在各地以相同的顺序执行。

复制的调用问题指的是所有的副本看到相同的调用。

解决的方法是由复制对象中的一个来负责转发或者应答请求。

基于法定数量(多数表决)的协议 （重点）

(Gifford 的方法)

对于一个具有 N 个副本的文件

客户要读取时，必须组织一个服务器数量为 Nr 的读团体(read quorum) 。读之前请求读团体返回该文件关联的版本号，相同即为最新版本

客户要修改时，必须组织一个服务器数量为 Nw 的写团体(write quorum) 。修改前向写团体请求，同意则修改该文件，且与一个新的版本号关联。

其中，Nr 与 Nw 满足以下限制条件：

1. Nr+Nw>N

   用于防止读写冲突

2. Nw>N/2

   用于防止读读冲突

容错 可信系统(Dependable System)特征

1. 可用性 Availability

   在任何给定的时刻，系统都可以正确及时地工作，并执行用户的请求。

2. 可靠性 Reliability

   系统可以无故障持续运行，但是只能根据时间间隔来定义。

   高可靠性的系统可以在一个相对较长的时间内持续工作而不被中断。

3. 安全性 Safety

   系统偶然出现故障时还能正确 *** 作和运行。

4. 可维护性 Maintainability

   表示发生故障后系统能被恢复到可用性的难易程度。

提高系统可信性的途径：冗余

使用冗余来掩盖故障：对其他进程隐藏故障的发生

信息冗余：添加额外的位可以使错乱的位恢复正常。例如，添加一段汉明码从噪声中恢复数据。

时间冗余：执行一个动作，如果需要就在此执行。适用于临时性和间歇性的错误。可以使用事务。

物理冗余：添加额外的装备（硬件）或者进程（软件）使系统整体容忍部分错误。

K容错系统

K 容错：系统能够经受 k 个组件的故障并且还能满足规范要求。

K 容错需要的冗余数：

• 失败沉默 Fail-silent faults：K+1
• 拜占庭失败 Byzantine faults ：2K+1

拜占庭问题( Byzantine Problem)

拜占庭问题是信道可信的

算法步骤：

1. 每个将军向其他 n-1 个将军告知自己的兵力（真实或说谎）
2. 每个将军将收到的消息组成一个长度为 n 的向量
3. 每个将军将自己的向量发送给其他 n-1 个将军
4. 每个将军检查每个接收到的向量中的第 i 个元素，将其众数作为其结果向量的第 i 个元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9VgLopZ1-1640522046215)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20211226200250918.png)]

系统恢复 回退恢复

通过定时设置检查点，将系统从错误的状态回到先前被记录的正确状态。例如，分组重发。

前向恢复

系统进入错误状态时，尝试从可以继续执行的某点开始把系统带入一个正确的新状态。必须预先知道会发生什么错误

检查点 (Check point)

独立的检查点  每个进程的检查点是以不协调的方式按时记录  可能导致多米诺效应

一致的全局状态  发送方不能回滚到发送前的状态  接收方可以回滚到接收前的状态

协调的检查点  所有进程同步地把各自状态写到本地稳定存储中
时性和间歇性的错误。可以使用事务。

物理冗余：添加额外的装备（硬件）或者进程（软件）使系统整体容忍部分错误。

K容错系统

K 容错：系统能够经受 k 个组件的故障并且还能满足规范要求。

K 容错需要的冗余数：

• 失败沉默 Fail-silent faults：K+1
• 拜占庭失败 Byzantine faults ：2K+1

拜占庭问题( Byzantine Problem)

拜占庭问题是信道可信的

算法步骤：

1. 每个将军向其他 n-1 个将军告知自己的兵力（真实或说谎）
2. 每个将军将收到的消息组成一个长度为 n 的向量
3. 每个将军将自己的向量发送给其他 n-1 个将军
4. 每个将军检查每个接收到的向量中的第 i 个元素，将其众数作为其结果向量的第 i 个元素

[外链图片转存中…(img-9VgLopZ1-1640522046215)]

系统恢复 回退恢复

通过定时设置检查点，将系统从错误的状态回到先前被记录的正确状态。例如，分组重发。

前向恢复

系统进入错误状态时，尝试从可以继续执行的某点开始把系统带入一个正确的新状态。必须预先知道会发生什么错误

检查点 (Check point)

独立的检查点  每个进程的检查点是以不协调的方式按时记录  可能导致多米诺效应

一致的全局状态  发送方不能回滚到发送前的状态  接收方可以回滚到接收前的状态

协调的检查点  所有进程同步地把各自状态写到本地稳定存储中