分布式系统的特征以及系统模型

什么是分布式系统

分布式系统是若干独立计算机的集合，在用户看来是一个单一相关系统。

例如:分配给用户的工作站网络、机房中动态分配的处理器池、单个文件系统等。

分布式系统涉及到网络、处理器、内存、存储、协议等。

分布式系统的目标

  • 使资源可访问
  • 透明性
  • 开放性
  • 可扩展性

为什么要分布式

  • 经济：相比于大型机，微型处理器的性价比更高
  • 速度：分布式系统比大型机计算能力更强
  • 内在分布：一些应用需要在不同空间的机器上运行
  • 可靠性：当某一台机器挂掉时，分布式系统仍能运行
  • 可增加：通过增加分布式系统的组件使其计算能力增强

使资源可访问

分布式系统的最主要目标是使用户能够方便地访问远程资源，并且以一种受控方式与其他用户共享这些资源。

透明性

对用户和应用程序员屏蔽分布式系统组件和分散性，系统被认为是一个整体，而不是独立的组件集合。透明性对用户和应用程序员隐藏了与手头任务无直接关系的资源，并匿名使用，使得分布的某些特性对应用程序员具有不可见性，这样应用程序员只要关心特定应用的设计问题。

开放性

能与其他开放的系统进行交互，不考虑底层环境，要求系统：

  1. 良好说明的接口
  2. 支持程序的可移植性
  3. 系统容易交互

可拓展性

三个方面：

  1. 规模上可扩展（用户和处理器数目）
  2. 地域上可扩展（节点最大距离）
  3. 管理上可扩展（管理域数）

分布式系统的类型

  • 分布式计算系统：
    • 集群计算：本质是通过高速局域网连接的一组高端系统，每个节点运行相同的操作系统，硬件几乎相同，只有一个管理节点，同构性
    • 网格计算：异构性，硬件、操作系统、网络、管理域都不尽相同，可以跨广域网
  • 分布式信息系统：
    • 事务处理系统：有ACID四种特性，主要应用于数据库，邮件系统，财务系统等
      • 原子性：对于外部来说，事务处理不可见
      • 一致性：事务处理不会违反系统的不变性
      • 独立性：并发的事务不会相互干扰
      • 持久性：事务处理一旦提交，所发生改变是永久性的
  • 分布式普适系统：新兴的下一代分布式系统，其中节点小，移动，并且经常嵌入在更大的系统中，其特
    征在于系统自然地混合到用户环境中；

如何理解机制与策略

在开放的分布式系统中要获得灵活性，就要把系统组织成规模相对较小且容易修改和替换的组件，需要将策略和机制分离。

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

  • 分布式操作系统：配置在分布式系统上的操作系统，能够直接对分布式系统中的各种资源进行动态分
    配，并能有效地控制和协调分布式系统中各任务的并行执行，同时还向用户提供了一个方便的、透明的
    使用整个分布式系统的界面。
  • 网络操作系统：是在网络环境下实现对网络资源的管理和控制的操作系统，是用户与网络资源之间的接
    口。网络操作系统是建立在独立的操作系统之上，为网络用户提供使用网络系统资源的桥梁。在多个用
    户争用系统资源时，网络操作系统进行资源调剂管理，它依靠各个独立的计算机操作系统对所属资源进
    行管理，协调和管理网络用户进程或程序与联机操作系统进行交互。
  • 基于中间件的系统：在网络操作系统之上增加一个中间层，屏蔽各底层平台之间的异构性，从而增加分
    布式系统的透明性

分布式系统架构

