「分布式计算」期末复习

考点

「第一章 概述部分」

• 分布式系统定义
• 衡量分布式系统优劣的特性
• 设计分布式系统的挑战
• 分布式计算任务的分类
• 几类分布式系统的构架模式
• 同步交互模型和异步交互模型
• 节点故障模式(Fail-Stop和拜占庭的区别)

「第二章 分布式节点通信技术」

• RPC
• 消息队列通信

「第三章 分布式存储」

• 一致性模型的基本概念
• 强一致性和最终一致性
• CAP定理
• 两种基本的分区技术
• 一致性Hash算法
• HDFS的工作原理

「第四章 MapReduce」

• 理解框架的作用
• 理解分布式计算模型的概念
• 能根据需求写出MapReduce程序
• 本地聚合的作用

「第五章 Spark」

• 理解Spark平台的特点, RDD, DAG的概念
• 常用算子
• 能根据需求写出简单的Spark程序

第一章 概述

分布式系统定义

一个分布式系统由多个通过网络互连的独立自治的计算节点组成，这些计算节点基于消息通信机制进行相互协作，以完成共同的目标。

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

• 可扩展性
• 容错性
• 透明性
• 开放性
• 安全性
• 可维护性

设计分布式系统的挑战

• 异构性：各个节点的软硬件差异性很大
• 自治：各节点有自己独立的时钟和独立的内部状态
• 局部视图：节点只能看到整个系统的某个局部视图
• 开放性：节点数目在变动，网络情况在变动
• 可扩展性：节点增加时性能须合理增长
• 故障处理：必须处理网络故障和局部节点故障
• 安全性
• 透明性：应用层或用户无法察觉位置，并发，复制，故障，移动，伸缩，性能等变化
• 服务质量保证

分布式计算任务的分类

按时效性分类：

• 实时处理任务
• 准实时处理任务
• 批处理任务

几类分布式系统构架模式

• 客户端-服务器模式 （client-server)
• 主-从模式 (client-slave)
• 总线模式
• 对等模式 (peer-to-peer)
• 混合模式

同步交互模型和异步交互模型

同步模型：

• 假定消息传输延迟有上限，并且上限已知。节点之间的交互按周期进行，需要不同节点之间进行物理时钟同步。
• 分布式算法设计较简单，因为很容易检测失效节点。

异步模型：

• 假定消息传输延迟没有上限。节点之间异步工作，不进行周期同步。
• 分布式算法设计难度大，更接近现实的模型。

节点故障模式

失效停止（Fail-Stop）模式

节点失效后停止工作

失效停止恢复模式

• 节点失效后停止工作，但经过一段时间后又重新启动，失效之前的程序重新运行。

• 失效之前缓存的接收消息和内存中的私有状态全部丢失，但是非易失性存储器中的数据仍然存在。

拜占庭模式

节点失效后行为模式任意，例如可以故意发送恶意消息破坏分布式系统正常运行

第二章 分布式通信技术

三种并发服务技术

名称	使用场景
基于多线程的并发服务技术	需要进行大量计算，强相关的处理
基于线程池的并发服务技术	解决了线程创建和销毁的问题 适合高并发、任务执行时间短的业务
事件驱动技术（多路复用技术）	处理大量短事务的应用场景

RPC

RPC和RMI

RPC的定义：远程过程调用，使应用程序可以像调用本地节点上的过程那样去调用一个远程节点上的子程序。

RMI的定义：RMI使应用程序可以像调用本机上对象的方法一样调用远程主机中对象的方法

RPC中间件的作用

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

RPC中间件的实现原理

• RPC中间件在调用者进程中植入stub/proxy模块，该模块作为远程过程的本地代理，并暴露与远程过程相同的接口。
• RPC中间件在被调用者进程中植入skeleton模块，该模块作为调用者在远程主机中的代理，代替客户端调用本地方法，并把结果返回给客户端。
• stub模块和skeleton模块利用socket进行通信
• skeleton模块相当于c-s通信模式中的服务器端，要先于客户端运行，并且在某个socket端口进行监听

IDL

接口定义语言，用于支持跨编程语言调用的RPC中间件，独立于各类编程语言。

Web Service

是一种特殊的RPC技术, RPC的一套协议标准

WebService包含的标准协议:

• 消息编码标准 XML
• 传输协议标准 HTTP
• 远程对象访问协议 SOAP
• Web服务描述语言 WSDL
• 服务目录, 服务注册和服务发现 UDDI
• 安全相关标准: 签名加密认证等
• 服务组合和服务编排

MOM

面向消息中间件

提供了一种分布式的消息队列服务，使得节点之间可以实现基于消息的形式灵活的异步通信。

两种通信模式

