程付超，苗 放，2，陳 墾

（1.成都理工大學(xué) 地球探測(cè)與信息技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，四川 成都610059；2.成都理工大學(xué)地質(zhì)災(zāi)害防治與地質(zhì)環(huán)境保護(hù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，四川 成都610059）

0 引 言

分布式文件系統(tǒng)的元數(shù)據(jù)管理直接影響到系統(tǒng)的性能、擴(kuò)展性、穩(wěn)定性和可靠性。目前，分布式文件系統(tǒng)大多將元數(shù)據(jù)全部緩存到服務(wù)器內(nèi)存中進(jìn)行管理［1］，按照其部署方式可分為集中式元數(shù)據(jù)管理模型、分布式元數(shù)據(jù)管理模型和無(wú)元數(shù)據(jù)模型三類［2］，見(jiàn)表1。多數(shù)分布式文件系統(tǒng)采用了集中式的元數(shù)據(jù)管理模型［3－7］，如GFS［3］、HDFS［4］、Lustre［5］等；GlusterFS［8］中采用了無(wú)元數(shù)據(jù)模型。但隨著當(dāng)前各類應(yīng)用系統(tǒng)中數(shù)據(jù)量的爆發(fā)性增長(zhǎng)，元數(shù)據(jù)的數(shù)據(jù)量已經(jīng)逐漸超過(guò)單臺(tái)服務(wù)器的內(nèi)存上限，采用分布式元數(shù)據(jù)管理模型是未來(lái)的發(fā)展趨勢(shì)［9，10］。因此，如何在多臺(tái)元數(shù)據(jù)服務(wù)器間進(jìn)行高效低開(kāi)銷的元數(shù)據(jù)同步，維護(hù)元數(shù)據(jù)的一致性，成為一個(gè)需要解決的重要問(wèn)題。目前主要存在兩種解決辦法：

（1）使用多個(gè)獨(dú)立命名空間。一些分布式文件系統(tǒng)，比如HDFS Federation［11］，讓每臺(tái)元數(shù)據(jù)服務(wù)器單獨(dú)管理一個(gè)命名空間，服務(wù)器間不需要互相協(xié)調(diào)。這種方法從根本上消除了同步元數(shù)據(jù)的必要性，其性能與使用集中式模型的系統(tǒng)一致；但這種方法沒(méi)有完全解決單點(diǎn)故障問(wèn)題，當(dāng)某個(gè)元數(shù)據(jù)服務(wù)器宕機(jī)時(shí)，其管理的相應(yīng)文件便不可訪問(wèn)。

（2）使用分布式共享內(nèi)存技術(shù)。一些分布式文件系統(tǒng)采用了硬件級(jí)的分布式共享內(nèi)存技術(shù)（如MMP、SMP和cc－NUMA）［2］，雖然可以明顯提高系統(tǒng)性能，并抵消同步性能開(kāi)銷，卻大大增加了系統(tǒng)的構(gòu)建成本。

表1 元數(shù)據(jù)管理模型對(duì)比

針對(duì)分布式文件系統(tǒng)元數(shù)據(jù)管理模型存在的上述不足，本文借鑒Spark計(jì)算框架中RDDs［12］的設(shè)計(jì)思路，提出了一種分布式的內(nèi)存抽象——工作－備份數(shù)據(jù)集（workingbackup dataset，WBD），將內(nèi)存區(qū)域抽象為數(shù)據(jù)集，并通過(guò)數(shù)據(jù)集操作來(lái)實(shí)現(xiàn)內(nèi)存訪問(wèn)，減小了數(shù)據(jù)同步時(shí)內(nèi)存操作的復(fù)雜度，降低了元數(shù)據(jù)同步造成的額外性能開(kāi)銷。在WBD 的基礎(chǔ)上，本文設(shè)計(jì)了一種分布式文件系統(tǒng)元數(shù)據(jù)管理模型——自應(yīng)從模型（self－adaptation master－slave，SAMS），通過(guò)數(shù)據(jù)的放置、更新和同步策略，實(shí)現(xiàn)元數(shù)據(jù)管理的自適應(yīng)性。實(shí)驗(yàn)分析表明，采用SAMS作為分布式文件系統(tǒng)的元數(shù)據(jù)管理模型，不但能夠提供高性能的元數(shù)據(jù)服務(wù)，還能夠保證元數(shù)據(jù)服務(wù)的高容錯(cuò)性和高擴(kuò)展性。

1 工作－備份數(shù)據(jù)集

工作－備份數(shù)據(jù)集是一種內(nèi)存抽象，也是一種面向高效數(shù)據(jù)訪問(wèn)服務(wù)的分布式數(shù)據(jù)集，它將內(nèi)存區(qū)域抽象為數(shù)據(jù)集形式，通過(guò)數(shù)據(jù)集操作來(lái)訪問(wèn)內(nèi)存區(qū)域，實(shí)現(xiàn)基于內(nèi)存的數(shù)據(jù)高效查詢、更新和同步等功能，同時(shí)具備多種工作狀態(tài)，可以為分布式文件系統(tǒng)的元數(shù)據(jù)管理提供支持。

1.1 WBD的構(gòu)成

工作－備份數(shù)據(jù)集由數(shù)據(jù)集版本、工作數(shù)據(jù)集和備份數(shù)據(jù)集三部分構(gòu)成。

1.1.1 數(shù)據(jù)集版本

數(shù)據(jù)集版本（dataset version，DV）是進(jìn)行數(shù)據(jù)一致性校驗(yàn)和數(shù)據(jù)恢復(fù)的重要依據(jù)。版本的內(nèi)容包括WBD 名稱、當(dāng)前版本號(hào)和歷史版本。WBD 名稱是在全局維護(hù)的WBD 唯一標(biāo)識(shí)符；當(dāng)前版本號(hào)是與最新的數(shù)據(jù)集相對(duì)應(yīng)的WBD 版本；歷史版本用于查詢WBD 的更新歷史，進(jìn)行數(shù)據(jù)恢復(fù)。數(shù)據(jù)集版本存儲(chǔ)在服務(wù)器的外部存儲(chǔ)器上，同時(shí)也被緩存到內(nèi)存里。

1.1.2 工作數(shù)據(jù)集

WBD 中的工作數(shù)據(jù)集（working dataset，WD）用于提供數(shù)據(jù)的查詢、更新和同步等功能，被緩存到服務(wù)器內(nèi)存中。工作數(shù)據(jù)集由服務(wù)數(shù)據(jù)集和操作數(shù)據(jù)集組成。

（1）服務(wù)數(shù)據(jù)集（service dataset，SD）

服務(wù)數(shù)據(jù)集是WBD 中的主要數(shù)據(jù)集，WBD 的絕大部分?jǐn)?shù)據(jù)記錄都被放置在服務(wù)數(shù)據(jù)集中。SD 主要用于提供數(shù)據(jù)的查詢服務(wù)，因此只支持讀操作和批量寫(xiě)入操作，而不支持細(xì)粒度的寫(xiě)操作，這樣就減少了數(shù)據(jù)的更新頻率，從而降低了更新造成的性能開(kāi)銷。

