基于Trevni行列混合的分布式嵌套存儲(chǔ)研究

文衛(wèi)東，李 鴦，李文海

1.軟件工程國家重點(diǎn)實(shí)驗(yàn)室，武漢 430072

2.武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072

1 引言

伴隨互聯(lián)網(wǎng)相關(guān)技術(shù)的快速發(fā)展和分布式計(jì)算方法在數(shù)據(jù)密集型應(yīng)用的逐步深入，越來越多的數(shù)據(jù)庫平臺(tái)在面對(duì)半結(jié)構(gòu)化數(shù)據(jù)的查詢中引入存儲(chǔ)和計(jì)算并行化。近年來，相關(guān)并行化技術(shù)主要沿MapReduce[1]和MPP[2]（Massive Parallel Processing）兩個(gè)維度展開，二者顯著的不同在于數(shù)據(jù)庫算符與Map和Reduce兩個(gè)階段之間的轉(zhuǎn)換。其中，MPP更加側(cè)重于在不同計(jì)算階段之間盡量減少階段化的持久化操作，從而實(shí)現(xiàn)算符之間的管道工作（Pipelining）模式。一種折衷的方式[2-3]是將數(shù)據(jù)庫中無法管道化的操作分解成一個(gè)操作符超集（Super Cluster of Operators），從而實(shí)現(xiàn)超集內(nèi)管道化執(zhí)行，超集間持久化執(zhí)行。這一方式使得數(shù)據(jù)庫查詢的負(fù)載較傳統(tǒng)基于MapReduce的開源實(shí)現(xiàn)（如Hive[4]）更多依賴底層存儲(chǔ)和數(shù)據(jù)組織方法。

為提高數(shù)據(jù)訪問效率，列存儲(chǔ)技術(shù)自20世紀(jì)末被逐步引入，其常見的存儲(chǔ)[5]和組合[6]方式先后得到較為深入的研究。列存提升數(shù)據(jù)庫應(yīng)用的前提是查詢的局部性特征，即單個(gè)查詢?cè)谀硞€(gè)執(zhí)行階段上往往僅訪問數(shù)據(jù)模式中的一個(gè)子模式。通過引入列存，已有數(shù)據(jù)庫應(yīng)用中OLAP[7]（OnLine Analytical Processing）負(fù)載的可用性得到了保障。然而必須指出，OLAP的星型模式以減少數(shù)據(jù)冗余為目標(biāo)，引入了代價(jià)高昂的連接操作。早在20世紀(jì)80年代[8-9]，就有研究指出這些連接操作可以通過嵌套建模方式予以優(yōu)化，通過迭代遍歷嵌套記錄既保證數(shù)據(jù)的低冗余又通過線性掃描嵌套元組降低操作執(zhí)行代價(jià)。該思想直到近年仍然受到學(xué)界的廣泛重視[10-11]，同時(shí)有大量的開源框架[12]在持續(xù)開發(fā)。

列存儲(chǔ)和嵌套模型的混合催生了大量極具現(xiàn)實(shí)意義和研究價(jià)值的問題[13-16]。而其中一個(gè)核心問題在于如何在保證列存數(shù)據(jù)局部性的同時(shí)降低其高昂的裝配（Assembly）代價(jià)。這里的裝配可以解釋為將分散于各列的數(shù)據(jù)單元進(jìn)行封裝、形成滿足給定數(shù)據(jù)模式的各個(gè)記錄。傳統(tǒng)行存中的這一代價(jià)表現(xiàn)為連接被廣泛研究，而列存在去除連接后的代價(jià)主要集中于迭代遍歷單元以及依據(jù)模式構(gòu)建元組上。后者的代價(jià)更加側(cè)重于這樣一個(gè)事實(shí)：當(dāng)元組依據(jù)列存方式加載到內(nèi)存后，列和列之間的同屬一個(gè)元組的單元在內(nèi)存中不再連續(xù)，從而對(duì)其訪問在L1/L2緩存中的訪問效率也大大降低。此外，在嵌套模式下這一問題顯得更加突出：由于嵌套模式需要在不同層級(jí)之間維護(hù)一對(duì)多關(guān)聯(lián)關(guān)系，因而常用嵌套框架在跨層關(guān)聯(lián)時(shí)的表現(xiàn)不能讓人滿意[14]。

有鑒于此，本文研究并給出一個(gè)行列混合式存儲(chǔ)設(shè)計(jì)。該存儲(chǔ)方法的核心在于通過將經(jīng)常聚集訪問的屬性列按照行的方式與其他列等同建模和組織，形成空間上局部的若干列組、進(jìn)而保證數(shù)據(jù)交換的有效性和裝配的內(nèi)存局部性。為該設(shè)計(jì)目標(biāo)，研究深入分析了主流開源框架的模式和存儲(chǔ)構(gòu)成，通過特殊設(shè)計(jì)union結(jié)構(gòu)實(shí)現(xiàn)復(fù)雜類型的嵌入。研究設(shè)計(jì)并給出了一種特殊類型Group，并將該類型與普通列統(tǒng)一存儲(chǔ)。從而在當(dāng)查詢僅涉及到若干屬于某列組的單元時(shí)以行方式反序列化（Deserialize）元組，提高了列存的裝配性能。

