摘  要： 通常網絡硬盤系統會向用戶提供高可用性和低延遲的網絡服務，并且通過對不同程度上的一致性進行選取，從而尋找可用性、低延遲與一致性這三者的平衡。高一致性意味著系統將會犧牲掉一定的可用性，但低一致性會增加程序設計的難度。為一款網絡硬盤系統設計一種一致性協議，使得該網盤可以高效地處理用戶對共享目錄或文件的移動、刪除和重命名等操作，與此同時還能確保共享目錄及文件在各個客戶端中不會有混亂無序的情況出現。
關鍵詞： 網絡硬盤存儲系統；一致性協議；可用性；可擴展性

    在信息技術飛速發展的今天，企業和個人所擁有的數據總量在不斷地增加，而且為了能夠更好地協同工作，人們對數據共享的需求也日益旺盛。相比將大量數據放置在本地，越來越多的人們開始選擇使用網絡硬盤系統來保存數據。網絡硬盤系統所提供的高可靠性及可用性使得用戶所上傳的數據不易丟失，而且隨時可以獲取[1]。
    近些年，針對一致性協議的研究與設計逐漸成為分布式系統領域的一個熱點問題[2-3]。而新興的網絡硬盤系統與其他的分布式存儲系統一樣面臨著同樣的問題，即它們都需要在一致性和可用性之間尋找一個較為合理的平衡點。本文在一款由清華大學所研制的網盤系統——Corsbox的基礎之上，為其設計一種用于客戶端之間進行共享操作的一致性協議，使得該網盤系統在此種情況下具有高可用性和低延遲的特點。
1 背景知識
    系統中保存的數據被某一客戶端更新時，可以根據其余客戶端何時能夠看到此更新的數據來對一致性進行分類。強一致性是指當系統中的數據更新完成以后，任何后續的客戶端訪問此數據時都能夠返回更新過的值；弱一致性是指系統不能保證當數據更新完成以后，客戶端的后續訪問能夠返回更新過的值；最終一致性是指系統保證如果用戶數據在沒有新的更新操作發生的情況下，最終所有對此數據的訪問都將返回最后更新過的值。
    分布式共享存儲系統在理想情況下應該同時具有強一致性、系統可用性和網絡分區容忍性。但不幸的是，Eric Brewer的CAP[4]理論證明了這三者不可能同時實現，并指出任何系統在任一時刻只能滿足其中兩條性質。在網絡分區已經成為一種基本要求的情況下，分布式系統的設計者幾乎一邊倒地選擇了可用性而放棄了強一致性。之所以如此是因為對于大多數應用來說，并不一定需要強一致性；而且選擇可用性不僅可以降低系統響應客戶端請求時的延遲，還能增加系統的可擴展性。Wyatt Lloyd[5]等人將具有可用性（Availability）、低延遲（Low latency）、分區可容忍性(Partition-tolerance)和可擴展性(Scalability)這4種特性的系統稱之為ALPS系統?，F如今有很多系統同時具有ALPS這4種特性，如Dynamo[6]、Voldemort[7]和Memcached[8]等一些具有最終一致性特點的鍵值對存儲系統。Facebook的Cassandra[9]是一種可配置的系統，可以根據需要設置其具有上述4種特性，也可以視具體情況使其具有線性一致性。本文將為一款網絡硬盤系統——Corsbox設計一種一致性協議，使得該網盤在移動、刪除和重命名共享目錄或文件的過程中具有高可用性和低延遲的特點，加之Corsbox網盤在網絡分區的情況下本身就有很強的擴展能力，所以使其滿足了成為ALPS系統所需要的所有條件。
2 網絡硬盤與底層云存儲系統
    大部分網絡硬盤系統通常由客戶端、服務器端和底層的云存儲端3個部分組成。云存儲是云計算技術的發展和延伸，云端將用戶數據分布在由大量計算機節點構成的資源池中，由于云存儲系統使用了特殊的容錯機制，所以可以采購一些價格相對低廉的節點構成云，而且還可以將各種不同類型的存儲設備集合起來協同工作。為了降低運營成本，大部分網絡硬盤都不會自己搭建底層的云存儲系統，而是轉而與大型的云存儲供應商合作。
    Corsbox網絡硬盤采用的底層云存儲系統是開源的OpenStack Swift[10]，它具有極高的數據持久性、數據冗余和高擴展性等特點。OpenStack并不是傳統文件系統，它為每一個使用者創建一個賬戶（Account），用戶可以在其賬戶下建立多個容器（Container），并將數據文件以對象（Object）的形式存放在其中，這一點與Amazon S3[11]很相似。
    Corsbox網盤在設計上規定了以目錄為最小的共享單位，并且允許目錄的所有者與被共享者都有權移動、重命名和刪除此目錄及其中的文件。由于OpenStack Swift[10]在處理刪除、移動和重命名等操作時只能確保數據的最終一致性，也就是說某一用戶對數據的修改不會立刻得到更新，所以當多個用戶在共享同一數據時，網盤系統不可能滿足他們之間的強一致性需求。并且即便Swift底層云存儲系統能夠確保強一致性，由于共享用戶不可能同時在線的原因，也無法做到在任何時刻，所有用戶所共享的數據都是一致的。因此需要為網絡硬盤系統設計一種一致性協議，來保證共享用戶在目錄或文件不會再發生任何改變時，他們所看到的視圖都是相同的。