• 消息队列通信模式
  • 在生产者和消费者之间建立的满足先进先出的消息队列
  • 一个队列可以有多个生产者，也可以有多个消费者。
  • 消息队列中的消息一旦被某个消费者取走，该消息就从队列中删除。
  • 出队的消息按照某种负载均衡策略发送给特定的消费者。
  • 高级队列模式：带优先级的队列；支持持久性的队列
• 主题/订阅通信模式
  • 支持向一个特定的消息主题发布消息。
  • 多个订阅同一主题的消费者可以同时接收发布到该消息主题的消息
  • 可以灵活地实现广播、组播等多对多通信模式

三种接收方式

• 阻塞接收
• 轮询接收
• 回调接收

基于MOM实现通信的优点

• 异步通信, 可以减少系统响应时间, 提高吞吐量
• 分布式节点之间的解耦
• 保证消息的可靠递交, 实现最终一致性
• 实现广播, 组播和多对多通信
• 流量削峰和流控
• 支持Push模型和Pull模型

第三章 分布式存储

一致性模型

多个客户端在读写数据时, 分布式存储系统为客户端提供的关于数据外在表现的保证

强一致性

• 在客户端看来, 分布式存储系统的外在表现和单副本存储系统的外在表现完全一致
• 任意客户端看到的所有针对分布式系统的操作(读写等原子操作)按全局一致的顺序排列(线性化), 并且该排序满足多个操作在时间维度上实际发生的先后顺序

最终一致性

• 在分布式系统停止更新时, 最终所有读操作都可以获得最新版本的数据

CAP定理

C: Consistency(一致性) - 不同节点上数据的强一致性

A: Availability(可用性) - 发出的请求在规定时间段内总能返回结果 (请求响应延时短, 可用性高; 否则可用性低)

P: Partition Tolerance(割断容忍性) - 允许部分节点和其他节点断裂

CAP定理的内容: 在设计分布式系统中, 三者只能取其二, 不能三者兼得

数据分区的基本方法

按主键范围进行分区

数据集合中每个元素（块、对象、记录）都可以找到一个主键，根据主键的连续范围进行分区。

• 各个主键范围分区一般都是非均匀分布的。
• 不同的主键范围分区分配给不同的物理存储节点。在特定分区进行分裂或合并时会产生数据移动。
• 优点：按主键进行连续查询很方便。
• 缺点：在主键范围非均匀分布时必须建立全局索引以记录数据分区和存储节点的对应关系。一般要专门指定一个节点维护全局索引，该节点是中心节点。

按主键哈希值进行分区

将整个哈希空间均匀分成k个区间, 每个存储节点负责一个哈希区间(桶)

• 计算新插入的数据元素主键的哈希值, 然后计算该哈希值落入了哪个桶, 然后将该元素分配给对应的存储节点

• 优点: 可以在一定程度避免偏斜和热点问题; 无需建立全局索引, 因此也无需中心节点

• 缺点: 基于主键进行连续范围查询效率极低; 在物理存储节点较少时仍会出现偏斜和热点问题(采用虚拟节点缓解); 桶个数改变时会造成大量数据移动

一致性哈希算法

是一种特殊的哈希算法。在使用一致哈希算法后，桶数量的改变平均只需要对K/n 个关键字重新映射，其中K是关键字的数量，n是桶的数量

• 找一个普通的理想哈希函数HASH。
• 将该HASH函数的值域空间首尾相接做成一个环。
• 假定每个存储节点（每个节点负责一个桶）都有一个唯一标识（例如针对每个节点生成一个随机数作为其标识；或用其IP地址）：ID1，ID2，……, IDn。
• 每个节点的唯一标识作为输入计算其HASH函数输出，并将其输出值映射到环上，会产生n个映射点。
• 节点IDi所负责的桶就是环上从映射点HASH(IDi)开始到下一个映射点之间的连续哈希值区间。（假定按顺时针旋转）

常用的负载均衡策略

• 随机
• 轮询
• 固定权重值
• ip哈希
• 最小tcp连接数
• 最小响应时间
• 根据各服务器实际负载的动态负载均衡算法

HDFS分布式文件系统

NameNode, DataNode

NameNode是整个文件系统的管理节点。它维护：

1. 整个文件系统的文件目录树
2. 文件目录元信息和每个文件对应的数据块列表
3. 接受用户的操作需求

NamedNode维护着两张表：文件名-数据块对应表和数据块-物理节点对应表。

DataNode：负责存储client发来的数据块，执行数据块的读写操作，使用多备份策略。

HDFS读数据流程

1. 客户端将读请求发送给NameNode，读请求参数中包含了文件名、偏移量和长度。

2. NameNode根据文件名、偏移量查找自己内存中“文件名—数据块对应表”和“数据块—物理节点对应表”，并将包含目标数据块的数据节点IP列表发送给客户端。

3. 客户端从数据节点IP列表中选择“最近的”的数据节点，并与该节点建立Socket连接直接读取数据。