2 相關(guān)研究

近年來，面向嵌套列存的研究伴隨Dremel[10]在Web級(jí)數(shù)據(jù)上的逐步深入應(yīng)用而被廣泛重視。該方法在數(shù)據(jù)庫領(lǐng)域曾得到深入研究，大量有關(guān)模式[8]、互操作[9]和存取方法[13]的優(yōu)化成果先后被提出。

Dremel的核心特色在于通過引入定義層（Definition Level，DL）和重復(fù)層（Repetition Level，RL）的嵌套抽象，使得任意嵌套記錄的層級(jí)映射可以通過狀態(tài)機(jī)轉(zhuǎn)換方式在兩個(gè)層次的數(shù)組上得到。即連續(xù)的子層元組通過列上對(duì)應(yīng)的重復(fù)層指示器得到層級(jí)，通過其定義層指示器得到單元是否為空值。該方法的優(yōu)勢在于通用，但每個(gè)可為空（nonrequired）的嵌套列均需要進(jìn)行轉(zhuǎn)換、降低了其裝配效率[14]。

Avro的列存核心組件Trevni[12]采用了層映射方法，即同一嵌套層次共享一個(gè)映射單元。該策略的優(yōu)勢在于裝配復(fù)雜度較Dremel低，但逐一計(jì)數(shù)的方式使得該存儲(chǔ)格式僅支持迭代方式。同時(shí)，Trevni的變長字段采取單元塊內(nèi)偏移與數(shù)據(jù)負(fù)載混合存放，進(jìn)一步降低了列映射的效率。已有研究通過引入Dremel設(shè)計(jì)思想改寫Trevni，如Parquet等。如上述可知，引入Dremel需要對(duì)嵌套列的每行增加RL和DL，從而增加了逐列進(jìn)行狀態(tài)轉(zhuǎn)換的代價(jià)。因而如何在保證列存優(yōu)勢的同時(shí)減少裝配代價(jià)仍然是Trevni和Dremel研究中的一個(gè)開放問題。

已有研究在上層模式上側(cè)重平坦化（Flattening）[13]和共享優(yōu)化設(shè)計(jì)[14]。平坦化研究分析并給出了避免上層高代價(jià)平坦化裝配操作的場景，與本文研究正交；而共享優(yōu)化僅限于單個(gè)映射節(jié)點(diǎn)，難以適用于具有任意級(jí)聯(lián)層次的即席（ad-hoc）查詢[6，15-16]，如富含嵌套連接條件的關(guān)系子查詢[17]或?qū)ο竽Ｐ拖耓18]面向嵌套模式的多選擇條件查詢。

3 行列混合存儲(chǔ)設(shè)計(jì)

本章給出嵌套模式列存架構(gòu)樣例，分析模式構(gòu)造與裝配的通用過程，進(jìn)而研究提出列組物理結(jié)構(gòu)。

3.1 通用嵌套行列混合模式

主流列存框架（如Trevni和Parquet等）將每個(gè)列存放于連續(xù)的物理塊中實(shí)現(xiàn)高效的按列提取。其中，Trevni的思路是同一個(gè)列的所有單元（unit）具有全局連續(xù)的偏移量，其表示為塊號(hào)和塊內(nèi)偏移；而Parquet采用Dremel架構(gòu)，基于定義層（Definition Level）表示某列的某個(gè)單元是否為空、基于復(fù)制層（Replication Level表示層級(jí)）。此外，Google的數(shù)據(jù)交換格式Protobuf也被廣為接受，其提供與JSON兼容的模式定義方法用于數(shù)據(jù)交換。Parquet與Trevni均采用計(jì)數(shù)原理完成不通層級(jí)之間的關(guān)聯(lián)。

圖1給出了Trevni和Parquet建立層級(jí)關(guān)聯(lián)的過程。該過程通過計(jì)數(shù)（Trevni采用圖1（a）所示方式）或復(fù)制層遍歷（Parquet如圖1（b）所示）對(duì)各個(gè)列獨(dú)立存儲(chǔ)的方式重建上下層之間的一對(duì)多關(guān)系。如果發(fā)生一個(gè)上層實(shí)體對(duì)下層的映射，可以根據(jù)行標(biāo)或復(fù)制層計(jì)數(shù)進(jìn)行裝配，模式的層級(jí)可以通過類似JSON的格式進(jìn)行定義。該方法的潛在不足之處在于：當(dāng)需要一對(duì)多重建嵌套記錄時(shí)，頻繁在列間進(jìn)行計(jì)數(shù)和狀態(tài)切換會(huì)帶來大量的裝配開銷。為此，研究給出一種新的邏輯模式定義與物理存儲(chǔ)分離的行列組織策略，迭代定義嵌套模式如下。

圖1 嵌套元組用例和兩種典型列存框架組織示意圖

定義1（邏輯嵌套模式）任意一個(gè)嵌套模式可基于樹結(jié)構(gòu)[13]遞歸定義如下。