分布式系统架构的风格

  1. 组织成逻辑上不同的组件，并且将这些组件分布在不同的机器上

    1. 分层体系结构（client-server架构）
    2. Object-based style for distributed object systems 对于分布式对象系统使用基于对象的风格

    image-20211226175558158

  2. 在空间（匿名）时间（异步）的解耦过程中产生了替代的样式（Decoupling processes in space (“anonymous”) and also time (“asynchronous”) has led to alternative styles）

    1. 以数据为中心的体系结构

      思想：进程通信需要一个公用仓库（共享的分布式文件系统）

    2. 基于事件的体系结构

      image-20211226180719684

    a图是空间解耦，进程通过事件的传播来通信，事件传播可以有选择地携带数据，分布式系统的事件传播通常与发布/订阅系统有关；

    b图是时间空间都解耦，将基于事件的体系结构与以数据为中心的体系结构组合形成共享数据空间

分布式系统组织形式

  1. 集中式

    1. 客户端服务器模式：

      • 提供服务器的进程

      • 提供客户端的进程

      • 客户端和服务器可以在不同的机器上运行

      • 客户端遵守请求/回复行为来使用服务

        客户端服务器之间的交互

    2. 为了在客户和服务器之间划分界限，使用了应用分层：

      1. 用户接口层：含有与用户交互所需的一切如显示管理

      2. 处理层：应用程序

      3. 数据层：使用的实际数据

        搜索引擎的抽象

    3. 多层体系结构

      1. 单层：哑终端/主机
      2. 双层：客户端/单服务器
      3. 三层：每一层都在不同的机器上运行

      各种客户服务器的组织架构

      其中a-c式瘦客户，后面的是胖客户

  2. 非集中式

    1. 结构化的点对点系统：

      比如chord，CAN等等，特点在于节点以特定的分布式数据结构进行组织。在一个结构化的覆盖网络(如逻辑环或超立方体)中组织节点，并使特定节点仅根据其ID负责某些服务。

      image-20211226212647705

      image-20211226212655369

    2. 非结构化的点对点系统

      构建类似于随机图的覆盖网络，基本模型是每一个节点都维护一个含有c个邻节点的列表。随机选择一个邻居v，如果v有答案，它会回答，否则v随机选择它的一个邻居。（维护一个超级节点）

  3. 混合式

    它将客户服务器体系结构和非集中式体系结构组合在了一起

    1. 边界服务器系统：用于内容分发网络，在进行过滤和编码转换后提供内容服务，还可用于优化内容和应用程序的分布性。

      把英特网堪称一系列边界服务器

    2. 协作分布式系统：比如BitTorrent文件共享，点对点文件下载：

      BitTorrent工作原理

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

分布式系统组织为中间件

中间件在应用程序和分布式平台之间形成了一个层，可以提供分布式透明性。

image-20211226214734990
image-20211226214734990

方式之一为中断器：作为一种软件结构，能中断正常的控制流，从而允许其他代码运行。

进程与线程

进程线程的定义

进程是特定上下文里一个执行的流，可以包含多个线程，有自己独立的内存管理单元，切换时也需要一
个进程所拥有的全部内容。
线程是一段执行流，是轻量级的进程，只需要简单切换堆栈和寄存器内的值即可，共享内存单元。

LWP

轻量级进程，这个采用了用户级线程和内核级线程的混合形式,

其中对于用户级线程：

  • 所有的线程都在用户的进程地址空间中创建。
  • 优点：所有的操作都能在单个进程中完成，导致实现起来很高效。
  • 缺点：难以从操作系统和block中得到支持。内核提供的所有服务都是代表线程所在的进程执行的，如果内核决定阻塞一个线程，那么整个进程将被阻塞。

内核级线程：

  • 可以解决上述问题
  • 但是由于每一个线程操作（创建删除同步化）都需要内核来进行执行，需要系统调用，导致内核级线程的开销可能和进程差不多大

