摘要：高效的元數(shù)據(jù)索引是一個(gè)重要手段，提高大容量存儲(chǔ)系統(tǒng)的性能，在時(shí)間和空間上的開銷日本性能不穩(wěn)定現(xiàn)有的元數(shù)據(jù)管理方法存在的問題，我們?cè)O(shè)計(jì)了元數(shù)據(jù)索引算法的屬性分頻器?；谠獢?shù)據(jù)的元數(shù)據(jù)屬性的訪問頻率等因素，分解的高頻率元件的數(shù)據(jù)分別存儲(chǔ)到屬性集和低頻率的元數(shù)據(jù)屬性集中，KD樹生成指數(shù)高的元數(shù)據(jù)屬性設(shè)置滿足許多條件高頻混合查詢?cè)獢?shù)據(jù)屬性的要求；人工免疫算法索引低頻率的元數(shù)據(jù)屬性設(shè)置，避免了很多額外的存儲(chǔ)空間，同時(shí)保持較高的查詢性能。該算法的原型系統(tǒng)使用兩個(gè)真實(shí)數(shù)據(jù)集上的測試和分析，結(jié)果表明，在的財(cái)產(chǎn)分頻元數(shù)據(jù)索引算法有時(shí)間和空間的開銷，適應(yīng)性強(qiáng)。

關(guān)鍵詞：元數(shù)據(jù)；云計(jì)算；索引算法

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 23-0000-02

1 引言

云計(jì)算的發(fā)展帶來了爆炸性的數(shù)據(jù)增長，這使得大容量存儲(chǔ)技術(shù)成為的重要支撐云計(jì)算的研究和開發(fā)的熱點(diǎn)之一。云計(jì)算系統(tǒng)，查詢操作的數(shù)目和所需的時(shí)間和空間上的開銷是遠(yuǎn)遠(yuǎn)大于對(duì)數(shù)據(jù)的訪問的操作，執(zhí)行查詢操作，只使用數(shù)據(jù)對(duì)應(yīng)的元數(shù)據(jù)，統(tǒng)計(jì)數(shù)據(jù)顯示，海量存儲(chǔ)系統(tǒng)中的元數(shù)據(jù)的讀分別占系統(tǒng)的75%和82%的總操作的元數(shù)據(jù)管理，高效率的算法是一個(gè)重要的手段來提高云計(jì)算系統(tǒng)的性能和寫入操作。需要比較大的存儲(chǔ)空間量數(shù)據(jù)，元數(shù)據(jù)所占份額較小的存儲(chǔ)空間，奠定了基礎(chǔ)，以實(shí)現(xiàn)高效的查詢，元數(shù)據(jù)包含多個(gè)屬性的類型和訪問頻率的差異，每個(gè)查詢的基礎(chǔ)屬性的數(shù)量，它并沒有，這使得難以提高的元數(shù)據(jù)查詢的效率。研究了海量存儲(chǔ)系統(tǒng)元數(shù)據(jù)的特性，在新的元數(shù)據(jù)索引算法的類型是非常重要的。

海量存儲(chǔ)系統(tǒng)中一般使用目錄子樹分區(qū)法、哈希法和LH等元數(shù)據(jù)管理算法。采用目錄子樹分區(qū)法時(shí)，將目錄樹按照層次和所屬關(guān)系分成若干個(gè)子樹，能減少管理元數(shù)據(jù)的復(fù)雜度；但在查詢?cè)獢?shù)據(jù)時(shí)需要逐層訪問元數(shù)據(jù)所在絕對(duì)路徑中的所有目錄，所需的時(shí)間與空間開銷較大。從而采用哈希算法管理元數(shù)據(jù)能減少查詢?cè)獢?shù)據(jù)所需的時(shí)間與空間開銷，但哈希函數(shù)的選取很困難，如哈希值的碰撞率較高會(huì)使得查詢?cè)獢?shù)據(jù)所需的時(shí)間與空間開銷急劇增加；單個(gè)哈希函數(shù)也難以適應(yīng)海量存儲(chǔ)系統(tǒng)所保存元數(shù)據(jù)的變化，造成查詢性能會(huì)出現(xiàn)較大的波動(dòng)。LH算法是目錄子樹分區(qū)法和哈希法的混合，同樣存在選取哈希函數(shù)困難的問題。Weijia Li等使用動(dòng)態(tài)哈希表實(shí)現(xiàn)多個(gè)元數(shù)據(jù)服務(wù)器之間的負(fù)載均衡。Zhu Yif}ng等使用布魯姆過濾器管理元數(shù)據(jù)，設(shè)計(jì)了HBA系統(tǒng)，使用兩級(jí)布姆過濾器索引元數(shù)據(jù)[’〕，但只能計(jì)算出元數(shù)據(jù)可能所在的分區(qū)，準(zhǔn)確性偏低。Andrew W.Leun：等設(shè)計(jì)了Spyglass；依據(jù)目錄層次關(guān)系劃分元數(shù)據(jù)，使用布魯姆過濾器確定鐮詢?cè)獢?shù)據(jù)可能所在的分區(qū)，仍然存在查詢準(zhǔn)確性較低的問題。穆飛等利用定位目錄組織元數(shù)據(jù)，用于改進(jìn)負(fù)載均衡機(jī)制的性能但存儲(chǔ)定位目錄需要較多的空間開銷。我們針對(duì)查詢和管理元數(shù)據(jù)的特點(diǎn)，依據(jù)元數(shù)據(jù)中各屬性被訪問的特性。分解元數(shù)據(jù)，分別建立索引，從而提高查詢的效率，減少索引元數(shù)據(jù)所需的時(shí)間與空間開銷。

