一種應(yīng)用于網(wǎng)絡(luò)硬盤(pán)存儲(chǔ)系統(tǒng)的一致性協(xié)議

劉青昆，石彥博，梁 瑩

(遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧 大連116081)

在信息技術(shù)飛速發(fā)展的今天，企業(yè)和個(gè)人所擁有的數(shù)據(jù)總量在不斷地增加，而且為了能夠更好地協(xié)同工作，人們對(duì)數(shù)據(jù)共享的需求也日益旺盛。相比將大量數(shù)據(jù)放置在本地，越來(lái)越多的人們開(kāi)始選擇使用網(wǎng)絡(luò)硬盤(pán)系統(tǒng)來(lái)保存數(shù)據(jù)。網(wǎng)絡(luò)硬盤(pán)系統(tǒng)所提供的高可靠性及可用性使得用戶所上傳的數(shù)據(jù)不易丟失，而且隨時(shí)可以獲取[1]。

近些年，針對(duì)一致性協(xié)議的研究與設(shè)計(jì)逐漸成為分布式系統(tǒng)領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題[2-3]。而新興的網(wǎng)絡(luò)硬盤(pán)系統(tǒng)與其他的分布式存儲(chǔ)系統(tǒng)一樣面臨著同樣的問(wèn)題，即它們都需要在一致性和可用性之間尋找一個(gè)較為合理的平衡點(diǎn)。本文在一款由清華大學(xué)所研制的網(wǎng)盤(pán)系統(tǒng)——Corsbox的基礎(chǔ)之上，為其設(shè)計(jì)一種用于客戶端之間進(jìn)行共享操作的一致性協(xié)議，使得該網(wǎng)盤(pán)系統(tǒng)在此種情況下具有高可用性和低延遲的特點(diǎn)。

1 背景知識(shí)

系統(tǒng)中保存的數(shù)據(jù)被某一客戶端更新時(shí)，可以根據(jù)其余客戶端何時(shí)能夠看到此更新的數(shù)據(jù)來(lái)對(duì)一致性進(jìn)行分類(lèi)。強(qiáng)一致性是指當(dāng)系統(tǒng)中的數(shù)據(jù)更新完成以后，任何后續(xù)的客戶端訪問(wèn)此數(shù)據(jù)時(shí)都能夠返回更新過(guò)的值；弱一致性是指系統(tǒng)不能保證當(dāng)數(shù)據(jù)更新完成以后，客戶端的后續(xù)訪問(wèn)能夠返回更新過(guò)的值；最終一致性是指系統(tǒng)保證如果用戶數(shù)據(jù)在沒(méi)有新的更新操作發(fā)生的情況下，最終所有對(duì)此數(shù)據(jù)的訪問(wèn)都將返回最后更新過(guò)的值。

分布式共享存儲(chǔ)系統(tǒng)在理想情況下應(yīng)該同時(shí)具有強(qiáng)一致性、系統(tǒng)可用性和網(wǎng)絡(luò)分區(qū)容忍性。但不幸的是，Eric Brewer的CAP[4]理論證明了這三者不可能同時(shí)實(shí)現(xiàn)，并指出任何系統(tǒng)在任一時(shí)刻只能滿足其中兩條性質(zhì)。在網(wǎng)絡(luò)分區(qū)已經(jīng)成為一種基本要求的情況下，分布式系統(tǒng)的設(shè)計(jì)者幾乎一邊倒地選擇了可用性而放棄了強(qiáng)一致性。之所以如此是因?yàn)閷?duì)于大多數(shù)應(yīng)用來(lái)說(shuō)，并不一定需要強(qiáng)一致性；而且選擇可用性不僅可以降低系統(tǒng)響應(yīng)客戶端請(qǐng)求時(shí)的延遲，還能增加系統(tǒng)的可擴(kuò)展性。Wyatt Lloyd[5]等人將具有可用性（Availability）、低延遲（Low latency）、分區(qū)可容忍性(Partition-tolerance)和可擴(kuò)展性(Scalability)這4種特性的系統(tǒng)稱之為ALPS系統(tǒng)?，F(xiàn)如今有很多系統(tǒng)同時(shí)具有ALPS這4種特性，如Dynamo[6]、Voldemort[7]和Memcached[8]等一些具有最終一致性特點(diǎn)的鍵值對(duì)存儲(chǔ)系統(tǒng)。Facebook的Cassandra[9]是一種可配置的系統(tǒng)，可以根據(jù)需要設(shè)置其具有上述4種特性，也可以視具體情況使其具有線性一致性。本文將為一款網(wǎng)絡(luò)硬盤(pán)系統(tǒng)——Corsbox設(shè)計(jì)一種一致性協(xié)議，使得該網(wǎng)盤(pán)在移動(dòng)、刪除和重命名共享目錄或文件的過(guò)程中具有高可用性和低延遲的特點(diǎn)，加之Corsbox網(wǎng)盤(pán)在網(wǎng)絡(luò)分區(qū)的情況下本身就有很強(qiáng)的擴(kuò)展能力，所以使其滿足了成為ALPS系統(tǒng)所需要的所有條件。

