分布式计算

概述

分布式系统定义

分布式计算：多个通过网络互联的计算节点通过相互协作共同完成计算任务。

理解分布式系统定义的几个要点

多个计算节点：计算节点抽象为有限状态机（图灵机）
网络互联
独立自治
相互协作共同完成目标
消息传递模型

与并行计算的关系

不同层次的并行计算：

指令级并行：多指令并行；单指多数并行（向量指令）
CPU多核并行：多线程编程
多CPU并行（一致性内存访问）：多线程编程
多CPU并行（非一致性内存访问）：超级计算机
基于GPU的并行：单指多数并行；CUDA、OpenCL
多机并行：就业消息传递的分布式计算（share nothing）

构建分布式系统的目的

提高计算能力
提高存储能力
提高网络吞吐能力（并发访问能力）
提高可靠性（解决局部失效问题）
提高安全性（解决被局部攻击问题）
提高可扩展性（解决瓶颈问题）
实现资源共享
实现跨越时空的协同服务（发挥不同节点的优势）

衡量分布式系统优劣的特性

可扩展性/可伸缩性（Scalability）
- 垂直可扩展性（Vertical Scalablility）
- 水平可扩展性（Horizontal Scalability）
容错性（Fault Tolerance/Reliability）
- 可用性（Availability）
- 可恢复性（Recoverability）
透明性（Transparency）
开放性（Openness）
安全性（Security）
可维护性（Maintainability）

设计分布式系统的挑战

异构性
自治
局部视图
开放性
可扩展性
故障处理
安全性
透明性
服务质量保证

关于分布式一致性

几类分布式系统框架模式

客户端-服务器（Client-Server）模式
- 客户端发出服务请求，服务端根据客户端请求参数完成实际运算，并将运算结果返回给客户端
- 客户端运算任务轻、服务端运算任务重
- 客户端生命周期短、服务端生命周期长
- 服务端一般要应对并发问题
- 客户端一般负责和用户进行交互
- 瘦客户端/胖服务端
Client—Cluster模式
- 是Client-Server模式的变种
- 服务端由多个服务器构成，共同承担计算任务
- 在宏观逻辑上，多个服务器构成的集群可以视为单一的功能强大的计算节点。客户端感觉不到服务端的实际构成。
主从（Master-Slave）模式
- 主节点（Master）负责将总任务分解为多个自任务分发给各个从节点（Slave，也叫Worker节点）
- 主节点监视各个从节点的任务执行情况，将执行失败的任务调度给其他的从节点完成
- 主节点在分配任务时会参考各个节点的当前负载情况
总线模式
- 不同节点通过虚拟总线相连
- 消息发送者不必知道接收者是谁，接收者也不知道发送者是谁
- 发送者和接收者之间用异步方式通信
- 一种松耦合结构
- 不同节点完成不同功能，分工协作
对等（Peer-to-Peer）模式
- 系统中每个计算节点在任务分工上是完全对等的
- 完全相同软件在不同的计算机上运行，只是初始化参数不同
- 结构化P2P：不同节点之间的交互模式遵循固定规律
- 非结构化P2P：不同节点之间的交互模式没有固定规律
混合模式

常用的负载均衡策略

随机
轮询
固定权重值
IP哈希（基于一致性随机散列函数）
最少TCP连接数
最小响应时间
基于各服务器实际负载的动态负载均衡算法

中间件的基本概念

中间件的作用

为开发者提供高层的编程抽象，屏蔽分布式系统的底层的异构型复杂性
提高互操作性和可移植性
提供分布式系统的基础设施服务

常用的中间件

远程过程调用中间件
分布式对象中间件
分布式组件中间件
消息队列中间件
Web服务中间件
P2P中间件

中间件的表现形式

作为独立的后台进程存在
作为运行时的函数库/类库存在（LIB静态库、DLL动态库、Jar包等）
作为源代码级的函数库/类库存在
作为高级语言解释器的一部分存在
作为辅助编译工具存在
作为高级语言编译器的一部分存在

抽象理论模型

交互模式
- 同步模型
- 异步模型
信息故障模式
节点故障模式
- 失效停止模式（Fail—Stop）
- 失效停止恢复模式
- 拜占庭模式
- 发送者验证拜占庭模式
- 理性拜占庭模式

分布式节点之间的通信技术

