本文最后更新于：1 年前

这里是期末对于大数据计算课程的复习嗷！！！

内存计算模型

存储访问速度比较：

内存计算指采用了各种内存技术在计算过程中让CPU从主内存而不是从磁盘读写数据的计算模型。这里的内存技术包括列存储格式、数据分区与压缩、增量写入、无汇总表等方法。

分布式缓存体系：
- 两重含义：1. 由多台服务器组成一个缓存服务器集群，以多节点集群方式提供缓存服务，即物理架构上是分布式。2. 缓存数据（可看作一个大数据表）被分布式存储在多台缓存服务器上，即逻辑架构上也是分布式的。
分布式缓存架构：
- 缓存服务器不是把数据存储在磁盘上而是存放在内存中，多个缓存服务器按分布式共同存放一个数据表，涉及到数据同步的问题。
- 以JBoss Cache为代表。JBoss Cache的缓存服务器集群中所有节点均保存一份相同的缓存数据，当某个节点有缓存数据更新的时候，会通知集群中其他机器更新内存或清除缓存数据。
- Memchache则采用了数据不同步的架构，采用一组专用缓存服务器，缓存与应用分离部署。在存放和访问缓存数据时，通过一致性 Hash算法选择缓存节点，集群缓存服务器之间不需要数据同步，因此集群规模可以很容易地实现扩容，具有良好的可伸缩性
内存技术：

字典编码技术，包括字典编码算法、高效压缩存储、数据操作等。下图为字典编码压缩基本原理：

列存储结构，包含内存数据格式、内存索引等技术。下图为列存储结构基本原理：

一个算例：

数据表分区，对数据表的划分及多节点并行处理。分布式缓存系统主要采用水平划分和垂直划分两种方式。

只插入差异数据，只写入差异数据来提高访问效率。如图所示，在内存中划分两个区域：主表（Main）和差异表（Delta）。主表包含完整的数据，采用高度压缩的列存储方式，支持高效率的读数据操作；差异表只包
含少量的新增数据，支持写数据操作。

Memcache工作流程：
- 代表性的高性能分布式内存对象缓存系统，通过缓存数据和对象来减少读取数据库次数，从而提高数据库驱动网站的访问速度。
- 专用缓存服务器，缓存与应用分离部署。
- 一致性Hash很重要！！！
流程面经背过，看图就成。（如果内存满了，LRU或其他算法替换缓存数据）
- 计算架构：多个Memcache Server组成一个虚拟的Server。对于应用程序完全屏蔽和透明，提高内存利用率，提供优良的系统可拓展性。
- 数据项 -> 服务器映射：当一个键值对数据项被提交给memcache客户端，假设有3个节点在memchached集群中，需要一个路由算法帮助我们LB。
- 扩容 -> 命中率降低：
- 一致性Hash算法：Hash环，它跨越了长度区间[$0,2^{32}-1$]
如果扩容：

优势：影响局部，而非全局。随着节点增多，影响区域会越来越小。规模扩大 -> Hash算法的结果倾向稳定。
内存数据库技术：
- 计算架构：一个完整的数据库应用系统计算架构见图，它包含应用层、高速缓存层、内存数据库层、磁盘数据库层（持久性存储）四个层次。
- 全内存架构：为了提高数据访问，一种理想的模式是全部数据存储在内存中，所有数据计算和事务性操作都在内存中完成。问题：
  - 内存有限，一次性装载困难
  - 并非持久化存储介质，断电或重启数据就丢失
  - 拓展性差，加入新的机器，无法立即寻址，需要修改代码。
- 读写分离架构：克服全内存数据库无法提供及时的持久性存储的缺点，我们在系统中增加了磁盘存储，但为了提高数据访问速度，又在内存中
  另外实现了一套存储结构或内存数据库。
  - 读数据内存数据库（缓存），写数据写入磁盘，定期同步，达到既能保证高速访问速度、又能持久化存储数据的目的。
- 混合分区架构（Hybrid Shard）：
  - 即使采用可扩容的集群架构仍需解决内存数据持久化问题，集群分区方中采用混合模式 -> 每个分区由一个内存数据库节点和一个MySQL节点共同组成。原来一个MySQL节点承担的一个水平分区现在变成 H-Shard = MMDB + MySQL。
  - 这种混合分区数据库架构将形成水平方向的多分区、垂直方向的二级数据库。