3 一致性協議設計
    本文在描述為Corsbox網絡硬盤系統所設計的一致性協議時，以用戶操作共享文件為例進行說明。假設網盤系統中有5名用戶A、B、C、D、E，他們共享了同一目錄，其中用戶A是此共享目錄的擁有者，目錄的路徑為：Corsbox/album，其余用戶都是被共享者。在共享目錄中存有兩個子目錄sarah和enya，sarah目錄下有一音頻文件living.mp3。按照如下順序對共享目錄中的文件進行操作：
    (1)B、C、D 3名用戶首先上線，并一直保持在線狀態，且此時不對共享文件做任何操作；
    (2)用戶E和用戶A登錄，并在其后的任一時刻退出系統；
    (3)用戶B、C在用戶E和用戶A登錄網盤之后分別對共享文件進行操作，B用戶將living.mp3改名為journay.mp3，C用戶將living.mp3移動至enya目錄下；
    (4)用戶E再次登錄，并在其后任意時間下線；
    (5)用戶D在用戶E再次登錄后將共享文件living.mp3改名為crazy.mp3；
    (6)用戶A再次登錄網盤系統。
    在如上所述的操作系列下，本文所設計的協議會按照時間先后順序記錄下每個用戶的登錄情況和對共享文件的操作。當用戶E在步驟(4)中再次登錄時，網盤系統會根據記錄向上搜索，直至找到其上一次的登錄記錄為止。在搜索過程中，系統獲取了在用戶E的兩次登錄之間，B、C分別對共享文件進行了操作。當搜索工作結束之后，本協議會對由用戶A在云端所保存的這一共享文件做統一處理，即分別向云端發出B、C兩者對此文件的操作請求。之后網盤系統會根據本文所設計的協議將B、C的操作信息發送至用戶E，E的客戶端會根據這一信息，按照B、C的操作順序依次修改本地的共享文件。在進入到步驟(6)時，用戶A再次上線，網盤系統同樣會向前搜索至其上一次登錄的時間點，此時系統會檢測到在這一時間段內B、C、D都對共享文件進行了操作，而且用戶B、C的請求已經在云端完成，所以網盤系統現在只需要處理D用戶的操作請求即可。在完成了云端同步之后，B、C、D 3者的操作信息會被發送給用戶A，由于用戶A的客戶端之前沒有處理過B、C的操作，所以此時會連同D的操作按次序一并處理。需要注意的是，當這5位用戶中的任意一個對共享文件做了刪除操作時，其余用戶在此后對這一文件的操作都將被忽略。具體操作流程如圖1所示。

    使用本文為網盤系統所設計的上述協議可以帶來很多優點：
    (1)此協議可以很好地適應OpenStack Swift底層云存儲系統的最終一致性特點。
    (2)用戶對共享目錄及文件的移動、刪除和重命名操作會得到網盤系統的迅速響應，因為網盤系統并沒有立刻向底層云系統轉發用戶的操作請求，而只是將其操作記錄下來而已。具體的底層操作會推遲到其后任一用戶登錄時進行，即網盤系統會在各個用戶上線時對他們進行同步操作，這也是現行大多數網盤的通行做法。
    (3)網盤系統推遲了對用戶的操作請求，不會對共享此目錄或文件的用戶和其余被共享者造成任何使用上的影響。
    (4)由于協議嚴格地按照時間先后順序執行各個用戶的請求，所以最終共享用戶所看到的目錄及文件視圖不會有混亂不一致的情況發生。
    (5)本協議在處理由各共享用戶的操作所引起的沖突時，使用了類似last-writer-wins[12]的原則，即最后修改共享目錄或文件的操作將覆蓋掉之前其余所有用戶的操作（除刪除操作）。它不同于Coda[13]和Dynamo[6]等一些系統需要客戶端直接人為地介入來解決沖突問題。
4 一致性協議的實現
    為了實現所設計的協議，在網盤系統中引入了MySQL數據庫，每當用戶共享一個新的目錄給其他用戶時，系統都會為其生成一張數據表與之對應，此后所有共享此目錄的用戶的登錄操作和對這一共享目錄及其所包含的子目錄和文件的刪除、移動、重命名操作都會被記錄到這張表上。當有用戶登錄進行數據同步時，網盤系統根據協議只需對該表做降序搜索即可，并將搜索到的各個用戶的操作信息保存在特定的數據結構中。此數據結構的具體成員如表1所示。

    用戶E在登錄網盤以后，記錄在數據結構中的具體信息如表2所示，其中path項中的“&”符號用于分隔文件的新舊路徑。網盤系統在執行第一條操作之后會對表中的第二條記錄做預處理，即B用戶重命名后的新路徑替換第二條記錄中path項的原有路徑，替換后的結果為Corsbox/album/sarah/journay.mp3&Corsbox/album/enya/，這樣網盤在其后操作第二條記錄時就能夠作出正確處理。

    當用戶A再次登錄網盤時，數據結構中的信息如表3所示。由于用戶B、C的操作已經在底層云端處理妥當，此時網盤只需在云端執行第三條操作記錄即可。但是在這之前，還是需要對第二、三條記錄中的path項做兩次循環替換，替換后的最終結果如表4所示。

    Corsbox網絡硬盤系統在經過了這一系列處理之后，A、B、C、D、E這5位用戶在云端所對應的共享文件達到最終一致。共享用戶在客戶端的一致性操作與在云端的大致相同，不再累述。
    本文為一款網絡硬盤系統——Corsbox設計了一種一致性協議，從而使得該系統具備了高可用性和低延遲等特點。這意味著該網絡硬盤系統擁有了成為ALPS系統所需要的所有條件。當該網絡硬盤系統使用此協議時，能夠高效、快速地處理用戶對共享目錄及文件的操作請求，并達到最終一致。
參考文獻
[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，FREEDMAN 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.