【转】经典论文翻译导读之《A Bloat-Aware Design for Big Data Applications》

【译者预读】

世界上最窝囊的莫过于运维说可以给你8核16G内存的高配机器你却只能说虚成4份再给我吧。。。为何，因为怕Java程序驾驭不了这么大的内存。实践发现JVM堆内存调到2G以上就要非常小心GC带来的巨大开销了。本篇论文从理论和实践上摸索出了一条解决之道，其思路清晰、分析透彻，想享受Java便利又远离GC困扰的，可供参考。

 

1简介

在过去十年里，在数据驱动商业智能持续增长的需求下，各种大规模数据密集型应用开始繁荣兴盛，它们经常要处理成吨的数据（TP或PB规模）。面向对象风格的语言，比如Java，经常被开发者使用来实现这些应用，首要原因就是Java的快速开发周期和丰富社区资源。尽管使用这种语言让开发变得简单，它带来的显著性能问题却如噩梦挥之不去——在托管式运行时系统中存在各种与生俱来的低效因素，外加在有限内存空间中处理大规模数据的冲击，最终导致了惊人的内存膨胀和性能退化。

本片论文提出一个膨胀感知的设计范式，旨在开发高效、可伸缩的大数据应用，即使使用的是面向对象、需要GC的语言。我们首先会学习几个典型的内存膨胀模式。这些模式总结自两个广泛使用的开源大数据应用的用户抱怨邮件。然后我们将讨论一种新的设计范例来消除膨胀。通过示例和实验，我们演示了使用此范例编程不会显著增加开发成本。然后我们分别使用新设计原则和便利的面向对象设计原则实现了一些常用的数据处理任务以作对比。实验结果显示新设计范例极大的改进了性能——甚至在数据规模不那么庞大时，我们都看到了2.5倍以上的性能提升，随着数据集合的扩大，性能收益成比例上升。

 

2 对大数据应用的内存分析

本章节中，我们通过对Giraph和Hive这两个流行的数据密集型应用的研究，来分析用Java对象来表述、处理数据对性能和可伸缩性的冲击。我们的分析会深入到最基本的问题——时间和空间：1 被对象头和对象引用消耗的大量内存空间，导致很低的内存堆积密度，2 海量对象和引用导致悲催的GC效率。

 

2.1 堆积密度低

在Java运行时，每个对象需要一个头空间，以支持类型管理和内存管理。数组对象需要附加空间来存储它的长度。比如，在Oracle的64位HotSpot JVM中，常规对象、数组的头空间分别占据8和12字节。在一个典型的大数据应用中，JVM堆中经常包含很多小对象（比如代表记录ID的Integer），其中头空间的开销不容忽视。而且由于面向对象数据结构的大量使用，空间会越发低效。这些数据结构经常使用多级委托来达到它们的功能，导致大量空间被用来存储指针而不是真实数据。为了衡量空间使用的性价比，我们使用了一个标准，名为堆积密度(Packing Factor)，它表示能存储到一个固定大小内存中的真实数据的最大数量。我们的分析主要针对大数据应用场景，也就是海量数据分批流经一个固定大小的内存。
为了分析典型大数据应用的堆内存堆积密度，我们使用PageRank算法（一个基于Giraph构建的应用程序）作为一个例子。PR（PageRank下面简称PR）是一个连接分析算法，它在一个图结构中为每个顶点分配权重，通过迭代的方式、基于每个顶点入度邻居的权重来计算。这个算法广泛使用在搜索引擎的页面排名中。
我们在不同的开源大数据计算系统上运行了PR，包括Giraph、Spark和Mahout，使用一个6机组、180台机器的集群。每个机器有2个quad-core Intel Xeon E5420处理器和16GB的RAM。实验的数据集合（web graph dataset）共70GB，包含1,413,511,393个顶点。我们发现他们仨没有谁能成功的处理这个数据集合，都崩溃在java.lang.OutOfMemoryError，数据是分区在每台机器上（少于500MB）的，物理内存足够。

我们发现很多开发者遇到了类似的问题。比如，我们在Giraph的用户邮件中看到很多OutOfMemoryError的抱怨。为了定位瓶颈，我们决定用PR来做一个定量分析。Giraph包含一个PR算法的例子，部分数据结构的表述如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public abstract class EdgeListVertex< I extends WritableComparable, V extends Writable, E extends Writable, M extends Writable> extends MutableVertex<I, V, E, M> {     private I vertexId = null;     private V vertexValue = null;     /** indices of its outgoing edges */     private List<I> destEdgeIndexList;     /** values of its outgoing edges */     private List<E> destEdgeValueList;     /** incoming messages from the previous iteration */     private List<M> msgList;     ......     /** return the edge indices starting from 0 */     public List<I> getEdegeIndexes(){     ...     } }

