吳齊躍

[摘要] 針對當前傳統(tǒng)數(shù)據(jù)庫技術(shù)對大數(shù)據(jù)進行分析時系統(tǒng)性能嚴重下降、查詢效率受限的問題，本文研究分布式文件系統(tǒng)中數(shù)據(jù)讀取關(guān)鍵技術(shù)。在分布式系統(tǒng)中，數(shù)據(jù)的存儲結(jié)構(gòu)直接影響著大數(shù)據(jù)的存儲效率和處理性能，本文基于行列存儲結(jié)構(gòu)的特點，綜合比較不同存儲的模式在大數(shù)據(jù)應(yīng)用中的優(yōu)劣，展望未來研究與應(yīng)用方向。

[關(guān)鍵詞] 大數(shù)據(jù)；列存儲；MapReduce；

1 引言

在信息化技術(shù)高度發(fā)展的今天，大數(shù)據(jù)應(yīng)用變得日漸普及而且非常重要。鑒于傳統(tǒng)關(guān)系型數(shù)據(jù)庫在大數(shù)據(jù)應(yīng)用領(lǐng)域應(yīng)用時遇到的困難，基于分布式的海量數(shù)據(jù)管理是當前的研究熱點，這就包括如何有效地存儲和處理這些增長迅速的海量數(shù)據(jù)。

一半而言大數(shù)據(jù)的數(shù)據(jù)規(guī)?？梢赃_到PB級，這就對存儲空間和計算能力提出了很高的要求，大數(shù)據(jù)存儲的數(shù)據(jù)類型多，復(fù)雜度高。大數(shù)據(jù)環(huán)境下，對數(shù)據(jù)存儲的組織和管理提出了更高的要求。本文在分析列存儲技術(shù)和分布式存儲系統(tǒng)HDFS 局限性基礎(chǔ)上，重點研究了數(shù)據(jù)存放結(jié)構(gòu)，綜述了各項關(guān)鍵技術(shù)當前的研究現(xiàn)狀，分析了現(xiàn)有技術(shù)存在的問題探討如何使用列存儲技術(shù)提升大數(shù)據(jù)存儲和處理的性能以提升大數(shù)據(jù)查詢的效率，并展望了未來研究的發(fā)展方向。

2 列存儲技術(shù)

2.1 列存儲方式

自SIGMOD85會議論文A Decomposition Storage Model [ ] 提出了DSM概念以來， 經(jīng)歷30年的發(fā)展，在Stonebraker 、Abadi、 Boncz 等為首的一批數(shù)據(jù)庫專家的大力提倡下， 列存儲相關(guān)技術(shù)及應(yīng)用快速得到了快速發(fā)展， 這種技術(shù)的特點是對復(fù)雜數(shù)據(jù)的查詢效率高， 讀取磁盤少， 存儲空間占用少。這些特點使其大數(shù)據(jù)和OLAP應(yīng)用存儲的理想結(jié)構(gòu)。

列存儲是相對于行存儲而言的，列存儲最核心的技術(shù)就是基于垂直分區(qū)的存儲設(shè)計和訪問模式。列存儲系統(tǒng)將數(shù)據(jù)庫完全劃分為多個獨立的列的集合進行存儲，圖1展示了行存儲和列存儲的在物理存儲設(shè)計上的本質(zhì)區(qū)別，展示了3種數(shù)據(jù)庫的存儲方式，其中圖 1（a） 和圖 1（b））是兩種列存儲的方式，每一列單獨保存Sales表中的每個屬性數(shù)據(jù)對象，圖1（c）是行存儲形式。

列存儲數(shù)據(jù)庫只需查詢讀取涉及關(guān)系中某些數(shù)據(jù)列，避免無關(guān)列的提取，不像行存儲那樣需要從磁盤讀取整行信息并去除不需要的屬性信息，從而減少I/O和內(nèi)存帶寬的占用，提高查詢效率。而且，同一列數(shù)據(jù)屬性相同，可以使用針對性的壓縮算法，因此壓縮效率高。C-Store[ ]和Monet DB[ ]是其中有影響力的代表性成果，它們在存儲結(jié)構(gòu)、查詢優(yōu)化、壓縮等方面進行了很多技術(shù)創(chuàng)新，使得列存儲相比較行存儲而言更適合大規(guī)模的訪問和查詢。

