NoSQL系統(tǒng)的容錯(cuò)機(jī)制：原理與系統(tǒng)示例

孔 超， 錢衛(wèi)寧， 周傲英

（華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程研究院，上海 200062）

0 引 言

傳統(tǒng)的關(guān)系型數(shù)據(jù)管理系統(tǒng)已經(jīng)不能滿足高并發(fā)的讀寫、高可用性和高可擴(kuò)展性的新興互聯(lián)網(wǎng)應(yīng)用的需求.NoSQL系統(tǒng)在這種背景下應(yīng)運(yùn)而生.NoSQL常被認(rèn)為不同于傳統(tǒng)關(guān)系型數(shù)據(jù)管理系統(tǒng)，是具有非關(guān)系型、分布式、開源、橫向擴(kuò)展等特性的新型數(shù)據(jù)管理系統(tǒng)［1］.這些系統(tǒng)犧牲了一些已在傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)中成為標(biāo)準(zhǔn)的功能，如數(shù)據(jù)一致性、標(biāo)準(zhǔn)查詢語(yǔ)言以及參照完整性等，以換取高可擴(kuò)展性、高可用性和高可靠性.

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，海量數(shù)據(jù)的存儲(chǔ)、管理和處理已經(jīng)成為全球各大互聯(lián)網(wǎng)公司不可回避的嚴(yán)峻問(wèn)題.以業(yè)務(wù)范圍跨越C2C（個(gè)人對(duì)個(gè)人）和B2C（商家對(duì)個(gè)人）的淘寶網(wǎng)為例：截至2013年，淘寶網(wǎng)擁有近5億的注冊(cè)用戶數(shù)，每天有超過(guò)6 000萬(wàn)的固定訪客，每天的在線商品數(shù)已經(jīng)超過(guò)了8億件，平均每分鐘售出4.8萬(wàn)件商品［2，3］；2013年11月11日零時(shí)，開場(chǎng)僅1分鐘成交的訂單數(shù)量達(dá)到33.9萬(wàn)筆，總成交金額達(dá)到1.17億元，第二分鐘，成交數(shù)字突破3.7億元，到了零時(shí)6分7秒，成交額直接沖上10億元，截至11日24時(shí)，“雙11”天貓及淘寶的總成交額破300億元，達(dá)350.19億元［4］，這些海量交易信息的存儲(chǔ)、分析和處理對(duì)淘寶網(wǎng)提出了巨大的挑戰(zhàn)，類似的問(wèn)題也出現(xiàn)在Google、Facebook、Yahoo等互聯(lián)網(wǎng)應(yīng)用上.例如，2012年Facebook在總部的一次會(huì)議中披露了一組Facebook每天要處理的數(shù)據(jù)：25億條分享的內(nèi)容條數(shù)，27億個(gè)“贊”的數(shù)量，3億張上傳的照片數(shù)，超過(guò)500 TB新產(chǎn)生的數(shù)據(jù)，每半小時(shí)通過(guò)Hive掃描105 TB的數(shù)據(jù)，單個(gè)HDFS集群中的磁盤容量超過(guò)100 PB［5］.

當(dāng)今的互聯(lián)網(wǎng)應(yīng)用具有以下特性：

（1）用戶基數(shù)大，而且增長(zhǎng)速度快；

（2）數(shù)據(jù)類型多、總量大；

（3）對(duì)數(shù)據(jù)操作較為單一，一致性要求較弱.

雖然互聯(lián)應(yīng)用中涉及的數(shù)據(jù)類型多樣，但普通用戶的數(shù)據(jù)處理操作較為單一，對(duì)數(shù)據(jù)的操作無(wú)非讀或?qū)?，或者是增加、刪除、修改和查詢等.Henderson在2008年Web 2.0expo中的報(bào)告指出：通常在互聯(lián)網(wǎng)應(yīng)用中，用戶更多的是讀數(shù)據(jù)；據(jù)統(tǒng)計(jì)，讀／寫數(shù)據(jù)的比例大約為80∶20或者90∶10［6］.低延遲的用戶響應(yīng)、高吞吐量是首先要考慮的技術(shù)問(wèn)題，以滿足基本的用戶需求；而對(duì)數(shù)據(jù)沒(méi)有嚴(yán)格的強(qiáng)一致性要求，這有別于金融行業(yè)的數(shù)據(jù)操作.

互聯(lián)網(wǎng)應(yīng)用的這些特性對(duì)海量數(shù)據(jù)存儲(chǔ)、管理和處理提出了巨大的挑戰(zhàn)，例如：支持PB級(jí)甚至EB級(jí)數(shù)據(jù)的存儲(chǔ)系統(tǒng)、具有良好的擴(kuò)展性以滿足不斷增長(zhǎng)的數(shù)據(jù)和用戶需求，具有低延遲的用戶響應(yīng)和高吞吐量，具備良好的容錯(cuò)機(jī)制以保證互聯(lián)網(wǎng)應(yīng)用的高可用性和高可靠性等.

現(xiàn)有的NoSQL系統(tǒng)都有相應(yīng)的機(jī)制來(lái)解決容錯(cuò)問(wèn)題.容錯(cuò)機(jī)制與NoSQL系統(tǒng)的高可用性、高可靠性息息相關(guān)，在采用大量非可靠硬件的集群環(huán)境中尤為重要.良好的容錯(cuò)機(jī)制使得NoSQL系統(tǒng)在某些組件發(fā)生故障時(shí)，仍能繼續(xù)為用戶服務(wù)，滿足基本的用戶需要.Bigtable、HBase等幾種典型的NoSQL系統(tǒng)的容錯(cuò)機(jī)制越來(lái)越成熟，大大提高了NoSQL系統(tǒng)的可靠性和可用性.

隨著硬件技術(shù)，特別是內(nèi)存技術(shù)的發(fā)展，基于內(nèi)存計(jì)算的數(shù)據(jù)管理系統(tǒng)，如SAP HANA，因其所具有的高性能，已經(jīng)引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注［7］.而在依賴于易失內(nèi)存的數(shù)據(jù)管理系統(tǒng)中的容錯(cuò)處理，則是內(nèi)存數(shù)據(jù)管理系統(tǒng)所無(wú)法回避的重要問(wèn)題.NoSQL系統(tǒng)中能夠保持系統(tǒng)高可擴(kuò)展性的容錯(cuò)機(jī)制和實(shí)現(xiàn)技術(shù)，為這一問(wèn)題的研究提供了思路.

本文以下主要從三個(gè)部分展開論述.第1部分對(duì)集群環(huán)境數(shù)據(jù)管理系統(tǒng)的一致性保持和容錯(cuò)處理基本原理進(jìn)行介紹；第2部分對(duì)Bigtable、HBase、Dynamo、Cassandra和PNUTS五個(gè)典型的NoSQL系統(tǒng)的容錯(cuò)機(jī)制及實(shí)現(xiàn)進(jìn)行分析對(duì)比，并討論它們的設(shè)計(jì)原則和實(shí)現(xiàn)技術(shù)對(duì)于系統(tǒng)的可用性、性能、復(fù)雜負(fù)載的處理能力等方面的影響；第3部分討論現(xiàn)有NoSQL系統(tǒng)容錯(cuò)機(jī)制對(duì)于設(shè)計(jì)和實(shí)現(xiàn)支持關(guān)鍵任務(wù)的內(nèi)存數(shù)據(jù)管理系統(tǒng)的借鑒意義.

1 基礎(chǔ)理論

數(shù)據(jù)庫(kù)領(lǐng)域的容錯(cuò)指系統(tǒng)從故障恢復(fù)的能力，是數(shù)據(jù)管理應(yīng)用中必須考慮的關(guān)鍵問(wèn)題.

NoSQL存儲(chǔ)系統(tǒng)的容錯(cuò)機(jī)制設(shè)計(jì)，需要考慮恢復(fù)和復(fù)制技術(shù)，還必須考慮它們對(duì)系統(tǒng)的性能和負(fù)載能力等方面的影響.本節(jié)介紹構(gòu)建高可用、高可靠的NoSQL系統(tǒng)的基礎(chǔ)理論，包括CAP理論，以及分布式鎖服務(wù)、恢復(fù)和復(fù)制等實(shí)現(xiàn)技術(shù).