該定義通過基本類型primary及集合類型array構(gòu)造了兩類高層對(duì)象object和value，并在這兩類高層對(duì)象基礎(chǔ)上遞歸定義了對(duì)象類型record和group。其中，record類型可遞歸通過primary、array或group分組構(gòu)成；group只能遞歸由array或primary構(gòu)成。考慮到規(guī)范化嵌套模式均可通過一個(gè)模式根Troot表達(dá)成上述定義中的record類型[13]，通過對(duì)不同類型定義列映射，建立如下行列混合存儲(chǔ)約束。

定義2（行列混合存儲(chǔ)）任意獨(dú)立存儲(chǔ)的連續(xù)物理單元必須由primary和group兩種類型的同構(gòu)實(shí)體或array類型的映射數(shù)組構(gòu)成。

該定義通過約定可連續(xù)存儲(chǔ)的單元類型，為混合存儲(chǔ)構(gòu)建了通用模式要素。這里任意模式根節(jié)點(diǎn)可以由多個(gè)列（集）的record構(gòu)成，其中每個(gè)列可以由三種類型構(gòu)成，三種類型數(shù)據(jù)實(shí)體按列連續(xù)存放（array的映射數(shù)組與primary等價(jià)處理）。下面給出一個(gè)典型的模式實(shí)例，其中record與group類型在“組”中取一種即可。當(dāng)選定group類型時(shí)，其下屬三個(gè)域需要作為整體連續(xù)存放。

3.2 基于Trevni的列組構(gòu)造

上述模式及其約束適用于主流嵌套列存框架，下面以Trevni為例對(duì)嵌套模式的列式存儲(chǔ)給出構(gòu)造方法。在該存儲(chǔ)框架下，以支持嵌套的模式元數(shù)據(jù)為基礎(chǔ)，該框架為列存數(shù)據(jù)庫提供了兩層描述。通過特別構(gòu)建列存映射數(shù)據(jù)塊形成不同層次的數(shù)據(jù)映射關(guān)系。模式中的每個(gè)葉子節(jié)點(diǎn)的數(shù)據(jù)連續(xù)保存于若干數(shù)據(jù)塊中，保證數(shù)據(jù)按列訪問的效率。在實(shí)現(xiàn)上，Trevni提供一組用于持久化基本類型的單列載入類ColumnFileReader，通過依次順序掃描維護(hù)在緩沖區(qū)InputBuffer中的單個(gè)列的所有實(shí)例，實(shí)現(xiàn)按列載入。能夠支持的基本類型有：長整形、布爾、整形、字符串、字節(jié)數(shù)組、浮點(diǎn)和定長類型等。

如圖2所示，Trevni的數(shù)據(jù)由一個(gè)文件頭和連續(xù)的列數(shù)據(jù)塊構(gòu)成，其中文件頭的核心結(jié)構(gòu)由版本號(hào)、基于JSON的模式信息和塊偏移量數(shù)組構(gòu)成。每個(gè)數(shù)據(jù)塊原則上被設(shè)計(jì)為定長的數(shù)據(jù)塊，每個(gè)塊的實(shí)際長度被保存于文件頭的偏移量結(jié)構(gòu)中，其中記錄每個(gè)塊的實(shí)際維護(hù)的單元（同屬于一個(gè)列的實(shí)例）數(shù)量。一個(gè)模式根節(jié)點(diǎn)下的子節(jié)點(diǎn)間關(guān)聯(lián)關(guān)系通過JSON格式的模式信息描述，模式特別對(duì)存在嵌套的字段構(gòu)建一個(gè)容器，所有同屬于一個(gè)父親的孩子節(jié)點(diǎn)共享一個(gè)一對(duì)多的映射結(jié)構(gòu)。圖2示意了這兩個(gè)核心結(jié)構(gòu)與所面向的數(shù)據(jù)塊之間的關(guān)系。其中，JSON格式給出了一個(gè)具有兩層級(jí)聯(lián)（Cascading）的嵌套關(guān)系：作者（Authors，簡稱A，下同）節(jié)點(diǎn)包含三個(gè)屬性，即名（F）、姓（L）和聯(lián)系地址（C）。

圖2 行列混合存儲(chǔ)示意圖

上述模式及其約束中，record類型為嵌套結(jié)構(gòu)，即一個(gè)父親下面可以有多個(gè)孩子節(jié)點(diǎn)，但是不經(jīng)array解釋，每個(gè)孩子在一個(gè)父親實(shí)例下僅有一個(gè)實(shí)例；array為行迭代類型，即一個(gè)父親實(shí)例可以有多個(gè)孩子實(shí)例。二者可以結(jié)合，用以描述具有層次嵌套關(guān)系的復(fù)雜實(shí)體。例如，一個(gè)文獻(xiàn)若有多個(gè)作者，則通過在作者映射數(shù)組中保存該文獻(xiàn)的作者數(shù)量，最終裝配過程中根據(jù)作者數(shù)量確定該文獻(xiàn)的作者。這一方法的優(yōu)勢在于當(dāng)查詢需要少量的列時(shí)，裝配僅發(fā)生在這些列上，有利于減少IO代價(jià)和記錄寬度。然而，由于多個(gè)同屬于一個(gè)父親的列，如上例中A到F、L、C三個(gè)子節(jié)點(diǎn)，在封裝對(duì)象時(shí)需要依次訪問對(duì)象數(shù)組元素、增加了裝配代價(jià)。

