《分布式计算》总结

一、分布式计算概述

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 客户端-服务器模式

负载均衡技术

如何架构
- 通过DNS轮询
- 通过反向代理
- 通过负载均衡器
带来的收益
- 提高系统的可扩展性，弹性增减节点
- 提高系统的可靠性
- 提高系统的性能
常用的负载均衡算法及优劣
- 轮询：简单，均衡，但不考虑节点的负载情况
- 随机：简单，均衡，但不考虑节点的负载情况
- 最少连接：考虑节点的负载情况，但不考虑节点的性能
- 最少响应时间：考虑节点的负载情况，考虑节点的性能，但不考虑节点的可用性
- 哈希：考虑节点的负载情况，考虑节点的性能，考虑节点的可用性，但不支持动态增减节点
- 一致性哈希：考虑节点的负载情况，考虑节点的性能，考虑节点的可用性，支持动态增减节点

6.2 主从模式

主从模式的概念

主节点
负责处理客户端的请求，维护系统的状态
从节点
负责处理主节点分配的任务，不维护系统的状态

主从模式的优缺点

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

6.3 总线模式

总线模式的概念

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

6.4 对等模式

对等模式的概念

系统中的所有计算节点任务分工都是对等的
完全相同的软件在不同的节点上运行，只是初始化参数不同

对等模式的优缺点

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

7. 分布式中间件的概念

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

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

7.2 中间件的作用

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

7.3 中间件的基本表现形式

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

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

1. 基于Socket的通信技术

1.1 Socket的概念

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

1.2 基于流式Socket（TCP）

建立连接（三次握手）
- 客户端向服务器发送连接请求
- 服务器向客户端发送连接确认
- 客户端向服务器发送连接确认
发送请求
- 客户端向服务器发送请求
返回响应
- 服务器向客户端发送响应
关闭连接

1.3 基于数据报Socket（UDP）

发送请求
- 客户端向服务器发送请求
返回响应
- 服务器向客户端发送响应

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

1.4 并发服务技术

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

2. 远程过程调用RPC（上层通信技术）

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

2.1 RPC的基本原理

序列化/反序列化
- 序列化：将对象转换为字节序列
- 反序列化：将字节序列转换为对象
插桩/代理（stub/skeleton）
- 插桩：客户端调用本地函数，插桩将函数调用转换为网络消息
- 代理：服务器端接收网络消息，代理将网络消息转换为函数调用
实现RPC语义的应用层协议
负责远程对象的集中注册与管理

点对点通信的缺点

关系复杂，耦合度高
可扩展性差

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

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

2.3 接口描述语言IDL

作用：定义接口，实现语言无关，平台无关，网络协议无关

2.4 RPC调用模式

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

3. 基于HTTP的通信技术

Web Service
- 优点：跨平台，跨语言，跨网络
- 缺点：效率低，不支持异步调用
RESTful
- 优点：效率高，支持异步调用
- 缺点：不支持跨语言，跨网络

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

优势
- 异步通信，提高系统的并发性
- 解耦，提高系统的可扩展性
- 削峰填谷，提高系统的可靠性
通信模式
1. 消息队列
  - 一对一（一个队列，一个消费者）
  - 一对多（一个队列，多个消费者）
2. 发布/订阅
  - 一对多，广播
投递模式
- At Most Once
  - 消息可能会丢失，但不会重复投递
- At Least Once
  - 消息不会丢失，但可能会重复投递
- Exactly Once
  - 消息不会丢失，不会重复投递
缓存模式
- 持久化
  - 消息持久化到磁盘
- 非持久化
  - 消息不持久化到磁盘

三、模型问题

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_3$和$T_2$的包
- 客户端在本地对其接收服务器响应的时间戳T4$T_4$
- 目标：将时钟校正为
  $ T_3 + ?_{resp} $
  $ ?_{resp} = \frac{(T_2 - T_1) + (T_3 - T_4)}{2} $

2. 逻辑时钟

2.1 Lamport时钟

Happen-Before关系
- 如果事件$a$和$b$是同一个节点（单进程/线程）中的两个事件,事件$a$发生在事件$b$之前，那么$a \to b$
- 如果$a$事件是 “节点$P_1$发送消息$m$到$P_2$”，$b$事件是“节点$P_2$接收消息$m$”，那么$a \to b$
- 如果$a \to b$且$b \to c$，那么$a \to c$(传递性)
- 如果$a ↛ b$且$b ↛ a$，那么$a$和$b$是并发事件
Lamport时钟
- 每个节点维护一个逻辑时钟，初始值为$C_i$
- 每个节点在执行一个事件生（消息产生、消息发送、消息接收都是事件）时，将逻辑时钟加1
- 每个节点在发送消息时，将逻辑时钟加1，并将当前逻辑时钟作为消息的时间戳
- 每个节点在接收消息时，将逻辑时钟更新为“当前逻辑时钟”和“消息时间戳”中较大的值加1

2.2 向量逻辑时钟

基本算法

设分布式系统包含 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$

优缺点

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

2.3 向量时钟的应用

全序广播
因果排序广播

五、分布式存储

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 按容错模型分类

失效停止模式共识协议
最多允许f = (n-1)/2个节点失效
- Paxos
- Raft
  - 过程：
    1. Leader接收客户端请求，存入日志
    2. 将新增日志复制给其他节点
    3. 确认日志复制成功，提交日志，执行日志中的命令
  - Leader选举过程：
    1. Leader失效
    2. Follower发现Leader失效，发起选举
    3. 超过半数节点投票给某个Follower，该Follower成为新的Leader
    4. 修改朝代号，通知其他节点
- Zab
拜占庭模式共识协议
原理：通过多数派原则，保证系统的一致性
- PBFT
- VFT

4. 分区（分片）技术

4.1 分区带来的收益和挑战

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

4.2 分区技术的分类

按主键范围分区
将主键的值按范围划分到不同的分区
- 均匀分区
  将主键的值按范围均匀划分到不同的分区
  - 优点：容易实现点查询，范围查询，排序等操作
  - 缺点：不适合数据分布不均匀的场景
- 不均匀分区
  将主键的值按范围不均匀划分到不同的分区
  - 优点：可处理数据偏斜，热点查询
  - 缺点：需要全局索引，导致查询多了一次网络开销
哈希分区
确定性，随机性，无碰撞性
- 简单哈希分区
  将主键的值通过哈希函数计算，得到哈希值，再通过哈希值对分区数取模，得到分区号
- 一致性哈希分区
  将主键的值通过哈希函数计算，得到哈希值，再通过哈希值对分区数取模，得到分区号
  - 优点：
  - 可处理数据分布不均匀，热点查询；
  - 不用全局索引，减少网络开销
  - 不用事先知道数据分布情况
  - 缺点：
  - 效率低，需要多次哈希计算
  - 在分区数变化时，数据迁移量大
  - 物理储存少时容易出现偏斜和热点问题

4.3 分区技术带来的挑战

分布式事务概念(ACID)
- 原子性（Atomicity）
  事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败
- 一致性（Consistency）
  事务执行前后，系统的状态保持一致
- 隔离性（Isolation）
  事务的执行不会相互影响
- 持久性（Durability）
  事务执行成功后，对系统的影响是永久的

4.4 分区和复制组和使用

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

4.5 HDFS分布式文件系统

HDFS系统架构
- NameNode(主节点)
  负责管理文件系统的命名空间，维护文件系统的元数据
- DataNode(从节点)
  负责管理文件系统的数据块，维护文件系统的数据块副本
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

一、 分布式计算概述