云计算与大数据处理
1. 引言
从某种程度上来讲，云计算是面向服务计算的一个极其成功的范例。云计算的三大理念包括：基础设施即服务（IaaS ）、平台即服务（PaaS ）以及软件即服务（SaaS ）。这一概念甚至同样可以扩展到数据库即服务（DBaaS ）抑或存储即服务（SaaS ）。灵活性强、计次付费、前期低投资以及风险转移几大特性，使得云计算成为部署新型应用的一种普遍方式。大量云计算应用服务的不断涌现，也催生了各种各样的云平台。越来越多的平台和应用，同时作为生产者和消费者，也使得互联网上的数据量以惊人的速度日益扩增。可扩展数据管理系统因此就成为云计算基础架构的重要一环。对于可扩展分布式数据管理的研究已经持续了许多年。大多数研究都关注于如何设计出一种同时适用于更新密集任务和专业分析任务的可扩展式系统。最初的方案有应用于更新密集型任务的分布式数据库，以及专业分析任务的并行数据库。其中并行数据库更是从原型系统一直发展到可用的商业系统水准。然而相比之下分布式数据库却发展的差强人意且从未得到商业化。
2. 可扩展海量数据管理系统
应用服务的数据访问模式的变革，再加上急速扩增的需求，催生了一种被称作键值对（Key-Value ）存储的新型系统。键值存储模式出现后受到各种企业的追捧并且得到了广泛采用。在工业界和学术界，MapReduce 模式以及其开源实现项目Hadoop 都得到了迅速应用普及。而且更进一步，针对不同的应用场景下的可用性以及运行效率提升，也不断有各种Hadoop 改良解决方案被提出。部署在云端的应用服务都有着各自对于数据管理的迫切需求，这样就有诸多的可供研究的空间。总之，为解决各领域大数据管理带来的挑战，催生了数不胜数的系统方案。各种云计算服务都需要对分布存储的、海量的数据进行处理分析。具体而言，云计算应用面临的数据管理挑战体现在数据的海量性、异构性以及非确定性。针对这些特点，来构建高可用性及强可扩展性的分布式数据存储系统，目前云计算系统中的数据管理技术除了MapReduce 之外，主要还包括Google 的GFS 、 BigTable 和亚马逊的Dynamo 。
2.1 MapReduce 技术
MapReduce 是Google 提出的一个软件架构，用于大规模数据集（大于1TB ）的并行计算。作为一个新的编程模型，MapReduce 将所有针对海量异构数据的操作抽象为两种操作，
即Map 和Reduce 。使用Map 函数将任务分解为适合在单个节点上执行的计算子任务，通过
图1. MapReduce 架构模型
调度执行处理后得到一个“Key-Value ”集。而Reduce 函数则根据预先制定的规则对在Map 阶段得到的“Key-Value ”集进行归并操作，得到最终计算结果。MapReduce 架构模型最为成功之处就在于，让人们可以根据需求将针对海量异构数据的处理操作（无论是多么复杂）分解为任意粒度的计算子任务，并能够在多个计算节点之间灵活地调度计算任务以及参与计算的数据，从而实现计算资源和存储资源配置的全局最优化。另外，MapReduce 方法在将Map 任务和Reduce 任务分配到集群中的相应节点时，会考虑到数据的本地性(Data Locality)，即一般会将Map/Reduce安排到参与计算数据的存放节点或附近节点来执行。
2.2 GFS 技术
GFS （Google File System ）是一个大型的分布式文件系统。它为Google 云计应用算提供分布式海量存储解决方案，并且与MapReduce 和BigTable 等技术结合十分紧密，形成Google 独有的一套的云计算解决方案。GFS 的架构模型如图2所示，GFS 将整个系统的节点分为三类角色：Client （客户端）、Master （主服务器）和Chunk Server（数据块服务器）。Client 是GFS 提供给应用程序的访问接口，它是一组专用接口，不遵守POSIX 规范，以库文件的形式提供。应用程序直接调用这些库函数，并与该库链接在一起；Master 是GFS 的管理节点，其数量在逻辑上只有一个，它保存系统的元数据，负责整个文件系统的管理，是GFS 文件系统中的大脑；Chunk Server负责具体的存储工作，数据以文件的形式存储在Chunk Server 上，Chunk Server 的个数可以有多个，它的数目直接决定了GFS 的规模。GFS
将文
件按照
图2. GFS架构模型
固定大小进行分块（默认是64MB ），每一块称为一个Chunk （数据块），每个Chunk 都有一个对应的索引号（Index ）。客户端应用在访问GFS 时，首先访问Master 节点，获取将要与之进行交互的Chunk Server信息，然后再行直接访问这些Chunk Server完成数据存取。GFS 的这种设计方法实现了控制流和数据流的分离。Client 与Master 之间只有控制流，而无数据流，这样就极大地降低了Master 的负载，使之免于成为制约系统性能的一个瓶颈。Client 与Chunk Server 之间直接传输数据流，同时由于文件被分成多个Chunk 进行分布式存储，Client 又可以同时访问多个Chunk Server ，从而使得整个系统I/O活动高度并行，整体性能得到极大提升。
2.3 BigTable 技术
Google 提出的BigTable 技术是建立在GFS 和MapReduce 之上的一个大型的分布式数据管理系统。BigTable 实际上的确是一个很庞大的表结构，它的规模可以超过1PB （1024TB ）。它将所有数据都作为对象来处理，形成一个巨大的表格。对于BigTable ，Google 给出了如下定义：BigTable 是一种为了管理结构化数据而设计的分布式存储系统，系统中存放管理数据可以扩展到非常大的规模，例如在数千台服务器上的达到PB 规模的数据，现在有很多Google 的应用程序建立在BigTable 的基础之上，例如Google Earth 。而基于BigTable 模型实现的Hadoop Hbase开源项目也逐渐在越来越多的应用中发挥作用。
BigTable 就是一个稀疏的、多维的和有序的Map ，每个Cell （单元格）由行关键字、列关键字和时间戳来进行三维定位。Cell 的内容本身是一个字符串，举例来说，当存储一个网页的内容，其数据模型如图3所示。在图3中，反向的URL “com.cnn.www ”是这一行的关键字，“contents ” 这列存储了多个版本的网页内容，其中每个版本都有一个时间戳。BigTable 还提供一个用于将多个相似的列整合到一起的Column Family（列组）机制。比如，
“anchor ”这个Column Family就有“anchor ：cnnsi.com ”和“anchor ：my.look.ca ”这个两个列。通过Column Family这个概念，使得表可以轻松地横向扩展。
图3.BigTable 数据模型
图3中，对于网页文档的全文有一个文本列，还有一个标题列，这样一来，没有必要对全部的文档文本进行分析，就可以快速地找到文档的标题。有两列用于锚文本，一个是“anchor ：other.com ”，包含从站点other.com 指向example.com 的超链接的锚文本；如图3中的单元所示，超链接上的文本是“example ”。anchor ：null.com 描述了从null.com 指向example.com 的一个超链接上的锚文本是“点击此处”。这些列都属于锚文本列组（column group ）。可以向该列组中增加其他的列，以增加更多的链接信息。
图4.Tablet 位置结构
BigTable 使用一个3层的、类似B+树的结构存储Tablet 的位置信息，如图4所示。第1层是一个存储在Chubby 中的文件，它包含了Root Tablet的位置信息。Root Tablet包含了一个特殊的metadata 表里所有的Tablet 的位置信息。metadata 表的每个Tablet 包含了一个用户Tablet 的集合。Root Tablet实际上是metadata 表的第1个Tablet ，只不过对它的处理比较特殊（Root Tablet永远不会被分割）这就保证了Tablet 的位置信息存储结构不会超过3层．其中在Chubby 中存储着多个Root Tablet的位置信息。Metadata Tables中存储着许多User Table的位置信息。因此当用户读取数据时，需先从Chubby 中读取Root Tablet的位置信息然后逐层往下读取直至找到所需数据为止。
BigTabl e 的负载均衡采用的是传统的方式，BigTable 在执行任务时，在任意时刻每个Tablet 只被分配到一个Tablet 服务器。依靠一个Master 服务器监视子表Server
的负载情况，
根据所有子表服务器的负载情况进行数据迁移的，比如将访问很热的列表迁移到压力轻的子表服务器上，以调节Tablet 服务器的负载平衡。
2.4 Dynamo 技术
Dynamo 是一个高可用，专有的键值结构化存储系统，或分布式存储系统。它同时具有数据库和分布式哈希表的特征，并不直接暴露在外网，而是为Amazon Web Services（AWS ）提供底层支持。目前Dynamo 已经有很多实现，典型的有：Apache Cassandra、Project Voldemort以及Riak 。
图5.Dynamo 架构
Dynamo 是采用分布式哈希表作为基本存储架构和理念，这个架构最大特点是能让数据在环中均匀存储，各存储点相互能感知（因数据需要在环内转发，以及相互之间进行故障探测，因此需要节点之间的通信），自我管理性强，因为它不需要Master 主控点控制，无单点故障危险。此外，Dynamo 的主要优点是：它提供了使用3个参数（N ，R ，W ），可以根据实际的需要来调整它们的实例。Dynamo 支持对对象的不同版本进行记录和处理，并且可以将不同版本提供给应用，供应用自身更加灵活地进行合并。对象的副本数遵循(N，R ，W) 的规则，N 个副本，如果R 次读取的一致，则确定读取成功；如果W 次写入成功，则认为写入成功；不要求全部N 个都成功完成，只要R+W>N，数据的最终一致性就可以得到保障。在这里，读操作比一次写多次读的系统（比如HDFS ）麻烦，但写操作变简单了，这一点适应了一些应用场景下的需求。
负载均衡对于Dynamo 系统而言是天生的优势，因为它采用了分布式哈希表将数据都均匀存储到各个点，所以没有访问热点，各点的数据存储量和访问压力应该都是均衡的。
3. 总结
在新兴的云计算数据管理领域Google 的BigTable 、MapReduce 和亚马逊的Dynamo 技术针对云计算海量数据处理的问题和应用特点有了很多创新，综合来看，采用分布式的存储技术可用于大型分布式的、需要对大量数据进行访问的应用。如GFS ，其运行于各种类似的普通硬件上，提供容错功能，为用户提供低成本、高可靠性、高并发和高性能的数据并行存取访问。针对数据的非确定性、分布异构性、海量、动态变化等特点，采用分布式数据管理技术，通过采用BigTable ，Hbase 等分布式数据库技术对大数据集进行处理和分析，面向用户提供高效的服务。为了高效地利用在分布式环境下的数据挖掘和处理，采用基于云计算的并行编程架构，如MapReduce ，将任务自动分成多个子任务，通过映射和化简两步实现任务在大规模计算节点中的调度与分配。后台复杂的并行执行和任务调度对用户和编程人员则无须关心。
4. 参考文献
[1] 刘正伟, 文中领, 张海涛等. 云计算和云数据管理技术[J].计算机研究与发展,2012,49(z1):26-31.
[2] 周晓方, 陆嘉恒, 李翠平, 等. 从数据管理视角看大数据挑战 [J][J]. 中国计算机学会通讯, 2012, 8(9): 16-20.
[3] 陈全, 邓倩妮. 云计算及其关键技术[J]. 计算机应用, 2009, 29(9): 2562-2567.
[4] Agrawal D, Das S, El Abbadi A. Big data and cloud computing: current state and future opportunities[C]//Proceedings of the 14th International Conference on Extending Database Technology. ACM, 2011: 530-533.
[5] Agrawal D, Das S, El Abbadi A. Big data and cloud computing: new wine or just new bottles?[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 1647-1648.
云计算与大数据处理
1. 引言
从某种程度上来讲，云计算是面向服务计算的一个极其成功的范例。云计算的三大理念包括：基础设施即服务（IaaS ）、平台即服务（PaaS ）以及软件即服务（SaaS ）。这一概念甚至同样可以扩展到数据库即服务（DBaaS ）抑或存储即服务（SaaS ）。灵活性强、计次付费、前期低投资以及风险转移几大特性，使得云计算成为部署新型应用的一种普遍方式。大量云计算应用服务的不断涌现，也催生了各种各样的云平台。越来越多的平台和应用，同时作为生产者和消费者，也使得互联网上的数据量以惊人的速度日益扩增。可扩展数据管理系统因此就成为云计算基础架构的重要一环。对于可扩展分布式数据管理的研究已经持续了许多年。大多数研究都关注于如何设计出一种同时适用于更新密集任务和专业分析任务的可扩展式系统。最初的方案有应用于更新密集型任务的分布式数据库，以及专业分析任务的并行数据库。其中并行数据库更是从原型系统一直发展到可用的商业系统水准。然而相比之下分布式数据库却发展的差强人意且从未得到商业化。
2. 可扩展海量数据管理系统
应用服务的数据访问模式的变革，再加上急速扩增的需求，催生了一种被称作键值对（Key-Value ）存储的新型系统。键值存储模式出现后受到各种企业的追捧并且得到了广泛采用。在工业界和学术界，MapReduce 模式以及其开源实现项目Hadoop 都得到了迅速应用普及。而且更进一步，针对不同的应用场景下的可用性以及运行效率提升，也不断有各种Hadoop 改良解决方案被提出。部署在云端的应用服务都有着各自对于数据管理的迫切需求，这样就有诸多的可供研究的空间。总之，为解决各领域大数据管理带来的挑战，催生了数不胜数的系统方案。各种云计算服务都需要对分布存储的、海量的数据进行处理分析。具体而言，云计算应用面临的数据管理挑战体现在数据的海量性、异构性以及非确定性。针对这些特点，来构建高可用性及强可扩展性的分布式数据存储系统，目前云计算系统中的数据管理技术除了MapReduce 之外，主要还包括Google 的GFS 、 BigTable 和亚马逊的Dynamo 。
2.1 MapReduce 技术
MapReduce 是Google 提出的一个软件架构，用于大规模数据集（大于1TB ）的并行计算。作为一个新的编程模型，MapReduce 将所有针对海量异构数据的操作抽象为两种操作，
即Map 和Reduce 。使用Map 函数将任务分解为适合在单个节点上执行的计算子任务，通过
图1. MapReduce 架构模型
调度执行处理后得到一个“Key-Value ”集。而Reduce 函数则根据预先制定的规则对在Map 阶段得到的“Key-Value ”集进行归并操作，得到最终计算结果。MapReduce 架构模型最为成功之处就在于，让人们可以根据需求将针对海量异构数据的处理操作（无论是多么复杂）分解为任意粒度的计算子任务，并能够在多个计算节点之间灵活地调度计算任务以及参与计算的数据，从而实现计算资源和存储资源配置的全局最优化。另外，MapReduce 方法在将Map 任务和Reduce 任务分配到集群中的相应节点时，会考虑到数据的本地性(Data Locality)，即一般会将Map/Reduce安排到参与计算数据的存放节点或附近节点来执行。
2.2 GFS 技术
GFS （Google File System ）是一个大型的分布式文件系统。它为Google 云计应用算提供分布式海量存储解决方案，并且与MapReduce 和BigTable 等技术结合十分紧密，形成Google 独有的一套的云计算解决方案。GFS 的架构模型如图2所示，GFS 将整个系统的节点分为三类角色：Client （客户端）、Master （主服务器）和Chunk Server（数据块服务器）。Client 是GFS 提供给应用程序的访问接口，它是一组专用接口，不遵守POSIX 规范，以库文件的形式提供。应用程序直接调用这些库函数，并与该库链接在一起；Master 是GFS 的管理节点，其数量在逻辑上只有一个，它保存系统的元数据，负责整个文件系统的管理，是GFS 文件系统中的大脑；Chunk Server负责具体的存储工作，数据以文件的形式存储在Chunk Server 上，Chunk Server 的个数可以有多个，它的数目直接决定了GFS 的规模。GFS
将文
件按照
图2. GFS架构模型
固定大小进行分块（默认是64MB ），每一块称为一个Chunk （数据块），每个Chunk 都有一个对应的索引号（Index ）。客户端应用在访问GFS 时，首先访问Master 节点，获取将要与之进行交互的Chunk Server信息，然后再行直接访问这些Chunk Server完成数据存取。GFS 的这种设计方法实现了控制流和数据流的分离。Client 与Master 之间只有控制流，而无数据流，这样就极大地降低了Master 的负载，使之免于成为制约系统性能的一个瓶颈。Client 与Chunk Server 之间直接传输数据流，同时由于文件被分成多个Chunk 进行分布式存储，Client 又可以同时访问多个Chunk Server ，从而使得整个系统I/O活动高度并行，整体性能得到极大提升。
2.3 BigTable 技术
Google 提出的BigTable 技术是建立在GFS 和MapReduce 之上的一个大型的分布式数据管理系统。BigTable 实际上的确是一个很庞大的表结构，它的规模可以超过1PB （1024TB ）。它将所有数据都作为对象来处理，形成一个巨大的表格。对于BigTable ，Google 给出了如下定义：BigTable 是一种为了管理结构化数据而设计的分布式存储系统，系统中存放管理数据可以扩展到非常大的规模，例如在数千台服务器上的达到PB 规模的数据，现在有很多Google 的应用程序建立在BigTable 的基础之上，例如Google Earth 。而基于BigTable 模型实现的Hadoop Hbase开源项目也逐渐在越来越多的应用中发挥作用。
BigTable 就是一个稀疏的、多维的和有序的Map ，每个Cell （单元格）由行关键字、列关键字和时间戳来进行三维定位。Cell 的内容本身是一个字符串，举例来说，当存储一个网页的内容，其数据模型如图3所示。在图3中，反向的URL “com.cnn.www ”是这一行的关键字，“contents ” 这列存储了多个版本的网页内容，其中每个版本都有一个时间戳。BigTable 还提供一个用于将多个相似的列整合到一起的Column Family（列组）机制。比如，
“anchor ”这个Column Family就有“anchor ：cnnsi.com ”和“anchor ：my.look.ca ”这个两个列。通过Column Family这个概念，使得表可以轻松地横向扩展。
图3.BigTable 数据模型
图3中，对于网页文档的全文有一个文本列，还有一个标题列，这样一来，没有必要对全部的文档文本进行分析，就可以快速地找到文档的标题。有两列用于锚文本，一个是“anchor ：other.com ”，包含从站点other.com 指向example.com 的超链接的锚文本；如图3中的单元所示，超链接上的文本是“example ”。anchor ：null.com 描述了从null.com 指向example.com 的一个超链接上的锚文本是“点击此处”。这些列都属于锚文本列组（column group ）。可以向该列组中增加其他的列，以增加更多的链接信息。
图4.Tablet 位置结构
BigTable 使用一个3层的、类似B+树的结构存储Tablet 的位置信息，如图4所示。第1层是一个存储在Chubby 中的文件，它包含了Root Tablet的位置信息。Root Tablet包含了一个特殊的metadata 表里所有的Tablet 的位置信息。metadata 表的每个Tablet 包含了一个用户Tablet 的集合。Root Tablet实际上是metadata 表的第1个Tablet ，只不过对它的处理比较特殊（Root Tablet永远不会被分割）这就保证了Tablet 的位置信息存储结构不会超过3层．其中在Chubby 中存储着多个Root Tablet的位置信息。Metadata Tables中存储着许多User Table的位置信息。因此当用户读取数据时，需先从Chubby 中读取Root Tablet的位置信息然后逐层往下读取直至找到所需数据为止。
BigTabl e 的负载均衡采用的是传统的方式，BigTable 在执行任务时，在任意时刻每个Tablet 只被分配到一个Tablet 服务器。依靠一个Master 服务器监视子表Server
的负载情况，
根据所有子表服务器的负载情况进行数据迁移的，比如将访问很热的列表迁移到压力轻的子表服务器上，以调节Tablet 服务器的负载平衡。
2.4 Dynamo 技术
Dynamo 是一个高可用，专有的键值结构化存储系统，或分布式存储系统。它同时具有数据库和分布式哈希表的特征，并不直接暴露在外网，而是为Amazon Web Services（AWS ）提供底层支持。目前Dynamo 已经有很多实现，典型的有：Apache Cassandra、Project Voldemort以及Riak 。
图5.Dynamo 架构
Dynamo 是采用分布式哈希表作为基本存储架构和理念，这个架构最大特点是能让数据在环中均匀存储，各存储点相互能感知（因数据需要在环内转发，以及相互之间进行故障探测，因此需要节点之间的通信），自我管理性强，因为它不需要Master 主控点控制，无单点故障危险。此外，Dynamo 的主要优点是：它提供了使用3个参数（N ，R ，W ），可以根据实际的需要来调整它们的实例。Dynamo 支持对对象的不同版本进行记录和处理，并且可以将不同版本提供给应用，供应用自身更加灵活地进行合并。对象的副本数遵循(N，R ，W) 的规则，N 个副本，如果R 次读取的一致，则确定读取成功；如果W 次写入成功，则认为写入成功；不要求全部N 个都成功完成，只要R+W>N，数据的最终一致性就可以得到保障。在这里，读操作比一次写多次读的系统（比如HDFS ）麻烦，但写操作变简单了，这一点适应了一些应用场景下的需求。
负载均衡对于Dynamo 系统而言是天生的优势，因为它采用了分布式哈希表将数据都均匀存储到各个点，所以没有访问热点，各点的数据存储量和访问压力应该都是均衡的。
3. 总结
在新兴的云计算数据管理领域Google 的BigTable 、MapReduce 和亚马逊的Dynamo 技术针对云计算海量数据处理的问题和应用特点有了很多创新，综合来看，采用分布式的存储技术可用于大型分布式的、需要对大量数据进行访问的应用。如GFS ，其运行于各种类似的普通硬件上，提供容错功能，为用户提供低成本、高可靠性、高并发和高性能的数据并行存取访问。针对数据的非确定性、分布异构性、海量、动态变化等特点，采用分布式数据管理技术，通过采用BigTable ，Hbase 等分布式数据库技术对大数据集进行处理和分析，面向用户提供高效的服务。为了高效地利用在分布式环境下的数据挖掘和处理，采用基于云计算的并行编程架构，如MapReduce ，将任务自动分成多个子任务，通过映射和化简两步实现任务在大规模计算节点中的调度与分配。后台复杂的并行执行和任务调度对用户和编程人员则无须关心。
4. 参考文献
[1] 刘正伟, 文中领, 张海涛等. 云计算和云数据管理技术[J].计算机研究与发展,2012,49(z1):26-31.
[2] 周晓方, 陆嘉恒, 李翠平, 等. 从数据管理视角看大数据挑战 [J][J]. 中国计算机学会通讯, 2012, 8(9): 16-20.
[3] 陈全, 邓倩妮. 云计算及其关键技术[J]. 计算机应用, 2009, 29(9): 2562-2567.
[4] Agrawal D, Das S, El Abbadi A. Big data and cloud computing: current state and future opportunities[C]//Proceedings of the 14th International Conference on Extending Database Technology. ACM, 2011: 530-533.
[5] Agrawal D, Das S, El Abbadi A. Big data and cloud computing: new wine or just new bottles?[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 1647-1648.