第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp .20XX 年X 月 JOURNAL OF CO

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp .

20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

海量結(jié)構(gòu)化數(shù)據(jù)存儲檢索系統(tǒng)

吳廣君1 王樹鵬1 陳明2 李超3

1(中國科學(xué)院計算技術(shù)研究所 北京 100190)

2(北京郵電大學(xué) 100786)

3(國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 北京100029) ;

摘要 Big Data 是近年在云計算領(lǐng)域中出現(xiàn)的一種新型數(shù)據(jù)管理模式，具有存儲數(shù)據(jù)量大、檢索效率高等需求特點。傳統(tǒng)關(guān)系型數(shù)據(jù)庫系統(tǒng)在數(shù)據(jù)存儲規(guī)模、檢索效率等方面不再適用。目前的分布式No-SQL 數(shù)據(jù)庫可以提供分布式數(shù)據(jù)存儲環(huán)境，但是無法支持多屬性檢索、數(shù)值統(tǒng)計等復(fù)雜查詢功能。本文結(jié)合Hadoop 框架，設(shè)計并實現(xiàn)分布式海量結(jié)構(gòu)化數(shù)據(jù)存儲檢索系統(tǒng)（MDSS ）。系統(tǒng)采用列存儲結(jié)構(gòu)，結(jié)合全文索引技術(shù)和分布式B Tree 索引技術(shù)管理結(jié)構(gòu)化數(shù)據(jù)源。在此基礎(chǔ)上討論復(fù)雜查詢條件的查詢?nèi)蝿?wù)分解機制，支持大數(shù)據(jù)的多屬性檢索、模糊檢索以及統(tǒng)計、分析等查詢功能。MDSS 可以有效解決海量結(jié)構(gòu)化流數(shù)據(jù)存儲與數(shù)據(jù)多屬性檢索等問題。實驗結(jié)果表明，本文提出的分布式結(jié)構(gòu)化數(shù)據(jù)管理技術(shù)和查詢?nèi)蝿?wù)分解機制可以顯著提高分布式條件下大數(shù)據(jù)集的查詢效率，適合應(yīng)用在日志類數(shù)據(jù)，流記錄數(shù)據(jù)等海量結(jié)構(gòu)化數(shù)據(jù)的存儲應(yīng)用場合，并為進一步研究云存儲中“大數(shù)據(jù)”的存儲，檢索等相關(guān)問題提供理論和實驗基礎(chǔ)。

關(guān)鍵詞 Big data; Hadoop ；數(shù)據(jù)檢索；No-SQL 數(shù)據(jù)庫; 海量數(shù)據(jù)存儲

中圖法分類號 TP393

Massive Structured Data Oriented Storage and Retrieve System

WU guang-jun1 WANG shu-peng 1 CHEN ming2 LI chao3

1(Institute of Computing Technology Chinese Academy of Sciences, BeiJing, 100190)

2（BeiJing University of Posts and Telecommunications,BeiJing,100786）

3(National Computer network Emergency Response technical Team/Coordination Center of China, Beijing, 100029)

Abstract Big Data has emerged as a new type of data in the cloud computing. It stores large amounts of data with high query efficiency. The traditional RDBMS is no longer fit to manage Big Data in face of the large storage size and high query efficiency. Currently, the No-SQL(Not Only SQL) DB can provide distributed storage environment, but it is in the limitation of query capability. We design and implement distributed Massive Data Storage System (MDSS) for structured data based on Hadoop. MDSS adopt column-based storage structure and use full-text indexing and distributed B tree to manage data source. The query planning mechanism was built for multi-attributes query, fuzzy query and data statistics query based on MDSS. MDSS can resolve query capability problems for massive structured data storage. The experiment results exposed that the techniques for distributed structured data and query planning methods can improve Big Data query efficiency significantly. MDSS is suitable to manage massive structured data, such as log-structured data, streaming data etc. and the most important is that MDSS provide valuable knowledge for further research on the storage and retrieve techniques for massive structured data in cloud storage.

Key words：Big Data; Hadoop; Data Query; No-SQL DB; Massive Storage

投稿日期: 2011-07-17；修改日期:

基金項目：國家自然科學(xué)基金項目 (61003260)；“八六三”高技術(shù)研究發(fā)展計劃項目（863計劃）(2009AA01A403, 2007AA010501, 2007AA01Z467, 2007AA01Z474) 。

