本文是一篇软件工程硕士论文，本文对 Spark 框架的缓存替换策略和 DBSCAN 聚类算法展开研究，并提出改进缓存替换策略及并行化改进 DBSCAN 聚类算法，对 Spark 执行缓存展开优化，提升大数据量样本集密度聚类分析的性能和准确率。但考虑到 Spark 集群环境运行机制，聚类并行化算法设计模型等因素。
1 绪论
1.1 课题研究背景
据权威机构Statista 统计，2020 年全球统计数据量达到了 47ZB，在 2035 年统计数据量将会达到 2142ZB，数据在未来还会有更大规模上升。近年来不断推进数字化转型经济，伴随着 5G，物联网，人工智能等领域的不断发展，大数据已成为信息时代最为重要的信息资源[1]。挖掘数据价值成为各个领域发展的关键因素，各国各地区之间也在部署大数据战略，推动着大数据创新发展和大数据产业成型[2]。在大数据深入发展的过程中，数值分析上逐渐出现性能瓶颈，单体服务计算模式已无法适应海量数据增长，挖掘出的数据价值只占据总量的一小部分。
为应对大数据分析能力与海量数据不匹配的问题，研究产生了 Hadoop，Spark 以及Storm 等分布式计算框架。Hadoop 采用分布式计算架构，MapReduce 计算模式，计算出入口与 HDFS 结合，在各节点间降低分布式服务器计算交互通信代价，以此应对海量数据迭代任务与分析计算。MRv1 版本存在可扩展性不足，可用性差，资源利用率低等缺点。MRv2 对原版本进行改进，但依然存在持久化结果数据，数据信息备份，磁盘 I/O次数过多等问题影响计算性能[3]。
Spark 内存计算框架在 MapReduce 计算模式基础上进行改进。Spark 设置内存空间，存储 RDD 中间计算数据以及最终计算数据，DAG 执行引擎有相同性能，避免过多的磁盘 I/O 和重复任务，提升数据分析的速度和能力。Spark 也支持结合 Hive SQL 以及Streaming 实时流计算。Spark 有不同的集群管理器部署模式，如 Standalone，EC2，YARN以及 Mesos 等。Spark 可以使用多种数据源，可用内置文件系统和 HDFS，还可以结合Hbase，Hive，Tachyon 以及 Cassandra，极大方便各个大数据体系互相迁移。
..........................
1.2 研究现状
1.2.1 Spark 缓存替换算法研究现状 Spark 缓存替换内核运用 LRU 算法，LRU 考虑到 RDD 时间间隔影响因素，但在复杂 Spark 计算迭代模型和分布式环境中需考虑复合型影响因子，许多学者对改进缓存替换算法展开研究。
（1）采用包括 FCFS[6]，MRU[7]，RR[8]等缓存替换算法。FCFS 算法表现为先来先服务特性，在 RDD 分区计算中对应存入时间影响因子，但如果在 RDD 计算过程中存在跨度过大的时间线任务，会导致缓存替换频繁抖动，造成缓存命中率下降资源消耗增多。MRU 算法表现最近最常使用替换特性，该算法在父 RDD 计算重复性高，且子 RDD 计算重复性低的迭代模型中有较高缓存命中率，但限制条件较为严苛，计算不符合条件的迭代模型会降低运行效率。RR 算法核心是将 Cache 区域划分成不同单元，根据不同的Cache 单元位置完成 RDD 缓存替换，该算法考虑到 RDD 存放位置影响因素，但依然存在影响因子单一的情况，影响 RDD 缓存替换命中率。
（2）RDD 缓存替换策略第二个改进方向侧重于优化 JVM 和 GC 内存管理机制，以及建立可存入缓存的分布式文件系统。Ziyao Zhu[9]等提出 MCS 内存约束管理替换策略，优化 GC 造成的运行时缓存开销，包括优化缓存逐出开销和缓存重新计算开销。Luna Xu[10]等提出 MEMTUNE 内存数据分析平台动态内存管理方案，统计 GC 持续时间和内存分页频率等运行信息来动态监控内存的使用状态，并通过监控内存状态参数来动态调整缓存分区大小，利用配置预取逐出策略，提高 RDD 缓存替换的命中率和运行性能。分布式文件系统采用 UCBerkeley 开发的 Tachyon 文件系统[11]，它独立存在于计算框架和存储系统之间，用 lineage 信息以及异步记录 Checkpoint 来恢复数据，可用 Tachyon实现内存管理，减少磁盘 I/O，提升执行性能和效率。
.............................
2 相关技术介绍
2.1 Spark 框架相关技术
2.1.1 Spark 架构与数据集 RDD
Spark 框架由加州大学伯克利分校 AMP Lib 研究并开发，之后成长为 Apache 组织的顶级项目。Spark 框架可处理大数据级规模信息并展开分析计算，在计算结构上，沿用了 Hadoop 框架的 MapReduce 计算模式，此外框架具有分区伸缩，内存空间计算等特性。Spark 可灵活配置整合其它组件，包括读写 Hadoop 上任何格式的数据，可结合多种大数据数据源。Spark 在实现批处理计算时相较于 Hadoop 要更加高效，运行延迟更低。
Spark 已逐渐发展成为轻量级分布式基于内存计算的快速计算分析平台框架，在数据分析，计算挖掘，实时处理，机器学习，图型计算等领域应用广泛[25]。Spark 框架体系结构如图 2.1 所示。
图 2.1 Spark 大数据分析平台体系图
.......................
2.2 聚类算法相关技术
2.2.1 聚类算法介绍
聚类分析简称为聚类，其定义是将样本数据集划分成不同小的数据集。划分成的每个子集中数据属性相似，但对于不同子集之间样本信息特征不同，针对数据特征提出不同的聚类算法加以分析，选取较优方式获取聚类结果。聚类属于无监督学习范畴，其中聚类数据在训练之前的标记信息显示为未知状态，通过对此未知性数据训练获取信息规律，以便对数据样本展开进一步分析。
聚类应用范围广泛，涉及包括数据挖掘，智能分析，生物科技，网络搜索，图像模式识别等众多研究领域。在数据挖掘研究领域中，不断寻找为大型数据集展开有效聚类分析的方法。
需要聚类算法具有可伸缩性，应对数以亿计训练对象的聚类计算，可以处理不同属性不同类型样本数据，应对训练数据样本的复杂性；可以发现任意形状类簇，应对聚类中非球状数据分布；有设置输入参数的方法，弥补参数敏感和参数确定困难的不足；有处理噪声数据的能力，避免存在噪声敏感的数据聚类造成结果准确率降低；对增量数据和迭代顺序没有明确限制，应对随时产生的数据更新和计算不确定性，使得聚类结果数据不会产生较大波动；需具有高维数据聚类以及在一定特殊条件下聚类的能力。
各研究学者提出不同的聚类算法，算法根据其聚类特性大致可以分为：基于距离的划分方法，为使聚类最优，会列举所有可能的划分情况；基于自底向上思想的层次方法，初始将自身样本数据单独作为一个类，之后逐步合并相近的样本，最后将所有组合合并成一个组；基于密度的方法，弥补数据样本无法聚类不同形状类簇的不足；基于网格的方法，将样本数据量划成不同的网格单元，使各个样本隶属于其中一个网格，在网格中展开聚类分析，突出快速处理数据的特点。
..................
3 动态选择 RDD 缓存替换算法 DSR-CRA......................30
3.1 Spark 缓存替换算法的问题......................30
3.2 DSR-CRA 算法整体改进分析......................30
4 并行化改进聚类算法 SDKB-DBSCAN......................38
4.1 DBSCAN 聚类算法的问题...................38
4.2 并行化改进算法整体分析...................38
5 实验结果与分析...................45
5.1 动态选择 RDD 缓存替换算法实验................45
5.1.1 实验环境................45
5.1.2 实验过程与分析................45
5 实验结果与分析
5.1 动态选择 RDD 缓存替换算法实验
5.1.1 实验环境
基于 ITCE-RRWM 排序权重模型的动态选择 RDD 缓存替换算法 DSR-CRA 的优化步骤和算法分析，对源码展开修改实现了改进算法 DSR-CRA，并与 Spark 中 LRU 替换算法以及赋值权重模型 AWMRS 替换算法[51]展开对比实验。验证 DSR-CRA 改进算法在Spark 计算模型中 RDD 分区缓存命中率是否提高，以及在 Spark 集群各服务器资源消耗是否减少，分析改进算法在大数据环境下是否具有可用性和高效性。
实验中对 Spark2.4.3 版本 Storage 模块中 BlockManager、MemoryStore 等组件源码进行修改，将动态选择 RDD 缓存替换算法 DSR-CRA 添加入 Storage 模块，并在修改后将 Spark 源码重新编译，并部署到 Spark 分布式集群当中。本文实验是按照五台服务器展开 Spark 集群配置，其中一台 Master 服务器，四台 Slave 服务器，每台服务器性能配置项如下表 5.1 所示。
表 5.1 实验服务器性能配置
.........................
6 总结与展望
6.1 研究总结
在大数据技术快速发展驱动之下，Spark 计算框架处理大数据计算需求的重要性日益明显。Spark 缓存替换算法是影
