黃 斌，彭宇行

(1.貴州師范大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550001；2.武漢大學(xué)計算機(jī)學(xué)院，湖北 武漢 430072；3.國防科學(xué)技術(shù)大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073)

云計算環(huán)境中高效可擴(kuò)展的元數(shù)據(jù)管理方法*

黃 斌1,2，彭宇行3

(1.貴州師范大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550001；2.武漢大學(xué)計算機(jī)學(xué)院，湖北 武漢 430072；3.國防科學(xué)技術(shù)大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073)

針對現(xiàn)有可擴(kuò)展的元數(shù)據(jù)管理方法存在性能較低問題，提出一種高效可擴(kuò)展的元數(shù)據(jù)管理方法，它首先采用動態(tài)二叉映射樹來實現(xiàn)元數(shù)據(jù)服務(wù)器精確定位，然后采用延遲更新方法來動態(tài)更新二叉映射樹，最后提出動態(tài)K叉編碼樹的元數(shù)據(jù)組織方法以提高元數(shù)據(jù)服務(wù)器擴(kuò)展時選擇遷移元數(shù)據(jù)的速度。實驗結(jié)果表明，它有效提高了云計算環(huán)境中可擴(kuò)展元數(shù)據(jù)管理方法的效率。

云計算；元數(shù)據(jù)；高效；可擴(kuò)展

1 引言

隨著互聯(lián)網(wǎng)應(yīng)用和數(shù)據(jù)密集型計算的流行，云計算環(huán)境中出現(xiàn)了許多新的應(yīng)用系統(tǒng)。這些系統(tǒng)與傳統(tǒng)分布式系統(tǒng)的不同之處是：系統(tǒng)中存儲的文件數(shù)量巨大，有的甚至將要達(dá)到萬億(Trillions)級別[1～3]，并且還在以較快速度增加。據(jù)統(tǒng)計：截止2011年2月，F(xiàn)acebook[4]存有600億張照片，Photobucket[5]存有90億張照片，谷歌的Picasa[6]存有70億張照片，F(xiàn)lickr[7]存有60億張照片，并且這些系統(tǒng)中的文件數(shù)量增長非常迅速(如Facebook目前每天有上億張圖片上傳，Photobucket目前每天有400萬張圖片上傳)，因此不久的將來系統(tǒng)中的文件數(shù)將達(dá)到萬億級別[3]。一些地理信息系統(tǒng)存儲了數(shù)十億張衛(wèi)星照片[3]，如美國的巡天項目(LSST)[8]目前存有9×1019張圖片。如此海量的文件數(shù)導(dǎo)致可擴(kuò)展性成為存儲系統(tǒng)有效應(yīng)用的一個瓶頸。元數(shù)據(jù)方式是實現(xiàn)海量存儲系統(tǒng)的一種重要方法。云計算系統(tǒng)的海量文件造成其元數(shù)據(jù)也海量，解決的元數(shù)據(jù)可擴(kuò)展性問題也就解決了海量存儲系統(tǒng)的可擴(kuò)展性問題，因此元數(shù)據(jù)的有效管理成為解決云計算環(huán)境中海量文件可擴(kuò)展存儲的關(guān)鍵技術(shù)。