Foundation Items: The National Natural Science Foundation of China(61003260);The National High Technology Research and Development Program of China(863 Program)(2009AA01A403, 2007AA010501, 2007AA01Z467, 2007AA01Z474).

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

1引言

Big Data 是近年在云計算領(lǐng)域提出的對數(shù)據(jù)的加載效率、存儲規(guī)模以及數(shù)據(jù)的檢索效率有很高要求的應(yīng)用場合，通常數(shù)據(jù)的加載效率在Mb/s甚至Gb/s量級，數(shù)據(jù)的存儲規(guī)模在TB 甚至PB 規(guī)模，本文稱這種模式為“大數(shù)據(jù)集”管理。大數(shù)據(jù)集的一類重要應(yīng)用針對結(jié)構(gòu)化數(shù)據(jù)的存儲與檢索。典型的應(yīng)用如海量日志、網(wǎng)絡(luò)報文以及web2.0框架下的SNS ，電子商務(wù)，數(shù)據(jù)挖掘等應(yīng)用場合。傳統(tǒng)的RDBMS 由于數(shù)據(jù)一致性的約束，在管理大規(guī)模數(shù)據(jù)集存儲條件下，在數(shù)據(jù)更新、局部數(shù)據(jù)失效以及系統(tǒng)擴展性等方面工作效率低下[1][2]。目前的解決思路是：通過放寬對于數(shù)據(jù)一致性的要求，取消復(fù)雜的關(guān)聯(lián)查詢，結(jié)合具體的應(yīng)用場景，提高系統(tǒng)的可用性。但是由于大量的記錄存放于同一個表空間中，會達到數(shù)十億條甚至上百億條記錄的規(guī)模。在如此大規(guī)模數(shù)據(jù)存儲條件下，如何高效的實現(xiàn)數(shù)據(jù)的存儲、檢索都面臨著新的挑戰(zhàn)。

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

加載機集群：整個系統(tǒng)的數(shù)據(jù)加載端?？梢砸赃M程為單位，在多臺設(shè)備上同時建立多個并發(fā)數(shù)據(jù)加載客戶端，通過并發(fā)加載提高系統(tǒng)整體加載效率。在MDSS 中，加載機集群同時緩存近期入庫的數(shù)據(jù)，經(jīng)過固定的時間周期，把緩存數(shù)據(jù)通過Gb Ethernet 寫到數(shù)據(jù)存儲管理裝置中。

查詢機集群：用戶在查詢機上發(fā)出查詢指令，查詢機根據(jù)元數(shù)據(jù)節(jié)點集群保存的元數(shù)據(jù)信息，向存儲節(jié)點分發(fā)查詢?nèi)蝿?wù)，最后匯總多個存儲節(jié)點返回的查詢結(jié)果，提交給用戶；

存儲節(jié)點集群：持久存儲長期保存的歷史數(shù)據(jù)。把數(shù)據(jù)源進行分塊存儲，通常把一次或幾次從加載機刷新到集群中的數(shù)據(jù)作為數(shù)據(jù)分塊。

元數(shù)據(jù)節(jié)點集群：用來協(xié)調(diào)整個集群的工作，查詢子任務(wù)的并發(fā)執(zhí)行，保存整個系統(tǒng)工作所需的元數(shù)據(jù)信息。元數(shù)據(jù)節(jié)點集群存儲的元數(shù)據(jù)包括：系統(tǒng)節(jié)點狀態(tài)信息；索引分片具體的存儲位置信息；表空間元數(shù)據(jù)、每個表空間的一些輔助信息以及系統(tǒng)的工作日志等。MDSS 系統(tǒng)主要支持分布式的數(shù)據(jù)存儲和檢索，具體數(shù)據(jù)查詢流程如圖2所示。

圖2 MDSS系統(tǒng)檢索工作原理示意圖

①用戶在查詢機上提交查詢請求；

②查詢機根據(jù)具體的查詢?nèi)蝿?wù)，向元數(shù)據(jù)節(jié)點查詢對應(yīng)表空間元數(shù)據(jù)和檢索所需的元數(shù)據(jù)信息；

