《分布式计算》总结


一、 分布式计算概述

1. 分布式系统定义

分布式系统是由一组通过网络进行通信,为了完成共同的任务而协调工作的计算机节点组成的系统

1.1 消息传递模型(Shared-Nothing)

  • 节点之间通过消息传递进行通信
  • 内部运算速度快,但通信速度慢

1.2 分布式计算与并行计算

  • 分布式计算是并行计算的一种特殊形式
  • 并行计算
    • 指令并行
    • CPU多核并行:多线程编程
    • 多CPU并行(一致性内存共享):多进程编程
    • 多CPU并行(非一致性内存共享):分布式计算
    • 基于GPU的并行计算
    • 多机并行计算

1.3 分布式与云计算

  • 云计算

    • 用户角度:是一种服务/应用/交付模式,方便用户随时随地通过网络访问应用程序、存储数据,不是一种技术
  • 与分布式计算的关系
    • 云计算是目标,分布式计算是手段
    • 分布式计算是实现云计算的核心技术之一(还有虚拟化技术,网络通信技术,安全技术等)

2. 构建分布式系统的收益

  • 提高计算能力
  • 提高存储能力
  • 提高网络吞吐能力
  • 提高可靠性
  • 提高可扩展性
  • 提高安全性
  • 实现资源共享
  • 实现跨时空协同服务

3. 分布式系统衡量指标

  • 业务层性能
    • 时间复杂度
    • 空间复杂度
    • 通信复杂度
  • 可扩展性:系统能够适应业务量的增长
  • 容错性:系统在部分节点失效时,仍能正常工作
  • 并发性:系统能同时处理多个请求
  • 透明性:用户感知不到系统的分布式特性
  • 开放性:节点可以动态加入或退出系统
  • 安全性:系统能抵御各种攻击
  • 可观测/可维护性:系统能够监控自身的运行状态,及时发现故障并修复

简记:扩容,容错,并发,透明,开放,安全,可观测

4. 设计分布式系统的挑战

与性能衡量指标 类似

5. 分布式计算任务的分类

5.1 OLTP(联机事务处理)

实时处理大量的短小的事务请求,每个事务请求的处理时间很短,通常是几毫秒到几秒钟

5.2 OLAP(联机分析处理)

对大量的历史数据进行分析,通常是对大量数据进行聚合计算,每个计算任务的处理时间很长,通常是几分钟到几小时

5.3 流式计算

对大量的实时数据进行分析,通常是对数据进行过滤、聚合、统计等操作,每个计算任务的处理时间很短,通常是几毫秒到几秒钟

6. 分布式系统架构模式

6.1 客户端-服务器模式

负载均衡技术
  1. 如何架构

    • 通过DNS轮询
    • 通过反向代理
    • 通过负载均衡器
  2. 带来的收益

    • 提高系统的可扩展性,弹性增减节点
    • 提高系统的可靠性
    • 提高系统的性能
  3. 常用的负载均衡算法及优劣
    • 轮询:简单,均衡,但不考虑节点的负载情况
    • 随机:简单,均衡,但不考虑节点的负载情况
    • 最少连接:考虑节点的负载情况,但不考虑节点的性能
    • 最少响应时间:考虑节点的负载情况,考虑节点的性能,但不考虑节点的可用性
    • 哈希:考虑节点的负载情况,考虑节点的性能,考虑节点的可用性,但不支持动态增减节点
    • 一致性哈希:考虑节点的负载情况,考虑节点的性能,考虑节点的可用性,支持动态增减节点

6.2 主从模式

主从模式的概念
  • 主节点

    负责处理客户端的请求,维护系统的状态

  • 从节点

    负责处理主节点分配的任务,不维护系统的状态

主从模式的优缺点
  • 优点
    • 提高系统的可扩展性
    • 提高系统的可靠性
    • 提高系统的性能
  • 缺点
    • 主节点成为瓶颈
    • 从节点的状态不一致

6.3 总线模式

总线模式的概念
  • 不同节点通过总线进行通信
  • 消息发送与接受者解耦
  • 异步
  • 分工

6.4 对等模式

对等模式的概念
  • 系统中的所有计算节点任务分工都是对等的
  • 完全相同的软件在不同的节点上运行,只是初始化参数不同