1.1 CAP理論

2000年，Brewer提出了CAP理論，即一個(gè)分布式系統(tǒng)，最多只能同時(shí)滿足：一致性（Consistency，用C表示），可用性（Availability，用A表示）和網(wǎng)絡(luò)分區(qū)容忍性（Tolerance to Network Partitions，下文簡(jiǎn)稱分區(qū)容忍性，用P表示），這三個(gè)需求中的兩個(gè)［8］.2002年Gilbert和Lynch論證了該理論的正確性［9］.

一般而言，分布式系統(tǒng)首先應(yīng)該具備分區(qū)容忍性，以滿足大規(guī)模數(shù)據(jù)中心的相關(guān)操作.因此CAP理論意味著對(duì)于一個(gè)網(wǎng)絡(luò)分區(qū)，在一致性和可用性二者之間的取舍［10］.傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)選擇一致性，而互聯(lián)網(wǎng)應(yīng)用更傾向于可用性.Brewer指出：在大多數(shù)情況下，分區(qū)故障不會(huì)經(jīng)常出現(xiàn)，因此在設(shè)計(jì)系統(tǒng)的時(shí)候允許一致性和可用性并存［11］.當(dāng)分區(qū)故障發(fā)生時(shí)，應(yīng)該有一套策略來(lái)檢測(cè)出這些故障，并有合理的故障恢復(fù)方法.當(dāng)然，在系統(tǒng)設(shè)計(jì)時(shí)，不可能完全舍棄數(shù)據(jù)一致性，否則數(shù)據(jù)是不安全的和混亂錯(cuò)誤的，以致再高的可用性和可靠性也沒(méi)了意義.犧牲一致性指允許系統(tǒng)弱化一致性要求，只要滿足最終一致性（Eventual Consistency）即可，而不再要求關(guān)系型數(shù)據(jù)庫(kù)中的強(qiáng)一致性（即時(shí)一致性）.最終一致性指：若對(duì)一個(gè)給定的數(shù)據(jù)項(xiàng)沒(méi)有新的更新，那么最終對(duì)該數(shù)據(jù)項(xiàng)所有的訪問(wèn)都返回最后更新的值.它被集群環(huán)境的數(shù)據(jù)管理系統(tǒng)廣泛采用，也常被稱為“樂(lè)觀復(fù)制”（Optimistic Replication）［12］.

根據(jù)CAP理論，C、A、P三者不可兼得，必須有所取舍.傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)保證了強(qiáng)一致性（ACID模型）和高可用性，但其擴(kuò)展能力有限.而NoSQL系統(tǒng)則通過(guò)犧牲強(qiáng)一致性，以最終一致性進(jìn)行替代，來(lái)使得系統(tǒng)可以達(dá)到很高的可用性和擴(kuò)展性［13］.

1.1.1 一致性（Consistency）

分布式存儲(chǔ)系統(tǒng)領(lǐng)域的一致性指：在相同的時(shí)間點(diǎn)，所有節(jié)點(diǎn)讀到相同的數(shù)據(jù)［14］.傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)很少存在一致性問(wèn)題，數(shù)據(jù)的存取具有良好的事務(wù)性，不會(huì)出現(xiàn)讀寫的不一致；對(duì)于分布式存儲(chǔ)系統(tǒng)，一個(gè)數(shù)據(jù)存多份副本，一致性要求用戶對(duì)數(shù)據(jù)的修改操作要么在所有的副本中操作成功，要么全部失敗.若保證一致性，那么用戶讀寫的數(shù)據(jù)則可以保證是最新的，不會(huì)出現(xiàn)兩個(gè)客戶端在不同的節(jié)點(diǎn)中讀到不同的情況.

1.1.2 可用性（Availability）

可用性指：用戶發(fā)送訪問(wèn)請(qǐng)求時(shí)，無(wú)論操作成功與否，都能得到及時(shí)反饋［14］.系統(tǒng)可用不代表所有節(jié)點(diǎn)提供的數(shù)據(jù)是一致的.實(shí)際應(yīng)用中，往往對(duì)不同的應(yīng)用設(shè)定一個(gè)最長(zhǎng)響應(yīng)時(shí)間，超過(guò)這個(gè)響應(yīng)時(shí)間的服務(wù)被認(rèn)為是不可用的.

1.1.3 網(wǎng)絡(luò)分區(qū)容忍性（Tolerance to Network Partitions）

分區(qū)容忍性指：任意消息丟失或部分系統(tǒng)故障發(fā)生時(shí)，系統(tǒng)仍能良好地運(yùn)行［14］.一個(gè)存儲(chǔ)系統(tǒng)只運(yùn)行在一個(gè)節(jié)點(diǎn)上，要么系統(tǒng)整個(gè)崩潰，要么全部運(yùn)行良好，一旦分布到了多個(gè)節(jié)點(diǎn)上，整個(gè)存儲(chǔ)系統(tǒng)就存在分區(qū)的可能性.

1.2 分布式鎖服務(wù)：以Chubby為例

分布式鎖是分布式系統(tǒng)中控制同步訪問(wèn)共享資源的一種方式.如果不同的系統(tǒng)或同一個(gè)系統(tǒng)的不同主機(jī)之間共享了一個(gè)或一組資源，當(dāng)訪問(wèn)這些資源時(shí)，需要互斥來(lái)防止彼此干擾，從而保證一致性，則需要使用分布式鎖［15］.

分布的一致性問(wèn)題描述為：在一個(gè)分布式系統(tǒng)中，有一組進(jìn)程，需要這些進(jìn)程確定一個(gè)值.于是每個(gè)進(jìn)程都給出了一個(gè)值，并且只能其中的一個(gè)值被選中作為最后確定的值以保證一致性，當(dāng)這個(gè)值被選出來(lái)以后，要通知所有的進(jìn)程.Na?ve的解決方案為：構(gòu)建一個(gè)master server，所有進(jìn)程都向它提交一個(gè)值，master server從中挑一個(gè)值，并通知其他進(jìn)程.在分布式環(huán)境下，該方案不可行，可能會(huì)發(fā)生的問(wèn)題有：master server宕機(jī)怎么辦？由于網(wǎng)絡(luò)傳輸?shù)难舆t，如何保證每個(gè)值到達(dá)master server的順序等［16］.

為解決以上問(wèn)題，Chubby被構(gòu)建出來(lái)，它并不是一個(gè)協(xié)議或者算法，而是Google精心設(shè)計(jì)的一個(gè)分布式的鎖服務(wù)［17］.通過(guò)Chubby，client能夠?qū)Y源進(jìn)行“加鎖”、“解鎖”.Chubby通過(guò)文件實(shí)現(xiàn)這樣的“鎖”功能，創(chuàng)建文件就是進(jìn)行“加鎖”操作，創(chuàng)建文件成功的server則搶占到了“鎖”，用戶通過(guò)打開、關(guān)閉和讀取文件，獲取共享鎖或者獨(dú)占鎖，并且通過(guò)通信機(jī)制向用戶發(fā)送更新信息［18］.Chubby的結(jié)構(gòu)見圖1.

圖1 Chubby結(jié)構(gòu)［17］Fig.1 Structure of Chubby

如圖1所示，Chubby有兩個(gè)主要組件：Chubby cell和Chubby library；兩者通過(guò)RPCs通信.Chubby cell由五個(gè)被稱為replica的server組成；只要其中三個(gè)正常，它就能提供服務(wù).這些server通過(guò)分布式一致性協(xié)議選舉一個(gè)作為master server；client application和server間的通信都需要通過(guò)Chubby library；client application通過(guò)Chubby library的接口調(diào)用，在Chubby cell上創(chuàng)建文件獲得相應(yīng)鎖功能.