③元數(shù)據(jù)節(jié)點集群根據(jù)查詢條件，提供檢索所需的元數(shù)據(jù)，例如：對應(yīng)的表空間結(jié)構(gòu)數(shù)據(jù)，索引分塊與節(jié)點的映射關(guān)系等；

④查詢機根據(jù)元數(shù)據(jù)信息，建立查詢規(guī)劃，決定向哪些存儲節(jié)點發(fā)送查詢命令。某些查詢可以利用元數(shù)據(jù)信息優(yōu)化查詢過程。由于加載機會緩存有近期的數(shù)據(jù)，針對近期數(shù)據(jù)的查詢會發(fā)送到加載機；

⑤數(shù)據(jù)存儲節(jié)點根據(jù)檢索條件，檢索符合條件的數(shù)據(jù)集，并發(fā)回給查詢機，查詢機對查詢結(jié)果進行最后的匯總、統(tǒng)計，以及必要的后期數(shù)據(jù)處理工作；

⑥查詢機對結(jié)果集按照用戶指定的格式封裝，返回給查詢用戶，完成一次完整的數(shù)據(jù)查詢過程。

在上述檢索過程，涉及兩個核心的問題是：存儲系統(tǒng)采用何種數(shù)據(jù)存儲模型以及針對復(fù)雜查詢條件的具體的任務(wù)分解方法，下面分別在第3部分介紹MDSS 采用的數(shù)據(jù)模型；在第4部分介紹復(fù)雜查詢條件的任務(wù)分解機制。

3

MDSS 中數(shù)據(jù)模型與存儲結(jié)構(gòu)

3.1數(shù)據(jù)模型

MDSS 為用戶提供二維表空間數(shù)據(jù)管理模型。一行代表一條記錄，每行內(nèi)包含多個字段或?qū)傩?。表空間利用表結(jié)構(gòu)描述字段類型。目前表結(jié)構(gòu)支持的數(shù)據(jù)類型包括：INTEGER(或INT) ，IPFIELD ，INDEX ，TIMESTAMP 和STORE 五種數(shù)據(jù)類型。INTEGER 是整數(shù)類型，支持大于，小于，等于數(shù)學(xué)比較運算；支持SUM ，AVG ，MAX ，MIN 等統(tǒng)計運算。IPFIELD 存儲IP 類型字段，支持子網(wǎng)查詢，區(qū)間查詢；進一步分為IPV4_ADDR和IPV6_ADDR兩種數(shù)據(jù)格式，分別用來保存IPV4的地址和IPV6的地址。INDEX 存儲字符類數(shù)據(jù)源，支持精確匹配，模糊匹配等查找規(guī)則。TIMESTAMP 存儲時間類型字段，支持精確查找。STORE 直接存儲數(shù)據(jù)，不支持基于內(nèi)容的查詢，通常存儲BLOB 類型數(shù)據(jù)源。

數(shù)據(jù)類型由表結(jié)構(gòu)元數(shù)據(jù)文件描述。表結(jié)構(gòu)文件在創(chuàng)建表空間時生成，保持到元數(shù)據(jù)節(jié)點集群中。針對一條DNS 訪問記錄，創(chuàng)建的表空間以及使用的語句如下；

CREATE TABLE DNS_TABLE (DOMAIN INDEX, VALUE IPFIELD, COUNT INTEGER, TIME TIMESTAMP);

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

其中：DOMAIN 字段是INDEX 類型，記錄域名字符串數(shù)據(jù)；VALUE 記錄域名對應(yīng)的IP 地址，使用IPFIELD 字段；COUNT 記錄一段時間內(nèi)域名被解析總的次數(shù)，采用整數(shù)表示；TIME 表示記錄產(chǎn)生的時間戳，使用定長的字符串表示。向DNS_TABLE表空間加載一條記錄可以使用如下命令：

INSERT

INTO

DNS_TABLE

VALUES

(‘www.xx.com’,‘192.16.18.10’,‘10’, ‘20110628101010’);

在數(shù)據(jù)加載過程中，需要根據(jù)存儲的表結(jié)構(gòu)進行字段類型的判斷，符合表結(jié)構(gòu)的字段類型加載到數(shù)據(jù)庫中，否則提示錯誤信息，直接返回。

圖3基本數(shù)據(jù)模型

