本文介紹了Facebook公司數(shù)據(jù)分析系統(tǒng)中的RCFile存儲(chǔ)結(jié)構(gòu)，該結(jié)構(gòu)集行存儲(chǔ)和列存儲(chǔ)的優(yōu)點(diǎn)于一身，在MapReduce環(huán)境下的大規(guī)模數(shù)據(jù)分析中扮演重要角色。

Facebook曾在2010 ICDE（IEEE International Conference>

圖1 Hive數(shù)據(jù)倉庫的系統(tǒng)結(jié)構(gòu)

基于MapReduce的數(shù)據(jù)倉庫在超大規(guī)模數(shù)據(jù)分析中扮演了重要角色，對(duì)于典型的Web服務(wù)供應(yīng)商，這些分析有助于它們快速理解動(dòng)態(tài)的用戶行為及變化的用戶需求。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是影響數(shù)據(jù)倉庫性能的關(guān)鍵因素之一。Hadoop系統(tǒng)中常用的文件存儲(chǔ)格式有支持文本的TextFile和支持二進(jìn)制的SequenceFile等，它們都屬于行存儲(chǔ)方式。Facebook工程師發(fā)表的RCFile: A Fast and Spaceefficient Data Placement Structure in MapReducebased Warehouse Systems一文，介紹了一種高效的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)——RCFile（Record Columnar File），并將其應(yīng)用于Facebook的數(shù)據(jù)倉庫Hive中。與傳統(tǒng)數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)相比，RCFile更有效地滿足了基于MapReduce的數(shù)據(jù)倉庫的四個(gè)關(guān)鍵需求，即Fast data loading、Fast query processing、Highly efficient storage space utilization和Strong adaptivity to highly dynamic workload patterns。

數(shù)據(jù)倉庫的需求

基于Facebook系統(tǒng)特征和用戶數(shù)據(jù)的分析，在MapReduce計(jì)算環(huán)境下，數(shù)據(jù)倉庫對(duì)于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有四個(gè)關(guān)鍵需求。

Fast data loading

對(duì)于Facebook的產(chǎn)品數(shù)據(jù)倉庫而言，快速加載數(shù)據(jù)（寫數(shù)據(jù)）是非常關(guān)鍵的。每天大約有超過20TB的數(shù)據(jù)上傳到Facebook的數(shù)據(jù)倉庫，由于數(shù)據(jù)加載期間網(wǎng)絡(luò)和磁盤流量會(huì)干擾正常的查詢執(zhí)行，因此縮短數(shù)據(jù)加載時(shí)間是非常必要的。

Fast query processing

為了滿足實(shí)時(shí)性的網(wǎng)站請(qǐng)求和支持高并發(fā)用戶提交查詢的大量讀負(fù)載，查詢響應(yīng)時(shí)間是非常關(guān)鍵的，這要求底層存儲(chǔ)結(jié)構(gòu)能夠隨著查詢數(shù)量的增加而保持高速的查詢處理。

Highly efficient storage space utilization

高速增長的用戶活動(dòng)總是需要可擴(kuò)展的存儲(chǔ)容量和計(jì)算能力，有限的磁盤空間需要合理管理海量數(shù)據(jù)的存儲(chǔ)。實(shí)際上，該問題的解決方案就是最大化磁盤空間利用率。

Strong adaptivity to highly dynamic workload patterns

同一份數(shù)據(jù)集會(huì)供給不同應(yīng)用的用戶，通過各種方式來分析。某些數(shù)據(jù)分析是例行過程，按照某種固定模式周期性執(zhí)行；而另一些則是從中間平臺(tái)發(fā)起的查詢。大多數(shù)負(fù)載不遵循任何規(guī)則模式，這需要底層系統(tǒng)在存儲(chǔ)空間有限的前提下，對(duì)數(shù)據(jù)處理中不可預(yù)知的動(dòng)態(tài)數(shù)據(jù)具備高度的適應(yīng)性，而不是專注于某種特殊的負(fù)載模式。

MapReduce存儲(chǔ)策略