文獻(xiàn)［17］闡述了Chubby的工作流程：首先，Chubby cell從五個(gè)replica按照分布式一致性協(xié)議選舉出一個(gè)master，master必須獲得半數(shù)以上的選票，同時(shí)保證在該master的租約內(nèi)不會(huì)再選舉出新的master，replica通過(guò)Paxos協(xié)議［19］保持日志的一致性，采用Quorums［20］做決策，使用多副本滿足高可用性；其次，每個(gè)replica維護(hù)一個(gè)數(shù)據(jù)庫(kù)的拷貝，但只有master能夠執(zhí)行讀／寫操作，master通過(guò)一致性協(xié)議將更新傳送到其他replica上.client向DNS中replica列表發(fā)送master定位請(qǐng)求來(lái)找到master，非master的replica返回master標(biāo)識(shí)符響應(yīng)請(qǐng)求，一旦client找到master就會(huì)將所有請(qǐng)求直接發(fā)送給master.讀請(qǐng)求由master處理，只要master還在租約期內(nèi)就是安全的.master會(huì)通過(guò)一致性協(xié)議將寫請(qǐng)求發(fā)送給其他replica，當(dāng)半數(shù)以上的replica收到請(qǐng)求，則認(rèn)為操作成功；最后，一旦master意外停機(jī)，其他replica在master租約過(guò)期后選舉其他的replica作為master.

1.3 分布式容錯(cuò)中的復(fù)制技術(shù)和恢復(fù)技術(shù)

容錯(cuò)指：一個(gè)系統(tǒng)的程序在出現(xiàn)邏輯故障的情況下仍能被正確執(zhí)行［21］.分布式系統(tǒng)中容錯(cuò)的概念指：在系統(tǒng)發(fā)生故障時(shí)，以不降低系統(tǒng)性能為前提，用冗余資源完成故障恢復(fù)，使系統(tǒng)具備容忍故障的能力［22］.本節(jié)介紹分布式容錯(cuò)中的復(fù)制技術(shù)和恢復(fù)技術(shù).

1.3.1 復(fù)制

分布式存儲(chǔ)系統(tǒng)中的數(shù)據(jù)一般存儲(chǔ)多個(gè)副本以保證系統(tǒng)的高可用性和高可靠性，當(dāng)存儲(chǔ)某個(gè)副本的節(jié)點(diǎn)發(fā)生故障時(shí)，系統(tǒng)能自適應(yīng)地將運(yùn)行中的服務(wù)切換到其他副本，實(shí)現(xiàn)自動(dòng)容錯(cuò).復(fù)制技術(shù)可以分為同步復(fù)制和異步復(fù)制兩大類：同步復(fù)制能夠保證主備副本的強(qiáng)副本一致性：當(dāng)客戶端訪問(wèn)一組被復(fù)制的副本時(shí)，每個(gè)副本就如同一個(gè)邏輯服務(wù)［23］，但當(dāng)備副本發(fā)生故障時(shí)，可能會(huì)影響系統(tǒng)正常的寫操作，降低系統(tǒng)的可用性；異步復(fù)制通常只能滿足最終一致性：保證副本的最終狀態(tài)相同，在異步系統(tǒng)中，可能存在一個(gè)或多個(gè)主節(jié)點(diǎn)來(lái)完成副本間的狀態(tài)同步［24］，但當(dāng)主副本出現(xiàn)故障時(shí)，可能會(huì)導(dǎo)致數(shù)據(jù)丟失，一致性得不到保障.分布式存儲(chǔ)系統(tǒng)中使用的復(fù)制協(xié)議主要有：基于主副本的復(fù)制協(xié)議（Primary－based protocol）和基于多個(gè)存儲(chǔ)節(jié)點(diǎn)的復(fù)制協(xié)議（Replicated－write protocol）［25］.

主備復(fù)制通常在分布式存儲(chǔ)系統(tǒng)中保存多個(gè)副本，選舉其中一個(gè)副本為主副本，其他的為備副本，數(shù)據(jù)寫入主副本中，由主副本按照一定的操作順序復(fù)制到備副本［26］.同步復(fù)制和異步復(fù)制都是基于主副本的復(fù)制協(xié)議，兩者的區(qū)別在于：異步復(fù)制協(xié)議中，主副本無(wú)需等待備副本的響應(yīng)，只需本地操作成功便告知客戶端更新成功.同步復(fù)制的流程如下：第一，客戶端向主副本發(fā)送寫請(qǐng)求，記為W1；第二，主副本通過(guò)操作日志（Commit Log）的方式將日志同步到備副本，記為 W2；第三，備副本重放（replay）日志，完成后通知主副本，記為 W3；第四，主副本進(jìn)行本地修改，更新完畢后通知客戶端操作成功，記為W4.R1表示客戶端將讀請(qǐng)求發(fā)送給一個(gè)副本，R2表示將讀取結(jié)果返回給客戶端，具體見圖2.

主備副本之間的復(fù)制通過(guò)操作日志的方式來(lái)實(shí)現(xiàn)：第一，將客戶端的寫操作順序?qū)懙酱疟P中；第二，利用內(nèi)存的隨機(jī)讀寫特性，將其應(yīng)用到內(nèi)存中，有效組織數(shù)據(jù)；第三，宕機(jī)重啟后，重放操作日志恢復(fù)內(nèi)存狀態(tài).為了減少執(zhí)行長(zhǎng)日志的代價(jià)，系統(tǒng)會(huì)定期創(chuàng)建checkpoint文件將內(nèi)存狀態(tài)dump到磁盤中.若服務(wù)器出現(xiàn)故障，則只需恢復(fù)在checkpoint之后插入的日志條目.

1.3.2 恢復(fù)

圖2 同步復(fù)制流程［27］Fig.2 The process of synchronous replication

構(gòu)建具備健壯性的分布式存儲(chǔ)系統(tǒng)前提是具備良好的容錯(cuò)性能，具備從故障種恢復(fù)的能力.在NoSQL系統(tǒng)中，這樣的恢復(fù)能力有一個(gè)前提：擁有有效的故障檢測(cè)（Failure Detection）手段，只有能有效、即時(shí)地檢測(cè)到故障發(fā)生，才有制定恢復(fù)策略的可能.故障檢測(cè)是任何一個(gè)擁有容錯(cuò)性的分布式系統(tǒng)的基本功能，實(shí)際上所有的故障檢測(cè)都基于心跳（Heartbeat）機(jī)制：被監(jiān)控的組件定期發(fā)送心跳信息給監(jiān)控進(jìn)程，若給定時(shí)間內(nèi)監(jiān)控進(jìn)程沒(méi)有收到心跳信息，則認(rèn)為該組件失效［28］.

在NoSQL系統(tǒng)中，當(dāng)master server檢測(cè)到slave server發(fā)生故障時(shí)，便會(huì)將服務(wù)遷移到其他節(jié)點(diǎn).常見的分布式系統(tǒng)有兩種結(jié)構(gòu)：?jiǎn)螌咏Y(jié)構(gòu)和雙層結(jié)構(gòu)，如圖3所示.

圖3 故障恢復(fù)［27］Fig.3 Failure recovery

單層結(jié)構(gòu)的分布式存儲(chǔ)系統(tǒng)有三個(gè)數(shù)據(jù)分片A、B和C，分別存儲(chǔ)了三個(gè)副本；其中A1、B1、C1為主副本，分別存儲(chǔ)在節(jié)點(diǎn)1、節(jié)點(diǎn)2和節(jié)點(diǎn)3.若節(jié)點(diǎn)1發(fā)生故障，主控節(jié)點(diǎn)檢測(cè)到該故障，就會(huì)選擇一個(gè)最新的副本，A2或A3替換A1成為新的主副本提供寫服務(wù).

雙層結(jié)構(gòu)的分布式存儲(chǔ)系統(tǒng)會(huì)將所有的數(shù)據(jù)持久化寫入底層的分布式文件系統(tǒng)，每個(gè)數(shù)據(jù)分片同一時(shí)刻只有一個(gè)提供服務(wù)的節(jié)點(diǎn).若節(jié)點(diǎn)1發(fā)生故障，主控節(jié)點(diǎn)將選擇節(jié)點(diǎn)2加載A的服務(wù).由于A的所有數(shù)據(jù)都存儲(chǔ)在共享的分布式文件系統(tǒng)中，節(jié)點(diǎn)2只需要從底層分布式文件系統(tǒng)中讀取A的數(shù)據(jù)并加載到內(nèi)存中.

