基于多級列式索引的海量數(shù)據(jù)高效查詢設(shè)計

楊淙鈞+艾中良+劉忠麟+李常寶

摘要：伴隨海量數(shù)據(jù)存儲、處理技術(shù)的發(fā)展，數(shù)據(jù)中心中積累了大量的格式化歷史數(shù)據(jù)，此類數(shù)據(jù)呈現(xiàn)出數(shù)據(jù)規(guī)模龐大、被查詢頻次低和查詢內(nèi)容規(guī)律不確定等特點(diǎn)，而當(dāng)前以文件為操作對象的系統(tǒng)在查詢此類數(shù)據(jù)時主要采用分布式計算引擎對數(shù)據(jù)進(jìn)行全局遍歷，存在處理時間長、系統(tǒng)資源消耗高等問題。因此，本文提出了一種基于列式多級索引的海量數(shù)據(jù)高效查詢方法，使得查詢過程中只有承載相關(guān)數(shù)據(jù)的節(jié)點(diǎn)參與計算，大幅降低了系統(tǒng)資源消耗。實驗表明，本文方法在用于大規(guī)模歷史數(shù)據(jù)內(nèi)容查詢時，相對于較主流的文件系統(tǒng)查詢技術(shù)有明顯的效率提升。

關(guān)鍵詞：海量數(shù)據(jù)；文件系統(tǒng)；索引機(jī)制

中圖分類號：TP314 文獻(xiàn)標(biāo)識碼：A DOI：10.3969/j.issn.1003-6970.2016.03.020

0引言

隨著大數(shù)據(jù)技術(shù)的發(fā)展以及互聯(lián)網(wǎng)+應(yīng)用模式的不斷推廣，通過分析全信息要素獲取更加準(zhǔn)確信息的數(shù)據(jù)分析模式被各領(lǐng)域廣泛采用，許多領(lǐng)域中存在大量信息采集原始數(shù)據(jù)并積累了大規(guī)模的歷史產(chǎn)品數(shù)據(jù)，其中包含了大量有價值的信息要素，目前該類數(shù)據(jù)主要采用文件系統(tǒng)存儲，當(dāng)前大數(shù)據(jù)技術(shù)僅支持對分布式文件系統(tǒng)中的數(shù)據(jù)進(jìn)行全量處理，而數(shù)據(jù)調(diào)研分析是制定海量數(shù)據(jù)處理流程的前提，當(dāng)前技術(shù)無法有效支撐數(shù)據(jù)調(diào)研階段內(nèi)容分析。針對這一問題，本文設(shè)計了較為完善的數(shù)據(jù)查詢系統(tǒng)，通過建立合理的索引、數(shù)據(jù)模型為分布式文件系統(tǒng)構(gòu)建高效內(nèi)存查詢功能。

本文首先介紹國內(nèi)外研究現(xiàn)狀，針對海量格式化的歷史數(shù)據(jù)查詢問題，詳細(xì)分析當(dāng)前技術(shù)的局限性；然后闡述基于列式多級索引的海量數(shù)據(jù)高效查詢方法，在此基礎(chǔ)上進(jìn)行系統(tǒng)實現(xiàn)，最后通過實驗對本文方法的有效性進(jìn)行驗證。

1工團(tuán)國內(nèi)外研究現(xiàn)狀

隨著對海量數(shù)據(jù)的存儲及使用的需求得增多，許多企業(yè)、組織對海量數(shù)據(jù)的存儲、查詢做出了研究，并開發(fā)出相應(yīng)工具，例如Apache SoftwareFoundation（AFS）的HBase和Hive項目，Google公司開發(fā)的Dremel等。

Hadoop Database，是一個高可靠性、高性能、面向列、可伸縮的分布式存儲系統(tǒng)，利用HBase技術(shù)可在廉價PC上搭建起大規(guī)模結(jié)構(gòu)化存儲集群。由于HBase使用了基于RowKey進(jìn)行檢索的機(jī)制，因此無法在不指定RowKey的情況下針對列簇中的值直接進(jìn)行條件查詢。

Hive是一個基于Hadoop的開源數(shù)據(jù)倉庫工具，用于存儲和處理海量結(jié)構(gòu)化數(shù)據(jù)。Hive提供了一套類數(shù)據(jù)庫的數(shù)據(jù)存儲和處理機(jī)制，并采用HQL（類SQL）語言對數(shù)據(jù)進(jìn)行自動化管理和處理。Hive經(jīng)過對語句進(jìn)行解析和轉(zhuǎn)換，最終生成一系列MapReduce任務(wù)，通過執(zhí)行產(chǎn)生的任務(wù)完成對數(shù)據(jù)的處理。由于Hive需要使用MapReduce任務(wù)對數(shù)據(jù)進(jìn)行遍歷查詢，因此查詢效率低。