内存数据库产品：
- SAP的HANA（High-performance Analytic Appliance），是一个软硬件结合支持内存计算模式的高性能计算分析平台。
- 主要提供数据存储、预处理、计算分析、支持
  行存储和列存储两种结果、事务处理、数据访问、持久化存储等功能和服务。除了数据持久化存储这一功能，其他功能和操作都在内存中完成
MemCloud计算架构：
- 每个节点包含Master和Backup两个模块。Master模块管理节点主内存，负责Clinet程序的读写数据妖气。Backup模块负责管理节点本地磁盘和闪存，以及存储在磁盘上的其他节点数据文件的副本。
- 数据存储架构：简单的键值对数据结构，封装为Object，每个Object被长度不一的唯一的Key标记。Object的操作都是原子的。Object的大小介于几十bytes到1MB之间，一般使用较小单位。多个Objects 组成一个Table，一个Table可以有多个副本存放在集群不同节点上。下图描绘了RAMCloud的数据模型。
节点存储结构：
- RAMCloud在每个集群节点上的Master程序管理着存放在内存里的一组Objects和一个哈希表，表里面每一条entry都对应着内存里存放的一个Object。多个Objects组成内存里一个Segment (64MB)。
- 每个Segment生成2~3个副本，分散在集群中其他节点持久化存储在当地磁盘上，由Backup程序管理。
内存清除机制：
- 内存空间在使用一段时间后，不可避免地有一些Log会失效，一些Log空间没有使用完，即内存碎片化。由于内存空间非常宝贵，RAMCloud设计了一套内存清除机制来有效地使用和管理内存。
内存清除效率：
- 当内存使用率低时（有较多空余内存空间），进行内存清除工作有较高收益；内存使用率高时（空余内存空间已很小），内存清除的收益就很低。
- 另外注意到RAMCloud在Master内存和Backup磁盘上保留了两套Segment体系，清楚工作也需要对于两套体系完成。当内存使用率高时（80~90%），与内存清除同时进行的磁盘清除占用了大量的网络带宽（这时磁盘使用率也高，迁移数据需要很大的开销），影响了集群写入数据（Write Data）的效率（Throughput）
- RAMCloud的设计目标是达到内存高使用率的同时，也要有较高的写数据效率（Write Throughput）。对比内存与磁盘的性能特点可看出，内存空间昂贵，但读写带宽足够；磁盘存储空间廉价富余，但带宽有限。如何把性能特点相差悬殊的两种存储结构放在一个清除流程中达到较理想效果
RAMCloud Two-level Cleaning机制：

Spark内存计算

逻辑计算模型：

MapReduce Computing VS Spark Computing:

Spark功能框架：SQL：SQL查询，Hive进行HQL解析，翻译为Spark上的RDD操作。Core：内存计算模型。DAG的分布式并行计算框架，支持内存迭代计算和数据共享（减少了迭代的I/O开销）。Streaming：支持流计算，流数据按照batch size分成数据段，转换为RDD，操作变成中间结果保存在内存中。GraphX；图并行框架。MLBase：机器学习组件库。
计算架构：M/S结构。主节点（Master）：部署有ClusterManager（Standalone模式是 Master程序，分布式模式是YARN 的ResourceManager），工作节点（Worker）：部署有YARN的 NodeManager， ApplicationMaster，Executor，以及由Executor启动的Task线程；客户端节点（Client）：应用程序Application。运行模式：Standalone模式，YARN-Client模式，YARN-Cluster模式。
RDD数据模型：弹性分布式数据集，即一组不可改变、可并行计算、分区的（partitioned）数据集集合。 RDD既是一个数据模型也是一个内存抽象模型。在逻辑结构上，RDD 可以理解为一个数组，数组的元素即是分区Partition；在物理数据存储上，RDD的每一个Partition对应的就是一个数据块Block，Block可以有多个副本，分别存储在不同节点的内存中，当内存不够时还可以持久化存储到磁盘上