在Giraph中处理的图是带标记的（顶点和连线都有值），连线是有向的。EdgeListVertex类代表了图中一个顶点。在它的字段里，vertexId和vertexValue存储了ID和顶点值。字段destEdgeIndexList和destEdgeValueList，引用的分别是出度连线的ID列表和值列表。msgList包含上一次迭代发来的消息。图1以一个EdgeListVertex对象为根顶点展示了此图结构。

在Giraph的PR实现中，I,V,E和M的真实类型是LongWritable、DoubleWritable、FloadWritable和DoubleWritable。图中每个连线权值相同，因此destEdgeValueList引用的list一直是空的。假设每个顶点平均下来有m个出度连线和n个消息。得到表1，其展示了一个顶点数据结构在Oracle64位HotSpot虚拟机上的内存消耗统计。表中每行针对一个类，展示了它在这种数据结构中需要的对象数量、这些对象的头空间使用的字节数量、引用类型的字段使用的字节数量。一个顶点的空间额外开销就是16(m+n)+148（也就是头size和指针size的总和）
另一方面，图2展现了一个理论上的内存布局，其中仅仅存储必需信息（不需要使用对象）。在这种场景下，一个顶点需要m+1个long值（顶点ID），n个double值（消息），和两个32位的int值（出度数量和消息数量），这些消耗总共8（m+n+1）+16=8(m+n)+24字节的内存。这比表1中对象头和指针的内存消耗的一半还小。很明显，在基于对象的表述中，空间额外开销超过了200%（相比必需开销）。

 

 

2.2 当对象和引用的数量达到一定规模

在一个JVM里，GC线程会周期的遍历堆中所有存活的对象，以鉴别和回收死对象。假设存活对象的数量是n，对象组成的图结构中连线的总数量是e，一个追踪垃圾回收算法的计算复杂度就是O(n+e)。在大数据应用中，对象图往往包含超大规模的、隔离的对象子图，有些代表数据项，有些代表为处理数据项而创建的数据结构。因此内存中数据对象的规模庞大，n和e都比常规的Java应用大好几个数量级。

我们使用一个在Hive的用户邮件的异常例子来分析这个问题：

FATAL org.apache.hadoop.mapred.TaskTracker:
Error running child : java.lang.OutOfMemoryError: Java heap space
org.apache.hadoop.io.Text.setCapacity(Text.java:240)
at org.apache.hadoop.io.Text.set(Text.java:204)
at org.apache.hadoop.io.Text.set(Text.java:194)
at org.apache.hadoop.io.Text.<init>(Text.java:86)
……
at org.apache.hadoop.hive.ql.exec.persistence.Row
Container.next(RowContainer.java:263)
org.apache.hadoop.hive.ql.exec.persistence.Row Container.next(RowContainer.java:74)
at org.apache.hadoop.hive.ql.exec.CommonJoinOperator. checkAndGenObject(CommonJoinOperator.java:823)
at org.apache.hadoop.hive.ql.exec.JoinOperator. endGroup(JoinOperator.java:263)
at org.apache.hadoop.hive.ql.exec.ExecReducer. reduce(ExecReducer.java:198)
……
at org.apache.hadoop.hive.ql.exec.persistence.Row
Container.nextBlock(RowContainer.java:397)
at org.apache.hadoop.mapred.Child.main(Child.java:170)

我们检查了Hive的源码，发现堆栈顶端的Text.setCapacity()并不是问题根源。在Hive的join实现里，JoinOperator持有来自RowContainer中一个输入分支的所有Row对象。若大量Row对象被存储在RowContainer中，单次GC都会变得十分昂贵。在堆栈里，Row对象的总size超过了堆上限，导致了内存溢出。

即使在内存溢出没有触发的场景中，大规模数量的ROW对象也会导致性能退化。假设Row对象数量为n，那GC遍历复杂度至少是O(n)。对Hive来说，n会随着输入数据成比例的增长，这能轻易的导致大量GC开销。下面也是一个类似的例子，来自StackOverflow的用户报告，尽管表现不太一样，根本原因是同一个：