要想設(shè)計(jì)并實(shí)現(xiàn)一種基于MapReduce數(shù)據(jù)倉庫的高效數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，關(guān)鍵挑戰(zhàn)是在MapReduce計(jì)算環(huán)境中滿足上述四個(gè)需求。在傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中，三種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)被廣泛研究，分別是行存儲(chǔ)結(jié)構(gòu)、列存儲(chǔ)結(jié)構(gòu)和PAX混合存儲(chǔ)結(jié)構(gòu)。上面這三種結(jié)構(gòu)都有其自身特點(diǎn)，不過簡單移植這些數(shù)據(jù)庫導(dǎo)向的存儲(chǔ)結(jié)構(gòu)到基于MapReduce的數(shù)據(jù)倉庫系統(tǒng)并不能很好地滿足所有需求。

行存儲(chǔ)

如圖2所示，基于Hadoop系統(tǒng)行存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)在于快速數(shù)據(jù)加載和動(dòng)態(tài)負(fù)載的高適應(yīng)能力，這是因?yàn)樾写鎯?chǔ)保證了相同記錄的所有域都在同一個(gè)集群節(jié)點(diǎn)，即同一個(gè)HDFS塊。不過，行存儲(chǔ)的缺點(diǎn)也是顯而易見的，例如它不能支持快速查詢處理，因?yàn)楫?dāng)查詢僅僅針對(duì)多列表中的少數(shù)幾列時(shí)，它不能跳過不必要的列讀??；此外，由于混合著不同數(shù)據(jù)值的列，行存儲(chǔ)不易獲得一個(gè)極高的壓縮比，即空間利用率不易大幅提高。盡管通過熵編碼和利用列相關(guān)性能夠獲得一個(gè)較好的壓縮比，但是復(fù)雜數(shù)據(jù)存儲(chǔ)實(shí)現(xiàn)會(huì)導(dǎo)致解壓開銷增大。 

圖2 HDFS塊內(nèi)行存儲(chǔ)的例子

列存儲(chǔ)

圖3顯示了在HDFS上按照列組存儲(chǔ)表格的例子。在這個(gè)例子中，列A和列B存儲(chǔ)在同一列組，而列C和列D分別存儲(chǔ)在單獨(dú)的列組。查詢時(shí)列存儲(chǔ)能夠避免讀不必要的列，并且壓縮一個(gè)列中的相似數(shù)據(jù)能夠達(dá)到較高的壓縮比。然而，由于元組重構(gòu)的較高開銷，它并不能提供基于Hadoop系統(tǒng)的快速查詢處理。列存儲(chǔ)不能保證同一記錄的所有域都存儲(chǔ)在同一集群節(jié)點(diǎn)，例如圖2的例子中，記錄的4個(gè)域存儲(chǔ)在位于不同節(jié)點(diǎn)的3個(gè)HDFS塊中。因此，記錄的重構(gòu)將導(dǎo)致通過集群節(jié)點(diǎn)網(wǎng)絡(luò)的大量數(shù)據(jù)傳輸。盡管預(yù)先分組后，多個(gè)列在一起能夠減少開銷，但是對(duì)于高度動(dòng)態(tài)的負(fù)載模式，它并不具備很好的適應(yīng)性。除非所有列組根據(jù)可能的查詢預(yù)先創(chuàng)建，否則對(duì)于一個(gè)查詢需要一個(gè)不可預(yù)知的列組合，一個(gè)記錄的重構(gòu)或許需要2個(gè)或多個(gè)列組。再者由于多個(gè)組之間的列交疊，列組可能會(huì)創(chuàng)建多余的列數(shù)據(jù)存儲(chǔ)，這導(dǎo)致存儲(chǔ)利用率的降低。 

圖3 HDFS塊內(nèi)列存儲(chǔ)的例子

PAX混合存儲(chǔ)

