架构师训练营 -week13- 学习总结

Spark

特点

• DAG（Directed Acyclic Graph）切分的多阶段计算过程更快速

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

• RDD（Resilient Distributed Datasets）的编程模型更简单

对比MapReduce

• 可做更复杂的大数据计算，多次迭代，中间过程的输出可作为下次计算的输入。

• 使用内存存储，读写数据更快。

• 面向数据编程更直观。

• 不需要关心中间过程

Shuffle

不同于MapReduce，Spark的Shuffle过程对用户透明化了，并且不会总是触发Shuffle。

只有在生成新的RDD时，才会根据key进行Shuffle。

窄依赖（无shuffle依赖）

部分操作不会产生新的分片，map、filter等操作在物理上不会生成一个新的RDD，这个过程不需要进行shuffle。

宽依赖（shuffle依赖）

reduceByKey、groupByKey、partitionBy等操作，需要将不同分片相同key聚合在一起的操作，会产生新的RDD分片，这个过程会触发Shuffle。

PS：是否会产生新的RDD分片，并不能根据转换函数名就能判断出来。

计算阶段

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

调度核心

DAG

生成和管理DAG的组件

DAGScheduler。

根据程序代码生成DAG，然后将程序分发到分布式计算集群，按计算阶段的先后关系调度执行。

划分计算阶段的依据

Shuffle

作业管理

Spark里的RDD函数有两种，一种是转换函数，调用以后得到的还是一个RDD。

另一种是action函数，调用以后，不再返回RDD。

当DAGScheduler在遇到shuffle的时候，会生成一个计算阶段；

在遇到action是，会生成一个作业（job）

PS：RDD里的每个数据分片，Spark都会创建一个task去处理，所以一个计算阶段会包含多个task。

执行过程

Spark应用程序启动在自己JVM进程里，即Driver进程，启动后调用SparkContext初始化执行配置和输入数据。

SparkContext启动DAGScheduler构造执行的DAG图，切分成最小的执行单位，即计算任务。

Driver向Cluster Manager请求计算资源，用于DAG的分布式计算。

Cluster Manager收到请求后，将Driver的主机地址等信息通知给集群的所有计算节点Worker

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

Worker收到任务后，启动Executor进程开始执行任务。

Executer先检查自己是否有Driver的执行代码，如果没有，从Driver下载执行代码，通过Java反射加载后开始执行。

时序图

流计算

实时计算

本质上是实时对几毫秒、几秒的数据进行批数据计算。

实时计算系统

• 低延迟

• 高性能

• 分布式

• 可伸缩

• 高可用

Storm

基本概念

Nimbus：负责资源分配与资源调度，类Spark的Cluster Manager。

Supervisor：负责接收Nimbus分配的任务，启动和停止属于自己管理的Worker进程，类Spark的Worker。

Worker：运行具体处理组件逻辑的进程，类Spark的Executor。

Task：Worker中每一个Spout/Bolt的线程称为Task，同Spark的计算任务。

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

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

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

Tuple：一次消息传递的基本单元，是一个key-value的map，但由于各个组件间传递的tuple的字段名已经实现定义好了，所以tuple只要按序填入value即可。

Stream：源源不断传递tuple就形成了stream。

Steam Grouping

定义了一个流在Bolt任务间该如何被切分。Storem提供了6种Stream Grouping类型：

• 随机分组（Shuffle Grouping）

• 字段分组（Fields Grouping）

• 全部分组（All Grouping）：tuple被复制到Bolt的所有任务，慎用。

• 全局分组（Global Grouping）：全部流分配到ID最小的Task。

• 无分组（None Grouping）：目前，该类型等效于随机分组。

• 直接分组（Direct Grouping）：tuple的生产者决定tuple去哪个Bolt。

以及CustomStreamGrouping接口。

应用场景（淘宝）

被广泛用来进行实时日志处理，出现在实时统计、实时风控、实时推荐等场景中。

Storm往往会配合分布式存储服务一起使用。例如个性化搜索实时分析项目中，就使用了TimeTunnel+HBase+Storm+UPS的架构，每天处理几十亿的用户日志，从用户行为发生到完成分析延迟在秒级。

Spark Streaming

Flink



HiBench

一个数据库基准测试套件，可帮助评估大数据框架的速度、吞吐量和系统资源利用率。

Micro Benchmarks

Sort

WordCount

TeraSort

HDFS Benchmarks

DFSIO：产生大量同时执行读写请求的任务测试HDFS吞吐量。

Web Search Benchmarks

Nutch indexing：使用自动生成的Web数据，Web数据中的链接和单词符合Zipfian分布。

PageRank

Data Analytics Benchmarks

