分布式笔记

分布式笔记

作者：哈利波特👑

第一章 分布式简介

分布式定义，分布式特点，目标（四个特性的含义），分布式的类型。

分布式系统的定义

由若干个独立的计算机组成（硬件），这些计算机对于用户来说像是一个耦合系统（软件），这些计算机（节点）之间通过网络通信来互相协同，共同完成特定的任务。

物理分布，逻辑集中，个体独立，整体统一。

分布式系统的特性

  1. 构成组件被所有用户共享

    这意味着用户无需关心资源的具体位置或所属节点，可以像使用本地资源一样访问和使用这些共享资源。

  2. 系统资源可能不允许访问

    尽管资源是共享的，但并不是所有资源对所有用户都开放。

  3. 软件运行在不同处理器上的多个并发进程上

    在分布式系统中，软件不是在单一的处理器或计算机上运行，而是分布在多个处理器或节点上同时运行。

  4. 允许多点控制

    多点控制指的是系统中的多个节点或用户能够同时控制和管理系统资源或服务。在一个分布式版本控制系统（如Git）中，多个开发者可以在不同的地点同时对代码库进行更改和管理。

  5. 允许多点失效

    多点失效意味着系统能够容忍多个节点或组件的同时故障，而不会影响整个系统的正常运行。

分布式系统的四个目标

资源能够共享（方便访问数据）

在云计算平台上，用户可以存储和访问存储在不同服务器上的数据，而无需了解数据存储的具体位置。

透明性（用户不知道分布式系统内部是如何协作和计算的）

用户在使用分布式文件系统时，无需关心文件存储在哪个服务器上，只需像操作本地文件一样进行访问和管理。

但是**完全透明性是不可取的！**因为：

  • 难以找到失效的节点

  • 分不清节点是失效还是性能变慢

    当一个节点响应变慢时，系统难以判断是节点真正失效还是只是暂时的性能下降。这会影响系统的故障处理策略，可能导致误判和资源浪费。

  • 会牺牲性能

    为了隐藏数据分布，系统可能需要频繁地进行数据复制和同步，这会增加网络负载和延迟，影响系统的响应速度。

  • 有一致性问题

    在分布式文件系统中，当一个文件被修改时，需要将修改同步到所有副本节点。这一过程需要时间，如果同步延迟过长，用户可能会看到不一致的文件版本。

开放性

通过标准化的接口使得不同设备和应用可以轻松地进行通信和数据交换。

**标准化的接口：**使用大家都认可的通信规则和接口，让不同的系统和设备能够互相“说同一种语言”。

  • **策略（做什么）与机制（如何做）**分离

可扩展性

分布式数据库系统可以通过增加更多的服务器节点来处理更大的数据量和更多的并发请求，而不影响查询速度和响应时间。

  • 规模扩展性

    系统能够在用户数量和进程（或服务）数量不断增加的情况下，依然保持高效运转。

  • 地域扩展性

    系统中的节点能够分布在很远的地理位置（甚至跨国跨洲），但整体依旧能高效运作，避免因网络延迟、带宽等问题导致系统性能急剧下降。

    CDN

  • 管理扩展性

    大型企业或跨国公司在多个地区有独立的IT管理团队，系统需要支持多层权限和多域管理，保证各团队在各自的权限范围内管理资源，同时又能协同工作。

可扩展技术如下：

  • 隐藏通信时间

    就是想办法在等待远程响应的同时，让系统做其他有用的事情。

  • 分布

    在多个机器上划分数据和计算

  • 副本

分布式系统的分类

分布式内存共享系统

分布式内存共享系统是一种使多个节点（计算机）看起来像一个统一的共享内存空间的系统。通过这种方式，分布在不同节点上的进程可以像在单一系统中一样访问和操作共享内存，从而简化并行编程模型。

集群计算系统

想象一下，你和你的朋友们一起完成一个大型项目：

  • 单台计算机：就像一个人独自完成整个项目，可能速度较慢，遇到问题时无法继续。
  • 集群：就像一个团队，每个人负责不同的部分，大家一起工作，完成速度更快，而且如果某个人有事，其他人还能继续完成任务。

网格计算系统

想象你在组织一个全球性的拼图比赛：

  • 单台计算机：就像一个人独自拼一幅巨大的拼图，可能需要很长时间才能完成。
  • 网格计算：就像你邀请世界各地的朋友们，每个人负责拼图的一部分，大家一起合作，很快就能完成整个拼图。

第二章 分布式系统架构

两种架构（系统、软件）、软件：四种（分层、事件… 四种特性）、系统三种（集中、非集中、混合特点）

重点：C-S集中式架构、P2P非集中式：非结构P2P如何查询、DHT构建与查询

软件体系结构

分层结构

主要用于客户-服务器模型。

每层之间是独立的，并且每层只知道下一层提供的服务而不关心是如何实现的。

面向对象结构

每个对象都有自己的数据和方法（函数），假设对象A调用方法B，但是方法B其实在对象B上，对象A对对象B执行RPC。

基于事件结构

发布者发布事件，订阅者订阅感兴趣的事件。当事件发生时，发布者将事件发送到一个中介，订阅者接收并处理这些事件。

将时间解耦了，发布者发布完事件之后就可以做自己的事情（异步）。

共享数据空间结构

多个进程或节点通过共享一个共同的数据空间进行通信和协作。

将空间解耦了，节点并不知道自己使用的是谁的数据。

系统体系结构

确定软件组件、软件组件之间的交互与位置，就是软件体系结构的一个实例，也是软件体系结构的一个具体应用。

集中式体系结构

整个系统包含一个控制中心，协同系统的运行。

有客户服务器模型：

  • Server进程：实现特定服务的进程；
  • Client进程：通过往服务器发送请求来请求服务、然后等待服务器回复的进程；

像软件体系结构的分层和面向对象都是客户服务器模型。

应用分层

我的理解是跟数据库的分层是一样的。

层与层之间有接口，同一层的两个节点有通信和提供的服务。

非集中式组织结构(P2P)

系统没有一个整体的控制中心，各个节点独立自主运行。

  • 垂直分布：系统逻辑分层，不同层次分布式不同的机器上；

  • 水平分布：客户或者服务器在物理上分成逻辑上相等的几个部分， 每个部分相对独立，且分布在不同的机器上；

  • 点对点系统（P2P）：水平分布，构成点对点的系统的进程完全相同（既是客户端又是服务器、无中心化系统）。

    • 结构化的P2P系统：P2P系统中的节点按照特定的分布式数据结构组织，like chord环形结构。

    • 无结构化的P2P系统 ：点的邻居是随机选择的。

    • 混合化的P2P系统：某些组织是具备特定结构的。

分布式哈希表（DHT）

可以不依赖一个中心服务器，每个节点维护一部分的哈希数据。

  • 加入：新节点加入DHT网络时，会根据哈希函数分配一部分键空间，接管部分数据存储，保持哈希表的平衡。
  • 离开：节点离开时，其存储的数据会被重新分配到其他节点，确保数据的完整性和可访问性。