現(xiàn)有的元數(shù)據(jù)管理方法分為查表法、子樹分割法、靜態(tài)哈希法和可擴(kuò)展哈希法。查表法[9～11]在云計算系統(tǒng)中的典型應(yīng)用是Google使用的單元數(shù)據(jù)服務(wù)器MDS(Meta Data Server)方法。該方法將元數(shù)據(jù)以表格形式存儲在一臺服務(wù)器的內(nèi)存中，適合文件數(shù)量不多的存儲系統(tǒng)，其擴(kuò)展能力不強(qiáng)，不適合文件數(shù)海量且快速增長的存儲系統(tǒng)。子樹分割法[12～16]將存儲系統(tǒng)全局唯一的名字空間按照目錄層次分割為獨立的子樹，元數(shù)據(jù)服務(wù)器集群中的每個元數(shù)據(jù)服務(wù)器負(fù)責(zé)管理其中的一個或多個子樹。該方法可擴(kuò)展性較好，但由于目錄分布在多臺元數(shù)據(jù)服務(wù)器中，需要跨多臺元數(shù)據(jù)服務(wù)器進(jìn)行目錄遍歷來定位文件的元數(shù)據(jù)，導(dǎo)致訪問效率低效。靜態(tài)哈希法[17～25]是對文件標(biāo)識符(如文件全路徑名)進(jìn)行哈希來定位該文件的存儲位置。該方法突破了單元數(shù)據(jù)服務(wù)器個數(shù)的限制，但它在擴(kuò)展時需要重新分布所有元數(shù)據(jù)，使得元數(shù)據(jù)服務(wù)器不能隨文件數(shù)目的增加而動態(tài)擴(kuò)展。可擴(kuò)展哈希法[1～3,26,27]把文件標(biāo)識符分成標(biāo)識元數(shù)據(jù)服務(wù)器字段和標(biāo)識服務(wù)器內(nèi)數(shù)據(jù)塊字段，通過擴(kuò)展元數(shù)據(jù)服務(wù)器字段來動態(tài)地增加元數(shù)據(jù)服務(wù)器，實現(xiàn)元數(shù)據(jù)系統(tǒng)動態(tài)可擴(kuò)展，并且擴(kuò)展時只遷移分裂元數(shù)據(jù)服務(wù)器一半左右的元數(shù)據(jù)。該方法在系統(tǒng)擴(kuò)展時需要進(jìn)行元數(shù)據(jù)遷移，其確定哪些數(shù)據(jù)遷移的速度較慢，并采用消息廣播方式定位元數(shù)據(jù)，造成系統(tǒng)服務(wù)性能較低。

針對現(xiàn)有可擴(kuò)展元數(shù)據(jù)管理方法存在性能較低問題，本文提出一種高效可擴(kuò)展的元數(shù)據(jù)管理方法，它包括精確定位可擴(kuò)展哈希方法、緩沖區(qū)延遲更新方法、高效確定遷移數(shù)據(jù)的元數(shù)據(jù)組織方法，有效解決了元數(shù)據(jù)管理高效可擴(kuò)展問題。

本文貢獻(xiàn)主要包括：(1)針對現(xiàn)有可擴(kuò)展哈希方法定位數(shù)據(jù)時采用訪問請求廣播方式，容易造成網(wǎng)絡(luò)擁擠這一問題，提出了精確定位可擴(kuò)展哈希方法，有效降低了系統(tǒng)中的通信量，提高了訪問性能；(2)針對精確定位可擴(kuò)展哈希的特點，提出了基于元數(shù)據(jù)服務(wù)器分裂日志的緩沖區(qū)延遲更新方法，把總的更新開銷分?jǐn)偟礁鱾€操作中，避免緩沖區(qū)更新操作對系統(tǒng)性能產(chǎn)生較大波動；(3)針對現(xiàn)有可擴(kuò)展哈希方法采用的元數(shù)據(jù)組織方法(如堆、線性哈希等)造成元數(shù)據(jù)服務(wù)器擴(kuò)展時，選擇遷移元數(shù)據(jù)速度慢這一問題，提出了動態(tài)K叉編碼樹元數(shù)據(jù)組織方法，有效地提高了選擇遷移元數(shù)據(jù)速度。

2 精確定位可擴(kuò)展哈希方法

可擴(kuò)展哈希能較好地支持元數(shù)據(jù)存儲系統(tǒng)動態(tài)擴(kuò)展，其原理是把文件的標(biāo)識符(記為FID)哈希成m位二進(jìn)制值hash(FID)，hash(FID)的i位前綴值a0a1…ai-1相同的文件元數(shù)據(jù)被分布到同一臺元數(shù)據(jù)服務(wù)器中(a0a1…ai-1稱為該元數(shù)據(jù)服務(wù)器的數(shù)據(jù)標(biāo)識符，i稱為數(shù)據(jù)標(biāo)識符長度)。當(dāng)數(shù)據(jù)標(biāo)識符為a0a1…ai-1的元數(shù)據(jù)服務(wù)器容量不夠時，分裂該元數(shù)據(jù)服務(wù)器，分裂規(guī)則是：將hash(FID)前綴為a0a1…ai-11元數(shù)據(jù)遷移到新增的元數(shù)據(jù)服務(wù)器中，hash(FID)前綴為a0a1…ai-10元數(shù)據(jù)仍保留在原元數(shù)據(jù)服務(wù)器中，此時前者的數(shù)據(jù)標(biāo)識符變?yōu)閍0a1…ai-11，后者的數(shù)據(jù)標(biāo)識符變?yōu)閍0a1…ai-10，兩者的數(shù)據(jù)標(biāo)識符長度增加1?？蓴U(kuò)展哈希原理如圖1所示。

Figure 1 Extensible hash圖1 可擴(kuò)展哈希