（2）操作數(shù)據(jù)集（operation dataset，OD）

操作數(shù)據(jù)集在WBD 中占的比重較小，但卻非常重要，數(shù)據(jù)的查詢和更新等操作的完成都在一定程度上依賴于操作數(shù)據(jù)集。OD 中放置的是對(duì)當(dāng)前數(shù)據(jù)集的實(shí)時(shí)操作記錄，這些操作記錄按照順序排列，組成一個(gè)操作隊(duì)列。相對(duì)于SD，OD 支持完整的讀寫(xiě)操作，其數(shù)據(jù)更新和同步都較為頻繁，但由于其數(shù)據(jù)總量較小，造成的性能開(kāi)銷也就相對(duì)較小。

1.1.3 備份數(shù)據(jù)集

備份數(shù)據(jù)集（backup dataset，BD）存在于外部存儲(chǔ)器上，以文件形式存儲(chǔ)，主要用于數(shù)據(jù)的加載和恢復(fù)，由補(bǔ)丁和鏡像構(gòu)成。

（1）補(bǔ)?。╬atch）：補(bǔ)丁是操作數(shù)據(jù)集的備份數(shù)據(jù)，由持久化操作生成。在一個(gè)WBD 中一般存在一個(gè)或多個(gè)補(bǔ)丁，每個(gè)補(bǔ)丁與一個(gè)數(shù)據(jù)集版本相對(duì)應(yīng)，通過(guò)補(bǔ)丁能夠?qū)BD 恢復(fù)到其任意版本。

（2）鏡像（image）：鏡像是WBD 中服務(wù)數(shù)據(jù)集的備份數(shù)據(jù)，通過(guò)持久化操作寫(xiě)入外部存儲(chǔ)器。鏡像中記錄了對(duì)應(yīng)的數(shù)據(jù)集版本和此版本服務(wù)數(shù)據(jù)集的全部數(shù)據(jù)記錄，可以用于節(jié)點(diǎn)重啟和宕機(jī)之后服務(wù)數(shù)據(jù)集的恢復(fù)。每個(gè)WBD只有一個(gè)鏡像文件，老版本的鏡像將被替換。

1.2 WBD的操作

WBD 提供了較為豐富的數(shù)據(jù)集操作，能夠滿足分布式文件系統(tǒng)元數(shù)據(jù)管理的需要。按照操作對(duì)象的不同，WBD操作可以分為基本操作、工作數(shù)據(jù)集操作和備份數(shù)據(jù)集操作三類，見(jiàn)表2。

表2 WBD 提供的操作

1.2.1 數(shù)據(jù)融合

數(shù)據(jù)融合是WBD 的核心操作，通過(guò)數(shù)據(jù)融合能夠?qū)φ麄€(gè)數(shù)據(jù)集進(jìn)行更新。其步驟為：①將OD 中的操作記錄持久化到外部存儲(chǔ)器上，成為新的補(bǔ)??；②將OD 中的操作記錄融合到SD 中，實(shí)現(xiàn)對(duì)SD 的批量更新，融合算法如圖1所示。③清空OD，并生成新的數(shù)據(jù)集版本，融合完畢。

圖1 數(shù)據(jù)融合算法流程

1.2.2 數(shù)據(jù)恢復(fù)

