以下为《翻译：CoHadoop：Hadoop上灵活的数据摆放和访问》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

翻译：CoHadoop：Hadoop上灵活的数据摆放和访问

Mohamed Y. Eltabakh, Yuanyuan Tian, Fatma O¨ zcan

Rainer Gemulla+, Aljoscha Krettek#, John McPherson

BM Almaden Research Center, USA fmyeltaba, ytian, fozcan, jmcphersg@us.ibm.com

+Max Planck Institut f¨ur Informatik, Germany rgemulla@mpi-inf.mpg.de

#IBM Germany aljoscha.krettek@de.ibm.com

说明：原文标题为CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop，是VLDB大会上的一篇论文，出于学习的目的进行翻译，所有权益归原作者所有。以下是原文版权信息。

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Articles from this volume were invited to present their results at The 37th International Conference on Very Large Data Bases,

August 29th September

3rd 2011, Seattle, Washington.

Proceedings of the VLDB Endowment, Vol. 4, No. 9

Copyright 2011 VLDB Endowment ***/

11/06... $ 10.00.

摘要

Hadoop已经成为一个大数据分析中有吸引力的平台。本文中介绍了一个Hadoop的主要性能瓶颈：缺少将相关的数据一并摆放在一组同样的节点中的能力。为了解决这个瓶颈，我们实现了CoHadoop。它是一个Hadoop的轻量级扩展，允许应用来控制数据存储的位置。与以前的方法不同的是，CoHadoop保留了Hadoop的灵活性，也就是说它不需要用户将其数据转换为特别的格式（比如一个关系数据库或一个特殊的文件格式）。它所采用的方法是，由应用程序给出注释（Hints）来标明某个文件的集合是相关的而且将来可能被一起来处理；然后CoHadoop尽量将这些文件一并摆放（Colocation）在一组同样的节点中以提升性能。我们的方法尽量保留了Hadoop的高可用和容错特性。“Colocation”的特性增强可以被用来改善许多操作的性能，比如索引、分组、聚合、列存储、关联和序列化。我们利用Hadoop的常用的日志处理场景对关联和序列化进行了深入研究，在这些场景下降可以利用“一并摆放”的特点来实现Map-Only的算法。在我们的实验中，我们发现CoHadoop比原生的Hadoop和其他先前的改进性能有很大提升。特别的是，不仅比那些重分区的算法更好，而且也比那些进行分区，但没有进行“Colocation”的算法更好。

一、介绍

大数据分析变得对企业来说不可或缺，因为他们需要从越来越多的数据中获得洞察。Google MapReduce算法以及其开源实现Hadoop为企业提供了一种性价比很高的选择。Hadoop是一个支持数据并行计算的框架，可以运行在1000+节点和PB级数据环境中。

在Hadoop中，Map和Reduce函数操作在HDFS上的数据。HDFS将大文件存储为一系列的分布在集群上各个节点的块，并通过副本的方式来提供容错。HDFS的数据摆放策略是通过随机的摆放让各个节点更加平衡，它没有考虑任何数据特征。特别的是，HDFS没有提供任何手段来将相关的数据放置在一组相同的节点上。为了克服这个短板，我们才提议了CoHadoop，一个Hadoop上的轻量级扩展机制，来允许应用程序控制数据存放的位置。

我们通过日志处理场景来研究数据“Colocation”的好处，这是Hadoop的一个通常使用的场景。在这种场景下，数据从事件日志（比如点击流、CDR、应用日志或交易日志等）中批量累积得到。每批数据被Hadoop获取并存储在一个或多个HDFS文件中。日志分析中两项通常的操作是：1、将日志数据与其他参考数据JOIN起来；2、序列化，例如计算用户session。我们的实验指出，数据“Colocation”可以显著提升以上数据处理任务的性能。

如同在参考文档【1、16、10、6】中所显示的那样，JOIN性能可以被两个输入文件的共同分区操作而显著提升。在这些情况下，性能的提升得益于消除了数据shuffling过程和Reduce过程。通过将这些数据分区放置在一起，JOIN操作可以通过一个MAP-ONLY的JOIN算法来实现，没有远程的IO。一些早期的研究【10】也支持数据Colocation的操作，另外其他一些【1、6】通过重量级的修改来实现将相关数据的分区放置在一起：HadoopDB【1】将数据存储在一个本地的DBMS中并因此破坏了Hadoop的动态调度和容错特性；Hadoop++【6】通过创建一个特殊的“特洛伊”索引而将两个输入文件进行共同分组。虽然这种方法不需要修改Hadoop，但是它是一种静态的解决方案，需要用户重组他们的输入数据。实际上，Hadoop++仅能对同样任务创建的两个文件进行“Colocation”，并且需要将这些数据重组为新文件再灌入HDFS。在类日志处理这样的应用中，数据是增量且连续的到达，这就使得将很多文件进行“Colocation”而不仅是两个文件变得非常重要，同样这还需要将新文件增量的附加在已有文件之后。