Hive Query Benchmarks（hivebench）：包含执行典型OLAP查询的Hive查询。

Machine Learning Benchmarks

Mahout Bayesian classification：Naive Bayesian训练器，输入数据是自动生成的文档，文档中的单词符合Zipfian分布。

Mahout K-means clustering：输入数据集由基于均匀分布和高斯分布的GenKMeansDataset产生。

大数据可视化

互联网运营常用数据指标

• 新增用户数：日新增、周新增、月新增等统计口径。

• 用户留存率：留存用户数/档期新增用户数。

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

• 活跃用户数：打开使用产品的用户数，由日活跃、月活跃等统计口径。

• PV（Page View）：用户每次点击，每个页面跳转，被称为一个PV。是网页访问统计的重要指标。

• GMV（Gross Merchandise Volume）：电商网站统计总营业额（流水），配合使用的还有订单量、客单价。

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

数据可视化图表和数据监控

折线图：展示时间维度上的数据变化规律。

散点图：可快速发现数据分布的规律与趋势。

热力图：分析用户访问的热点区域。

漏斗图：常用于表示在用户的整个访问路径中每一步的转化率。

大数据算法和机器学习

PageRank

基础公式

PR为权重，L为出链数。在理想状态下，页面i的权重是所有链接到该页面的页面平均投票权重的总和。

在初始化阶段，设所有页面的权重都为1，根据以上公式进行迭代计算，更新各个页面的PR值，直到PR值收敛。

终止点





终止点是指一个没有任何出链的网页，如图中C点。

在基础公式中，终止点会导致转移矩阵终止转移概率，最后迭代的结果是所有的网页PR值都是0。

因此当访问到终止点时，以等概率跳转到下一个网页。该概率为1/矩阵行数。

陷阱





陷阱/黑洞指的是只有指向自身链接的网页，如图中C点。

根据基础公式多次迭代，会使得陷阱页面的PR值为1，而其他正常网页的概率为0。

为了解决这个问题，就有了随机浏览模型。

随机浏览模型

假定一个用户从一个随机的网页开始浏览，此时有两种选择：

• 通过点击当前页面的其他链接开始下一次浏览；

• 通过在浏览器的地址栏输入新的地址以开启新的页面。

假设点击链接开启新页面的概率为d（阻尼系数，通常取0.85）.则随机浏览模型公式为

其中d为阻尼系数，N为所有页面的数量。

链接农场

指由互联网中的一部分网页组成，这些网页非常密集地互相连接在一起。通过创建一个堆砌大量链接而没有实质内容的网页，这些链接彼此互链，或指向特定网站，以提高某个或者某些特定网页的 PageRank 值。

黄金链

指一些高权重的网站出售首页的链接给作弊网站，以提高作弊网站的 PageRank 值。

作弊

通过链接农场、黄金链，进行链接作弊。

缺点

• 主题漂移：忽略了主提相关性。

• 没有过滤广告链接和功能链接

• 对新网页不友好

其他搜索引擎算法

• 社会化搜索：除了搜素结果和相关性，还有搜索可信赖性。

• 实时热搜

• 多媒体搜索

KNN分类算法

也叫K近邻（K Nearest Neighbour）算法。

准备好一组已经分类标注好的样本集合，将需要分类的数据，与样本集合进行比较。

得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类的数据的类别。

数据的距离算法

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

欧式距离公式

余弦相似度公式



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

TF：Tearm Frequency，词频，表示某个单词在文档中出现的频率。

IDF：Inverser Document Frequency，表示这个单词在所有文档中的稀缺程度。

贝叶斯分类算法

贝叶斯（条件概率）公式

分类流程

K-means聚类算法

接受一个未标记的数据集，然后将数据聚成不同的组，是一种无监督学习算法。

算法步骤

1. 随机选取k个点，作为聚类中心；

2. 计算每个点分别到k个聚类中心的聚类，然后将该点分到最近的聚类中心，这样就行成了k个簇；

3. 再重新计算每个簇的质心（均值）；

4. 重复以上2~4步，直到质心的位置不再发生变化或者达到设定的迭代次数。

推荐引擎算法

基于人口统计的推荐

通过对用户的基础信息进行分类推荐。

基本商品属性的推荐

基于用户的协同过滤推荐

基于商品的协同过滤推荐

神经网络

感知机

一种比较见到那的二分类模型，其输入特征分类为+1、-1两类。

感知机模型

感知机输入权值

一个感知机可以接收多个输入，每个输入上有一个权值w，此外还有一个偏置项b。

激活函数

• 阶跃函数

• sigmoid函数

• relu函数

感知机输出空间

损失函数

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

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

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

神经网络

两层以及两层以上的感知机，组成了神经网络。