非结构化P2P数据查询

节点之间的连接是动态且随机的，网络的整体拓扑结构没有严格的规则。

维持一个动态随机的邻接表，确保每个节点只与网络中一部分随机选取的其他节点直接连接，从而降低维护整个网络连接的复杂性。

  • 泛洪方式：

    因为只能看到部分视图，所以像其他所有邻居节点发送数据查询请求，如果邻居也没有的话就继续迭代下去发送数据请求。会有很多冗余请求。

  • 随机游走：

    随机选择一个邻居发送数据查询请求，没有就找下一个邻居。这种方式可能会找不到数据。

因为非结构化P2P很难查询数据，所以引入超级对等节点。

超级对等节点

将非结构化的P2P系统拓扑划分为一个个自治区（子网），然后找数据的时候只需要找自治区的超级对等节点（边缘路由器）就行了。

选择超级对等节点的条件：选择运算力大、存储空间大或者看自治区的拓扑与节点位置决定。

混合组织结构

系统中既包含集中式结构也包含了非集中式结构。

在很多场景中，客户端-服务器架构（集中式）是和P2P架构（非集中式）整合在一起的。

例如像计网的CDN：

首先有客户请求视频（集中式架构），但是存储视频的服务器可能将视频存到多个CDN服务器上，客户可以直接去找CDN服务器拿视频。CDN服务器既是服务器也是客户（非集中式结构）。

分布式系统的自我管理

出现问题能够自我优化、恢复。在需要完成自适应功能时， 系统架构和软件架构之间的界线逐渐模糊。

采用反馈控制循环来控制：

like 强化学习。

第三章 分布式系统的进程与虚拟化

虚拟化的含义、类型，docker的定义，有/无状态服务器优缺点，服务器集群（负载均衡），代码迁移。

为什么要利用线程而不是进程

  • 线程是共享内存的，切换上下文不需要操作系统介入。
  • 线程切换上下文的开销比进程小，进程切换上下文需要操作系统内核操作。
  • 创建和删除线程的开销比进程小很多，并且速度快很多。

但是因为线程是共享内存的，所以其实不安全。

虚拟化

虚拟化是通过软件技术将物理计算资源抽象和隔离，使多个独立的虚拟实例能够在同一硬件上同时运行。

情景描述： 假设你有一台运行Windows操作系统的电脑，但你同时需要使用Linux系统来完成某些特定任务。

虚拟化的应用：

  1. 安装虚拟机软件：
    • 你可以安装像VirtualBox或VMware这样的虚拟机软件，这些软件能够在你的Windows系统上创建虚拟环境。
  2. 创建虚拟机：
    • 在虚拟机软件中，你创建一个新的虚拟机实例，并为其分配一定的硬件资源（如CPU、内存、存储空间）。
  3. 安装Linux操作系统：
    • 在这个虚拟机中，你安装Linux操作系统。现在，你的电脑上既运行着Windows系统，又通过虚拟机运行着Linux系统。

通过模拟接口，虚拟化软件为虚拟机提供了一个虚拟的、标准化的硬件环境。这使得虚拟机中的操作系统和应用程序无需感知底层物理硬件的具体细节，能够像在真实硬件上运行一样操作。

虚拟机化的不同方式

  • 进程虚拟机：分离的指令集合，实际是运行在操作系统之上的解释器或者模拟器。

    它为单个应用程序或进程提供一个抽象的执行环境，使其能够在不同的硬件和操作系统平台上运行，而无需修改源代码。

    例如像JVM，允许Java程序在任何安装了JVM的设备上运行，无需关心具体的操作系统和硬件架构。

  • 原生虚拟机监控器：底层的指令，同时具有跑在硬件上的最小的操作系统。

    是一种直接运行在物理硬件上的虚拟化层，不依赖于宿主操作系统，所以性能高。

  • 主机虚拟机监控器：底层指令，但是需要一个完整的 OS。

    是一种运行在宿主操作系统之上的虚拟化软件。

Docker

  • 镜像—镜像就像是一份食谱。，docker 将所有app都标准化，需要使用就拉取镜像。
  • 仓库—仓库就相当于是一个烹饪书，里面存放了各种食谱，docker将所有镜像存储于仓库。
  • 容器—容器就是就像是根据食谱实际制作出来的菜肴，每个容器是独立的。这就体现了它的隔离性；

虚拟机与Docker的比较

  • **虚拟机：**虚拟机是在物理硬件之上运行的完整计算机系统。每个虚拟机都有自己的操作系统（Guest OS），并通过虚拟化软件（如VMware、Hyper-V、VirtualBox）与物理硬件交互。
  • **Docker：**通过容器（Containers）运行应用程序。

虚拟机隔离性更好，每个虚拟机有自己独立的操作系统；Docker性能更好。

服务器与状态

  • 无状态服务器

    在处理完请求后，从来不保存关于客户端的精确的信息。

    • 不记录一个文件是否被打开
    • 不去追踪客户的信息
    • 客户端和服务器完全独立

    可能会导致：

    • 客户和服务器的不一致问题减少，因为客户的记录和服务器的记录不需要一致。
    • 由于服务器不能预测客户端的行为，可能导致性能下降（例如有状态服务器可以记录上次这个文件看到哪里了，但是无状态服务器不行）。

  • 有状态服务器

    记录客户端的状态信息。

    • 记录客户端打开的文件，下次访问可以提前预取。
    • 需记录客户的信息。

    可能会导致：

    • 有状态的服务器的性能非常高。
    • 可靠性问题是一个主要的问题（可能客户端和服务器端的缓存不一致）。

服务集群的负载均衡

负载均衡：用于将网络或应用程序的流量分配到多个服务器上，以确保系统的高可用性、可靠性和高性能。

简单来说，首先先基于内容可感知的分派：

客户端发送 Setup Request (连接请求)

  • Client → Switch
    客户端向负载均衡器（Switch）发送一个连接请求（Setup Request），这个请求可能包含连接所需的信息。

Switch 将请求转发给分发器 (Distributor)

  • Switch → Distributor
    负载均衡器将 Setup Request 转发给分发器。分发器会负责根据调度算法决定将请求分配给哪个应用服务器。

分发器选择应用服务器

  • Dispatcher Selects Server
    分发器根据某种调度策略（如最少连接数、权重等）选择最合适的应用服务器来处理该请求。

TCP 连接的转交 (Hand Off)

  • Distributor → Application Server
    分发器选定服务器后，将该 TCP 连接的处理权交给具体的应用服务器。这一步实现了对客户端请求的分派。

Switch 被通知处理其他消息

  • Distributor → Switch
    分发器将负载分配信息通知 Switch，使其知道后续的数据包应如何转发。

应用服务器处理请求并返回响应

  • Application Server → Client
    应用服务器完成客户端请求的处理，并将结果直接返回给客户端，通常通过 Switch 转发。

就是可以考虑到的条件更多了，例如像查看请求的内容去分发合适的服务器，之前是只分发TCP连接少的服务器。

