|
本文介紹了Facebook公司數據分析系統中的RCFile存儲結構，該結構集行存儲和列存儲的優(yōu)點(diǎn)于一身，在MapReduce環(huán)境下的大規模數據分析中扮演重要角色。 Facebook曾在2010 ICDE（IEEE International Conference on Data Engineering）會(huì )議上介紹了數據倉庫Hive。Hive存儲海量數據在Hadoop系統中，提供了一套類(lèi)數據庫的數據存儲和處理機制。它采用類(lèi)SQL語(yǔ)言對數據進(jìn)行自動(dòng)化管理和處理，經(jīng)過(guò)語(yǔ)句解析和轉換，最終生成基于Hadoop的MapReduce任務(wù)，通過(guò)執行這些任務(wù)完成數據處理。圖1顯示了Hive數據倉庫的系統結構。 
圖1 Hive數據倉庫的系統結構 基于MapReduce的數據倉庫在超大規模數據分析中扮演了重要角色，對于典型的Web服務(wù)供應商，這些分析有助于它們快速理解動(dòng)態(tài)的用戶(hù)行為及變化的用戶(hù)需求。數據存儲結構是影響數據倉庫性能的關(guān)鍵因素之一。Hadoop系統中常用的文件存儲格式有支持文本的TextFile和支持二進(jìn)制的SequenceFile等，它們都屬于行存儲方式。Facebook工程師發(fā)表的RCFile: A Fast and Spaceefficient Data Placement Structure in MapReducebased Warehouse Systems一文，介紹了一種高效的數據存儲結構——RCFile（Record Columnar File），并將其應用于Facebook的數據倉庫Hive中。與傳統數據庫的數據存儲結構相比，RCFile更有效地滿(mǎn)足了基于MapReduce的數據倉庫的四個(gè)關(guān)鍵需求，即Fast data loading、Fast query processing、Highly efficient storage space utilization和Strong adaptivity to highly dynamic workload patterns。 數據倉庫的需求 基于Facebook系統特征和用戶(hù)數據的分析，在MapReduce計算環(huán)境下，數據倉庫對于數據存儲結構有四個(gè)關(guān)鍵需求。 Fast data loading 對于Facebook的產(chǎn)品數據倉庫而言，快速加載數據（寫(xiě)數據）是非常關(guān)鍵的。每天大約有超過(guò)20TB的數據上傳到Facebook的數據倉庫，由于數據加載期間網(wǎng)絡(luò )和磁盤(pán)流量會(huì )干擾正常的查詢(xún)執行，因此縮短數據加載時(shí)間是非常必要的。 Fast query processing 為了滿(mǎn)足實(shí)時(shí)性的網(wǎng)站請求和支持高并發(fā)用戶(hù)提交查詢(xún)的大量讀負載，查詢(xún)響應時(shí)間是非常關(guān)鍵的，這要求底層存儲結構能夠隨著(zhù)查詢(xún)數量的增加而保持高速的查詢(xún)處理。 Highly efficient storage space utilization 高速增長(cháng)的用戶(hù)活動(dòng)總是需要可擴展的存儲容量和計算能力，有限的磁盤(pán)空間需要合理管理海量數據的存儲。實(shí)際上，該問(wèn)題的解決方案就是最大化磁盤(pán)空間利用率。 Strong adaptivity to highly dynamic workload patterns 同一份數據集會(huì )供給不同應用的用戶(hù)，通過(guò)各種方式來(lái)分析。某些數據分析是例行過(guò)程，按照某種固定模式周期性執行；而另一些則是從中間平臺發(fā)起的查詢(xún)。大多數負載不遵循任何規則模式，這需要底層系統在存儲空間有限的前提下，對數據處理中不可預知的動(dòng)態(tài)數據具備高度的適應性，而不是專(zhuān)注于某種特殊的負載模式。 MapReduce存儲策略 要想設計并實(shí)現一種基于MapReduce數據倉庫的高效數據存儲結構，關(guān)鍵挑戰是在MapReduce計算環(huán)境中滿(mǎn)足上述四個(gè)需求。在傳統數據庫系統中，三種數據存儲結構被廣泛研究，分別是行存儲結構、列存儲結構和PAX混合存儲結構。上面這三種結構都有其自身特點(diǎn)，不過(guò)簡(jiǎn)單移植這些數據庫導向的存儲結構到基于MapReduce的數據倉庫系統并不能很好地滿(mǎn)足所有需求。 行存儲 如圖2所示，基于Hadoop系統行存儲結構的優(yōu)點(diǎn)在于快速數據加載和動(dòng)態(tài)負載的高適應能力，這是因為行存儲保證了相同記錄的所有域都在同一個(gè)集群節點(diǎn)，即同一個(gè)HDFS塊。不過(guò)，行存儲的缺點(diǎn)也是顯而易見(jiàn)的，例如它不能支持快速查詢(xún)處理，因為當查詢(xún)僅僅針對多列表中的少數幾列時(shí)，它不能跳過(guò)不必要的列讀��；此外，由于混合著(zhù)不同數據值的列，行存儲不易獲得一個(gè)極高的壓縮比，即空間利用率不易大幅提高。盡管通過(guò)熵編碼和利用列相關(guān)性能夠獲得一個(gè)較好的壓縮比，但是復雜數據存儲實(shí)現會(huì )導致解壓開(kāi)銷(xiāo)增大。
圖2 HDFS塊內行存儲的例子 列存儲 圖3顯示了在HDFS上按照列組存儲表格的例子。在這個(gè)例子中，列A和列B存儲在同一列組，而列C和列D分別存儲在單獨的列組。查詢(xún)時(shí)列存儲能夠避免讀不必要的列，并且壓縮一個(gè)列中的相似數據能夠達到較高的壓縮比。然而，由于元組重構的較高開(kāi)銷(xiāo)，它并不能提供基于Hadoop系統的快速查詢(xún)處理。列存儲不能保證同一記錄的所有域都存儲在同一集群節點(diǎn)，例如圖2的例子中，記錄的4個(gè)域存儲在位于不同節點(diǎn)的3個(gè)HDFS塊中。因此，記錄的重構將導致通過(guò)集群節點(diǎn)網(wǎng)絡(luò )的大量數據傳輸。盡管預先分組后，多個(gè)列在一起能夠減少開(kāi)銷(xiāo)，但是對于高度動(dòng)態(tài)的負載模式，它并不具備很好的適應性。除非所有列組根據可能的查詢(xún)預先創(chuàng )建，否則對于一個(gè)查詢(xún)需要一個(gè)不可預知的列組合，一個(gè)記錄的重構或許需要2個(gè)或多個(gè)列組。再者由于多個(gè)組之間的列交疊，列組可能會(huì )創(chuàng )建多余的列數據存儲，這導致存儲利用率的降低。
圖3 HDFS塊內列存儲的例子 PAX混合存儲 PAX存儲模型（用于Data Morphing存儲技術(shù)）使用混合存儲方式，目的在于提升CPU Cache性能。對于記錄中來(lái)自不同列的多個(gè)域，PAX將它們放在一個(gè)磁盤(pán)頁(yè)中。在每個(gè)磁盤(pán)頁(yè)中，PAX使用一個(gè)迷你頁(yè)來(lái)存儲屬于每個(gè)列的所有域，并使用一個(gè)頁(yè)頭來(lái)存儲迷你頁(yè)的指針。類(lèi)似于行存儲，PAX對多種動(dòng)態(tài)查詢(xún)有很強的適應能力。然而，它并不能滿(mǎn)足大型分布式系統對于高存儲空間利用率和快速查詢(xún)處理的需求，原因在于：首先，PAX沒(méi)有數據壓縮的相關(guān)工作，這部分與Cache優(yōu)化關(guān)系不大，但對于大規模數據處理系統是非常關(guān)鍵的，它提供了列維度數據壓縮的可能性；其次，PAX不能提升I/O性能，因為它不能改變實(shí)際的頁(yè)內容，該限制使得大規模數據掃描時(shí)不易實(shí)現快速查詢(xún)處理；再次，PAX用固定的頁(yè)作為數據組織的基本單位，按照這個(gè)大小，在海量數據處理系統中，PAX將不會(huì )有效存儲不同大小類(lèi)型的數據域。本文介紹的是RCF i l e 數據存儲結構在Hadoop系統上的實(shí)現。該結構強調：第一，RCFile存儲的表是水平劃分的，分為多個(gè)行組， 每個(gè)行組再被垂直劃分， 以便每列單獨存儲；第二，RCFile在每個(gè)行組中利用一個(gè)列維度的數據壓縮，并提供一種Lazy解壓（decompression）技術(shù)來(lái)在查詢(xún)執行時(shí)避免不必要的列解壓；第三，RCFile支持彈性的行組大小，行組大小需要權衡數據壓縮性能和查詢(xún)性能兩方面。 RCFile的設計與實(shí)現 RCFile（Record Columnar File）存儲結構遵循的是“先水平劃分，再垂直劃分”的設計理念，這個(gè)想法來(lái)源于PAX。它結合了行存儲和列存儲的優(yōu)點(diǎn)：首先，RCFile保證同一行的數據位于同一節點(diǎn)，因此元組重構的開(kāi)銷(xiāo)很低；其次，像列存儲一樣，RCFile能夠利用列維度的數據壓縮，并且能跳過(guò)不必要的列讀取。圖4是一個(gè)HDFS塊內RCFile方式存儲的例子。
圖4 HDFS塊內RCFile方式存儲的例子 數據格式 RCFile在HDFS分布式文件系統之上設計并實(shí)現，如圖4所示，RCFile按照下面的數據格式來(lái)存儲一張表。 RCFile基于HDFS架構，表格占用多個(gè)HDFS塊。 每個(gè)HDFS塊中，RCFile以行組為基本單位來(lái)組織記錄。也就是說(shuō)，存儲在一個(gè)HDFS塊中的所有記錄被劃分為多個(gè)行組。對于一張表，所有行組大小都相同。一個(gè)HDFS塊會(huì )有一個(gè)或多個(gè)行組。 一個(gè)行組包括三個(gè)部分。第一部分是行組頭部的同步標識，主要用于分隔HDFS塊中的兩個(gè)連續行組；第二部分是行組的元數據頭部，用于存儲行組單元的信息，包括行組中的記錄數、每個(gè)列的字節數、列中每個(gè)域的字節數；第三部分是表格數據段，即實(shí)際的列存儲數據。在該部分中，同一列的所有域順序存儲。從圖4可以看出，首先存儲了列A的所有域，然后存儲列B的所有域等。 壓縮方式 RCFile的每個(gè)行組中，元數據頭部和表格數據段分別進(jìn)行壓縮。 對于所有元數據頭部，RCFile使用RLE（Run Length Encoding）算法來(lái)壓縮數據。由于同一列中所有域的長(cháng)度值都順序存儲在該部分，RLE算法能夠找到重復值的長(cháng)序列，尤其對于固定的域長(cháng)度。 表格數據段不會(huì )作為整個(gè)單元來(lái)壓縮；相反每個(gè)列被獨立壓縮，使用Gzip壓縮算法。RCFile使用重量級的Gzip壓縮算法，是為了獲得較好的壓縮比，而不使用RLE算法的原因在于此時(shí)列數據非排序。此外，由于Lazy壓縮策略，當處理一個(gè)行組時(shí)，RCFile不需要解壓所有列。因此，相對較高的Gzip解壓開(kāi)銷(xiāo)可以減少。 盡管RCFile對表格數據的所有列使用同樣的壓縮算法，不過(guò)如果使用不同的算法來(lái)壓縮不同列或許效果會(huì )更好。RCFile將來(lái)的工作之一可能就是根據每列的數據類(lèi)型和數據分布來(lái)自適應選擇最好的壓縮算法。 數據追加 RCFile不支持任意方式的數據寫(xiě)操作，僅提供一種追加接口，這是因為底層的HDFS當前僅僅支持數據追加寫(xiě)文件尾部。數據追加方法描述如下。 RCFile為每列創(chuàng )建并維護一個(gè)內存column holder，當記錄追加時(shí)，所有域被分發(fā)，每個(gè)域追加到其對應的column holder。此外，RCFile在元數據頭部中記錄每個(gè)域對應的元數據。 RCFile提供兩個(gè)參數來(lái)控制在刷寫(xiě)到磁盤(pán)之前，內存中緩存多少個(gè)記錄。一個(gè)參數是記錄數的限制，另一個(gè)是內存緩存的大小限制。 RCFile首先壓縮元數據頭部并寫(xiě)到磁盤(pán)，然后分別壓縮每個(gè)column holder，并將壓縮后的column holder刷寫(xiě)到底層文件系統中的一個(gè)行組中。 數據讀取和Lazy解壓 在MapReduce框架中，mapper將順序處理HDFS塊中的每個(gè)行組。當處理一個(gè)行組時(shí)，RCFile無(wú)需全部讀取行組的全部?jì)热莸絻却妗?br /> 相反，它僅僅讀元數據頭部和給定查詢(xún)需要的列。因此，它可以跳過(guò)不必要的列以獲得列存儲的I/O優(yōu)勢。例如，表tbl(c1, c2, c3, c4)有4個(gè)列，做一次查詢(xún)“SELECT c1 FROM tbl WHERE c4 = 1”，對每個(gè)行組，RCFile僅僅讀取c1和c4列的內容。在元數據頭部和需要的列數據加載到內存中后，它們需要解壓。元數據頭部總會(huì )解壓并在內存中維護直到RCFile處理下一個(gè)行組。然而，RCFile不會(huì )解壓所有加載的列，相反，它使用一種Lazy解壓技術(shù)。 Lazy解壓意味著(zhù)列將不會(huì )在內存解壓，直到RCFile決定列中數據真正對查詢(xún)執行有用。由于查詢(xún)使用各種WHERE條件，Lazy解壓非常有用。如果一個(gè)WHERE條件不能被行組中的所有記錄滿(mǎn)足，那么RCFile將不會(huì )解壓WHERE條件中不滿(mǎn)足的列。例如，在上述查詢(xún)中，所有行組中的列c4都解壓了。然而，對于一個(gè)行組，如果列c4中沒(méi)有值為1的域，那么就無(wú)需解壓列c1。 行組大小 I/O性能是RCFile關(guān)注的重點(diǎn)，因此RCFile需要行組夠大并且大小可變。行組大小和下面幾個(gè)因素相關(guān)。 行組大的話(huà)，數據壓縮效率會(huì )比行組小時(shí)更有效。根據對Facebook日常應用的觀(guān)察，當行組大小達到一個(gè)閾值后，增加行組大小并不能進(jìn)一步增加Gzip算法下的壓縮比。 行組變大能夠提升數據壓縮效率并減少存儲量。因此，如果對縮減存儲空間方面有強烈需求，則不建議選擇使用小行組。需要注意的是，當行組的大小超過(guò)4MB，數據的壓縮比將趨于一致。 盡管行組變大有助于減少表格的存儲規模，但是可能會(huì )損害數據的讀性能，因為這樣減少了Lazy解壓帶來(lái)的性能提升。而且行組變大會(huì )占用更多的內存，這會(huì )影響并發(fā)執行的其他MapReduce作業(yè)�？紤]到存儲空間和查詢(xún)效率兩個(gè)方面，Facebook選擇4MB作為默認的行組大小，當然也允許用戶(hù)自行選擇參數進(jìn)行配置。 小結 本文簡(jiǎn)單介紹了RCFile存儲結構，其廣泛應用于Facebook公司的數據分析系統Hive中。首先，RCFile具備相當于行存儲的數據加載速度和負載適應能力；其次，RCFile的讀優(yōu)化可以在掃描表格時(shí)避免不必要的列讀取，測試顯示在多數情況下，它比其他結構擁有更好的性能；再次，RCFile使用列維度的壓縮，因此能夠有效提升存儲空間利用率。 為了提高存儲空間利用率，Facebook各產(chǎn)品線(xiàn)應用產(chǎn)生的數據從2010年起均采用RCFile結構存儲，按行存儲（SequenceFile/TextFile）結構保存的數據集也轉存為RCFile格式。此外，Yahoo公司也在Pig數據分析系統中集成了RCFile，RCFile正在用于另一個(gè)基于Hadoop的數據管理系統Howl（http://wiki.apache.org/pig/Howl）。而且，根據Hive開(kāi)發(fā)社區的交流，RCFile也成功整合加入其他基于MapReduce的數據分析平臺。有理由相信，作為數據存儲標準的RCFile，將繼續在MapReduce環(huán)境下的大規模數據分析中扮演重要角色。 |
