Facebook的数据仓库是如何扩展到300PB的

Facebook在数据仓库上遇到的存储可扩展性的挑战是独一无二的。我们基于Hive的数据仓库中存储了超过300PB的数据，并且以每日新增600TB的速度增长。去年这个数据仓库所存储的数据量增长了3倍。考虑到这个增长趋势，存储效率问题是我们数据仓库基础设施方面目前乃至将来一段时间内最需要关注的。

在提高数据仓库的存储效率方面我们有许多创新点，例如建立冷数据存储的数据中心、对HDFS采用类似RAID的技术在保证数据高可用性不变的前提下降低冗余率、在数据被写入到HDFS之前先做压缩以减少数据占用的存储空间。在Facebook对于大量原始日志的转换（transformations）操作最广泛使用的系统是Hive，Facebook的Hive是建立在 Corona Map-Reduce框架之上的用于处理数据、建立数据仓库表等工作的查询引擎。在这篇文章中，我们主要讨论Hive表的存储格式的演化，这个工作主要的目的是使Hive表的存储格式要尽可能高效压缩原始数据。

RCFile

我们的数据仓库中数据被加载到表里面时首先使用的存储格式是Facebook自己开发的 Record-Columnar File Format(RCFile)。RCFile是一种“允许按行查询，提供了列存储的压缩效率”的混合列存储格式。它的核心思想是首先把Hive表水平切分成多个行组（row groups），然后组内按照列垂直切分，这样列与列的数据在磁盘上就是连续的存储块了。

当一个行组内的所有列写到磁盘时，RCFile就会以列为单位对数据使用类似zlib/lzo的算法进行压缩。当读取列数据的时候使用惰性解压策略（ lazy decompression），也就是说用户的某个查询如果只是涉及到一个表中的部分列的时候，RCFile会跳过不需要的列的解压缩和反序列化的过程。通过在我们的数据仓库中选取有代表性的例子实验，RCFile能够提供5倍的压缩比。

超越RCFile，下一步采用什么样的方法？

随着数据仓库中存储的数据量持续增长，组内的工程师开始研究提高压缩效率的技术和方法。研究的焦点集中在列级别的编码方法，例如行程长度编码（run-length encoding）、词典编码（dictionary encoding）、参考帧编码（frame of reference encoding）、能够在通用压缩过程之前更好的在列级别降低逻辑冗余的数值编码方法。我们也尝试过新的列类型（例如JSON是在Facebook内部广泛使用的格式，把JSON格式的数据按照结构化的方式存储既可以满足高效查询的需求，同时也降低了JSON元数据存储的冗余）。我们的实验表明列级别的编码如果使用得当的话能够显著提高RCFile的压缩比。

与此同时，Hortonworks也在尝试类似的思路去改进Hive的存储格式。Hortonworks的工程团队设计和实现了ORCFile（包括存储格式和读写接口），这帮助我们为Facebook的数据仓库设计和实现新的存储格式提供了一个很好的开始。

ORCFile详解

Hive的数据以ORCFile的格式写到磁盘时，数据被分成一系列的256MB的条带（stripe），一个条带类似于在RCFile中的一个行组。在每一个条带内，ORCFile首先对每个列的数据进行编码，然后把整个条带内的所有列使用类似zlib压缩算法进行压缩。对于一个字符串格式的列使用词典编码，而且是对一个条带内的所有的行数据放到一起进行列编码。在每个条带内会对每10,000行数据存储一个索引，并记录每一列中的最大值和最小值。这些在过滤式的查询时能够跳过一些不在范围内的行。

除了压缩改进，新的存储格式的一个显著优点就是列和行会以偏移（offset）的形式被记录，这样就不需要用分隔符去标记行尾。然而在RCFile中是通过预留某些ASCII值作为分隔符，那么这些分隔符就不允许出现在数据流中。同时查询引擎能够利用条带和每一列在文件级别的元数据去优化查询效率。

自适应的列编码

当我们开始在数据仓库中测试ORCFile的时候，我们发现有些Hive表压缩表现良好，有的反而会引起数据膨胀，导致我们数据仓库中一个有代表性的表集合上的测试中压缩效率提升非常不明显。因为如果某一列数据的熵很大的时候，词典编码会引起数据膨胀，所以如果默认对所有的字符串类型的列都进行词典编码是不合适的。对于某一列是否需要词典编码我们考虑两种方法：通过用户指定的列元数据静态指定；在运行时通过考察列值的情况动态选择编码方法。我们选择后者是因为它能够很好的兼容我们数据仓库已有的数量众多的表。

我们进行了很多测试目的是找到最大化压缩比同时又不影响ORCFile写性能的方法。由于字符串类型在我们最大的那些表中占据主导，同时数据仓库中大约80%的列是由字符串类型组成的，所以优化字符串类型的压缩比最重要。对于每个条带内每一列的不同数值的数目设置一个阈值，同时我们修改了ORCFile的写接口，对于每个条带内的数据如果使用词典编码能够带来压缩效率提升我们就对数据进行词典编码。同时我们对列值进行采样，考察组成列值的字符集合。因为如果这个字符集合比较小的话像zlib这样的通用压缩算法可以有比较好的压缩比，这种情况下词典编码就不是很必要了，有的时候甚至会起副作用。