LWP：

  • 运行在单个重量级进程的上下文中，每一个进程都可以包含多个LWP。另外系统还提供用户级线程包，包括了用于线程同步的工具，这部分内容完全在用户空间实现。并且可以被多个LWP共用。

    image-20211227140800732

  • 优点在于：线程创建，销毁，同步化工作开销小不需要内核干预，并且如果进程中有足够数量的LWP，阻塞的系统调用将不需要整个进程被挂起，另外应用程序不需要知道LWP存在，事实上只能见到用户级线程，并且通过在不同CPU执行不同的LWP，可以在多处理器系统中方便的使用

  • 缺点在于：必须进行LWP的创建和销毁工作，开销不必内核级线程小，但是只需要偶尔进行，并且受到操作系统的完全控制

代码迁移

  • 代码迁移的方法：

    • 代码段(Code Segment)：包含实际的代码
    • 数据段(Data Segment)：包含状态
    • 执行状态(Execution State)：包含线程执行对象代码的上下文

  • 强弱迁移

    • 弱迁移：只迁移代码部分和数据部分，最后被目标进程或另外一个独立进程执行

    • 强迁移：迁移执行部分，要么复制进程，要么克隆(所有数据完全复制，和原来的进程并行)

      image-20211227151251247

通信

通信的类型

  • 瞬时通信(Transient Commnunication)：通讯系统只有在发送和接收应用程序正
    在运行时才能存储消息
  • 持久通信(Persistent Communication)：提交传输的消息一直由通信中间件存储，
    直到该消息被传送给接收方为止
  • 异步通信(Asynchronous Communication)：发信方发信后立即继续，消息存储在发信方主机或者通信服务器的缓冲区中。
  • 同步通信(Synchronous Communication)：发信方在到达同步点前保持阻塞。

远程过程调用RPC

PS: 一般程序的调用：

image-20211227153318439
image-20211227153318439

RPC的工作过程：

  1. 客户过程以正常的方式调用客户存根(client stub)；

  2. 客户存根生成一个消息，然后调用本地操作系统；

  3. 客户端操作系统将消息发送给远程操作系统；

  4. 远程操作系统将消息交给服务器存根；

  5. 服务器存根调将参数提取出来，而后调用服务器；

  6. 服务器执行要求的操作，操作完成后将结果返回给服务器存根；

  7. 服务器存根将结果打包成一个消息，而后调用本地操作系统；

  8. 服务器操作系统将含有结果的消息发送给客户端操作系统；

  9. 客户端操作系统将消息交给客户存根；

  10. 客户存根将结果从消息中提取出来，返回给调用它的客户存根

    image-20211227154006443

    image-20211227154100592

故障处理

5 种故障

  1. 客户端不能定位服务器：使用特定的返回值 (异常处理)

    例如：服务器故障，服务器进化但客户端使用过期的客户端存根
    可能的解决方案：用特殊代码（如-1）作为返回值声明故障；抛出异常或信号

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

  3. 服务器发给客户的应答消息丢失：设置一个计时器，对于不幂等的请求 为客户请求分配序号 服务器
    区别不同的请求。

  4. 服务器在收到消息后崩溃(接受后执行前崩溃或者执行后发送前崩溃)：等待服务器启动 然后重发请
    求(至少一次)；或者立即放弃并报告失败(至多一次)；或者不做任何保证 ;

  5. 客户机在发送消息后崩溃：

    客户端在发送请求后，在收到服务器响应前故障，通讯是活跃的，但没有parent 在等待响应，形成孤儿

    1. 消除 extermination: 在日志文件中纪录 RPC 请求 重启后清除孤儿 。
    2. 再生 reincarnation: 按时间顺序编号不同的时间段。当客户端重启时，广播 一条消息宣布新的时间段开始，当广播到达时终止所有远程计算，无需日志。(服务端杀死所有的)（另一种说法：设置一个epoch,每个客户端进程重启为一个新的epoch。新epoch到达意味着之前的计算全部杀死）
    3. 温和再生 gentle reincarnation: 与再生相似，但是当广播到达时，每台机器会寻找远程计算的所
      有者，仅当找不到所有者时，计算才会被终止 。（服务端杀死掉线的）（另一种说法：设置一个epoch,每个客户端进程重启为一个新的epoch。新epoch 到达意味着将没有主的孤儿进程杀死 ）
    4. 过期 expiration: 赋予每个RPC一个标准时间配额，未完成任务明确申请额外配额。