2.2 列存儲關(guān)鍵技術(shù)

（1）壓縮技術(shù)

Abadi D J [ ]在SIGMOD06會議上提出列存儲的主要壓縮方法有：行程編碼算法、詞典編碼算法、位向量編碼算法。

①行程編碼算法（Run-length Encoding-RLE）

行程編碼算法用一個三元組記錄數(shù)據(jù)值。這個三元組記錄包括數(shù)據(jù)出現(xiàn)的起始位置和持續(xù)長度（ 即行程） ，目的在于壓縮原始數(shù)據(jù)的長度，適用于相同數(shù)據(jù)連續(xù)存儲的情況，三元組描述為（ X，Y，Z） ，X 表示數(shù)據(jù)的值，Y 表示數(shù)據(jù)起始位置，Z 表示長度。舉例而言假如在一個列中初始的50個元素中包含值‘W，則這50個元素可以表示為三元組（‘W， 1， 50）。

該技術(shù)適用于重復(fù)數(shù)據(jù)較多的的數(shù)據(jù)列，具有較好的壓縮效果，缺點是對列值的重復(fù)性及排序要求較高。

②詞典編碼算法（Dictionary Compression）

詞典編碼算法將原始值轉(zhuǎn)換成替代值存儲在系統(tǒng)中，所以會產(chǎn)生 “原始值-替代值”對照詞典，替代值的長度大大小于原始值的長度，從而達到壓縮存儲空間的目的。如圖2 所示， 可以用簡單的兩位數(shù)字代替原始字符串， 從而縮短所需存儲空間。

該算法對于數(shù)據(jù)類型要求較低，不要求數(shù)據(jù)排序，缺點是要創(chuàng)建詞典表，維護成本高，如果數(shù)據(jù)重復(fù)性不高則詞典表會過于龐大。

③位向量編碼算法（Bit-Vector Encoding）

位向量編碼是為每一個不同的取值生成一個位向量， 根據(jù)位向量（串）中不同的位置取值0或1 來對應(yīng)并確定不同的原始值。位向量編碼算法是輕量級的編碼算法，可以直接在壓縮數(shù)據(jù)上進行操作，可以降低CPU 成本。例如對以下的列存儲數(shù)據(jù)：

該算法對數(shù)據(jù)類型要求不高，在有些情況下查詢效率甚至高于詞典編碼，缺點是位置數(shù)據(jù)會因為取值空間的太大或者重復(fù)性低導(dǎo)致空間占用較大。

對于列存儲主要應(yīng)用的海量數(shù)據(jù)查詢分析領(lǐng)域，有效壓縮是一個十分重要的優(yōu)勢。

（2）延時物化

延時物化的主要優(yōu)點在于允許對壓縮態(tài)的列存儲數(shù)據(jù)進行高性能操作，具備高效的壓縮傳輸數(shù)據(jù)開銷，通過延遲元組物化，盡可能少的進行元組物化，盡可能地避免了不必要的實際數(shù)據(jù)傳輸開銷。

元組物化是將常用元組從實際物理存儲的狀態(tài)生成為實體化的元組， 即物化存儲在內(nèi)存中。在以后的查詢中， 方便直接讀取已物化元組， 從而提高查詢效率。物化有提前物化和延時物化兩種，提前物化在提交查詢之前物化元組； 延時物化是推遲物化元組時間， 在查詢最后時刻物化元組。對于列存儲數(shù)據(jù)庫而言， 提前物化需要解壓壓縮數(shù)據(jù)，時間和空間的開銷都很大，而提前物化會涉及到很多不必要的列。