WBD 的數(shù)據(jù)恢復(fù)主要是對(duì)工作數(shù)據(jù)集進(jìn)行恢復(fù)，而對(duì)其中的OD 和SD 采用了不同的恢復(fù)方式。OD 的恢復(fù)通過(guò)與其它節(jié)點(diǎn)進(jìn)行同步來(lái)完成。SD 的恢復(fù)通過(guò)版本、鏡像和補(bǔ)丁來(lái)完成，能夠?qū)D 恢復(fù)到剛剛完成某次融合之后的狀態(tài)，流程如圖2所示。

1.2.3 分裂與合并

WBD 支持在線的分裂和合并操作。

（1）WBD 的分裂：在進(jìn)行分裂操作時(shí)，會(huì)首先對(duì)原始WBD 進(jìn)行一次數(shù)據(jù)融合，然后創(chuàng)建兩個(gè)新的WBD，將原始WBD 的服務(wù)數(shù)據(jù)集進(jìn)行劃分后，分別存入新的WBD中，并將數(shù)據(jù)持久化為各自的初始補(bǔ)丁，最后設(shè)置好初始版本，完成分裂操作。分裂操作的關(guān)鍵在于服務(wù)數(shù)據(jù)集中數(shù)據(jù)記錄的劃分算法，可以采用的算法包括排序算法，隨機(jī)算法，hash算法，局部匹配算法等，在實(shí)際應(yīng)用中可以根據(jù)需要進(jìn)行選擇。

圖2 服務(wù)數(shù)據(jù)集恢復(fù)流程

（2）WBD 的合并：與分裂操作類似，在進(jìn)行合并操作時(shí)，也會(huì)首先對(duì)兩個(gè)WBD 進(jìn)行一次數(shù)據(jù)融合，然后創(chuàng)建一個(gè)新的WBD，將兩個(gè)服務(wù)數(shù)據(jù)集合并為一個(gè)寫(xiě)入新的WBD 中，并持久化為初始補(bǔ)丁，最后設(shè)置初始版本，完成合并操作。

1.3 WBD的狀態(tài)

工作－備份數(shù)據(jù)集具有預(yù)備和活動(dòng)兩種工作狀態(tài)，分別對(duì)應(yīng)于不同的功能，通過(guò)加載、恢復(fù)和釋放操作可以實(shí)現(xiàn)WBD 狀態(tài)切換，如圖3所示。

圖3 WBD 狀態(tài)切換

（1）預(yù)備狀態(tài)。WBD 部署完成等待載入的狀態(tài)叫做預(yù)備狀態(tài)，在這種狀態(tài)下，工作數(shù)據(jù)集相關(guān)的操作都無(wú)法執(zhí)行，WBD 不能提供服務(wù)，但并不影響數(shù)據(jù)恢復(fù)、同步和校驗(yàn)等操作的執(zhí)行。

（2）活動(dòng)狀態(tài)。將工作數(shù)據(jù)集緩存到內(nèi)存中，并開(kāi)始提供數(shù)據(jù)服務(wù)的狀態(tài)，叫做WBD 的活動(dòng)狀態(tài)?；顒?dòng)狀態(tài)是WBD 的工作狀態(tài)，在這種狀態(tài)下WBD 提供的所有操作都能夠執(zhí)行，從而提供高效的數(shù)據(jù)訪問(wèn)服務(wù)。

1.4 工作－備份數(shù)據(jù)集與分布式共享內(nèi)存的比較

工作－備份數(shù)據(jù)集與分布式共享內(nèi)存的對(duì)比見(jiàn)表3。

表3 工作－備份數(shù)據(jù)集與分布式共享內(nèi)存的對(duì)比

2 基于工作－備份數(shù)據(jù)集的SAMS模型

2.1 SAMS的組成結(jié)構(gòu)

SAMS是一種主－從模式的分布式元數(shù)據(jù)管理模型，由一個(gè)控制節(jié)點(diǎn)（controller）和多個(gè)工作節(jié)點(diǎn)（worker）構(gòu)成，并通過(guò)工作－備份數(shù)據(jù)集實(shí)現(xiàn)元數(shù)據(jù)的共享和同步。SAMS維護(hù)全局唯一的命名空間，沿用了HDFS／HDFS Federation中目錄分層的命名空間劃分算法，將命名空間分為多個(gè)子空間，每個(gè)子命名空間的元數(shù)據(jù)通過(guò)一個(gè)WBD 進(jìn)行管理，這樣整個(gè)命名空間就劃分成了多個(gè)WBD，這些WBD 會(huì)被分配到工作節(jié)點(diǎn)，并提供元數(shù)據(jù)服務(wù)。為了保證SAMS的容錯(cuò)性，每個(gè)WBD 被分配到至少3 個(gè)不同的工作節(jié)點(diǎn)。SAMS組成結(jié)構(gòu)如圖4所示。

圖4 SAMS組成結(jié)構(gòu)

（1）控制節(jié)點(diǎn)?？刂乒?jié)點(diǎn)負(fù)責(zé)整個(gè)SAMS集群中各節(jié)點(diǎn)的數(shù)據(jù)同步、數(shù)據(jù)備份、負(fù)載均衡和故障恢復(fù)等任務(wù)?？刂乒?jié)點(diǎn)會(huì)按照命名空間的劃分，將各子命名空間對(duì)應(yīng)的WBD 分配給各個(gè)工作節(jié)點(diǎn)，并對(duì)所有工作節(jié)點(diǎn)的狀態(tài)進(jìn)行監(jiān)控，維護(hù)元數(shù)據(jù)集群的負(fù)載均衡。為了保證元數(shù)據(jù)的一致性，控制節(jié)點(diǎn)上還建立了同步緩存，用于對(duì)數(shù)據(jù)同步進(jìn)行協(xié)調(diào)。同步緩存是一個(gè)FIFO 隊(duì)列，其中按序存儲(chǔ)了各節(jié)點(diǎn)發(fā)來(lái)的更新記錄，每條記錄由更新的序號(hào)、內(nèi)容、目標(biāo)WBD 和目標(biāo)節(jié)點(diǎn)四部分信息構(gòu)成。