2 系統(tǒng)示例

高可用性和高可靠性是互聯(lián)網(wǎng)應(yīng)用需求下海量數(shù)據(jù)存儲(chǔ)考慮的首要問(wèn)題，也是核心存儲(chǔ)系統(tǒng)的基本特性.以下通過(guò)分析對(duì)比Bigtable、HBase、Dynamo、Cassandra和PNUTS五個(gè)典型的NoSQL系統(tǒng)的容錯(cuò)機(jī)制：故障檢測(cè)手段和故障恢復(fù)策略，探討對(duì)系統(tǒng)的可用性、性能、一致性保持和復(fù)雜負(fù)載處理能力的影響.

2.1 Bigtable和HBase

Bigtable是一個(gè)高性能、高可擴(kuò)展性的分布式的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)，其系統(tǒng)結(jié)構(gòu)如圖4所示.Google的很多項(xiàng)目使用Bigtable存儲(chǔ)數(shù)據(jù)，包括 Web索引、Google Earth和Google Finance.這些應(yīng)用對(duì)Bigtable提出的要求差異非常大，無(wú)論是在數(shù)據(jù)量上（從URL到網(wǎng)頁(yè)到衛(wèi)星圖像）還是在響應(yīng)速度上（從后端的批量處理到實(shí)時(shí)數(shù)據(jù)服務(wù)）［29］.作為集中式數(shù)據(jù)管理系統(tǒng)，Bigtable采用傳統(tǒng)的服務(wù)器集群架構(gòu)，整個(gè)系統(tǒng)由一個(gè)主控服務(wù)器（master server）和多個(gè)片服務(wù)器（tablet server）構(gòu)成，主控節(jié)點(diǎn)集中控制、管理、維護(hù)從節(jié)點(diǎn)的元信息.集中式管理的優(yōu)勢(shì)在于：人為可控且維護(hù)方便，在處理數(shù)據(jù)同步時(shí)較簡(jiǎn)單；其劣勢(shì)在于：系統(tǒng)存在單點(diǎn)故障的危險(xiǎn).

圖4 Bigtable的系統(tǒng)結(jié)構(gòu)［30］Fig.4 Architecture of Bigtable

HBase是在HDFS（Hadoop分布式文件系統(tǒng)）上開發(fā)的基于列的分布式存儲(chǔ)系統(tǒng)，具有高可靠性、高性能、可伸縮、支持實(shí)時(shí)讀寫等特性，其系統(tǒng)結(jié)構(gòu)見圖5.該項(xiàng)目由Powerset公司的Chad Walters和Jim Kelleman在2006年末發(fā)起的，根據(jù)Chang等人發(fā)表的論文“Bigtable：A Distributed Storage System for Structured Data”來(lái)設(shè)計(jì)的［31］.HBase的 Client使用遠(yuǎn)程過(guò)程調(diào)用（RPC）機(jī)制與master和region server通信，完成管理和讀寫等操作；HBase中的ZooKeeper當(dāng)作一個(gè)協(xié)調(diào)工具［32］.ZooKeeper中存儲(chǔ)－ROOT－目錄表的地址信息和master的地址信息.region server在ZooKeeper中注冊(cè)，所以master可以跟蹤每個(gè)region server的狀態(tài)；HBase不同于Bigtable，允許啟動(dòng)多個(gè)master，ZooKeeper保證總有有效個(gè)master運(yùn)行，因此弱化了Bigtable中單點(diǎn)故障的問(wèn)題.

圖5 HBase系統(tǒng)結(jié)構(gòu)［33］Fig.5 Architecture of HBase

HBase作為Google的Bigtable架構(gòu)的一個(gè)開源實(shí)現(xiàn)，在容錯(cuò)機(jī)制和一致性保持的某些方面繼承了Bigtable的特性；但二者之間也存在細(xì)致的差別.下文主要從這兩個(gè)方面進(jìn)行闡述.

2.1.1 Bigtable和HBase的容錯(cuò)機(jī)制

Bigtable和HBase的故障檢測(cè)手段都是基于Heartbeat機(jī)制，但具體的實(shí)現(xiàn)方式有區(qū)別.Bigtable通過(guò)分布式鎖服務(wù)Chubby確保任何時(shí)刻最多只有一個(gè)活動(dòng)的master副本，檢測(cè)tablet server和master server狀態(tài)，以便進(jìn)行故障恢復(fù).

在Bigtable中，通過(guò)Chubby跟蹤tablet server狀態(tài)信息.當(dāng)啟動(dòng)一個(gè)tablet server時(shí)，系統(tǒng)會(huì)在特定的Chubby目錄下，對(duì)一個(gè)唯一標(biāo)識(shí)的文件獲得排他鎖（exclusive lock），master會(huì)通過(guò)該目錄檢測(cè)tablet server狀態(tài)，當(dāng)諸如網(wǎng)絡(luò)不穩(wěn)定等因素導(dǎo)致tablet server和Chubby之間的會(huì)話中斷，tablet server失去排他鎖，便停止對(duì)tablet的一切服務(wù).

當(dāng)tablet server出現(xiàn)故障時(shí)，tablet server嘗試重新獲取唯一標(biāo)識(shí)的文件的排他鎖，若該文件不存在，tablet server將永遠(yuǎn)不會(huì)提供服務(wù)，便自行終止進(jìn)程.一旦tablet server終止，它將嘗試釋放鎖，此時(shí)master便對(duì)tablet重新合并、切分、分配到其他tablet sever上.該過(guò)程中，master為了隨時(shí)檢測(cè)tablet server的狀態(tài)信息，會(huì)通過(guò)Heartbeat機(jī)制周期性地詢問(wèn)每個(gè)tablet server排他鎖的持有狀態(tài)，若tablet server報(bào)告失去排他鎖，或者master和tablet server無(wú)法通信，master便獲取鎖，一旦tablet server宕機(jī)或與Chubby通信出現(xiàn)故障，master便確認(rèn)tablet server無(wú)法提供服務(wù)，便刪除該tablet server在Chubby目錄下唯一標(biāo)識(shí)的文件.

當(dāng)master與Chubby之間的會(huì)話失效時(shí)，master終止服務(wù)，但是不會(huì)改變tablet server當(dāng)前對(duì)tablet的分配情況.此時(shí)，master會(huì)被系統(tǒng)重啟：首先，master在Chubby中獲取一個(gè)唯一的master lock，以防出現(xiàn)并發(fā)的master實(shí)例，確保只有一個(gè)master；其次，master掃描Chubby下server目錄，獲取現(xiàn)存的server信息；第三，master與現(xiàn)有的每個(gè)tablet server進(jìn)行通信，以確定哪些已被分配了tablet；最后，master掃描METADATA表，獲取tablet信息.在掃描時(shí)，一旦發(fā)現(xiàn)某個(gè)tablet尚未被分配，master便把該tablet信息添加到“未分配”的tablet集合中，保證這些未被分配的tablet有被分配的機(jī)會(huì).

Bigtable的底層存儲(chǔ)是基于GFS（Google File System）的，其對(duì)于數(shù)據(jù)、日志的容錯(cuò)主要通過(guò)GFS多副本冗余來(lái)保證.GFS存儲(chǔ)的文件都被分割成一個(gè)個(gè)大小固定的chunk.在chunk創(chuàng)建之時(shí)，master服務(wù)器會(huì)給每個(gè)chunk分配一個(gè)唯一、不變的64位標(biāo)識(shí)，chunk服務(wù)器把chunk以Linux文件的形式保存在本地硬盤上，每個(gè)chunk將副本寫入多臺(tái)chunk服務(wù)器中，master節(jié)點(diǎn)管理所有從節(jié)點(diǎn)文件的元數(shù)據(jù)（METADATA）：命名空間、訪問(wèn)控制信息、文件和chunk的映射信息以及當(dāng)前Chunk位置信息等［34］.當(dāng)客戶端進(jìn)行讀操作時(shí)，從Namenode中獲取文件和chunk的映射信息，再?gòu)目捎玫腸hunk服務(wù)器中讀數(shù)據(jù).