本文的內(nèi)容組織如下：第一節(jié)中介紹了元數(shù)據(jù)屬性分頻機(jī)制，第二節(jié)給出了基于屬性分頻的元數(shù)據(jù)索引算法，在第三節(jié)從性能和效率兩方面與現(xiàn)有元數(shù)據(jù)管理算法進(jìn)行了比較與分析，第四節(jié)中構(gòu)建了算法的原型系統(tǒng)使用通用數(shù)據(jù)集進(jìn)行了測試與分析。

2 元數(shù)據(jù)屬性分頻機(jī)制

每條元數(shù)據(jù)中包含如文件名、文件標(biāo)識(shí)、創(chuàng)建時(shí)間等多個(gè)不同類型的屬性，有些屬性如文件名和文件標(biāo)識(shí)等經(jīng)常被訪問，但有些屬性如創(chuàng)建時(shí)間、修改時(shí)間和摘要等被訪問的次數(shù)較少甚至在很長時(shí)間內(nèi)都不會(huì)被訪問；如果以相同的方式索引被訪問頻率不同的屬性，一方面會(huì)因?yàn)樵獢?shù)據(jù)數(shù)量的巨大使得在查找使用頻率較高屬性時(shí)所需的時(shí)間和空間開銷較大，另一方面維護(hù)包含大量被訪問頻率較低屬性的索引需要大量的時(shí)間和空間開銷，因此對(duì)元數(shù)據(jù)中各屬性進(jìn)行區(qū)分能為提高元數(shù)據(jù)索引的效率奠定基礎(chǔ)。

我們依據(jù)元數(shù)據(jù)中各屬性被訪問頻率的不同，將元數(shù)據(jù)分解保存到高頻元數(shù)據(jù)屬性集（月材）和低頻元數(shù)據(jù)屬性集（LM）兩個(gè)集合中。

定義屬性活躍度HEN，作為區(qū)分屬性被訪問頻率高低的依據(jù)，使用公式進(jìn)行計(jì)算。

通過將元數(shù)據(jù)分解保存到高頻元數(shù)據(jù)屬性集和低頻元數(shù)據(jù)屬性集中，可減少所建立的高頻元數(shù)據(jù)屬性索引中包含的屬性數(shù)量，為提高索引的效率、同時(shí)也為降低維護(hù)索引所需的時(shí)間與空間開銷奠定了基礎(chǔ)，同時(shí)也為高效的組織和存儲(chǔ)元數(shù)據(jù)提供了基礎(chǔ)。

3 基于屬性分頻的元數(shù)據(jù)索引算法

在海量存儲(chǔ)系統(tǒng)中一般僅依據(jù)少數(shù)幾個(gè)屬性查詢?cè)獢?shù)據(jù)，因此不需要對(duì)所有屬性均建立索引。我們收集高傾屬性名集中可能被用作查詢條件的屬性名（如文件名、文件擴(kuò)及名等），構(gòu)成高頻檢索集HF={hf1，hf2，…，hfk}（kEN），hfi表示其中的一個(gè)屬性，‘表示高頻檢索集中屬性的個(gè)數(shù)；同樣構(gòu)建低頻檢索集LF={lf}，lf2}…}（nEN），slfi表示其中的一個(gè)屬性，n表示低頻檢索集中屬性的個(gè)數(shù) 高頻元數(shù)據(jù)屬性被訪問的頻率高，經(jīng)常被用于查詢海量存儲(chǔ)系統(tǒng)中的元數(shù)據(jù)，因此要求索引的查詢效率較高；低頻元數(shù)據(jù)屬性被訪問的概率較低，或者在很長時(shí)間內(nèi)不會(huì)被訪問引被使用的頻率也較低，如果索引所需的額外存儲(chǔ)空間較會(huì)浪費(fèi)較多系統(tǒng)存儲(chǔ)資源。我們分別使用KD-tree和人工免疫方法建立高頻元數(shù)據(jù)屬性集和低頻元數(shù)據(jù)屬性集的索引。

4 性能分析

我們依據(jù)元數(shù)據(jù)中不同屬性的被訪問頻率等特性，將元數(shù)據(jù)分解到高頻元數(shù)據(jù)屬性集和低頻元數(shù)據(jù)屬性集中，分別使用KD-tree和人工免疫算法建立了索引，能提高查詢?cè)獢?shù)據(jù)的效率，減少索引元數(shù)據(jù)所需的額外時(shí)空開銷。我們分別從性能和適應(yīng)能力兩方面進(jìn)行分析。于