（2）工作節(jié)點(diǎn)。工作節(jié)點(diǎn)是SAMS中提供元數(shù)據(jù)服務(wù)的節(jié)點(diǎn)，負(fù)責(zé)通過(guò)WBD 管理分配到的子命名空間，提供目錄查詢、數(shù)據(jù)定位等元數(shù)據(jù)服務(wù)。每個(gè)工作節(jié)點(diǎn)上可以運(yùn)行一個(gè)或多個(gè)WBD，這些WBD 之間相互獨(dú)立，不需要互相協(xié)調(diào)，各自管理自己的子命名空間。

2.2 SAMS的運(yùn)行策略

2.2.1 數(shù)據(jù)放置策略

在分布式文件系統(tǒng)中，元數(shù)據(jù)的數(shù)據(jù)總量相對(duì)較小，雖然可能超過(guò)單個(gè)節(jié)點(diǎn)的內(nèi)存容量，但在節(jié)點(diǎn)的外部存儲(chǔ)器上進(jìn)行全冗余備份是可行的。因此，對(duì)于構(gòu)成命名空間的WBD，SAMS按照 “全冗余部署，分布式運(yùn)行”的策略進(jìn)行放置：

（1）全冗余部署。在全部節(jié)點(diǎn)（包括控制節(jié)點(diǎn)）上對(duì)WBD 按照全冗余方式進(jìn)行部署，保證每個(gè)節(jié)點(diǎn)在數(shù)據(jù)上的一致性；

（2）分布式運(yùn)行。工作節(jié)點(diǎn)按照分配的子命名空間，加載相應(yīng)的WBD，使之進(jìn)入活動(dòng)狀態(tài)，開(kāi)始提供元數(shù)據(jù)服務(wù)。

以這種方式進(jìn)行數(shù)據(jù)放置，從局部看，每個(gè)工作節(jié)點(diǎn)上都部署了全部的WBD，并且大部分都處于預(yù)備狀態(tài)，控制節(jié)點(diǎn)可以根據(jù)集群負(fù)載狀況，隨時(shí)對(duì)命名空間的劃分進(jìn)行調(diào)整，保證了元數(shù)據(jù)服務(wù)的可用性；從全局看，所有節(jié)點(diǎn)（包括控制節(jié)點(diǎn)在內(nèi)）在物理上都是對(duì)等的，只是運(yùn)行的程序和WBD 有所不同，為實(shí)現(xiàn)節(jié)點(diǎn)的自適應(yīng)控制提供了條件。

2.2.2 數(shù)據(jù)更新策略

SAMS的數(shù)據(jù)更新通過(guò)WBD 相關(guān)操作實(shí)現(xiàn)，具有實(shí)時(shí)和異步兩種不同的更新策略：

（1）實(shí)時(shí)更新。SAMS通過(guò)登記操作對(duì)活動(dòng)狀態(tài)WBD的OD 進(jìn)行實(shí)時(shí)更新，WBD 中其余部分的數(shù)據(jù)都直接或間接的來(lái)自于OD，保證了OD 數(shù)據(jù)的有效性，也就保證了整個(gè)WBD 的數(shù)據(jù)是有效的。

（2）異步更新。對(duì)于WBD 的其余部分，采用異步方式進(jìn)行數(shù)據(jù)更新。SAMS會(huì)根據(jù)OD 的數(shù)據(jù)量大小，定期執(zhí)行融合操作，實(shí)現(xiàn)對(duì)SD、補(bǔ)丁和數(shù)據(jù)集版本的更新；對(duì)于鏡像文件，SAMS會(huì)根據(jù)工作節(jié)點(diǎn)負(fù)載情況，選擇負(fù)載較低的時(shí)候通過(guò)持久化操作對(duì)鏡像文件進(jìn)行更新。

通過(guò)這樣的更新策略，SAMS將數(shù)據(jù)的更新過(guò)程進(jìn)行了分解，避免一次性更新?lián)斐蛇^(guò)大的服務(wù)器性能開(kāi)銷。

2.2.3 數(shù)據(jù)同步策略

為了保證元數(shù)據(jù)的一致性，提供可靠的元數(shù)據(jù)服務(wù)，SAMS中需要對(duì)元數(shù)據(jù)進(jìn)行同步，采用了強(qiáng)一致性同步和最終一致性同步兩種策略，分別與數(shù)據(jù)更新策略中實(shí)時(shí)更新和異步更新相對(duì)應(yīng)。