同以前的方法相比，我们解决了应用来将文件进行Colocation的问题。为了达到这个目的，我们对HDFS进行了扩展来使得在文件系统级别Colocation一系列文件成为可能。我们的扩展对HDFS的修改达到了最小化：我们引入了一个新的文件属性来识别一组相关的数据文件，并且修改了HDFS的数据放置策略来将这些相关文件的所有副本Colocation在一起。这些改变保持了Hadoop的优点，包括负载均衡和容错。这种方法也使得各种不同的应用可以通过这个新的“相关文件”的属性来进行具有数据“Colocation”特点的数据访问。案例包括对已经进行Colocation后的日志文件和其参考文件进行JOIN，对Colocation的各个分区执行分组和聚合操作，将索引文件和对应的数据文件放置在一起，将一个表的各个列放置在一起（每个列存储为一个单独的文件）等等。CoHadoop的灵活性对MapReduce上的高级语言，例如Pig、Hive和Jaql非常有吸引力。我们希望这些系统可以自动地利用CoHadoop的能力来优化查询。

我们进行了扩展的实验来评估CoHadoop的性能。在我们的实验中区分了由于分区和Colocation带来的性能提升，并发现仅仅进行数据分区是不够的，我们还需要将相关的分区进行Colocation以便达到最大的性能提升。我们观察到CoHadoop提供了显著地性能改善；不需要修改Hadoop的调度；Hadoop的容错和数据分布特性得以保留。我们也与Hadoop++的“特洛伊”索引进行了比较，结果显示在CoHadoop的灵活性和增加的功能下，它的性能比Hadoop++要好。

本文的贡献可以总结如下：

我们引入了一种灵活、动态和轻量级的方法在HDFS中Colocation相关文件。我们的解决方案不是为了一个特别的场景所涉及，它可以应用在多种场景，覆盖之前的许多工作；

我们定义了两种日志处理的应用场景，例如JOIN和序列化。在这些场景中，通过分区相关文件并且Colocation它们来显著提升查询效率。我们也提供了访问已经进行了Colocation的数据的高效算法，这些也可以用于增量和连续的数据采集场景；

我们从定性和定量两个角度通过一个随机模型对CoHadoop的容错、数据分布和数据丢失情况进行了分析；

我们报告了不同设置情况下CoHadoop执行JOIN和序列化查询的实验结果。

以下论文组织如下：在第二节，我们同了HDFS的背景信息。然后在第三节描述了HDFS上的Colocation。在第四节中，我们提供了JOIN和序列化算法来通过Colocation访问数据。第五节讨论了我们的实验结果。最后，我们在第六节中回顾了相关工作，并在第七节进行了总结。

二、HDFS背景知识

HDFS是一个分布式文件系统，提供了高吞吐率的数据存储和访问。文件被分割成固定大小的块，存储在datanode上。块大小是可以配置的，默认64MB。文件只能被写一次，也就是说对已有文件的修改是不允许的。HDFS的Namenode存储了文件系统的目录信息。它也维护了一个活动的Datanode列表以及它们上面的数据块的BlockMap。一旦Datanode启动，它就在向Namenode注册它存储的文件块，这些块就被加到BlockMap中。一旦Namenode检测到一个Datanode故障，故障节点的所有块就被从BlockMap中移除。Datanode根据请求将块送给客户端，同时也从客户端获取新的块数据。这个过程由Namenode来进行协调，它指导客户端找到正确的Datanode。

HDFS通过副本的机制来实现快速的故障恢复。默认三份副本，这意味着一个块被存储在三个不同的Datanode上。HDFS使用一个简单的数据放置策略来选择Datanode存储块和他们的副本。这个默认的策略将一个新创建的块的第一个副本放在这个块创建所在的本地Datanode上（只要有足够的空间）。这叫做就近写（Write affinity）。然后HDFS选择同机架的一个Datanode存储第二个副本，一个不同机架的Datanode来存储第三副本。我们修改了这个数据放置策略来支持Colocation，在第三节会详细介绍。

