Spark

特点

• DAG 切分的多阶段计算过程更快速

• 使用内存存储中间计算结果更高效

• RDD 的编程模型更简单

编程模型

RDD 模型

RDD 是 Spark 的核心概念，是弹性分布式数据集(Resilient Distributed Datasets)的

缩写。RDD 既是 Spark 面向开发者的编程模型，又是 Spark 自身架构的核心元素。

作为 Spark 编程模型的 RDD。我们知道，大数据计算就是在大规模的数据集上进行一系列的数据计算处理。MapReduce 针对输入数据，将计算过程分为两个阶段，一个 Map 阶段，一个 Reduce 阶段，可以理解成是面向过程的大数据计算。我们在用 MapReduce 编程的时候，思考的是，如何将计算逻辑用 Map 和 Reduce 两个阶段实现，map 和 reduce 函数的输入和输出是什么，MapReduce 是面向过程的。

而 Spark 则直接针对数据进行编程，将大规模数据集合抽象成一个 RDD 对象，然后在这个 RDD 上进行各种计算处理，得到一个新的 RDD，继续计算处理，直到得到最后的结果数据。所以 Spark 可以理解成是面向对象的大数据计算。我们在进行 Spark 编程的时候，思考的是一个 RDD 对象需要经过什么样的操作，转换成另一个 RDD 对象，思考的重心和落脚点都在 RDD 上。

RDD 函数

RDD 上定义的函数分两种，一种是转换(transformation)函数，这种函数的返回值还是 RDD;另一种是执行(action)函数，这种函数不再返回 RDD。

RDD 定义了很多转换操作函数，比如有计算 map(func)、过滤 filter(func)、合并数据集 union(otherDataset)、根据 Key 聚合 reduceByKey(func, [numPartitions])、连接数据集 join(otherDataset, [numPartitions])、分组 groupByKey([numPartitions]) 等十几个函数。

作为数据分片的 RDD

跟 MapReduce 一样，Spark 也是对大数据进行分片计算，Spark 分布式计算的数据分片、任务调度都是以 RDD 为单位展开的，每个 RDD 分片都会分配到一个执行进程去处理。

RDD 上的转换操作又分成两种，一种转换操作产生的 RDD 不会出现新的分片，比如 map、filter 等，也就是说一个 RDD 数据分片，经过 map 或者 filter 转换操作后，结果还在当前分片。就像你用 map 函数对每个数据加 1，得到的还是这样一组数据，只是值不同。实际上，Spark 并不是按照代码写的操作顺序去生成 RDD，比如

rdd2 = rdd1.map(func)

这样的代码并不会在物理上生成一个新的 RDD。物理上，Spark 只有在产生新的 RDD 分片时候，才会在物理上真的生成一个 RDD，Spark 的这种特性也被称作惰性计算。

另一种转换操作产生的 RDD 则会产生新的分片，比如 reduceByKey，来自不同分片的 相同 Key 必须聚合在一起进行操作，这样就会产生新的 RDD 分片。然而，实际执行过 程中，是否会产生新的 RDD 分片，并不是根据转换函数名就能判断出来的。

• 窄依赖（无 shuffle 依赖）

• 宽依赖（shuffle 依赖）

Spark 计算阶段

和 MapReduce 一个应用一次只运行一个 map 和一个 reduce 不同，Spark 可以根据应用的复杂程度，分割成更多的计算阶段(stage)，这些计算阶段组成一个有向无环图 DAG，Spark 任务调度器可以根据 DAG 的依赖关系执行计算阶段。

Spark 的作业管理

Spark 里面的 RDD 函数有两种，一种是转换函数，调用以后得到的还是一个 RDD，RDD 的计算逻辑主要通过转换函数完成。

另一种是 action 函数，调用以后不再返回 RDD。比如 count() 函数，返回 RDD 中数据的元素个 数;saveAsTextFile(path)，将 RDD 数据存储到 path 路径下。Spark 的 DAGScheduler 在遇到 shuffle 的时候，会生成一个计算阶段，在遇到 action 函数的时候，会生成一个作业(job)。

RDD 里面的每个数据分片，Spark 都会创建一个计算任务去处理，所以一个计算阶段会包含很多 个计算任务(task)。

Spark 的执行过程

Spark 支持 Standalone、Yarn、Mesos、Kubernetes 等多种部署方案，几种部署方案原理也都一样，只是不同组件角色命名不同，但是核心功能和运行流程都差不多。

首先，Spark 应用程序启动在自己的 JVM 进程里，即 Driver 进程，启动后调用 SparkContext 初始化执行配置和输入数据。SparkContext 启动 DAGScheduler 构造执行的 DAG 图，切分成最小的执行单位也就是计算任务。

然后 Driver 向 Cluster Manager 请求计算资源，用于 DAG 的分布式计算。ClusterManager 收到请求以后，将 Driver 的主机地址等信息通知给集群的所有计算节点 Worker。