“我写了个Hive查询，它select大约30个列、大概400，000条记录、插入到另一个表。我的SQL里有个内连接。查询失败，因为一个Java GC overhead limit exceeded异常。”

事实上，在Hive邮件列表或者StackOverflow站点上经常能看到关于GC开销太大的抱怨。更糟的是，从开发者角度来说做不了什么优化，因为低效的根源在于Hive的内在设计。Hive中所有数据处理相关的接口都需要使用Java对象来表述数据项。为了操作Row里包含的数据，我们需要将其封装为一个Row对象，遵循接口设计。如果我们希望完全的解决这个性能问题，那就需要重新设计和实现所有相关的接口，任何用户都无法承受这种颠覆。这个例子促使我们在设计层面寻求解决方案，不能再受限于传统面向对象的条条框框。

 

3 膨胀感知的设计范例

上述性能问题的根本原因在于这两个大数据应用都是完全遵循常规面向对象原则而设计和实现的：万物皆对象。对象被使用来表述数据处理器和需要被处理的数据项。创建数据处理器对象可能不会有显著的性能冲击，而对数据项使用对象表述则会导致大规模的瓶颈，妨碍应用处理大型数据集合。值得一提的是，典型的大数据应用会重复执行类似的数据处理任务，一组相关的数据项经常有类似的行为模式和生命周期，因此我们能轻易的在一个大型缓冲块里集中管理它们，这样GC就不需要遍历每个单独的数据项来检查它是否已死。比如，在Giraph的例子里，所有顶点对象在有相同的生命周期；在Hive里的Row也是一样。所以我们很自然的想到，应该分配一大块内存区域，将所有数据项的真实内容（data字节，而不是对象）放置其中，集中管理它们，对JVM来说这一片内存区域整体才是一个对象，如果数据项不再需要只需回收这一个整体对象。

基于这个观察，我们提出一个膨胀感知的设计范例，旨在开发高效的大数据应用。这个范例包含下列两个重要的组成部分：1 将小数据记录合并、组织为几个大对象（比如byte缓冲），而不是一条记录一个对象，2 通过直接的缓冲访问操作数据（在字节层面而不是对象层面）。设计范例的核心是限制对象的数量，而不是让它与输入数据成比例增长。注意这些指导方针应该在早期设计阶段就考虑明确，才能使得后期API和实现都遵从这些原则。我们构建了一个大数据处理框架Hyracks，它严格遵守此设计范例。后续将使用Hyracks运行一些示例来诠释这些设计原则。

 

3.1 数据存储设计：合并小对象

如章节2所述，用Java对象存储数据会导致内存和CPU的各种开销。所以，我们提出将一组数据项集中存储在一个Java内存page中。不像系统层面的内存page是用于处理虚拟内存，我们说的Java内存page是JVM堆中一个固定长度的连续的内存块。为了简化描述，后文中我们将使用page来表示Java内存page。在Hyracks里，每个page被表述为一个对象，类型为java.nio.ByteBuffer。将记录布置到page里能减少对象的数量，以前等于数据项的总量，现在等于page总量。因此，系统的堆积密度能更接近于理想状态。注意将数据项组合到一个二进制page只是很多方法的一种，我们后续会考虑更多的小对象合并方案。

