[科普中国]-大型数据处理系统

概述

互联网的迅速发展导致数据量爆炸式增长，根据国际数据公司的统计，2011年全球产生的数据总量为1.8ZB(1ZB=1021B)，最近3年人类产生的信息量已经超过了之前产生的信息量总和。IBM用4个V，即Volume(数据体量巨大)、Velocity(数据以高速率产生)、Variety(数据类型多种多样)和VMue(数据的价值密度低)，来描述大数据的特点，对低价值数据进行深度地分析，提炼出高价值的知识，已经成为目前普遍的共识。由于数据体量大、产生速
度快，以关系型数据库为代表的传统数据管理与分析工具无法应对大数据时代的挑战，新型的海量数据处理技术应运而生。2012年，美国政府提出了“大数据研究发展计划”，将大数据的研究与应用上升到战略层面。毋庸置疑，我们已经处于大数据时代，并经历这场技术变革2。

大型数据处理系统的分类大数据处理系统的种类繁多，目前还没有公认的分类方法。为了清晰掌握技术的发展现状，这里从负载类型和数据类型两个角度对代表性的系统进行分类，一方面明确了各种系统的适用范围；另一方面可看到尚未解决的空白领域2。

从负载类型上分类从负载类型的角度，目前的系统可以划分为批处理、流式计算和交互式查询等三类。批处理系统强调系统的高吞吐量，例如Hadoop系统就定位于批处理。流式计算是近几年兴起的一个研究领域，很多应用场景对计算的时效性要求高，希望能够在尽可能小的延迟内完成，例如在线广告推荐、入侵检测和作弊识别等。目前代表性的流式计算系统包括雅虎的s4、Twitter的Storm、Google的MillWheel、微软的TimeStream和美国加州大学伯克利分校的DStream等。交互式查询分析主要应用于大规模的数据仓库，从早期的Hive到Dremel、Impala和Shark等，各种SQL-On-Ha-doop与大规模并行处理(massive parallel processing，MPP)系统不断出现2。

从数据类型上分类从数据类型的角度，目前的系统提供了集合、表、图和矩阵等多种数据抽象。通常一个编程框架只适合解决某类问题，无法对各种问题领域都适用。例如，MapReduce适合解决记录之间相互独立的集合类数据；Piccolo利用分布式内存存储表格数据，能够加快迭代计算的运行效率；MadLINQ提供大规模的矩阵运算，可简化一大类机器学习和数据挖掘算法的开发2。

研究进展批处理编程框架种类繁多，但大部分编程框架都与数据流模型有密切关系，对数据流模型进行概括和总结可厘清一大类系统之间的差异。大规模图计算和分布式机器学习是目前两个非常活跃的研究方向，由于其计算特点的特殊性，数据流模型并不擅长解决此类问题，需要新式的计算模型2。

基于数据流模型的编程框架许多的编程框架都可以归结为数据流模型，如批处理中的MapReduce、Dryad、Spark、FlumeJava，流处中的Storm等。数据流模型有相当长的研究历史。简单而言，数据流模型使用有向无环图(directed acyclic graph，DAG)表达一个计算，图中的顶点表示计算任务，而边表示数据依赖。

(1)MapReduce：MapReduce计算为程序员提供了两个简捷的编程接口，即Map函数和Reduce函数。任务的输入和输出数据按照Key-Value的方式组织，框架会自动将中间结果中相同Key值的记录聚合在一起，作为Reduce函数的输人值。MapReduce具有非常突出的优点。首先是具有极高的可伸缩性，可以在数千台机器上并发执行；其次具有容错性，即使集群发生了故障，一般情况下也不会影响任务的正常执行；三是简单性，用户只需要完成map和reduce两个函数就可以完成大规模数据的并行处理。但MapReduce也存在一些局限性，比如map和reduce任务的启动时间长，不适合对时效性要求高的应用场景。MapReduce模型存在多处的磁盘读写和网络传输，对于迭代机器学习应用，往往需要同一个mapreduce任务反复执行，这就带来了大量的磁盘读写和网络传输开销，使运行效率非常低。MapReduce包括Map和Reduce两个阶段的任务，Map阶段的任务执行完后才能执行Reduce阶段的任务，无法表达任务之间复杂的拓扑结构，本质上MapReduce模型可以看作是DAG计算的一种特例。