对等模式的优缺点
  • 优点

    • 不会出现单点故障
    • 无需维护系统的状态
  • 缺点
    • 效率低

7. 分布式中间件的概念

7.1 中间件在计算机系统中的位置

中间件是介于操作系统和应用程序之间的软件,它为应用程序提供服务,为操作系统提供接口

7.2 中间件的作用

  • 为开发者提供高层的抽象接口
  • 提高互操作性和可移植性
  • 提供分布式系统的基础设施

7.3 中间件的基本表现形式

  • 独立的后台进程
  • 语言编译/解释器的一部分
  • 函数库

二、分布式系统节点通信技术

1. 基于Socket的通信技术

1.1 Socket的概念

  • Socket是一种通信机制,它允许不同节点上的应用程序通过网络进行通信
  • 是传输层和网络层提供给应用层的接口

1.2 基于流式Socket(TCP)

  1. 建立连接(三次握手)
    • 客户端向服务器发送连接请求
    • 服务器向客户端发送连接确认
    • 客户端向服务器发送连接确认
  2. 发送请求
    • 客户端向服务器发送请求
  3. 返回响应
    • 服务器向客户端发送响应
  4. 关闭连接

1.3 基于数据报Socket(UDP)

  1. 发送请求
    • 客户端向服务器发送请求
  2. 返回响应
    • 服务器向客户端发送响应

与TCP的区别:没有建立连接的过程,不可靠,不保证数据的顺序

1.4 并发服务技术

  • 多线程——线程池
    • 优点:线程复用,减少线程创建和销毁的开销
  • 多路复用(事件驱动技术)
    • 优点:单线程,减少线程切换的开销,适用于并发连接数少,连接时间短,IO密集的场景

2. 远程过程调用RPC(上层通信技术)

凤凰架构 RPC是一种通信机制,它允许不同节点上的应用程序通过网络进行通信,它是Socket的高级封装,使应用程序可以像调用本地函数一样调用远程函数

2.1 RPC的基本原理

  1. 序列化/反序列化
    • 序列化:将对象转换为字节序列
    • 反序列化:将字节序列转换为对象
  2. 插桩/代理(stub/skeleton)
    • 插桩:客户端调用本地函数,插桩将函数调用转换为网络消息
    • 代理:服务器端接收网络消息,代理将网络消息转换为函数调用
  3. 实现RPC语义的应用层协议
  4. 负责远程对象的集中注册与管理
点对点通信的缺点
  • 关系复杂,耦合度高
  • 可扩展性差

2.2 RPC中间件的作用——注册中心的作用

  • 服务启动时,将服务的地址注册到注册中心,客户端从注册中心获取服务地址,实现服务发现
  • 优点: 动态增减节点,负载均衡,容错

2.3 接口描述语言IDL

  • 作用:定义接口,实现语言无关,平台无关,网络协议无关

2.4 RPC调用模式

  • 同步调用

    • 客户端调用远程函数,等待远程函数返回结果
  • 异步调用
    • 客户端调用远程函数,不等待远程函数返回结果,继续执行后续操作
    • 远程函数执行完毕后,通知客户端

3. 基于HTTP的通信技术

  • Web Service

    • 优点:跨平台,跨语言,跨网络
    • 缺点:效率低,不支持异步调用
  • RESTful
    • 优点:效率高,支持异步调用
    • 缺点:不支持跨语言,跨网络

4. 基于消息队列(MOM)中间件的通信技术

  1. 优势

    • 异步通信,提高系统的并发性
    • 解耦,提高系统的可扩展性
    • 削峰填谷,提高系统的可靠性
  2. 通信模式

    1. 消息队列
      • 一对一(一个队列,一个消费者)
      • 一对多(一个队列,多个消费者)
    2. 发布/订阅
      • 一对多,广播
  3. 投递模式

    • At Most Once

      • 消息可能会丢失,但不会重复投递
    • At Least Once

      • 消息不会丢失,但可能会重复投递
    • Exactly Once
      • 消息不会丢失,不会重复投递
  4. 缓存模式
    • 持久化
      • 消息持久化到磁盘
    • 非持久化
      • 消息不持久化到磁盘

三、 模型问题

1. 设计分布式系统的挑战