PAX存儲(chǔ)模型（用于Data Morphing存儲(chǔ)技術(shù)）使用混合存儲(chǔ)方式，目的在于提升CPU Cache性能。對(duì)于記錄中來自不同列的多個(gè)域，PAX將它們放在一個(gè)磁盤頁中。在每個(gè)磁盤頁中，PAX使用一個(gè)迷你頁來存儲(chǔ)屬于每個(gè)列的所有域，并使用一個(gè)頁頭來存儲(chǔ)迷你頁的指針。類似于行存儲(chǔ)，PAX對(duì)多種動(dòng)態(tài)查詢有很強(qiáng)的適應(yīng)能力。然而，它并不能滿足大型分布式系統(tǒng)對(duì)于高存儲(chǔ)空間利用率和快速查詢處理的需求，原因在于：首先，PAX沒有數(shù)據(jù)壓縮的相關(guān)工作，這部分與Cache優(yōu)化關(guān)系不大，但對(duì)于大規(guī)模數(shù)據(jù)處理系統(tǒng)是非常關(guān)鍵的，它提供了列維度數(shù)據(jù)壓縮的可能性；其次，PAX不能提升I/O性能，因?yàn)樗荒芨淖儗?shí)際的頁內(nèi)容，該限制使得大規(guī)模數(shù)據(jù)掃描時(shí)不易實(shí)現(xiàn)快速查詢處理；再次，PAX用固定的頁作為數(shù)據(jù)組織的基本單位，按照這個(gè)大小，在海量數(shù)據(jù)處理系統(tǒng)中，PAX將不會(huì)有效存儲(chǔ)不同大小類型的數(shù)據(jù)域。本文介紹的是RCF i l e 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)在Hadoop系統(tǒng)上的實(shí)現(xiàn)。該結(jié)構(gòu)強(qiáng)調(diào)：第一，RCFile存儲(chǔ)的表是水平劃分的，分為多個(gè)行組， 每個(gè)行組再被垂直劃分， 以便每列單獨(dú)存儲(chǔ)；第二，RCFile在每個(gè)行組中利用一個(gè)列維度的數(shù)據(jù)壓縮，并提供一種Lazy解壓（decompression）技術(shù)來在查詢執(zhí)行時(shí)避免不必要的列解壓；第三，RCFile支持彈性的行組大小，行組大小需要權(quán)衡數(shù)據(jù)壓縮性能和查詢性能兩方面。

RCFile的設(shè)計(jì)與實(shí)現(xiàn)

RCFile（Record Columnar File）存儲(chǔ)結(jié)構(gòu)遵循的是“先水平劃分，再垂直劃分”的設(shè)計(jì)理念，這個(gè)想法來源于PAX。它結(jié)合了行存儲(chǔ)和列存儲(chǔ)的優(yōu)點(diǎn)：首先，RCFile保證同一行的數(shù)據(jù)位于同一節(jié)點(diǎn)，因此元組重構(gòu)的開銷很低；其次，像列存儲(chǔ)一樣，RCFile能夠利用列維度的數(shù)據(jù)壓縮，并且能跳過不必要的列讀取。圖4是一個(gè)HDFS塊內(nèi)RCFile方式存儲(chǔ)的例子。 

圖4 HDFS塊內(nèi)RCFile方式存儲(chǔ)的例子

數(shù)據(jù)格式

RCFile在HDFS分布式文件系統(tǒng)之上設(shè)計(jì)并實(shí)現(xiàn)，如圖4所示，RCFile按照下面的數(shù)據(jù)格式來存儲(chǔ)一張表。

RCFile基于HDFS架構(gòu)，表格占用多個(gè)HDFS塊。

每個(gè)HDFS塊中，RCFile以行組為基本單位來組織記錄。也就是說，存儲(chǔ)在一個(gè)HDFS塊中的所有記錄被劃分為多個(gè)行組。對(duì)于一張表，所有行組大小都相同。一個(gè)HDFS塊會(huì)有一個(gè)或多個(gè)行組。