(2)Dryad：Dryad采用了通用的DAG计算模型，能够灵活地表达任务之间的拓扑结构，由于需要程序员显式地构建拓扑结构，也带来了一定的编程负担。Dryad在数据传输方面提供了更多的机制，包括共享内存、TCP管道、临时文件和分布式文件系统等，而MapReduce只提供了临时文件的方式传输map和reduce阶段之间的中间结果。

(3)Spark：Spark的核心思想是使用数据集的转换图(DAG结构)来表达一个完整的数据处理过程，DAG中的顶点表示弹性分布式数据集(resilient distributed dataset，RDD)，边表示转换操作。RDD是对迭代计算中反复使用的中间数据集的一种抽象，表示一个只读记录组成的集合。RDD创建后其内容不能修改，但可以对RDD进行各种转换操作，原先RDD的内容经过转换后形成了新的RDD，Spark会维护RDD之间的依赖关系，称为血统(Lineage)。这种链式操作不仅简化了应用程序的开发，而且也让故障恢复变得简单了。Spark将RDD分片(partition)到多台机器上，同时执行粗粒度的转换操作，即数据并行。一条记录进入Spark的任务后会经历多个转换操作再输出，即流水线。Spark提供RDD．Cache()的应用程序编程接口(API)，允许程序员将一个RDD显式地加载并驻留在内存中，这样可极大地加快后续的处理速度，对于迭代计算特别有效。随着内存越来越便宜，基于内存计算会越来越成为系统设计上的一种选择。

(4)高级的库与语言：随着Hadoop的广泛应用，直接采用MapReduce编程面临开发效率和性能等几方面的问题。目前的发展趋势是将Hadoop封装到下层作为执行引擎，在上层系统中提供更加简单易用的高级库或面向领域的编程语言(domain specific language，DSL)等，由转换层负责将更高级的抽象自动翻译为大量的Hadoop作业2。

图计算大规模的图数据分析在实际应用中有广泛的需求。例如互联网的网页之间形成了一个超大的图，其顶点规模达到千亿级，必须借助于大规模的集群才能完成巨型图的分析与挖掘。图数据具有非规则的结构，导致图数据访问的局部性差。很多现实世界中的图符合幂律分布，即图顶点的分布极不均匀，极少的顶点通过大量的边与其他大量顶点发生关联，这意味着图数据很难切分均匀，从而带来机器负载不均衡和大量的网络通信开销，这会严重影响图计算系统的整体运行效率。

大图的分割是图计算中基础性的问题之一。目前，图数据的切分主要有两种方法：切边和切点。衡量图数据的切分主要考虑两个因素：机器的负载均衡性和网络通信量。理想的情况是机器负载尽量均衡，并且网络通信量最小。现实世界中的大多数图的边分布遵守幂律分布，理论和实践均已证明，对于遵守这一特征的图数据，切点法比切边法的计算效率要高一个数量级。

目前图数据领域的相关系统可划分为两类：在线查询的图数据库和离线图数据分析系统。Facebook的Tao是目前代表性的大规模图数据库查询系统，离线图分析系统包括Pregel、Giraph、GraphLab和PowerGraph等，适合解决大规模图数据的挖掘与分析类应用，如计算网页的PageRank值、计算图中两个顶点之间的最短路径等2。

分布式机器学习系统在大数据时代，传统的单机版机器学习算法因为处理器和内存受限制，无法处理海量数据，分布式机器学习成为备受关注的研究领域。通常，机器学习算法使用迭代计算在巨大的参数空间中求最优解，其计算特点对分布式机器学习带来了严重挑战，主要表现在以下几方面：

(1)单机版机器学习算法通过共享内存可存取全局参数，在分布式环境下需要通过网络来存取全局参数，效率比内存低很多，如何提高通信效率或者减少通信量，对提高分布式机器学习的运行效率至关重要。

(2)大量的并发任务由于各种原因(如机器负载或者软硬件故障等)会导致其执行速度不统一，快任务需要等待慢任务执行完，负载的不均衡会降低任务的整体完成效率，如何避免“快等慢”现象也是需要解决的问题。

