架构师训练营第 13 周学习总结

13.1 大数据计算引擎Spark（上）

• Spark 特点（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

• 跟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 分片，并不是根据转换函数名就能判断出来的。

13.2 大数据计算引擎Spark（下）

• Spark 的计算阶段

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

• Spark 作业调度执行的核心是DAG，有了DAG，整个应用就被切分成哪些阶段，每个阶段的依赖关系也就清楚了。之后再根据每个阶段要处理的数据量生成相应的任务集合（TaskSet），每个任务都分配一个任务进程去处理，Spark 就实现了大数据的分布式计算。

• 负责Spark 应用DAG 生成和管理的组件是DAGScheduler，DAGScheduler 根据程序代码生成DAG，然后将程序分发到分布式计算集群，按计算阶段的先后关系调度执行。

• 那么Spark 划分计算阶段的依据是什么呢？显然并不是RDD 上的每个转换函数都会生成一个计算阶段，比如上面的例子有4 个转换函数，但是只有3 个阶段。

• 当RDD 之间的转换连接线呈现多对多交叉连接的时候，就会产生新的阶段。一个RDD 代表一个数据集，图中每个RDD 里面都包含多个小块，每个小块代表RDD 的一个分片。

• Spark 也需要通过shuffle 将数据进行重新组合，相同Key 的数据放在一起，进行聚合、关联等操作，因而每次shuffle 都产生新的计算阶段。这也是为什么计算阶段会有依赖关系，它需要的数据来源于前面一个或多个计算阶段产生的数据，必须等待前面的阶段执行完毕才能进行shuffle，并得到数据。

• 计算阶段划分的依据是shuffle，不是转换函数的类型，有的函数有时候有shuffle，有时候没有。

• 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 反射加载后开始执行。

• Spark 生态体系

13.3 流处理计算：Flink、Storm、Spark Streaming

• Storm 实时的Hadoop

• 实时计算系统

• 低延迟

• 高性能

• 分布式

• 可伸缩

• 高可用

• 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。

• Spark Streaming

• Flink

• Flink流处理计算

StreamExecutionEnvironment see = StreamExecutionEnvironment.getExecutionEnvironment();

DataStream<WikipediaEditEvent> edits = see.addSource(new WikipediaEditsSource());

• Flink批处理计算

ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();

DataSet<String> text = env.readTextFile("/path/to/file");

13.4 大数据基准测试工具HiBench

HiBench 是Intel 开放的一个Hadoop Benchmark Suit，包含9个典型的Hadoop 负载

• Micro benchmarks

• Sort

• WordCount

• TeraSort

• HDFS benchmarks

• DFSIO

• web search benchmarks

• Nutch indexing

• PageRank

• machine learning benchmarks

• Mahout Bayesian classification

• Mahout K-means clustering

• data analytics benchmarks

• Hive Query Benchmarks

主页是：https://github.com/intel-hadoop/hibench

13.5 大数据分析与可视化

• 互联网运营常用数据指标

• 新增用户数

• 新增用户数是网站增长性的关键指标，指新增加的访问网站的用户数（或者新下载App 的用户数），对于一个处于爆发期的网站，新增用户数会在短期内出现倍增的走势，是网站的战略机遇期，很多大型网站都经历过一个甚至多个短期内用户暴增的阶段。新增用户数有日新增用户数、周新增用户数、月新增用户数等几种统计口径。

• 用户留存率

• 新增的用户并不一定总是对网站（App）满意，在使用网站（App）后感到不满意，可能会注销账户（卸载App），这些辛苦获取来的用户就流失掉了。网站把经过一段时间依然没有流失的用户称作留存用户，留存用户数比当期新增用户数就是用户留存率。

• 用户留存率= 留存用户数/ 当期新增用户数

• 计算留存有时间窗口，即和当期数据比，3 天前新增用户留存的，称作3 日留存；相应的，还有5 日留存、7 日留存等。新增用户可以通过广告、促销、病毒营销等手段获取，但是要让用户留下来，就必须要使产品有实打实的价值。用户留存率是反映用户体验和产品价值的一个重要指标，一般说来，3 日留存率能做到40% 以上就算不错了。和用户留存率对应的是用户流失率。

• 用户流失率= 1 - 用户留存率

• 活跃用户数

• 用户下载注册，但是很少打开产品，表示产品缺乏黏性和吸引力。活跃用户数表示打开使用产品的用户数，根据统计口径不同，有日活跃用户数、月活跃用户数等。提升活跃是网站运营的重要目标，各类App 常用推送优惠促销消息给用户的手段促使用户打开产品。

• PV

• 打开产品就算活跃，打开以后是否频繁操作，就用PV 这个指标衡量，用户每次点击，每个页面跳转，被称为一个PV（Page View）。PV 是网页访问统计的重要指标，在移动App上，需要进行一些变通来进行统计。

• GMV