HBase基于Heartbeat機(jī)制進(jìn)行故障檢測(cè)，master和region server組件的故障恢復(fù)策略如下：

（1）當(dāng)master出現(xiàn)故障時(shí)，ZooKeeper會(huì)重新選擇一個(gè)master；當(dāng)新的master被啟用之前，數(shù)據(jù)的讀取正常進(jìn)行，但不能進(jìn)行region分割和均衡負(fù)載等操作.

（2）當(dāng)region server出現(xiàn)故障時(shí)，它通過(guò)Heartbeat機(jī)制定期和ZooKeeper通信；若一段時(shí)間內(nèi)未出現(xiàn)心跳，master會(huì)將該region server上的region分配到其他region server上.由圖5可知，MemStore中內(nèi)存數(shù)據(jù)全部丟失；此時(shí)，region server中的一個(gè)實(shí)現(xiàn)預(yù)寫日志（Write Ahead Log）的類HLog保存了用戶每次寫入MemStore的數(shù)據(jù).具體恢復(fù)過(guò)程如下：master通過(guò)ZooKeeper感知region server出現(xiàn)故障，master首先處理該region server遺留的HLog文件，將不同region的日志文件拆分，放到相應(yīng)region目錄下；其次將失效的region重新分配到region server上，這些region server在加載被分配到的region的同時(shí)會(huì)重寫歷史HLog中的數(shù)據(jù)到MemStore；最后，F(xiàn)lush到StoreFile，數(shù)據(jù)得以恢復(fù)［35］.

HBase 0.90版本以后開始使用基于操作日志（put／get／delete）的副本機(jī)制進(jìn)行失效恢復(fù)：region server將客戶端的操作寫入本地HLog中，每個(gè)region server將HLog放入對(duì)應(yīng)znode（ZooKeeper維護(hù)的樹形層次結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn)）上的副本隊(duì)列，將HLog內(nèi)容發(fā)送到集群中某個(gè)region server上，并將當(dāng)前復(fù)制的偏移量保存在ZooKeeper上，整個(gè)過(guò)程采用異步復(fù)制機(jī)制，滿足高可用性的需求［36］.

在工程實(shí)踐中，Bigtable和HBase為避免某個(gè)節(jié)點(diǎn)的訪問(wèn)壓力過(guò)載造成的節(jié)點(diǎn)失效，有專門的負(fù)載均衡策略［37］來(lái)解決這一問(wèn)題.Bigtable的tablet服務(wù)節(jié)點(diǎn)上的負(fù)載均衡依靠master通過(guò)心跳機(jī)制周期性地監(jiān)控tablet server的負(fù)載情況：將增長(zhǎng)到閾值的tablet切分后遷移到負(fù)載壓力較輕的節(jié)點(diǎn)上，可以將用戶的請(qǐng)求均衡分布到tablet server上；HBase的數(shù)據(jù)在存儲(chǔ)節(jié)點(diǎn)上的負(fù)載均衡由HDFS完成.一個(gè)文件的數(shù)據(jù)保存在一個(gè)個(gè)block中，當(dāng)增加一個(gè)block時(shí)，通過(guò)以下四種方式保證數(shù)據(jù)節(jié)點(diǎn)的均衡負(fù)載［38］：

（1）將數(shù)據(jù)塊的一個(gè)副本放在正在寫這個(gè)數(shù)據(jù)塊的節(jié)點(diǎn)上；

（2）盡量將數(shù)據(jù)塊的不同副本分布在不同的機(jī)架上，這樣集群可在完全失去某一機(jī)架的情況下還能存活；

（3）一個(gè)副本通常被放置在和寫文件的節(jié)點(diǎn)同一機(jī)架的某個(gè)節(jié)點(diǎn)上，這樣可以減少跨越機(jī)架的網(wǎng)絡(luò)I／O；

（4）盡量均勻地將HDFS數(shù)據(jù)分布在集群的數(shù)據(jù)節(jié)點(diǎn)中.

2.1.2 Bigtable和HBase的一致性保持

Bigtable和HBase采用多副本冗余的方式滿足系統(tǒng)性能，但多副本冗余的的直接后果就是數(shù)據(jù)一致性問(wèn)題，本節(jié)主要探討B(tài)igtable和HBase如何在不影響系統(tǒng)的可用性和性能的前提下考量一致性問(wèn)題.

Bigtable保證強(qiáng)一致性：某個(gè)時(shí)刻某個(gè)tablet只能為一臺(tái)tablet server服務(wù)，即master將子表分配給某個(gè)tablet server時(shí)確保沒(méi)有其他的tablet server正在使用這個(gè)tablet［29］.通過(guò)Chubby的互斥鎖機(jī)制來(lái)實(shí)現(xiàn)：首先，啟動(dòng)tablet server時(shí)獲取Chubby互斥鎖，一旦tablet server出現(xiàn)故障，master要等到tablet sever的互斥鎖失效時(shí)才能把出現(xiàn)故障的tablet server上的tablet分配到其他tablet server上.

HBase保證最終一致性（eventual consistency），通過(guò)ZooKeeper來(lái)實(shí)現(xiàn)：第一，客戶端的更新請(qǐng)求以其發(fā)送順序被提交；第二，更新操作要么成功，要么失敗，一旦操作失敗，則不會(huì)有客戶端看到更新后的結(jié)果；第三，更新一旦成功，結(jié)果會(huì)持久保存，不會(huì)受到服務(wù)器故障的影響；第四，一個(gè)客戶端無(wú)論連接哪一個(gè)服務(wù)器，看到的是同樣的系統(tǒng)視圖；第五，客戶端看到的系統(tǒng)視圖滯后是有限的，不會(huì)超過(guò)幾十秒［31］.

2.2 Dynamo和Cassandra

Dynamo和Cassandra的數(shù)據(jù)管理方式是非集中式的.系統(tǒng)中沒(méi)有主從節(jié)點(diǎn)的區(qū)分，每個(gè)節(jié)點(diǎn)都和其他節(jié)點(diǎn)周期性地分享元數(shù)據(jù)，通過(guò)Gossip協(xié)議［39］，節(jié)點(diǎn)之間的運(yùn)行狀態(tài)可以相互查詢.非集中式的數(shù)據(jù)管理方式避免了單點(diǎn)故障，但同時(shí)由于沒(méi)有master，實(shí)現(xiàn)METADATA的更新操作會(huì)比較復(fù)雜.

Dynamo是Amazon2007年推出的基于Key－value的大規(guī)模高性能數(shù)據(jù)存儲(chǔ)系統(tǒng)，面向服務(wù)的Amazon平臺(tái)體系結(jié)構(gòu)如圖6所示［40］.

Cassandra是Facebook的采用P2P技術(shù)實(shí)現(xiàn)的去中心化的結(jié)構(gòu)分布式存儲(chǔ)系統(tǒng)，Cassandra系統(tǒng)設(shè)計(jì)目標(biāo)是：運(yùn)行在廉價(jià)商業(yè)硬件上，高寫入吞吐量處理，同時(shí)又不用以犧牲讀取效率為代價(jià)［41］.

2.2.1 Dynamo和Cassandra的容錯(cuò)機(jī)制

Dynamo采用多副本冗余的方式保證系統(tǒng)的高可用性，各節(jié)點(diǎn)之間通過(guò)Gossip機(jī)制相互感知，進(jìn)行故障檢測(cè).Dynamo的容錯(cuò)機(jī)制主要有以下兩點(diǎn)：（1）數(shù)據(jù)回傳.在Dynamo中，一份數(shù)據(jù)被寫到編號(hào)K，K＋1，…，K＋N－1的N臺(tái)機(jī)器上，若機(jī)器K＋i（0≤i≤N－1）宕機(jī)，原本寫入該機(jī)器的數(shù)據(jù)轉(zhuǎn)移到機(jī)器K＋N上，若在給定的時(shí)間T內(nèi)機(jī)器K＋i恢復(fù)，K＋N通過(guò)Gossip機(jī)制感知到，將數(shù)據(jù)回傳到K＋i上.（2）Merkle Tree［42］同步.當(dāng)超過(guò)時(shí)間T機(jī)器K＋i還沒(méi)有恢復(fù)服務(wù)的話，被認(rèn)為是永久性異常，通過(guò)Merkle Tree機(jī)制從其他副本進(jìn)行數(shù)據(jù)同步［27］.