MDSS 支持的基本功能如表1所示，目前MDSS 不支持UPDATE 操作。

表1 MDSS基本操作方法描述

3.2數(shù)據(jù)存儲組織結(jié)構(gòu)

數(shù)據(jù)存儲格式主要分為兩種類型：STORE 類型和字符類型。STORE 類型直接存儲文件信息，對數(shù)據(jù)內(nèi)容的解析由用戶完成。字符類型存儲方式把數(shù)據(jù)源以字符方式分塊存儲。字符存儲方式可以在異構(gòu)存儲環(huán)境中自由的遷移，具有更大的靈活性。字符類型可以處理數(shù)據(jù)類型包括：INDEX ，IPFIELD ，TIMESTAMP 以及INTEGER 等，在數(shù)據(jù)加載時根據(jù)表結(jié)構(gòu)定義的數(shù)據(jù)類型進行數(shù)據(jù)轉(zhuǎn)換。比如整數(shù)10在字符類型中需要存儲00000010。這部分的轉(zhuǎn)換工作在加載機上實現(xiàn)。

數(shù)據(jù)在存儲節(jié)點上采用列存儲結(jié)構(gòu)，把字段值按照字典序排序存儲，不同字段分別保存到文件的不同位置，一定長度的數(shù)據(jù)作為一個單獨的文件保存，稱為索引分片，索引分片是并發(fā)檢索和分布存儲的基本單位，目前通常以加載機一次或幾次刷新到集群中的數(shù)據(jù)源作為一個索引分片單位。

在每個索引分片內(nèi)部引入塊內(nèi)索引，用來標記索引分塊內(nèi)部不同字段屬性數(shù)據(jù)的具體存儲位置。索引塊的大小通常使用固定大小空間存儲，便于一次性加載到內(nèi)存中進行數(shù)據(jù)統(tǒng)計，目前是4K 大小。索引分片在存儲節(jié)點上采用gzip 壓縮算法進行數(shù)據(jù)壓縮，由于內(nèi)容相同的字段根據(jù)字典序排序后相鄰存儲，因此引入壓縮技術(shù)會顯著提高數(shù)據(jù)的存儲效率。

在日志、流記錄等應(yīng)用場合，時間屬性是最常

用的檢索屬性，MDSS 采用時間屬性對數(shù)據(jù)進行分區(qū)管理，索引分片之間保持時間有序。同時建立基于時間屬性的分布式B Tree，加快分區(qū)數(shù)據(jù)的檢索過程。B Tree的葉節(jié)點保存每個索引分片對應(yīng)的最大時間屬性和索引分片的存儲節(jié)點的位置。分布式B Tree保存在元數(shù)據(jù)節(jié)點集群中。具體結(jié)構(gòu)如圖4所示。

圖4 數(shù)據(jù)組織結(jié)構(gòu)圖

分布式存儲系統(tǒng)都面臨著數(shù)據(jù)容錯，負載均衡等問題。MDSS 利用副本實現(xiàn)數(shù)據(jù)容錯功能，在數(shù)據(jù)加載時進行數(shù)據(jù)負載均衡處理。元數(shù)據(jù)節(jié)點集群基于zookeeper 建立，根據(jù)zookeeper 配置規(guī)則，實

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

現(xiàn)元數(shù)據(jù)容錯以及節(jié)點失效處理，此處不再詳細介紹。

索引分片數(shù)據(jù)作為基本的調(diào)度和計算單位，持久存儲到存儲節(jié)點上。當數(shù)據(jù)從加載機刷新到存儲節(jié)點集群時，根據(jù)設(shè)置的副本冗余度和集群存儲節(jié)點列表，按序選擇可用的存儲節(jié)點，寫入數(shù)據(jù)。當設(shè)置副本冗余度時，加載機會選擇不同的節(jié)點分別寫入數(shù)據(jù)。

在數(shù)據(jù)檢索時，一個索引分片檢索結(jié)果如果超過返回時間限制，可以選擇對應(yīng)的索引分片的副本重新執(zhí)行檢索操作，實現(xiàn)數(shù)據(jù)容錯功能。限于篇幅，關(guān)于數(shù)據(jù)詳細的組織方式不再詳述。

4. MDSS數(shù)據(jù)檢索方法