Hadoop利用InputFormats来定义文件如何被分割并由Map任务使用。Hadoop提供了一些InputFormats。文件上的输入格式以抽象类FileInputFormat为基类。当一个Hadoop任务启动的时候，带需要执行文件的路径参数的FileInputFormat会被传递给它。它然后将这些文件分为一个或多个分片（splits），每一个分片对应了MapReduce程序中的一个Map任务。默认情况下，不同的FileInputFormat实现将一个文件分成64MB的chunk（HDFS的默认块大小）。Hadoop调度器尽量将Map任务调度给那些包含分片的本地副本的Datanode。InputFormats为用户提供了一种扩展的手段来通过组装定制化的分片来将一些分布的数据提供给Map任务。在第四节，我们将展示这种InputFormat的扩展如何提升JOIN和聚合算法的效率。

三、数据的Colocation

HDFS当前数据放置策略的目标是为了通过将数据均衡地分布在所有Datanode上来获得均衡的负载【18】。这种简单的策略对那些仅需要访问单个文件的Hadoop应用程序来说大部分表现都很好，但是那些需要处理来自不同文件的应用就要通过定制化的策略才能获得显著地性能提升。CoHadoop，一种轻量级的Hadoop扩展，使得应用程序能轻易定义和使用这种定制化的策略。它被设计成很容易被应用使用，同时保留了HDFS的负载均衡和容错特性。在本节中，我们描述和分析了CoHadoop的数据Colocation方法；访问Colocation后的数据的算法和应用程序将在第四节被讨论。

对并行数据库的研究以及近段时间对Hadoop的研究显示——精细化的数据组织方式使得查询操作的算法优化成为可能。例如，数据库中常采用如下技术：1、将数据在某个JOIN或分组的字段上根据使用的模式进行分区；2、将对应的分区存储在相同的节点。这种想法引入Hadoop并不简单：虽然在Hadoop中进行分区不难，但是Colocation就难了。这是因为Hadoop没有提供相应的手段使得应用可以控制数据存储的位置。没有了Colocation，数据Shuffling的开销和网络的开销就降低了分区获得的收益。为了解决这些问题，CoHadoop提供了一个通用的机制，允许应用在需要的时候可以在文件系统的级别控制数据摆放。这个机制可以被用在诸如将对应的分区以及它们的副本存储在一个相同的Datanode节点集中。

/

为了实现Colocation，CoHadoop扩展了HDFS，提供了一个新的文件级属性，称之为Locator。并且修改了Hadoop的数据放置策略，使得它能充分利用Locator属性。在我们的实现中，每个Locator对应一个整数，当然其他数据类型也是可以的。在文件和Locator之间是一个N对1的关系：每个HDFS上的文件都被分配最多一个Locator，数个文件可以被分配给同一个Locator。拥有相同Locator的文件被放置在一个同样的Datanode节点集上，没有Locator的文件通过HDFS的默认策略来放置。注意Colocation影响所有的数据块，包括副本。图1中显示了两个文件A和B通过同一个Locator进行Colocation的示例。A的两个HDFS块和B的三个HDFS块都被放置在同一组Datanode上。

为了管理Locator信息并追踪按照这种策略放置的文件，我们引入了一个新的数据结构——在Namenode上的Locator表。其存储了一个Locator到文件列表的映射。图1中显示了一个示例集群上的Locator表。类似HDFS上块到节点的映射，Locator表也不同步到磁盘上。而是在Namenode的内存中进行动态的管理，当NameNode重启的时候它从文件系统的映像中重建起来。为了实现重建功能，我们将每个文件的Locator属性存储在其INode中，这是一个保留在磁盘上的数据结构来跟踪所有的文件属性。

数据放置通过以下方式修改：每当一个文件f带着Locator属性l被创建的时候，我们查询Locator表检查是否包含l的项。如果没有，就添加一个（l,f）的项到其中并使用默认的数据放置策略来选择存储各个副本的数据节点。否则的话，Locator l就是已经有了的，我们可以找到所有与Locator l相关的文件。对于每个文件，我们查询NameNode的BlockMap数据结构来找到这些块以及他们所存储的位置（也就是一组DataNode）。为了存储新文件的r个副本，我们需要从上述节点集中选择r个节点。我们选择拥有Locator l，并存储了最高数量的块，且拥有足够空间的r个节点来存储新文件。如果上述节点中不足r个拥有足够的空间，我们就通过HDFS的默认数据放置策略选择剩余的节点。这样在CoHadoop中的数据放置策略就变成尽力而为的：在整个集群有足够空间的情况下新文件的创建总是会成功，数据并不需要按照严格的Colocation策略来进行强制的移动。我们选择这种方法是因为它保留了HDFS的容错特性，并且没有重组数据的开销。当每个节点都有足够空间且没有错误发生的时候，CoHadoop总是能确保实现Colocation。