动态绑定

绑定：一种让客户端找到服务器的方法

静态绑定：将服务器地址（IP、端口）硬编码到客户端代码中

动态绑定过程：

  1. 服务器启动时向Binder 注册
    Register 请求：参数:ID、名字、版本、地址
    Unregister 请求：参数:ID、名字、版本
  2. 客户端存根向Binder 查找服务器接口
    Lookup 请求：参数: 名字、版本；返回：ID、地址
    调用：客户端根据地址发送RPC 调用

优点：灵活性，可以支持多个支持同一接口的服务器，绑定程序可以验证客户端和服务器都使用相同版本的接口

缺点：导出/导入接口的额外开销花费时间，绑定程序可能成为大型分布式系统中的瓶颈

基于消息的通信

  • 瞬时通信(Transient Commnunication)：通讯系统只有在发送和接收应用程序正
    在运行时才能存储消息
  • 持久通信(Persistent Communication)：提交传输的消息一直由通信中间件存储，
    直到该消息被传送给接收方为止
  • 异步通信(Asynchronous Communication)：发信方发信后立即继续，消息存储在发信方主机或者通信服务器的缓冲区中。
  • 同步通信(Synchronous Communication)：发信方在到达同步点前保持阻塞。

面向流的通信

  • 分类

    • 连续数据流：支持异构数据传输的通信设施
    • 离散媒体：数据项在时间上的联系不重要
    • 连续媒体：不同数据项在时间上的联系非常重要，如：音频、视频、动画

  • 不同传输模式

    • 异步传输模式（离散媒体）：没有时间限制
    • 同步传输模式（连续媒体）：没有最大延迟时间
    • 等时传输模式（连续媒体）：最大延迟时间、最小延迟时间
  • 流与Qos
    • 利用区分服务为不同类型的数据提供服务
    • 利用缓冲区减少延时抖动
    • 交错传输来降低丢包影响

PS：流媒体看直播卡顿的解决的方法：

  • 利用区分服务为不同类型的数据提供服务
  • 利用缓冲区减少延时抖动
  • 交错传输来降低丢包影响
  • 使用更好的带宽估计算法

同步和资源管理

Lamport时钟

参考了该博客

  1. 先后关系：把事件 a 发生在 b 之前定义为 a → b，以下三种条件满足a → b：

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

    如果a和b没有先后关系，则称两个事件是并发的，记作 a || b。
    例子：

    image-20211227222919525

    ​ 这个例子中：

    • a → b → c → d
    • a → b → e
    • f → c → d
    • a || f
    • e || d
    • b || f
    • e || c

    1. 逻辑时钟算法：分布式系统中每个进程Pi保存一个本地逻辑时钟值Ci，Ci (a) 表示进程Pi发生事件a时的逻辑时钟值，Ci的更新算法如下：

      1. 进程Pi每发生一次事件，Ci加1。
      2. 进程Pi给进程Pj发送消息，需要带上自己的本地逻辑时钟Ci。
      3. 进程Pj接收消息，更新Cj为 max (Ci, Cj) + 1。

      上述例子的逻辑时钟：

      image-20211227223041307

      从以上算法可以很容易地得出下面两个结论：

      1. 同一个进程内的两个事件a和b，如果 a → b，那么 Ci (a) < Ci (b)。
      2. a是Pi进程的消息发送事件，b是Pj进程该消息的接收事件，那么 Ci (a) < Cj (b)。

    2. 另外如果 C (a) < C (b)，那么可以得出 a → b 吗？

      答案是不能，举个反例，图二中C (e) = 2，C (d) = 3，虽然 C (e) < C (d)，但并不能得出 e → d，e和d实际上是并发关系 e || d，也就是说由于并发的存在，导致反向的推论并不成立。