Worker 收到信息以后，根据 Driver 的主机地址，跟 Driver 通信并注册，然后根据自己的空闲资源向 Driver 通报自己可以领用的任务数。Driver 根据 DAG 图开始向注册的 Worker 分配任务。

Worker 收到任务后，启动 Executor 进程开始执行任务。Executor 先检查自己是否有 Driver 的执行代码，如果没有，从 Driver 下载执行代码，通过 Java 反射加载后开始执行。

Storm

实时计算系统

• 低延迟

• 高性能

• 分布式

• 可伸缩

• 高可用

Storm 的基本概念

• Nimbus:负责资源分配和任务调度。

• Supervisor:负责接受 Nimbus 分配的任务，启动和停止属于自己管理的 Worker 进程。

• Worker:运行具体处理组件逻辑的进程。

• Task:Worker 中每一个 Spout/Bolt 的线程称为一个 Task。

• Topology:Storm 中运行的一个实时应用程序，因为各个组件间的消息流动形成逻辑上的一个拓扑结构。

• Spout:在一个 Topology 中产生源数据流的组件。通常情况下 Spout 会从外部数据源中读取数据，然后转换为 Topology 内部的源数据。Spout 是一个主动的角色，其接口中有个 nextTuple() 函数，Storm 框架会不停地调用此函数，用户只要在其中生成源数据即可。

• Bolt:在一个 Topology 中接受数据然后执行处理的组件。Bolt 可以执行过滤、函数操作、合并、写数据库等任何操作。Bolt 是一个被动的角色，其接口中有个 execute(Tuple input) 函数,在接受到消息后会调用此函数，用户可以在其中执行自己想要的操作。

• Tuple:一次消息传递的基本单元。本来应该是一个 key-value 的 map，但是由于各个组件间传递的 tuple 的字段名称已经事先定义好，所以 tuple 中只要按序填入各个 value 就行了，所以就是一个 value list.

• Stream:源源不断传递的 tuple 就组成了 stream。

Storm Streaming Grouping

Stream Grouping 定义了一个流在 Bolt 任务间该如何被切分。

这里有 Storm 提供的 6 个 StreamGrouping 类型:

• 随机分组(Shuffle grouping):随机分发 tuple 到 Bolt 的任务，保证每个任务获得相等数量的 tuple。

• 字段分组(Fields grouping):根据指定字段分割数据流，并分组。例如，根据“user-id”字段，相同“user-id”的元组总是分发到同一个任务，不同“user-id”的元组可能分发到不同的任务。

• 全部分组(All grouping):tuple 被复制到 Bolt 的所有任务。这种类型需要谨慎使用。

• 全局分组(Global grouping):全部流都分配到 Bolt 的同一个任务。明确地说，是分配给 ID 最小的

• 无分组(None grouping):你不需要关心流是如何分组。目前，无分组等效于随机分组。但最终，Storm 将把无分组的 Bolts 放到 Bolts 或 Spouts 订阅它们的同一线程去执行(如果可能)。

• 直接分组(Direct grouping):这是一个特别的分组类型。元组生产者决定 tuple 由哪个元组处理者任务接收。

• 当然还可以实现 CustomStreamGroupimg 接口来定制自己需要的分组。

Flink

大数据算法与机器学习

网页排名算法 PageRank

假设一个由 4 个页面组成的小团体:A，B，C 和 D。如果所有页面都链向 A，那么 A 的

PR(PageRank)值将是 B，C 及 D 的 Pagerank 总和。

PR(A) = PR(B) + PR(C) + PR(D)

继续假设 B 也有链接到 C，并且 D 也有链接到包括 A 的 3 个页面。一个页面不能投票 2 次。所以 B 给每个页面半票。以同样的逻辑，D 投出的票只有三分之一算到了 A 的 PageRank 上。

PR(A) = PR(B) /2 + PR(C) / 1+ PR(D) / 3

KNN 分类算法

KNN 算法，也叫 K 近邻(K Nearest Neighbour)算法

对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的 K 个样本，K 个样本最多归属的类别，就是这个需要分类数据的类别。

数据的距离算法

对于数据 xi 和 xj，若其特征空间为 n 维实数向量空间 Rn，即 xi=(xi1,xi2,...,xin)，xj=(xj1,xj2,...,xjn)

数据文本特征值 TF-IDF 算法

贝叶斯算法

K-means 聚类算法

第 1 步:随机在图中取 K 个种子点，图中 K=2，即图中的实心小圆点。

第 2 步:求图中所有点到这 K 个种子点的距离，假如一个点离种子点 X 最近，那么这个点属于 X 点群。

在图中，可以看到 A、B 属于上方的种子点，C、D、E 属于中部的种子点。

第 3 步:对已经分好组的两组数据，分别求其中心点。对于图中二维平面上的数据，求中心点最简单暴力的算法就是对当前同一个分组中所有点的 X 坐标和 Y 坐标分别求平均值，得到的 就是中心点。

