一、 分布式计算概述
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)中间件的通信技术
-
优势
- 异步通信,提高系统的并发性
- 解耦,提高系统的可扩展性
- 削峰填谷,提高系统的可靠性
-
通信模式
- 消息队列
- 一对一(一个队列,一个消费者)
- 一对多(一个队列,多个消费者)
- 发布/订阅
- 一对多,广播
- 消息队列
-
投递模式
-
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
-
过程:
- Leader接收客户端请求,存入日志
- 将新增日志复制给其他节点
- 确认日志复制成功,提交日志,执行日志中的命令
- Leader选举过程:
- Leader失效
- Follower发现Leader失效,发起选举
- 超过半数节点投票给某个Follower,该Follower成为新的Leader
- 修改朝代号,通知其他节点
-
- 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
jjagxxuwaa
想想你的文章写的特别好www.jiwenlaw.com
bgwqsmapvr
看的我热血沸腾啊https://www.237fa.com/
aksggttyfm
叼茂SEO.bfbikes.com
ugfifcpxnp
想想你的文章写的特别好
xmmeaicahu
叼茂SEO.bfbikes.com