2 網(wǎng)絡(luò)硬盤(pán)與底層云存儲(chǔ)系統(tǒng)

大部分網(wǎng)絡(luò)硬盤(pán)系統(tǒng)通常由客戶端、服務(wù)器端和底層的云存儲(chǔ)端3個(gè)部分組成。云存儲(chǔ)是云計(jì)算技術(shù)的發(fā)展和延伸，云端將用戶數(shù)據(jù)分布在由大量計(jì)算機(jī)節(jié)點(diǎn)構(gòu)成的資源池中，由于云存儲(chǔ)系統(tǒng)使用了特殊的容錯(cuò)機(jī)制，所以可以采購(gòu)一些價(jià)格相對(duì)低廉的節(jié)點(diǎn)構(gòu)成云，而且還可以將各種不同類(lèi)型的存儲(chǔ)設(shè)備集合起來(lái)協(xié)同工作。為了降低運(yùn)營(yíng)成本，大部分網(wǎng)絡(luò)硬盤(pán)都不會(huì)自己搭建底層的云存儲(chǔ)系統(tǒng)，而是轉(zhuǎn)而與大型的云存儲(chǔ)供應(yīng)商合作。

Corsbox網(wǎng)絡(luò)硬盤(pán)采用的底層云存儲(chǔ)系統(tǒng)是開(kāi)源的OpenStack Swift[10]，它具有極高的數(shù)據(jù)持久性、數(shù)據(jù)冗余和高擴(kuò)展性等特點(diǎn)。OpenStack并不是傳統(tǒng)文件系統(tǒng)，它為每一個(gè)使用者創(chuàng)建一個(gè)賬戶（Account），用戶可以在其賬戶下建立多個(gè)容器（Container），并將數(shù)據(jù)文件以對(duì)象（Object）的形式存放在其中，這一點(diǎn)與Amazon S3[11]很相似。

Corsbox網(wǎng)盤(pán)在設(shè)計(jì)上規(guī)定了以目錄為最小的共享單位，并且允許目錄的所有者與被共享者都有權(quán)移動(dòng)、重命名和刪除此目錄及其中的文件。由于OpenStack Swift[10]在處理刪除、移動(dòng)和重命名等操作時(shí)只能確保數(shù)據(jù)的最終一致性，也就是說(shuō)某一用戶對(duì)數(shù)據(jù)的修改不會(huì)立刻得到更新，所以當(dāng)多個(gè)用戶在共享同一數(shù)據(jù)時(shí)，網(wǎng)盤(pán)系統(tǒng)不可能滿足他們之間的強(qiáng)一致性需求。并且即便Swift底層云存儲(chǔ)系統(tǒng)能夠確保強(qiáng)一致性，由于共享用戶不可能同時(shí)在線的原因，也無(wú)法做到在任何時(shí)刻，所有用戶所共享的數(shù)據(jù)都是一致的。因此需要為網(wǎng)絡(luò)硬盤(pán)系統(tǒng)設(shè)計(jì)一種一致性協(xié)議，來(lái)保證共享用戶在目錄或文件不會(huì)再發(fā)生任何改變時(shí)，他們所看到的視圖都是相同的。