圖6 面向服務(wù)的Amazon平臺(tái)［40］Fig.6 Service－Oriented Amazon Platform

Cassandra同Dynamo一樣通過(guò)Gossip跟蹤各節(jié)點(diǎn)心跳信息，判斷其異常與否.Cassandra通過(guò)網(wǎng)絡(luò)條件、服務(wù)器負(fù)載等復(fù)雜的檢測(cè)機(jī)制判斷是否宕機(jī).一旦檢測(cè)到某一節(jié)點(diǎn)故障，原先對(duì)該節(jié)點(diǎn)的操作，會(huì)由其他節(jié)點(diǎn)替代，需要開啟Hinted Handoff操作，若一個(gè)節(jié)點(diǎn)，宕機(jī)時(shí)間超過(guò)1 h，hints的數(shù)據(jù)將不會(huì)寫入到其他節(jié)點(diǎn).因此在每一個(gè)節(jié)點(diǎn)上由Node Tool定期執(zhí)行Node Repair確保數(shù)據(jù)的一致性.在宕機(jī)節(jié)點(diǎn)恢復(fù)之后，也要執(zhí)行repair，幫助恢復(fù)數(shù)據(jù)［43］.

Dynamo采用虛擬節(jié)點(diǎn)技術(shù)改進(jìn)了傳統(tǒng)一致性hash［44］中由于節(jié)點(diǎn)的異構(gòu)性帶來(lái)的負(fù)載不均衡問(wèn)題，將數(shù)據(jù)均勻地劃分到各個(gè)節(jié)點(diǎn)上，保證系統(tǒng)的健壯性：每個(gè)節(jié)點(diǎn)根據(jù)性能差異分配多個(gè)token，每個(gè)token對(duì)應(yīng)一個(gè)虛擬節(jié)點(diǎn)，其處理能力基本相同.存儲(chǔ)數(shù)據(jù)時(shí)，按照hash值映射到的虛擬節(jié)點(diǎn)區(qū)域，最終存儲(chǔ)在該虛擬節(jié)點(diǎn)對(duì)應(yīng)的物理節(jié)點(diǎn)上.假設(shè)Dynamo集群中原有三個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分配三個(gè)token：node 1（1，4，7），node 2（2，3，8），node 3（0，5，9）.存數(shù)據(jù)時(shí)，先計(jì)算key的hash值，根據(jù)hash值將數(shù)據(jù)存放在對(duì)應(yīng)token所在的節(jié)點(diǎn)上.若此時(shí)增加一個(gè)節(jié)點(diǎn)node 4，集群可能會(huì)將node 1和node 3的token1、token5遷移到node 4，token重新分配后的結(jié)果為：node 1（4，7），node 2（2，3，8），node 3（0，9），node 4（1，5），從而達(dá)到負(fù)載均衡的目標(biāo)，見圖7.

圖7 Dynamo虛擬節(jié)點(diǎn)［27］Fig.7 Virtual nodes of Dynamo

改進(jìn)后的一致性hash，將負(fù)載較大的虛擬節(jié)點(diǎn)分配給性能較強(qiáng)的物理節(jié)點(diǎn)，將負(fù)載較小的虛擬節(jié)點(diǎn)分配給性能較弱的物理節(jié)點(diǎn)，最終達(dá)成動(dòng)態(tài)負(fù)載均衡.

Cassandra避免節(jié)點(diǎn)訪問(wèn)過(guò)載的容忍機(jī)制同Dynamo一樣，來(lái)源于一致性hash算法，通過(guò)Order－preserving hash function（保序Hash）實(shí)現(xiàn).Cassandra的設(shè)計(jì)考慮到傳統(tǒng)的一致性hash算法無(wú)視節(jié)點(diǎn)處理能力的不均衡和分配數(shù)據(jù)的不均勻的弊端，不同于Dynamo增加虛擬節(jié)點(diǎn)的做法，Cassandra采用Stoica等人的的思想，分析hash環(huán)上各節(jié)點(diǎn)的負(fù)載信息，優(yōu)先routing輕載節(jié)點(diǎn)減輕重載節(jié)點(diǎn)負(fù)擔(dān)以均衡負(fù)載［45］.

2.2.2 Dynamo和Cassandra的一致性保持

在Dynamo中，最重要的是要保證寫操作的高可用性（Always Writeable），Dynamo犧牲部分的一致性，采用多副本冗余的方式來(lái)保證系統(tǒng)的高可用性.Dynamo只保證最終一致性，即：若多個(gè)節(jié)點(diǎn)之間的更新順序不一致，客戶端可能讀取不到預(yù)期的結(jié)果.Dynamo中涉及三個(gè)重要參數(shù)NWR，N代表數(shù)據(jù)的備份數(shù)，W 代表成功寫操作的最少節(jié)點(diǎn)數(shù)，R代表成功讀操作的最少節(jié)點(diǎn)數(shù).Dynamo中要求W＋R＞N，以保證當(dāng)不超過(guò)一臺(tái)機(jī)器發(fā)生故障的時(shí)候，至少能讀到一份有效的數(shù)據(jù).

Cassandra有一套自己的機(jī)制來(lái)保障最終一致性：（1）Read Repair.在讀數(shù)據(jù)時(shí)，系統(tǒng)會(huì)先讀取數(shù)據(jù)副本，若發(fā)現(xiàn)不一致，則進(jìn)行一致性修復(fù).根據(jù)讀一致性等級(jí)不同，有不同的解決方案：當(dāng)讀一致性要求為ONE時(shí)，會(huì)立即返回用戶最近的一份副本，后臺(tái)執(zhí)行Read Repair，意味著可能第一次讀不到最新的數(shù)據(jù)；當(dāng)讀一致性要求為QUORUM時(shí)，則在讀取超過(guò)半數(shù)的一致性的副本后返回一份副本給客戶端，剩余節(jié)點(diǎn)的一致性檢查和修復(fù)則在后臺(tái)執(zhí)行；當(dāng)讀一致性為ALL時(shí)，則只有Read Repair完成后才能返回一份一致性的副本給客戶端；（2）Anti－Entropy Node Repair.通過(guò) Node Tool負(fù)責(zé)管理維護(hù)各個(gè)節(jié)點(diǎn)，由 Anti－Entropy聲稱的Merkle Tree對(duì)比發(fā)現(xiàn)數(shù)據(jù)副本的不一致，通過(guò)org.apache.cassandra.streaming來(lái)進(jìn)行一致性修復(fù)；（3）Hinted Handoff作為實(shí)現(xiàn)最終一致性的優(yōu)化措施，減少最終一致的時(shí)間窗口［46］.

2.3 PNUTS

PNUTS是由Yahoo公司推出的超大規(guī)模并發(fā)分布式數(shù)據(jù)庫(kù)系統(tǒng).PNUTS提供哈希表和順序表兩種數(shù)據(jù)存儲(chǔ)方式，可以對(duì)海量并發(fā)的更新和查詢請(qǐng)求提供快速響應(yīng)，它是一個(gè)托管型、集中式管理的分布式系統(tǒng)，并且能夠?qū)崿F(xiàn)自動(dòng)化的負(fù)載均衡和故障恢復(fù)，以減輕使用的復(fù)雜度［47］.PNUTS的系統(tǒng)結(jié)構(gòu)如圖8所示：系統(tǒng)被劃分為多個(gè)region，每個(gè)region包含整套完整的組件，例如：tablet controller維護(hù)活動(dòng)節(jié)點(diǎn)的路由信息以判斷節(jié)點(diǎn)失效與否；Yahoo！Message Broker（以下簡(jiǎn)稱YMB）是基于topic的訂閱／發(fā)布系統(tǒng)，一旦數(shù)據(jù)的更新操作發(fā)布到Y(jié)MB則被認(rèn)為是提交了的.在提交后的某個(gè)時(shí)間點(diǎn)，該更新操作被異步廣播到不同的region和副本上.PNUTS區(qū)別于其他NoSQL系統(tǒng)的特性是：沒(méi)有采用傳統(tǒng)的日志或歸檔數(shù)據(jù)實(shí)現(xiàn)復(fù)制保證高可用性，而是利用訂閱／發(fā)布機(jī)制來(lái)實(shí)現(xiàn).

