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

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

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

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

中圖分類號(hào)：TP314 文獻(xiàn)標(biāo)識(shí)碼：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ù)，其中包含了大量有價(jià)值的信息要素，目前該類數(shù)據(jù)主要采用文件系統(tǒng)存儲(chǔ)，當(dāng)前大數(shù)據(jù)技術(shù)僅支持對(duì)分布式文件系統(tǒng)中的數(shù)據(jù)進(jìn)行全量處理，而數(shù)據(jù)調(diào)研分析是制定海量數(shù)據(jù)處理流程的前提，當(dāng)前技術(shù)無法有效支撐數(shù)據(jù)調(diào)研階段內(nèi)容分析。針對(duì)這一問題，本文設(shè)計(jì)了較為完善的數(shù)據(jù)查詢系統(tǒng)，通過建立合理的索引、數(shù)據(jù)模型為分布式文件系統(tǒng)構(gòu)建高效內(nèi)存查詢功能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2列式多級(jí)索引模型

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

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

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

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