（1）強(qiáng)一致性同步。在SAMS中元數(shù)據(jù)服務(wù)通過(guò)活動(dòng)狀態(tài)的WBD 提供，因此需要對(duì)活動(dòng)狀態(tài)的WBD 維護(hù)強(qiáng)一致性。又由于WBD 中OD 是更新較為頻繁的部分，且對(duì)元數(shù)據(jù)的查詢和更新等操作都在一定程度上依賴于OD，所以SAMS對(duì)OD 采用了強(qiáng)一致性的同步策略，具體方法是：當(dāng)某工作節(jié)點(diǎn)需要更新OD 時(shí)，會(huì)先將更新數(shù)據(jù)同步到控制節(jié)點(diǎn)上，控制節(jié)點(diǎn)為這些數(shù)據(jù)分配一個(gè)序號(hào)后放入同步緩存中，并將序號(hào)返回給該工作節(jié)點(diǎn)，工作節(jié)點(diǎn)按照序號(hào)將更新數(shù)據(jù)插入OD 中；當(dāng)同步緩存不為空時(shí)，控制節(jié)點(diǎn)會(huì)按序取出記錄，并將其轉(zhuǎn)發(fā)給所有目標(biāo)節(jié)點(diǎn)。OD 的強(qiáng)一致性同步，不但保證了元數(shù)據(jù)服務(wù)的一致性，也保證了各節(jié)點(diǎn)在進(jìn)行融合操作時(shí)對(duì)SD、數(shù)據(jù)集版本和補(bǔ)丁的更新是一致的（根據(jù)FLP 結(jié)論），對(duì)維護(hù)整個(gè)WBD 的一致性具有較大的影響。

（2）最終一致性同步。SAMS中最終一致性同步主要使用在對(duì)預(yù)備狀態(tài)WBD 的同步上。這些WBD 并不用于提供元數(shù)據(jù)服務(wù)，因此其數(shù)據(jù)一致性要求相對(duì)較低，由節(jié)點(diǎn)自行決定在何時(shí)同步，其同步方法可以直接采用分布式文件系統(tǒng)數(shù)據(jù)同步的方法。

2.3 SAMS的自適應(yīng)特性

SAMS的自適應(yīng)特性包括控制節(jié)點(diǎn)的自適應(yīng)性、工作節(jié)點(diǎn)的自適應(yīng)性和命名空間的自適應(yīng)性。

2.3.1 控制節(jié)點(diǎn)的自適應(yīng)性

由于節(jié)點(diǎn)都是對(duì)等的，當(dāng)集群需要一個(gè)新的控制節(jié)點(diǎn)時(shí)（比如第一次運(yùn)行或是原控制節(jié)點(diǎn)宕機(jī)），SAMS可以通過(guò)控制節(jié)點(diǎn)選舉算法從所有節(jié)點(diǎn)中快速選出一個(gè)新的控制節(jié)點(diǎn)，因此SAMS中的控制節(jié)點(diǎn)是具有自適應(yīng)性的。

從易于實(shí)現(xiàn)的角度出發(fā)，SAMS采用了一種仿效Paxos的兩階段選舉算法SimpleElect，通過(guò)節(jié)點(diǎn)之間的消息傳遞，實(shí)現(xiàn)控制節(jié)點(diǎn)的選舉。按照SimpleElect算法，選舉過(guò)程分為Propose和Accept兩個(gè)階段，每個(gè)階段又包括Request和Response兩個(gè)部分，系統(tǒng)中同一時(shí)刻可能存在多個(gè)正在進(jìn)行的選舉，但只有一個(gè)選舉能夠完整執(zhí)行Accept階段，并完成選舉。SimpleElect算法中，同一節(jié)點(diǎn)可以同時(shí)扮演兩種角色Proposer和Acceptor，分別用于發(fā)起選舉和接受選舉。當(dāng)某工作節(jié)點(diǎn)發(fā)現(xiàn)控制節(jié)點(diǎn)宕機(jī)時(shí)，開(kāi)始執(zhí)行SimpleElect，發(fā)起選舉，算法流程如下：

（1）Propose request：Proposer向Acceptor廣播選舉請(qǐng)求消息，內(nèi)容為選舉編號(hào)和節(jié)點(diǎn)ID。每個(gè)Proposer的選舉編號(hào)都從1開(kāi)始，按選舉次數(shù)遞增。

（2）Propose response：Acceptor接收到選舉請(qǐng)求消息后，判斷收到的選舉編號(hào)是否大于本地緩存的最大選舉編號(hào)：是，則緩存新編號(hào)，并回復(fù)接受消息，內(nèi)容為Acceptor之前緩存的最大選舉編號(hào)；否，回復(fù)拒絕消息；

（3）Accept request：Proposer接收到回復(fù)消息后，判斷回復(fù)消息的內(nèi)容是否為空：是，進(jìn)入（4）；否，終止當(dāng)前選舉；

（4）Accept request：Proposer接收到全部回復(fù)消息后，判斷是否超過(guò)半數(shù)回復(fù)為接受：是，Proposer廣播選舉確認(rèn)消息，內(nèi)容與選舉請(qǐng)求消息一致；否，隨機(jī)等待一段時(shí)間，提高選舉編號(hào)，重啟Propose過(guò)程；

（5）Accept response：Acceptor收到選舉確認(rèn)消息后，將控制節(jié)點(diǎn)設(shè)置為Proposer的節(jié)點(diǎn)ID，清空緩存的選舉編號(hào)，返回確認(rèn)消息。

（6）Accept response：Proposer判斷接收到的確認(rèn)消息是否超過(guò)半數(shù)：是，Proposer改變工作狀態(tài)，成為新的控制節(jié)點(diǎn)，選舉結(jié)束；否，重啟選舉過(guò)程。