第 4 步:重复第 2 步和第 3 步，直到每个分组的中心点不再移动。这时候，距每个中心点最近的点数据聚类为同一组数据。

推荐引擎算法

• 基于人口统计的推荐

• 基于商品属性的推荐

• 基于用户的协同过滤推荐

• 基于商品的协同过滤推荐

机器学习系统架构

样本

样本就是通常我们常说的“训练数据”，包括输入和结果两部分。

T=(x1,y1),(x2,y2),...,(xn,yn)

模型

模型就是映射样本输入与样本结果的函数，可能是一个条件概率分布，也可能是一个决策函数。一个具体的机器学习系统所有可能的函数构成了模型的假设空间，数学表示是:

F=f｜Y=f（X）

其中 X 是样本输入，Y 是样本输出，f 就是建立 X 和 Y 映射关系的函数。所有 f 的可能 结果构成了模型的假设空间 F。

很多时候 F 的函数类型是明确的，需要计算的是函数的参数，比如确定 f 函数为一个线 性函数，那么 f 的函数表示就可以写为:

y=a1x + a0

这时候需要计算的就是 a1 和 a0 两个参数的值。这种情况下模型的假设空间的数学表示 是:其中 θ 为 f 函数的参数取值空间，一个 n 维欧氏空间，被称作参数空间。

算法

算法就是要从模型的假设空间中寻找一个最优的函数，使得样本空间的输入 X 经过该函数的映射得到的 f(X)，和真实的 Y 值之间的距离最小。这个最优的函数通常没办法直接计算得到，即没有解析解，需要用数值计算的方法不断迭代求解。因此如何寻找到 f 函数的全局最优解，以及使寻找过程尽量高效，就构成了机器学习的算法。

如何保证 f 函数或者 f 函数的参数空间最接近最优解，就是算法的策略。机器学习中用损失函数来评估模型是否最接近最优解。损失函数用来计算模型预测值与真实值的差距，常用的有 0-1 损失函数、平方损失函数、绝对损失函数、对数损失函数等。以平方损失函数为例，损失函数如下:

数学原理

给定模型类型，也就是给定函数类型的情况下，如何寻找使结构风险最小的函数表达式。由于函数类型已经给定，实际上就是求函数的参数。各种有样本的机器学习算法基本上都是在各种模型的假设空间上求解结构风险最小值的过程，理解了这一点也就理解了各种机器学习算法的推导过程。

机器学习要从假设空间寻找最优函数，而最优函数就是使样本数据的函数值和真实值距离最小的那个函数。给定函数模型，求最优函数就是求函数的参数值。给定不同参数，得到不同函数值和真实值的距离，这个距离就是损失，损失函数是关于模型参数的函数，距离越小，损失越小。最小损失值对应的函数参数就是最优函数。

数学上求极小值就是求一阶导数，计算每个参数的一阶导数为零的偏微分方程组，就可以算出最优函数的参数值。这就是为什么机器学习要计算偏微分方程的原因。

感知机

感知机是一种比较简单的二分类模型，将输入特征分类为 +1、-1 两类，就像下图所示的，一条直线将平面上的两类点分类。

f(x) = sign(w*x +b)

其中 x 代表输入的特征空间向量，输出空间是{-1, +1}，w 为权值向量，b 叫作偏置，

sign 是一个符号函数。

sign(x) = 1 x >=0 ; sign(x)=-1 x<0;

训练感知机模型就是要计算出 w 和 b 的值，当有新的数据需要分类的时候，输入感知机模型就可以计算出 +1 或者 -1 从而进行分类。

由于输出空间只有{-1, +1}两个值，所以只有误分类的时候，才会有模型计算值和样本真实值之间的偏差，偏差之和就是感知机的损失函数。

其中 M 为误分类点集合，误分类点越少，损失函数的值越小;如果没有误分类点，损失函数值为 0。求模型的参数 w 和 b，就是求损失函数的极小值。

数学上求函数的极小值就是求函数的一阶导数，但是感知机损失函数用统计求和函数表达，没办法计算解析解。机器学习采用梯度下降法求损失函数极小值，实质上就是求导过程的数值计算方法。

对于误分类点集合 M，损失函数 L(w,b) 变化的梯度，就是某个函数变量的变化引起的函 数值的变化，根据感知机损失函数可知:

使用梯度下降更新 w 和 b，不断迭代使损失函数 L(w,b) 不断减小，直到为 0，也就是没 有误分类点。

感知机算法的实现过程:

1. 选择初始值 w0,b0。

2. 在样本集合中选择样本数据 xi,yi。

3. 如果 yi(w⋅xi+b)<0，表示 yi 为误分类点，那么 w=w+ηyixi、b=b+ηyi，在梯度方向校正 w 和 b。其中 η 为步长，步长选择要适当，步长太长会导致每次计算调整太大出现震荡;步长太短又会导致收敛速度慢、计算时间长。

4. 跳转回 2，直到样本集合中没有误分类点， 即全部样本数据 yi(w⋅xi+b)≥0。