揭秘:RCFile高效存儲(chǔ)結(jié)構(gòu)
掃描二維碼
隨時(shí)隨地手機(jī)看文章
本文介紹了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 on Data Engineering)會(huì)議上介紹了數(shù)據(jù)倉庫Hive。Hive存儲(chǔ)海量數(shù)據(jù)在Hadoop系統(tǒng)中,提供了一套類數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)和處理機(jī)制。它采用類SQL語言對(duì)數(shù)據(jù)進(jìn)行自動(dòng)化管理和處理,經(jīng)過語句解析和轉(zhuǎn)換,最終生成基于Hadoop的MapReduce任務(wù),通過執(zhí)行這些任務(wù)完成數(shù)據(jù)處理。圖1顯示了Hive數(shù)據(jù)倉庫的系統(tǒng)結(jié)構(gòu)。
圖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ǔ)的例子[!--empirenews.page--]列存儲(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ǔ)的例子[!--empirenews.page--]
數(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)勢。例如,表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í)避免不必要的列讀取,測試顯示在多數(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ù)分析中扮演重要角色。