代码迁移

迁移模型中，进程由三个部分组成：

  • 代码片段（code）：包含实际执行的代码；
  • 数据片段（resource）：包含状态 ；
  • 执行状态（exec）：包含线程执行对象代码的上下文；

  • 弱移动性：仅仅移动代码和数据片段

    • 相对简单，特别是如果代码是可移植的
    • 需要区分两种模式：代码推送（push）和代码拉取（pull）

  • 强移动性：移动组件，包括执行状态

    • 迁移：将整个对象从一个机器移动到另一个机器；

      冷迁移，两个对象的执行状态可能不一样。

    • 克隆：开始克隆，将其设置为相同的执行状态；

      热迁移，两个对象的执行状态一样。

虚拟机迁移

无论哪种方式，虚拟机都会停机。

  • 预拷贝：将内存页面推送到新的机器，在迁移过程中重新发送被修改过的页面；
  • 停机-迁移-启动：停止当前的虚拟机；迁移内存，然后重新启动虚拟机；
  • 按需拉取：让新的虚拟机按需拉取内存页面：在新的虚拟机上立即创建进程，并且按需拷贝内存页面；

第四章 通信

RPC的基本过程、通信类型（异步同步）、面向消息通信（sockets的操作：创建发送接收）、消息队列类型，实现，管理器，路由，转发器等作用

多播通信，Gossip通信（解决传播）（反熵，流言工作过程）

通信类型

瞬态 VS 持久通信

  • 瞬态通信：当消息不能传递到另外一个服务器的时候，丢弃消息；

    依赖双方同时在线，例如像线上聊天系统。

  • 持久通信：消息存储在通信服务器直到消息被传递出去；

    消息在中间保存，适用于可靠传输的系统，例如像邮件系统。

异步通信VS 同步通信

  • 同步通信：客户端需要等待服务器响应（阻塞）。客户端等待回应的时候不能做其他工作。
  • 异步通信：客户端不需要等待服务器响应。

RPC的基本过程

程序在不同计算机上调用另一个计算机的程序。

透明性：使得用户像在本地调用函数一样。

基本流程如下：

客户端流程

  1. 客户端调用本地代理（Stub）：

    • 客户端调用一个本地方法（例如 doit(a, b)），看起来像本地函数调用。
    • 实际上，这个方法会被传递给客户端的“Stub”（代理）处理。

  2. 客户端 Stub 构建消息：

    • 客户端的 Stub 将调用的函数名（doit）、参数类型（如 type1）和参数值（如 val(a)）打包成一个消息。

    • Stub 的工作是将本地调用转换为可以通过网络发送的消息（序列化）。

      函数参数可能是复杂的对象、列表、字符串等，无法直接通过网络传输

  3. 客户端操作系统发送消息：

    • 客户端 Stub 调用本地操作系统（Client OS）来通过网络发送消息到服务端。

服务端流程

  1. 服务端操作系统接收消息：
    • 消息通过网络到达服务端的操作系统（Server OS）。
    • 操作系统将消息传递给服务端的 Stub。
  2. 服务端 Stub 解包消息：
    • 服务端的 Stub 从消息中提取出函数名和参数，将其翻译成服务端可以理解的本地调用。
  3. 服务端调用实际方法：
    • 服务端 Stub 调用对应的实际实现方法（例如 doit 方法）。
    • 方法使用解包后的参数（如 val(a) 和 val(b)）进行计算，返回结果。

服务端返回结果到客户端

  1. 服务端 Stub 构建响应消息：
    • 服务端 Stub 将返回的结果打包成一个响应消息。
  2. 服务端操作系统发送消息：
    • 服务端 Stub 调用操作系统，将响应消息通过网络发送回客户端。
  3. 客户端操作系统接收消息：
    • 客户端操作系统接收响应消息，并将其传递给客户端的 Stub。
  4. 客户端 Stub 解包消息并返回结果：
    • 客户端 Stub 解包消息，提取出返回值并将其交给调用者。
    • 对客户端调用者来说，整个过程就像是一次本地函数调用。

面向消息的通信

面向消息的瞬时通信：Berkeley套接字

记得看看服务器的accept和客户的connect是同步点。

是面向消息的同步、瞬态通信。

面向消息的持久通信：消息队列系统（MPI）

通过中间件层的队列支持实现异步持久的通信。队列相当于通信服务器的缓冲区（持久通信）。

队列管理器：负责管理队列，应用程序仅将消息放在本地队列中，然后由队列管理者将消息路由到其他地方。

消息队列系统的一般体系结构：

消息转换器：消息队列系统假定存在一个共同的消息协议；应用程序会在消息的格式上达成一致（即消息的结构和数据表示）

是消息队列系统的核心组件，负责管理消息的传递、存储和分发。

实际上实现的是队列！！

面向流的通信

多播通信

其本质是将分布式系统组织成一个覆盖网络，然后利用这个网络分发数据；覆盖网络的构建方法：

  • 组织成树，导致每对节点之间只有唯一的路径（一对多）；
  • 组织成网络结构，每个节点都有多个邻居节点（健壮性高）；

Gossip数据通信

本质是一种分布式的去中心化的协议，可以解决状态在集群中的传播和最终一致性的保证。

假设信息传播过程中不存在写-写冲突：

  • 更新是从一个节点开始的
  • 仅会向几个邻居传播副本（像病毒一样传播）
  • 更新是滞后的
  • 最终，每一个更新都会到达所有副本。（最终一致性）

反熵模型

反熵模型是 结点P随机选取另一节点Q，然后与Q交换更新信息，减少系统的不一致性（降低熵）。

  1. P只是把它自己的更新信息发出给Q，即为push的方法
  2. P只是从Q那里获得更新信息，即为基于pull的方法
  3. P和Q相互发送更新信息给对方，基于push-pull的方法

第五章 命名系统

给实体名字，命名是什么（标识符），指纹表如何构建、查询。结构化命名（DNS解析）组织以及如何DNS解析。

简单来说，分布式命名系统实现的作用就是我可以通过一个“名字”来查询我要的资源。

命名：是指在系统中为对象、资源或实体分配一个唯一的标识符，以便能够识别和引用这些对象、资源或实体。

名称：用名字标识分布式系统中的实体对象，由字符组成的字符串。

一个独立于实体地址的名称通常是比较合理的，而且更为灵活， 这样的名称是与位置无关（位置可能会变）。

标识符：一个标识符至多引用一个实体； 每一个实体最多由一个标识符引用； 一个标识符始终引用一个实体（标识符永远不会重新使用）

一个标识符不一定是一个单纯的名字，它可以包含特定的内容。

原则上，命名系统含有一个名称到地址的绑定，即一个（name, address）对的表。

分布式散列表

  • 每一个节点被赋予一个由m位构成的标识符；
  • 每一个实体被赋予一个唯一的m位的健值；
  • 健值为k 的实体存储在满足id >= k 的最小标识符节点上，成为k 的后继者, succ(k)。