Dremel是Google的“交互式”數(shù)據(jù)分析系統(tǒng)，可以處理PB級別的數(shù)據(jù)，并將處理數(shù)據(jù)的時間縮短到秒級。Dremel并非是MapReduce的替代品，而是作為MapReduee的有力補(bǔ)充，常常被用來處理MapReduee的結(jié)果集或用來建立分析原型。由于Dremel采用了基于內(nèi)存的查詢方式，受集群內(nèi)存的限制，因此難以將非高頻使用的數(shù)據(jù)全部導(dǎo)入作為待查詢數(shù)據(jù)。

2基于列式多級索引的海量數(shù)據(jù)高效查詢方法

在海量數(shù)據(jù)環(huán)境中，由于數(shù)據(jù)規(guī)模的原因，需要將數(shù)據(jù)存儲于分布式文件系統(tǒng)中，而直接基于文件的查詢方式不僅查詢效率低而且系統(tǒng)資源消耗大，因此本文設(shè)計了基于列式多級索引的海量數(shù)據(jù)高效查詢方法。

本章首先介紹了數(shù)據(jù)組織方式以及列式多級索引模型，其次介紹了索引的更新方式，最后具體的介紹了基于列式多級索引的海量數(shù)據(jù)高效查詢的流程。

2.1數(shù)據(jù)組織

由于海量數(shù)據(jù)環(huán)境中，單機(jī)節(jié)點(diǎn)的存儲系統(tǒng)無法存放所有的數(shù)據(jù)，因此本課題所設(shè)計的查詢系統(tǒng)將數(shù)據(jù)存儲在HDFS（Hadoop Distributed File Sys-tern，Hadoop分布式文件系統(tǒng)），以展開基于文件的查詢。

雖然HDFS可支持非常大的單個文件容量（TB級），但鑒于海量數(shù)據(jù)查詢系統(tǒng)無法避免對數(shù)據(jù)進(jìn)行全量或局部檢索，因此在本文所設(shè)計的查詢系統(tǒng)中不適于采用單個或數(shù)個大文件（GB級及以上）存儲被導(dǎo)人數(shù)據(jù)，通過減小單個數(shù)據(jù)文件大小以達(dá)到縮小單次文件檢索的數(shù)據(jù)量的目的。

基于此原因，在將數(shù)據(jù)導(dǎo)人該查詢系統(tǒng)時，需要對待查數(shù)據(jù)分文件進(jìn)行管理，即進(jìn)行文件切片操作，以嚴(yán)格控制單個文件的大小以及文件個數(shù)，用于存儲數(shù)據(jù)的文件結(jié)構(gòu)大致如下圖所示：

在本系統(tǒng)建立的索引中有一個指向待查數(shù)據(jù)中對應(yīng)記錄的指針，為使該指針能夠快速定位記錄位置，我們?yōu)榇閿?shù)據(jù)中的每一個記錄隱身地生成一個RowID。RowID由文件全局路徑以及行號兩部分信息組成，其形式為RowID=?；谠撔问降腞owID，在記錄定位時可以先通過文件全局路徑定位結(jié)果記錄所在的文件，再通過行號直接獲取記錄的完整信息。

2.2列式多級索引模型

本文通過對歷史數(shù)據(jù)特點(diǎn)的分析結(jié)果，建立基于分布式文件系統(tǒng)的全屬性列式多級索引模型。本節(jié)從全屬性列式索引和多級索引兩個角度描述索引模型。

在海量格式化數(shù)據(jù)的環(huán)境下，數(shù)據(jù)往往具有較多的屬性，各個屬性之間關(guān)系相對較弱，因此針對多個屬性的聯(lián)合索引實用價值較低。而且由于數(shù)據(jù)規(guī)模方面的原因，會導(dǎo)致聯(lián)合索引創(chuàng)建和維護(hù)成本較高。因此本課題采用單屬性索引。

在實際的查詢場景中，結(jié)構(gòu)化數(shù)據(jù)中的任意一個屬性都有作為篩選條件進(jìn)行查詢的可能性，為了滿足這一條件，本文所設(shè)計的系統(tǒng)針對數(shù)據(jù)中的所有屬性建立索引。

基于以上兩點(diǎn)原因，采用了全屬性列式索引的機(jī)制。使用這種機(jī)制可以保證在處理對任意屬性作為篩選條件的查詢請求時都可以高效的完成，并且通過分列建立索引的方法降低索引的創(chuàng)建和維護(hù)成本。