MDSS 執(zhí)行復(fù)雜查詢條件的基本原則是對查詢條件劃分成查詢子任務(wù)，每個子任務(wù)在分布式環(huán)境下的不同層次上并發(fā)實現(xiàn)。查詢條件的分解和查詢子任務(wù)的劃分，既要保證查詢語義的正確性，同時需要充分考慮分布式環(huán)境下影響數(shù)據(jù)檢索的多種因素，充分發(fā)揮分布式環(huán)境下并發(fā)、并行的計算能力。

4.1查詢條件分解

為了支持二維表空間的相關(guān)操作，實現(xiàn)結(jié)構(gòu)化數(shù)據(jù)的統(tǒng)計與檢索，MDSS 設(shè)計了一種針對單表空間內(nèi)面向流記錄的數(shù)據(jù)統(tǒng)計與分析語言，語法規(guī)則與標準的SQL 相同，但是取消了標準SQL 中關(guān)聯(lián)查詢，嵌套查詢，視圖等復(fù)雜的檢索功能，本文簡稱為MQL 語言，具體支持的查詢功能如下：

表2 MQL支持的基本功能

具體的查詢?nèi)蝿?wù)可以是由上述多種子查詢語句構(gòu)成的具體查詢條件，為了快速執(zhí)行相對復(fù)雜的查詢計劃，MDSS 把具體的查詢條件分解為三類基本條件，每類基本條件作為一類查詢子任務(wù)。

分區(qū)查詢條件：分區(qū)查詢條件直接定位于滿足查詢條件的目標索引文件，大大縮小海量數(shù)據(jù)的查詢范圍。是最先執(zhí)行的查詢條件。這類條件的特點是每個表空間只能設(shè)置一種分區(qū)查詢條件，相當于關(guān)系型數(shù)據(jù)庫的聚簇索引。MDSS 選擇時間屬性作為分區(qū)查詢條件；

過濾查詢條件：結(jié)構(gòu)化數(shù)據(jù)每條記錄由多個字段組成，每個字段可以獨立設(shè)置查詢條件。字符類屬性支持模糊查詢，數(shù)字類的支持比較查詢等。多個過濾查詢條件之間通過邏輯運算符號AND OR NOT 進行連接，構(gòu)成多個邏輯組合查詢條件。AND OR NOT之間滿足基本的集合運算關(guān)系；

統(tǒng)計分析查詢條件：統(tǒng)計分析類查詢條件主要用于經(jīng)過分區(qū)查詢條件、過濾查詢條件后返回的結(jié)果集，實現(xiàn)面向全局數(shù)據(jù)集的統(tǒng)計、分析操作。具體的查詢條件包括：數(shù)據(jù)分組操作（GROUP BY ），數(shù)據(jù)排序操作（ORDER BY ），TOP-K ，以及統(tǒng)計函數(shù)，如SUM ，AVG ，MAX ，MIN 等。這類條件的特點是需要建立在獲得全部符合條件的數(shù)據(jù)集基礎(chǔ)上實現(xiàn)的數(shù)據(jù)統(tǒng)計、分析后獲得正確結(jié)果。具體查詢?nèi)蝿?wù)的分解流程如下圖所示。

圖5 查詢條件分解流程

4.2查詢子任務(wù)的并發(fā)執(zhí)行與數(shù)據(jù)匯總

在分布式環(huán)境下，可以把一個具體的復(fù)雜查詢?nèi)蝿?wù)按照上述分類方法分解成三類基本查詢條件，每類查詢條件對應(yīng)一種查詢子任務(wù)，利用分布式環(huán)境下的不同層次執(zhí)行具體的查詢子任務(wù)。其中分區(qū)類查詢條件結(jié)合元數(shù)據(jù)信息在具體的存儲節(jié)點上進行索引文件級別的查詢；過濾類查詢條件針對目標索引文件內(nèi)的具體記錄進行過濾，這兩類條件在多數(shù)據(jù)存儲節(jié)點中并發(fā)執(zhí)行。統(tǒng)計分析類查詢條件在查詢機上，針對過濾類查詢條件返回的結(jié)果集進行匯總后再進行統(tǒng)一計算處理，保證查詢語義的正確性。

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