指状表的第 i 项（FTp[i]）指向的是距离当前节点 p 至少 $$2^{i-1}$$ 位置的第一个节点。

查找逻辑：当前节点 p 检查它的指状表，并将查询请求转发给一个更接近目标节点的节点。

查找过程：

  • 使用指状表逐步跳跃查找目标节点，每次跳跃使范围缩小一半，最终找到目标节点。
  • 查找效率为 O(log N)。

节点加入：

  • 新节点计算其位置，更新后继和前驱关系。
  • 将数据从后继节点转移到新节点。
  • 并且其他节点也需要更新自己的指纹表。

节点退出：

  • 离开节点通知后继和前驱节点，将范围和数据转移给后继节点。
  • 通过稳定化更新指状表，维持系统一致性。

分层定位方法

创建一个大规模的搜索树，底层的网络被划分成多个分层的域。每一个域由一个目录节点表示。

树结构查询的过程总结

  • 起点：从叶节点开始查找。
  • 向下搜索：如果当前节点知道目标实体的位置，则沿着指向子节点的指针继续向下查找。
  • 向上回退：如果当前节点无法找到目标，则回退到父节点，逐步向上查找。
  • 终止条件：
    • 找到目标实体，查找结束。
    • 回退到根节点，如果根节点仍然无法找到目标实体，则查找失败。

树结构插入的关键

  • 插入请求被转发到知道实体 E 地址对的第一个节点；

  • 建立一条从第一个知道实体 E 地址的节点到实体 E 的指针链

名称解析-闭包机制（closure mechanism）

名称解析： 给定一个路径名，查找出存储在由该名称所指向的节点中的任何信息，查询名称的过程称为名称解析。

简单来说，名称解析就是根据给定的“名称”（通常是路径名或标识符），找到对应资源的实际位置或其存储的信息。

闭包机制：知道如何启动以及在何处启动名称解析通常称为闭包机制

没有闭包机制，名称解析无法顺利启动，因为系统不知道解析的入口和规则。闭包机制确保了解析能够启动并顺利完成。

链接

硬链接（Hard link）:我们所描述的路径名. 即用于在命名图中按照特定路径搜索节点的名字就是“硬链接”；

无论你用哪个硬链接访问文件，它们都是同一个文件。

删除一个硬链接不会影响另一个，因为实体只在所有硬链接删除后才会真正从磁盘上清除。

软链接（Soft link）：允许一个节点 N 包含另外一个节点名字. 用叶节点表示实体，而不是存储实体的地址和位置，该节点存储绝对路径名。

首先解析N 的名字；读取N 的内容返回名字；利用返回的名字进行名字解析；

软连接是一个独立的实体, 实体内容是指向的实体的绝对路径.

挂载

挂接点: 挂接点是本地命名空间中的一个目录节点，它用来存储外部命名空间的入口。

挂载点: 挂载点是外部命名空间中的目录节点，作为外部命名空间的入口点。它是外部命名空间的“根”（Root），从这里开始，外部命名空间的资源可以被访问。

命名空间

命名空间是用于区分名称的一种逻辑结构或范围，确保不同实体的名称在其范围内唯一。

三层名称空间：

  • 全局层：由最高级别的节点构成，即由根节点以及其他逻辑上靠近根节点的目录节点组成。特点是：稳定，目录表很少改变， 可以代表组织。
  • 行政层：由那些在单个组织内一起被管理的目录节点组成。行政层中的目录节点所具有的特点是代表属于同一组织或行政单位的实体组；相对稳定，但是比全局层的目录变化频繁；
  • 管理层：由经常改变的节点组成。如代表本地主机的节点及本地文件系统等，由终端用户维护；

迭代命名解析

迭代命名解析是一种逐步查询的名称解析方式。在这种方式中，**客户端（请求方）**负责主动与每一级名称服务器通信，并根据返回的部分解析结果，自己决定下一步要查询的服务器，直到解析完成找到目标资源。

客户端一直参与，时延比较大。

递归命名解析

递归命名解析是一种自动查询的名称解析方式。在这种方式中，**客户端（请求方）**只向一个命名服务器发出请求，这个服务器会代替客户端完成所有后续的查询，并最终将结果返回给客户端。

根命名服务器负载很大。

第六章 协同

时钟同步、逻辑时钟、向量时钟（必考）、互斥（集中，非集中，分布式）、选举算法

同步（进程之间步调一致）：事件之间进行协调，在时间上达成一致。

隐含意义：是信息交换，告诉其他进程当前进程的状态。

分布式系统中的协作要比单节点、多处理器系统复杂得多。

因为每个节点都有自己的时钟，很难同步（步调一致）。

时钟的内同步和外同步

精度：保证任意两个节点之间的时钟偏差在一个给定范围内。（是相对的）

准确度：节点与UTC时间的误差在一个给定范围内。

**内部同步：**保证时钟的精度；

外部同步：保证时钟的准确度；

计算时间误差

没有UTC的情况下保障时间的准确性

本质上是因为有些机器没有联网，所以并不知道UTC时间。

Berkeley算法：时间服务器（类似一个UTC时间服务器，不过是相对时间）周期性的扫描所有的节点，计算时间均值之后告诉其他机器如何调整。

happen-before关系

所有的进程并不一定在时间上达成一致，而只需要在时间发生顺序上达成一致。

实际上隐含的是因果关系。

定义如下：

  • 如果a 和 b 是同一个进程中的两个事件，并且 a 在 b 之 前到达，则有：a->b；
  • 如果 a 是消息的发送者，b 是消息的接收者，则 a->b；
  • 如果 a->b 并且 b->c 则 a->c；

逻辑时钟

为每一个事件 e 分配一个时间戳 C(e) 使其满足以下属性：

  • 如果 a 和 b 是同一个进程中的事件，并且a->b， 那么有：C(a) < C(b);
  • 如果 a 是信息 m 的发送方，并且 b 是信息的接收者，那么C(a) < C(b);

这个时间戳实际上是一个计数器，每个进程自己维护，每当发生事件就加一这样子。

算法如下：

例子如下：

要记得！时间戳并不能推出因果关系！ 只有因果关系能推出时间戳关系！所以后面引入了向量时钟

全序多播

在一个分布式系统内，每个副本更新完之后多播自己的操作，要求满足所有副本上执行的并发操作顺序是一样的。

例如像两个人同时对一个银行账户操作，一个增加1%余额，一个增加100元余额，必须保证并发操作顺序一样才能够保证账户余额一致。

Lamport逻辑时钟解决互斥访问

与全序多播算法一样，每个进程维护一个时间戳和事件队列，当进程 P 想访问临界区资源时，将自己加上自己当前的时间戳和自己想访问的临界区(<T, P, C>)，多播到其他进程并且加入到自己的事件队列中。

其他进程收到进程后，更新自己的逻辑时钟：Lc = max(Lc, T) + 1，其中 T 是请求的时间戳。并且将该请求加入到自己的本地队列，并进行排序。向优先级最高的请求的进程发出ack。