• GMV 即成交总金额（Gross Merchandise Volume），是电商网站统计营业额（流水）、反映网站营收能力的重要指标。和GMV 配合使用的还有订单量（用户下单总量）、客单价（单个订单的平均价格）等。

• 转化率

• 转化率是指在电商网站产生购买行为的用户与访问用户之比。

• 转化率= 有购买行为的用户数/ 总访问用户数

• 数据可视化图表与数据监控

• 折线图

• 折线图是用的最多的可视化图表之一，通常横轴为时间，用于展示在时间维度上的数据变化规律，正向指标（比如日活跃用户数）斜率向上，负向指标（比如用户流失率）斜率向下，都表示网站运营日趋良好，公司发展欣欣向荣。

• 散点图

• 数据分析的时候，散点图可以有效帮助分析师快速发现数据分布上的规律与趋势，可谓肉眼聚类算法。

• 热力图

• 热力图用以分析网站页面被用户访问的热点区域，以更好进行页面布局和视觉展示。在地图上展示的热力图则表示了该地区的拥堵和聚集状态，方便用户进行出行规划。

• 漏斗图

• 漏斗图可谓是网站数据分析中最重要的图表，表示在用户的整个访问路径中每一步的转化率。

13.6 网页排名算法PageRank

• 网页排名算法PageRank

• PageRank，网页排名，又称网页级别，Google 左侧排名或佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的技術，而作为网页排名的要素之一，以Google 公司創辦人拉里·佩奇（Larry Page）之姓來命名。

• PageRank 让链接来「投票」

• PageRank 通过网络浩瀚的超链接關係来确定一个页面的等级。Google 把从A 页面到B 页面的链接解释为A 页面给B 页面投票，Google 根据投票来源（甚至来源的来源，即链接到A 页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

• 一个页面的「得票数」由所有链向它的页面的重要性來决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank 是由所有链向它的页面（「链入页面」）的重要性经过递归算法得到的。一个有較多链入的页面会有較高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。

• 互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减，显然不合理。

• 为了解决这个问题。我们想象一个随机浏览网页的人，假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。

• PageRank 计算公式

13.7 分类和聚类算法

• KNN 分类算法

• KNN 算法，也叫K 近邻（K Nearest Neighbour）算法

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

• 数据的距离算法

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

• 欧氏距离计算公式

• 余弦相似度计算公式

• 提取文本的特征值TF-IDF 算法

• TF 是词频（Term Frequency），表示某个单词在文档中出现的频率。



• IDF 是逆文档频率（Inverse Document Frequency），表示这个单词在所有文档中的稀缺程度。



• 贝叶斯分类算法

• 贝叶斯公式

• K-means 聚类算法



13.8 推荐引擎算法

• 基于人口统计的推荐

• 根据用户标签，向同类用户推荐

• 基于商品属性的推荐

• 根据商品属性，推荐同类商品

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

• 根据用户喜欢的商品，向同类用户推荐

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

• 根据商品的被喜欢，向喜欢同类商品的用户推荐

13.9 机器学习与神经网络算法

• 机器学习系统架构

• 样本

• 样本就是通常我们常说的“训练数据”，包括输入和结果两部分。比如我们要做一个自动化新闻分类的机器学习系统，对于采集的每一篇新闻，能够自动发送到对应新闻分类频道里面，比如体育、军事、财经等。这时候我们就需要批量的新闻和其对应的分类类别作为训练数据。通常随机选取一批现成的新闻素材就可以，但是分类需要人手工进行标注，也就是需要有人阅读每篇新闻，根据其内容打上对应的分类标签。

• T=(x1,y1),(x2,y2),…,(xn,yn)

其中xn 表示一个输入，比如一篇新闻；yn 表示一个结果，比如这篇新闻对应的类别。

• 模型

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



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

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



这时候需要计算的就是a1 和a0 两个参数的值。这种情况下模型的假设空间的数学表示是：



其中θ 为f 函数的参数取值空间，一个n 维欧氏空间，被称作参数空间。

• 算法

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

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

• 对于一个给定的样本数据集，模型f(X) 相对于真实值的平均损失为每个样本的损失函数的求和平均值，这个值被称作经验风险，如果样本量足够大，那么使经验风险最小的f 函数就是模型的最优解。

• 但是相对于样本空间的可能取值范围，实际中使用的样本量总是有限的，可能会出现使样本经验风险最小的模型f 函数并不能使实际预测值的损失函数最小，这种情况被称作过拟合，即一味追求经验风险最小，而使模型f 函数变得过于复杂，偏离了最优解。这种情况下，需要引入结构风险以防止过拟合。

• 在经验风险的基础上加上λJ(f)，其中J(f) 表示模型f 的复杂度，模型越复杂，J(f) 越大。要使结构风险最小，就要使经验风险和模型复杂度同时小。求解模型最优解就变成求解结构风险最小值。

• 机器学习的数学原理

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

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

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

• 感知机

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

• 神经网络