向量时钟

在向量时钟中如果C (a) < C (b)，可以得出 a → b，它的思想是进程间通信的时候，不光同步本进程的时钟值，还同步自己知道的其他进程的时钟值。

分布式系统中每个进程Pi保存一个本地逻辑时钟向量值VCi，向量的长度是分布式系统中进程的总个数。VCi (j) 表示进程Pi知道的进程Pj的本地逻辑时钟值，VCi的更新算法如下：

  1. 初始化VCi的值全为0：VCi = [0, … , 0]
  2. 进程Pi每发生一次事件，VCi[i]加1。
  3. 进程Pi给进程Pj发送消息，需要带上自己的向量时钟VCi。
  4. 进程Pj接收消息，需要做两步操作。
    1. 对于VCj向量中的每个值VCj[k]，更新为 max (VCi[k], VCj[k])。
    2. 将VCj中自己对应的时钟值加1，即VCj[j]加1

例子：

image-20211227223758776
image-20211227223758776

向量时钟中的向量的偏序关系定义如下：

  • 如果向量VCi中的每个元素VCi[k]都小于等于VCj中的对应元素VCj[k]，则VCi ≤ VCj。
  • 如果VCi中的每个元素VCi[k]都和VCj中的对应元素VCj[k]相等，则VCi = VCj。
  • 如果VCi和VCj不能比较大小，则称两个向量是并发的 VCi || VCj。

因此可以有以下推论：

  • 同一个进程内的两个事件a和b，如果 a → b，那么 VCi (a) < VCi (b)。
  • a是Pi进程的消息发送事件，b是Pj进程该消息的接收事件，那么 VCi (a) < VCj (b)。

然后可以推出：对于任意两个事件a和b，如果 a → b，那么 VC (a) < VC (b)。

证明VC(a) < VC(b) 可以推导a → b：

  • 如果事件a和b在同一个进程内，很显然 a → b。

  • 如果事件a和b在不同进程内，比如Pa和Pb。

    设VCa = [m ,n], VCb = [s, t]。

    因为VCa < VCb，所以m ≤ s，所以必然在不早于a之前和不晚于b之后的时间内，Pa向Pb发送了消息，否则Pb对Pa的计数器得不到及时刷新，s就不会小于m。

    实际上可以分为如下四种情况：

    image-20211227224429102

    1. 当a = c且d = b，易得a → b。
    2. 当a = c且d → b，由传递性，得a → b。
    3. 同样对于d = b且a → c的情况。
    4. 当a → c且d → b，根据进程内的算法逻辑性和传递性，也很容易得出结论。

  • 综上: VCa < VCb 推导出 a → b 得证。

分布式系统中的互斥访问

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

    优点：

    • 保持互斥
    • 公平
    • 无饥饿
    • 容易失效：请求、授权、释放

    缺点：

    • 单点故障
    • 性能瓶颈
    • 无法区分coordinator 失效or 权限拒绝

    PS: 非集中式 多个leader

  2. 分布式算法：基于时间戳；

    1. 进程如果想进入临界区，那么构建含临界区名字、进程编号、当前时间的消息发给所有进程；
    2. 进程收到请求消息：
      1. 如果接收方未在临界区
        1. 想进入临界区：对比消息的timestamp，如果接收消息的timestamp比较早，返回
          OK；否则缓存请求，返回空
        2. 不想进入临界区：返回OK
      2. 如果接收方已在临界区，缓存请求

  3. 令牌环算法：

    1. 用软件的方法，按照进程的地址或者编号等，为总线型的网络构造一个逻辑环。一个令牌环只能
      对应进入一个临界区。
    2. 过程：令牌环绕进程环依次传递，如果接受进程如果不需要进入临界区，则继续传递给下一个进程，如
      果接受进程需要进入临界区，那么此时传递暂停，令牌等待，直到进程从临界区返回后继续。
    3. 缺点：令牌丢失的检测和再生因为无法确定时间间隔而非常困难；进程崩溃虽然可以恢复，但是需要通
      过每个进程向前继进程发送确认消息来实现，也就需要每个进程都维护当前的配置信息。

  4. 比较：

    image-20211227231113593