1.1 不可靠的网络——信道故障

  • 传输延迟的不确定性
  • 网络断裂
  • 丢包
  • 乱序

1.2 不可靠的节点

  • 部分节点失效
  • 单点失效

1.3 不可靠的时钟

2.分布式系统的模型

2.1 节点故障模型

  • fail-stop模型

    • 节点失效后,不会再次恢复
  • fail-stop-restart模型

    • 节点失效后,会再次恢复
  • byzantine模型
    • 节点失效后,会再次恢复,但是恢复后的节点可能会发生任意行为

2.2 链路模型

  • 任意链路

    • 丢包、重复包、内容篡改、伪造、乱序、传输延迟抖动
    • 有主动攻击者存在的情况
  • 一般损失链路

    • 只存在丢包、重复包、乱序和传输延迟抖动
    • 链路会发生断裂(Partition),但断裂持续时间是有限的
  • 可靠链路

    • 发送者发出的每个消息都可以被正确接收
    • 但是:
    • 存在传输延迟抖动
    • 接收到消息的顺序可能和发送顺序不一致
  • 可靠FIFO链路

    • 发出的每个消息都可以被正确接收并且不会乱序
  • 如何基于弱假设链路实现强假设链路
    • 如何基于“任意链路” 实现“一般损失链路”?
    • 利用纠错码、HASH函数、消息认证码、加密算法等手段;
    • 利用SSL/TLS/HTTPS协议
    • 如何基于“一般损失链路” 实现“可靠链路”?
    • 发送者持续地尝试重传数据包,直到收到ACK;
    • 利用数据包序列号等手段实现去除重复数据包
    • 如何基于“可靠链路”实现“可靠FIFO链路”?
    • 利用数据包序列号,对收到的数据包进行排序,然后按序列号由小到大依次向应用层投递

2.3 时间同步模式

  • 同步模式

    • 消息传输延迟不超过已知的上限
    • 节点以已知速度执行算法
  • 异步模式

    • 消息传输延迟没有上限
    • 节点在运行期间可能会暂停任意长的时间
  • 部分同步模式
    • 系统大部分时间工作在同步模式;
    • 但在有限时间段(该时间段长度不可预知)内工作在异步 模式;

四、 时钟问题

1. 物理时钟

1.1 单调钟的概念

  • 按照一定频率持续自增;
  • 其绝对值无意义,相对值表示延时或时间差;
  • Java:System.nanoTime()

