Abstract
鏈復制是一種協(xié)調(diào)故障停止(fail-stop)存儲服務(wù)器群集的新方法元旬。 該方法旨在支持具有高吞吐量和可用性而又不犧牲強大一致性保證的大規(guī)模存儲服務(wù)外恕。 除了概述鏈復制協(xié)議之外媚赖，仿真實驗還探索了原型實現(xiàn)的性能特征漏隐。 討論了吞吐量，可用性和幾種對象放置策略（包括基于分布式哈希表路由的方案）信认。
1材义、 Introduction
存儲系統(tǒng)通常實現(xiàn)能讓客戶端進行存儲，檢索嫁赏，更改數(shù)據(jù)的操作其掂。文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)也許是最著名的例子。在文件系統(tǒng)中潦蝇，操作（讀和寫）訪問單個文件并且是冪等的款熬。 對于數(shù)據(jù)庫系統(tǒng)，操作（事務(wù)）可以分別訪問多個對象并且可以序列化攘乒。
本文涉及存儲系統(tǒng)贤牛，該存儲系統(tǒng)位于文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)之間。特別是持灰，我們關(guān)注的存儲系統(tǒng)（以下稱為存儲服務(wù)）：
存儲對象（性質(zhì)不明）
支持查詢操作以返回從單個對象派生的值
支持更新操作盔夜，根據(jù)某些操作原子地更改單個對象的狀態(tài)預編程（可能不確定）的計算，涉及該對象的先前狀態(tài)堤魁。
因此喂链，文件系統(tǒng)寫入是我們存儲服務(wù)更新的特例，而存儲服務(wù)更新又是數(shù)據(jù)庫事務(wù)的特例妥泉。
我們越來越多地看到在線供應(yīng)商（如Amazon.com）椭微，搜索引擎（如Google和FAST）以及許多其他信息密集型服務(wù)通過將大型存儲系統(tǒng)連接到網(wǎng)絡(luò)來提供價值。 當數(shù)據(jù)庫系統(tǒng)太昂貴而文件系統(tǒng)缺乏足夠豐富的語義時盲链，存儲服務(wù)是此類應(yīng)用程序的適當折衷方案蝇率。
建立大規(guī)模的存儲服務(wù)時面臨的挑戰(zhàn)之一是，盡管存在故障刽沾，并且隨著檢測到并更換了故障組件而對存儲服務(wù)的配置進行了相應(yīng)的更改本慕，但仍要保持高可用性和高吞吐量。
一致性保證也可能至關(guān)重要侧漓。 但是锅尘，即使不是這樣，在給定強大的一致性保證的情況下布蔗，通常也會簡化面向存儲服務(wù)的應(yīng)用程序的構(gòu)造藤违，這保證了查詢和更新單個對象的操作按一定順序執(zhí)行，并且 更新操作的效果必須反映在后續(xù)查詢操作返回的結(jié)果中纵揍。
人們通常認為顿乒，強大的一致性保證會在實現(xiàn)高吞吐量和高可用性方面造成壓力。 因此泽谨，不愿犧牲系統(tǒng)吞吐量或可用性的系統(tǒng)設(shè)計人員經(jīng)常會拒絕支持強大的一致性保證璧榄。 Google文件系統(tǒng)（GFS）闡明了這種想法特漩。 實際上，大型存儲服務(wù)中的強一致性保證不會與高吞吐量和可用性不兼容犹菱。 協(xié)調(diào)本文所述的故障停止服務(wù)器的新鏈復制方法可同時支持高吞吐量拾稳，可用性和強一致性。
我們按以下步驟進行腊脱。 通用存儲服務(wù)的接口在§2中指定访得。 在§3中，我們解釋了如何使用鏈式復制來實現(xiàn)查詢和更新操作陕凹。 鏈式復制可以看作是Primary/BackUp方法的一個實例悍抑，因此§4將它們進行了比較。 然后杜耙，§5總結(jié)了使用鏈復制的原型實現(xiàn)和模擬網(wǎng)絡(luò)來分析吞吐量和可用性的實驗搜骡。 其中一些模擬將基于分布式哈希表（DHT）路由的鏈復制與存儲系統(tǒng)（如CFS [7]和PAST [19]）進行比較； 當采用鏈式復制的系統(tǒng)從服務(wù)器故障中恢復時佑女，其他模擬也揭示了令人驚訝的行為记靡。 在第6節(jié)中，將鏈復制與可伸縮存儲系統(tǒng)上的其他工作团驱，可用性的交易一致性和副本放置進行了比較摸吠。 結(jié)束語出現(xiàn)在§7中，后跟尾注嚎花。
