引言
近年来，工业界和学术界越来越重视大数据处理的相关技术及方法。科研过程必然会产生大量的数据，如何理解数据已成为科学研究的重要问题。目前企业在信息化过程中积累了大量的数据，有结构化的和非结构化的，这些已成为企业的核心资产，深刻影响着企业的业务模式，大数据处理使企业决策、组织和业务流程比之过去发生了显著变化。
随着云计算技术的发展，越来越多的公司及学术单位构建了大数据处理平台。学术界开展了大量的针对可定制的云计算技术、基于横向大规模扩展能力的大数据处理平台、非结构化的大规模分布式文件系统、结构化与半结构化的分布式数据库等方面的研究，取得了大量的研究成果。另外，在工业实践中有许多企业希望使用大数据处理的方法，在现有的算法与模型研究的基础上，结合企业的实际数据开展实证研究及模型优化，对企业自身的业务发展起到促进作用。
本文将对大数据处理系统进行讨论。依据数据处理模式的不同，采取的方式也不同。大数据处理系统通常需要对不同的应用场景进行调优，因为没有一个系统能够适应所有的情况。这反映了计算机系统设计中的一个原理性哲学，即如果一个系统能适应所有的情况，那么该系统肯定不是最优的。
本文还将讨论大数据处理中的应用问题，并对应用模式进行归类，提出大数据处理的不同模式。这些模式可以依据与用户交互的速度进行分类。但这种分类也不是绝对的，特别是针对同一个问题需要进行不同处理时，会有不同的处理需求，因此在速度上表现各异。我们要掌握现阶段大数据处理的基本方式，在处理不同数据时采用不同的方法，获得在进行数据处理时的一般性原则以及数据处理的能力界限的位置。在面对新问题的时候，类比现有的做法，选择合适的方式去处理，以便获得更高效率。
大数据处理的模式
大数据领域关注的处理对象 ：(1) 网页数据，例如构建搜索引擎、分析网页中用户点击的情况、观察网页的变化等；(2)各种日志，用以分析用户行为、系统运行状态等 ；(3) 电信领域中的信号、信令数据、电话通信用户以及时长数据等 ；(4) 电力领域中的用电数据、电表汇报数据以及抄表数据 ；(5) 国民经济分项数据与统计数据 ；(6) 各单位的金融数据、社保银行数据等；(7) 互联网实时监控数据、病毒或者蠕虫的传播数据等。
这些大数据的应用及处理的特点如下 ：
1. 网页数据处理。最典型的应用是建立搜索引擎，帮助用户进行数据检索。建立搜索引擎，首先要从互联网中抓取大量数据，下载到搜索引擎数据中心 ；然后将下载的数据进行索引，生成倒排表，以便能够进行快速检索 ；与用户交互，将用户的查询翻译为搜索引擎能够使用的表达，并在内容索引中查找相应的信息合成用户的检索结果。在进行用户交互时，还需要进行数据结果的排序工作，这些工作会涉及大数据处理。例如，在数据下载阶段，最重要的工作就是数据存储，尽可能将大量有价值的数据存储到数据中心 ；在数据索引阶段，需要对存储的数据进行扫描，建立倒排文件的索引。这两部分工作是在后台进行。在不和用户交互时，数据处理不需要进行快速的结果返回，而是需要在后台用较长的时间（数个小时至数天时间）进行数据处理，并将结果保存到存储中备用。
2. 日志数据处理。可进行的分析包括用户点击的日志分析、系统运行行为的日志分析。前者可以帮助分析用户行为，为每个用户打上标签，针对不同用户的请求，返回个性化的查询结果或者做个性化的推荐，也可以帮助建立一个有效的输入法，匹配网络中最新词语的变化。而后者能够帮助管理员更好地理解系统中的各个模块的变化。这两个大数据处理的方式与网页的大数据处理方式类似，都是用较长的时间做详尽的分析，以便获得智能的结果。我们将这种处理方式称为“离线批处理式数据处理”的大数据处理模式。
3. 电信中的信令数据分析、电力系统中的电表数据分析。前者可以建立电信掉线率的分析模型，帮助运营或者设备供货商获知某一时段的网络运营状况，并进行有针对性的优化 ；后者可以对电表数据的情况进行综合，分析用电情况，获得电网优化方案。该类型分析与网页与日志有所不同。在获取数据并进行分析后，管理员或最终的分析决策人员会对数据进行查询和统计，需要在数分钟之内获得结果，否则系统的交互性会急剧下降，降低用户体验的好感。这种“查询式数据处理”的方式也体现在经济数据的统计以及查询方面。
4. 互联网中的在线数据分析、病毒和蠕虫的监控。我们将这种模式称为“实时式数据处理”。例如，在互联网中，需要过滤有害信息，如垃圾邮件、网页数据传输中的有害网页、大规模文件数据传输中的病毒与蠕虫数据。这些数据必须实时处理，否则就可能会将有害数据或者无效数据传输给用户，不仅浪费网络流量，也会带来危害。
综上所述，根据数据处理的时间特征，大数据处理的模式可以分为“离线批处理式数据处理”、“查询式数据处理”和“实时式数据处理”。这三种模式需要的处理时间分别为超过小时级、数秒至数分钟级以及实时级（小于 1秒）。详细对比见表1。
大数据处理的总体系统架构
大数据处理的总体架构与计算机系统的总体架构密不可分。针对不同的大数据处理模式，建立不同的总体系统结构之间并没有太大区别。大数据处理是随着新型互联网企业的发展而发展起来的，其中一个最重要的推动者是谷歌公司。谷歌公司在处理大规模互联网应用，特别是在搜索引擎的建立中构建了一整套进行大规模数据处理的方式与方法，并将之公布，开源社区的开发人员据此建立了开源软件。为了理解大数据处理的总体框架，我们将大数据处理的软件架构与传统的单机处理的软件架构进行了对比。
从表 2 可以看出，大数据处理的架构思路实际上是对单机系统软件架构思路的扩展，将其扩展到大规模的集群中，节点可能成百上千。这种扩展不是直接将现有的系统软件照搬到大规模的集群中。由于分布式系统与集中式系统的重大差别，这种照搬是无法实现的。除了需要实现类似的功能外（例如分布式文件系统中同样也需要提供文件系统的功能），还需要特别注意以下几个问题 ：
l 大数据分布式系统的扩展性。扩展性问题实际上是性能问题。例如，对于一个分布式的文件系统，整个文件系统运行在一个分布式的环境中，这个环境中的节点数量可达数千个。所有的服务器都需要发挥数据存储以及数据服务的功能，并承担起自己的“责任”，不能只让少数服务器承担，因此需要考虑负载均衡。
l 大数据分布式系统的可靠性。分布式系统需要具备一定的可靠性，能够处理一台完整的机器、一个机柜甚至一个数据中心出现的错误。分布式系统的可靠性能够保证一定程度的容错，并且为系统的可用性提供基础。
l 大数据分布式系统的一致性。一致性问题涉及分布式系统的正确性。例如在一个使用多副本进行数据可靠性保证的系统中，如何保证多个副本的数据是一样的就属于一致性的问题。
按照总体系统结构建设的思路，我们通过对单机系统软件的扩展来获得大数据处理的，并对大数据进行优化。这种扩展方式是自然的方式。存储的模式有文件系统、键值对 (key-value)以及数据库。在这个基础上衍生出来的处理模式可以自然地被看作是单机多进程以及多线程的运行模式的扩展。上层应用也是由类似的基本模块进行构造的。
大数据的存储
从系统软件的角度讲，大数据的存储形式没有什么不同。它实际上是对现有的分布式存储的扩展，与单机的存储最大的区别在于数据的容量。大数据的容量要扩展到与互联网规模数据相当的级别，而在科学计算大数据中，数据量甚至会更大。
在应用中，现有的数据存储方式有两种 ：一种是没有任何格式的文件数据，任意的二进制流；另一种是具有一定格式的数据，例如数据库中的结构化数据，构成数据表格的形式。这两种形式都可以被简化为第三种类型的数据存储，即键值对的数据存储。文件数据的存储可以看作是从文件名到文件数据的映射，而数据库中的数据记录则可以看作是键到数据记录的映射。大数据处理也存在这三方面的存储需求，在大规模集群环境下、甚至在跨数据中心的环境下产生新的需要解决的技术问题。
键值对的存储模型最简单。在本地存储中，键值对的存储包括三种技术，即使用哈希表、日志以及顺序表（例如B树、B+树、排序表等）。三种技术各有长短。对于键值对存储，首先要考虑哈希表结构，这种结构对数据的插入以及数据的查询非常方便，能够迅速找到插入的位置。但是当把数据保存到磁盘时，就会产生大量的随机读写操作，降低性能。因此，这种数据结构适合在内存中建立键值对的数据结构，不过在磁盘上还需要做优化。哈希表的数据结构在存储键值对时还存在一个比较严重的问题，即在进行范围查询时（例如查询在某一对键之间的值）比较麻烦，因为哈希表本质上不是一个排序的结构，因此在这方面需要进行特殊处理才能完成范围的查询。为了支持它，就会产生一系列的排序表结构，包括直接使用排序数组的方式以及常用的B树等平衡树的方式。这种方式能够较好地进行范围的查询，缺点是数据插入的过程及获取的过程比较复杂，如果直接使用，磁盘效率不高。因此，通过日志进行数据访问是利用磁盘性能最有效的方式。在键值对的存储中，日志方式用来进行真正的数据存储，而前两种方式则作为日志存储的索引结构来使用。
对键值对存储进行扩展，可以获得大规模集群环境下的键值对存储。由于我们不能更改键值对存储的基本的编程结构，即通过键获取对应的值，因此在本地的键值对存储的基础上以及分布式环境中，要考虑如何将键定位到某一个节点中。一种可以直接使用的方式是使用哈希表来定位到某一个节点中，但是在系统扩展以及缩小的时候需要移动数据。解决该问题的途径就是使用类似一致性哈希的方法，使用虚拟节点而不是物理节点来进行数据的路由，典型的系统有亚马逊公司的 Dynamo。为了解决哈希方法不能进行范围查询的问题，需要建立类似的排序表。排序表的方式需要建立元数据结构，建立具体的服务节点的映射。这种方式需要操作元数据，而一性哈希是几乎不需要元数据的，典型的系统有谷歌公司的 BigTable 【1】，它采用了类似于 B树的结构来记录排序的键值。
分布式文件系统是分布式存储中的一个重要的课题。由于本地文件系统能够支持大量的应用程序，如果能够在分布式环境下也提供文件系统的语义，就能支持一大批应用。分布式文件系统相对于本地文件系统，需要解决的关键问题是如何给出一个文件名并定位这个文件名所代表文件的具体存储的节点，剩下的任务交给本地文件系统处理。当今最著名的大数据处理文件系统是谷歌文件系统 (Google file system,GFS) 及其开源的版本实现 hadoop HDFS。
数据存储的另一种重要的形式是按照数据库进行存储。数据库存储关系两个方面的内容，一是数据库存储的数据模型，关注的是数据库保存数据格式的问题；另一个是数据库操作的一致性，关注的是数据库进行操作时遇到并发情况的正确性问题。使用数据库存储与文件存储的最大区别在于，数据库存储在存储之前需要用户建立存储模型，在大数据处理中的分布式数据存储也不例外。
BigTable是谷歌公司用于存储万维网索引、谷歌地球、谷歌财经数据的分布式数据库存储系统，尽管需求的差异较大，但BigTable给出了一个灵活的数据模型。具体如下：
(row: string, column: string, time:int64) → String(cell contents).
为了向上层应用提供更灵活的操作（如提供范围查询），保证行键 (row-key)之间的有序性，BigTable 使用类似于 B+ 树的结构在分布式环境下存储元数据，数据按照行键进行排序，通过查询元数据找到对应的值和它所在的位置。同时，通过采用预取和缓存策略，大部分操作都可以直接与对应的服务节点进行通信，无须元数据服务器的交互，更无须主服务器的交互。通过多层优化，能够做到高效地访问。
图 1 是谷歌公司大数据存储技术的演进图。图中显示，谷歌公司从搜索引擎的存储需求出发，建立了谷歌文件系统，并在此基础上不断进行更新和改进。在谷歌文件系统语义不足的情况下，建立了 BigTable大规模数据库存储系统 ；在应用需要更新支持的时候，建立了类似触发器的数据库存储系统Percolator【2】，以支持应用的更新操作 ；在 BigTable 单行一致性不足的情况下，建立了 MegaStore数据库存储系统，支持跨多行的事务处理。另外，在 MegaStore 【3】的基础上，在全球多个数据中心的组合上建立了跨数据中心的数据库存储系统 Spanner 【4】。Spanner底层已经更新了对应的文件系统支持，即Colossus分布式文件系统，对上层的应用提供了更多支持，提高了存储效率。从图中还可以看出，当前的大数据的存储正在朝着多个数据中心支持、支持更丰富的语义以及更强的一致性方向发展。分布式大数据存储正沿着数据库曾经走过的发展历程前进，其规模和可靠性、扩展性又提高了多个数量级。
大数据的处理以及对交互数据查询的支持
从大数据处理技术和传统的单机系统技术的对比可以看出，对数据处理、交互数据查询以及类似结构化查询语言的支持是建立在大数据存储的基础上的。从应用的角度出发，数据处理技术的使用者是应用程序员。应用程序员通常只关注应用本身，不会关注系统方面的工作机制。例如，一个日志分析程序员关心的是用户的偏好信息，以及通过偏好信息能够获得的对应的用户关注点计算。系统方面的工作（例如整个系统的可靠性、扩展性）则可以交给系统程序员去处理。因此，大数据处理的架构被分成两部分：系统程序员建立编程框架，提供简明的编程接口，并且在后台自动处理诸如系统的可靠性以及扩展性问题 ；应用程序员如日志分析员、图形处理人员或者进行数据处理的程序员等只需要关注应用，其它的任务交由编程框架进行处理。
当前，在大数据处理的发展过程中，建立了一种被称为隐式消息传递编程模式，与显式的消息传递接口 (message passing interface,MPI)相区别。MPI是高性能计算中的事实标准，如果很好地利用其进行编程，性能会非常优秀。但 MPI 和现有的并行编程模式也存在一些问题 ：应用程序员必须自己考虑系统的可靠性以及扩展性问题，而大数据处理面对的机器数量已达数千，应用程序员无法面对系统的底层细节。而为此建立的隐式消息传递模型编程模型则将这一复杂性通过系统程序员的工作进行了屏蔽，使得消息传递被嵌入到整个系统的内部，编程模型自动处理出错和自动处理扩展性的问题。通过这些工作，应用程序员只须关注与应用紧密相关的内容，将系统细节相关的内容交给底层的编程模型处理即可。
当前比较著名的隐式消息传递模型编程模式有谷歌公司的 MapReduce【5】以及微软公司的Dryad【6】。相关人员围绕着这些模型也进行了一系列扩展和优化工作，例如加州大学伯克利分校的spark/shark【7,8】，用以在大规模集群中的内存优化。
从技术层面看，Dryad 系统的执行引擎处于比 MapReduce更加底层的位置，因此可以通过Dryad来执行MapReduce的程序。Dryad 的执行引擎能够执行一个二维的有向无环图，当所有的节点执行完毕，整个系统也就执行完毕。这种结构与当前许多程序被编译完成之后的中间表达是一致的，即可以构造一个执行流程，来逐步完成工作。而流程中的每一个节点都是一些操作原语，能够运行在大规模的集群之上。
Dryad 是基于微软公司集群架构搭建的，并且封装了若干高级语言应用程序界面 (application program interface, API )，一个典型的例子是DryadLINQ【9】。Dryad将作业构建为点和边的集合，整个作业组成一张有向非循环图(directed acyclic graph, DAG)，其结构如图 2所示。
从图中可以看出，一个大型任务会被分解为多个步骤的任务，每个步骤继而被分解为任务DAG图中的节点。每一个节点由程序员编程，然后投入到大规模的集群中执行。而 DAG 图中的有向边就是数据传输的通路，可以通过内存传递数据，也可以通过网络通道传递数据，具体由实际的执行情况决定。由于需要处理的数据规模巨大，因此任务节点数据量远远多于执行的计算节点的数量，调度器可以充分利用这种特性获得高扩展性，同时通过重新执行完成任务的容错特性。
Dryad 是一种通用的方法，适应的范围比MapReduce 广。由于 Dryad 的灵活性，直接进行节点与边的操作对程序员来说比较困难。由于许多查询语言被编译后的内部表示也 是 DAG 图，因此更好的方式是使用Dryad作为底层的查询引擎去执行上层查询语言产生的执行流程图。虽然MapReduce也能够做同样的工作，但是 MapReduce的多步执行本质上是连串的，有可能在表达查询的时候不自然。通过Dryad支持的典型的查询语言是DryadLINQ，即LINQ语言在分布式环境下的扩展。而通过MapReduce支持查询语言的包括HIVE，Pig Latin以及谷歌公司内部的Sawzall【10】。
图 3 是谷歌公司大数据处理技术进展情况，同时列出了在开源社区软件以及相应研究中对等的研究内容。其特点是 ：首先构造一个能够支持大数据处理的引擎，再在此基础上支持查询语言。为了提高效率，可对底层的数据结构以及存储结构进行改变，如Dremel充分利用列式数据库建立高效的查询引擎。当然，针对特定的应用也可以改变底层执行引擎，例如 Pregel建立了高效的图计算引擎，能够对类似社交网络这样的图计算进行高效计算。
实时数据处理模式与系统
针对不同的应用可以建立不同的实时处理系统，但是这种针对每个案例逐一解决的做法会造成“重复造轮子”的问题。因此，需要建立合适的编程框架，适应一大类应用程序的需求。本文主要关注两个实用的开源项目 ：雅虎公司的S4系统和推特的 Storm系统。这两个系统采用的技术类似，但具有不同的特征。
雅虎公司的 S4 系统现已经被归为 Apache（网站服务器）的一个孵化项目。它使用一种事件驱动的方式进行流式的处理，图4是它的一个逻辑处理节点。
逻辑处理节点是 S4 中基本的处理单元，由处理节点以及通信层组成。处理节点对用户的数据进行处理。需要处理的数据类似于键值对形式的数据，包括事件的类型、事件中包含的键值以及数据，这部分内容被称为处理单元。处理单元编码需要进行的处理动作、事件类型、属性的键以及属性的值，都属于需要处理的数据。数据处理会在不同的处理节点进行，处理完毕后，如果还需要继续处理，会生成新的处理单元。底层的通信层则进行数据单元路由的工作，路由方法通过数据单元的哈希值完成。
Storm 的流信息处理机制使用了类似的技术，即将信息的处理作为一系列的事件进行处理，数据也被封装在事件中，事件在多个处理节点内部进行流动。不同的是在Storm中对数据的流向进行了加强，使处理的语义信息更加丰富，能够支持高层的编程语言。这一点与前文所述的Dryad系统中的信息流动是类似的。
图 5 中进行的数据分发过程被称为 All Grouping，即广播发送的方式，具体是指 ：对于每一个 Tuple（数据），所有的bolts（处理单元）都会收到。Storm中也提供了其它的各种数据发送方式，例如进行随机分组、字段分组（类似于S4）、全局分组、直接分组等。这些分组方式对分组形式做了一定的限制，以匹配应用于不同需求。
“实时式数据处理”模式与其它两种模式类似，它力图建立一整套编程框架，以便将应用程序的编程人员与底层系统进行剥离。应用程序的编程人员只需要关注处理的具体内容以及处理的内容流程，而系统的架构以及系统运行中的动态的变化情况等底层细节则交给运行时系统完成。
总结
大数据处理中存储和计算方法一直是工业界及学术界研究的热点，当前研究的一个热点是如何继续提高数据处理能力。无论在哪种模式下，提高运算速度都是一个永恒不变的主题。加州大学伯克利分校的 Spark / Shark 系统着力于提高内存的利用效率，希望充分利用内存的缓存作用，提高迭代计算的处理速度。这一点是对 MapReduce的有力补充，因为 MapReduce 没有缓存。在流式计算处理中，一些研究机构也希望改进流式引擎使用的便捷性，在此基础之上建立查询引擎，通过查询方式获知流式数据的特图5Storm中的数据分发流程 征。在数据存储领域，随着大数据规模的增长以及互联网应用的需求，数据存储逐渐开始向地理分布的多个数据中心转移，甚至有人提出建立全球统一的存储引擎。但其中有一个重要的问题需要解决，即数据在多个数据中心之间的一致性，这涉及到 Paxos 算法。由于这个算法能够在多个数据中心之间提供一致性操作，受到各大公司关注。在开源社区中，ZooKeeper 系统提供了类似功能，可以使用该软件提供基础、稳固的配置信息存储等。
据规模的增长以及互联网应用的需求，数据存储逐渐开始向地理分布的多个数据中心转移，甚至有人提出建立全球统一的存储引擎。但其中有一个重要的问题需要解决，即数据在多个数据中心之间的一致性，这涉及到 Paxos 算法。由于这个算法能够在多个数据中心之间提供一致性操作，受到各大公司关注。在开源社区中，ZooKeeper 系统提供了类似功能，可以使用该软件提供基础、稳固的配置信息存储等。
脚注：
------
1 Petabyte，1015 字节。
2 Terabyte，1012 字节。
参考文献
【1】Fay Chang, Jeffrey Dean, Sanjay Ghemawat, et al..
Bigtable: a distributed storage system for structured data.
Proceedings of 7th USENIX Symposium on Operating Systems Design and Implementation. Seattle, WA, November, 2006. 205~218.
【2】Daniel Peng, Frank Dabek,
Large-scale incremental processing using distributed transactions and notifications,
Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, USENIX 2010.
【3】Jason Baker, Chris Bond, James C. Corbett, et all.
Megastore: providing scalable, highly available storage for interactive services,
Proceedings of the Conference on Innovative Data system Research (CIDR) 2011;
223~234.
【4】James C. Corbett, Jeffrey Dean, Michael Epstein, et all..,
Spanner: Google's globally-distributed database,
Proceedings of OSDI'12: Tenth Symposium on Operating System Design and Implementation, Hollywood, CA, October, 2012.
【5】Jeffrey Dean, Sanjay Ghemawat.
MapReduce: simplified data processing on large clusters.
Communications of the ACM, 2005;51(1): 107~113.
【6】Michael Isard, Mihai Budiu, Yuan Yu, et al..
Dryad: distributed data-parallel programs from sequential building blocks.
Proceedings of the 2rd European Conference on Computer Systems (EuroSys), Lisbon,
Portugal, March 21~23, 2007:28~43.
【7】Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, et al..
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing.
NSDI 2012. April 2012.
【8】Cliff Engle, Antonio Lupher, Reynold Xin, et al..Shark:
fast data analysis using coarse-grained distributed memory (demo).
SIGMOD 2012. May 2012.
【9】Yuan Yu, Michael Isard, Dennis Fetterly, et al..
DryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language,
Symposium on Operating System Design and Implementation (OSDI), San Diego, CA, December
8~10, 2008.
【10】Rob Pike, Sean Dorward, Robert Griesemer, et al..
Interpreting the data: parallel analysis with sawzall.
Scientific Programming Journal, 2005; 13(4): 277~298.