Abadi D J在文獻[ ] 中， 詳細介紹了兩種物化方式的實驗過程，證明延時物化許多性能上的潛力只有在列存儲數(shù)據(jù)庫中才能發(fā)揮。文獻[ ]比較了提前物化和延時物化的優(yōu)劣，在延時物化引入橫向信息傳遞技術(shù)應(yīng)用，有效解決了溢出連接產(chǎn)生的性能下降問題。

3 列存儲技術(shù)在大數(shù)據(jù)分析中的

3.1 大數(shù)據(jù)分析的存儲

國際數(shù)據(jù)中心（IDC）在2011 年的報告[ ]中定義了大數(shù)據(jù)： “大數(shù)據(jù)技術(shù)描述了一個技術(shù)和體系的新時代， 被設(shè)計于從大規(guī)模多樣化的數(shù)據(jù)中通過高速捕獲、發(fā)現(xiàn)和分析技術(shù)提取數(shù)據(jù)的價值”。 這個定義刻畫了大數(shù)據(jù)的4 個顯著特點， 即容量（volume）、多樣性variety）、速度（velocity） 和價值（value）。大數(shù)據(jù)具有規(guī)模大、深度大、寬度大、處理時間短、硬件系統(tǒng)普通化和軟件系統(tǒng)開源化的特點。

現(xiàn)有大數(shù)據(jù)處理技術(shù)主要有對稱多處理機架構(gòu)（SMP）和大規(guī)模并行處理架構(gòu)（MPP）兩大類。在數(shù)據(jù)量極速增長的大數(shù)據(jù)背景下，計算分布和存儲分布的MPP架構(gòu)成為主流。MapReduce[ ]分布式并行計算是MPP架構(gòu)的代表。Hadoop[ ]是MapReduce分布式計算框架的實現(xiàn)，為大數(shù)據(jù)處理大型分布式集群，通過分布式存儲系統(tǒng)HDFS（ Hadoop Distributed File System）[ ]來管理海量數(shù)據(jù)。如何在HDFS 中設(shè)計一個高效的數(shù)據(jù)存儲結(jié)構(gòu)來組織大數(shù)據(jù)遇到了一系列的困難，而影響大數(shù)據(jù)查詢分析性能的關(guān)鍵因素是能夠滿足充分利用MapReduce 計算特性來處理大數(shù)據(jù)。

3.2 大數(shù)據(jù)分析中的數(shù)據(jù)存儲

基于Hadoop系統(tǒng)的數(shù)據(jù)倉庫中，數(shù)據(jù)存儲格式是影響數(shù)據(jù)倉庫性能的一個重要因素，它直接影像如何高效的存儲、管理和使用這寫數(shù)據(jù)。在Hadoop運行環(huán)境中，數(shù)據(jù)的存儲格式要滿足以下幾個特點： 數(shù)據(jù)加載數(shù)據(jù)要快、數(shù)據(jù)查詢處理要快、 高效的數(shù)據(jù)存儲空間利用率、適應(yīng)高強度的動態(tài)負載模式。

對比圖3中行列存儲方式的不同，基于行存儲的數(shù)據(jù)結(jié)構(gòu)：優(yōu)點是具備快速數(shù)據(jù)加載和動態(tài)負載的高適應(yīng)能力，因為行存儲保證了相同記錄的所有域都在同一個集群節(jié)點；但是它不太滿足快速的查詢響應(yīng)時間的要求，特別是在當查詢僅僅針對所有列中的少數(shù)幾列時，它就不能直接定位到所需列而跳過不需要的列，由于混合著不同數(shù)據(jù)值的列，行存儲不易獲得一個極高的壓縮比，行存儲不易獲得一個較高的壓縮比。

在面向列的文件存儲結(jié)構(gòu)中，列A和列B存儲在同一列組，而列C和列D分別存儲在單獨的列組。這種結(jié)構(gòu)使得在查詢時能夠直接讀取需要的列而避免不必要列的讀取，并且對于相似數(shù)據(jù)也可以有一個更好的壓縮比。但是他的缺點也很明顯，那就是由于元組重構(gòu)的較高開銷，它并不能提供基于Hadoop系統(tǒng)的快速查詢處理，也不能保證不能保證同一記錄的所有列都存儲在同一集群節(jié)點之上，也適應(yīng)高度動態(tài)的數(shù)據(jù)負載模式。