4.1 元數(shù)據(jù)索引的性能

目錄子樹分區(qū)法將目錄樹劃分為若干子樹，縮小了查詢?cè)獢?shù)據(jù)時(shí)需訪問的目錄樹范日，但仍需要遍歷訪問路徑中的各級(jí)目錄；訪問路徑中各目錄可能會(huì)包含大量的屬性，雖然其中一些并不會(huì)被訪問，但在遍歷目錄時(shí)仍需要被軟人內(nèi)存會(huì)浪費(fèi)大量的內(nèi)存空間和調(diào)人的時(shí)間開銷。

哈希法中使用元數(shù)據(jù)的唯一標(biāo)識(shí)如訪間路徑等計(jì)算哈希值，確定所在的位置，所需的時(shí)間和空間開銷??；但選擇一個(gè)合適的哈希函數(shù)非常困難，如計(jì)算出的哈希值碰撞率較高，會(huì)出現(xiàn)時(shí)間與空間開銷急劇增加的問題；隨著系統(tǒng)所存儲(chǔ)數(shù)據(jù)量的增加，會(huì)導(dǎo)致時(shí)間和空間開銷的增加。

基于屬性分頻元數(shù)據(jù)索引算法中，我們首先依據(jù)元數(shù)據(jù)中不同屬性的被訪問頻率等特性，對(duì)元數(shù)據(jù)進(jìn)行分解，經(jīng)常被訪問的屬性值存儲(chǔ)在高頻元數(shù)據(jù)屬性集中，不經(jīng)常被訪問的屬性存儲(chǔ)在低頻元數(shù)據(jù)屬性集中。

4.2 適應(yīng)性分析

目錄子樹分區(qū)法難以保證各目錄子樹數(shù)據(jù)量的均衡，元數(shù)據(jù)的改變也會(huì)導(dǎo)致和加劇目錄子樹間數(shù)據(jù)量的不均衡，使得查找元數(shù)據(jù)所需時(shí)間與空間開銷出現(xiàn)較大波動(dòng)的問題。使用哈希法時(shí)元數(shù)據(jù)的不斷變化會(huì)影響哈希值的碰撞率，造成查詢?cè)獢?shù)據(jù)所需時(shí)間與空間開銷的波動(dòng)，修改哈希函數(shù)后元數(shù)據(jù)的重新組織則需要大量的時(shí)間與空間開銷。

5 結(jié)論

海量存儲(chǔ)系統(tǒng)是云計(jì)算的重要組成部分，元數(shù)據(jù)操作占海量存儲(chǔ)系統(tǒng)中總操作數(shù)量的一半以上，因此高效的元數(shù)據(jù)索引算法是提高海量存儲(chǔ)系統(tǒng)性能的重要手段。我們?cè)诜治鲈獢?shù)據(jù)中不同屬性被訪問頻率等因素的基礎(chǔ)上，將元數(shù)據(jù)分解存儲(chǔ)到高頻元數(shù)據(jù)屬性集和低頻元數(shù)據(jù)屬性集中，為建高效的元數(shù)據(jù)索引提供了基礎(chǔ)；針對(duì)高頻元數(shù)據(jù)屬性和低頻元數(shù)據(jù)屬性的不同特性，使川KD-tree建立高頻元數(shù)據(jù)屬性集的索引，滿足高效和多屬性組合查詢的要求；使用人工免咬算法建立低頻元數(shù)據(jù)屬性集的索引，在保持較高查找性能的同時(shí)，避免了大量額外的索引存儲(chǔ)空間；從元數(shù)據(jù)索引算法的性能和適應(yīng)兩方面進(jìn)行了分析與比較，并使用兩個(gè)真實(shí)數(shù)招集進(jìn)行了測試，驗(yàn)證了基于屬性分頻元數(shù)據(jù)索引算法具有時(shí)間空間開銷小、性能穩(wěn)定等特性。

我們?cè)谠獢?shù)據(jù)屬性分頻時(shí)，主要還是依靠經(jīng)驗(yàn)和測試數(shù)據(jù)設(shè)置活躍度闌值，缺乏調(diào)竹機(jī)制；下一步我們準(zhǔn)備研究元數(shù)據(jù)屬性的動(dòng)態(tài)分頻策略，根據(jù)海量存儲(chǔ)系統(tǒng)運(yùn)行情況動(dòng)態(tài)調(diào)整屬性的分頻，進(jìn)一步提高算法的適應(yīng)能力。

參考文獻(xiàn)：

[1]肖晨，武東英，郭紹忠，陳新.一種基于XML的CMS元數(shù)據(jù)索引算法[J].計(jì)算機(jī)工程，2007，07.

[作者簡介]劉艷青.山西農(nóng)業(yè)大學(xué)信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)技科信091班。