TCP/IP网络体系介绍

TCP/IP先于OSI模型，不完全符合OSI标准
TCP/IP四层模型（也可分为五层，将网络接口分为两层）

Socket

什么是Socket

网络层和传输层提供给应用层的标准化编程接口（或称为编程接口）

套接字分类-Socket类型

流式套接字
数据报套接字
原始套接字

如何标识一个Socket

五元组：<SIP, sPort, dIP, dPort, 协议>
- 本地IP地址
- 本地端口号（通常临时分配：1024~5000）
- 远程IP地址
- 远程端口号（通常使用保留端口号1~1023）
- 协议类型（注意TCP 53和UDP 53是不同的）
TCP套接字编程典型模型
UDP套接字编程典型模型

并发服务技术

基于多线程的并发服务技术
基于线程池的并发服务技术

示例程序

基于TCP协议的Client-Server通信程序示例
- Server
- Client

第一次作业

将基于UDP协议的Client-Server通信程序示例的服务器端程序改造成多线程版。
将基于TCP协议的Client-Server通信程序示例的服务器端程序改造成线程池版。
代码实现

远程调用RPC和RMI

远程调用RPC

远程过程调用（Remote Procedure Call，RPC）：使应用程序可以像调用本地节点上的过程那样去调用一个远程节点上的子程序。

远程方法调用RMI

远程方法调用（Remote Method Invocation， RMI）：将面向对象的编程模型扩展到了分布式环境。

RPC/RMI中间件的作用

定义并利用Socket服务接口实现了一套调用者和被调用者之间的通信协议——远程调用协议
实现了过程参数以及运算结果的序列化和反序列化
通信过程中的错误处理
过程服务进程（或远程对象）的集中注册与发现——目录服务
远程对象的统一标识和生命周期管理
在服务端支持并发访问（多采用多线程技术）

注册中心

用于服务端注册远程服务以及客户端发现服务
可以实现负载均衡

RPC/RMI中间件的实现原理

在调用者进程中注入stu/proxy模块
在被调用者进程中注入skeleton模块
stub和skeleton之间利用Socket进行通信
skeleton相当于服务器端

gRPC中间件

通信协议基于HTTP协议标准，对象序列化基于**ProtoBuf(Protocol Buffers)**序列化协议
Protocol Buffers(简称Protobuf) 是Google设计的序列化标准协议和序列化中间件。

程序中应用Protobuf的方法

在.proto文件中定义要序列化的对象（使用独立于具体编程语言的标准格式Protocol Buffers）
利用代码自动生成工具（eg：Windows下protoc.exe）生成所有要序列化对象的工厂类
将生成的工厂类源码添加到应用工程中
需要创建一个可序列化对象时，用工厂对象创建
调用可序列化对象的writeTo方法将对象序列化成字节流并存入外部存储介质
调用工厂对象的parseFrom方法可以实现反序列化，并根据反序列化结果生成一个新的对象

程序中应用gRPC的方法

将RPC服务接口定义为标准.proto文件
用Protobuf提供的代码自动生成工具根据.proto文件生成RPC服务中所有要序列化对象的工厂类
利用gRPC提供的代码自动生成工具根据.proto文件生成RPC服务的stub类和skeleton类
将工具自动生成的序列化对象工厂相关源程序、RPC服务的stub类和skeleton类相关源程序加入的RPC服务端工程中
RPC服务端工程基于skeleton类中相关基类实现RPC服务功能的核心逻辑和监听服务器
将工具自动生成的序列化对象工厂相关源程序、RPC服务的stub类和skeleton类相关源程序加入的RPC客户端工程中
RPC客户端工程基于stub类实现调用RPC服务的相关逻辑

第二次作业

利用RPC技术实现一个书籍信息管理系统，具体要求：