当进程 P 的事件队列中事件（<T, P, C>）优先级最高且收到了其他所有进程的 ack 消息（证明同步），P 可以访问临界区。

向量时钟

因为逻辑时钟不能从C(a) < C(b) 推导出 a->b，所以引入向量时钟来从时间戳推导出因果关系。

每个进程维护一个时钟向量（作为自己的全局视图）。

因果依赖

算法如下：

因果有序多播

与全序多播的关系：**因果有序的多播比之前提到的全序多播更弱。**尤其是如果两个消息互相没有任何关系，并不关心以哪种顺序发送给应用程序。

使用向量时钟，可以确保所有因果先于某个消息的所有消息接收后才传送这个消息。

互斥

分布式系统中的多个进程需要互斥地访问某些资源。

基于令牌的方法

仅有的一个令牌在进程之间传递。拥有令牌的进程 可以访问临界区或者将令牌传递给其他进程。

可能存在的问题：如果令牌传丢了（进程突然被kill了）或者令牌不知道传哪去了。

基于许可的集中式方法

找一个协作者来管理节点，其他节点如果想访问临界资源需要先询问协作者。

可能存在的问题：太依赖协作者了，如果协作者寄了就寄了。

非集中式算法

因此才有了下面这种分布式的协作者方法：假设每个临界资源有N个副本，每个副本都有一个协作者管理访问，一个进程 m 需要获得 N/2 个协作者的许可（过半数）即可访问临界资源，避免单一协作者crash之后崩溃。

但是存在一个问题：

Ricart & Agrawala互斥算法

要求系统中的所有事件都是完全排序的。对于每对事件， 比方说消息，哪个事件先发生都必须非常明确。

进程要访问共享资源时，构造一个消息，包括资源名、它的进程号和当前逻辑时间。然后发送给所有的其他进程

接收到消息的决策动作分为三种情况：

  • 若接收进程没有访问资源，而且也不想访问资源，向发送者返回一个OK消息；
  • 若接收者已获得对资源的访问，那么它就不答应，而是将该请求放入队列中；
  • 如果接收者想访问资源但尚未访问时，它将收到消息的时间戳与它发送到其他进程的消息的时间戳进行比较。时间戳早的那个进程获胜，如果接收到的消息的时间戳比较早，那么返回一个OK消息。如果它自己的消息的时间戳比较早，那么接收者将收到的消息放入队列中，并且不发送任何消息；

算法遇到的问题：若有单个进程crash了算法就跑不动了，因为需要全部进程发ack。并且每次想访问就进行多播，网络流量大大的增加。进程需要维护一个消息队列，不适用于进程多的情况。

互斥算法的比较

选举算法

某些算法需要一些进程作为一个协作者。问题是如何动态的选择（自动选择）这个特殊的进程。

基本假设

  • 每个进程都有一个ID。
  • 每个进程都知道其他进程的ID，但是不知道它们是否还在运行。
  • 选举算法是找到具有最大ID的活跃进程。

bully 算法

Ring 算法

第七章 一致性和复制

CAP原理、如何判断属于哪种一致性（数据、用户）、副本管理（主从副本）、一致性协议（要知道原理）

CAP 原理

CAP原则又称CAP定理，指的是在一个分布式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼得。

  • 一致性：无论用户从哪个节点访问副本，都会获得最新的副本版本。
  • 可用性：无论用户何时开始访问，都会获得响应。
  • 分区可容忍性：系统需要在部分节点通信失败的时候系统仍能运作。

三者不可兼得，简单来说：一个分布式系统在网络分区存在时，必须权衡：

  1. 是否保证一致性，但可能牺牲可用性。

    例如像保证分区可容忍性和一致性，就不能保证可用性，因为当发生某些节点通信失败的时候，为了保证副本的一致性，就不允许用户进行操作（可用性）。

  2. 是否保证可用性，但可能牺牲一致性。

    保证分区可容忍性和可用性，即在发生通信失败的时候为了响应客户的访问，可能会造成一致性的问题。

分区可容忍性是分布式系统避免不了的一个情况！！

数据一致性模型（以下讨论的都是基于数据的一致性模型）

一致性模型实际上本质是进程（客户）和数据存储的一个约定。当对数据存储的操作需要满足一定的规则，才会正常存储。特别是当多个进程发生并发读写操作，需要如何返回结果。

一致性模型解决了分布式系统中的核心问题：并发操作导致的结果不确定性。

连续一致性（一致性程度）

由以下三个部分组成：

  • **数值偏差：**不同副本之间的数值可能不同。

  • **新旧偏差：**不同副本之间的“新旧”不同。

    例如像天气预报，需要每隔四个小时就同步一次。

  • **顺序偏差：**不同副本更新操作的顺序和数量可能不同（即不同更新方法）。

只有当在本地提交之后才会多播给其他副本。

顺序偏差指的是本地没有提交的操作次数（白色区域）。

数值偏差的构成的第一部分是其他进程未提交的操作次数。

顺序一致性

以数据为中心的一致性模型。

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

只需要观察每个进程的读操作是否顺序一样即可。

因果一致性

一种弱化的顺序一致性模型。

所有的进程必须要以一样的顺序看到具有因果关系的写操作。

不同进程看到的并发写操作可以不同。

客户一致性模型

先讨论数据一致性模型的特点：读写并重的数据存储，以进程作为视角。

但是以客户为中心的一致性模型是读多写少的，即大部分都是查询操作，所以提供弱一致性（最终一致性），以副本作为视角。

最终一致性：如果副本很长一段时间没有更新，则最终每个副本将变成一致的。（允许更新过程中副本是不一致的）

适合数据一致性的场景：银行系统，需要确保每个账号的写操作顺序是一致的；库存管理系统，不允许衣服超卖了。

适合客户一致性的场景：社交媒体平台（朋友圈），允许有更新延迟；在线协作工具。

最终一致性的优缺点

定义：如果副本最近很长一段时间没有更新操作，那么所有副本都会变得趋于一致。简单来说，就是更新操作最终会传到每个副本。

优点：只要求更新操作能传播到副本即可，开销小。

缺点：如果用户访问到了还未更新的节点则会发现不一致性。

读写一致性

单调读：一旦一个进程读取了某个数据项的某个版本，接下来的所有读取操作将只会看到相同或更新的版本。

单调写：一个进程对数据项 x 执行的写操作必须在该进程对 x 执行任何后续写操作之前完成。

读写一致性：一个进程对 X 的写操作总是会被该进程后续对 X 的读操作看见。

即一个用户一定能看见自己写入的内容。

例子：更新自己的Web界面，确保自己刚刚修改的内容能够被自己重新登录Web页面看见（不是读取缓存的界面）。其他用户的更新可能一会才看到，但是自己的更新是立刻被看到的。

写读一致性

写读一致性：一个进程对 X 进行读操作后的写操作，保证发生在与 X 取值更新的值上或者与之相等的情况。

例子：刷新闻的时候看到原文章才能看到回复文章。

副本服务器放置