訪問一個文件元數(shù)據(jù)時,把文件的標(biāo)識符(FID)哈希成m位二進(jìn)制值hash(FID)，把訪問請求廣播到所有元數(shù)據(jù)服務(wù)器中，元數(shù)據(jù)服務(wù)器依據(jù)它的數(shù)據(jù)標(biāo)識符長度i，取hash(FID)前i位值a0a1…ai-1與元數(shù)據(jù)服務(wù)器的數(shù)據(jù)標(biāo)識符進(jìn)行比對，如兩者相同，說明要訪問的元數(shù)據(jù)在該元數(shù)據(jù)服務(wù)器中，則做進(jìn)一步訪問，否則忽略該訪問請求。

Figure 2 Extensible hash with precise location圖2 精確定位可擴(kuò)展哈希

在數(shù)據(jù)訪問時，傳統(tǒng)的可擴(kuò)展哈希需要把訪問請求廣播到所有存儲節(jié)點中，造成網(wǎng)絡(luò)擁擠，因而影響系統(tǒng)性能。針對這一問題，我們提出精確定位可擴(kuò)展哈希方法(如圖2所示)，它在可擴(kuò)展哈希中引入動態(tài)二叉映射樹來實現(xiàn)訪問請求的點對點通信，降低通信量，提高訪問性能。

動態(tài)二叉映射樹位于客戶端，是元數(shù)據(jù)服務(wù)器地址的一棵編碼樹，它的每個左分支代表0，右分支代表1，每個葉子節(jié)點代表一臺元數(shù)據(jù)服務(wù)器。從根節(jié)點到一個葉子節(jié)點的所有分支組成的編碼就是一臺元數(shù)據(jù)服務(wù)器的地址，對應(yīng)于一個葉子節(jié)點的編號。在數(shù)據(jù)訪問時，只需從hash(FID)第一位起，在二叉映射樹中逐位向下搜索，搜索到葉子節(jié)點，就得到數(shù)據(jù)存儲位置。

動態(tài)二叉映射樹具有如下特點：(1)動態(tài)二叉映射樹是隨著元數(shù)據(jù)服務(wù)器的分裂而動態(tài)生成的。當(dāng)一個元數(shù)據(jù)服務(wù)器a0a1…ai分裂為a0a1…ai0和a0a1…ai1時，動態(tài)二叉映射樹中對應(yīng)節(jié)點a0a1…ai也相應(yīng)地產(chǎn)生a0a1…ai0和a0a1…ai1兩個孩子節(jié)點。(2)通常元數(shù)據(jù)服務(wù)器數(shù)量較少，因此動態(tài)二叉映射樹不高，定位元數(shù)據(jù)服務(wù)器效率也就比較高。

3 延遲更新方法

當(dāng)一個元數(shù)據(jù)服務(wù)器分裂時，如果采用同步更新方法，更新操作對系統(tǒng)性能影響較大，因此我們采用延遲更新方法，把總的更新開銷分?jǐn)偟礁鱾€操作中，避免動態(tài)二叉映射樹更新操作對系統(tǒng)性能產(chǎn)生較大波動。其具體方法是：

(1)給每一個元數(shù)據(jù)服務(wù)器賦予兩個地址：物理地址和邏輯地址，物理地址在服務(wù)器生命周期內(nèi)不變，如服務(wù)器的IP地址；而邏輯地址是隨著元數(shù)據(jù)服務(wù)器分裂而改變的地址，動態(tài)二叉映射樹分支編碼構(gòu)成的地址是邏輯地址。

(2)在動態(tài)二叉映射樹中，每個葉子節(jié)點都記錄了邏輯地址到物理地址的映射關(guān)系，以方便服務(wù)器的定位。

(3)在每個元數(shù)據(jù)服務(wù)器中設(shè)計一個分裂日志，記錄該服務(wù)器的分裂歷史，它是一個二維表，它的每行記錄結(jié)構(gòu)是〈邏輯地址，物理地址〉。例如，服務(wù)器a0a1…ap經(jīng)過w次分裂后，它的分裂日志如圖3所示。分裂日志的第j行表明以a0a1…apap+j為首部的元數(shù)據(jù)存放在物理地址為IPj的元數(shù)據(jù)服務(wù)器中，其邏輯地址為a0a1…apap+j。

分裂序號物理地址a0a1…apap+1IP1??a0a1…ap+wIPw

Figure3Splittinglogofservera0a1…ap

圖3 服務(wù)器a0a1…ap的分裂日志