MDSS 采用時間屬性作為分區(qū)類檢索條件，根據(jù)檢索條件中的時間屬性可以直接檢索到符合條件的目標索引分片，加速檢索過程。這一點與目前的No-SQL 數(shù)據(jù)庫不同，目前No-SQL 數(shù)據(jù)庫通常按照關(guān)鍵字進行數(shù)據(jù)塊分裂，并涉及到新老數(shù)據(jù)塊的遷移、合并等操作。MDSS 采用時間屬性作為分區(qū)條件簡化了數(shù)據(jù)管理策略，同時符合日志類數(shù)據(jù)，流數(shù)據(jù)的應(yīng)用場景。

統(tǒng)計分析類查詢條件主要針對具有分組，排序，數(shù)值分析，以及TOPK 類的檢索條件進行具體操作。這類查詢操作需要根據(jù)全部的結(jié)果集進行統(tǒng)計后才能給出正確的查詢結(jié)果。

統(tǒng)計分析類查詢條件，如分組與排序等操作主要放在查詢機上實現(xiàn)，為了加速數(shù)據(jù)分組，去重計算過程，引入Bloom Filter算法，快速判斷一條記錄是否屬于同一個分組或快速去重。

MDSS 針對部分查詢做了特殊優(yōu)化處理。比如僅對字段屬性進行簡單統(tǒng)計的分組、排序、去重等查詢，如SELECT DOMAIN ? GROUP BY(ORDER BY) DOMAIN ；SELECT DISTINCT *?，盡管具有統(tǒng)計分析函數(shù)標識，但是由于在存儲節(jié)點上進行計算不會影響最后查詢結(jié)果的正確性，MDSS 會選擇放到底層存儲節(jié)點上同過濾類查詢條件一起并行執(zhí)行。此時返回的子查詢結(jié)果集是已經(jīng)分好組、排好序或去重后的結(jié)果集，最后的數(shù)據(jù)匯總階段只做一次對應(yīng)的統(tǒng)計操作，會大大提高數(shù)據(jù)匯總階段的執(zhí)行效率。一個具體的查詢條件分層次執(zhí)行示意圖如圖6所示。

圖6 數(shù)據(jù)檢索與合并流程

不同的查詢機對應(yīng)的查詢條件，要求的響應(yīng)時間都各不相同。MDSS 主要采用兩類查詢機制滿足不同的查詢需求：在線查詢機制和離線查詢機制。

在線查詢是指對數(shù)據(jù)查詢響應(yīng)時間要求較高，在數(shù)秒甚至1秒鐘內(nèi)返回查詢結(jié)果，主要用于C/S或B/S框架下的界面展示中，用戶可以在線等待查詢結(jié)果；離線查詢是指在數(shù)據(jù)挖掘、統(tǒng)計分析等應(yīng)用場合中，要求的數(shù)據(jù)查詢模式相對復(fù)雜，有時需要針對全部數(shù)據(jù)進行統(tǒng)計、分析計算后才能得出查詢結(jié)果，一般使用定制的ETL 工具實現(xiàn)，能夠容忍較長的數(shù)據(jù)查詢響應(yīng)時間。上述兩種數(shù)據(jù)查詢機制在海量結(jié)構(gòu)化數(shù)據(jù)管理系統(tǒng)中普遍存在。為了綜合考慮兩種檢索應(yīng)用背景，引入了分批返回機制，即在執(zhí)行子查詢中，設(shè)置子查詢檢索結(jié)果集的閾值，如果檢索到結(jié)果集超過閾值，返回當前的檢索結(jié)果，同時存儲節(jié)點保存當前的檢索狀態(tài)、緩存剩余的結(jié)果集以及對應(yīng)的SessionID 。在線檢索應(yīng)用中需要展現(xiàn)的結(jié)果集數(shù)據(jù)較少，一個批次可以滿足要求。當下次使用新的查詢語句建立新的查詢請求時，存儲節(jié)點會放棄緩存的信息，同時建立新的查詢請求。對于離線檢索機制，往往進行大數(shù)據(jù)量的統(tǒng)計與分析，需要建立在檢索全部結(jié)果集基礎(chǔ)上實現(xiàn)此時可以繼續(xù)使用同一個SessionID ，繼續(xù)上次的檢索操作，循環(huán)檢索，直到檢索完滿足條件的所有記錄為止。分批次異步檢索機制充分考慮了兩類檢索應(yīng)用的不同場景，目前每個批次默認設(shè)置為70萬查詢結(jié)果集，根據(jù)具體的應(yīng)用可以進行配置。