目的：从N 个可能的位置中找出 K 个最佳的位置。

  • 假定已放置了 k-1 个服务器，从N-k+1个服务器中选择一个最佳的服务器，与所有的客户端之间的距离最小，计算复杂度过高。即从剩下的服务器选出最好的并且距离最小的位置。
  • 假定在⼀个 D 维的⼏何空间中放置服务器，节点之间的距离反映了延迟。把整个空间划分为多个单元，选择 K 个密度最⼤的单元放置副本服务器。

服务器放置内容

  • 永久副本：即机器持久存储的数据。
  • 服务器副本：初始化数据存储的时候创建的，进程可以动态的持有副本数据，例如多客户经常访问文件A，则将文件A加入副本。
  • 客户副本：客户端初始化创建的副本，目的是减少与服务器的通信次数。

内容分发

内容分发的方式：

  1. 只传播副本更新的通知（常用于缓存）。
  2. 当副本发生更新，将整个数据都传送到另一个副本（被动复制）。
  3. 当副本发生更新，将更新的操作传给其他副本（主动复制）。

push-base：属于主动复制，服务器主动将更新推送到其他副本。适合读/更新频率高的系统使用。

pull-base：属于被动复制，客户端向服务器获取更新内容，适合于读/更新频率低的系统使用。

租用方式：在PUSH和PULL操作间切换，租期内是PUSH操作，租期外是PULL操作。

如果租期过长会增加服务器的负担，如果租期过短则可能未能有效地获得更新的副本。

一致性协议

一致性协议描述了特定的一致性实现。

持续一致性

限制了数值偏差

设定 Val(w) > 0，其中 Val(w)是更新后和更新前的差值绝对值。

假设有N个副本，副本之间会传递更新操作给其他副本，TW[i, j]意味着所有副本 j 的写操作传到副本 i 的总和。

可判断出，目前最新值 v(t) 的计算公式为 初始值 + 所有的TW[k, k]。

单个副本 i 内的值 vi 计算公式为 初始值 + 所有的TW[i, k]。

需要限制数值偏差 v(t) - vi 小于等于一个给定的 δ。

限制新旧偏差

要记得那个例子，天气系统每隔四个小时就需要更新一次。

服务器S_k保持实时向量时钟RVC_k，其中RVC_k[i] = T(i) 为 到时间T(i)时，S_k看到了已提交给S_i的所有写操作；

  • 即T(i)时，S_k 收到了来自 S_i 传播的写操作。

如果T(k) - RVC_k[i] 大于某个设定的值，则开始拉入副本 S_i 晚于 RVC_k[i] 执行的写操作。

基于主备份的协议

分为远程写协议和本地写协议。

远程写协议

从名字看，实现数据项X的更新是在远端的主备份上实现的。

所有读操作和写操作都转发给单个固定的远程（主）服务器：要在数据项x上执行一个写操作的进程，会把该操作转发给x的主服务器。该主服务器在其x 的本地副本上执行更新操作，随后把该更新转发给备份服务器。

写操作：经过的比较长，W1-W2-W3-W4-W5

可靠性很好，但是性能不高。

实现了顺序一致性，完成了阻塞操作。

本地写协议

主副本在要执行写操作的进程之间迁移：某个进程对x进行写操作，则定位x的主副本，然后将x转移到自己的位置上。 W3处就已经返回了。

在断网之前将数据保存在本地，然后修改是对本地操作的，等重新联网后向原来的主备份同步。

基于团队的复制写协议

复制写协议：将各更新操作主动发给各个副本上的进程。

跟著主备份协议的区别：可以多个副本同时写（基于全序多播）。

基于团队的协议，读或者写需要通过团队的统一，为了满足一致性，需要有以下两个条件成立：

  1. 一定要有进程既是写团体也是读团体（避免读写冲突）

    这样假设访问的话就可以访问即写又读的副本了。

  2. 写团体要占大多数（避免写写冲突）

第八章 容错

故障类型（三个不同的概念），可靠性，可用性，如何保障，可靠多播，分布式两段提交，如何恢复（前向后向），检查点开销大所以用日志，两阶段具体了解。

可依赖性

定义：软件组件用于服务客户，但是软件组件可能用到其他组件的服务，即组件依赖于其他组件。

相关的四个需求：

  • 可靠性
  • 可用性
  • 安全性
  • 可维护性

可靠性和可用性的区别

可靠性指的是连续工作的概率（即不被打断）。

可用性指的是工作时间跟总时间的比。

可靠性高不一定可用性高：一个系统平时很少出错，但是一出错恢复时间特别长。

可用性高不一定可靠性高：系统经常出错，但是恢复时间十分短。

分布式系统中的bug

失效（Failure）、错误（Error）、故障（fault）。

按照失效程度：失效 > 错误 > 故障。

错误是部分组件失效，失效是整个组件失效。

故障（fault）是失效 (Failure) 的原因。

五个失效模型

崩溃性故障

  • 服务器停机，但在停机之前工作正常

忽略性故障

  • 服务器不能响应到来的请求
  • 服务器不能接受到来地消息
  • 服务器不能发送消息

时间性故障

  • 服务器的响应在指定的时间间隔之外

响应故障

  • 服务器的响应不正确
  • 响应地值错误
  • 服务器偏离了正确的控制流

任意性故障

  • 服务器可能在随意的时间产生随意的响应

冗余掩盖故障

故障透明，用户并不知道。

冗余类型有以下三种：

  • 信息冗余：在信息中增加额外的位使得错乱的位回复正常。
  • 时间冗余：如果系统出错，可以再次执行这个事务。
  • 物理冗余：添加额外的装备或进程，使得系统作为一个整体来容忍部分组件的失效。

分布式系统检测失效

因为有忽略性失效，所以怎么检测变得困难。

  • 如果 P 没有在规定的时间 t 内收到来自 Q 的心跳信息：P 怀疑 Q 失效；
  • 如果 Q 稍后发出消息：P 停止怀疑 Q，P 增加 timeout 的时间；
  • 如果 Q 确实宕机，P 会一直怀疑 Q；

可靠的通信方式

可靠的RPC过程

  • 两个简单的方案：

    定位不到服务器：像客户端报错。

    请求丢失：再次发送请求。

Client-server失效场景及恢复方法

  • 最多一次和最少一次语义：

    最多执行一次写操作。

    最少执行一次读操作。

完全透明的服务器恢复是不可能的，举例说明： 假设请求服务器更新文档：

M：发送完成信息（请求的发送ACK）

P：完成文档处理

C：crash

有6种可能的顺序：

可以发现，完全透明的服务器恢复是不可能的。

可靠的RPC过程

  • 丢失应答信息

    客户端不能判断是服务器宕机还是丢失响应。

    将服务器设计成幂相等的系统。

  • 客户端崩溃：

    • 服务器在⼯作且持有资源，但没有客户端需要结果。

    • 解决⽅案：

      孤⼉消灭———— 客户端恢复时重启服务器或丢弃之前的计算；

      再⽣—— 把时间分为顺序编号的时期，客户端恢复后向所有的服务器⼴播新时期的开始，由服务器杀死与客户端相关的「孤⼉」；

      优雅再⽣；

      到期；