基于行列混合存儲的RCFile[ ]，如圖4所示，它即滿足快速數(shù)據(jù)加載和動態(tài)負載高適應(yīng)的需求外，也解決了數(shù)據(jù)查詢處理的瓶頸。該存儲結(jié)構(gòu)遵循的是“先水平劃分，再垂直劃分”的設(shè)計理念。先將數(shù)據(jù)按行水平劃分為行組，這樣一行的數(shù)據(jù)就可以保證存儲在同一個集群節(jié)點；然后在對行進行垂直劃分。RCFile具備相當于行存儲的數(shù)據(jù)加載速度和負載適應(yīng)能力，在讀數(shù)據(jù)時可以在掃描表格時避免不必要的列讀取，它比其他結(jié)構(gòu)擁有更好的性能，使用列維度的壓縮能夠有效提升存儲空間利用率。

通過設(shè)計一個分布式文件存儲格式（MapReduce column-store file，MCF），基于列存儲的大數(shù)據(jù)分析系統(tǒng)物化策略，在MapReduce分布式并行處理環(huán)境中結(jié)合列存儲技術(shù)對物化策略進行優(yōu)化執(zhí)行。

在數(shù)據(jù)加載中，利用列存儲的特點提出數(shù)據(jù)存儲的協(xié)同定位策略來優(yōu)化數(shù)據(jù)的存儲，在數(shù)據(jù)加載過程中進行數(shù)據(jù)的預(yù)處理，通過構(gòu)建MapReduce早期物化策略、MapReduce延遲物化策略和MapReduce混合的物化策略，結(jié)合利用自適應(yīng)物化集合調(diào)整策略避免物化集合的惡性膨脹。通過實驗證明，物化策略和自適應(yīng)物化集合調(diào)整策略有效地減少MapReduce過程的中間數(shù)據(jù)、網(wǎng)絡(luò)帶寬占用和不必要的I/O開銷，較大提高大數(shù)據(jù)分析效率。

4 結(jié)束語

通過本文研究發(fā)現(xiàn)，行存儲結(jié)構(gòu)在數(shù)據(jù)加載的效率上優(yōu)于列存儲，但在數(shù)據(jù)壓縮的效率很低，不能有效地提高磁盤利用率。列存儲結(jié)構(gòu)在數(shù)據(jù)壓縮上有很好的壓縮效果，因為跨數(shù)據(jù)節(jié)點訪問使得數(shù)據(jù)加載及重構(gòu)的時間較長，對系統(tǒng)I/O要求較高。行列相結(jié)合的數(shù)據(jù)存儲結(jié)構(gòu)可以結(jié)合行存儲的高效數(shù)據(jù)加載和列存儲的高效數(shù)據(jù)壓縮效果，在大數(shù)據(jù)分布式系統(tǒng)中，行列數(shù)據(jù)存儲結(jié)構(gòu)極大地提高了大數(shù)據(jù)存儲及處理性能，SAP HANA和HP VERTICAL等都是很好的商用系統(tǒng)的例子。

基于列存儲的物化策略可以有效減少大數(shù)據(jù)調(diào)用過程中的中間數(shù)據(jù)為和元組重構(gòu)的開銷，減少網(wǎng)絡(luò)帶寬和I/0占用，極大提升大數(shù)據(jù)的查詢效率。

研究同時發(fā)現(xiàn)在應(yīng)用中應(yīng)該著重于適用與不同數(shù)據(jù)類型的大數(shù)據(jù)壓縮方法以及直接對壓縮數(shù)據(jù)的直接訪問及列存儲的MapReduce 連接索引技術(shù)研究，進一步優(yōu)化大數(shù)據(jù)查詢性能。