圖8 PNUTS系統(tǒng)結(jié)構(gòu)［47］Fig.8 Architecture of PNUTS

2.3.1 PNUTS的容錯(cuò)機(jī)制

PNUTS通過(guò)YMB防止在更新過(guò)程中的節(jié)點(diǎn)故障，從遠(yuǎn)程副本的拷貝實(shí)現(xiàn)故障恢復(fù).YMB保證在一個(gè)Message Broker機(jī)器宕機(jī)后，已發(fā)布的消息仍然會(huì)傳遞給topic訂閱者，該功能通過(guò)將message記錄在不同服務(wù)器上的多個(gè)磁盤上來(lái)實(shí)現(xiàn).所有的消息直到被系統(tǒng)確認(rèn)已經(jīng)寫到數(shù)據(jù)庫(kù)中后才會(huì)被YMB清洗.

PNUTS中的故障恢復(fù)是指從其他的副本中復(fù)制已丟失的tablet，其復(fù)制策略具體實(shí)現(xiàn)如下：首先，tablet controller從source tablet（一種特定的遠(yuǎn)程副本）申請(qǐng)一份拷貝；接著，發(fā)布檢查點(diǎn)消息到Y(jié)MB，確保正在執(zhí)行的更新操作都在source tablet上進(jìn)行；最后，將source tablet復(fù)制到目標(biāo)region.要實(shí)現(xiàn)這個(gè)恢復(fù)策略要求tablet boundary在副本間保持同步，并且所有region的table在同一時(shí)間分裂.該策略的最大開銷是將一個(gè)tablet從一個(gè)region遷移到另一個(gè)region，為避免遠(yuǎn)程獲取的開銷，通常會(huì)創(chuàng)建backup regions就近維護(hù)一個(gè)backup副本.

PNUTS擁有類似Bigtable均衡節(jié)點(diǎn)訪問(wèn)壓力避免“熱點(diǎn)”的容錯(cuò)機(jī)制，PNUTS主要瓶頸是存儲(chǔ)單元和YMB的磁盤訪問(wèn)量.目前，用戶還不能共享所有的組件，只能共享routers和tablet controller，不同的用戶會(huì)被分配到不同的存儲(chǔ)單元和YMB.PNUTS的tablet代表的是數(shù)據(jù)表被水平切分成的一組組記錄.tablet分散在服務(wù)器上，每個(gè)服務(wù)器可能包含成百上千個(gè)tablet.在PNUTS中，一個(gè)tablet占用幾百M(fèi)或幾個(gè)G的容量，包含幾千條記錄，tablet被靈活地分配到不同的server上以均衡負(fù)載.系統(tǒng)使用n－bit hash函數(shù)來(lái)得到hash值H（），其中0≤H（）≤2n.hash空間［0，2n］被分裂為多個(gè)區(qū)間，每個(gè)區(qū)間對(duì)應(yīng)一個(gè)tablet.要將一個(gè)key映射到一個(gè)tablet上，首先對(duì)這個(gè)key做hash，得到該key的H（）；然后搜索區(qū)間集；最后，采用二分查找定位到相應(yīng)的閉合區(qū)間及對(duì)應(yīng)的tablet和存儲(chǔ)單元.PNUTS也采用了順序分裂的方式按照key或H（key）來(lái)劃分順序表及其中的數(shù)據(jù).圖8中Routers僅包含一個(gè)區(qū)間映射的緩存副本，這個(gè)映射為tablet controller所有，router周期性地輪詢tablet controller獲取映射更新，當(dāng)tablet空間到達(dá)閾值需要分裂時(shí)，tablet controller便在存儲(chǔ)單元間移動(dòng)tablet以均衡負(fù)載或處理故障.

2.3.2 PNUTS的一致性保持

PNUTS的一致性模型介于即時(shí)一致性和最終一致性之間，被稱為per－record timeline consistency：一條記錄所有的副本按照相同的順序執(zhí)行更新操作，如圖9所示.timeline上包括對(duì)主鍵的增、刪、改操作.對(duì)任意副本的讀操作都會(huì)從這個(gè)timeline上返回一致的版本，并且副本總是沿著timeline向前移動(dòng).該一致性模型實(shí)現(xiàn)過(guò)程如下：首先，指派一個(gè)副本作為master，每條記錄之間相互獨(dú)立，互不干擾，對(duì)記錄的所有操作轉(zhuǎn)發(fā)給master，被指派為master的副本是自適應(yīng)不斷變化的，這主要依據(jù)哪個(gè)副本接受大多數(shù)的寫操作；其次，隨著寫操作的執(zhí)行，記錄的序列號(hào)遞增，每條記錄的序列號(hào)包括該記錄的generation（每一個(gè)新的insert操作）和version（每一個(gè)update操作創(chuàng)建一個(gè)version）.

圖9 Per－record timeline一致性［47］Fig.9 Per－record timeline consistency

3 討 論

本文探討了五種典型的NoSQL系統(tǒng)的容錯(cuò)機(jī)制及相關(guān)的一致性保持解決方案.它們有各自的適用場(chǎng)景，因此不能簡(jiǎn)單地判斷孰優(yōu)孰劣，只有結(jié)合業(yè)務(wù)特性，才會(huì)產(chǎn)生高效的解決方案.例如Bigtable和Dynamo，后者的亮點(diǎn)是“無(wú)主”的架構(gòu)，從而能避免單點(diǎn)故障，但并不代表Dynamo比Bigtable更優(yōu)秀.Bigtable的主控節(jié)點(diǎn)足夠可靠，達(dá)到“4個(gè)9”的可靠性，足夠滿足通常的應(yīng)用場(chǎng)景，因此可以采取簡(jiǎn)單的一個(gè)master主控節(jié)點(diǎn)的解決方案.Bigtable、HBase、Dynamo、Cassandra、PNUTS的容錯(cuò)機(jī)制及一致性保持方案的異同點(diǎn)及自身主要的優(yōu)缺點(diǎn)概括如表1所示.

面對(duì)海量數(shù)據(jù)的挑戰(zhàn)，Bigtable、HBase、Dynamo、Cassandra、PNUTS等優(yōu)秀的NoSQL存儲(chǔ)系統(tǒng)解決了高可靠性、可用性、和可擴(kuò)展性的問(wèn)題，這些面向互聯(lián)網(wǎng)的應(yīng)用滿足橫向擴(kuò)展，面對(duì)用戶量、訪問(wèn)量的急速增長(zhǎng)的挑戰(zhàn)，靈活提高負(fù)載的能力為學(xué)術(shù)界、工業(yè)界提供了新思路.2011年，“云計(jì)算”、“大數(shù)據(jù)”襲來(lái)，越來(lái)越多的企業(yè)趨之若鶩，大量企業(yè)級(jí)的應(yīng)用也在發(fā)生革命.越來(lái)越多的企業(yè)級(jí)應(yīng)用要求更快的訪問(wèn)速度，內(nèi)存計(jì)算和內(nèi)存數(shù)據(jù)管理也成為熱門的研究方向.內(nèi)存數(shù)據(jù)管理中列存儲(chǔ)、多核多節(jié)點(diǎn)的分布式實(shí)現(xiàn)等本質(zhì)與本文分析比較的五種典型NoSQL系統(tǒng)實(shí)現(xiàn)有諸多的契合點(diǎn)，本文從一定程度上為內(nèi)存數(shù)據(jù)管理的研究提供經(jīng)驗(yàn)指導(dǎo).