5. 實驗結(jié)果與分析

為了測試系統(tǒng)的具體性能，針對某運營商DNS 訪問記錄進行落地存儲。實驗環(huán)境為：加載機為兩個節(jié)點, 配置為AMD Opteron 2378 8核800MHz 8G內(nèi)存X 2；查詢機一個節(jié)點，配置為AMD Opteron 2378 8核800MHz 16G 內(nèi)存；元數(shù)據(jù)集群一個節(jié)點，具體配置為AMD Opteron 2378 8核800Mhz 16G 內(nèi)存。四個存儲節(jié)點，具體配置為AMD Opteron 8380 4核800MHz X 4。存儲節(jié)點加載磁盤陣列，每個節(jié)點加載5T 磁盤空間，集群提供20T 的磁盤存儲空間。

系統(tǒng)連續(xù)運行50天左右，平均每天入庫數(shù)據(jù)量4-5億條記錄，保存DNS 記錄230億條左右，占用的存儲空間14TB 。在當前數(shù)據(jù)規(guī)模條件下進行具體的實驗測試。

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

首先給出不同的檢索時間間隔對檢索效率的影響。針對2011-07-01:00:00:00到2011-07-01:24:00:00期間內(nèi)，連續(xù)24個小時的數(shù)據(jù)進行實驗分析。該時間段內(nèi)的保存的記錄數(shù)目為510335051條。具體的檢索條件包括下列條件：

? 模糊檢索條件：DOMAIN=www.*.com.cn； ? 精確匹配屬性檢索：TYPE=A； ? 分區(qū)檢索條件：TIME=T；

設(shè)檢索時間為T 為參數(shù)，當T 取不同時間間隔時，檢索效率與具體的時間關(guān)系如圖7所示。

從圖示可以看出檢索效率基本上與檢索條件的時間間隔成線性增長。在數(shù)據(jù)庫規(guī)模為230億記錄存儲空間為14TB 四個存儲節(jié)點條件下，對24個小時內(nèi)的數(shù)據(jù)進行多屬性檢索時，檢索時間在140s 左右返回查詢結(jié)果。該結(jié)果遠遠高于傳統(tǒng)數(shù)據(jù)庫的查詢效率。其主要時間消耗在查詢機從元數(shù)據(jù)節(jié)點查詢元數(shù)據(jù)信息以及多查詢節(jié)點間的數(shù)據(jù)通信和匯總上。

)

S ( 間時索檢時間間隔T (h)

圖7 不同檢索時間間隔對應(yīng)的檢索效率

為了進一步分析影響分布式系統(tǒng)的主要因素，分別考察返回查詢結(jié)果集數(shù)目以及檢索條件數(shù)目兩

個因素對查詢時間的影響。

圖8給出了MDSS 檢索效率與返回結(jié)果集數(shù)目的之間的關(guān)系，從圖示中可以看出，MDSS 檢索效率與返回的結(jié)果集有關(guān)。當結(jié)果集過大時，不僅傳輸數(shù)據(jù)、數(shù)據(jù)匯總占用更多的時間，在使用列存儲結(jié)構(gòu)，重構(gòu)整條原始記錄都會占用更多的時間。

圖9給出，當使用多個邏輯條件組合時，檢索條件通過OR 或AND 進行連接，檢索效率與多檢索條件個數(shù)之間的關(guān)系。通過圖示可以看出，邏輯條

件的個數(shù)增加時（實驗中增加到32個檢索條件），檢索時間基本不發(fā)生變化。主要原因是

由于過濾類檢索條件在分布式存儲節(jié)點上并發(fā)執(zhí)行, 每個節(jié)點針對具體的索引分片啟動多線程檢索，同時MDSS 索引分片采用列存結(jié)構(gòu)，適于應(yīng)用在大數(shù)據(jù)集、復(fù)雜檢索條件的分析應(yīng)用中。

結(jié)合上述兩個實驗，可以得出MDSS 具體的查詢效率主要與檢索結(jié)果集數(shù)目有關(guān)，當結(jié)果集過大，由分布式系統(tǒng)的數(shù)據(jù)通信、查詢機上的數(shù)據(jù)匯總等操作會占用較多的時間，進而導(dǎo)致系統(tǒng)檢索效率下降。對于相對復(fù)雜的檢索條件可以根據(jù)具體索引結(jié)構(gòu)、數(shù)據(jù)存儲組織方式進行具體的優(yōu)化。目前MDSS 系統(tǒng)可以有效解決多屬性數(shù)據(jù)檢索需求，而對于更復(fù)雜的關(guān)聯(lián)查詢，正在進一步的研究設(shè)計中。

)