分布式系统中的选举机制

  1. bully算法：

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

    2. 选举过程：

      1. 发起选举的进程Q只能向编号比自己大的进程发起election消息
      2. 如果Q一直没有接受到OK应答消息，则由Q获胜充当协调者，否则，退出选举

      因此最大的进程总是取胜，所以叫 bully(欺凌)算法

    3. 例子：

      image-20211227233130739

  2. 环算法：

    1. 发起选举的条件：所有进程已经按照编号进行排序并且链接成环，任何一个或者多个进程发现原有协
      调者崩溃或者没有响应时，开始发起选举。

    2. 选举过程：发起消息者构造election消息，依次向后传递。传递过程中如果后继进程已经崩溃，则绕
      过（不仅仅是刚刚崩溃了的协调者），如果后继进程正在运行，则把编号添加进election消息成员列表。待绕环一周返回到发起者后，根据选举消息中的编号（选取成员列表里面最大的那个）选出协调者，并用coordinator消息绕环通知所有进程，循环一周后该消息被删除。

    3. 栗子：

      image-20211227233428655

复制与一致性

复制的优势和不足（分布式系统多副本的优点和缺点）

  • 优点：
    • 可靠性：避免单点故障
    • 性能：对服务器数量和地理区域上的扩展
  • 不足：
    • 复制透明性：某个用户不知道某个对象是复制的
    • 一致性问题：更新过程开销大，可能影响系统可用性

一致性模型实质上是进程和数据存储之间的一个约定，也就是如果进程同意遵守某些规则，那么数据存储将正常运行

PS：一致性模型的类型：

  • 面向数据一致性模型：本地数据存储的组织通常在分布在多个进程，并进行复制
  • 面向客户的一致性模型：保证单个客户端访问数据存储的一致性

数据一致性模型

参考了博客1以及博客2

image-20211228142648852
image-20211228142648852