可靠多播

消息发送和接收按照发送者发送的顺序进行。

问题：如果存在N的接收方，会导致大量返回 N 个确认信息，如果数量 很大，发送方会被反馈消息淹没，形成反馈拥塞。

解决方案： 接收方不对消息进行反馈，而只是在消息丢失时才返回一个反馈消息。

存在的问题是：需要缓存大量的陈旧的信息。

分布式两阶段提交协议

目的：一个操作要么被进程组中的每一个成员执行，要么一个都不执行；

可以用刚刚提到的可靠多播进行实现。

两阶段提交协议：

  1. 协作者发起投票请求。
  2. 参与者收到投票请求，并根据自身情况返回 abort 或者 commit。
  3. 协作者收集请求，如果没有收到 abort，则发送 global commit；否则，发送 global abort.
  4. 参与者根据收到的全局消息执行对应的动作。、

参与者失效情况：

  1. init：此时还未收到投票信息，不会有任何问题。

  2. ready：此时已经投完票了，恢复后通过日志查看协作者的决策。或者查看其他参与者的动作也可以。

    若此时恢复之后发现参与者都被阻塞在ready状态，代表协作者被阻塞了。

  3. abort：此时是幂等操作，再执行一次abort即可。

  4. commit：此时是幂等操作，再执行一次commit即可。

协作者失效情况：

分布式系统失效恢复的主要方式

前向恢复：将系统状态设置为将来的某个状态。

后向恢复：将系统状态设置为过去某个状态，需要周期性记录检查点，其实就是找恢复线。

分布式系统恢复更困难：需要找到全局一致的检查点。

恢复线

假定每一个进程都会周期性记录检查点，最近一次的全局一致的检查点就是恢复线路。

在上图中，（c, d）就是一个恢复线。

检查点方法

保存进程的运行状态，存储到内存或者磁盘，用于对进程进行迁移或者故障恢复。

例如在数据库中，检查点是将那些未写入磁盘（还在内存）的写操作执行结果写入磁盘。

独立的检查点方法

每个进程的检查点是以一种不协调的方式来按时记录本地状态，这种分布式特性使得找到一个恢复线路非常困难，可能会导致多米诺效应。

最保守的恢复状态是初始状态！

协调的检查点方法

所有进程都同步地把他们的状态写道本地稳定存储中。优点：保存的状态自动保持全局一致，避免导致多米诺效应。

  1. 协调者多播checkpoint request消息。
  2. 参与者接收到消息，打检查点，停止发送应用消息，向协作者报告他打了检查点。
  3. 所有检查点的报告都被协作者确认，协作者广播一个checkpoint done消息以允许所有进程继续。

日志

检查点的代价过高，通过“重放（replay）”的方式达到一个全局一致的状态而不需要从持久存储中恢复该状态=>在日志中持久化消息。

第九章 Paxos

三种paxos，运用场景不一样，paxos工作过程，raft过程（跟paxos区别），PBFT知道用来干嘛

共识

定义：使所有非故障进程就由谁来执行命令达成一致，而且在有限的步骤内就达成一致。

前提 ：在一个容错组里面，每一个非故障进程执行的命令以及执行的顺序与其他非故障进程相同

共识协议的思想就是某些节点可能失效的情况下剩余的节点能达成共识。

共识协议分类

失效容错协议（Fault-Tolerant Protocols）

  • 特点：能够处理节点失效（如崩溃、掉线）情况。

  • 准确检测失效：泛洪

  • 最终检测到失效：Pasox Raft

  • 应用：分布式数据库、分布式文件系统、服务协调系统

拜占庭容错协议（Byzantine Fault Tolerant Protocols, BFT）

  • 特点：能够处理节点的任意故障行为，包括恶意攻击、数据篡改等。
  • PBFT
  • 应用：区块链系统、金融交易系统、高安全性分布式系统

Paxos

能够在部分节点发生故障的情况下保持共识。