将记录放置到page方式很多，Hyracks系统使用的是”基于slot的记录管理“[36]，其被广泛使用在现有的DBMS实现里。再次以PR算法为例，图3展现了4个顶点存储在一个page中。很容易看出每个顶点是按图2中的紧凑布局存储的，我们使用 4个slot（占据4字节）在page末尾来存储每个顶点的offset（4个顶点，所以4个offset）。这些offset将被用来快速定位数据项、支持可变长度记录。注意数据记录的格式对开发者是不可见的，所以他们能仍然聚焦在高级数据管理任务，不用关心字节格式。由于page是固定大小的，经常有小的残留空间造成浪费、不能被重用。背景介绍完毕，现在来计算这个设计的堆积密度，我们假设每个page平均拥有p条记录，残留空间有r个字节。每个顶点表述的额外开销包含3个部分:存offset的slot（4个字节）、分摊的残留空间（也就是r/p）、分摊的page对象开销（也就是java.nio.ByteBuffer这个对象的额外开销）。page对象有8字节头空间（在Oracle 64位HotSpot JVM）和一个引用（8字节）指向一个内部字节数组，此数组头空间占据12字节。所以page对象额外开销被分摊后为28/p。结合章节2.1，我们得到一个顶点总共需要 (8m+8n)+24+4+(r+28)/p 个字节，其中(8m+8n)+24被用来存储必需数据，4+(r+28)/p 是开销。由于r是残留空间的size，所以我们得到r ≤ 8m + 8n + 24，因此一个顶点的空间额外开销限制在4+(8m+8n+52)/p。在Hyracks里，我们使用32KB为page的size，p的大小区间是100到200（真实数据实验中看到的）。为了计算最大可能的开销，考虑最坏的场景，残留空间等于顶点大小。一个顶点的size在 (32768 − 200 ∗ 4)/(200 + 1)=159 到 (32768 − 100 ∗ 4)/(100 + 1)=320 之间，所以159 ≤ r ≤ 320。这样一个顶点的空间额外开销就是4字节（因为至少需要4字节为offset的slot）到 (4 + (320 + 28)/100)=7  之间。因此相对于真实数据的size，总体的额外开销率为2-4%，远低于基于对象表述的200%（章节2.1论证的）。

 

3.2 数据处理器设计：访问缓冲

实现基于buffer的内存管理后，就需要支持基于buffer的数据处理编程，我们提出了一个基于访问器的编程范式。以前我们总是在堆中创建数据结构，其中包含各种数据项，并表述它们的逻辑关系，现在，我们改为定义一个包含多种访问器的结构，每个访问器可以访问不同类型的数据。同样的，我们仅仅需要很少的访问器结构就可以处理所有数据，显著的减少堆对象。在本章节，我们要首先做个思维转变，将以前面向对象设计的数据结构转变为对应的访问器结构，然后通过一些示例来描述执行过程。

 

3.2.1 设计上的转变

假设以前我们会根据面向对象原则，为数据项设计一种数据结构，类型为D，现在我们将D换成一个访问器类——Da。开发者可以指定某个类型是否为数据项类。转变步骤如下：
Step1：假设f是D类型里的一个字段（field），类型为F，我们在Da里添加一个对应字段fa，类型为Fa，让Fa作为F的访问器类。D中的非数据项类型里只需直接拷贝到Da里（非数据项不重要，量不大，不管它，主要针对page里存的数据项内容）。

Step2: 添加一个public方法 set(byte[] data,int start,int length)到Da里。这个方法用来将访问器绑定到page中一个指定的字节范围，以访问类型D的某个数据项。这个可以做成热实例化或者lazy实例化，热实例化将会递归的为所有成员访问器fa绑定到各自的二进制区域，lazy实例化中直到成员访问器真正需要被使用时才去绑定。

Step3：对D中的每个方法M，我们在Da里创建一个对应的方法Ma。然后将M的数据项类型参数和返回值全换成对应的数据访问器类型，访问器作为参数或返回值可以用来访问它绑定字节范围中的数据项。

从常规面向对象的设计转变到上述设计，应该在早期开发阶段就实施，否则后期改造成本太大。我们未来也将尝试通过编译器实现自动的设计转变。

 

3.2.2 执行过程

在运行时，我们可以将关联的访问器理解为一个图结构，每个访问器图可以分批处理高级记录。图中每个节点是一个字段（field）的访问器对象，每个连线表示一个”成员“关系（如D类的对象中包含一个字段f，那Da和fa之间用连线表示其从属关系）。一个访问器图与它对应的堆数据结构的骨架类似，但它不会在内部存储任何数据。我们让page“流经”访问器图，访问器依次绑定到page中各数据项的字节范围继而处理该数据项。对单个线程来说，访问器图的数量与数据结构类型的数量相同，同个数据结构的不同实例能被相同的访问器图处理。

若使用热实例化，执行任务时创建的访问器对象的数量等于所有访问器图的节点总和。如果用lazy实例化，创建的访问器对象数量能显著降低，因为一个成员访问器能经常被几个相同类型的不同数据项重用。在一些场景里还需要附加的创建访问器对象。比如在数据项类中有一个compare方法，它会比较两个数据项参数，转变后的compare方法需要两个访问器对象参数在运行时执行对比。不管用什么方法实现访问器，访问器对象的数量一定是可以在编译时确定的，不会随着数据集合的基数成比例增长。

【译者注】