(3)当集群中的机器发生故障后，系统应当保证程序能够容错并运行正确。

最近几年，大规模的深度学习在实际应用中获得了巨大的成功，特别是在语音识别和图像识别等领域取得了突破性进展。

根据技术路线的差异，目前分布式机器学习系统可以划分为三类：基于Hadoop、基于Spark和参数服务器架构。

Mahout是在Hadoop上构建的机器学习算法库，提供了常见的聚类、分类和推荐等算法，由于底层机制受限于MapReduce提供的计算接口，算法的实现要复杂一些。此外，运算的中间结果都需要持久化到磁盘上，在迭代计算中需要频繁地读写磁盘上的数据，导致运行效率低。

MLlib是在Spark上构建的机器学习系统，内置了大量成熟的机器学习算法库，系统的优化器会根据参数的组合、数据特征等信息自动地优化算法，降低了机器学习算法的使用门槛。由于Spark比Hadoop运行速度快几十倍甚至上百倍，因此MLlib的运行效率要高许多。

参数服务器是目前分布式深度学习系统的典型结构。参数服务器包括大量并发执行的客户端和多台参数服务器组成的参数服务器集群，不同的系统基本遵循上述结构，但在具体实现上有差异。从概念上讲，参数服务器可以看作是分布式共享内存的Key-Value存储，用于存储客户端共享的全局参数，参数服务器对全局参数进行数据分片，每个数据分片维护一部分全局参数的存储与更新；在训练过程中，客户端可以读取或更新全局参数，不同应用的全局参数可以存储在参数服务器的不同表格中。从结构上讲，参数服务器集群通常采用传统的Master-slave结构，其中一台参数服务器充当主控节点的角色，负责数据路由以及在不同的服务器之间进行数据分片等工作2。

研究热点与趋势虽然大数据处理系统已取得大量的研究成果，各种工具与系统的研究方兴未艾，但许多技术仍处于摸索阶段，远未达到成熟。本节归纳了三个方面的研究热点与趋势，并对国内的大数据处理系统的重点突破方向进行了展望。

(1)异构硬件平台的并行训练

深度学习的计算特点是参数量巨大、更新频繁，传统的大数据处理技术如Hadoop，由于数据处理延迟高，并不适合需要频繁迭代的深度学习，需要针对深度学习的模型结构和计算特征来设计相应的专用系统。目前大规模的并行训练是一个热点问题，特别是如何利用CPU和GPU组成的异构并行硬件平台来加速计算值得深入研究。

(2)串行代码的自动化并行

目前的编程框架提供了标准的数据操作接口，程序员编写接口的实现函数，由底层的系统负责并行地执行用户代码，这种编程方式与传统的串行编程差别大。最近，基于程序分析的自动化成为一个研究热点，其基本思想是程序员编写传统的串行代码，通过程序分析技术来自动获取代码中的并行性。这方面的代表性工作包括pydron和SDG，二者均通过分析代码中的标注(annotation)来获取并行性。串行代码的自动化并行是一个具有吸引力的方向，许多问题有待进一步解决，包括优化的方法、减少对串行程序的限制等。

(3)混合编程

大数据处理技术的多样化丰富了数据处理的手段，但也给实际应用带来的困难。由于不存在全能通用的计算框架，多种编程框架需要协同工作才能完成复杂的数据处理任务。例如，典型的机器学习可以组织成数据预处理、特征提取、训练和评价等工作流。数据预处理和特征提取阶段可采用MapReduce来完成，而训练阶段采用PowerGraph来完成。目前实现上述处理流程需要多个独立的作业，作业之间通过Hadoop分布式文件系统(Hadoop distributed file system，HDFS)共享数据，造成大量的HDFS读写开销，并且大量的作业也增加了资源调度的开销。根本原因在于目前的编程框架相互独立，计算之间只能以粗粒度的方式组合，如何打破目前编程框架之间的壁垒，让多种计算能够自由、高效地组合在一起完成更为复杂的处理流程，这个问题目前还没有很好的解决方案。Transformerl提出了一种混合计算的编程系统，能够将多种计算融合在一个程序中，并且通过分布式内存来加快中间数据集的访问2。