五个属性：一个RDD有多个分区。作函数作用在每一个分区中。一个RDD会依赖其他RDD。（可选）针对于kv类型的rdd才会有分区函数（必须要产生shuffle），分区函数就决定了数据会流入到子rdd的那些分区中。（可选）一个列表，存储每个Partition的优先位置，数据位置最优(spark在进行任务分配的时候，会优先考虑存有数据的worker节点来进行任务计算)。
RDD特点：RDD本身不被改变，只会创造新的RDD，但是需要记录转换过程，支持同步和可重算性。分布存储，分区的数据经济，以分区为最小存储和处理单位，来优化存储结构。一个Task对应一个partition，Task之间相互独立，并行计算。基于Lineage的高容错性，丢失不用做checkpoint，可以根据L重新计算出来。可序列化，可通过存储级别重用，空间不足RDD存在磁盘。
RDD算子：
- 算子是RDD中定义的外部函数，可以对RDD中的数据进行转换和操作。
- RDD算子有转换（Transformation）和操作（Action）两种。其中，转换又分为数值型和键值对型两种。
- Transformation 按照一定的准则将一个RDD转换生成另一个新 RDD，即返回值还是一个RDD。但Transformation属于延迟转换，即对一个RDD执行Transformation动作时并不是立即进行转换，而是记住其执行逻辑，等到有Action操作的时候才真正启动转换过程完成计算。Transformation算子有map, filter, join, cogroup, …等多种类型
- Action 是完成对RDD的计算后返回结果或把RDD写到存储系统中，它也是触发Spark计算流程的动因，Action的返回值不是一个RDD。Action算子有count, collect, reduce, lookup和save等操作
- 算子列表：
RDD依赖与血缘（Lineage）：
- 依赖关系：
  - Transformation产生一个新的RDD，新旧RDD之间（又称父子RDD）会形成一个前后依赖关系，即所谓的dependency。Spark中存在两种依赖关系
  - 窄依赖：父RDD的每一个分区最多被子RDD的一个分区所用，表现为父RDD的一个分区对应于子RDD的一个分区或父RDD的多个分区对应于子RDD的一个分
    区，即转换前后父子的分区对应关系是一对一或多对一映射。
  - 宽依赖：：子RDD的一个分区依赖于父RDD的所有分区或多个分区，父RDD的一个分区会被子RDD 的多个分区使用，即转换前后父子的分区对应是一对多或多对多映射
- 特点：
  - 窄：父一个最多只能被用一次。宽：存在一个被用了多余一次。
  - 窄：由于前后RDD的分区是一对一或多对一关系，所以当某个节点失败后只需重新计算父节点的分区即可。
  - 宽：宽依赖是一对多映射，重算的父RDD分区对应多个子RDD分区，这样父RDD中只有一部分数据是被用于恢复这个丢失的子 RDD分区，而另一部分数据对应子RDD的其它未丢失分区，这就造成了多余计算。更一般的情况，宽依赖子RDD分区通常来自多个父RDD分区，极端情况下所有的父RDD分区都要进行重新计算；
- 血缘关系：
  - 惰性调用，每个RDD记录父RDD转换，指导一个操作触发了一系列转换，构成了一个链表，血缘关系图也就是计算模型的DAG
  - 程序例子：
  计算模型：
算例很重要！！！

又一个算例（分词）：

一，需要将文件内容读取到计算节点内存，同时对数据进行分片；二，对于每个数据分片，我们要将句子分割为一个个的单词；
三，同样的单词可能存在于多个不同的分片中（如单词 I），因此需要对单词进行分发，从而使得同样的单词只存在于一个分片之中；
四，最后，在所有分片上计算每个单词的计数。

Spark作业模型：
- 上层包括Job，Stage，Task等计算项，由DAGScheduler完成划分调派
- 下层包括Worker，Executor，Thread，由SchedulerBackend负责分派
- 上层计算任务的调度（即如何将具体的 RDD分区映射到 Worker上的Task线程，或者说如何将Task分发到集群的Worker节点上去执行）则是由 TaskSetManager通过 TaskScheduler与下层的计算资源管理器（SchedulerBackend）的协调来实现

Job调度算法：

在Application内部，调度流程如图所示，RDD处理流程构成一个 DAG，然后由DAGScheduler按照shuffle dependency将DAG划分成多个Stage，每个Stage包含的分区组成一个TaskSet，DAGScheduler通过TaskScheduler接口提交TaskSet，这个TaskSet最终会触发TaskScheduler构建一个TaskSetManager的实例。

FIFO调度策略：