上例給出文獻(xiàn)的一個(gè)模式定義，其中作者信息依次由array和group嵌入類型構(gòu)成。原始Trevni給出的模式定義通過在group的位置定義record，從而使得頂層四個(gè)屬性和“作者”下屬三個(gè)屬性形成獨(dú)立的列，以構(gòu)成物理存儲(chǔ)結(jié)構(gòu)。通過引入例子中給出的group類型，將列組類型作為一種普通bytes類型與Trevni其他基礎(chǔ)類型采用相同的方法讀寫，并在裝配時(shí)根據(jù)每個(gè)group的變長實(shí)例的模式信息進(jìn)行反序列化。這樣同一頂層實(shí)體的下屬被頻繁聚集訪問的屬性列能夠以一個(gè)整體對(duì)每個(gè)實(shí)例反序列化，從而有利于提高裝配效率。

3.3 級(jí)聯(lián)存儲(chǔ)結(jié)構(gòu)

上述group構(gòu)造的基本原理是通過聚集group節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)和解析，從而在存儲(chǔ)階段以普通字節(jié)數(shù)組方式存取這些實(shí)體。而解析階段，依據(jù)該類型字段的讀寫對(duì)象、基于模式對(duì)字節(jié)數(shù)組進(jìn)行反序列化。下面針對(duì)上述過程詳述存儲(chǔ)方法。

設(shè)計(jì)解析group類型的GenericGroupReader，該類與ColumnFileReader和InputBuffer的轉(zhuǎn)換功能同構(gòu)，根據(jù)模式信息調(diào)用已讀入到內(nèi)存的group類型對(duì)象的反序列化接口。GenericGroupReader除了能夠支持上述基本類型外，還提供對(duì)array和record的嵌套反序列化。實(shí)現(xiàn)對(duì)這三類復(fù)雜結(jié)構(gòu)的嵌套調(diào)用，并對(duì)葉子節(jié)點(diǎn)的基本類型的實(shí)例進(jìn)行嵌套定義。不同于record，group將下屬所有節(jié)點(diǎn)按照行方式在磁盤塊中以字節(jié)數(shù)組方式存儲(chǔ)，從而保證了應(yīng)用中被連續(xù)訪問的字段能夠在空間上連續(xù)存放，從而可以保證反序列化和裝配的效率。

基于字節(jié)數(shù)組方式保存模式化group實(shí)例的塊分布如圖3所示。通過將圖2中的數(shù)據(jù)庫展開，可以看到采用group方式存儲(chǔ)的字段集與其他獨(dú)立存儲(chǔ)的字段之間在物理結(jié)構(gòu)上的差別。由上述模式樣例可知這里的作者信息包括姓、名和聯(lián)系三個(gè)字段，與其他字段共同構(gòu)成模式的頂層節(jié)點(diǎn)。

從圖中可以看到作者信息包含一個(gè)映射字段，用以維護(hù)文獻(xiàn)與作者之間的一對(duì)多映射。與該節(jié)點(diǎn)處于同一層次的關(guān)鍵字、修訂日期等字段采用列存儲(chǔ)（如上述模式定義所述），每個(gè)列分別占用連續(xù)的磁盤塊。其中，關(guān)鍵字信息也包含一個(gè)映射字段，用以描述一個(gè)文獻(xiàn)對(duì)多個(gè)關(guān)鍵字的約束。值得注意的是，這里的映射字段采用全局連續(xù)的偏移量進(jìn)行記錄，以方便快速定位一個(gè)字段的實(shí)例。在圖中，文獻(xiàn)[1]的兩個(gè)作者“張，三，武漢”，“李，四，北京”被連續(xù)存放于塊2和塊3，當(dāng)某查詢需要訪問這些作者信息的時(shí)候，該聚集存儲(chǔ)方法可以依次獲得同一作者的三個(gè)字段，從而有利于提高系統(tǒng)效率。對(duì)于其他列信息，查詢必須逐列序列化后再依據(jù)映射列的一對(duì)多關(guān)系分別裝配。

4 模式關(guān)聯(lián)方法

為進(jìn)一步加速反序列化過程，設(shè)計(jì)了變長字段塊內(nèi)聚集存儲(chǔ)策略，通過高效保存空值、偏移量和變長數(shù)據(jù)的字節(jié)數(shù)組，提高塊內(nèi)數(shù)據(jù)訪問效率。

4.1 塊內(nèi)聚集存儲(chǔ)

從圖3可知，對(duì)某屬性列（組），行列混合存儲(chǔ)面對(duì)三類對(duì)象存在不同的訪問方式，即葉子節(jié)點(diǎn)中基本類型的對(duì)象數(shù)組、葉子節(jié)點(diǎn)中g(shù)roup類型對(duì)象的字節(jié)數(shù)組和映射關(guān)系中的偏移量數(shù)組?？梢酝ㄟ^塊偏移量描述符對(duì)各個(gè)塊進(jìn)行定位，但在塊內(nèi)數(shù)據(jù)進(jìn)行反序列化的時(shí)候按照偏移量逐次確定列實(shí)例的邊界，使得查詢無法跳過無用的記錄。這在很多應(yīng)用中無法保證對(duì)空值的高效處理?；谶@一問題，研究給出了塊內(nèi)數(shù)據(jù)的一種快速訪問方法。