3 一致性協(xié)議設(shè)計(jì)

本文在描述為Corsbox網(wǎng)絡(luò)硬盤(pán)系統(tǒng)所設(shè)計(jì)的一致性協(xié)議時(shí)，以用戶操作共享文件為例進(jìn)行說(shuō)明。假設(shè)網(wǎng)盤(pán)系統(tǒng)中有5名用戶A、B、C、D、E，他們共享了同一目錄，其中用戶A是此共享目錄的擁有者，目錄的路徑為：Corsbox/album，其余用戶都是被共享者。在共享目錄中存有兩個(gè)子目錄sarah和enya，sarah目錄下有一音頻文件living.mp3。按照如下順序?qū)蚕砟夸浿械奈募M(jìn)行操作：

(1)B、C、D 3名用戶首先上線，并一直保持在線狀態(tài)，且此時(shí)不對(duì)共享文件做任何操作；

(2)用戶E和用戶A登錄，并在其后的任一時(shí)刻退出系統(tǒng)；

(3)用戶B、C在用戶E和用戶A登錄網(wǎng)盤(pán)之后分別對(duì)共享文件進(jìn)行操作，B用戶將living.mp3改名為journay.mp3，C用戶將living.mp3移動(dòng)至enya目錄下；

(4)用戶E再次登錄，并在其后任意時(shí)間下線；

(5)用戶D在用戶E再次登錄后將共享文件living.mp3改名為crazy.mp3；

(6)用戶A再次登錄網(wǎng)盤(pán)系統(tǒng)。

在如上所述的操作系列下，本文所設(shè)計(jì)的協(xié)議會(huì)按照時(shí)間先后順序記錄下每個(gè)用戶的登錄情況和對(duì)共享文件的操作。當(dāng)用戶E在步驟(4)中再次登錄時(shí)，網(wǎng)盤(pán)系統(tǒng)會(huì)根據(jù)記錄向上搜索，直至找到其上一次的登錄記錄為止。在搜索過(guò)程中，系統(tǒng)獲取了在用戶E的兩次登錄之間，B、C分別對(duì)共享文件進(jìn)行了操作。當(dāng)搜索工作結(jié)束之后，本協(xié)議會(huì)對(duì)由用戶A在云端所保存的這一共享文件做統(tǒng)一處理，即分別向云端發(fā)出B、C兩者對(duì)此文件的操作請(qǐng)求。之后網(wǎng)盤(pán)系統(tǒng)會(huì)根據(jù)本文所設(shè)計(jì)的協(xié)議將B、C的操作信息發(fā)送至用戶E，E的客戶端會(huì)根據(jù)這一信息，按照B、C的操作順序依次修改本地的共享文件。在進(jìn)入到步驟(6)時(shí)，用戶A再次上線，網(wǎng)盤(pán)系統(tǒng)同樣會(huì)向前搜索至其上一次登錄的時(shí)間點(diǎn)，此時(shí)系統(tǒng)會(huì)檢測(cè)到在這一時(shí)間段內(nèi)B、C、D都對(duì)共享文件進(jìn)行了操作，而且用戶B、C的請(qǐng)求已經(jīng)在云端完成，所以網(wǎng)盤(pán)系統(tǒng)現(xiàn)在只需要處理D用戶的操作請(qǐng)求即可。在完成了云端同步之后，B、C、D 3者的操作信息會(huì)被發(fā)送給用戶A，由于用戶A的客戶端之前沒(méi)有處理過(guò)B、C的操作，所以此時(shí)會(huì)連同D的操作按次序一并處理。需要注意的是，當(dāng)這5位用戶中的任意一個(gè)對(duì)共享文件做了刪除操作時(shí)，其余用戶在此后對(duì)這一文件的操作都將被忽略。具體操作流程如圖1所示。

圖1 用戶操作共享文件的流程