1.2 墙钟的概念

  • 和日常生活中的日历、天文事件对应的时钟
  • 世界墙钟标准:协调世界时(Coordinated Universal Time)
  • 可能会发生倒流现象(NTP时钟校正、闰秒)
  • System.currentTimeMillis() (1970-1-1 午夜 0点以来的秒数

1.3 NTP实现时钟同步的原理

  • Cristian算法

    • 客户端发送请求包,以其本地时钟T_1为时间戳

    • 服务器在收到请求T_2及其本地时钟

    • 服务器发送一个带有其本地时钟T_3T_2的包

    • 客户端在本地对其接收服务器响应的时间戳T4T_4

    • 目标:将时钟校正为

    T_3 + ?_{resp}

    ?_{resp} = \frac{(T_2 - T_1) + (T_3 - T_4)}{2}

2. 逻辑时钟

2.1 Lamport时钟

  1. Happen-Before关系

    • 如果事件ab是同一个节点(单进程/线程)中的两个事件,事件a发生在事件b之前,那么a \to b

    • 如果a事件是 “节点P_1发送消息mP_2”,b事件是“节点P_2接收消息m”,那么a \to b

    • 如果a \to bb \to c,那么a \to c(传递性)

    • 如果a ↛ bb ↛ a,那么ab是并发事件
  2. Lamport时钟

    • 每个节点维护一个逻辑时钟,初始值为C_i
    • 每个节点在执行一个事件生(消息产生、消息发送、消息接收都是事件)时,将逻辑时钟加1
    • 每个节点在发送消息时,将逻辑时钟加1,并将当前逻辑时钟作为消息的时间戳
    • 每个节点在接收消息时,将逻辑时钟更新为“当前逻辑时钟”和“消息时间戳”中较大的值加1

2.2 向量逻辑时钟

  1. 基本算法
  • 设分布式系统包含 n 个节点N_1,N_2,...,N_n,节点N_i的向量时钟T形式为:

    T = (T_1,T_2,...,T_n)

    其中T[i] = T_j表示节点N_i的逻辑时钟,T[j]表示N_i所知道的关于节点N_j的最大标量时钟值

  • 向量时钟的更新

    • 节点N_i在执行一个事件时,将自己的标量时钟自增;
    • 节点N_i在发送消息时,将当前向量时钟T作为消息的时间戳;
    • 当收到其它节点发送的消息<m,T_m>时,节点N_i将自己的向量时钟T更新为: T[j] = max(T[j],T_m[j]) T[i] = T[i] + 1
  1. 优缺点
  • 优点

    • 可以检测出因果关系
  • 缺点
    • 向量时钟的长度随节点数目增加而增加,不适合大规模系统

2.3 向量时钟的应用

  1. 全序广播

  2. 因果排序广播

五、 分布式存储

1. 复制(多副本)技术

1.1 多副本复制带来的收益和挑战

  • 收益
    • 提供冗余
    • 应对节点失效
    • 提高吞吐率
    • 改善访问性能
  • 挑战
    • 硬件成本
    • 保持一致性困难

1.2 主从技术复制

  • 单主复制

    一个领导者,多个从属者

    优点:简单

    缺点:主节点成为瓶颈

    • 同步复制: 领导者将每个写操作发送给所有从属者,直到所有从属者都确认写操作后,领导者才能确认写操作
    • 异步复制: 领导者将每个写操作发送给所有从属者,但不等待从属者确认写操作,而是立即确认写操作
    • 链式复制: 从属者将写操作发送给其他从属者,而不是领导者,形成一个链式结构
    • 混合复制: 部分从属者采用同步复制,部分从属者采用异步复制
  • 多主复制

  • 无主复制

2. 分布式系统一致性模型

2.1 一致性模型的概念

多个客户端同时访问分布式系统,系统应该保证客户端看到的数据是一致的

2.2 强一致性(线性一致性)

分布式系统对外提供的服务,与单机系统对外提供的服务一致,即客户端看到的对系统的操作是与物理世界真实发生的顺序一致的

2.3 最终一致性和弱一致性

  • 最终一致性

    • 系统保证在没有新的更新操作时,系统最终会达到一致状态
    • 适用于读操作远远多于写操作的场景
  • 弱一致性
    • 系统不保证在没有新的更新操作时,系统最终会达到一致状态
    • 适用于读操作远远多于写操作的场景

2.4 CAP定理

CAP定理指出,对于一个分布式系统来说,不可能同时满足以下三点,最多只能同时满足两点

  • 一致性(Consistency)

    • 所有节点在同一时间具有相同的数据
  • 可用性(Availability)

    • 保证每个请求不管成功或者失败都有响应
  • 割舍分区容错性(Partition tolerance)
    • 系统中任意信息的丢失或失败不会影响系统的继续运作

3. 分布式共识协议

3.1 共识协议的作用

利用共识协议,分布式系统可以在不同节点之间达成一致,从而保证分布式系统的一致性

  • 多副本主从复制
  • 异步通信
  • 容错

3.2 复制状态机的概念

  • 状态机

状态机是一个抽象的数学模型,它包含一组状态和一组操作,每个操作都将状态从一个状态转换为另一个状态

  • 目标:让所有节点的状态机保持一致
  • 用处:某节点的状态机失效,可立即切换到另一个节点的状态机
  • 实现:
    • 每个节点维护一个日志,日志中记录了所有状态机执行的操作
    • 利用共识协议,让所有节点的日志保持一致

3.3 共识协议和分布式一致性的关系

  • 共识协议是分布式一致性的基础
  • 一致性是对用户的承诺
  • 共识协议是实现一致性的手段

3.4 按容错模型分类

  1. 失效停止模式共识协议

    最多允许f = (n-1)/2个节点失效

    • Paxos
    • Raft

      • 过程:

        1. Leader接收客户端请求,存入日志
        2. 将新增日志复制给其他节点
        3. 确认日志复制成功,提交日志,执行日志中的命令
      • Leader选举过程:
        1. Leader失效
        2. Follower发现Leader失效,发起选举
        3. 超过半数节点投票给某个Follower,该Follower成为新的Leader
        4. 修改朝代号,通知其他节点
    • Zab
  2. 拜占庭模式共识协议

    原理:通过多数派原则,保证系统的一致性

    • PBFT
    • VFT

4. 分区(分片)技术

4.1 分区带来的收益和挑战

  • 收益

    • 提高系统的可扩展性
    • 提高系统的可靠性
    • 提高系统的性能
  • 挑战
    • 数据分布不均匀
    • 跨分区查询
    • 事务处理

4.2 分区技术的分类

  1. 按主键范围分区

    将主键的值按范围划分到不同的分区

    • 均匀分区

      将主键的值按范围均匀划分到不同的分区

      • 优点:容易实现点查询,范围查询,排序等操作
      • 缺点:不适合数据分布不均匀的场景
    • 不均匀分区

      将主键的值按范围不均匀划分到不同的分区

      • 优点:可处理数据偏斜,热点查询
      • 缺点:需要全局索引,导致查询多了一次网络开销
  2. 哈希分区

    确定性,随机性,无碰撞性

    • 简单哈希分区

      将主键的值通过哈希函数计算,得到哈希值,再通过哈希值对分区数取模,得到分区号

    • 一致性哈希分区

      将主键的值通过哈希函数计算,得到哈希值,再通过哈希值对分区数取模,得到分区号

    • 优点:

      • 可处理数据分布不均匀,热点查询;
      • 不用全局索引,减少网络开销
      • 不用事先知道数据分布情况
    • 缺点:

      • 效率低,需要多次哈希计算
      • 在分区数变化时,数据迁移量大
      • 物理储存少时容易出现偏斜和热点问题

4.3 分区技术带来的挑战

  • 分布式事务概念(ACID)

    • 原子性(Atomicity)

    事务是一个不可分割的工作单位,事务中的操作要么全部成功,要么全部失败

    • 一致性(Consistency)

    事务执行前后,系统的状态保持一致

    • 隔离性(Isolation)

    事务的执行不会相互影响

    • 持久性(Durability)

    事务执行成功后,对系统的影响是永久的

4.4 分区和复制组和使用

  • 节点内有多个分区,每个分区有多个副本
  • 每个节点充当某些分区的领导者,其他分区充当从属者

4.5 HDFS分布式文件系统

  1. HDFS系统架构

    • NameNode(主节点)

      负责管理文件系统的命名空间,维护文件系统的元数据

    • DataNode(从节点)

      负责管理文件系统的数据块,维护文件系统的数据块副本

  2. HDFS工作机制

    • 读操作
      • 客户端向NameNode发送读请求,
      • NameNode返回数据块所在的DataNode列表
      • 客户端直接从最近的DataNode读取数据
    • 写操作

      • 客户端向NameNode发送写请求
      • NameNode根据负载均衡策略,返回数据块所在的DataNode列表,共3个
      • 客户端将3个数据节点构成一个流水线,将第一个数据块写入流水线
      • 再向NameNode获取下一个数据块对应的3个DataNode列表
    • 数据复制方法

cd /home/aweip/Software/Distribute/hadoop/hadoopspark/
docker-compose up -d

docker-compose down

ssh -p 2222 root@localhost
start-dfs.sh

cd /root/share/mapreduce
hadoop fs -mkdir /input
mvn clean
mvn package
hadoop fs -put ./grades.txt /input
hadoop jar ./target/AvgGradeStudent.jar com.org.xidian.MapReduceAvgGradeStudent /input/grades.txt /output1
hadoop fs -cat /output1/part-r-00000

cd ../mapreduce2
mvn clean
mvn package
hadoop jar ./target/AvgGradeClass.jar com.org.xidian.MapReduceAvgGradeClass /input/grades.txt /output2
hadoop fs -cat /output2/part-r-00000

cd ../mapreduce3
mvn clean
mvn package
hadoop fs -put ./child-parent.txt /input
hadoop jar ./target/FatherSon.jar com.org.xidian.MapReduceFatherSon /input/child-parent.txt /output3
hadoop fs -cat /output3/part-r-00000

声明:AweiP Cache|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 《分布式计算》总结


且愿饮冰而热血不凉