对于很大的整形数据，我们可以考虑使用行程长度编码或者词典编码。大多数情况下行程长度编码只比通用压缩算法稍微好一点，然而当列数据是由少数几个不同数值组成的时候词典编码会表现比较出色。基于这个结果，对于很大的整形数据我们也是采用词典编码而不是行程长度编码。对于字符串类型和数值类型的数据采用这个思路编码能够给ORCFile带来很高的压缩效率。

我们也实验了很多其他的提高压缩比的方法。其中值得一提的思路就是自适应行程长度编码，也就是一种启发式的策略，只有当使用行程长度编码能够提高压缩比的时候才会使用。在ORCFile的开源版本中这个策略应用到为整形数据在多种方法中自适应地选择编码算法的过程中。这个方法虽然提高了压缩比，但是写性能下降了。我们也研究了条带大小对压缩比的影响。出乎我们的意料，增加条带的大小并不能显著提高压缩比。因为随着条带大小的增加，词典元素的数量会增加，这会导致编码后的列值所占用的字节数量增大。所以想要存储较少的词典带来的优势不符合预期，以256MB作为一个条带大小的这个经验值还是挺靠谱的。

写性能

考虑到在我们的规模下数据的写入速度会影响查询性能，我们对开源的ORCFile的写入接口进行了很多改进用于提高写入性能。其中关键的一点是消除冗余或者不必要的操作，同时要优化内存使用情况。

我们对ORCFile写接口的改进中最关键的就是创建有序词典的过程。在开源ORCFile的版本中为了保证词典的有序，写接口是用红黑树（red-black tree）来存储的词典。然后在自适应的词典编码中，即使某一列不适合使用词典编码存储，它也要花费O(log(n))的时间复杂度向红黑树插入一个新的key。如果使用一个存储高效的哈希映射来存放词典，只有在需要的时候排序，词典的内存占用量降低了30%，而且更重要的是写性能提高了1.4倍。为了更快、更高效利用内存地调整词典大小，初始词典是由一个字节数组为元素的数组存储的。然而这会使得访问词典元素这个操作非常频繁，我们选择使用Airlift库的Slice类用来代替词典实现高效内存拷贝，能把写性能再提高20%-30%。

按列打开词典编码很耗费计算资源。因为每一列的字符在不同的条带里会有重复，我们已经发现对于所有条带统一进行词典编码没有优势。所以我们改进写接口，基于条带的子集合判断列编码算法，同时接下来的条带中对应的列会重复上面条带的算法。也就是说如果写接口判断对于这一列的值使用词典编码没有优势，那么在接下来的条带中会智能地不使用词典编码。由于Facebook自有的ORCFile格式带来的压缩效率的提升，我们可以降低已经使用的zlib的压缩级别，同时写性能得到20%的提升。

读性能

谈到读性能，大家很快就会想到的问题就是惰性列解压缩（laze column decompression）。例如一个要读取很多列但是只在某一列有过滤条件的查询。如果没有我们实现的惰性解压缩，所有列都会被读取并解压缩。理想情况是只有设置有过滤条件的列被解压缩和解码，这样这个查询才不会浪费大量的时间在解压缩和解码那些无关数据上。

为了这个目的，我们利用ORCFile存储格式中的索引跨步（index strides）给Facebook的ORCFile的读接口实现了惰性解压缩和惰性解码功能。在前面讲的例子中，对于有过滤条件的那一列涉及到的所有数据将要被解压缩和解码。对于其他列的数据，我们改变读接口去读取条带内相应的索引跨步（对条带的元数据操作），只需要解压缩和解码相应索引跨步前面的行数据。经过我们的测试，这个改进使得在我们Facebook的ORCFile的版本上运行的简单过滤型（select）查询比开源版本性能提高了3倍。因为没有了额外数据的惰性解码，Facebook的ORCFile在这种简单过滤型查询的性能也比RCFile高。

总结

通过应用这些改进，在数据仓库数据中我们使用ORCFile相比RCFile在压缩比上带来了5到8倍的提升。从数据仓库中选择了一系列典型的查询和数据的测试中，我们发现Facebook的ORCFile的写性能会比开源版本高3倍。

我们已经把这种新的存储格式应用到许多数十PB级别的表数据中，通过把数据从RCFile改成ORCFile存储格式，已经再生出数十PB级别的存储容量。我们正在把这种新的存储格式向数据仓库中的其他表推广，这个改进可以达到存储效率和读写性能的双重提升。我们Facebook内部的ORCFile的代码是开源的，同时我们也在与开源社区密切配合把这些改进并入Apache Hive的代码中。

下一步？

在进一步改进ORCFile的压缩比和读写效率方面我们有很多想法。包括支持新的压缩编码例如LZ4HC、不同的列当编码不同时使用不同的压缩算法和压缩等级、存储更多的统计信息并暴露给查询引擎使用、把开源社区像谓词下压（predicate pushdown）等工作引入Facebook内部。另外还有一些其他的改进思路，例如降低源表和派生表的逻辑冗余、对于冷数据集的采样、增加目前暂时以字符串格式存储的却有通用需求的Hive原生数据类型。

Facebook分析基础设施组的许多同事参与了ORCFile相关的工作，包括了本文的作者 Pamela Vagata，Kevin Wilfong and Sambavi Muthukrishnan。同时感谢Hortonworks的同事对我们的工作的配合和帮助。