(4)假設(shè)一個服務(wù)器的邏輯地址為a0a1…ax,物理地址為IPm。當(dāng)一個訪問請求q(將訪問的元數(shù)據(jù)服務(wù)器邏輯地址a0a1…ai，物理地址為IPn)到達(dá)元數(shù)據(jù)服務(wù)器IPm時，如果x=i,則直接在該服務(wù)器完成操作；如果x>i，那么將訪問該節(jié)點的分裂日志，將訪問請求轉(zhuǎn)交到相應(yīng)的服務(wù)器中，并根據(jù)節(jié)點的分裂日志來更新客戶端的動態(tài)二叉映射樹。根據(jù)節(jié)點的分裂日志更新客戶端的算法為：

對服務(wù)器端：

將〈IPi, IPi+1,…,IPn〉發(fā)給流出訪問請求q的客戶端;

對客戶端:

p= a0a1…ai;

For:j從1到n

P.lchild.laddress=a0a1…ai0…0;//j 個0

P.lchild.paddress=IPm;

P.rchild.laddress=a0a1…ai1…1;//j個1

P.rchild.paddress=IPi+j-1;

P=a0a1…ai0…0;//j 個0

從算法中可以看出，在一客戶端二次訪問服務(wù)器x 期間，如果服務(wù)器x分裂w次，那么只需在該客戶端對應(yīng)的節(jié)點增加w層二叉樹，因此更新成本較低。

4 元數(shù)據(jù)組織方法

隨著元數(shù)據(jù)不斷增長，當(dāng)服務(wù)器容量不夠時，每臺元數(shù)據(jù)服務(wù)器分裂為兩臺元數(shù)據(jù)服務(wù)器(編號為a0a1…ai-1的元數(shù)據(jù)服務(wù)器分裂后編號變?yōu)閍0a1…ai-10，新增加的元數(shù)據(jù)服務(wù)器編號為a0a1…ai-11)，同時每臺元數(shù)據(jù)服務(wù)器選擇hash(FID)的ai=1的文件元數(shù)據(jù)遷移到新增的元數(shù)據(jù)服務(wù)器中，單臺服務(wù)器分裂示意圖如圖4所示，數(shù)據(jù)重分布如圖5所示。

Figure 4 Splitting of MDS a0a1…ai-1圖4 元數(shù)據(jù)服務(wù)器分裂

Figure 5 Distribution of directory metadata圖5 目錄元數(shù)據(jù)在元數(shù)據(jù)服務(wù)器的分布

隨著數(shù)據(jù)的不斷插入，服務(wù)器的分裂過程是以a0a1…ai-1為根的二叉樹，數(shù)據(jù)分裂過程也是一個二叉樹。因此，可以預(yù)先以每次分裂位的值(為0或為1)對hash(FID)構(gòu)建二叉樹索引(如圖6所示)，減少數(shù)據(jù)選擇時間。構(gòu)造二叉樹索引以后，在每次分裂時選擇右分支遷移即可，執(zhí)行速度快，但是查詢數(shù)據(jù)時，查詢訪問的層次高，執(zhí)行速度較慢。

Figure 6 Binary tree index圖6 二叉樹索引

針對這一缺點，我們對文件元數(shù)據(jù)索引樹進(jìn)行改進(jìn)，提出動態(tài)K叉編碼樹方法，有效減少查詢操作的樹的遍歷次數(shù)，同時仍保持選擇遷移的文件元數(shù)據(jù)速度快的優(yōu)點。其基本思想：

(1)在數(shù)據(jù)服務(wù)器中(設(shè)元數(shù)據(jù)服務(wù)器的編號為a0a1…ai-1)，將m位的hash(FID)的后m-i位分成h個分段(如圖7所示)，第一段長度用n表示，其余各段長度為n0(n0是由系統(tǒng)配置的固定值)。n的值隨服務(wù)器分裂而動態(tài)變化，其值n=m-i-(h-1)×n0，分段數(shù)h=(m-i/m0)，由此可見h也隨i而動態(tài)變化。

Figure 7 Segmented diagram of hash(FID)圖7 hash(FID)分段圖