表1 NoSQL系統(tǒng)的對(duì)比Tab.1 Comparison of NoSQL systems

［1］ NoSQL matters.NoSQL DEFINITION［EB／OL］.［2014－06－08］.http：／／nosql－database.org.

［2］ 百度百科.淘寶網(wǎng)［EB／OL］.［2014－06－08］.http：／／baike.baidu.com／view／1590.htm？fromtitle＝%E6%B7%98%E5%AE%9D＆fromid＝145661 ＆type＝syn

［3］ 淘寶網(wǎng)品牌介紹［EB／OL］.［2014－06－08］.http：／／www.maigoo.com／maigoocms／special／services／170taobao.html.

［4］ 張瀟.“雙11”網(wǎng)購(gòu)瘋狂！天貓及淘寶成交額突破350億［EB／OL］.［2014－06－08］.http：／／money.163.com／13／1112／16／9DGCT0BJ00253B0H.html.

［5］ CONSTINE J.How Big Is Facebook’s Data？2.5 Billion Pieces Of Content And 500＋ TerabytesIngested Every Day［EB／OL］.［2014－06－08］.http：／／techcrunch.com／2012／08／22／how－big－is－facebooks－data－2－5－billion－piecesof－content－and－500－terabytes－ingested－every－day／.

［6］ HENDERSON C.Flickr－Scalable Web Architectures：Common Patterns and Approaches［EB／OL］.［2014－06－08］.http：／／krisjordan.com／2008／09／16／cal－h(huán)enderson－scalable－web－architectures－common－patterns－and－approaches.

［7］ PLATTNER H，ZEIER A.In－memory Data Management：Technology and Applications［M］.Berlin：Springer，2012.

［8］ BREWER E A.Towards robust distributed systems（Invited Talk）.ACM SIGACT－SIGOPS，2000.

［9］ GILBERT S，LYNCH N.Brewer’s conjecture and the feasibility of consistent，available，partition－tolerant web services［C］.SIGACT News，2002.

［10］ BREWER E A.Pushing the cap：Strategies for consistency and availability［J］.IEEE Computer，2012，42（2）：23－29.

［11］ AGRAWAL D，DAS S，ABBADI A E.Data Management in the Cloud Challenges and Opportunities［M］.California：Morgan ＆Claypool，2013.

［12］ VOGELS W.Eventually consistent［J］.ACM Queue，2008，6（6）：14－19.

［13］ 何坤.基于內(nèi)存數(shù)據(jù)庫(kù)的分布式數(shù)據(jù)庫(kù)架構(gòu)［J］.程序員，2010（7）：116－118.

［14］ WIKIPEDIA.CAP theorem［EB／OL］.［2014－06－08］.http：／／en.wikipedia.org／wiki／CAP＿theorem.

［15］ COULOURIS G，DOLLIMORE J，KINDBERG T，et al.Distributed Systems：Concepts and Design［M］.5th ed.［s.l.］：Addison－Wesley，2011.

［16］ Chubby總結(jié)［EB／OL］.［2014－06－08］.http：／／blog.csdn.net／ggxxkkll／article／details／7874465.

［17］ Mike Burrows.The Chubby lock service for loosely－coupled distributed systems［C］.OSDI，2006.

［18］ Google利器之Chubby［EB／OL］.［2014－06－08］.http：／／blog.csdn.net／historyasamirror／article／details／3870168.

［19］ LAMPORT L.Paxos made simple［J］.ACM SIGACT News，2001.

［20］ GIFFORD D K.Weighted voting for replicated data［C］.SOSP，1979.

［21］ AVIZIENIS A.Design of fault－tolerant computers［C］.AFIPS，1967.

［22］ OZSU M T，VALDURIEZ P.Principles of Distributed Database Systems［M］.3rd ed.［s.l.］：Springer，2011.

［23］ GUERRAOUI R，SCHIPER A.Fault－Tolerance by Replication in Distributed System［EB／OL］.［2014－06－12］.http：／／link.springer.com／chapter／10.1007%2FBFb0013477＃page－1.

［24］ SAITO Y，SHAPIRO M.Optimistic Replication［C］.ACM Computing Surveys，2005.

［25］ BERNSTEIN P A，NEWCOMER E.Principles of Transaction Processing［M］.2nd ed.Elsevier，2009.

［26］ 李磊.分布式系統(tǒng)中容錯(cuò)機(jī)制性能優(yōu)化技術(shù)研究［D］.湖南：國(guó)防科技大學(xué)，2007.

［27］ 楊傳輝.大規(guī)模分布式存儲(chǔ)系統(tǒng)原理解析與架構(gòu)實(shí)踐［M］.北京：機(jī)械工業(yè)出版社，2013.

［28］ Distributed Algorithms in NoSQL Databases［EB／OL］.［2014－06－10］.http：／／vdisk.weibo.com／s／t3HPkX2GaIpf.

［29］ CHANG F，DEAN J，GHEMAWAT S，et al.Bigtable：A Distributed Storage System for Structured Data［C］.OSDI，2006.

［30］ DEAN J.Building Large－Scale Internet Services［EB／OL］.［2014－06－19］.http：／／static.googleusercontent.com／media／research.google.com／zh－CN／／people／jeff／SOCC2010－keynote－slides.pdf.

［31］ HADOOP W T.The Definitive Guide［M］.O＇Reilly，2012.

［32］ Apache ZooKeeper.What is ZooKeeper［EB／OL］.［2014－06－19］.http：／／zookeeper.apache.org／.

［33］ Searchtb.HBase技術(shù)介紹［EB／OL］.［2014－06－08］.http：／／www.searchtb.com／2011／01／understanding－h(huán)base.html.

［34］ GHEMAWAT S，Howard Gobioff，and Shun－Tak Leung.The Google File System［C］.SOSP，2006.

［35］ 康毅.HBase大對(duì)象存儲(chǔ)方案的設(shè)計(jì)與實(shí)現(xiàn)［D］.南京大學(xué)，2013.

［36］ APACHE HBASE［EB／OL］.［2014－06－15］.http：／／hbase.apache.org／replication.html.

［37］ 負(fù)載均衡技術(shù)大盤點(diǎn)［EB／OL］.［2014－06－10］.http：／／www.mmic.net.cn／news／865／9.htm.

［38］ 陸嘉恒.Hadoop實(shí)戰(zhàn)［M］.北京：機(jī)械工業(yè)出版社，2011.

［39］ SUBRAMANIYAN R.Gossip－based failure detection and consensus for terascale computing［EB／OL］.［2014－06－15］.http：／／etd.fcla.edu／UF／UFE0000799／subramaniyan＿r.pdf.

［40］ DECANDIA G，HASTORUN D，JAMPANI，et al.Dynamo：Amazon’s highly available key－value store［C］.SOSP，2007.

［41］ LAKSHMAN A，MALIK P.Cassandra– A Decentralized Structure Storage System［C］.SIGMOD，2008.

［42］ MERKLE R.A digital signature based on a conventional encryption function［C］.Proceedings of CRYPTO，1988.

［43］ DATASTAX.Internode communications［EB／OL］.［2014－06－11］.http：／／www.datastax.com／documentation／cassandra／2.0／cassandra／architecture／architectureGossipAbout＿c.html.

［44］ KARGER D，LEHMAN E，LEIGHTONT，et al.Consistent hashing and random trees［C］／／Procceding STOC’97 ACM Symposium，1997：643－663.

［45］ STOICA I，MORRIS R，KARGER D，et al.Chord：A Scalable Peer－to－peer Lookup Service for Internet Applications［C］／／SIGCOMM’01.San Diego：ACM，2001.

［46］ DATASTAX.Configuring data consistency［EB／OL］.［2014－06－11］.http：／／link.springer.com／chapter／10.1007%2FBFb0013477＃page－1.

［47］ COOPER B F，RAMAKRISHNAN R，SRIVASTAVA U，et al.PNUTS：Yahoo！’s Hosted Data Serving Platform［C］.VLDB’08.Auckland：ACM，2008.