圖3 組按行關(guān)聯(lián)與不同層次之間列關(guān)聯(lián)示意圖

如圖4所示，綜合考慮空值和變長字段，給出一個(gè)優(yōu)化塊內(nèi)數(shù)據(jù)組織方法將每個(gè)數(shù)據(jù)塊分割為三個(gè)區(qū)。其中，指示器（Indicator）區(qū)以1位指示一個(gè)實(shí)例是否為空；偏移量（Offsets）區(qū)存放該實(shí)例在塊內(nèi)的開始地址；對(duì)于一個(gè)開始地址，數(shù)據(jù)區(qū)存放該實(shí)例的變長字節(jié)數(shù)組。默認(rèn)地，如果字段在模式定義中未聲明為null，則該字段不能為空，存儲(chǔ)結(jié)構(gòu)中不為該字段設(shè)置指示區(qū)。圖中給出了第3章模式的塊內(nèi)數(shù)據(jù)形式。對(duì)于“摘要”字段，模式定義為可以為空，因而該字段的每個(gè)數(shù)據(jù)塊采用三個(gè)區(qū)域?qū)?shù)據(jù)進(jìn)行組織。如果要訪問該塊中的第二個(gè)記錄（該記錄對(duì)應(yīng)第二個(gè)“文獻(xiàn)”）的“摘要”，反序列化過程首先根據(jù)模式找到指示器的第二位得到該實(shí)例不為空。然后基于偏移量區(qū)域的第二個(gè)元素定位到內(nèi)存中cache頁面的該實(shí)例起始位置，讀取該位置到下一個(gè)開始位置之前的字節(jié)數(shù)組。

圖4 塊內(nèi)空值—位置—數(shù)據(jù)三級(jí)訪問結(jié)構(gòu)

當(dāng)需要跳過若干字段的時(shí)候，可以直接在塊內(nèi)進(jìn)行二分查找、基于塊內(nèi)計(jì)數(shù)定位到需要跳轉(zhuǎn)的目的實(shí)例位置，完成對(duì)中間無用實(shí)例的跳過；當(dāng)發(fā)現(xiàn)若干實(shí)例為空的時(shí)候，同樣可以根據(jù)指示位“0”決定是否忽略該實(shí)例。這對(duì)于特殊場景（如選擇下推[6，14]或空值字段[13]）中的數(shù)據(jù)裝配具有較強(qiáng)的現(xiàn)實(shí)意義。同時(shí)，對(duì)于通常應(yīng)用中的記錄裝配，這些聚集存儲(chǔ)的指示位對(duì)每個(gè)實(shí)例僅占用一位的存儲(chǔ)空間，可以采用選擇下推操作提升訪問效率。

4.2 組裝流程設(shè)計(jì)

如前所述，列組中的數(shù)據(jù)在存儲(chǔ)時(shí)按照普通字節(jié)數(shù)組方式讀寫，在模式轉(zhuǎn)換過程中形成與復(fù)雜類型record同構(gòu)的行存嵌套對(duì)象。對(duì)于一個(gè)從模式根節(jié)點(diǎn)開始的訪問請(qǐng)求，需要以深度優(yōu)先方式（Breath first）依次訪問各層節(jié)點(diǎn)的列（組）數(shù)據(jù)塊，將其讀入內(nèi)存中的各個(gè)封裝器中。然后對(duì)其中的一對(duì)多的節(jié)點(diǎn)進(jìn)行組裝，形成嵌套記錄。

如圖5所示，深度優(yōu)先算法的流程以模式的讀取和解析作為起始過程，在遍歷完一個(gè)模式的所有節(jié)點(diǎn)后結(jié)束一個(gè)層次的訪問，其中的遍歷模式可以是數(shù)據(jù)模型的一個(gè)任意子集。例如，在上一章給出的模式定義中，可以根據(jù)用戶的查詢請(qǐng)求查找所有包含關(guān)鍵字集合{“存儲(chǔ)”，“數(shù)據(jù)庫”}的論文題名和作者信息。這一查詢模式（Pattern）實(shí)際上排除了除關(guān)鍵字和題名以外的其他屬性，是數(shù)據(jù)模式的一個(gè)子集。僅需要依次遍歷一級(jí)節(jié)點(diǎn)“關(guān)鍵字”，“題名”和“作者”。其元組組裝過程如下：

首先，加載模式根的一級(jí)列中的葉子“題名”，根據(jù)其對(duì)象數(shù)組找到第一個(gè)記錄的“題名”對(duì)象。

然后遍歷“題名”的兄弟節(jié)點(diǎn)，根據(jù)“關(guān)鍵字”字段的第一個(gè)映射元素找到四個(gè)關(guān)鍵字對(duì)象，并根據(jù)作者的映射關(guān)系找到兩個(gè)作者的三個(gè)字段。這一映射過程可以參考圖3的映射字段，并在其偏移量2的基礎(chǔ)上在圖4所示的塊結(jié)構(gòu)中找到對(duì)應(yīng)的作者信息。兩個(gè)字段均包含一個(gè)映射數(shù)組，但根據(jù)模式給定的類型差異分別做如下處理：