不引入同步操作的一致性模型

  • 严格一致性（Strict Consistency）：

    所有共享访问事项的绝对时间顺序

    • 任何读操作返回与最新写操作结果对应的值
    • 依赖绝对全局时间; 所有写入对所有进程都即时可见，并维护绝对全局时间顺序
    • 分布式系统中无法实现

  • 线性一致性（Linearizability），又称为强一致性或者原子一致性：

    所有进程都必须以相同的顺序查看所有共享访问。此外，访问根据（非唯一）全局时间戳排序;

    一旦某一个读操作返回了新值，之后所有的读（包括相同或不同的客户端）都必须返回新值

  • 顺序一致性(Sequential)：

    所有进程都以相同的顺序查看所有共享访问。访问不是按时间排序；

    • 与线性一致性类似，对时间顺序无要求
    • 从单个处理器 (线程或者进程)的角度来看，执行指令的顺序以编程中的顺序为准。
    • 从所有的处理器(线程或者进程)的角度来看，指令的执行保持一个单一的顺序。

    与线性一致性比较的例子：

    image-20211228150820914

    因为a中可以找到一个执行序列： Write("y", 1) -> Read("x" -> 0) -> Write("x", 1) -> Read("y" -> 1) 满足顺序一致性。但是从时间角度看Write("x",1) 要先于 Read("x") -> 0 执行，但是 Read 却没有读取到最新值，所以不满足线性一致性。

    b中都满足

    c中找不到这样的执行序列，所以不满足顺序一致性；

    顺序一致性和线性一致性都是要找到一个满足 “写后读” 的一组操作历史，差异在于线性一致性要求严格的时间序，而顺序一致性只要求满足编程顺序。

  • 因果一致性（Causal Consistency）

    所有进程都以相同的顺序查看与因果相关的共享访问

    • 有因果关系的写操作，不同的进程看到相同的顺序
    • 没有因果关系的写操作，不同的进程可以看到不同顺序

    来自这个知乎的例子:

    image-20211228153131011

    image-20211228153136952

  • 管道一致性（FIFO Consistency/PRAM）

    所有进程都按使用顺序看到彼此的写入；不同进程的写入可能并不总是按相同的顺序显示

    • 由同一个进程进行的写操作，必须看到相同的顺序
    • 不同进程的写操作，不同进程可以看到不同顺序

    这个算是一种弱一致性

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

  • 弱一致性（Weak Consistency）

    只有在同步完成后，才能让共享数据保持一致；（有一个同步事件S，保证在S之后的读能看到S之前的读写顺序。）

    具体限制：

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

  • 释放一致性（Release Consistency）

    退出关键区域时，共享数据保持一致（写数据时加全局锁，加锁之后的顺序就不能乱来，不加锁的话读到什么都可以。还锁的时候同步）

    • 获取操作：用于通知数据存储进程进入临界区的操作
    • 释放操作︰表明进程刚刚离开临界区的操作

    具体限制：

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

  • 入口一致性：

    进入共享数据对应临界区时，共享数据一致（每个数据的读写都要加锁，不加锁读数据，不保证给出什么东西，给出nil都可以。拿锁的时候同步）

    • 要求每个普通的共享数据项都要与某种同步变量关联
    • 具体限制为
      • 在一个进程可以获取一个同步变量之前，所有的由此同步变量保护的共享数据的更新都必须已经相对于该进程执行完毕
        • 执行获取操作时，所有的受保护数据的远程改变都必须已经可见
      • 在一个进程对一个同步变量的独占访问被允许执行之前，其他的进程不可以拥有这个同步变量，甚至也不能以非独占的方式拥有这个同步变量
        • 更新共享数据项之前，必须以独占的方式进入临界区
      • 一个进程对一个同步变量执行独占访问之后，在对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个非独占访问
        • 非独占方式进入临界区之前，必须检查保护这个临界区同步变量的所有者,以获得受保护的共享数据的最新副本

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

  • 最终一致性

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

  • 单调读：

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

  • 单调写：

    一个进程对数据项x 执行的写操作必须在该进程对x 执行任何后续写操作之前完成；写操作必须顺序完成，不能交叉（写完一个值之后，才能继续写下一个，不允许写的过程中开始一个新的写时间(read your write):写了之后，后续的读一定能读到这个值，而不会读到旧值写的时候，保证所替换掉的是之前读出来的值）

  • 写后读 Read your writes（读写一致性）：

    一个进程对数据项x 执行一次写操作的结果总是会被该进程对x执行的后续读操作看见；保证读取最新（写了之后，后续的读一定能读到这个值，而不会读到旧值）

    image-20211228163203615

  • 读后写 writes-follow-reads consistency （写读一致性）：

    同一个进程对数据项x 执行的读操作之后的写操作，保证发生在与x 读取值相同或比之更新的值上；更新作为前一个读操作结果传播（写的时候，保证所替换掉的是之前读出来的值）

    image-20211228163229625

数据一致性协议实例

基于法定数量的协议 Quorum-based protocols

  • 对于一个具有 N 个副本的文件
    • 客户要读取时，必须组织一个服务器数量为 Nr 的读团体(read quorum)
    • 客户要修改时，必须组织一个服务器数量为 Nw 的写团体(write quorum)
  • 其中，Nr 与 Nw 满足以下限制条件
    • Nr+Nw>N: 用于防止读写冲突
    • Nw>N/2: 用于防止写写冲突
image-20211228171012230
image-20211228171012230

容错

可靠（Dependable System）的系统的特征

有群友总结为 ASMR

  • 可用性：在任意给定的时刻，系统都可以正确及时地工作，并执行用户的请求。 A
  • 安全性：系统偶然出现故障时还能正确操作和执行。 S
  • 可维护性：表示发生故障后系统能被恢复到可用性的难易程度 M
  • 可靠性：系统可以无故障持续运行； R

