mateizaharia-基于大型集群的快速通用数据处理架构

过去的几年中,计算系统经历着重大的变革,为了满足不断增长的数据量和处理速度需求, 越来越多的应用向分布式系统扩展。如今,从互联网到企业运作,再到科技设备,不尽其数的 数据源都在产生大量的、有价值的数据流。然而,单一的机器处理能力并没有跟上数据增长的 速度,使得这些有价值的数据越来越难以被使用。以至于越来越多的组织——不仅仅是互联网 公司,还有一些传统企业和研究室——迫切需要将他们重要的计算能力扩展到成百上千台机器 上去。 在这同时,数据处理所需的速度和复杂性也在逐渐增加。在许多领域中,除了简单的查询, 像机器学习和图分析这样的复杂算法也得到日益广泛的应用。另外,除了批量处理,一些组织 还需要在实时数据源上进行流分析,以保证能够及时采取行动。未来的计算平台不仅需要能满 足常规作业的扩展,同时也需要对新的应用有更好的支持。 针对上述的各种问题,本文提出了一种集群计算架构,能够解决这些新出现的数据处理作业 的需求,同时还可以应对越来越大规模的扩展。虽然早期的集群计算系统,如 MapReduce,已经 能够进行批量处理,但我们的架构更支持流处理和交互查询,并且拥有和之前系统相同的可扩 展性和容错性。然而当前所部署的大部分的系统仅支持简单的单路运算(例如,聚 合或 SQL 查询), 而我们的系统针更为复杂的分析(例如,机器学习的迭代算法)扩展到了对多路算法的支持。 最后,与处理特定工作的专有系统不同的是,我们的架构允许这些算法相互结合,从而实现更 丰富的新应用。例如,流处理和批量处理,或 SQL 和复杂分析之间的相互结合。 为了实现上述的各种特性,我们通过简单的扩展 MapReduce,为其增加了数据共享原语,也 就是所谓的弹性分布式数据集(RDDs)。我们发现,这样的扩展足以能够有效地覆盖大部分作业 的需求。在开源的 Spark 系统中我们实现了 RDDs,同时使用了模拟测试程序和真实的用户应用 对其进行评估。在许多应用领域中,Spark 已经接近或是超过了专有系统的性能,同时提供更强 大的容错保证,并允许这些作业之间能够进行结合。我们从理论建模和实践的角度去探索 RDDs 的通用性,来解释为什么这样的扩展可以覆盖大范围的不同作业需求。 第 1 章 简介 .................................................................... 1 1.1 专业系统相关的问题 .................................................. 2 1.2 弹性分布式数据集(RDDS) ............................................ 3 1.3 基于 RDD 机制实现的模型 .............................................. 4 1.4 总结................................................................ 6 1.5 论文计划............................................................ 7 第二章 弹性分布式数据集 ........................................................ 8 2.1 2.2 2.3 2.4 2.5 简介................................................................ 8 RDD 概述 ........................................................... 10 2.2.1 概念 ........................................................... 10 2.2.2 Spark编程接口....................................................10 2.2.3 RDD 模型的优点 ................................................. 13 2.2.4 不适合 RDDs 的应用 .............................................. 14 Spark 编程接口 ..................................................... 15 2.3.1 Spark 中 RDD 的操作 ............................................. 17 2.3.2 应用示例 ....................................................... 17 抽象 RDDs .......................................................... 20 实现............................................................... 22 2.5.1 作业调度 ....................................................... 22 2.5.2 多用户管理 ..................................................... 24 2.5.3 解析器集成 ..................................................... 25 2.5.4 内存管理 ....................................................... 26 2.5.5 检查点支持 ..................................................... 27 性能评估........................................................... 27 2.6.1 迭代式机器学习应用 ............................................. 28 2.6.2 PageRank ....................................................... 30 2.6 2.7 2.8 2.9 3.1 3.2 3.3 3.4 3.5 2.6.3 故障恢复 ....................................................... 30 2.6.4 内存不足的情况 ................................................. 31 2.6.5 交互式数据挖掘 ................................................. 32 2.6.6 实际应用 ....................................................... 33 讨论............................................................... 34 2.7.1 对现有编程模型的表达 ........................................... 34 2.7.2 解释 RDD 表达能力 ............................................... 35 2.7.3 利用 RDD 来调试 ................................................. 36 相关工作........................................................... 36 总结............................................................... 38 第三章 基于 RDD 的模型 ......................................................... 38 简介............................................................... 38 一些在 RDDs 上实现其他模型的技术 .................................... 39 3.2.1 RDDs 里的数据格式 .............................................. 39 3.2.2 数据分区..........................................................40 3.2.3 关于不可变性 ................................................... 41 3.2.4 实现自定义转换 ................................................. 42 Shark:RDDs 上的 SQL ................................................. 42 3.3.1 动机 ........................................................... 42 实现............................................................... 44 3.4.1 列式内存存储 ................................................... 45 3.4.2 数据协同划分 ................................................... 45 3.4.3 分区统计和映射修剪................................................46 3.4.4 局部 DAG 执行 (PDE) ........................................... 46 性能............................................................... 48 3.5.1 方法和集群设置 ................................................. 48 3.5.2 Pavlo 等人的基准测试 ........................................... 49 3.6 3.7 4.1 4.2 4.3 3.5.3 微基准测试 ..................................................... 51 3.5.4 容错 ........................................................... 53 3.5.5 真实的 Hive 数据仓库查询.......................................... 54 与 SQL 相结合的复杂分析 ............................................. 55 3.6.1 语言集成 ....................................................... 56 3.6.2 执行引擎集成 ................................................... 57 3.6.3 性能 ........................................................... 57 总结............................................................... 58 第四章 离散流 ................................................................. 59 简介............................................................... 59 目标与背景......................................................... 61 4.2.1 目标 ........................................................... 61 4.2.2 以往的处理模型 ................................................. 62 离散流(D-Streams)................................................ 63 4.3.1 计算模型 ....................................................... 64 4.3.2 时序方面的考虑 ................................................. 66 4.3.3 D-Stream API ................................................... 67 4.3.4 一致性语义 ..................................................... 70 4.3.5 批处理与交互式处理的统一 ....................................... 70 4.3.6 总结 ........................................................... 71 4.4 系统架构 ....................................................... 72 4.4.1 应用程序执行 ................................................... 73 4.4.2 流处理优化 ..................................................... 74 4.4.3 内存管理 ....................................................... 74 4.5 故障和慢节点恢复 ............................................... 75 4.5.1 并行恢复 ....................................................... 75 4.5.2 减缓慢结点的影响 ............................................... 76 4.7 4.5.3 Master 恢复 .................................................... 76 4.6 评估............................................................... 77 4.6.1 性能 ........................................................... 77 4.6.2 故障和慢节点恢复 ............................................... 79 4.6.3 实际应用 ....................................................... 81 4.8 讨论............................................................... 83 相关工作 ....................................................... 85 总结 ........................................................... 86 4.9 第五章 RDD 的通用性 ........................................................ 88 5.1 简介 ........................................................... 88 5.2 观点描述 ....................................................... 88 5.2.1 MapReduce 所能涵盖的计算范围 ..................................... 88 5.2.2 lineage 和故障恢复 ............................................. 89 5.2.3 与 BSP 的比较 ................................................... 91 5.3 系统角度 ....................................................... 91 5.3.1 瓶颈资源 ....................................................... 92 5.3.2 容错的开销 ..................................................... 93 5.4 限制与扩展 ..................................................... 94 5.4.1 延迟 ........................................................... 94 5.4.2 通信模式 ....................................................... 94 5.4.3 异步 ........................................................... 94 5.4.4 细粒度更新 ..................................................... 95 5.4.5 不变性和版本追踪 ............................................... 95 5.5 相关工作 ....................................................... 96 5.6 小结................................................................ 96 第六章 总结 ............................................................... 97 6.1 经验总结 ....................................................... 98 6.2 更深远的影响 ................................................... 99 6.3 未来的工作........................................................100 参考文献 ................................................................. 102 合或 SQL 查询), 而我们的系统针更为复杂的分析(例如,机器学习的迭代算法)扩展到了对多路算法的支持。 最后,与处理特定工作的专有系统不同的是,我们的架构允许这些算法相互结合,从而实现更 丰富的新应用。例如,流处理和批量处理,或 SQL 和复杂分析之间的相互结合。 为了实现上述的各种特性,我们通过简单的扩展 MapReduce,为其增加了数据共享原语,也 就是所谓的弹性分布式数据集(RDDs)。我们发现,这样的扩展足以能够有效地覆盖大部分作业 的需求。在开源的 Spark 系统中我们实现了 RDDs,同时使用了模拟测试程序和真实的用户应用 对其进行评估。在许多应用领域中,Spark 已经接近或是超过了专有系统的性能,同时提供更强 大的容错保证,并允许这些作业之间能够进行结合。我们从理论建模和实践的角度去探索 RDDs 的通用性,来解释为什么这样的扩展可以覆盖大范围的不同作业需求。 第 1 章 简介 .................................................................... 1 1.1 专业系统相关的问题 .................................................. 2 1.2 弹性分布式数据集(RDDS) ............................................ 3 1.3 基于 RDD 机制实现的模型 .............................................. 4 1.4 总结................................................................ 6 1.5 论文计划............................................................ 7 第二章 弹性分布式数据集 ........................................................ 8 2.1 2.2 2.3 2.4 2.5 简介................................................................ 8 RDD 概述 ........................................................... 10 2.2.1 概念 ........................................................... 10 2.2.2 Spark编程接口....................................................10 2.2.3 RDD 模型的优点 ................................................. 13 2.2.4 不适合 RDDs 的应用 .............................................. 14 Spark 编程接口 ..................................................... 15 2.3.1 Spark 中 RDD 的操作 ............................................. 17 2.3.2 应用示例 ....................................................... 17 抽象 RDDs .......................................................... 20 实现............................................................... 22 2.5.1 作业调度 ....................................................... 22 2.5.2 多用户管理 ..................................................... 24 2.5.3 解析器集成 ..................................................... 25 2.5.4 内存管理 ....................................................... 26 2.5.5 检查点支持 ..................................................... 27 性能评估........................................................... 27 2.6.1 迭代式机器学习应用 ............................................. 28 2.6.2 PageRank ....................................................... 30 2.6 2.7 2.8 2.9 3.1 3.2 3.3 3.4 3.5 2.6.3 故障恢复 ....................................................... 30 2.6.4 内存不足的情况 ................................................. 31 2.6.5 交互式数据挖掘 ................................................. 32 2.6.6 实际应用 ....................................................... 33 讨论............................................................... 34 2.7.1 对现有编程模型的表达 ........................................... 34 2.7.2 解释 RDD 表达能力 ............................................... 35 2.7.3 利用 RDD 来调试 ................................................. 36 相关工作........................................................... 36 总结............................................................... 38 第三章 基于 RDD 的模型 ......................................................... 38 简介............................................................... 38 一些在 RDDs 上实现其他模型的技术 .................................... 39 3.2.1 RDDs 里的数据格式 .............................................. 39 3.2.2 数据分区..........................................................40 3.2.3 关于不可变性 ................................................... 41 3.2.4 实现自定义转换 ................................................. 42 Shark:RDDs 上的 SQL ................................................. 42 3.3.1 动机 ........................................................... 42 实现............................................................... 44 3.4.1 列式内存存储 ................................................... 45 3.4.2 数据协同划分 ................................................... 45 3.4.3 分区统计和映射修剪................................................46 3.4.4 局部 DAG 执行 (PDE) ........................................... 46 性能............................................................... 48 3.5.1 方法和集群设置 ................................................. 48 3.5.2 Pavlo 等人的基准测试 ........................................... 49 3.6 3.7 4.1 4.2 4.3 3.5.3 微基准测试 ..................................................... 51 3.5.4 容错 ........................................................... 53 3.5.5 真实的 Hive 数据仓库查询.......................................... 54 与 SQL 相结合的复杂分析 ............................................. 55 3.6.1 语言集成 ....................................................... 56 3.6.2 执行引擎集成 ................................................... 57 3.6.3 性能 ........................................................... 57 总结............................................................... 58 第四章 离散流 ................................................................. 59 简介............................................................... 59 目标与背景......................................................... 61 4.2.1 目标 ........................................................... 61 4.2.2 以往的处理模型 ................................................. 62 离散流(D-Streams)................................................ 63 4.3.1 计算模型 ....................................................... 64 4.3.2 时序方面的考虑 ................................................. 66 4.3.3 D-Stream API ................................................... 67 4.3.4 一致性语义 ..................................................... 70 4.3.5 批处理与交互式处理的统一 ....................................... 70 4.3.6 总结 ........................................................... 71 4.4 系统架构 ....................................................... 72 4.4.1 应用程序执行 ................................................... 73 4.4.2 流处理优化 ..................................................... 74 4.4.3 内存管理 ....................................................... 74 4.5 故障和慢节点恢复 ............................................... 75 4.5.1 并行恢复 ....................................................... 75 4.5.2 减缓慢结点的影响 ............................................... 76 4.7 4.5.3 Master 恢复 .................................................... 76 4.6 评估............................................................... 77 4.6.1 性能 ........................................................... 77 4.6.2 故障和慢节点恢复 ............................................... 79 4.6.3 实际应用 ....................................................... 81 4.8 讨论............................................................... 83 相关工作 ....................................................... 85 总结 ........................................................... 86 4.9 第五章 RDD 的通用性 ........................................................ 88 5.1 简介 ........................................................... 88 5.2 观点描述 ....................................................... 88 5.2.1 MapReduce 所能涵盖的计算范围 ..................................... 88 5.2.2 lineage 和故障恢复 ............................................. 89 5.2.3 与 BSP 的比较 ................................................... 91 5.3 系统角度 ....................................................... 91 5.3.1 瓶颈资源 ....................................................... 92 5.3.2 容错的开销 ..................................................... 93 5.4 限制与扩展 ..................................................... 94 5.4.1 延迟 ........................................................... 94 5.4.2 通信模式 ....................................................... 94 5.4.3 异步 ........................................................... 94 5.4.4 细粒度更新 ..................................................... 95 5.4.5 不变性和版本追踪 ............................................... 95 5.5 相关工作 ....................................................... 96 5.6 小结................................................................ 96 第六章 总结 ............................................................... 97 6.1 经验总结 ....................................................... 98 6.2 更深远的影响 ................................................... 99 6.3 未来的工作........................................................100 参考文献 ................................................................. 102