（1）“作者”字段為group類型，其對(duì)象以字節(jié)數(shù)組存放，需要在裝配階段反序列化。

（2）“關(guān)鍵字”字段為基本類型string，其對(duì)象在裝配之前的讀取階段已經(jīng)是string類型的字節(jié)數(shù)組了，因而僅需要進(jìn)行一次類型轉(zhuǎn)換。

（3）各節(jié)點(diǎn)均無孩子節(jié)點(diǎn)后，一個(gè)記錄完成；所有記錄裝配后，程序完成讀取。

圖5 嵌套分組層級(jí)之間關(guān)聯(lián)流程圖

4.3 代價(jià)分析與MapReduce接口設(shè)計(jì)

上述按照group裝配的特點(diǎn)在于：當(dāng)模式指定的字段為group類型時(shí)，根據(jù)映射數(shù)組可以一次順序地裝配一個(gè)記錄的所有字段。傳統(tǒng)列存方法下，因?yàn)榉葱蛄谢A段是按列組織列實(shí)例的，因而需要輪轉(zhuǎn)根據(jù)映射關(guān)系裝配所有作者的三個(gè)子字段。

對(duì)于上述列組的組裝方式，當(dāng)需要的字段信息一定時(shí)，一定范圍的低層對(duì)象的若干個(gè)列僅需要順序進(jìn)行反序列化和一次掃描裝配；與之相反，Trevni需要針對(duì)每個(gè)列獨(dú)立反序列化成對(duì)象數(shù)組，需要輪轉(zhuǎn)依據(jù)映射數(shù)組進(jìn)行裝配。假定一個(gè)包含c列的列組在第l層逐層具有ni:1的映射，則每個(gè)頂層記錄在Group方式下裝配該列的內(nèi)存代價(jià)為：

這里Dj為反序列化和裝配某列的代價(jià)，D為反序列化一個(gè)映射數(shù)組中一個(gè)元素的代價(jià)。通用列存分離存儲(chǔ)模式下由于需要根據(jù)列組訪問，其代價(jià)為：

可以看到式（2）的內(nèi)存操作多出了對(duì)每列進(jìn)行數(shù)組映射的代價(jià)。進(jìn)一步的，假定可以在頂層掃描過程中進(jìn)行過濾，如在反序列化前根據(jù)前一個(gè)過濾器確定后一個(gè)對(duì)象是否需要進(jìn)行反序列化和封裝，給定第一個(gè)頂層選擇率r，則式（1）縮減為：

在一個(gè)選擇過程中，通過度量每個(gè)列的裝配代價(jià)和掃描代價(jià)，從而得到下面的總代價(jià)：

其中Fj為在給定列（列為第 j層）上執(zhí)行選擇的代價(jià)，且反序列化和選擇分別具有O(Nnc)和O(Nn)的時(shí)間復(fù)雜度。因?yàn)榉葱蛄谢瘡?fù)雜度較高、其在式（2）中不會(huì)受益于選擇率，故式（3）描述的代價(jià)顯示出所提方法可線性減少下層嵌套列的反序列化代價(jià)。行列混合存儲(chǔ)合并了原本分離存放的列、不需要額外引入存儲(chǔ)空間，因而不會(huì)帶來額外的存儲(chǔ)開銷，且內(nèi)存合并行組與列存分列存儲(chǔ)的時(shí)間復(fù)雜度相同?；谶x擇率在不同層次之間進(jìn)行選擇下推[5，14]將被作為后續(xù)的研究目標(biāo)。

對(duì)于MapReduce下的列存數(shù)據(jù)庫存取，研究給出了相應(yīng)的實(shí)現(xiàn)?；趯?duì)Hadoop HDFS的對(duì)象讀取類RecordReader進(jìn)行重載，研究引入了上述帶有g(shù)roup類型的模式轉(zhuǎn)換實(shí)現(xiàn)和塊反序列化實(shí)現(xiàn)。其核心流程遵循RecordReader的約束，首先通過打開數(shù)據(jù)分片（Split）得到分布于HDFS中的數(shù)據(jù)塊，然后按照塊內(nèi)進(jìn)行數(shù)據(jù)分割。其中每個(gè)分割后的小塊用以容納某個(gè)列的連續(xù)實(shí)例的字節(jié)數(shù)組，其訪問方式與本地模式相同，文件的頭信息和模式在各個(gè)Map任務(wù)上保存一個(gè)副本。當(dāng)一個(gè)Map任務(wù)執(zhí)行Split的掃描的時(shí)候，基于HDFS的訪問原則，在本地?cái)?shù)據(jù)塊上進(jìn)行響應(yīng)的封裝操作。這里需要說明的是，HDFS的數(shù)據(jù)塊默認(rèn)值是128 MB、上限2 GB，這會(huì)使得大規(guī)模數(shù)據(jù)的查詢請(qǐng)求被劃分成很多小的Map任務(wù)，實(shí)驗(yàn)可以看到這一條件的影響。

5 實(shí)驗(yàn)驗(yàn)證分析