一個(gè)行組包括三個(gè)部分。第一部分是行組頭部的同步標(biāo)識(shí)，主要用于分隔HDFS塊中的兩個(gè)連續(xù)行組；第二部分是行組的元數(shù)據(jù)頭部，用于存儲(chǔ)行組單元的信息，包括行組中的記錄數(shù)、每個(gè)列的字節(jié)數(shù)、列中每個(gè)域的字節(jié)數(shù)；第三部分是表格數(shù)據(jù)段，即實(shí)際的列存儲(chǔ)數(shù)據(jù)。在該部分中，同一列的所有域順序存儲(chǔ)。從圖4可以看出，首先存儲(chǔ)了列A的所有域，然后存儲(chǔ)列B的所有域等。

壓縮方式

RCFile的每個(gè)行組中，元數(shù)據(jù)頭部和表格數(shù)據(jù)段分別進(jìn)行壓縮。

對(duì)于所有元數(shù)據(jù)頭部，RCFile使用RLE（Run Length Encoding）算法來壓縮數(shù)據(jù)。由于同一列中所有域的長度值都順序存儲(chǔ)在該部分，RLE算法能夠找到重復(fù)值的長序列，尤其對(duì)于固定的域長度。

表格數(shù)據(jù)段不會(huì)作為整個(gè)單元來壓縮；相反每個(gè)列被獨(dú)立壓縮，使用Gzip壓縮算法。RCFile使用重量級(jí)的Gzip壓縮算法，是為了獲得較好的壓縮比，而不使用RLE算法的原因在于此時(shí)列數(shù)據(jù)非排序。此外，由于Lazy壓縮策略，當(dāng)處理一個(gè)行組時(shí)，RCFile不需要解壓所有列。因此，相對(duì)較高的Gzip解壓開銷可以減少。

盡管RCFile對(duì)表格數(shù)據(jù)的所有列使用同樣的壓縮算法，不過如果使用不同的算法來壓縮不同列或許效果會(huì)更好。RCFile將來的工作之一可能就是根據(jù)每列的數(shù)據(jù)類型和數(shù)據(jù)分布來自適應(yīng)選擇最好的壓縮算法。

數(shù)據(jù)追加

RCFile不支持任意方式的數(shù)據(jù)寫操作，僅提供一種追加接口，這是因?yàn)榈讓拥腍DFS當(dāng)前僅僅支持?jǐn)?shù)據(jù)追加寫文件尾部。數(shù)據(jù)追加方法描述如下。

RCFile為每列創(chuàng)建并維護(hù)一個(gè)內(nèi)存column holder，當(dāng)記錄追加時(shí)，所有域被分發(fā)，每個(gè)域追加到其對(duì)應(yīng)的column holder。此外，RCFile在元數(shù)據(jù)頭部中記錄每個(gè)域?qū)?yīng)的元數(shù)據(jù)。

RCFile提供兩個(gè)參數(shù)來控制在刷寫到磁盤之前，內(nèi)存中緩存多少個(gè)記錄。一個(gè)參數(shù)是記錄數(shù)的限制，另一個(gè)是內(nèi)存緩存的大小限制。

RCFile首先壓縮元數(shù)據(jù)頭部并寫到磁盤，然后分別壓縮每個(gè)column holder，并將壓縮后的column holder刷寫到底層文件系統(tǒng)中的一個(gè)行組中。

數(shù)據(jù)讀取和Lazy解壓

在MapReduce框架中，mapper將順序處理HDFS塊中的每個(gè)行組。當(dāng)處理一個(gè)行組時(shí)，RCFile無需全部讀取行組的全部內(nèi)容到內(nèi)存。

相反，它僅僅讀元數(shù)據(jù)頭部和給定查詢需要的列。因此，它可以跳過不必要的列以獲得列存儲(chǔ)的I/O優(yōu)勢(shì)。例如，表tbl(c1, c2, c3, c4)有4個(gè)列，做一次查詢“SELECT c1 FROM tbl WHERE c4 = 1”，對(duì)每個(gè)行組，RCFile僅僅讀取c1和c4列的內(nèi)容。在元數(shù)據(jù)頭部和需要的列數(shù)據(jù)加載到內(nèi)存中后，它們需要解壓。元數(shù)據(jù)頭部總會(huì)解壓并在內(nèi)存中維護(hù)直到RCFile處理下一個(gè)行組。然而，RCFile不會(huì)解壓所有加載的列，相反，它使用一種Lazy解壓技術(shù)。