使用本文為網(wǎng)盤(pán)系統(tǒng)所設(shè)計(jì)的上述協(xié)議可以帶來(lái)很多優(yōu)點(diǎn)：

(1)此協(xié)議可以很好地適應(yīng)OpenStack Swift底層云存儲(chǔ)系統(tǒng)的最終一致性特點(diǎn)。

(2)用戶對(duì)共享目錄及文件的移動(dòng)、刪除和重命名操作會(huì)得到網(wǎng)盤(pán)系統(tǒng)的迅速響應(yīng)，因?yàn)榫W(wǎng)盤(pán)系統(tǒng)并沒(méi)有立刻向底層云系統(tǒng)轉(zhuǎn)發(fā)用戶的操作請(qǐng)求，而只是將其操作記錄下來(lái)而已。具體的底層操作會(huì)推遲到其后任一用戶登錄時(shí)進(jìn)行，即網(wǎng)盤(pán)系統(tǒng)會(huì)在各個(gè)用戶上線時(shí)對(duì)他們進(jìn)行同步操作，這也是現(xiàn)行大多數(shù)網(wǎng)盤(pán)的通行做法。

(3)網(wǎng)盤(pán)系統(tǒng)推遲了對(duì)用戶的操作請(qǐng)求，不會(huì)對(duì)共享此目錄或文件的用戶和其余被共享者造成任何使用上的影響。

(4)由于協(xié)議嚴(yán)格地按照時(shí)間先后順序執(zhí)行各個(gè)用戶的請(qǐng)求，所以最終共享用戶所看到的目錄及文件視圖不會(huì)有混亂不一致的情況發(fā)生。

(5)本協(xié)議在處理由各共享用戶的操作所引起的沖突時(shí)，使用了類(lèi)似last-writer-wins[12]的原則，即最后修改共享目錄或文件的操作將覆蓋掉之前其余所有用戶的操作（除刪除操作）。它不同于Coda[13]和Dynamo[6]等一些系統(tǒng)需要客戶端直接人為地介入來(lái)解決沖突問(wèn)題。

4 一致性協(xié)議的實(shí)現(xiàn)

為了實(shí)現(xiàn)所設(shè)計(jì)的協(xié)議，在網(wǎng)盤(pán)系統(tǒng)中引入了MySQL數(shù)據(jù)庫(kù)，每當(dāng)用戶共享一個(gè)新的目錄給其他用戶時(shí)，系統(tǒng)都會(huì)為其生成一張數(shù)據(jù)表與之對(duì)應(yīng)，此后所有共享此目錄的用戶的登錄操作和對(duì)這一共享目錄及其所包含的子目錄和文件的刪除、移動(dòng)、重命名操作都會(huì)被記錄到這張表上。當(dāng)有用戶登錄進(jìn)行數(shù)據(jù)同步時(shí)，網(wǎng)盤(pán)系統(tǒng)根據(jù)協(xié)議只需對(duì)該表做降序搜索即可，并將搜索到的各個(gè)用戶的操作信息保存在特定的數(shù)據(jù)結(jié)構(gòu)中。此數(shù)據(jù)結(jié)構(gòu)的具體成員如表1所示。

用戶E在登錄網(wǎng)盤(pán)以后，記錄在數(shù)據(jù)結(jié)構(gòu)中的具體信息如表2所示，其中path項(xiàng)中的“&”符號(hào)用于分隔文件的新舊路徑。網(wǎng)盤(pán)系統(tǒng)在執(zhí)行第一條操作之后會(huì)對(duì)表中的第二條記錄做預(yù)處理，即B用戶重命名后的新路徑替換第二條記錄中path項(xiàng)的原有路徑，替換后的結(jié)果為Corsbox/album/sarah/journay.mp3&Corsbox/album/enya/，這 樣網(wǎng)盤(pán)在其后操作第二條記錄時(shí)就能夠作出正確處理。

表2 E登錄后數(shù)據(jù)結(jié)構(gòu)中的具體信息