S ( 間時索檢結(jié)果集數(shù)目

圖8 檢索效率與返回的結(jié)果集數(shù)目關(guān)系

)

S ( 間時索檢條件個數(shù)

圖9 檢索效率與過濾類檢索條件的關(guān)系

第 卷 計 算 機 研 究 與 發(fā) 展 Vol. , Supp . 20XX 年X 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT

6結(jié)束語

本文結(jié)合了傳統(tǒng)關(guān)系型數(shù)據(jù)庫設(shè)計思想并借鑒了云存儲中常用的數(shù)據(jù)管理方式，建立面向結(jié)構(gòu)化數(shù)據(jù)的海量數(shù)據(jù)存儲檢索系統(tǒng)。系統(tǒng)支持結(jié)構(gòu)化數(shù)據(jù)的高效加載、分布存儲與復(fù)雜條件的查詢功能。在具體設(shè)計、開發(fā)過程中得到如下的經(jīng)驗和結(jié)論： （1）結(jié)合具體的應(yīng)用，綜合利用分區(qū)索引條件、列存儲結(jié)構(gòu)等技術(shù)，會顯著提高海量結(jié)構(gòu)化數(shù)據(jù)的查詢效率；

（2）充分利用、挖掘分布式環(huán)境下的并發(fā)、并行計算能力，是提高面向大數(shù)據(jù)集、復(fù)雜查詢條件查詢效率的主要途徑。

MDSS 系統(tǒng)在查詢效率方面有待進一步改進主要的改進方向包括，如何提高元數(shù)據(jù)的管理、訪問效率；如何建立分布式環(huán)境下面向復(fù)雜條件的高效查詢規(guī)劃，減少中間結(jié)果集的傳遞、結(jié)果集匯總等時間消耗，都是進一步提高系統(tǒng)查詢效率的主要方面。

參 考 文 獻

[1] Bernstein, P.A., and Goodman, N. An algorithm for

concurrency control and recovery in replicated distributed databases. ACM Trans. on Database Systems, 9(4):596-615

[2] Lindsay, B.G., et. al., “Notes on Distributed

Databases”, Research Report RJ2571(33471), IBM Research, July 1979

[3] Chang, F., et al., Bigtable: A distributed storage

system for structured data. Acm Transactions on Computer Systems, 2008. 26(2)

[4] DeCandia, G ., et al., Dynamo: amazon's highly

available key-value store, in Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles. ACM: Stevenson, Washington, USA, 2007:205-220

[5] Lakshman, A. and P. Malik, Cassandra: a

decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010, 44 (2): 35-40.

[6] Cooper, B.F., et al. PNUTS: Yahoo!'s hosted data

serving platform. in Proceedings of the VLDB Endowment, 2008: 1277-1288 [7] [8] http://hypertable.org/

[9] Chen, G ., et al. A Framework for Supporting

DBMS-like Indexes. in Very Large Data Bases (VLDB), Seatle, WA. 2011

吳廣君（1981-），男，遼寧省遼陽人，博士，中國科學(xué)院計算技術(shù)研究所 助理研究員，主要研究方向：海量數(shù)據(jù)存儲，數(shù)據(jù)容災(zāi)，信息安全。

王樹鵬（1980-），男，山東省濟南人，博士，中國科學(xué)院計算技術(shù)研究所 助理研究員，主要研究方向：海量數(shù)據(jù)存儲與安全、數(shù)據(jù)災(zāi)備。

陳明 (1983-)，男，河南駐馬店人，博士研究生，主要研究方向: 重復(fù)數(shù)據(jù)刪除、信息安全。

李超，男，1982年生，博士研究生，主要研究方向為信息安全。