(2)對于一個具有n0位二進(jìn)制數(shù)的編碼段，它有k=2n0個值。因此，對于某一個編碼段的一個值，在下一個編碼段中有k=2n0個對應(yīng)值，前后段值之間的對應(yīng)關(guān)系形成了一個K叉編碼樹，如圖8所示。樹中的葉子節(jié)點的指針指向一個目錄的文件元數(shù)據(jù)塊；樹中的分支節(jié)點的每個數(shù)組元素代表具有相同的二進(jìn)制前綴目錄。從樹的根節(jié)點遍歷到一個葉子節(jié)點得到的m-i位二進(jìn)制代碼，是一個文件標(biāo)識符哈希值hash(FID)的后m-i位，加上服務(wù)器編碼a0a1…ai-1得到m位二進(jìn)制編碼，它是一個文件標(biāo)識符的hash(FID)。

文件元數(shù)據(jù)的動態(tài)K叉編碼樹組織方法具有如下特性：

(2)它預(yù)先按元數(shù)據(jù)服務(wù)器所有可能分裂過程對文件元數(shù)據(jù)進(jìn)行分類，分裂執(zhí)行速度快。因為在動態(tài)K叉編碼樹表示樹根的指針數(shù)組中，以第2n-1個元素(1/2處)為界，它左邊的所有數(shù)組元素的序號編碼第一位是0，右邊的所有數(shù)組元素的序號編碼第一位是1，這個剛好是下一次分裂所需的數(shù)據(jù)劃分；同樣，在第2n-2、3*2n-2數(shù)組元素兩邊，元素編號編碼左第二位是0，右第二位是1，這剛好是第二次分裂時所需的數(shù)據(jù)劃分；以此類推。將數(shù)組對半分割后，由于每個數(shù)組元素數(shù)量減少一半，因此數(shù)組元素的序號編碼減少一位，自然地去掉了前面一位。

Figure 8 Dynamic K-tree for code圖8 動態(tài)K叉編碼樹

(3)數(shù)據(jù)偏斜不影響系統(tǒng)性能。在一個元數(shù)據(jù)系統(tǒng)，對于兩個數(shù)據(jù)量相同的數(shù)據(jù)集來說，它們需要的元數(shù)據(jù)服務(wù)器數(shù)量一樣，也就是說元數(shù)據(jù)服務(wù)器編址長度i值相同。另外，m是由選擇的hash算法決定，n0由系統(tǒng)配置，二者都是固定值，因而它們的hash(FID)分段數(shù)h=(m-i)/n0也相同，即K叉編碼樹的高度相同，由此可知，不管數(shù)據(jù)偏斜與否，一個元數(shù)據(jù)在K叉編碼樹的搜索次數(shù)是相同的。

例如，有八個元素的數(shù)組如圖9所示，在第四個元素左右兩邊第一位分別為0，在第二、六個元素左右二邊第一位分別為0，經(jīng)過兩次分裂得到四個數(shù)組。

Figure 9 Splitting process of the array with 9 elements圖9 含有九個元素的數(shù)組分裂過程

由于指針數(shù)組很自然地把數(shù)據(jù)塊分類，每次分裂時只要選擇指針數(shù)組中前一半或后一半數(shù)組元素所指的數(shù)據(jù)塊即可。

5 實驗與性能分析

5.1 實驗環(huán)境

實驗在四個機(jī)柜中的126臺計算機(jī)中完成，這些機(jī)器通過吉比特以太交換機(jī)連接成網(wǎng)絡(luò)，機(jī)柜內(nèi)的對半帶寬約為14 Gbps, 機(jī)柜之間的對半帶寬約為6.5 Gbps。每臺計算機(jī)有兩個2.8 GHz英特爾至強(qiáng)CPU、4 GB內(nèi)存、兩個每分鐘10 000轉(zhuǎn)SCSI硬盤。所有計算機(jī)運行內(nèi)核版本為2.6.9的Red Hat Enterprise Linux AS 4.0。

MDS和客戶機(jī)均采用Java語言編寫，并且分別運行在不同的機(jī)器中。系統(tǒng)初始時，每個MDS存有20萬條元數(shù)據(jù)。

5.2 實驗結(jié)果與分析

5.2.1 系統(tǒng)整體性能評估

在系統(tǒng)整體性能評估中，測試了系統(tǒng)在穩(wěn)定狀態(tài)和擴(kuò)展?fàn)顟B(tài)的性能。測試系統(tǒng)在穩(wěn)定狀態(tài)性能以評估系統(tǒng)在不同規(guī)模下的性能變化情況；而測試系統(tǒng)在擴(kuò)展?fàn)顟B(tài)下的性能，以評估系統(tǒng)擴(kuò)展對性能的影響。為了強(qiáng)調(diào)我們方法在選擇遷移數(shù)據(jù)方面的優(yōu)越性，還進(jìn)行了查找遷移數(shù)據(jù)效率實驗。