當(dāng)用戶A再次登錄網(wǎng)盤(pán)時(shí)，數(shù)據(jù)結(jié)構(gòu)中的信息如表3所示。由于用戶B、C的操作已經(jīng)在底層云端處理妥當(dāng)，此時(shí)網(wǎng)盤(pán)只需在云端執(zhí)行第三條操作記錄即可。但是在這之前，還是需要對(duì)第二、三條記錄中的path項(xiàng)做兩次循環(huán)替換，替換后的最終結(jié)果如表4所示。

表3 A再次登錄后數(shù)據(jù)結(jié)構(gòu)中的具體信息

表4 處理后的信息

Corsbox網(wǎng)絡(luò)硬盤(pán)系統(tǒng)在經(jīng)過(guò)了這一系列處理之后，A、B、C、D、E這5位用戶在云端所對(duì)應(yīng)的共享文件達(dá)到最終一致。共享用戶在客戶端的一致性操作與在云端的大致相同，不再累述。

本文為一款網(wǎng)絡(luò)硬盤(pán)系統(tǒng)——Corsbox設(shè)計(jì)了一種一致性協(xié)議，從而使得該系統(tǒng)具備了高可用性和低延遲等特點(diǎn)。這意味著該網(wǎng)絡(luò)硬盤(pán)系統(tǒng)擁有了成為ALPS系統(tǒng)所需要的所有條件。當(dāng)該網(wǎng)絡(luò)硬盤(pán)系統(tǒng)使用此協(xié)議時(shí)，能夠高效、快速地處理用戶對(duì)共享目錄及文件的操作請(qǐng)求，并達(dá)到最終一致。

[1]Zeng Wenying，Zhao Yuelong，Ou Kairi，et al.Research on cloud storage architecture and key technologies[C].Proceedings of the 2nd International Conference on Interaction Sciences：Information Technology，Culture and Human，Seoul：2009：1044-1048.

[2]COOPER B F，RAMAKRISHNAN R，SRIVASTAVA U，et al.PNUTS∶Yahoo！’s hosted data serving platform[J].Proceedings of the VLDB Endowment，2008，1(2)：1277-1288.

[3]SOVRAN Y，POWER R，AGUILERA M K，et al.Transactional storage for geo-replicated systems[C].Proceedings of the 23rd ACM Symposium on Operating Systems Principles，Cascais：2011：385-400.

[4]BREWER E.Towards robust distributed systems[C].Proceedings of the 19th annual ACM symposium on Principles of distributed computing，ACM，2000：7.

[5]LLOYD W，F(xiàn)REEDMAN M J，KAMINSKY M，et al.Don’t settle for eventual：scalable causal consistency for wide-area storage with COPS[C].Proceedings of the 23rd ACM Symposium on Operating Systems Principles，Cascais：2011：401-416.

[6]CANDIA G D，HASTORUN D，JAMPANJ M，et al.Dynamo：Amazon’s highly available key-value store[J].Operating systems review，2007，41(6)：205-220.

[7]SUMBALY R，KREPS J，Gao Lei et al.Serving large-scale batch computed data with project Voldemort[C].Proceedings of the 10th USENIX conference on File and Storage Technologies，2012：18.

[8]FITZPATRICK B.Distributed caching with memcached[J].Linux Journal，2004(124)：5.

[9]LAKSHMAN A，MALIK P.Cassandra-a decentralized structured storage system[J].ACM SIGOPS Operating Systems Review，2009，44(2)：35-40.

[10]TAHERIMONFARED A，JAATUN M G.As strong as the weakest link：handling compromised components in open-Stack[C].Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science，Athens：2011：189-196.

[11]YOON H，GAVRILOVSKA A，SCHWAN K，et al.Interactive use of cloud services：Amazon SQS and S3[C].Proceedings of the 2012 twelfth IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing，Ottawa：2012：523-530.

[12]THOMAS R H，BERANEK B，NEWMAN.A majority consensus approach to concurrency control for multiple copy databases[J].ACM Transactions on Database Systems，1979，4(2)：180-209.

[13]KISTLER J，SATYANARAYANAN M.Disconnected operation in the Coda file system[J].ACM Transactions on Computer Systems，1992，10(1)：3-25.