就像上面指出的那样，Colocation对集群上的数据分布有一定的影响。实际上，数据分布依赖于几个因素，包括：每个Locator分配的文件数，文件创建的顺序，文件大小和每个节点的磁盘容量。例如：如果为一个Locator分配了太多的文件以至于当前节点集r没有空间了，CoHadoop会切换到一组新的节点集来存储此Locator的后续文件。当这种情况发生的时候，仅一部分拥有相同的Locator的文件实际上实现了Colocation：CoHadoop为了保证可用性牺牲了完全的Colocation。注意，因为这个原因，创建的文件的顺序也可能影响数据的分布，因为第一个文件的放置位置决定了后面那些拥有同样Locator的文件的放置位置。通常来说，一个或几个Locator的过度使用会导致数据分布上的倾斜。我们推荐（或者说是建议）应用应该明智地使用Locator来到达数据分布的平衡性。

在附录9.1中，我们分析了CoHadoop的数据分布和容错属性，并通过一个随机模型与原生的Hadoop进行比较。考虑到Datanode节点故障情况下的数据丢失情况，我们经过分析发现CoHadoop丢失数据的可能性低于原生Hadoop。不过在数据丢失发生的时候，CoHadoop会丢失更多的数据。数据丢失的可能性和数量可以相抵：丢失数据的平均期望是一样的。考虑集群上的数据分布，我们的模型显示当Locator被很好的使用了的情况下，CoHadoop只是轻微地增加了装载中的变化量。我们的实验指出，这些增加并没有给查询性能或容错带来负面的影响。

四、访问Colocation后的数据

所提出的数据Colocation机制可以被许多不同的应用程序所访问。在本节中，我们通过举例的方式讨论了如何使用Colocation来改善日志处理中的JOIN和序列化操作。

4.1原生Hadoop中的日志处理

在日志处理中，事件的日志（比如点击流、CDR、应用日志或者交易日志）被连续的收集。大量的日志从不同的服务器源源不断地同步过来。为了分析这些数据，日志文件被放到HDFS上来处理。另外，参考数据，例如用户信息和账户信息被用来在分析过程中进行信息的补充。我们描述了两个主要的日志分析场景，并演示了他们怎么在原生的Hadoop上执行的。

4.1.1 序列化

日志处理中最常见的就是序列化，它将日志分成用户Session。通过将日志按照用户或者账户进行分组，并按照时间序列进行排序，然后按照排序的顺序打上序列号来实现。标准的MapReduce算法是重新分区来实现。

基本的序列化算法：Mapper读取多个日志文件，并转换为K-V对（比如按照账户ID为KEY进行输出）。Map的输出在Shuffling过程中被分组，并提供给Reducer。然后Reducer对每个组中的记录按照时间进行排序，并打上序列号。

4.1.2 JOIN

另外一个重要的查询就是在日志和参考数据之间进行等值的JOIN；比如将交易日志和对应的账户信息进行关联。虽然有不同的MapReduce的关联算法，最常用的还是基于重新分区的JOIN算法。

基本的JOI 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 本放置。我们的数据放置策略可以使用这个API而应用在HDFS上，由于新版本HDFS的这种特性，代码的维护开销降低了。（当然，与文件关联的Locator属性是仍然需要的）

七、总结

我们展示了CoHadoop，一个轻量级的HDFS上的Colocation解决方案。通过我们的方法实现Colocation简单且灵活；它可以在多种应用程序中被不同的方式利用。我们定义了两个日志处理的案例（JOIN和序列化），描述了Map-Only算法来实现对Colocation数据的访问。我们研究了CoHadoop在不同设置下的性能，并与原生Hadoop和仅进行分区但不Colocation的解决方案进行比较。我们实验表明分区和Colocation同时实施提供了最好的性能。理论分析和实验指出，CoHadoop在最大程度上保留了Hadoop的容错特性。

致谢：We would like to thank Prof. Jens Dittrich and his team for providing us with the Hadoop++ source code.

参考和附录略，由人工智能负责翻译，仅限于学习用途。

[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

1. dunyadan-ilginc-haberler006
2. hadoop复习
3. 动态图代码内容
4. 译文_测温人脸识别说明书
5. 雅思听力 807 单词升级版单某某
6. -历年大学英语四级真题及答案
7. 01 高考核心语法知识点精练1（名词）-届高考英语一轮复习核心语法知识精讲精练(通用版）
8. 第二周第一次直播课教案讲稿
9. 纽约时报：关于新型冠状肺炎疫情的3个关键性问题外刊精读
10. Challenge to All演讲稿
11. 王凯 《Can you make cakes？》 教学设计
12. 索马鲁肽
13. YOLO V1
14. Python and HDF5
15. Full_Paper_Template
16. 4425
17. 英文邮件常用句式-查找

以上为《翻译：CoHadoop：Hadoop上灵活的数据摆放和访问》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。