實(shí)驗(yàn)基于不同數(shù)據(jù)規(guī)模的TPCH基準(zhǔn)進(jìn)行。通過級(jí)聯(lián)Customer、Orders、Lineitem三個(gè)表形成三級(jí)嵌套模式COL，生成具有不同選擇列和不同選擇率的查詢條件進(jìn)行測試和比較，以驗(yàn)證所提基于group方法的優(yōu)劣。特別的，比較過程中引入了原始的Trevni實(shí)現(xiàn)和一個(gè)基于Trevni的Deremel實(shí)現(xiàn)——Parquet。將在行存Avro和這兩類列存框架下進(jìn)行綜合比較。最后給出了真實(shí)數(shù)據(jù)Pubmed，通過對(duì)不同框架執(zhí)行時(shí)間比較，分析研究給出了技術(shù)的適用性實(shí)驗(yàn)分析結(jié)果。

實(shí)驗(yàn)環(huán)境中硬件由一個(gè)Dell 720服務(wù)器和一套集群系統(tǒng)分別對(duì)各類存儲(chǔ)框架在單節(jié)點(diǎn)和分布式環(huán)境下進(jìn)行比較。其中，Dell 720服務(wù)器由2個(gè)Intel Xeon ES-2640 8核CPU構(gòu)成，內(nèi)存為320 GB，磁盤由180 MB/s的SCSI磁盤構(gòu)成。單節(jié)點(diǎn)實(shí)驗(yàn)均在軟件設(shè)計(jì)中采用單線程執(zhí)行。集群由4節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)配備了24核AMD OperonTM1674CPU，內(nèi)存128 GB，網(wǎng)絡(luò)由40 Gb/s的InfiniBand網(wǎng)絡(luò)連通。

實(shí)驗(yàn)1變投影列實(shí)驗(yàn)

通過在COL級(jí)聯(lián)表的路徑上分別選擇不同數(shù)量的列驗(yàn)證存儲(chǔ)框架的IO和內(nèi)存效率，其中列的選擇要求是級(jí)聯(lián)外建關(guān)鍵字至少被選中。此外，其他的列平均分布于不同的層次上。實(shí)驗(yàn)分別選擇總共4、6、8、10個(gè)列作為投影列進(jìn)行元組提取驗(yàn)證，最終提取的元組以嵌套方式返回，以查詢的平均執(zhí)行時(shí)間作為度量標(biāo)準(zhǔn)。

如圖6所示，不同列數(shù)對(duì)列存影響顯著。其中圖6（a）為磁盤IO環(huán)境下的執(zhí)行時(shí)間，即每次查詢需要清空所有系統(tǒng)緩存區(qū)，保證數(shù)據(jù)讀取操作對(duì)磁盤的訪問。顯而易見，不管任何情況下Avro的行存結(jié)構(gòu)需要讀取所有列，因而其IO時(shí)間相對(duì)穩(wěn)定；而幾種列存框架僅需要訪問所需的列數(shù)據(jù)，因此其執(zhí)行時(shí)間大致與列數(shù)呈線性關(guān)系。圖6（b）給出了裝配時(shí)間，即在查詢前先執(zhí)行一次查詢，保證第二次的統(tǒng)計(jì)時(shí)間不包含IO時(shí)間（實(shí)驗(yàn)內(nèi)存遠(yuǎn)大于數(shù)據(jù)規(guī)模）。從圖中可以看到上述結(jié)果依然成立，即三種列存框架的效率顯著優(yōu)于行存框架Avro。此外，由于同一層次的選擇在Group中采用順序反序列化，因而其效率優(yōu)于原始Trevni的實(shí)現(xiàn)，而Parquet需要對(duì)投影的每個(gè)嵌套列進(jìn)行一次較為耗時(shí)的裝配，影響了其執(zhí)行效率。

圖6 嵌套分組與其他方法在磁盤和內(nèi)存中執(zhí)行時(shí)間比較

此外，一個(gè)顯著的現(xiàn)象需要分析：磁盤環(huán)境下的執(zhí)行時(shí)間僅比內(nèi)存下略大。這是由于現(xiàn)有操作系統(tǒng)廣泛采用磁盤預(yù)取技術(shù)，這使得IO和反序列化并行執(zhí)行。圖中的磁盤環(huán)境執(zhí)行的同時(shí)內(nèi)存中也并行執(zhí)行反序列化，因而統(tǒng)計(jì)的時(shí)間可理解為IO時(shí)間；而沒有IO時(shí)（圖6（b）），統(tǒng)計(jì)時(shí)間等價(jià)為反序列化等內(nèi)存操作的執(zhí)行時(shí)間。

實(shí)驗(yàn)2不同層次上的變選擇率實(shí)驗(yàn)

分別在同層和嵌套層次下進(jìn)行變選擇率實(shí)驗(yàn)，驗(yàn)證所提方法的優(yōu)越性。