PS 基础定义：

error → fault → failure

  • fault: 造成error 的原因
  • error：系统错误的状态，可能导致failure
  • failure：没有满足承诺，无法提供服务

故障分类：

  • Crash failure（服务器重启，重启正常）
  • Omission failure（遗漏错误）
  • Timing failure（超时）
  • Responsne failure
  • Byzantine faiure

提高系统可信性的途径

  • 使用冗余来掩盖故障：
    • 信息冗余：添加额外的位或码恢复错乱的信息。
    • 时间冗余：多次执行需要的动作。可以使用事务。适用于临时性或者间歇性的错误。
    • 物理冗余：添加额外的装备（硬件）或者进程（软件）使系统整体容忍部分错误。

K容错系统

参考博客

K容错：系统能够经受k个组件的故障并且还能满足规范要求。当这些组件是失败沉默的情况下，需要
k+1个组件可以提供k容错；如果发生拜占庭失败，至少需要2k+1个进程才能获得k容错。 课本P242页

怎么证明可以参考这个知乎

拜占庭问题

在容错计算机系统中，经常需要部件之间的信息传递与分发，而一个失效的部件将会向其他部件发送错误的消息。容错计算机中失效部件向不同部件发送错误消息的问题，可被抽象为拜占庭将军问题：

算法流程：

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

例子：

image-20211228194256257
image-20211228194256257

系统恢复

恢复：发生故障的进程能够恢复到正确的状态

  • 两种形式

    • 后向恢复：从当前错误状态回退到先前正确状态
    • 前向恢复：尝试从某点继续执行，把系统带入一个正确的新状态

  • 检查点：系统定时记录状态到稳定存储

    • 每个进程独立地设置本地检查点，依赖项的记录方式使进程可以联合回滚到一致的全局状态

    • 但每个进程回退的状态可能不一致，需要继续回退，可能造成多米诺效应

      多米诺效应

  • 协调的检查点：

    • 所有进程同步地把各自状态写到本地稳定存储中

PS 两阶段提交

二阶段提交
二阶段提交

为什么两阶段提交叫做阻塞提交协议？

当所有参与者都从协作者那里接收到信息变成READY状态的时候，并且同时协作者崩溃的时候就会发生阻塞

分布式一致性协议

Paxos协议

参考的知乎

Paxos 保证了：安全性 和 最终一致性（Eventual liveness）：

  • 安全性：只有被提议的值才可能会被选择，只有一个值会被选择，只有最终被选择的值才会被进程所保存。
  • Eventual liveness, 如果系统正常运行下去，在未来的某一个点，最终会达成共识。
通信实例
通信实例

Raft协议

  • 用户选举
  • Log Replication

Gossip协议

需要O(logN)轮才能把信息传播到所有节点，push SI总共传播的信息数量O(NlogN);Pulland push-pull SI 需要传播的信息数量O(NloglogN)

大数据处理系统

对于DAG型作业Spark+Yarn的优势在哪里？

  • DAG型的每个中间结果hadoop会有频繁的磁盘IO，spark用分布式弹性数据集把中间结果存在内存中，避免了DAG中间结构的频繁IO
  • hadoop+hdfs的集群，集群需要同时进行资源管理和任务控制，耦合度高。Yarn只负责资源管理，将任务控制交给应用去设计，耦合度低。虽然Yarn应用的逻辑变复杂了，但可以支持更多的编程模型和设备。
容错 拜占庭协定
沉默错 k+1 2k+1
拜占庭错 2k+1 3k+1

(所有挂k个，表格里面是总量)

沉默错拜占庭协定2k+1: 挂掉的节点k个醒了之后需要k+1个正确的来达成一致性

容错取众数，拜占庭协定需要两轮，可以参考这个知乎