Lazy解壓意味著列將不會(huì)在內(nèi)存解壓，直到RCFile決定列中數(shù)據(jù)真正對(duì)查詢執(zhí)行有用。由于查詢使用各種WHERE條件，Lazy解壓非常有用。如果一個(gè)WHERE條件不能被行組中的所有記錄滿足，那么RCFile將不會(huì)解壓WHERE條件中不滿足的列。例如，在上述查詢中，所有行組中的列c4都解壓了。然而，對(duì)于一個(gè)行組，如果列c4中沒有值為1的域，那么就無需解壓列c1。

行組大小

I/O性能是RCFile關(guān)注的重點(diǎn)，因此RCFile需要行組夠大并且大小可變。行組大小和下面幾個(gè)因素相關(guān)。

行組大的話，數(shù)據(jù)壓縮效率會(huì)比行組小時(shí)更有效。根據(jù)對(duì)Facebook日常應(yīng)用的觀察，當(dāng)行組大小達(dá)到一個(gè)閾值后，增加行組大小并不能進(jìn)一步增加Gzip算法下的壓縮比。

行組變大能夠提升數(shù)據(jù)壓縮效率并減少存儲(chǔ)量。因此，如果對(duì)縮減存儲(chǔ)空間方面有強(qiáng)烈需求，則不建議選擇使用小行組。需要注意的是，當(dāng)行組的大小超過4MB，數(shù)據(jù)的壓縮比將趨于一致。

盡管行組變大有助于減少表格的存儲(chǔ)規(guī)模，但是可能會(huì)損害數(shù)據(jù)的讀性能，因?yàn)檫@樣減少了Lazy解壓帶來的性能提升。而且行組變大會(huì)占用更多的內(nèi)存，這會(huì)影響并發(fā)執(zhí)行的其他MapReduce作業(yè)?？紤]到存儲(chǔ)空間和查詢效率兩個(gè)方面，F(xiàn)acebook選擇4MB作為默認(rèn)的行組大小，當(dāng)然也允許用戶自行選擇參數(shù)進(jìn)行配置。

小結(jié)

本文簡單介紹了RCFile存儲(chǔ)結(jié)構(gòu)，其廣泛應(yīng)用于Facebook公司的數(shù)據(jù)分析系統(tǒng)Hive中。首先，RCFile具備相當(dāng)于行存儲(chǔ)的數(shù)據(jù)加載速度和負(fù)載適應(yīng)能力；其次，RCFile的讀優(yōu)化可以在掃描表格時(shí)避免不必要的列讀取，測(cè)試顯示在多數(shù)情況下，它比其他結(jié)構(gòu)擁有更好的性能；再次，RCFile使用列維度的壓縮，因此能夠有效提升存儲(chǔ)空間利用率。

為了提高存儲(chǔ)空間利用率，F(xiàn)acebook各產(chǎn)品線應(yīng)用產(chǎn)生的數(shù)據(jù)從2010年起均采用RCFile結(jié)構(gòu)存儲(chǔ)，按行存儲(chǔ)（SequenceFile/TextFile）結(jié)構(gòu)保存的數(shù)據(jù)集也轉(zhuǎn)存為RCFile格式。此外，Yahoo公司也在Pig數(shù)據(jù)分析系統(tǒng)中集成了RCFile，RCFile正在用于另一個(gè)基于Hadoop的數(shù)據(jù)管理系統(tǒng)Howl（http://wiki.apache.org/pig/Howl）。而且，根據(jù)Hive開發(fā)社區(qū)的交流，RCFile也成功整合加入其他基于MapReduce的數(shù)據(jù)分析平臺(tái)。有理由相信，作為數(shù)據(jù)存儲(chǔ)標(biāo)準(zhǔn)的RCFile，將繼續(xù)在MapReduce環(huán)境下的大規(guī)模數(shù)據(jù)分析中扮演重要角色。