云計算環境中高效可擴展的元數據管理方法*

黃 斌，彭宇行

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

云計算環境中高效可擴展的元數據管理方法*

黃 斌1,2，彭宇行3

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

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

云計算；元數據；高效；可擴展

1 引言

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

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

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

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

2 精確定位可擴展哈希方法

可擴展哈希能較好地支持元數據存儲系統動態擴展，其原理是把文件的標識符(記為FID)哈希成m位二進制值hash(FID)，hash(FID)的i位前綴值a0a1…ai-1相同的文件元數據被分布到同一臺元數據服務器中(a0a1…ai-1稱為該元數據服務器的數據標識符，i稱為數據標識符長度)。當數據標識符為a0a1…ai-1的元數據服務器容量不夠時，分裂該元數據服務器，分裂規則是：將hash(FID)前綴為a0a1…ai-11元數據遷移到新增的元數據服務器中，hash(FID)前綴為a0a1…ai-10元數據仍保留在原元數據服務器中，此時前者的數據標識符變為a0a1…ai-11，后者的數據標識符變為a0a1…ai-10，兩者的數據標識符長度增加1。可擴展哈希原理如圖1所示。

Figure 1 Extensible hash圖1 可擴展哈希

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

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

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

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

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

3 延遲更新方法

當一個元數據服務器分裂時，如果采用同步更新方法，更新操作對系統性能影響較大，因此我們采用延遲更新方法，把總的更新開銷分攤到各個操作中，避免動態二叉映射樹更新操作對系統性能產生較大波動。其具體方法是：

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

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

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

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

Figure3Splittinglogofservera0a1…ap

圖3 服務器a0a1…ap的分裂日志

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

對服務器端：

將〈IPi, IPi+1,…,IPn〉發給流出訪問請求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

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

4 元數據組織方法

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

Figure 4 Splitting of MDS a0a1…ai-1圖4 元數據服務器分裂

Figure 5 Distribution of directory metadata圖5 目錄元數據在元數據服務器的分布

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

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

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

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

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

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

文件元數據的動態K叉編碼樹組織方法具有如下特性：

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

Figure 8 Dynamic K-tree for code圖8 動態K叉編碼樹

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

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

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

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

5 實驗與性能分析

5.1 實驗環境

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

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

5.2 實驗結果與分析

5.2.1 系統整體性能評估

在系統整體性能評估中，測試了系統在穩定狀態和擴展狀態的性能。測試系統在穩定狀態性能以評估系統在不同規模下的性能變化情況；而測試系統在擴展狀態下的性能，以評估系統擴展對性能的影響。為了強調我們方法在選擇遷移數據方面的優越性，還進行了查找遷移數據效率實驗。

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

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

Figure 10 Operation performance of metadata圖10 元數據操作性能

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

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

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

Table 1 Compare of extension efficiency表1 系統擴展效率對比

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

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

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

5.2.2 參數m和n0對系統性能的影響

(1)參數n0對系統性能的影響。

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

Figure 12 Effection of the system performance by n0圖12 n0對系統性能影響

(2)參數m對系統性能的影響。

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

Figure 13 Effection of the system performance by m圖13 m對系統性能影響

6 結束語

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

[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.

附中文參考文獻:

[22] 劉仲. 基于對象存儲結構的可伸縮集群存儲系統研究[D]. 長沙:國防科學技術大學, 2005.

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

[24] 王娟. 對象存儲系統中元數據管理研究[D]. 武漢：華中科

技大學, 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叉編碼樹中建立對應分支，否則它是一個空子樹，不需要為它分配節點空間。例如，在圖8中，根節點t的1…10值沒有分支，節點q中除0…01值外，其余值都沒有分支。當插入一個hash(FID)中ai…ai+n-1為1…10的文件元數據時，就會建立一個以1…10為根的子樹。節點的分支數隨文件元數據的插入而動態變化，因此，K叉編碼樹是一個動態樹。

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

通信地址：550001 貴州省貴陽市貴州師范大學數學與計算機科學學院

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