2.3.2 工作節(jié)點(diǎn)的自適應(yīng)性

當(dāng)工作節(jié)點(diǎn)數(shù)目發(fā)生變化時(shí)，控制節(jié)點(diǎn)會(huì)自動(dòng)進(jìn)行處理：

（1）新工作節(jié)點(diǎn)上線時(shí)，控制節(jié)點(diǎn)會(huì)計(jì)算應(yīng)分配給新節(jié)點(diǎn)的子命名空間，并將分配信息和WBD 備份數(shù)據(jù)集發(fā)送給新節(jié)點(diǎn)，新節(jié)點(diǎn)通過(guò)這些數(shù)據(jù)重建WBD 工作數(shù)據(jù)集，并開(kāi)始提供元數(shù)據(jù)服務(wù)。

（2）某工作節(jié)點(diǎn)宕機(jī)時(shí)，控制節(jié)點(diǎn)對(duì)當(dāng)前命名空間的劃分情況進(jìn)行評(píng)估，判斷是否需要對(duì)分布情況進(jìn)行調(diào)整，并根據(jù)判斷結(jié)果進(jìn)行相應(yīng)操作。

2.3.3 命名空間的自適應(yīng)性

控制節(jié)點(diǎn)會(huì)根據(jù)每個(gè)子命名空間對(duì)應(yīng)的WBD 的數(shù)據(jù)量大小，對(duì)命名空間的劃分進(jìn)行動(dòng)態(tài)調(diào)整。

（1）當(dāng)WBD 數(shù)據(jù)量過(guò)大，接近節(jié)點(diǎn)內(nèi)存上限時(shí)，控制節(jié)點(diǎn)會(huì)對(duì)該WBD 對(duì)應(yīng)的子命名空間進(jìn)行進(jìn)一步的劃分，并通過(guò)WBD 的分裂操作將該WBD 分成兩個(gè)新的WBD，并重新分配到其它節(jié)點(diǎn)上進(jìn)行管理。

（2）當(dāng)WBD 數(shù)據(jù)量過(guò)小，導(dǎo)致WBD 個(gè)體數(shù)量過(guò)多時(shí)，控制節(jié)點(diǎn)會(huì)對(duì)多余的子命名空間進(jìn)行合并，并使用WBD 的合并操作將該WBD 合并到同級(jí)WBD 中。

2.4 比 較

SAMS與HDFS Federation元數(shù)據(jù)模型的對(duì)比見(jiàn)表4。

表4 SAMS與HDFS Federation元數(shù)據(jù)模型的對(duì)比

3 實(shí)驗(yàn)分析

本文首先在Linux環(huán)境下通過(guò)Java對(duì)WBD 進(jìn)行了實(shí)現(xiàn)，并以HDFS Federation（Hadoop 0.23.0）為基礎(chǔ)實(shí)現(xiàn)了一個(gè)SAMS原型系統(tǒng)。實(shí)現(xiàn)過(guò)程中，最大化的利用了HDFS原有代碼，包括命名空間劃分算法、備份數(shù)據(jù)集同步等算法和功能都通過(guò)HDFS原有代碼進(jìn)行實(shí)現(xiàn)。原型系統(tǒng)部署在4個(gè)元數(shù)據(jù)節(jié)點(diǎn)，10個(gè)數(shù)據(jù)節(jié)點(diǎn)的實(shí)驗(yàn)集群上，各節(jié)點(diǎn)通過(guò)千兆網(wǎng)卡連接，所采用的服務(wù)器硬件指標(biāo)見(jiàn)表5。實(shí)驗(yàn)中使用約800G各類數(shù)據(jù)存儲(chǔ)在HDFS中作為實(shí)驗(yàn)數(shù)據(jù)。

表5 服務(wù)器硬件指標(biāo)

3.1 文件I／O 性能基準(zhǔn)實(shí)驗(yàn)

本實(shí)驗(yàn)對(duì)SAMS 的文件I／O 性能進(jìn)行測(cè)試，通過(guò)與HDFS Federation和HDFS進(jìn)行對(duì)比，分析SAMS 的I／O性能特征。實(shí)驗(yàn)方法：采用LoadRunner模擬100用戶進(jìn)行并發(fā)讀／寫(xiě)操作，記錄平均響應(yīng)時(shí)間。為了不相互干擾，讀寫(xiě)實(shí)驗(yàn)分開(kāi)進(jìn)行，讀／寫(xiě)操作每次隨機(jī)讀?。瘜?xiě)入大小為100K 的數(shù)據(jù)塊。

圖5顯示了3種系統(tǒng)對(duì)讀／寫(xiě)操作的平均響應(yīng)時(shí)間，可以看到，3 種系統(tǒng)的文件讀取操作響應(yīng)時(shí)間基本持平，SAMS的寫(xiě)操作響應(yīng)時(shí)間要略低于HDFS Federation 和HDFS約15ms，分析其原因在于：HDFS和HDFS Federation每完成一次元數(shù)據(jù)操作會(huì)將其記錄到editlog中，帶來(lái)一定的磁盤(pán)I／O；而在SAMS中，除了持久化，所有元數(shù)據(jù)操作均在內(nèi)存中完成，提高了元數(shù)據(jù)訪問(wèn)效率。