客户端实现用户交互，服务器端实现书籍信息存储和管理。客户端与服务器端利用RPC机制进行通信。可以选择Java RMI、gRPC、Dubbo等任意RPC中间件。
服务器端至少暴露如下RPC接口：
- bool add(Book b) 添加一个书籍对象。（注意Book对象序列化问题）
- Book queryByID(int bookID) 查询指定ID号的书籍对象。
- BookList queryByName(String name) 按书名查询书籍对象列表。
- bool delete((int bookID) 删除指定ID号的书籍对象。

实现

微服务

各个模块独立（大多采用容器技术（如Docker）），模块之间使用RPC通信。

基于消息中间件的通信技术

点到点通信技术的缺点

关系复杂，耦合度高
可扩展性差：增加生产者或消费者对多个节点产生影响
容错性差：节点失效或生产者和消费者速度不匹配会丢失数据

解决方案——增减中介节点

降低了耦合性
提高了容错性：中介节点具有数据缓存功能
提高了可扩展性：增加生产者或消费者对其他节点无影响

面向消息中间件（Message Oriented Middleware，MOM）

使分布式应用程序可以通过发送和接收消息来进行异步通信和交换数据。

MOM两种通信模式

消息队列模式
- 消息队列中的消息一旦被某个消费者取走，该消息就从队列中删除
- 可以实现负载均衡
主题订阅模式（类似微信公众号订阅）
- 多个订阅同一主题的消费者可以同时接收发布到该消息主题的消息
- 可以实现广播

三种接收方式

阻塞接收（同步）
轮询接收
回调接收（异步）

第三次作业

利用MOM消息队列技术实现一个分布式随机信号分析系统，具体要求：

随机信号产生器每隔10毫秒左右就产生一个正态分布的随机数字，并作为一个消发布
多个随机信号分析模块订阅并接收该随机数字，然后对信号进行分析并实时显示分结果。至少包含如下分析模块：
1. 计算随机信号的均值；
2. 计算过去N个随机信号的方差（N为常量，可设置）
3. 实现基于正态分布的异常点检测
4. 实时绘制过去一段时间内随机信号的折线图（选作）

基于NSQ的Golang实现

分布式存储

分布式存储要达到的目标

提高存储容量：多个存储节点容量的聚合（水平可扩展）
提高数据吞吐量
提高可靠性/可用性：部分存储节点发生故障时数据不丢失，部分节点失效时用户依然可以访问（容错性）
低时延：就近的服务器上（CDN）

基本手段：复制（replica）

用途
- 如果一些节点不可用，剩余的节点仍然可以提供服务
- 提高吞吐率
带来的问题
- 硬件成本
- 多数据副本之间的一致性问题

基本手段：分区（Partitioning)

将一个大型数据库文件（或数据库）拆分成较小的子集（称为分区partition或切片shard）派分给不同的节点

带来的问题
- 跨区处理（分布式索引问题）
- 合理、动态分区问题（大数据如何拆分）
- 负载均衡
- 分布式事务处理

基于领导者的复制（主从复制）

客户端要向数据存储系统写入数据时，它必须将请求发送给领导者；领导者将新数据写入本地存储，同时也会将数据变更发送给所有的追随者。
当客户想要从数据存储系统读取数据时，它可以向领导者或追随者查询。
适合于读多写少的应用场景。

同步复制和异步复制

同步
异步

多副本分布式存储中的一致性问题

强一致性
- 一个客户端写入成功，其他客户端后续都可以读出新版本的值
- 每个读操作一定不会读出比上一次更旧的版本
顺序一致性
因果一致性
最终一致性

CAP定理

Consistensy（一致性）、Partition Tolerance（切割容忍性）、Availability（可用性）三者只能取其二，不可兼得三者。

很多时候只能取CP或AP，因为一般无法保证网络每时每刻畅通

BASE定理

对CAP中的一致性和可用性权衡的结果：基本可用（Basically Available）、软件态（Soft State）、最终一致性（Eventually Consistency）

数据分区的基本方法

根据主键范围进行分区

一般都是非均匀分布的，所以需要建立全局索引

根据主键的哈希值进行分区

哈希函数

输入：长度不定的01串
输出：长度固定的01串
值域空间：$[0, 2^{n}-1]$
特性
- 确定性
- ”随机性“
- 无碰撞性：任何两个输入，它们输出值相等的概率为$2^{-n}$

主要思想

$$ hash(key)\mod N $$

优点

一定程度上避免了偏斜和热点问题
无须全局索引

缺点

当节点数量变动时，需要大量的数据迁移。

基于一致性哈希算法的分区——哈希环

当新增节点后，仅仅需要迁移少量数据。

缺点：只能在节点之间新增新节点，这样会导致负载分配不均衡。

使用虚拟节点改进的一致性哈希