(1)無MDS分裂的元數(shù)據(jù)操作性能。

這組實驗中，客戶端對MDS進(jìn)行各種元數(shù)據(jù)操作，測試在沒有元數(shù)據(jù)服務(wù)器分裂情況下元數(shù)據(jù)服務(wù)的性能。為了進(jìn)行性能對比，我們同時實現(xiàn)了可擴(kuò)展哈希方法(記為EH)和我們的高效可擴(kuò)展的元數(shù)據(jù)管理方法(記為EEH)。實驗過程中，所有客戶機(jī)均運行四個線程并發(fā)訪問MDS，測試不同服務(wù)器規(guī)模下單位時間內(nèi)完成的元數(shù)據(jù)操作數(shù)。其結(jié)果如圖10所示。

Figure 10 Operation performance of metadata圖10 元數(shù)據(jù)操作性能

從圖10中可以看出：①EEH的性能明顯優(yōu)于 EH，這是因為EEH采用精確定位方式，而EH采用廣播式定位，較多廣播消息影響系統(tǒng)性能。②隨著MDS的增加，二者性能都增加，但二者的性能增長率均逐漸下降，這是因為MDS增加，系統(tǒng)服務(wù)客戶的數(shù)量增加。但是，客戶增加后，對EH來說，廣播消息更多，每臺MDS花費更多的處理能力來處理無用的廣播消息，因而系統(tǒng)的有效服務(wù)能力下降；對EEH來說，MDS分裂加快，更新客戶端緩沖區(qū)的速度加快，從而系統(tǒng)的有效服務(wù)能力也有所下降。③隨著MDS的增加EH的性能增長率比EEH慢，這是因為較多的廣播消息影響EH的性能。

(2) 查找遷移數(shù)據(jù)效率。

在該測試中，同時實現(xiàn)了線性哈希元數(shù)據(jù)組織方法，以用來與動態(tài)K叉編碼樹方法做可擴(kuò)展性效率對比，選擇線性哈希方法來與動態(tài)K叉編碼樹方法做性能對比的原因是因為現(xiàn)有很多系統(tǒng)都采用它來組織元數(shù)據(jù)[22,23]。因為兩個方案的查找性能在每臺元數(shù)據(jù)服務(wù)器上都很相近，因此我們測試二者在一臺元數(shù)據(jù)服務(wù)器中不同對象(文件和目錄)數(shù)的查找性能(測試的對象元數(shù)據(jù)按兩種組織方式進(jìn)行組織，并緩沖在內(nèi)存中)，其測試結(jié)果如表1所示。從表1中可以看出，線性哈希法查找時間比較長，并且隨目錄數(shù)增加而增長，動態(tài)K叉編碼樹方法查找時間非常小，幾乎為零，并且不隨目錄數(shù)而變化。

Table 1 Compare of extension efficiency表1 系統(tǒng)擴(kuò)展效率對比

(3)MDS分裂對元數(shù)據(jù)操作性能影響。

該組實驗測試MDS從四臺變化為五臺過程中系統(tǒng)的性能。同樣，為了進(jìn)行性能對比，我們同時實現(xiàn)了EH和EEH。實驗過程中，所有客戶機(jī)均運行四個線程并發(fā)訪問MDS，測試不同時刻完成的元數(shù)據(jù)操作數(shù)。結(jié)果如圖11所示。從圖11中可以看出，在MDS分裂過程中，EH和EEH的性能均略有下降，這是因為MDS 分裂需要查找和遷移數(shù)據(jù)，從而引起系統(tǒng)性能下降，但EH受到的影響時間較長，這是因為在EH中查找遷移數(shù)據(jù)較長。

Figure 11 Effect of metadata operation performance by MDS splitting圖11 MDS分裂對元數(shù)據(jù)操作性能影響

5.2.2 參數(shù)m和n0對系統(tǒng)性能的影響

(1)參數(shù)n0對系統(tǒng)性能的影響。

這一組實驗測試m=128，n0取不同值時系統(tǒng)訪問性能。n0每取一個不同值，數(shù)據(jù)就重新組織一次，然后測試查詢數(shù)據(jù)的時間。在每次實驗過程中，數(shù)據(jù)規(guī)模均為20萬條，緩沖區(qū)設(shè)為600 MB。測試結(jié)果分別如圖12所示。從圖12中可以看出，隨著n0逐漸增加，查詢時間先逐漸減少，然后逐漸增加，這是因為：①在n0≤8時，K叉樹節(jié)點均緩沖到緩沖區(qū)中，隨著n0增加，樹的高度逐漸減小，因而查詢時間減少。②在n0>8時，一些節(jié)點數(shù)據(jù)存儲在磁盤中，訪問時要從磁盤讀到緩沖區(qū),n0越大，需要的存儲量越大，讀到內(nèi)存時間就越多。