[Paxos 协议详解：分布式系统一致性的基石_paxos协议-CSDN博客](https://blog.csdn.net/LearnerDL/article/details/142602963#:~:text=Paxos 是一个能够在分布式系统中帮助我们解决一致性问题的协议。 它可以确保多个节点（计算机）在不可靠的网络环境中达成一致，即使有些节点宕机或网络延迟，也能保证整个系统最终达到相同的决定。 Paxos 协议是由计算机科学家,莱斯利·兰伯特 （Leslie Lamport）在 1990 年代提出的，它的目标是在不可靠的网络环境中让多个分布式节点达成一致。)

分为两个阶段：预提交阶段和提交阶段。

预提交阶段：

阶段2：

以下是例子：

特性：

safety安全性（Paxos满足）：

  • 只有一个值被选定。

    整个系统最终只会确定一个值。（透过vrnd实现）

  • 两个正常的结点最终不会选择不同的值

    通过大多数投票实现。

  • 一个结点最多选一次

    每个提议者在某个时间只能持有一个提议编号，确保它不会同时发起多个不同值的提议。

liveness活性（Paxos没有满足！）：

  • 每一个正常的节点最终都会选择一个值。

  • 可能会发生活锁，即两个proposal轮流发起提议。

Paxos的主要变种：

Raft

解决非拜占庭式失效。

Paxos问题：

  • 效率低，写入一个值要2次RPC。
  • 无法解决livenness。
  • 不好理解。

Raft 的核心思想是通过领导者选举来简化一致性过程。与 Paxos 不同的是，Raft 一开始就明确选出一个 领导者（Leader），所有提案都由这个领导者发起。具体工作流程如下：

  • 领导者选举：系统中的节点会通过投票选举出一个领导者。这个领导者会负责处理所有的提案。
  • 日志复制：领导者接收客户端的提案后，会将提案添加到它的日志中，然后向其他节点（称为跟随者，Followers）发送这个提案，要求它们复制日志。
  • 日志提交：当领导者收到大多数跟随者的确认后，提案被认为提交成功，整个系统达成一致。
    Raft 的优点：

简单易懂：相比 Paxos，Raft 更容易理解，尤其是通过明确的领导者角色简化了提案过程。

统一领导者：Raft 避免了 Paxos 中多个提议者竞争导致的复杂性，提升了系统的性能。

PBFT

解决拜占庭式故障的协议。

第十章 分布式文件系统

分布式文件系统结构，分布式文件系统就是分布式系统的实例（有很多分布式的问题），NFS，知道GFS的特点。

NFS文件系统的主要特点

是客户-服务器结构。

  • 每个文件服务器都提供其本地文件系统的一个标准化视图。
  • 每个NFS都支持相同的模型。（有相同的接口）
  • 底层模型是远程文件访问模型。

NFS的架构

使用VFS实现，VFS是不同文件系统接口的标准， 现代OS都提供VFS。VFS提供了系统结构，屏蔽了访问本地和远程文件的差异性。

NFS像任何UNIX文件系统一样支持硬链接和符号链接；

GFS文件系统的特点

是基于集群的分布式文件系统。

将整个文件拆成多个块，将这些块分布、复制在不同的块服务器中。

现在描述Google File System的特点：

  • 主服务器只维护一张（filename，chunk server）的映射表（最小化IO），然后使用日志来记录对数据的操作。
  • 大量的实际工作都是块服务器完成的，主服务器没有参与循环（避免单节点依赖性能差）
  • 上述两个特点使得GFS的主服务器不会称为性能瓶颈，反而一个主服务器可以控制上百个块服务器，扩展性更好。

什么是文件共享语义，主要的语义模型包括哪些？简要描述其特征。

当需要处理分布式系统的时候，需要确定好并行读写的操作顺序和期望的语义（其实就是定义一个并行的规则，满足一致性）。

拜占庭容错的基本思想和基本过程

基本思想是通过构造有限状态机的集合来部署主动复制， 并且这个集合中具有无故障的进程以相同的顺序执行操作。

简单解决方案：指定一个协调器，它通过简单地给每个请求附加一个序号来序列化所有的操作。

问题转嫁到协调器身上。

  1. 请求阶段：客户端向主节点发送请求。
  2. 预准备阶段：主节点将请求广播给所有副本节点。
  3. 准备阶段：副本节点收到请求后，进行验证并向其他节点发送准备消息。
  4. 提交阶段：副本节点收集到足够的准备消息后，向其他节点发送提交消息。

为了 k 个服务器的拜占庭容错，服务器组必须包含至少 3k+1 个进程；

用一个副官模型来理解：

  • 假设只有 3 个人，A、B、C，三人中如果其中一个是叛徒。当 A 发出进攻命令时，B 如果是叛徒，他可能告诉 C，他收到的是「撤退」的命令。这时 C 收到一个「进攻」，一个「撤退「，于是 C 被信息迷惑，而无所适从。
  • 如果 A 是叛徒。他告诉 B「进攻」，告诉 C「撤退」。当 C 告诉 B，他收到「撤退」命令时，B 由于收到了司令「进攻」的命令，而无法与 C 保持一致。

因此在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于 1/3，拜占庭问题便不可解。

P2P系统中用于提高系统可用性的方案？以及方案的主要特点。

问题：P2P系统的节点的不可用性非常高，简单的复制文件已不能保证可用性。

冗余性方案：

  1. 复制：通过放置多个副本提高数据的冗余度从而提高可用性。
  2. 擦除编码（erasure coding）：通过把一个文件分成m块，随后把它记录到n大于m块中，任何 m个编码块的集合都足以用于重构造原始文件。冗余性因子： n/m。

在分布式文件系统中主要关注的问题包括哪些？并分别给出一些解决问题的方案

同步解决方案

  • 立即将缓存文件的所有改动传播回服务器，简单但是效率低；（对所有进程即时可见）
  • 在文件关闭之前，所有改动对其他进程都是不可见的即会话语义
  • 所有文件都是不可改变的，文件上的操作只有 create 和 read
  • 使用原子事务处理共享文件

命名

对于一个大型分布式系统，当需要提供对文件的共享访问时，至少要有一个全局名称空间。

全局名称空间服务( GNS); 把现有文件系统集成进单个全局名称空间中，只使用用户级解决方案

一致性

安全性

第十一章 大数据+分布式机器学习

MAP-Reduce 原理，优势；分布式机器学习，了解原理。

MAP-REDUCE

MapReduce 是一种编程模型和计算框架，主要用于处理大规模数据集。

流程如下：

  1. Map 阶段：将输入数据分成小块，并并行处理，生成一组中间的键值对。
  2. Shuffle 和 Sort 阶段：对 Map 阶段的输出进行分组和排序，确保相同的键被发送到同一个 Reduce 任务中。
  3. Reduce 阶段：处理相同键的所有值，通常进行汇总、聚合等操作，输出最终的结果。

特点：

  • 大规模的计算被分割成很多小的任务

    支持分布式运算。

  • 使用磁盘存储中间结果

    因为要处理很大规模的数据，所以没有受到内存限制。

  • 自动并行

    这个框架很适合并行计算。

  • 自动容错

    原本就是分布式的了，如果 Map 或 Reduce 任务失败，MapReduce 框架会将任务重新分配到其他节点上执行。

  • 可扩展性好

    只需要增加更多的节点提高计算能力。

  • 入门门槛低

    不需要实现底层逻辑，系统出错了也不用理。

缺点：

  • 没有办法实时计算
  • 输入需要是静态的，不能是动态的

与传统的高性能计算相比，MapReduce的优势是什么？

简化的编程模型（Simplicity of Programming Model）：
  • 传统 HPC：传统的高性能计算往往需要复杂的并行编程技术，如 MPI（消息传递接口）、OpenMP（开放多处理）等。开发人员需要手动管理数据的并行化、负载平衡、通信等方面，要求较高的计算机科学知识。
  • MapReduce：MapReduce 提供了一个非常简单和抽象的编程模型，开发者只需要实现两个函数（Map 和 Reduce）。这些函数通过定义输入数据的处理方式和输出方式，完成了所有复杂的并行计算和分布式操作。MapReduce 的高层抽象隐藏了底层的并行化和分布式管理，极大简化了开发过程。
更高的可扩展性（Scalability）：
  • 传统 HPC：高性能计算通常依赖于大规模的单机系统（如超级计算机或集群），这些系统依赖于强大的硬件和高效的计算架构。然而，传统 HPC 系统的扩展性受限于硬件的投入和成本，通常只能在单一集群或数据中心中扩展。
  • MapReduce：MapReduce 设计上就是为大规模分布式环境量身定制的，它能够通过增加计算节点来水平扩展，不需要特别昂贵的硬件，只需要普通的计算机节点即可。MapReduce 使得计算可以从几十台机器扩展到几千台机器，适用于大数据量的分布式处理。

分布式机器学习原理

分为服务器一方（ 主要是update 参数）和工作一方（主要是计算梯度 GPU）

基本流程如下：

  1. 工作节点拉取工作集：工作节点从服务器拉取当前的模型参数，并开始在本地的数据集上进行训练。
  2. 迭代计算：工作节点执行模型的前向传播和反向传播，计算梯度，完成一次训练迭代。
  3. 停止梯度计算：当满足某些停止条件时（如达到预定的训练轮数或模型收敛），停止梯度计算。
  4. 工作节点计算梯度：工作节点在自己的数据子集上进行计算，得出梯度信息。
  5. 工作节点推送梯度：工作节点将计算得到的梯度信息发送回服务器，以便进行模型更新。
  6. 更新模型：服务器根据收到的梯度信息更新全局模型参数。
  7. 工作节点拉取更新后的模型：工作节点从服务器拉取更新后的模型参数，继续进行下一轮的训练。
分布式笔记
https://tobytam23.github.io/2025/01/25/分布式笔记/
Author
tanzhuoheng
Posted on
January 25, 2025
Licensed under