如圖7（a）所示，選擇在嵌套表的Lineitem層級(jí)上進(jìn)行4列選擇，比較行存和三種列存方法。由于該層為嵌套表COL的核心負(fù)載，因而可以看到列存較行存節(jié)省了大約3/4的執(zhí)行時(shí)間（列存僅需讀取Lineitem16列中的4列）；同時(shí)，Group在這種沒有映射的平坦掃描的查詢中優(yōu)勢不明顯。而圖7（b）新增了三個(gè)層次中的另外兩列，總計(jì)構(gòu)成對(duì)COL三個(gè)層級(jí)一共10列的掃描。從執(zhí)行結(jié)果上看，Group因?yàn)檩^小的級(jí)聯(lián)組裝代價(jià)，執(zhí)行時(shí)間比Trevni節(jié)省了約2/3；此外上一個(gè)實(shí)驗(yàn)中Parquet的高代價(jià)分析在該實(shí)驗(yàn)結(jié)果中再次得到驗(yàn)證。

圖7 嵌套分組在不同模式下的執(zhí)行時(shí)間比較

實(shí)驗(yàn)3分布式環(huán)境效率比較

基于MapReduce對(duì)上述實(shí)驗(yàn)1進(jìn)行分布式效率比較。由于Trevni的數(shù)據(jù)轉(zhuǎn)換需要容納于內(nèi)存，無法轉(zhuǎn)換160 GB的數(shù)據(jù)，因而實(shí)驗(yàn)引入另一個(gè)分布式數(shù)據(jù)庫Asterix（DB）進(jìn)行比較。對(duì)Group數(shù)據(jù)采用構(gòu)建—?dú)w并方式進(jìn)行加載，并基于不同Map物理任務(wù)限制驗(yàn)證不同任務(wù)數(shù)量下，4個(gè)節(jié)點(diǎn)配備時(shí)的平均執(zhí)行時(shí)間。

圖8和圖9分別給出了不同并發(fā)度上的執(zhí)行時(shí)間對(duì)比。從圖中可以看到Group方式的效率在分布式環(huán)境下較其競爭對(duì)手更優(yōu)越，其執(zhí)行時(shí)間較次優(yōu)的Parquet節(jié)省了3/5。同時(shí)可以看到當(dāng)訪問層次更深的時(shí)候Asterix的模式內(nèi)置方式與Group方式相當(dāng)。而伴隨并發(fā)度的提升，Avro行存模式和Group受到的影響不大，均保持了大致線性的加速比；Parquet的執(zhí)行時(shí)間加速比其他幾種策略略低。這些都驗(yàn)證了Group方式的優(yōu)化在分布式環(huán)境下的有效性。

圖9 總數(shù)據(jù)量160 GB上16并發(fā)任務(wù)的執(zhí)行時(shí)間

上述執(zhí)行過程中，通過不斷增加節(jié)點(diǎn)數(shù)量對(duì)上述4個(gè)查詢的平均執(zhí)行時(shí)間進(jìn)行統(tǒng)計(jì)比較，如圖10所示。可以看到不同存儲(chǔ)架構(gòu)和大數(shù)據(jù)平臺(tái)的執(zhí)行時(shí)間大致隨節(jié)點(diǎn)數(shù)量增加而減少。其中研究給出的方法在不同規(guī)模下具有較好的可擴(kuò)展性。

圖10 總數(shù)據(jù)量160 GB上變節(jié)點(diǎn)數(shù)量查詢平均執(zhí)行時(shí)間

實(shí)驗(yàn)4真實(shí)負(fù)載執(zhí)行效率比較

最后通過在Medline網(wǎng)站下載真實(shí)的Pubmed數(shù)據(jù)，共計(jì)1 800萬嵌套記錄，模式包含107個(gè)節(jié)點(diǎn)，共計(jì)80 GB。不同框架在磁盤和內(nèi)存中的執(zhí)行時(shí)間如圖11所示。

圖中顯示非行存框架Parquet、Trevni和Group的執(zhí)行結(jié)果基本與圖6給出的結(jié)果一致。該模式較為復(fù)雜（模式節(jié)點(diǎn)多且層次更深），其中選擇僅在很少的列上執(zhí)行，因而相對(duì)于圖6，圖11中行存框架Avro的執(zhí)行效率進(jìn)一步顯著降低。此外，可以看到Group較之于其他框架仍具有顯著優(yōu)勢。

圖11 嵌套分組與其他方法真實(shí)負(fù)載性能比較

6 結(jié)束語

提出一種行列混合式存儲(chǔ)方法，通過引入分組形成邏輯上完整但局部上獨(dú)立的列組物理單元。分析了現(xiàn)有單純行存儲(chǔ)和列存儲(chǔ)的優(yōu)勢和潛在不足，并通過模式驅(qū)動(dòng)設(shè)計(jì)行列混合物理存儲(chǔ)結(jié)構(gòu)。基于Trevni對(duì)所提方法予以實(shí)現(xiàn)以降低列存到元組轉(zhuǎn)換過程中的開銷并保證數(shù)據(jù)交換的有效性。通過union對(duì)存儲(chǔ)結(jié)構(gòu)進(jìn)行優(yōu)化，使得訪問能夠集中于有效的單元中。實(shí)驗(yàn)基于10億條TPCH數(shù)據(jù)進(jìn)行。結(jié)果表明所提方法較傳統(tǒng)行列存儲(chǔ)方法有顯著提升。