访问器章节看似复杂其实原理十分简单，就好像你做一个学生信息管理系统，必然有学校、班级、学生3种对象。假设有1所学校、10个班级、600个学生，若用面向对象原则，当数据需要批量处理或常驻内存时，就会创建611个对象；若使用此文范例，则只会有4个对象，1个学校访问器，一个班级访问器，一个学生访问器，还有个Page对象里面包含611个数据项的缜密字节数组。把合适的访问器移到page中合适的位置上，就能访问此位置对应的数据项，比如302班、某位同学。所以访问器对象的数量只和模型种类有关，在编译时期就能确定（而不是在运行时随着数据项增长而增长）。而且从文中看出，在单个线程里一个访问器的理想状态是单例状态，即一种访问器类型只创建一个对象，串行的依次将它移动到合适的偏移，一个个的访问数据项。 但是某些时候不是单例，比如班级里原本只有一个数组访问器成员，ListAccessor<学生> students，现在要分为两个数组——ListAccessor<学生> maleStudent、ListAccessor<学生> femaleStudents，男女同学两拨，而访问器类型相同，却在访问器图结构中有两个成员对象（若是热实例化模式那就是俩，若是lazy模式那就是1个，可以重复使用，每次使用只需set新偏移量）。再比如Da类中有些方法，需要将当前对象和其他Da对象做处理，那也要附加的创建出其他Da对象。

至于为何叫访问器“图”（Accessor Graph）也不难理解，任何数据结构都不是孤立的，必然包含成员变量，成员变量可能不是个简单的原生类型（比如int、double），也许是另一种数据结构对象的引用。这种成员关系递归反复，就形成了一张图的结构。所以各数据结构的访问器也需组织成一个类似的图结构，当“根”访问器set到“根”偏移后，其成员访问器也需递归的set到各成员的偏移上。

3.2.3 运行示例

根据3个步骤，我们将章节2.1的顶点例子转变为如下形式：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public abstract class EdgeListVertexAccessor< I extends WritableComparableAccessor, V extends WritableAccessor, E extends WritableAccessor, M extends WritableAccessor> extends MutableVertexAccessor<I, V, E, M> {     private I vertexId = null;     private V vertexValue = null;     /** by S1: indices of its outgoing edges */     private ListAccessor<I> destEdgeIndexList = new                            ArrayListAccessor<I>();     /** by S1: values of its outgoing edges */     private ListAccessor<E> destEdgeValueList = new                             ArrayListAccessor<E>();     /** by S1: incoming messages from the previous iteration */     private ListAccessor<M> msgList = new ArrayListAccessor<M>();     ......    /** by S2:     * binds the accessor to a binary region *of a vertex     */     public void set(byte[] data, int start, int length){     /* This may in turn call the set method     of its member objects. */ ......     }     /** by S3: replacing the return type*/     public ListAccessor<I> getEdegeIndexes(){     }     ... }

 

在上述代码片段里，我们高亮显示改动过的代码、注释描述了转变步骤。图4中是运行时期的一个堆快照。真实数据被布置在page中，一个访问器图被用来处理所有顶点，每次一个。对每个顶点，set方法会将访问器图绑定到它的字节区域。

4 实验

【译者注】文章后续用各种算法为例尝试了一系列对比实验，这里不再细化翻译了，贴几张实验结果的性能对比图，以供感受，详情请参考原文。

 

【译者总结】

文章的精髓一言以蔽之——别创建对象，用固态byte数组。用byte数组，既减少内存空间占用，又避免海量对象的GC遍历，思路貌似和分布式小文件存储系统也有点类似（把小文件组装成固定chunk，避免海量小文件的元数据浪费和检索开销）。但是说起来容易做起来难，我们用Java就是为了享受设计模式的快感、整齐划一的风格、面向对象的便利，改成byte数组，那和用C有什么分别？即使文中期望用访问器图等各种手段来弥补这种缺憾，也难以挽回放弃面向对象而损失的优越感。 

 

然而这个世界有一个二八原则，即影响你系统80%性能的往往是那20%的代码，甚至更少。译者认为，鱼和熊掌不可兼得，只能求其中者。我们在大架构、领域模型、ER设计上依然贯彻面向对象原则，但是可以像文中强调的那样，针对数据穿梭的那条急流，做出妥协。

 

原文链接： asterix.ics.uci.edu 翻译： ImportNew.com - 储晓颖
译文链接： http://www.importnew.com/5061.html