圖5 I／O 操作響應(yīng)時(shí)間對(duì)比

本實(shí)驗(yàn)結(jié)果充分說(shuō)明，WBD 能夠有效地降低分布式元數(shù)據(jù)管理帶來(lái)的額外性能開(kāi)銷；并且，由于采用了全內(nèi)存的元數(shù)據(jù)管理，使整體文件I／O 性能得到了微小的提升。

3.2 容錯(cuò)性實(shí)驗(yàn)

3.2.1 元數(shù)據(jù)可用性實(shí)驗(yàn)

本實(shí)驗(yàn)測(cè)試節(jié)點(diǎn)宕機(jī)對(duì)SAMS 文件訪問(wèn)的影響，以HDFS Federation為對(duì)比。實(shí)驗(yàn)方法：通過(guò)shell腳本讓一臺(tái)元數(shù)據(jù)服務(wù)器在測(cè)試中自行斷開(kāi)網(wǎng)絡(luò)，模擬服務(wù)器宕機(jī)的情況。在宕機(jī)前后，分別采用LoadRunner模擬10000次隨機(jī)讀取操作，記錄宕機(jī)前后文件讀取操作的成功次數(shù)。結(jié)果見(jiàn)表6，當(dāng)HDFS Federation元數(shù)據(jù)節(jié)點(diǎn)宕機(jī)時(shí)，會(huì)導(dǎo)致部分文件無(wú)法訪問(wèn)，而SAMS由于采用了多重冗余設(shè)計(jì)，單個(gè)元數(shù)據(jù)節(jié)點(diǎn)故障不影響文件的訪問(wèn)。

表6 宕機(jī)前后讀操作成功率對(duì)比

3.2.2 宕機(jī)性能影響實(shí)驗(yàn)

本實(shí)驗(yàn)通過(guò)對(duì)比正常運(yùn)行、工作節(jié)點(diǎn)宕機(jī)和3種控制節(jié)點(diǎn)宕機(jī)情況下元數(shù)據(jù)的查詢效率，測(cè)試節(jié)點(diǎn)宕機(jī)對(duì)SAMS元數(shù)據(jù)服務(wù)性能的影響。實(shí)驗(yàn)方法：通過(guò)LoadRunner模擬100用戶并行執(zhí)行元數(shù)據(jù)隨機(jī)查詢，并通過(guò)shell腳本讓指定服務(wù)器在測(cè)試開(kāi)始600 秒左右自行斷開(kāi)網(wǎng)絡(luò)，輸出操作執(zhí)行的TPS曲線，分析丟失節(jié)點(diǎn)時(shí)SAMS元數(shù)據(jù)服務(wù)的性能變化。結(jié)果如圖6，在正常運(yùn)行的狀態(tài)下，元數(shù)據(jù)查詢操作的TPS曲線快速上升并保持在27000左右；在工作節(jié)點(diǎn)宕機(jī)的對(duì)照組中，可以看到隨著控制節(jié)點(diǎn)宕機(jī)，元數(shù)據(jù)查詢操作TPS迅速下降到約16000，并最終穩(wěn)定在17000左右，原因在于工作節(jié)點(diǎn)的宕機(jī)，導(dǎo)致提供元數(shù)據(jù)服務(wù)的節(jié)點(diǎn)減少，服務(wù)性能下降；在控制節(jié)點(diǎn)宕機(jī)的對(duì)照組中，控制節(jié)點(diǎn)宕機(jī)后，經(jīng)過(guò)了一小段時(shí)間，元數(shù)據(jù)查詢操作TPS才快速下降到約15000，并同樣穩(wěn)定在17000左右，原因是當(dāng)控制節(jié)點(diǎn)剛剛宕機(jī)時(shí)，對(duì)集群性能并無(wú)太大影響，但是當(dāng)某個(gè)工作節(jié)點(diǎn)被選舉為新的控制節(jié)點(diǎn)后，服務(wù)節(jié)點(diǎn)減少，集群狀態(tài)與工作節(jié)點(diǎn)宕機(jī)后的集群狀態(tài)保持一致。

容錯(cuò)性實(shí)驗(yàn)表明，丟失節(jié)點(diǎn)雖然會(huì)造成一定的性能下降，但不會(huì)導(dǎo)致元數(shù)據(jù)服務(wù)的失敗，SAMS具有較好的容錯(cuò)性，保證了元數(shù)據(jù)服務(wù)的高可用性。

3.3 擴(kuò)展性實(shí)驗(yàn)

本實(shí)驗(yàn)通過(guò)增加新的元數(shù)據(jù)節(jié)點(diǎn)，測(cè)試SAMS的擴(kuò)展能力。實(shí)驗(yàn)方法：通過(guò)LoadRunner模擬100用戶并行執(zhí)行元數(shù)據(jù)隨機(jī)查詢，并從600s開(kāi)始，每300s增加一個(gè)工作節(jié)點(diǎn)，總共增加3個(gè)，輸出操作執(zhí)行的TPS曲線，分析增加節(jié)點(diǎn)時(shí)SAMS元數(shù)據(jù)服務(wù)的性能變化。圖7展示了元數(shù)據(jù)隨機(jī)查詢操作的TPS曲線，在3次增加新節(jié)點(diǎn)后，SAMS性能都出現(xiàn)階梯狀增長(zhǎng)，表明SAMS的性能與節(jié)點(diǎn)數(shù)量呈現(xiàn)出一定的線性關(guān)系，具有良好的橫向擴(kuò)展性。