Figure 12 Effection of the system performance by n0圖12 n0對系統(tǒng)性能影響

(2)參數(shù)m對系統(tǒng)性能的影響。

這一組實驗中，測試n0=8、m取不同值時系統(tǒng)的性能，實驗過程中，數(shù)據(jù)規(guī)模仍均為20萬條，緩沖區(qū)設(shè)為600 MB。測試結(jié)果如圖13所示。從圖13中可以看出,在n0為固定值時，查詢時間隨著m的增加而逐漸增大。這是因為n0為固定值時，m增大，樹的高度增加。

Figure 13 Effection of the system performance by m圖13 m對系統(tǒng)性能影響

6 結(jié)束語

本文提出了一種高效可擴(kuò)展的元數(shù)據(jù)管理方法，有效解決了云計算環(huán)境中元數(shù)據(jù)管理高效可擴(kuò)展問題。它具有以下優(yōu)點：(1)與查詢表法和靜態(tài)哈希方法相比，它實現(xiàn)了系統(tǒng)動態(tài)擴(kuò)展；(2)與可擴(kuò)展哈希方法相比，它能精確地進(jìn)行數(shù)據(jù)定位和快速選擇需要遷移的元數(shù)據(jù)，提高了系統(tǒng)性能和擴(kuò)展效率。

[1] Patil S V, Gibson G. Giga+:Scalable directories for shared file systems[EB/OL].[2008-12-15].http://highscalability.com/flickr-architecture.

[2] Patil S V, Gibson G, Lang S,et al. Giga+:scalable directories for shared file systems[C]∥Proc of the 2nd International Workshop on Petascale Data Storage, 2007:26-29.

[3] Xing Jing,Xiong Jin,Sun Ning-hui,et al. Adaptive and scalable metadata management to support a trillion files[C]∥Proc of SC’09, 2009:1-11.

[4] Vajgel P. Needle in a haystack:Efficient storage of billions of photos[EB/OL].[2009-11-15].http://www.facebook.com/note.php?note_id=76191543919.

[5] http://www.photobucket.com/.

[6] http://picasa.google.com/.

[7] Hoff T. Flickr architecture[EB/OL].[2009-11-15].http://highscalability.com/flickr-architecture.

[8] Large synoptic survey telescope. http://www.lsst.org/lsst, 2008.