每个物理节点有若干个虚拟节点，这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分，解决了数据倾斜问题。

HDFS分布式文件系统

NameNode维护的两张表

文件名——数据块对应表：每个文件被切片之后对应若干个有唯一标识号的数据块
数据块——物理节点对应表：每个数据块在不同DataNode存储3份（3备份策略）

写流程

Client向NameNode请求增加数据块（维护文件名——数据块对应表）
NameNode返回数据块号及分配的3个DataNode IP地址（3备份策略）
Client与NameNode流水线方式写入数据块（完成后维护数据块——物理节点对应表）

读流程

客户端向请求NameNode，传送参数：文件名、偏移量、长度
NameNode查找文件名——数据块对应表和数据块——物理节点对应表，将对应DataNode的IP地址返回给CLient
Client向最近的DataNode建立连接完成读取

MapReduce模型和分布式计算框架

MapReduce并行计算模型

单词计数的例子

Hadoop MapReduce计算模型

Client类
1. 设置工作参数
2. 设置Map Reduce Job对象
3. 设置要上传给Hadoop平台的Jar包或Class
4. 指定Mapper类
5. 指定Combiner类（可选）
6. 指定Reducer类
7. 设定输出数据的格式
8. 设定输入、输出文件路径
9. 启动该Job直到运行结束
Mapper类：实现Map接口(K1, V1)->(K2, V2)
Combiner类：实现Reduce接口(K2, list(V2))->list(K3, V3)
Reducer类：实现Reduce接口(K3, list(V3))->list(K4, V4)

Spark平台和基于RDD-DAG的计算模型

Spark简介

Spark是一个快速、通用、可扩展的分布式计算平台。

Spark平台体系结构

分布式弹性数据集RDDs

RDDs全称Resilient Distributed Datasets是Spark最基本的数据抽象，它是只读的、分区存储的、分布式的数据集合。

可以将RDDs看作一个分布式存储的“大数组”，应用程序只需关心如何由一个RDDs转换为另一个RDDs，不用关心RDD在底层是如何分区、如何分布到多个节点上、如何在内存中缓存、内存缓存丢失后如何重新生成。

容错性

如果RDDs的某个分区失效，Spark会根据DAG往回查看并重新恢复数据。

概述#

分布式系统定义#

理解分布式系统定义的几个要点#

与并行计算的关系#

构建分布式系统的目的#

衡量分布式系统优劣的特性#

设计分布式系统的挑战#

关于分布式一致性#

几类分布式系统框架模式#

常用的负载均衡策略#

中间件的基本概念#

中间件的作用#

常用的中间件#

中间件的表现形式#

抽象理论模型#

分布式节点之间的通信技术#

TCP/IP网络体系介绍#

Socket#

什么是Socket#

套接字分类-Socket类型#

如何标识一个Socket#

并发服务技术#

示例程序#

第一次作业#

远程调用RPC和RMI#

远程调用RPC#

远程方法调用RMI#

RPC/RMI中间件的作用#

注册中心#

RPC/RMI中间件的实现原理#

gRPC中间件#

程序中应用Protobuf的方法#

程序中应用gRPC的方法#

第二次作业#

微服务#

基于消息中间件的通信技术#

点到点通信技术的缺点#

解决方案——增减中介节点#

面向消息中间件（Message Oriented Middleware，MOM）#

MOM两种通信模式#

三种接收方式#

第三次作业#

分布式存储#

分布式存储要达到的目标#

基本手段：复制（replica）#

基本手段：分区（Partitioning)#

基于领导者的复制（主从复制）#

同步复制和异步复制#

多副本分布式存储中的一致性问题#

CAP定理#

BASE定理#

数据分区的基本方法#

根据主键范围进行分区#

根据主键的哈希值进行分区#

哈希函数#

主要思想#

优点#

缺点#

基于一致性哈希算法的分区——哈希环#

使用虚拟节点改进的一致性哈希#

HDFS分布式文件系统#

NameNode维护的两张表#

写流程#

读流程#

MapReduce模型和分布式计算框架#

MapReduce并行计算模型#

单词计数的例子#

Hadoop MapReduce计算模型#

Spark平台和基于RDD-DAG的计算模型#

Spark简介#

Spark平台体系结构#

分布式弹性数据集RDDs#

容错性#

将计算任务抽象为有向无环图#

概述