圖6 宕機(jī)實(shí)驗(yàn)元數(shù)據(jù)查詢操作TPS

圖7 擴(kuò)展實(shí)驗(yàn)元數(shù)據(jù)查詢操作TPS

4 結(jié)束語(yǔ)

本文針對(duì)分布式文件系統(tǒng)元數(shù)據(jù)管理模型存在的不足，重點(diǎn)論述了WBD 的構(gòu)造、狀態(tài)和操作，設(shè)計(jì)并實(shí)現(xiàn)了一種分布式文件系統(tǒng)元數(shù)據(jù)管理模型SAMS。實(shí)驗(yàn)分析表明，采用SAMS作為分布式文件系統(tǒng)的元數(shù)據(jù)管理模型，在維持元數(shù)據(jù)服務(wù)性能的基礎(chǔ)上，實(shí)現(xiàn)了高容錯(cuò)性和高擴(kuò)展性。下一步的研究重點(diǎn)是在更大規(guī)模的集群中測(cè)試WBD 和SAMS的性能特點(diǎn)，并對(duì)其進(jìn)行優(yōu)化。

［1］WU Wei.Research on metadata management in large－scale storage system ［D］.Wuhan：Huazhong University of Science and Technology，2010 （in Chinese）.［吳偉.海量存儲(chǔ)系統(tǒng)元數(shù)據(jù)管理的研究 ［D］.武漢：華中科技大學(xué)，2010.］

［2］LIU Aigui.Metadata service model for distributed file systems［EB／OL］.［2011－09－05］.http：／／blog.csdn.net／liuaigui／article／details／6749188.（in Chinese）.［劉愛(ài)貴.分布式文件系統(tǒng)元數(shù)據(jù)服務(wù)模型［EB／OL］.［2011－09－05］.http：／／blog.csdn.net／liuaigui／article／details／6749188.］

［3］Wikipedia.Google file system［EB／OL］.［2013－01－30］.http：／／en.wi－kipedia.org／wiki／Google＿File＿System.

［4］The Apache Software Foundation.HDFS architecture guide［EB／OL］.［2011－05－04］.http：／／hadoop.apache.org／common／docs／current／hdfs＿design.html.

［5］Oracle.Lustre internals documentation［EB／OL］.［2010－04－06］.http：／／wiki.lustre.org／lid／index.html.

［6］ZHAO Yuelong，XIE Xiaoling，CAI Yongcai，et al.A strategy of small file storage access with performance optimization［J］.Journal of Computer Research and Development，2012，49 （7）：1579－1586 （in Chinese）.［趙躍龍，謝曉玲，蔡詠才，等.一種性能優(yōu)化的小文件存儲(chǔ)訪問(wèn)策略的研究 ［J］.計(jì)算機(jī)研究與發(fā)展，2012，49 （7）：1579－1586.］

［7］LIU Lian，ZHENG Biao，GONG Yili.Metadata processing optimization in distributed file systems［J］.Journal of Computer Applications，2012，32（12）：3271－3273（in Chinese）.［劉戀，鄭彪，龔奕利.分布式文件系統(tǒng)中元數(shù)據(jù)操作的優(yōu)化［J］.計(jì)算機(jī)應(yīng)用，2012，32（12）：3271－3273.］

［8］LIU Aigui.Research of the GlusterFS ［EB／OL］.［2011－09－05］.http：／／blog.csdn.net／liuaigui／article／details／6284551.（in Chinese）.［劉愛(ài)貴.GlusterFS集群文件系統(tǒng)研究［EB／OL］.［2011－03－28］.http：／／blog.csdn.net／liuaigui／article／details／6284551.］

［9］XUE Wei，ZHU Ming.Dynamic management system of distributed metadata ［J］.Computer Engineering，2012，38（4）：63－66 （in Chinese）.［薛偉，朱明.一種分布式元數(shù)據(jù)的動(dòng)態(tài)管理系統(tǒng) ［J］.計(jì)算機(jī)工程，2012，38 （4）：63－66.］

［10］CAI Tao，NIU Dejiao，LIU Yangkuan，et al.NVMMDS：Metadata management method based on non－volatile memory［J］.Journal of Computer Research and Development，2013，50 （1）：69－79 （in Chinese）.［蔡濤，牛德姣，劉揚(yáng)寬，等.NVMMDS——一種面向非易失存儲(chǔ)器的元數(shù)據(jù)管理方法［J］.計(jì)算機(jī)研究與發(fā)展，2013，50 （1）：69－79.］

［11］DONG Xicheng.Introduction of HDFS federation［EB／OL］.［2011－12－01］.http：／／dongxicheng.org／mapreduce／hdfs－federation－introduction／（in Chinese）.［董西成.HDFS Federation設(shè)計(jì)動(dòng)機(jī)與基本原理［EB／OL］.［2011－12－01］.http：／／dongxicheng.org／mapreduce／hdfs－federation－intro－duction／.］

［12］Zaharia M，Chowdhury M，Das T，et al.Resilient distributed datasets，a fault－tolerant abstraction for in－memory cluster computing ［R］.San Francisco：University of California at Berkeley，Technical Report No.UCB／EECS－2011－82，2011.