[9] Ghemawat S, Gobioff H,Leung S T.The Google file system[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[10] Shvachko K, Kuang H, Radia S, et al. The Hadoop distributed file system [C]∥Proc of NASA/IEEE Conference on Mass Storage Systems and Technologies (MSST), 2010:6-16.

[11] Braam P J.The Lustre storage architecture[EB/OL].[2004-12-15].http://www.lustre.org/docs/lustre.pdf.

[12] Pawlowski B,Juszczak C,Staubach P,et al. NFS version 3:Design and implementation[C]∥Proc of the Summer 1994 USENIX Conference, 1994:137-151.

[13] Morris J H,Satyanarayanan M,Conner M H,et al. Andrew:A distributed personal computing environment[J].Communications of the ACM,1986,29(3):184-201.

[14] Satyanarayanan M, Kistler J J, Kumar P, et al. Coda:A highly available file system for a distributed workstation environment[J].IEEE Transactions on Computers,1990,39(4):447-459.

[15] Ousterhout J K,Cherenson A R,Douglis F,et al.The sprite network operating system[J].IEEE Computer,1988,21(2):23-36.

[16] Weil S A,Pollack K T,Brandt S A,et al. Dynamic metadata management for petabyte-scale file systems[C]∥Proc of the 2004 ACM/IEEE Conference on Supercomputing, 2004:523-534.

[17] Corbett P F,Feitelson D G.The Vesta parallel file system[J].ACM Transactions on Computer Systems,1996,14(3):225-264.

[18] Braam P J,Callahan M,Schwan P,et al.The InterMezzo file system[C]∥Proc of the 3rd Perl Conference,1999:1.

[19] Miller E L,Katz R H.RAMA:An easy-to-use,high-performance parallel file system[J].Parallel Computing,1997,23(4):419-446.

[20] Rodeh O,Teperman A.zFS—a scalable distributed file system using object disks[C]∥Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies, 2003:207-218.

[21] Brandt S A, Xue L, Miller E L, et al. Efficient metadata management in large distributed file systems[C]∥Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Sysetms and Technologies,2003:290-298.

[22] Liu Z. Research on scalable cluster storage system based on object storage architecture[D]. Changsha:National University of Defense Technology,2005.(in Chinese)

[23] Liu Z, Zhou X M. A metadata management method based on directory path[J]. Journal of Software, 2007, 18(2):236-245.(in Chinese)

[24] Wang Juan. Research on metadata management in object-based storage system[D]. Wuhan:Huazhong University of Science & Technology,2010.(in Chinese)

[25] Wang Juan,Feng Dan,Wang Fang, et al.MHS:A distributed metadata management strategy[J].The Journal of Systems and Software, 2009,82(12),2004-2011.

[26] Fagin R, Nievergelt J, Pippenger N, et al. Extendible hashing:A fast access method for dynamic files[J]. ACM Transactions Database System, 1979,4(3):315-344.

[27] Schmuck F, Haskin R. GPFS:A shared-disk file system for large computing clusters[C]∥Proc of the Conference on File and Storage Technologies, 2002:1.

附中文參考文獻(xiàn):

[22] 劉仲. 基于對象存儲結(jié)構(gòu)的可伸縮集群存儲系統(tǒng)研究[D]. 長沙:國防科學(xué)技術(shù)大學(xué), 2005.

[23] 劉仲，周興銘.基于目錄路徑的元數(shù)據(jù)管理方法[J].軟件學(xué)報,2007,18(2):236-245.

[24] 王娟. 對象存儲系統(tǒng)中元數(shù)據(jù)管理研究[D]. 武漢：華中科

技大學(xué), 2010.

HUANGBin,born in 1971,PhD,associate professor,his research interests include cloud computing, mass data storage, analysis and processing of large data.

彭宇行(1963-),男，湖南長沙人，博士，研究員，研究方向為多媒體信息處理、并行與分布式計算。E-mail:

PENGYu-xing,born in 1963,PhD,research fellow,his research interests include multimedia information processing, parallel and distributed computing.

Anefficientscalablemetadatamanagementmethodincloudcomputing

HUANG Bin1,2,PENG Yu-xing3

(1.School of Mathematics and Computer Science,Guizhou Normal University,Guiyang 550001；2.School of Computer,Wuhan University,Wuhan 430072；3.College of Computer,National University of Defense Technology,Changsha 410073,China)

Aiming at the lower performance problem of the existing metadata management methods in cloud computing,an efficient scalable metadata management method is proposed in cloud computing.Firstly,a dynamic binary mapping tree is used to achieve the precise positioning of the metadata server.Secondly,a lazy update technique is adopted to dynamically update the binary mapping tree.Finally,a dynamic K tree is proposed to improve the speed of selecting migrated metadata during MDS splitting.The experimental results show that the method can effectively improve the efficiency of the scalable metadata management method in cloud computing.

cloud computing;metadata;efficient;scalable

1007-130X(2014)08-1447-08

2013-12-12;

：2014-04-03

國家973 計劃資助項目(2011CB302601)；國家863計劃資助項目(2011AA01A202)；湖南省科技計劃資助項目(2013FJ4335,2013FJ4295)

TP393

：A

10.3969/j.issn.1007-130X.2014.08.005

符時，我們才在K叉編碼樹中建立對應(yīng)分支，否則它是一個空子樹，不需要為它分配節(jié)點空間。例如，在圖8中，根節(jié)點t的1…10值沒有分支，節(jié)點q中除0…01值外，其余值都沒有分支。當(dāng)插入一個hash(FID)中ai…ai+n-1為1…10的文件元數(shù)據(jù)時，就會建立一個以1…10為根的子樹。節(jié)點的分支數(shù)隨文件元數(shù)據(jù)的插入而動態(tài)變化，因此，K叉編碼樹是一個動態(tài)樹。

黃斌(1971-),男，湖南溆浦人，博士，副教授，研究方向為云計算、大規(guī)模數(shù)據(jù)存儲、大數(shù)據(jù)分析與處理。E-mail:1059564040@qq.com

通信地址：550001 貴州省貴陽市貴州師范大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院

Address:School of Mathematics and Computer Science,Guizhou Normal University,Guiyang 550001,Guizhou,P.R.China