海量数据处理

4.4　海量数据处理

以互联网为计算平台的云计算，将会更广泛地涉及海量数据处理任务。海量数据处理指的是对大规模数据的计算和分析，通常数据的规模可以达到TB甚至PB级别。在互联网时代，互联网数据的统计和分析很多是海量数据级别的，一个典型的例子就是搜索引擎。由于数据量非常大，一台计算机不可能满足海量数据处理的性能和可靠性等方面的要求。以往对于海量数据处理的研究通常是某种并行计算模型和计算机集群系统。并行计算模型可以支持高吞吐量的分布式批处理计算任务和海量数据，计算机集群系统则在通过互联网连接的机器集群上建立一个可扩展的可靠的计算环境。

在互联网时代，由于海量数据处理操作非常频繁，很多研究者在从事支持海量数据处理的编程模型方面的研究。例如，Remzi等人在1999年设计了River编程模型，开发人员可以基于该编程模型开发和执行计算任务。River编程模型的设计目的就是使得大规模计算机集群的编程和计算更加容易，并且获得极佳的计算性能。River编程模型有两个核心设计特性：高性能的分布式队列和一个存储冗余机制。因此，River需要对磁盘和网络的数据传输进行非常精心的调度。当今世界最流行的海量数据处理的编程模型可以说是由Google公司的Jeffrey Dean等人所设计的MapReduce编程模型。MapReduce编程模型将一个任务分成很多更细粒度的子任务，这些子任务能够在空闲的处理节点之间调度，使得处理速度越快的节点处理越多的任务，从而避免处理速度慢的节点延长整个任务的完成时间。下面我们将介绍MapReduce框架的工作原理和设计原则，从而加深读者对海量数据处理系统的理解。

MapReduce框架从Lisp及很多其他类似的语言获得灵感，研究人员发现大多数分布式运算可以抽象为Map和Reduce两个步骤，从而实现可靠、高效的分布式应用。Map步骤负责根据输入的key/value（键值）对生成中间结果，中间结果同样采用key/value对的形式。Reduce步骤则将所有的中间结果根据key进行合并，然后生成最终结果。开发者只需要实现Map和Reduce函数的逻辑，然后提交给MapReduce远行环境，计算任务便会在由大量计算机组成的集群上被自动、并行地调度执行。运行环境负责将输入数据进行分割、调度任务、自动处理运行过程中的机器失效，以及协调不同节点之间的数据通信。

MapReduce的运行环境由两种不同类型的节点组成：Master和Worker。Worker，负责数据处理，Master，负责任务调度及不同节点之间的数据共享。

具体执行流程如下：（1）利用MapReduce提供的库将输入数据切分为M份，每份的大小为16～64 MB，然后在计算机集群上启动程序。（2）Master节点的程序负责为所有Worker节点分配子任务，其中包括M个Map子任务和R个Reduce子任务。Master负责找出空闲的节点并分配子任务。（3）获得Map子任务的Worker节点读入对应的输入数据，从输入数据中解析key/value对，并调用用户编写的Map函数。Map函数的中间结果缓存在内存中并周期性地写入本地磁盘。写入本地磁盘的数据根据用户指定的划分函数被分为R个数据区。这些中间结果的位置被发送Master节点。Master节点继续将这些数据信息发给负责Reduce任务的Worker节点进行Reduce处理。（4）执行Reduce子任务的Worker节点从Master节点获取子任务后，使用远程调用的方式从执行Map任务的Worker节点的本地磁盘读取数据到缓存。执行Reduce子任务的Worker节点首先遍历所有的中间结果，然后按照关键字进行排序。（5）执行Reduce子任务的Worker节点遍历获得Map子任务产生的中间数据，将每个不同的key和value进行结合并传递给用户的Reduce函数。Reduce函数的结果被写入到一个最终的输出文件。当所有的Map子任务和Reduce子任务完成后，Master节点将R份Reduce结果返回给用户程序。用户程序可以将这些执行Reduce子任务的Worker节点生成的结果数据合并得到最终结果。

在设计MapReduce的时候，研究人员考虑了很多大规模分布式计算机集群进行海量数据处理时所要考虑的关键问题：容错处理保证了在Master和Worker都失效的情况下计算任务仍然能够正确执行；操作本地化保证了在网络等资源有限的情况下，最大限度地将计算任务在本地执行；任务划分的粒度使得任务能够更加优化地被分解和并行执行；对于每个未完成的子任务，Master节点都会启动一个备份子任务同时执行，无论初始任务还是备份子任务处理完成，该子任务都会立即被标记为完成状态，通过备份任务机制可以有效避免因个别节点处理速度过慢而延误整个任务的处理速度。

大规模数据处理的另一类新技术被称为流计算（Stream Computing）。传统的计算或者数据处理的步骤是：首先收集数据，然后将数据储存起来，储存方式可能有数据库、文件等，最后对储存好的数据进行计算处理，将计算结果返回或者输出。这种计算模式，在现在的海量数据情况下遇到了挑战：（1）数据量非常大，目前互联网时代的数据不止是文本数据，而绝大多数是图像、音频、视频等，将这些数据进行存储就是很大的问题，针对海量数据进行计算也是很大的问题；（2）用户对于计算速度的要求越来越高，比如天气预报、金融分析、市场预测等应用，要求数据计算产生结果的速度尽量的快；（3）大量数据是实时生成的，比如用户的使用日志、交通流量实时监测、证券实时报价等，对这些数据进行分析计算的结果，很多时候都需要实时可用，而如果等待存储——计算——输出的过程，则无法满足需求。流计算是正式应对这些挑战的一项新兴技术。流计算的计算模式为：数据实时地进行输入，不需要强调存储过程，实时计算，实时输出。流计算将计算过程转化成一个流程图的形式，每一个计算模块负责流程中的一个步骤，通过网络连接将这些模块串接成一个反映整个计算过程的图，图的起始端就是用户输入的数据，而图的终止端就是计算输出的结果。流计算着重在“实时”上，以此来解决上文提到的传统计算和数据处理面临的挑战。目前，流计算还在研发阶段，需要研究对不同类型数据的处理方式、处理性能、硬件架构、软件支持等问题，同时也需要业界逐渐接受这种新兴的计算模式。目前，IBM、Google、NVidia等公司都在进行流计算的研发，并推出了一些产品，例如，IBM的System S。