HDFS写数据流程

1. 客户端将新建文件请求发送给NameNode，NameNode根据负载均衡策略选择3个数据节点，并将这些节点IP地址返回给客户端。
2. 客户端将这3个数据节点构成一个流水线，将第一个数据库的数据流写入流水线。
3. 第一个数据块写入成功后客户端再向NameNode获取下一个数据块对应的3个数据节点。

第四章 MapReduce

理解框架的作用

分布式计算平台(或叫框架)和运行在平台之上的应用层模块相互协作完成一个完整的分布式计算任务。

分布式计算平台的作用：

1. 将输入数据进行分片，将每个分片交给一个计算子任务处理；
2. 将不同的计算子任务分发给不同的计算节点执行；
3. 子任务分发时将考虑如下因素：各个计算节点的当前负载；尽量让计算子任务和对应的数据分片处于同一台物理主机。
4. 帮助实现中间计算结果的合并、中间结果在不同计算节点之间的交换(混洗)；
5. 容错性：监视各个子任务的执行状态，将执行失败的子任务重新调度给其它节点执行。
6. 可扩展性：对集群中计算节点的增长或减少可以自适应。

Combiner的作用

本地聚合, 为了避免map任务和reduce任务之间的数据传输而设置的，Hadoop允许用户针对map task的输出指定一个合并函数combiner, 即为了减少传输到Reduce中的数据量。

编程

Mapper:

/*
input: <k, v>
output: <key, value>
*/
key.set(xxx);
value.set(xxx);
context.write(key, value);

Reducer:

/*
input: <k, list(v)>
output: <key, value>
*/
value = 0;
for (i : v) {
    value += i;
}
key = k;
context.write(key, value);

第五章 Spark

Spark平台的特点

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

相对于MapReduce的批处理计算，Spark 可以带来上百倍的性能提升，因此成为继MapReduce之后，最为广泛使用的分布式计算平台。

使用先进的DAG(有向无环图) 调度程序，查询优化器和物理执行引擎，以实现性能上的保证；

多语言支持，目前支持的有Java，Scala，Python 和R；

提供了80 多个高级API，可以轻松地构建应用程序；

支持批处理，流处理和复杂的业务分析；

丰富的类库支持：包括SQL，MLlib，GraphX和Spark Streaming 等库，并且可以将它们无缝地进行组合；

丰富的部署模式：支持本地模式和自带的集群模式，也支持在Hadoop，Mesos，Kubernetes 上运行；

多数据源支持：支持访问HDFS，Alluxio，Cassandra，HBase，Hive 以及数百个其他数据源中的数据。

RDD的概念

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

在Spark平台的支持下，可以对RDD的内部元素进行并行粗粒度操作，操作的具体动作由应用层定义。

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

DAG的概念

一个具体的大数据处理任务可以表达为一系列RDD之间的转换。

一个分布式计算任务中涉及到的不同RDD之间存在依赖关系，RDD的每次转换都会生成一个新的依赖关系，这种RDD之间的依赖关系就像流水线一样。RDD(s) 及其之间的依赖关系组成了DAG(有向无环图)。

常用的RDD算子

Transformation算子: 惰性执行, 即不是在定义时刻执行, 只是在必要时刻执行

Action算子: 立即执行, 进而触发其他的惰性执行Transformation算子执行

常用的算子:

代码例子:

1. 单词统计

from pysparkimport SparkConf,SparkContext
conf= SparkConf().setMaster("local").setAppName(“wordcount")
sc= SparkContext(conf=conf)
textData= sc.textFile("./readme.txt")
splitData= textData.flatMap(lambda line:line.split(" "))
flagData= splitData.map(lambda word:(word,1))
countData= flagData.reduceByKey(lambda x,y:x+y)
countData.saveAsTextFile("./result")

1. 分数统计

rdd = 原始数据
rdd1 = rdd.map(lambda x : x.split(",")).filter(lambda x : x[3] == "必修")
rdd2 = rdd1.map(lambda x : (x[0] + "-" + x[1], x[4])).groupByKey().map(lambda x : (x[0], sum(x[1])))
rdd3 = rdd1.map(lambda x : (X[0] + "-" + x[1], 1)).groupByKey().map(lambda x : x[0], sum(x[1]))
rdd4 = rdd2.join(rdd3).map(lambda x : (x[0], x[1][0] / x[1][1]))
accumulator acc1, acc2, acc3, acc4, acc5
rdd4.foreach(lambda x : count_grade(x[1]))

def count_grade(x):
    if (x >= 90 and x <= 100):
        acc1.add(1)
    elif (x >= 80 and x <= 89):
        acc2.add(1)
    elif (x >= 70 and x <= 79):
        acc3.add(1)
    elif (x >= 60 and x <= 69):
        acc4.add(1)
    elif (x >= 0 and x <= 59):
        acc5.add(1)