卷1：第13章 NoSQL生態(tài)系統(tǒng)

作者：Adam Marcus 譯 / iammutex

與本書(shū)中提到的其它主題不同，NoSQL不是一個(gè)工具，而是由一些具有互補(bǔ)性和競(jìng)爭(zhēng)性的工具組成的一個(gè)概念，是一個(gè)生態(tài)圈。這些被稱作NoSQL的工具，在存儲(chǔ)數(shù)據(jù)的方式上，提供了一種與（基于SQL語(yǔ)言的）關(guān)系型數(shù)據(jù)庫(kù)截然不同的思路。要想了解NoSQL，我們必須先了解現(xiàn)有的這些工具，去理解那些引導(dǎo)它們開(kāi)拓出新的存儲(chǔ)領(lǐng)域的設(shè)計(jì)思路。 如果你正在考慮使用NoSQL，你應(yīng)該會(huì)馬上發(fā)現(xiàn)你有很多種選擇。NoSQL系統(tǒng)舍棄了許了傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的方便之處，而把一些通常由關(guān)系型數(shù)據(jù)庫(kù)本身來(lái)完成的任務(wù)交給了應(yīng)用層來(lái)完成。這需要開(kāi)發(fā)人員更深入的去了解存儲(chǔ)系統(tǒng)的架構(gòu)和具體實(shí)現(xiàn)。

13.1 NoSQL其名

在給NoSQL下定義之前，我們先來(lái)試著從它的名字上做一下解讀，顧名思義，NoSQL系統(tǒng)的數(shù)據(jù)操作接口應(yīng)該是非SQL類型的。但在NoSQL社區(qū)，NoSQL被賦予了更具有包容性的含義，其意為Not Only SQL，即NoSQL提供了一種與傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)不太一樣的存儲(chǔ)模式，這為開(kāi)發(fā)者提供了在關(guān)系型數(shù)據(jù)庫(kù)之外的另一種選擇。有時(shí)候你可能會(huì)完全用NoSQL數(shù)據(jù)庫(kù)代替關(guān)系型數(shù)據(jù)加，但你也可以同時(shí)使用關(guān)系型和非關(guān)系型存儲(chǔ)來(lái)解決具體的問(wèn)題。 在進(jìn)入NoSQL的大門之前，我們先來(lái)看看哪些場(chǎng)景下使用關(guān)系型數(shù)據(jù)庫(kù)更合適，哪些使用NoSQL更合適。

13.1.1 SQL及其關(guān)聯(lián)型結(jié)構(gòu)

SQL是一種任務(wù)描述性的查詢語(yǔ)言，所謂任務(wù)描述性的查詢語(yǔ)言，就是說(shuō)它只描述他需要系統(tǒng)做什么，而不告訴系統(tǒng)如何去做。例如：查出39號(hào)員工的信息，查出員工的名字和電話，只查找做會(huì)計(jì)工作的員工信息，計(jì)算出每個(gè)部門的員工總數(shù)，或者是對(duì)員工表和經(jīng)理表做一個(gè)聯(lián)合查詢。 簡(jiǎn)單的說(shuō)，SQL讓我們可以直接向數(shù)據(jù)庫(kù)提出上述問(wèn)題而不必考慮數(shù)據(jù)是如何在磁盤上存儲(chǔ)的，使用哪些索引來(lái)查詢數(shù)據(jù)，或者說(shuō)用哪種算法來(lái)處理數(shù)據(jù)。在關(guān)系型數(shù)據(jù)庫(kù)中有一個(gè)重要的組件，叫做查詢優(yōu)化器，正是它來(lái)推算用哪種操作方式能夠更快的完成操作。查詢優(yōu)化器通常比一般的數(shù)據(jù)庫(kù)用戶更聰明，但是有時(shí)候由于沒(méi)有充足的信息或者系統(tǒng)模型過(guò)于簡(jiǎn)單，也會(huì)導(dǎo)致查詢優(yōu)化器不能得出最有效的操作方式。 作為目前應(yīng)用最廣的數(shù)據(jù)庫(kù)系統(tǒng)，關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)以其關(guān)聯(lián)型的數(shù)據(jù)模型而命名。在關(guān)聯(lián)型的數(shù)據(jù)模型中，在現(xiàn)實(shí)世界中的不同類型的個(gè)體被存儲(chǔ)在不同的表里。比如有一個(gè)專門存員工的員工表，有一個(gè)專門存部門的部門表。每一行數(shù)據(jù)又包含多個(gè)列，比如員工表里可能包含了員工號(hào)，員工工資，生日以及姓名等，這些信息項(xiàng)被存在員工表中的某一列中。 關(guān)聯(lián)型的模型與SQL是緊密想連的。簡(jiǎn)單的查詢操作，比如查詢符合某個(gè)條件的所有行（例：employeeid = 3, 或者 salary > $20000）。更復(fù)雜一些的任務(wù)會(huì)讓數(shù)據(jù)庫(kù)做一些額外的工作，比如跨表的聯(lián)合查詢（例：查出3號(hào)員的部門名稱是什么）。一些復(fù)雜的查詢，比如統(tǒng)計(jì)操作（例：算出所有員工的平均工資），甚至可能會(huì)導(dǎo)致全表掃描。 關(guān)聯(lián)型的數(shù)據(jù)模型定義了高度結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)，以及對(duì)這些結(jié)構(gòu)之間關(guān)系的嚴(yán)格定義。在這樣的數(shù)據(jù)模型上執(zhí)行的查詢操作會(huì)比較局限，而且可能會(huì)導(dǎo)致復(fù)雜的數(shù)據(jù)遍歷操作。數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性及查詢的復(fù)雜性，會(huì)導(dǎo)致系統(tǒng)產(chǎn)生如下的一些限制： 復(fù)雜導(dǎo)致不確定性。使用SQL的一個(gè)問(wèn)題就是計(jì)算某個(gè)查詢的代價(jià)或者產(chǎn)生的負(fù)載幾乎是不可能的。使用簡(jiǎn)單的查詢語(yǔ)言可能會(huì)導(dǎo)致應(yīng)用層的邏輯更復(fù)雜，但是這樣可以將存儲(chǔ)系統(tǒng)的工作簡(jiǎn)單化，讓它只需要響應(yīng)一些簡(jiǎn)單的請(qǐng)求。 對(duì)一個(gè)問(wèn)題建模有很多種方式。其中關(guān)聯(lián)型的數(shù)據(jù)模型是非常嚴(yán)格的一種：表結(jié)構(gòu)的定義規(guī)定了表中每一行數(shù)據(jù)的存儲(chǔ)內(nèi)容。如果你的數(shù)據(jù)結(jié)構(gòu)化并沒(méi)有那么強(qiáng)，或者對(duì)每一行數(shù)據(jù)的要求比較靈活，那可能關(guān)聯(lián)型的數(shù)據(jù)模型就太過(guò)嚴(yán)格了。類似的，應(yīng)用層的開(kāi)發(fā)人員可能對(duì)關(guān)聯(lián)型的數(shù)據(jù)結(jié)構(gòu)并不滿意。比如很多應(yīng)用程序是用面向?qū)ο蟮恼Z(yǔ)言寫的，數(shù)據(jù)在這些語(yǔ)言中通常是以列表、隊(duì)列或集合的形式組織的，程序員們當(dāng)然希望他們的數(shù)據(jù)存儲(chǔ)層也能和應(yīng)用層的數(shù)據(jù)模型一致。 當(dāng)數(shù)據(jù)量增長(zhǎng)到一臺(tái)機(jī)器已經(jīng)不能容納，我們需要將不同的數(shù)據(jù)表分布到不同的機(jī)器。而為了避免在不同機(jī)器上的數(shù)據(jù)表在進(jìn)行聯(lián)合查詢時(shí)需要跨網(wǎng)絡(luò)進(jìn)行。我們必須進(jìn)行反范式的數(shù)據(jù)庫(kù)設(shè)計(jì)，這種設(shè)計(jì)方式要求我們把需要一次性查詢到的數(shù)據(jù)存儲(chǔ)在一起。這樣做使得我們的系統(tǒng)變得就像一個(gè)主鍵查詢系統(tǒng)一樣，于是我們開(kāi)始思考，是否有其它更適合我們數(shù)據(jù)的數(shù)據(jù)模型。 通常來(lái)說(shuō)，舍棄多年以來(lái)的設(shè)計(jì)思路是不明智的。當(dāng)你要把數(shù)據(jù)存到數(shù)據(jù)庫(kù)，當(dāng)考慮到SQL與關(guān)聯(lián)型的數(shù)據(jù)模型，這些都是數(shù)十年的研究的開(kāi)發(fā)成果，提供豐富的數(shù)據(jù)模型，提供復(fù)雜操作的保證。而當(dāng)你的問(wèn)題涉及到大數(shù)據(jù)量，高負(fù)載或者說(shuō)你的數(shù)據(jù)結(jié)構(gòu)在SQL與關(guān)聯(lián)型數(shù)據(jù)模型下很難得到優(yōu)化，NoSQL可能是更好的選擇。

13.1.2 NoSQL的啟示

NoSQL運(yùn)動(dòng)受到了很多相關(guān)研究論文的啟示，這所有論文中，最核心的有兩個(gè)。 Google的BigTable[CDG+06]提出了一種很有趣的數(shù)據(jù)模型，它將各列數(shù)據(jù)進(jìn)行排序存儲(chǔ)。數(shù)據(jù)值按范圍分布在多臺(tái)機(jī)器，數(shù)據(jù)更新操作有嚴(yán)格的一致性保證。 Amazon的Dynamo[DHJ+07]使用的是另外一種分布式模型。Dynamo的模型更簡(jiǎn)單，它將數(shù)據(jù)按key進(jìn)行hash存儲(chǔ)。其數(shù)據(jù)分片模型有比較強(qiáng)的容災(zāi)性，因此它實(shí)現(xiàn)的是相對(duì)松散的弱一致性：最終一致性。 接下來(lái)我們會(huì)深入介紹這些設(shè)計(jì)思想，而實(shí)際上在現(xiàn)實(shí)中這些思想經(jīng)常是混搭使用的。比如像HBase及其它一些NoSQL系統(tǒng)他們?cè)谠O(shè)計(jì)上更接受BigTable的模型，而像Voldemort 系統(tǒng)它就和Dynamo更像。同時(shí)還有像Cassandra這種兩種特性都具備的實(shí)現(xiàn)（它的數(shù)據(jù)模型和BigTable類似，分片策略和一致性機(jī)制和Dynamo類似）。

13.1.3 特性概述

NoSQL系統(tǒng)舍棄了一些SQL標(biāo)準(zhǔn)中的功能，取而代之的是一些簡(jiǎn)單靈活的功能。NoSQL 的構(gòu)建思想就是盡量簡(jiǎn)化數(shù)據(jù)操作，盡量讓操作的執(zhí)行效率可預(yù)估。在很多NoSQL系統(tǒng)里，復(fù)雜的操作都是留給應(yīng)用層來(lái)做的，這樣的結(jié)果就是我們對(duì)數(shù)據(jù)層進(jìn)行的操作得到簡(jiǎn)化，讓操作效率可預(yù)知。 NoSQL系統(tǒng)不僅舍棄了很多關(guān)系數(shù)據(jù)庫(kù)中的操作。它還可能不具備關(guān)系數(shù)據(jù)庫(kù)以下的一些特性：比如通常銀行系統(tǒng)中要求的事務(wù)保證，一致性保證以及數(shù)據(jù)可靠性的保證等。事務(wù)機(jī)制提供了在執(zhí)行多個(gè)命令時(shí)的all-or-nothing保證。一致性保證了如果一個(gè)數(shù)據(jù)更新后，那么在其之后的操作中都能看到這個(gè)更新?？煽啃员ＷC如果一個(gè)數(shù)據(jù)被更新，它就會(huì)被寫到持久化的存儲(chǔ)設(shè)備上（比如說(shuō)磁盤），并且保證在數(shù)據(jù)庫(kù)崩潰后數(shù)據(jù)可恢復(fù)。 通過(guò)放寬對(duì)上述幾點(diǎn)特性的要求，NoSQL系統(tǒng)可以為一些非銀行類的業(yè)務(wù)提供以性能換穩(wěn)定的策略。而同時(shí)，對(duì)這幾點(diǎn)要求的放寬，又使得NoSQL系統(tǒng)能夠輕松的實(shí)現(xiàn)分片策略，將遠(yuǎn)遠(yuǎn)超出單機(jī)容量的大量數(shù)據(jù)分布在多臺(tái)機(jī)器上的。 由于NoSQL系統(tǒng)還處在萌芽階段，本章中提到的很多NoSQL架構(gòu)都是用于滿足各種不同用戶的需求的。對(duì)這些架構(gòu)進(jìn)行總結(jié)不太可能，因?yàn)樗鼈兛傇谧兓?。所以希望你能記住的一點(diǎn)是，不同的NoSQL系統(tǒng)的特點(diǎn)是不同的，通過(guò)本章的內(nèi)容，希望你能該根據(jù)自己的業(yè)務(wù)情況來(lái)選擇合適的NoSQL系統(tǒng)，而本章內(nèi)容不可能給你直接的答案。 當(dāng)你去考查一個(gè)NoSQL系統(tǒng)的時(shí)候，下面的的幾點(diǎn)是值得注意的： 數(shù)據(jù)模型及操作模型：你的應(yīng)用層數(shù)據(jù)模型是行、對(duì)象還是文檔型的呢？這個(gè)系統(tǒng)是否能支持你進(jìn)行一些統(tǒng)計(jì)工作呢？ 可靠性：當(dāng)你更新數(shù)據(jù)時(shí)，新的數(shù)據(jù)是否立刻寫到持久化存儲(chǔ)中去了？新的數(shù)據(jù)是否同步到多臺(tái)機(jī)器上了？ 擴(kuò)展性：你的數(shù)據(jù)量有多大，單機(jī)是否能容下？你的讀寫量求單機(jī)是否能支持？ 分區(qū)策略：考慮到你對(duì)擴(kuò)展性，可用性或者持久性的要求，你是否需要一份數(shù)據(jù)被存在多臺(tái)機(jī)器上？你是否需要知道或者說(shuō)你能否知道數(shù)據(jù)在哪臺(tái)機(jī)器上。 一致性：你的數(shù)據(jù)是否被復(fù)制到了多臺(tái)機(jī)器上，這些分布在不同節(jié)點(diǎn)的數(shù)據(jù)如何保證一致性？ 事務(wù)機(jī)制：你的業(yè)務(wù)是否需要ACID的事務(wù)機(jī)制？ 單機(jī)性能：如果你打算持久化的將數(shù)據(jù)存在磁盤上，哪種數(shù)據(jù)結(jié)構(gòu)能滿足你的需求（你的需求是讀多還是寫多）？寫操作是否會(huì)成為磁盤瓶頸？ 負(fù)載可評(píng)估：對(duì)于一個(gè)讀多寫少的應(yīng)用，諸如響應(yīng)用戶請(qǐng)求的web應(yīng)用，我們總會(huì)花很多精力來(lái)關(guān)注負(fù)載情況。你可能需要進(jìn)行數(shù)據(jù)規(guī)模的監(jiān)控，對(duì)多個(gè)用戶的數(shù)據(jù)進(jìn)行匯總統(tǒng)計(jì)。你的應(yīng)用場(chǎng)景是否需要這樣的功能呢？ 盡管后三點(diǎn)在本章沒(méi)有獨(dú)立的小節(jié)進(jìn)行描述，但它們和其它幾點(diǎn)一樣重要，下面就讓我們對(duì)以上的幾點(diǎn)進(jìn)行闡述。

13.2 NoSQL數(shù)據(jù)模型及操作模型

數(shù)據(jù)庫(kù)的數(shù)據(jù)模型指的是數(shù)據(jù)在數(shù)據(jù)庫(kù)中的組織方式，數(shù)據(jù)庫(kù)的操作模型指的是存取這些數(shù)據(jù)的方式。通常數(shù)據(jù)模型包括關(guān)系模型、鍵值模型以及各種圖結(jié)構(gòu)模型。操作語(yǔ)言可能包括SQL、鍵值查詢及MapReduce等。NoSQL通常結(jié)合了多種數(shù)據(jù)模型和操作模型，提供了不一樣的架構(gòu)方式。

13.2.1 基于key值存儲(chǔ)的NoSQL數(shù)據(jù)模型

在鍵值型系統(tǒng)中，復(fù)雜的聯(lián)合操作以及滿足多個(gè)條件的取數(shù)據(jù)操作就不那么容易了，需要我們換一種思維來(lái)建立和使用鍵名。如果一個(gè)程序員既想通過(guò)員工號(hào)查到員工信息，又想通過(guò)部門號(hào)查到員工信息，那么他必須建立兩種類型的鍵值對(duì)。例如 emplyee:30 這個(gè)鍵用于指向員工號(hào)為30的員工信息。employee_departments:20 可能用到指向一個(gè)包含在20號(hào)部門工作的所有員工工號(hào)的列表。這樣數(shù)據(jù)庫(kù)中的聯(lián)合操作就被轉(zhuǎn)換成業(yè)務(wù)層的邏輯了：要獲取部門號(hào)為20的所有員工的信息，應(yīng)用層可以先獲取employee_departments:20 這個(gè)列表，然后再循環(huán)地拿這個(gè)列表中的ID通過(guò)獲取employee:ID得到所有員工的信息。 鍵值查找的一個(gè)好處是，對(duì)數(shù)據(jù)庫(kù)的操作模式是固定的，這些操作所產(chǎn)生的負(fù)載也是相對(duì)固定且可預(yù)知的。這樣像分析整個(gè)應(yīng)用中的性能瓶頸這種事，就變得簡(jiǎn)單多了。因?yàn)閺?fù)雜的邏輯操作并不是放在數(shù)據(jù)庫(kù)里面黑箱操作了。不過(guò)這樣做之后，業(yè)務(wù)邏輯和數(shù)據(jù)邏輯可能就沒(méi)那么容易分清了。 下面我們快速地把各種鍵值模型的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單描述一下。看看不同的NoSQL系統(tǒng)的在這方面的不同實(shí)現(xiàn)方式。

Key-Value 存儲(chǔ)

Key-Value存儲(chǔ)可以說(shuō)是最簡(jiǎn)單的NoSQL存儲(chǔ)。每個(gè)key值對(duì)應(yīng)一個(gè)任意的數(shù)據(jù)值。對(duì)NoSQL 系統(tǒng)來(lái)說(shuō)，這個(gè)任意的數(shù)據(jù)值是什么，它并不關(guān)心。比如在員工信念數(shù)據(jù)庫(kù)里，exployee:30 這個(gè)key對(duì)應(yīng)的可能就是一段包含員工所有信息的二進(jìn)制數(shù)據(jù)。這個(gè)二進(jìn)制的格式可能是Protocol Buffer、Thrift或者Avro都無(wú)所謂。 如果你使用上面說(shuō)的Key-Value存儲(chǔ)來(lái)保存你的結(jié)構(gòu)化數(shù)據(jù)，那么你就得在應(yīng)用層來(lái)處理具體的數(shù)據(jù)結(jié)構(gòu)：?jiǎn)渭兊腒ey-Value存儲(chǔ)是不提供針對(duì)數(shù)據(jù)中特定的某個(gè)屬性值來(lái)進(jìn)行操作。通常它只提供像set、get和delete這樣的操作。以Dynamo為原型的Voldemort數(shù)據(jù)庫(kù)，就只提供了分布式的Key-Value存儲(chǔ)功能。BDB 是一個(gè)提供Key-Value操作的持久化數(shù)據(jù)存儲(chǔ)引擎。

Key - 結(jié)構(gòu)化數(shù)據(jù) 存儲(chǔ)

Key - 結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)，其典型代表是Redis，Redis將Key-Value存儲(chǔ)的Value變成了結(jié)構(gòu)化的數(shù)據(jù)類型。Value的類型包括數(shù)字、字符串、列表、集合以及有序集合。除了set/get/delete 操作以為，Redis還提供了很多針對(duì)以上數(shù)據(jù)類型的特殊操作，比如針對(duì)數(shù)字可以執(zhí)行增、減操作，對(duì)list可以執(zhí)行 push/pop 操作，而這些對(duì)特定數(shù)據(jù)類型的特定操作并沒(méi)有對(duì)性能造成多大的影響。通過(guò)提供這種針對(duì)單個(gè)Value進(jìn)行的特定類型的操作，Redis可以說(shuō)實(shí)現(xiàn)了功能與性能的平衡。

Key - 文檔 存儲(chǔ)

Key - 文檔存儲(chǔ)的代表有CouchDB、MongoDB和Riak。這種存儲(chǔ)方式下Key-Value的Value是結(jié)構(gòu)化的文檔，通常這些文檔是被轉(zhuǎn)換成JSON或者類似于JSON的結(jié)構(gòu)進(jìn)行存儲(chǔ)。文檔可以存儲(chǔ)列表，鍵值對(duì)以及層次結(jié)構(gòu)復(fù)雜的文檔。 MongoDB 將Key按業(yè)務(wù)分到各個(gè)collection里，這樣以collection作為命名空間，員工信息和部門信息的Key就被隔開(kāi)了。CouchDB和Riak把類型跟蹤這種事留給了開(kāi)發(fā)者去完成。文檔型存儲(chǔ)的靈活性和復(fù)雜性是一把雙刃劍：一方面，開(kāi)發(fā)者可以任意組織文檔的結(jié)構(gòu)，另一方面，應(yīng)用層的查詢需求會(huì)變得比較復(fù)雜。

BigTable 的列簇式存儲(chǔ)

HBase和Cassandra的數(shù)據(jù)模型都借鑒自Google 的BigTable。這種數(shù)據(jù)模型的特點(diǎn)是列式存儲(chǔ)，每一行數(shù)據(jù)的各項(xiàng)被存儲(chǔ)在不同的列中（這些列的集合稱作列簇）。而每一列中每一個(gè)數(shù)據(jù)都包含一個(gè)時(shí)間戳屬性，這樣列中的同一個(gè)數(shù)據(jù)項(xiàng)的多個(gè)版本都能保存下來(lái)。 列式存儲(chǔ)可以理解成這樣，將行ID、列簇號(hào)，列號(hào)以及時(shí)間戳一起，組成一個(gè)Key，然后將Value按Key的順序進(jìn)行存儲(chǔ)。Key值的結(jié)構(gòu)化使這種數(shù)據(jù)結(jié)構(gòu)能夠?qū)崿F(xiàn)一些特別的功能。最常用的就是將一個(gè)數(shù)據(jù)的多個(gè)版本存成時(shí)間戳不同的幾個(gè)值，這樣就能很方便的保存歷史數(shù)據(jù)。這種結(jié)構(gòu)也能天然地進(jìn)行高效的松散列數(shù)據(jù)（在很多行中并沒(méi)有某列的數(shù)據(jù)）存儲(chǔ)。當(dāng)然，另一方面，對(duì)于那些很少有某一行有NULL值的列，由于每一個(gè)數(shù)據(jù)必須包含列標(biāo)識(shí)，這又會(huì)造成空間的浪費(fèi)。 這些NoSQL系統(tǒng)對(duì)BigTable數(shù)據(jù)模型的實(shí)現(xiàn)多少有些差別，這其中以Cassandra進(jìn)行的變更最為顯著。Cassandra引入了超級(jí)列（supercolumn）的概念，通過(guò)將列組織到相應(yīng)的超級(jí)列中，可以在更高層級(jí)上進(jìn)行數(shù)據(jù)的組織，索引等。這一做法也取代了locality groups的概念（這一概念的實(shí)現(xiàn)可以讓相關(guān)的幾個(gè)行的數(shù)據(jù)存儲(chǔ)在一起，以提高存取性能）。

13.2.2 圖結(jié)構(gòu)存儲(chǔ)

圖結(jié)構(gòu)存儲(chǔ)是NoSQL的另一種存儲(chǔ)實(shí)現(xiàn)。圖結(jié)構(gòu)存儲(chǔ)的一個(gè)指導(dǎo)思想是：數(shù)據(jù)并非對(duì)等的，關(guān)系型的存儲(chǔ)或者鍵值對(duì)的存儲(chǔ)，可能都不是最好的存儲(chǔ)方式。圖結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的基礎(chǔ)結(jié)構(gòu)之一，Neo4j和HyperGraphDB是當(dāng)前最流行的圖結(jié)構(gòu)數(shù)據(jù)庫(kù)。圖結(jié)構(gòu)的存儲(chǔ)與我們之前討論過(guò)的幾種存儲(chǔ)方式很不同，這種不同幾乎體現(xiàn)在每一個(gè)方面，包括：數(shù)據(jù)模型、數(shù)據(jù)查詢方式、數(shù)據(jù)在磁盤上的組織方式、在多個(gè)結(jié)點(diǎn)上的分布方式，甚至包括對(duì)事務(wù)機(jī)制的實(shí)現(xiàn)等等。由于篇幅的限制，對(duì)這些方面我們暫時(shí)不做深入的討論，這里需要你了解的是，某些數(shù)據(jù)結(jié)構(gòu)使用圖結(jié)構(gòu)的數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)可能會(huì)更好。

13.2.3 復(fù)雜查詢

在NoSQL存儲(chǔ)系統(tǒng)中，有很多比鍵值查找更復(fù)雜的操作。比如MongoDB可以在任意數(shù)據(jù)行上建立索引，可以使用Javascript語(yǔ)法設(shè)定復(fù)雜的查詢條件。BigTable型的系統(tǒng)通常支持對(duì)單獨(dú)某一行的數(shù)據(jù)進(jìn)行遍歷，允許對(duì)單列的數(shù)據(jù)進(jìn)行按特定條件地篩選。CouchDB允許你創(chuàng)建同一份數(shù)據(jù)的多個(gè)視圖，通過(guò)運(yùn)行MapReduce任務(wù)來(lái)實(shí)現(xiàn)一些更為復(fù)雜的查詢或者更新操作。很多NoSQL系統(tǒng)都支持與Hadoop或者其它一些MapReduce框架結(jié)合來(lái)進(jìn)行一些大規(guī)模數(shù)據(jù)分析工作。

13.2.4 事務(wù)機(jī)制

傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)在功能支持上通常很寬泛，從簡(jiǎn)單的鍵值查詢，到復(fù)雜的多表聯(lián)合查詢?cè)俚绞聞?wù)機(jī)制的支持。而與之不同的是，NoSQL系統(tǒng)通常注重性能和擴(kuò)展性，而非事務(wù)機(jī)制。 傳統(tǒng)的SQL數(shù)據(jù)庫(kù)的事務(wù)通常都是支持ACID的強(qiáng)事務(wù)機(jī)制。A代表原子性，即在事務(wù)中執(zhí)行多個(gè)操作是原子性的，要么事務(wù)中的操作全部執(zhí)行，要么一個(gè)都不執(zhí)行;C代表一致性，即保證進(jìn)行事務(wù)的過(guò)程中整個(gè)數(shù)據(jù)加的狀態(tài)是一致的，不會(huì)出現(xiàn)數(shù)據(jù)花掉的情況;I代表隔離性，即兩個(gè)事務(wù)不會(huì)相互影響，覆蓋彼此數(shù)據(jù)等;D表示持久化，即事務(wù)一量完成，那么數(shù)據(jù)應(yīng)該是被寫到安全的，持久化存儲(chǔ)的設(shè)備上（比如磁盤）。 ACID的支持使得應(yīng)用者能夠很清楚他們當(dāng)前的數(shù)據(jù)狀態(tài)。即使如對(duì)于多個(gè)事務(wù)同時(shí)執(zhí)行的情況下也能夠保證數(shù)據(jù)狀態(tài)的正常性。但是如果要保證數(shù)據(jù)的一致性，通常多個(gè)事務(wù)是不可能交叉執(zhí)行的，這樣就導(dǎo)致了可能一個(gè)很簡(jiǎn)單的操作需要等等一個(gè)復(fù)雜操作完成才能進(jìn)行的情況。 對(duì)很多NoSQL系統(tǒng)來(lái)說(shuō)，對(duì)性能的考慮遠(yuǎn)在ACID的保證之上。通常NoSQL系統(tǒng)僅提供行級(jí)別的原子性保證，也就是說(shuō)同時(shí)對(duì)同一個(gè)Key下的數(shù)據(jù)進(jìn)行的兩個(gè)操作，在實(shí)際執(zhí)行的時(shí)候是會(huì)串行的執(zhí)行，保證了每一個(gè)Key-Value對(duì)不會(huì)被破壞。對(duì)絕大多數(shù)應(yīng)用場(chǎng)景來(lái)說(shuō)，這樣的保證并不會(huì)引起多大的問(wèn)題，但其換來(lái)的執(zhí)行效率卻是非?？捎^的。當(dāng)然，使用這樣的系統(tǒng)可能需要我們?cè)趹?yīng)用層的設(shè)計(jì)上多做容錯(cuò)性和修正機(jī)制的考慮。 在NoSQL中，Redis在事務(wù)支持這方面上不太一樣，它提供了一個(gè)MULTI命令用來(lái)將多個(gè)命令進(jìn)行組合式的操作，通過(guò)一個(gè)WATCH命令提供操作隔離性。這和其它一些提供test-and-set這樣的低層級(jí)的隔離機(jī)制類似。

13.2.5 Schema-free的存儲(chǔ)

還有一個(gè)很多NoSQL都有的共同點(diǎn)，就是它通常并沒(méi)有強(qiáng)制的數(shù)據(jù)結(jié)構(gòu)約束。即使是在文檔型存儲(chǔ)或者列式存儲(chǔ)上，也不會(huì)要求某一個(gè)數(shù)據(jù)列在每一行數(shù)據(jù)上都必須存在。這在非結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)上更方便，同時(shí)也省去了修改表結(jié)構(gòu)的代價(jià)。而這一機(jī)制對(duì)應(yīng)用層的容錯(cuò)性要求可能會(huì)更高。比如程序可能得確定如果某一個(gè)員工的信息里缺少lastname這一項(xiàng)，是否算是錯(cuò)誤?；蛘哒f(shuō)某個(gè)表結(jié)構(gòu)的變更是否對(duì)所有數(shù)據(jù)行起了作用。還有一個(gè)問(wèn)題，就是數(shù)據(jù)庫(kù)的表結(jié)構(gòu)可能會(huì)因?yàn)轫?xiàng)目的多次迭代而變得混亂不堪。

13.3 數(shù)據(jù)可靠性

最理想狀態(tài)是，數(shù)據(jù)庫(kù)會(huì)把所有寫操作立刻寫到持久化存儲(chǔ)的設(shè)備，同時(shí)復(fù)制多個(gè)副本到不同地理位置的不同節(jié)點(diǎn)上，以防止數(shù)據(jù)丟失。但是這種對(duì)數(shù)據(jù)安全性的要求對(duì)性能是有影響的，所以不同的NoSQL系統(tǒng)在自身性能的考慮下，在數(shù)據(jù)安全上采取了不太一樣的策略。 一種典型的出錯(cuò)情況是重啟機(jī)器或者機(jī)器斷電了，這時(shí)候需要讓數(shù)據(jù)從內(nèi)存轉(zhuǎn)存到磁盤才能保證數(shù)據(jù)的安全性，因?yàn)榇疟P數(shù)據(jù)不會(huì)因斷電而丟失。而要避免磁盤損壞這種故障，就需要將數(shù)據(jù)冗余的存在其它磁盤上，比如使用RAID來(lái)做鏡像，或者將數(shù)據(jù)同步到不同機(jī)器。但是有些時(shí)候針對(duì)同一個(gè)數(shù)據(jù)中心來(lái)說(shuō)，是不可能做到完全的數(shù)據(jù)安全的，比如一旦發(fā)生颶風(fēng)地震這種天災(zāi)，整個(gè)機(jī)房機(jī)器可能都會(huì)損壞，所以，在這種情況下要保證數(shù)據(jù)的安全性，就必須將數(shù)據(jù)備份存儲(chǔ)到其它地理位置上比較遠(yuǎn)的數(shù)據(jù)中心。所以，具體各個(gè)NoSQL系統(tǒng)在數(shù)據(jù)安全性和性能上的權(quán)衡策略也不太一樣。

13.3.1 單機(jī)可靠性

單機(jī)可靠性理解起來(lái)非常簡(jiǎn)單，它的定義是寫操作不會(huì)由于機(jī)器重啟或者斷電而丟失。通常單機(jī)可靠性的保證是通過(guò)把數(shù)據(jù)寫到磁盤來(lái)完成的，而這通常會(huì)造成磁盤IO成為整個(gè)系統(tǒng)的瓶頸。而事實(shí)上，即使你的程序每次都把數(shù)據(jù)寫到了磁盤，實(shí)際上由于操作系統(tǒng)buffer層的存在，數(shù)據(jù)還是不會(huì)立刻被寫到物理磁盤上，只有當(dāng)你調(diào)用fsync這個(gè)系統(tǒng)調(diào)用的時(shí)候，操作系統(tǒng)才會(huì)盡可能的把數(shù)據(jù)寫到磁盤。 一般的磁盤大概能進(jìn)行每秒100-200次的隨機(jī)訪問(wèn)，每秒30-100MB的順序?qū)懭胨俣?。而?nèi)存在這兩方面的性能都有數(shù)量級(jí)上的提升。通過(guò)盡量減少隨機(jī)寫，取而代之的對(duì)每個(gè)磁盤設(shè)備進(jìn)行順序?qū)?，這樣能夠減少單機(jī)可靠性保證的代價(jià)。也就是說(shuō)我們需要減少在兩次fsync調(diào)用之間的寫操作次數(shù)，而增加順序?qū)懖僮鞯臄?shù)量。下面我們說(shuō)一下一些在單機(jī)可靠性的保證下提高性能的方法。

控制fsync的調(diào)用頻率

Memcached是一個(gè)純內(nèi)存的存儲(chǔ)，由于其不進(jìn)行磁盤上的持久化存儲(chǔ)，從而換來(lái)了很高的性能。當(dāng)然，在我們進(jìn)行服務(wù)器重啟或者服務(wù)器意外斷電后，這些數(shù)據(jù)就全丟了。因此Memcached 是一個(gè)非常不錯(cuò)的緩存，但是做不了持久化存儲(chǔ)。 Redis則提供了幾種對(duì)fsync調(diào)用頻率的控制方法。應(yīng)用開(kāi)發(fā)者可以配置Redis在每次更新操作后都執(zhí)行一次fsync，這樣會(huì)比較安全，當(dāng)然也就比較慢。Redis也可以設(shè)置成N秒種調(diào)用一次fsync，這樣性能會(huì)更好一點(diǎn)。但這樣的后果就是一旦出現(xiàn)故障，最多可能導(dǎo)致N秒內(nèi)的數(shù)據(jù)丟失。而對(duì)一些可靠性要求不太高的場(chǎng)合（比如僅僅把Redis當(dāng)Cache用的時(shí)候），應(yīng)用開(kāi)發(fā)者甚至可以直接關(guān)掉fsync的調(diào)用：讓操作系統(tǒng)來(lái)決定什么時(shí)候需要把數(shù)據(jù)flush到磁盤。 （譯者：這只是Redis append only file的機(jī)制，Redis是可以關(guān)閉aof日志的，另外請(qǐng)注意：Redis 本身支持將內(nèi)存中數(shù)據(jù)dump成rdb文件的機(jī)制，和上面說(shuō)的不是一回事。） 使用日志型的數(shù)據(jù)結(jié)構(gòu)

像B+ 樹(shù)這樣的一些數(shù)據(jù)結(jié)構(gòu)，使得NoSQL系統(tǒng)能夠快速的定位到磁盤上的數(shù)據(jù)，但是通常這些數(shù)據(jù)結(jié)構(gòu)的更新操作是隨機(jī)寫操作，如果你在每次操作后再調(diào)用一次fsync，那就會(huì)造成頻繁的磁盤隨機(jī)訪問(wèn)了。為了避免產(chǎn)生這樣的問(wèn)題，像Cassandra、HBase、Redis和Riak都會(huì)把寫操作順序的寫入到一個(gè)日志文件中。相對(duì)于存儲(chǔ)系統(tǒng)中的其它數(shù)據(jù)結(jié)構(gòu)，上面說(shuō)到的日志文件可以頻繁的進(jìn)行fsync操作。這個(gè)日志文件記錄了操作行為，可以用于在出現(xiàn)故障后恢復(fù)丟失那段時(shí)間的數(shù)據(jù)，這樣就把隨機(jī)寫變成順序?qū)懥恕?雖然有的NoSQL系統(tǒng)，比如MongoDB，是直接在原數(shù)據(jù)上進(jìn)行更新操作的，但也有許多NoSQL系統(tǒng)是采用了上面說(shuō)到的日志策略。Cassandra和HBase借鑒了BigTable的做法，在數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)了一個(gè)日志型的查找樹(shù)。Riak也使用了類似的方法實(shí)現(xiàn)了一個(gè)日志型的hash表（譯者：也就是Riak的BitCask模型）。CouchDB對(duì)傳統(tǒng)的B+樹(shù)結(jié)構(gòu)進(jìn)行了修改，使得對(duì)樹(shù)的更新可以使用順序的追加寫操作來(lái)實(shí)現(xiàn)（譯者：這種B+樹(shù)被稱作append-only B-Tree）。這些方法的使用，使得存儲(chǔ)系統(tǒng)的寫操作承載力更高，但同時(shí)為了防止數(shù)據(jù)異構(gòu)后膨脹得過(guò)大，需要定時(shí)進(jìn)行一些合并操作。

通過(guò)合并寫操作提高吞吐性能

Cassandra有一個(gè)機(jī)制，它會(huì)把一小段時(shí)間內(nèi)的幾個(gè)并發(fā)的寫操作放在一起進(jìn)行一次fsync調(diào)用。這種做法叫g(shù)roup commit，它導(dǎo)致的一個(gè)結(jié)果就是更新操作的返回時(shí)間可能會(huì)變長(zhǎng)，因?yàn)橐粋€(gè)更新操作需要等就近的幾個(gè)更新操作一起進(jìn)行提交。這樣做的好處是能夠提高寫操作承載力。作為HBase底層數(shù)據(jù)支持的Hadoop 分布式文件系統(tǒng)HDFS，它最近的一些補(bǔ)丁也在實(shí)現(xiàn)一些順序?qū)懞蚲roup commit的機(jī)制。

13.3.2 多機(jī)可靠性

由于硬件層面有時(shí)候會(huì)造成無(wú)法恢復(fù)的損壞，單機(jī)可靠性的保證在這方面就鞭長(zhǎng)莫及了。對(duì)于一些重要數(shù)據(jù)，跨機(jī)器做備份保存是必備的安全措施。一些NoSQL系統(tǒng)提供了多機(jī)可靠性的支持。 Redis采用了傳統(tǒng)的主從數(shù)據(jù)同步的方式。所有在master上執(zhí)行的操作，都會(huì)通過(guò)類似于操作日志的結(jié)構(gòu)順序地傳遞給slave上再執(zhí)行一遍。如果master發(fā)生宕機(jī)等事故，slave可以繼續(xù)執(zhí)行完master傳來(lái)的操作日志并且成為新的master?？赡苓@中間會(huì)導(dǎo)致一些數(shù)據(jù)丟失，因?yàn)閙aster同步操作到slave是非阻塞的，master并不知道操作是否已經(jīng)同步線slave了。CouchDB 實(shí)現(xiàn)了一個(gè)類似的指向性的同步功能，它使得一個(gè)寫操作可以同步到其它節(jié)點(diǎn)上。 MongoDB提供了一個(gè)叫Replica Sets的架構(gòu)方制，這個(gè)架構(gòu)策略使得每一個(gè)文檔都會(huì)保存在組成Replica Sets的所有機(jī)器上。MongoDB提供了一些選項(xiàng)，讓開(kāi)發(fā)者可以確定一個(gè)寫操作是否已經(jīng)同步到了所有節(jié)點(diǎn)上，也可以在節(jié)點(diǎn)數(shù)據(jù)并不是最新的情況下執(zhí)行一些操作。很多其它的分布式NoSQL存儲(chǔ)都提供了類似的多機(jī)可靠性支持。由于HBase的底層存儲(chǔ)是HDFS，它也就自然的獲得了HDFS提供的多機(jī)可靠性保證。HDFS的多機(jī)可靠性保證是通過(guò)把每個(gè)寫操作都同步到兩個(gè)以上的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的。 Riak、Cassandra和Voldemort提供了一些更靈活的可配置策略。這三個(gè)系統(tǒng)提供一個(gè)可配置的參數(shù)N，代表每一個(gè)數(shù)據(jù)會(huì)被備份的份數(shù)，然后還可以配置一個(gè)參數(shù)W，代表每個(gè)寫操作需要同步到多少能機(jī)器上才返回成功。當(dāng)然W是小于N的。 為了應(yīng)對(duì)整個(gè)數(shù)據(jù)中心出現(xiàn)故障的情況，需要實(shí)現(xiàn)跨數(shù)據(jù)中心的多機(jī)備份功能。Cassandra、HBase和Voldemort都實(shí)現(xiàn)了一個(gè)機(jī)架位置可知的配置，這種配置方式使得整個(gè)分布式系統(tǒng)可以了解各個(gè)節(jié)點(diǎn)的地理位置分布情況。如果一個(gè)操作需要等待另外的數(shù)據(jù)中心的同步操作成功才返回給用戶，那時(shí)間就太長(zhǎng)了，所以通?？鐢?shù)據(jù)中心的同步備份操作都是異步進(jìn)行的。用戶并不需要等待另一個(gè)數(shù)據(jù)中心同步的同步操作執(zhí)行成功。

13.4 橫向擴(kuò)展帶來(lái)性能提升

上面我們討論了對(duì)出錯(cuò)情況的處理，下面我們討論另一種情況：成功！如果數(shù)據(jù)存儲(chǔ)操作成功執(zhí)行了，那么你的系統(tǒng)就要負(fù)責(zé)對(duì)這些數(shù)據(jù)進(jìn)行處理。就要承擔(dān)數(shù)據(jù)帶來(lái)的負(fù)載。一個(gè)比較粗暴的解決方法是通過(guò)升級(jí)你的機(jī)器來(lái)提升單機(jī)性能：通過(guò)加大內(nèi)存和添加硬盤來(lái)應(yīng)對(duì)越來(lái)越大的負(fù)載。但是隨著數(shù)據(jù)量的增大，投入在升級(jí)機(jī)器上的錢將將不會(huì)產(chǎn)生原來(lái)那么大的效果。這時(shí)候你就必須考慮把數(shù)據(jù)同步到不同的機(jī)器上，利用橫向擴(kuò)展來(lái)分擔(dān)訪問(wèn)壓力。 橫向擴(kuò)展的目標(biāo)是達(dá)到線性的效果，即如果你增加一倍的機(jī)器，那么負(fù)載能力應(yīng)該也能相應(yīng)的增加一倍。其主要需要解決的問(wèn)題是如何讓數(shù)據(jù)在多臺(tái)機(jī)器間分布。數(shù)據(jù)分片技術(shù)實(shí)際上就是將對(duì)數(shù)據(jù)和讀寫請(qǐng)求在多個(gè)機(jī)器節(jié)點(diǎn)上進(jìn)行分配的技術(shù)，分片技術(shù)在很多NoSQL系統(tǒng)中都有實(shí)現(xiàn)，比如Cassandra、HBase、Voldemort和Riak等等，最近MongoDB和Redis也在做相應(yīng)的實(shí)現(xiàn)。而有的項(xiàng)目并不提供內(nèi)置的分片支持，比如CouchDB更加注重單機(jī)性能的提升。對(duì)于這些項(xiàng)目，通常我們可以借助一些其它的技術(shù)在上層來(lái)進(jìn)行負(fù)載分配。 下面讓我們來(lái)整理一些通用的概念。對(duì)于數(shù)據(jù)分片和分區(qū)，我們可以做同樣的理解。對(duì)機(jī)器，服務(wù)器或者節(jié)點(diǎn)，我們可以統(tǒng)一的理解成物理上的存儲(chǔ)數(shù)據(jù)的機(jī)器。最后，集群或者機(jī)器環(huán)都可以理解成為是組成你存儲(chǔ)系統(tǒng)的集合。 分片的意思是，沒(méi)有任何一臺(tái)機(jī)器可以處理所有寫請(qǐng)求，也沒(méi)有任何一臺(tái)機(jī)器可以處理對(duì)所有數(shù)據(jù)的讀請(qǐng)求。很多NoSQL系統(tǒng)都是基于鍵值模型的，因此其查詢條件也基本上是基于鍵值的查詢，基本不會(huì)有對(duì)整個(gè)數(shù)據(jù)進(jìn)行查詢的時(shí)候。由于基本上所有的查詢操作都是基本鍵值形式的，因此分片通常也基于數(shù)據(jù)的鍵來(lái)做：鍵的一些屬性會(huì)決定這個(gè)鍵值對(duì)存儲(chǔ)在哪臺(tái)機(jī)器上。下面我們將會(huì)對(duì)hash分片和范圍分片兩種分片方式進(jìn)行描述。

13.4.1 如非必要，請(qǐng)勿分片

分片會(huì)導(dǎo)致系統(tǒng)復(fù)雜程序大增，所以，如果沒(méi)有必要，請(qǐng)不要使用分片。下面我們先講兩種不用分片就能讓系統(tǒng)具有擴(kuò)展性的方法。 讀寫分離

大多數(shù)應(yīng)用場(chǎng)景都是讀多寫少的場(chǎng)景。所以在這種情況下，可以用一個(gè)簡(jiǎn)單的方法來(lái)分擔(dān)負(fù)載，就是把數(shù)據(jù)同步到多臺(tái)機(jī)器上。這時(shí)候?qū)懻?qǐng)求還是由master機(jī)器處理，而讀請(qǐng)求則可以分擔(dān)給那些同步到數(shù)據(jù)的機(jī)器了。而同步數(shù)據(jù)的操作，通常是不會(huì)對(duì)master帶來(lái)多大的壓力的。 如果你已經(jīng)使用了主從配置，將數(shù)據(jù)同步到多臺(tái)機(jī)器以提供高可靠性了，那么你的slave機(jī)器應(yīng)該能夠?yàn)閙aster分擔(dān)不少壓力了。對(duì)有些實(shí)時(shí)性要求不是非常高的查詢請(qǐng)求，比如一些統(tǒng)計(jì)操作，你完全可以放到slave上來(lái)執(zhí)行。通常來(lái)說(shuō)，你的應(yīng)用對(duì)實(shí)時(shí)性要求越低，你的slave機(jī)器就能承擔(dān)越多的任務(wù)。 使用緩存

將一些經(jīng)常訪問(wèn)的數(shù)據(jù)放到緩存層中，通常會(huì)帶來(lái)很好的效果。Memcached 主要的作用就是將數(shù)據(jù)層的數(shù)據(jù)進(jìn)行分布式的緩存。Memcached 通過(guò)客戶端的算法（譯者： 常見(jiàn)的一致性hash算法）來(lái)實(shí)現(xiàn)橫向擴(kuò)展，這樣當(dāng)你想增大你緩存池的大小時(shí)，只需要添加一臺(tái)新的緩存機(jī)器即可。 由于Memcached僅僅是一個(gè)緩存存儲(chǔ)，它并不具備一些持久存儲(chǔ)的復(fù)雜特性。當(dāng)你在考慮使用復(fù)雜的擴(kuò)展方案時(shí)，希望你先考慮一下使用緩存來(lái)解決你的負(fù)載問(wèn)題。注意，緩存并不是臨時(shí)的處理方案：Facebook 就部署了總?cè)萘窟_(dá)到幾十TB的Memcahced內(nèi)存池。 通過(guò)讀寫分離和構(gòu)建有效的緩存層，通?？梢源蟠蠓謸?dān)系統(tǒng)的讀負(fù)載，但是當(dāng)你的寫請(qǐng)求越來(lái)越頻繁的時(shí)候，你的master機(jī)器還是會(huì)承受越來(lái)越大的壓力。對(duì)于這種情況，我們可能就要用到下面說(shuō)到的數(shù)據(jù)分片技術(shù)了。

13.4.2 通過(guò)協(xié)調(diào)器進(jìn)行數(shù)據(jù)分片

由于CouchDB專注于單機(jī)性能，沒(méi)有提供類似的橫向擴(kuò)展方案，于是出現(xiàn)了兩個(gè)項(xiàng)目：Lounge 和 BigCouch，他們通過(guò)提供一個(gè)proxy層來(lái)對(duì)CouchDB中的數(shù)據(jù)進(jìn)行分片。在這種架構(gòu)中，proxy作為CouchDB集群的前端機(jī)器，接受和分配請(qǐng)求到后端的多臺(tái)CouchDB上。后端的CouchDB 之間并沒(méi)有交互。協(xié)調(diào)器會(huì)將按操作的key值將請(qǐng)求分配到下層的具體某臺(tái)機(jī)器。 Twitter 自己實(shí)現(xiàn)了一個(gè)叫Gizzard的協(xié)調(diào)器，可以實(shí)現(xiàn)數(shù)據(jù)分片和備份功能。Gizzard不關(guān)心數(shù)據(jù)類型，它使用樹(shù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)范圍標(biāo)識(shí)，你可以用它來(lái)對(duì)SQL或者NoSQL系統(tǒng)進(jìn)行封裝。通過(guò)對(duì) Gizzard 進(jìn)行配置，可以實(shí)現(xiàn)將特定范圍內(nèi)的數(shù)據(jù)進(jìn)行冗余存儲(chǔ)，以提高系統(tǒng)的容災(zāi)能力。

13.4.3 一致性hash環(huán)算法

好的hash算法可以使數(shù)據(jù)保持比較均勻的分布。這使得我們可以按這種分布將數(shù)據(jù)保存布多臺(tái)機(jī)器上。一致性hash是一種被廣泛應(yīng)用的技術(shù)，其最早在一個(gè)叫distributed hash tables (DHTs)的系統(tǒng)中進(jìn)行使用。那些類Dynamo的應(yīng)用，比如Cassandra、Voldemort和Riak，基本上都使用了一致性hash算法。

Hash環(huán)圖

一致性hash算法的工作原理如下：首先我們有一個(gè)hash函數(shù)H，可以通過(guò)數(shù)據(jù)的key值計(jì)算出一個(gè)數(shù)字型的hash值。然后我們將整個(gè)hash環(huán)的范圍定義為［1，L］這個(gè)區(qū)間，我們將剛才算出的hash值對(duì)L進(jìn)行取余，就能算出一個(gè)key值在這個(gè)環(huán)上的位置。而每一臺(tái)真實(shí)服務(wù)器結(jié)點(diǎn)就會(huì)負(fù)責(zé)［1-L］之間的某個(gè)區(qū)間的數(shù)據(jù)。如上圖，就是一個(gè)五個(gè)結(jié)點(diǎn)的hash環(huán)。 上面hash環(huán)的L值為1000，然后我們對(duì)ABCDE 5個(gè)點(diǎn)分別進(jìn)行hash運(yùn)算，H(A) mod L = 7, H(B) mod L = 234, H(C) mod L = 447, H(D) mod L = 660, and H(E) mod L = 875 ，這樣，hash值在7-233之間的所有數(shù)據(jù)，我們都讓它保存在A節(jié)點(diǎn)上。在實(shí)際動(dòng)作中，我們對(duì)數(shù)據(jù)進(jìn)行hash，算出其應(yīng)該在哪個(gè)節(jié)點(diǎn)存儲(chǔ)即可，例：H('employee30') mod L = 899 那么它應(yīng)該在E節(jié)點(diǎn)上，H('employee31') mod L = 234 那么這個(gè)數(shù)據(jù)應(yīng)該在B節(jié)點(diǎn)上。

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

一致性hash下的數(shù)據(jù)備份通常采用下面的方法：將數(shù)據(jù)冗余的存在其歸屬的節(jié)點(diǎn)的順序往下的節(jié)點(diǎn)，例如你的冗余系數(shù)為3（即數(shù)據(jù)會(huì)在不同節(jié)點(diǎn)中保存三份），那么如果通過(guò)hash計(jì)算你的數(shù)據(jù)在A區(qū)間［7，233］，你的數(shù)據(jù)會(huì)被同時(shí)保存在A，B，C三個(gè)節(jié)點(diǎn)上。這樣如果A節(jié)點(diǎn)出現(xiàn)故障，那么B，C節(jié)點(diǎn)就能處理這部分?jǐn)?shù)據(jù)的請(qǐng)求了。而某些設(shè)計(jì)會(huì)使E節(jié)點(diǎn)將自己的范圍擴(kuò)大到A233，以接受對(duì)出故障的A節(jié)點(diǎn)的請(qǐng)求。

優(yōu)化的數(shù)據(jù)分配策略

雖然hash算法能夠產(chǎn)生相對(duì)均勻的hash值。而且通常是節(jié)點(diǎn)數(shù)量越多，hash算法會(huì)越平均的分配key值。然而通常在項(xiàng)目初期不會(huì)有太多的數(shù)據(jù)，當(dāng)然也不需要那么多的機(jī)器節(jié)點(diǎn)，這時(shí)候就會(huì)造成數(shù)據(jù)分配不平均的問(wèn)題。比如上面的5個(gè)節(jié)點(diǎn)，其中A節(jié)點(diǎn)需要負(fù)責(zé)的hash區(qū)間范圍大小為227，而E節(jié)點(diǎn)負(fù)責(zé)的區(qū)間范圍為132。同時(shí)在這種情況下，出故障后數(shù)據(jù)請(qǐng)求轉(zhuǎn)移到相鄰節(jié)點(diǎn)的策略也可能不好實(shí)施了。 為了解決由于節(jié)點(diǎn)比較少導(dǎo)致數(shù)據(jù)分配不均的問(wèn)題，很多DHT系統(tǒng)都實(shí)現(xiàn)了一種叫做虛擬節(jié)點(diǎn)的技術(shù)。例如4個(gè)虛擬節(jié)點(diǎn)的系統(tǒng)中，A節(jié)點(diǎn)可能被虛擬化成A_1，A_2，A_3，A_4這四個(gè)虛擬節(jié)點(diǎn)，然后對(duì)這四個(gè)虛擬節(jié)點(diǎn)再進(jìn)行hash運(yùn)算，A節(jié)點(diǎn)負(fù)責(zé)的key值區(qū)間就比較分散了。Voldemort 使用了與上面類似的策略，它允許對(duì)虛擬節(jié)點(diǎn)數(shù)進(jìn)行配置，通常這個(gè)節(jié)點(diǎn)數(shù)會(huì)大于真實(shí)節(jié)點(diǎn)數(shù)，這樣每個(gè)真實(shí)節(jié)點(diǎn)實(shí)際上是負(fù)責(zé)了N個(gè)虛擬節(jié)點(diǎn)上的數(shù)據(jù)。 Cassandra 并沒(méi)有使用虛擬節(jié)點(diǎn)到真實(shí)節(jié)點(diǎn)映射的方法。這導(dǎo)致它的數(shù)據(jù)分配是不均勻的。為了解決這種不平衡，Cassandra 利用一個(gè)異步的進(jìn)程根據(jù)各節(jié)點(diǎn)的歷史負(fù)載情況來(lái)調(diào)節(jié)數(shù)據(jù)的分布。

13.4.4 連續(xù)范圍分區(qū)

使用連續(xù)范圍分區(qū)的方法進(jìn)行數(shù)據(jù)分片，需要我們保存一份映射關(guān)系表，標(biāo)明哪一段key值對(duì)應(yīng)存在哪臺(tái)機(jī)器上。和一致性hash類似，連續(xù)范圍分區(qū)會(huì)把key值按連續(xù)的范圍分段，每段數(shù)據(jù)會(huì)被指定保存在某個(gè)節(jié)點(diǎn)上，然后會(huì)被冗余備份到其它的節(jié)點(diǎn)。和一致性hash不同的是，連續(xù)范圍分區(qū)使得key值上相鄰的兩個(gè)數(shù)據(jù)在存儲(chǔ)上也基本上是在同一個(gè)數(shù)據(jù)段。這樣數(shù)據(jù)路由表只需記錄某段數(shù)據(jù)的開(kāi)始和結(jié)束點(diǎn)［start，end］就可以了。 通過(guò)動(dòng)態(tài)調(diào)整數(shù)據(jù)段到機(jī)器結(jié)點(diǎn)的映射關(guān)系，可以更精確的平衡各節(jié)點(diǎn)機(jī)器負(fù)載。如果某個(gè)區(qū)段的數(shù)據(jù)負(fù)載比較大，那么負(fù)載控制器就可以通過(guò)縮短其所在節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)段，或者直接減少其負(fù)責(zé)的數(shù)據(jù)分片數(shù)目。通過(guò)添加這樣一個(gè)監(jiān)控和路由模塊，使我們能夠更好的對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行負(fù)載均衡。

BigTable的處理方式

Google BigTable 論文中描述了一種范圍分區(qū)方式，它將數(shù)據(jù)切分成一個(gè)個(gè)的tablet數(shù)據(jù)塊。每個(gè)tablet保存一定數(shù)量的鍵值對(duì)。然后每個(gè)Tablet 服務(wù)器會(huì)存儲(chǔ)多個(gè)tablet塊，具體每個(gè)Tablet服務(wù)器保存的tablet數(shù)據(jù)塊數(shù)，則是由服務(wù)器壓力來(lái)決定的。 每個(gè)tablet大概100-200MB大。如果tablet的尺寸變小，那么兩個(gè)tablet可能會(huì)合并成一個(gè)tablet，同樣的如果一個(gè)tablet過(guò)大，它也會(huì)被分裂成兩個(gè)tablet，以保持每個(gè)tablet的大小在一定范圍內(nèi)。在整個(gè)系統(tǒng)中有一個(gè)master機(jī)器，會(huì)根據(jù)tablet的大小、負(fù)載情況以及機(jī)器的負(fù)載能力等因素動(dòng)態(tài)地調(diào)整tablet在各個(gè)機(jī)器上的分布。

master服務(wù)器會(huì)把 tablet 的歸屬關(guān)系存在元數(shù)據(jù)表里。當(dāng)數(shù)據(jù)量非常大時(shí)，這個(gè)元數(shù)據(jù)表實(shí)際也會(huì)變得非常大，所以歸屬關(guān)系表實(shí)際上也是被切分成一個(gè)個(gè)的tablet保存在tablet服務(wù)器中的。這樣整個(gè)數(shù)據(jù)存儲(chǔ)就被分成了如上圖的三層模型。 下面我們解釋一下上面圖中的例子。當(dāng)某個(gè)客戶端要從BigTable系統(tǒng)中獲取key值為900的數(shù)據(jù)時(shí)，首先他會(huì)到第一級(jí)元數(shù)據(jù)服務(wù)器A（METADATA0）去查詢，第一級(jí)元數(shù)據(jù)服務(wù)器查詢自己的元數(shù)據(jù)表，500-1500這個(gè)區(qū)間中的所有元數(shù)據(jù)都存在B服務(wù)器中，于是會(huì)返回客戶端說(shuō)去B服務(wù)器查詢，客戶端再到B服務(wù)器中進(jìn)行查詢，B服務(wù)器判斷到850-950這個(gè)區(qū)間中的數(shù)據(jù)都存在tablet服務(wù)器C中，于是會(huì)告知客戶端到具體的tablet服務(wù)器C去查詢。然后客戶端再發(fā)起一次向C服務(wù)器的請(qǐng)求，就能獲取到900對(duì)應(yīng)的數(shù)據(jù)了。然后，客戶端會(huì)把這個(gè)查詢結(jié)果進(jìn)行緩存，以避免對(duì)元數(shù)據(jù)服務(wù)器的頻繁請(qǐng)求。在這樣的三層架構(gòu)下，只需要128MB的元數(shù)據(jù)存儲(chǔ)，就能定位234 個(gè)tablet數(shù)據(jù)塊了（按128MB一個(gè)數(shù)據(jù)塊算，是261bytes的數(shù)據(jù)）。 故障處理

在BigTable中，master機(jī)器是一個(gè)故障單點(diǎn)，不過(guò)系統(tǒng)可以容忍短時(shí)間的master故障。另一方面，如果tablet 服務(wù)器故障，那么master可以把對(duì)其上tablet的所有請(qǐng)求分配到其它機(jī)器節(jié)點(diǎn)。 為了監(jiān)測(cè)和處理節(jié)點(diǎn)故障，BigTable實(shí)現(xiàn)了一個(gè)叫Chubby的模塊，Chubby是一個(gè)分布式的鎖系統(tǒng)，用于管理集群成員及檢測(cè)各成員是否存活。ZooKeeper是Chubby的一個(gè)開(kāi)源實(shí)現(xiàn)，有很多基于 Hadoop 的項(xiàng)目都使用它來(lái)進(jìn)行二級(jí)master和tablet節(jié)點(diǎn)的調(diào)度。

基于范圍分區(qū)的NoSQL項(xiàng)目

HBase 借鑒了BigTable的分層理論來(lái)實(shí)現(xiàn)范圍分區(qū)策略。tablet相關(guān)的數(shù)據(jù)存在HDFS里。HDFS 會(huì)處理數(shù)據(jù)的冗余備份，并負(fù)責(zé)保證各備份的一致性。而像處理數(shù)據(jù)請(qǐng)求，修改存儲(chǔ)結(jié)構(gòu)或者執(zhí)行tablet的分裂和合并這種事，是具體的tablet服務(wù)器來(lái)負(fù)責(zé)的。 MongoDB也用了類似于BigTable的方案來(lái)實(shí)現(xiàn)范圍分區(qū)。他用幾臺(tái)配置機(jī)器組成集群來(lái)管理數(shù)據(jù)在節(jié)點(diǎn)上的分布。這幾臺(tái)機(jī)器保存著一樣的配置信息，他們采用 two-phase commit 協(xié)議來(lái)保證數(shù)據(jù)的一致性。這些配置節(jié)點(diǎn)實(shí)際上同時(shí)扮演了BigTable中的master的路由角色，及Chubby 的高可用性調(diào)度器的角色。而MongoDB具體的數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)是通過(guò)其Replica Sets方案來(lái)實(shí)現(xiàn)數(shù)據(jù)冗余備份的。 Cassandra 提供了一個(gè)有序的分區(qū)表，使你可以快速對(duì)數(shù)據(jù)進(jìn)行范圍查詢。Cassandra也使用了一致性hash算法進(jìn)行數(shù)據(jù)分配，但是不同的是，它不是直接按單條數(shù)據(jù)進(jìn)行hash，而是對(duì)一段范圍內(nèi)的數(shù)據(jù)進(jìn)行hash，也就是說(shuō)20號(hào)數(shù)據(jù)和21號(hào)數(shù)據(jù)基本上會(huì)被分配在同一臺(tái)機(jī)器節(jié)點(diǎn)上。 Twitter的Gizzard框架也是通過(guò)使用范圍分區(qū)來(lái)管理數(shù)據(jù)在多個(gè)節(jié)點(diǎn)間的備份與分配。路由服務(wù)器可以部署成多層，任何一層只負(fù)責(zé)對(duì)key值進(jìn)行按范圍的分配到下層的不同節(jié)點(diǎn)。也就是說(shuō)路由服務(wù)器的下層既可以是真實(shí)的數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，也可能是下層的路由節(jié)點(diǎn)。Gizzard的數(shù)據(jù)備份機(jī)制是通過(guò)將寫操作在多臺(tái)機(jī)器上執(zhí)行多次來(lái)實(shí)現(xiàn)的。Gizzard的路由節(jié)點(diǎn)處理失敗的寫操作的方式和其它NoSQL不太一樣，他要求所有更新都是冪等的（意思是可以重復(fù)執(zhí)行而不會(huì)出錯(cuò)）。于是當(dāng)一個(gè)節(jié)點(diǎn)故障后，其上層的路由節(jié)點(diǎn)會(huì)把當(dāng)前的寫操作cache起來(lái)并且重復(fù)地讓這個(gè)節(jié)點(diǎn)執(zhí)行，直到其恢復(fù)正常。

13.4.5 選擇哪種分區(qū)策略

上面我們說(shuō)到了Hash分區(qū)和范圍分區(qū)兩種策略，哪種更好呢？這要看情況了，如果你需要經(jīng)常做范圍查詢，需要按順序?qū)ey值進(jìn)行操作，那么你選擇范圍分區(qū)會(huì)比較好。因?yàn)槿绻x擇hash分區(qū)的話，要查詢一個(gè)范圍的數(shù)據(jù)可能就需要跨好幾個(gè)節(jié)點(diǎn)來(lái)進(jìn)行了。 那如果我不會(huì)進(jìn)行范圍查詢或者順序查詢呢？這時(shí)候hash分區(qū)相對(duì)來(lái)說(shuō)可能更方便一點(diǎn)，而且hash分區(qū)時(shí)可能通過(guò)虛擬結(jié)點(diǎn)的設(shè)置來(lái)解決hash不均的問(wèn)題。在hash分區(qū)中，基本上只要在客戶端執(zhí)行相應(yīng)的hash函數(shù)就能知道對(duì)應(yīng)的數(shù)據(jù)存在哪個(gè)節(jié)點(diǎn)上了。而如果考慮到節(jié)點(diǎn)故障后的數(shù)據(jù)轉(zhuǎn)移情況，可能獲取到數(shù)據(jù)存放節(jié)點(diǎn)就會(huì)麻煩一些了。 范圍分區(qū)要求在查詢數(shù)據(jù)前對(duì)配置節(jié)點(diǎn)還要進(jìn)行一次查詢，如果沒(méi)有特別好的高可用容災(zāi)方案，配置節(jié)點(diǎn)將會(huì)是一個(gè)危險(xiǎn)的故障單點(diǎn)。當(dāng)然，你可以把配置節(jié)點(diǎn)再進(jìn)行一層負(fù)載均衡來(lái)減輕負(fù)載。而范圍分區(qū)時(shí)如果某個(gè)節(jié)點(diǎn)故障了，它上面的數(shù)據(jù)可以被分配到多個(gè)節(jié)點(diǎn)上，而不像在一致性hash時(shí)，只能遷移到其順序的后一個(gè)節(jié)點(diǎn)，造成下一個(gè)節(jié)點(diǎn)的負(fù)載飆升。

13.5 一致性

上面我們講到了通過(guò)將數(shù)據(jù)冗余存儲(chǔ)到不同的節(jié)點(diǎn)來(lái)保證數(shù)據(jù)安全和減輕負(fù)載，下面我們來(lái)看看這樣做引發(fā)的一個(gè)問(wèn)題：保證數(shù)據(jù)在多個(gè)節(jié)點(diǎn)間的一致性是非常困難的。在實(shí)際應(yīng)用中我們會(huì)遇到很多困難，同步節(jié)點(diǎn)可能會(huì)故障，甚至?xí)o(wú)法恢復(fù)，網(wǎng)絡(luò)可能會(huì)有延遲或者丟包，網(wǎng)絡(luò)原因?qū)е录褐械臋C(jī)器被分隔成兩個(gè)不能互通的子域等等。在NoSQL中，通常有兩個(gè)層次的一致性：第一種是強(qiáng)一致性，既集群中的所有機(jī)器狀態(tài)同步保持一致。第二種是最終一致性，既可以允許短暫的數(shù)據(jù)不一致，但數(shù)據(jù)最終會(huì)保持一致。我們先來(lái)講一下，在分布式集群中，為什么最終一致性通常是更合理的選擇，然后再來(lái)討論兩種一致性的具體實(shí)現(xiàn)結(jié)節(jié)。

13.5.1 關(guān)于CAP理論

為什么我們會(huì)考慮削弱數(shù)據(jù)的一致性呢？其實(shí)這背后有一個(gè)關(guān)于分布式系統(tǒng)的理論依據(jù)。這個(gè)理論最早被 Eric Brewer 提出，稱為CAP理論，爾后Gilbert 和 Lynch 對(duì)CAP進(jìn)行了理論證明。這一理論首先把分布式系統(tǒng)中的三個(gè)特性進(jìn)行了如下歸納： 一致性（C）：在分布式系統(tǒng)中的所有數(shù)據(jù)備份，在同一時(shí)刻是否同樣的值。 可用性（A）：在集群中一部分節(jié)點(diǎn)故障后，集群整體是否還能響應(yīng)客戶端的讀寫請(qǐng)求。 分區(qū)容忍性（P）：集群中的某些節(jié)點(diǎn)在無(wú)法聯(lián)系后，集群整體是否還能繼續(xù)進(jìn)行服務(wù)。 而CAP理論就是說(shuō)在分布式存儲(chǔ)系統(tǒng)中，最多只能實(shí)現(xiàn)上面的兩點(diǎn)。而由于當(dāng)前的網(wǎng)絡(luò)硬件肯定會(huì)出現(xiàn)延遲丟包等問(wèn)題，所以分區(qū)容忍性是我們必須需要實(shí)現(xiàn)的。所以我們只能在一致性和可用性之間進(jìn)行權(quán)衡，沒(méi)有NoSQL系統(tǒng)能同時(shí)保證這三點(diǎn)。 要保證數(shù)據(jù)一致性，最簡(jiǎn)單的方法是令寫操作在所有數(shù)據(jù)節(jié)點(diǎn)上都執(zhí)行成功才能返回成功。而這時(shí)如果某個(gè)結(jié)點(diǎn)出現(xiàn)故障，那么寫操作就成功不了了，需要一直等到這個(gè)節(jié)點(diǎn)恢復(fù)。也就是說(shuō)，如果要保證強(qiáng)一致性，那么就無(wú)法提供7×24的高可用性。 而要保證可用性的話，就意味著節(jié)點(diǎn)在響應(yīng)請(qǐng)求時(shí)，不用完全考慮整個(gè)集群中的數(shù)據(jù)是否一致。只需要以自己當(dāng)前的狀態(tài)進(jìn)行請(qǐng)求響應(yīng)。由于并不保證寫操作在所有節(jié)點(diǎn)都寫成功，這可能會(huì)導(dǎo)致各個(gè)節(jié)點(diǎn)的數(shù)據(jù)狀態(tài)不一致。 CAP理論導(dǎo)致了最終一致性和強(qiáng)一致性兩種選擇。當(dāng)然，事實(shí)上還有其它的選擇，比如在Yahoo! 的PNUTS中，采用的就是松散的一致性和弱可用性結(jié)合的方法。但是我們討論的NoSQL系統(tǒng)沒(méi)有類似的實(shí)現(xiàn)，所以我們?cè)诤罄m(xù)不會(huì)對(duì)其進(jìn)行討論。

13.5.2 強(qiáng)一致性

強(qiáng)一致性的保證，要求所有數(shù)據(jù)節(jié)點(diǎn)對(duì)同一個(gè)key值在同一時(shí)刻有同樣的value值。雖然實(shí)際上可能某些節(jié)點(diǎn)存儲(chǔ)的值是不一樣的，但是作為一個(gè)整體，當(dāng)客戶端發(fā)起對(duì)某個(gè)key的數(shù)據(jù)請(qǐng)求時(shí)，整個(gè)集群對(duì)這個(gè)key對(duì)應(yīng)的數(shù)據(jù)會(huì)達(dá)成一致。下面就舉例說(shuō)明這種一致性是如何實(shí)現(xiàn)的。 假設(shè)在我們的集群中，一個(gè)數(shù)據(jù)會(huì)被備份到N個(gè)結(jié)點(diǎn)。這N個(gè)節(jié)點(diǎn)中的某一個(gè)可能會(huì)扮演協(xié)調(diào)器的作用。它會(huì)保證每一個(gè)數(shù)據(jù)寫操作會(huì)在成功同步到W個(gè)節(jié)點(diǎn)后才向客戶端返回成功。而當(dāng)客戶端讀取數(shù)據(jù)時(shí)，需要至少R個(gè)節(jié)點(diǎn)返回同樣的數(shù)據(jù)才能返回讀操作成功。而NWR之間必須要滿足下面關(guān)系：R＋W>N 下面舉個(gè)實(shí)在的例子。比如我們?cè)O(shè)定N＝3（數(shù)據(jù)會(huì)備份到A、B、C三個(gè)結(jié)點(diǎn)）。比如值 employee30:salary 當(dāng)前的值是20000，我們想將其修改為30000。我們?cè)O(shè)定W＝2，下面我們會(huì)對(duì)A、B、C三個(gè)節(jié)點(diǎn)發(fā)起寫操作（employee30:salary, 30000），當(dāng)A、B兩個(gè)節(jié)點(diǎn)返回寫成功后，協(xié)調(diào)器就會(huì)返回給客戶端說(shuō)寫成功了。至于節(jié)點(diǎn)C，我們可以假設(shè)它從來(lái)沒(méi)有收到這個(gè)寫請(qǐng)求，他保存的依然是20000那個(gè)值。之后，當(dāng)一個(gè)協(xié)調(diào)器執(zhí)行一個(gè)對(duì)employee30:salary的讀操作時(shí)，他還是會(huì)發(fā)三個(gè)請(qǐng)求給A、B、C三個(gè)節(jié)點(diǎn)： 如果設(shè)定R＝1，那么當(dāng)C節(jié)點(diǎn)先返回了20000這個(gè)值時(shí)，那我們客戶端實(shí)際得到了一個(gè)錯(cuò)誤的值。 如果設(shè)定R＝2，則當(dāng)協(xié)調(diào)器收到20000和30000兩個(gè)值時(shí)，它會(huì)發(fā)現(xiàn)數(shù)據(jù)不太正確，并且會(huì)在收到第三個(gè)節(jié)點(diǎn)的30000的值后判斷20000這個(gè)值是錯(cuò)誤的。 所以如果要保證強(qiáng)一致性，在上面的應(yīng)用場(chǎng)景中，我們需要設(shè)定R＝2，W＝2 如果寫操作不能收到W個(gè)節(jié)點(diǎn)的成功返回，或者寫操作不能得到R個(gè)一致的結(jié)果。那么協(xié)調(diào)器可能會(huì)在某個(gè)設(shè)定的過(guò)期時(shí)間之后向客戶端返回操作失敗，或者是等到系統(tǒng)慢慢調(diào)整到一致。這可能就導(dǎo)致系統(tǒng)暫時(shí)處于不可用狀態(tài)。 對(duì)于R和W的不同設(shè)定，會(huì)導(dǎo)致系統(tǒng)在進(jìn)行不同操作時(shí)需要不同數(shù)量的機(jī)器節(jié)點(diǎn)可用。比如你設(shè)定在所有備份節(jié)點(diǎn)上都寫入才算寫成功，既W＝N，那么只要有一個(gè)備份節(jié)點(diǎn)故障，寫操作就失敗了。一般設(shè)定是R＋W = N+1，這是保證強(qiáng)一致性的最小設(shè)定了。一些強(qiáng)一致性的系統(tǒng)設(shè)定W＝N，R＝1，這樣就根本不用考慮各個(gè)節(jié)點(diǎn)數(shù)據(jù)可能不一致的情況了。 HBase是借助其底層的HDFS來(lái)實(shí)現(xiàn)其數(shù)據(jù)冗余備份的。HDFS采用的就是強(qiáng)一致性保證。在數(shù)據(jù)沒(méi)有完全同步到N個(gè)節(jié)點(diǎn)前，寫操作是不會(huì)返回成功的。也就是說(shuō)它的W＝N，而讀操作只需要讀到一個(gè)值即可，也就是說(shuō)它R＝1。為了不至于讓寫操作太慢，對(duì)多個(gè)節(jié)點(diǎn)的寫操作是并發(fā)異步進(jìn)行的。在直到所有的節(jié)點(diǎn)都收到了新的數(shù)據(jù)后，會(huì)自動(dòng)執(zhí)行一個(gè)swap操作將新數(shù)據(jù)寫入。這個(gè)操作是原子性和一致性的。保證了數(shù)據(jù)在所有節(jié)點(diǎn)有一致的值。

13.5.3 最終一致性

像Voldemort，Cassandra和Riak這些類Dynamo的系統(tǒng)，通常都允許用戶按需要設(shè)置N，R，W三個(gè)值，即使是設(shè)置成W＋R<= N也是可以的。也就是說(shuō)他允許用戶在強(qiáng)一致性和最終一致性之間自由選擇。而在用戶選擇了最終一致性，或者是W

由于同一份數(shù)據(jù)在不同的節(jié)點(diǎn)可能存在不同值，對(duì)數(shù)據(jù)的版本控制和沖突監(jiān)測(cè)就變得尤為重要。類Dynamo的系統(tǒng)通常都使用了一種叫vector clock（向量時(shí)鐘）的版本控制機(jī)制。一個(gè)vector clock可以理解成是一個(gè)向量，它包含了這個(gè)值在每一個(gè)備份節(jié)點(diǎn)中修改的次數(shù)。比如說(shuō)有的數(shù)據(jù)會(huì)備份到A，B，C三個(gè)節(jié)點(diǎn)，那么這些值的vector clock值就是類似（NA，NB，NC），而其初始值為（0，0，0）。 每次一個(gè)key的值被修改，其vector clock相應(yīng)的值就會(huì)加1。比如有一個(gè)key值當(dāng)前的vector clock值為（39，1，5），然后他在B節(jié)點(diǎn)被修改了一次，那么它的cector clock值就會(huì)相應(yīng)的變成（39，2，5）。而當(dāng)另一個(gè)節(jié)點(diǎn)C在收到B節(jié)點(diǎn)的同步請(qǐng)求時(shí)，他會(huì)先用自己保存的vector clock值與B傳來(lái)的vector clock值進(jìn)行對(duì)比，如果自己的vector clock值的每一項(xiàng)都小于等于B傳來(lái)的這個(gè)值，那么說(shuō)明這次的修改值是在自已保存的值上的修改，不會(huì)有沖突，直接進(jìn)行相應(yīng)的修改，并把自己的vector clock值更新。但是如果C發(fā)現(xiàn)自己的vector clock有些項(xiàng)比B大，而某些項(xiàng)比B小，比如B的是（39，2，5）C的是（39，1，6），那么這時(shí)候說(shuō)明B的這次修改并不是在C的基礎(chǔ)上改的，數(shù)據(jù)出現(xiàn)沖突了。 沖突解決

不同的系統(tǒng)有不同的沖突解決策略。Dynamo選擇把沖突留給應(yīng)用層來(lái)解決。如果是兩個(gè)節(jié)點(diǎn)保存的購(gòu)物車信息沖突了，可以選擇簡(jiǎn)單的通過(guò)把兩個(gè)數(shù)據(jù)合并進(jìn)行解決。但如果是對(duì)同一份文檔進(jìn)行的修改沖突了，可能就需要人工來(lái)解決沖突了（譯者：像我們?cè)赟VN中做的一樣）。Voldemort就是采用的后者，它在發(fā)現(xiàn)沖突后，會(huì)把有沖突的幾份數(shù)據(jù)一起返回給應(yīng)用層，把沖突解決留給應(yīng)用層來(lái)做。 Cassandra通過(guò)為每一個(gè)操作保存一個(gè)時(shí)間戳的方法來(lái)解決沖突，在沖突的幾個(gè)版本里，最后修改的一個(gè)會(huì)獲勝成為新的值。相對(duì)于上面的方式，它減少了通過(guò)應(yīng)用層解決沖突時(shí)需要的網(wǎng)絡(luò)訪問(wèn)，同時(shí)也簡(jiǎn)化了客戶端的操作API。但這種策略并不適合用來(lái)處理一些需要合并沖突的場(chǎng)合，比如上面的購(gòu)物車的例子，或者是分布式的計(jì)數(shù)器這樣的應(yīng)用。而Riak把Voldemort和 Cassandra 的策略都實(shí)現(xiàn)了。CouchDB會(huì)把沖突的key進(jìn)行標(biāo)識(shí)，以便應(yīng)用層可以主動(dòng)進(jìn)行人工修復(fù)，在修復(fù)完成前，客戶端的請(qǐng)求是無(wú)法得到確定值的。 讀時(shí)修復(fù)

在數(shù)據(jù)讀取時(shí)，如果有R個(gè)節(jié)點(diǎn)返回了一致的數(shù)據(jù)，那么協(xié)調(diào)器就可以認(rèn)為這個(gè)值是正確的并返回給客戶端了。但是在總共返回的N個(gè)值中，如果協(xié)調(diào)器發(fā)現(xiàn)有的數(shù)據(jù)不是最新的。那么它可以通過(guò)讀時(shí)修復(fù)機(jī)制來(lái)對(duì)這些節(jié)點(diǎn)進(jìn)行處理。這種方式在Dynamo中有描述，在Voldemort 、 Cassandra和Riak中都得到了實(shí)現(xiàn)。當(dāng)協(xié)調(diào)器發(fā)現(xiàn)有的節(jié)點(diǎn)數(shù)據(jù)不是最新時(shí)，它會(huì)在數(shù)據(jù)不一致的節(jié)點(diǎn)間啟動(dòng)一個(gè)沖突解決過(guò)程。這樣主動(dòng)的修復(fù)策略并不會(huì)有多大的工作量。因?yàn)樽x取操作時(shí)，各個(gè)節(jié)點(diǎn)都已經(jīng)把數(shù)據(jù)返回給協(xié)調(diào)器了，所以解決沖突越快，實(shí)際上可能造成的后續(xù)的不一致的可能性也就越小。

Hinted Handoff

Cassandra、Riak和Voldemort都實(shí)現(xiàn)了一種叫Hinted Handoff的技術(shù)，用來(lái)保證在有節(jié)點(diǎn)故障后系統(tǒng)的寫操作不受太大影響。它的過(guò)程是如果負(fù)責(zé)某個(gè)key值的某個(gè)節(jié)點(diǎn)宕機(jī)了，另一個(gè)節(jié)點(diǎn)會(huì)被選擇作為其臨時(shí)切換點(diǎn)，以臨時(shí)保存在故障節(jié)點(diǎn)上面的寫操作。這些寫操作被單獨(dú)保存起來(lái)，直到故障節(jié)點(diǎn)恢復(fù)正常，臨時(shí)節(jié)點(diǎn)會(huì)把這些寫操作重新遷移給剛剛恢復(fù)的節(jié)點(diǎn)。Dynamo 論文中提到一種叫“sloppy quorum”的方法，它會(huì)把通過(guò) Hinted Handoff 寫成功的臨時(shí)節(jié)點(diǎn)也計(jì)算在成功寫入數(shù)中。但是Cassandra和Voldemort并不會(huì)將臨時(shí)節(jié)點(diǎn)也算在寫入成功節(jié)點(diǎn)數(shù)內(nèi)，如果寫入操作并沒(méi)有成功寫在W個(gè)正式節(jié)點(diǎn)中，它們會(huì)返回寫入失敗。當(dāng)然，Hinted Handoff 策略在這些系統(tǒng)中也有使用，不過(guò)只是用在加速節(jié)點(diǎn)恢復(fù)上。

Anti-Entropy

如果一個(gè)節(jié)點(diǎn)故障時(shí)間太長(zhǎng)，或者是其 Hinted Handoff 臨時(shí)替代節(jié)點(diǎn)也故障了，那么新恢復(fù)的節(jié)點(diǎn)就需要從其它節(jié)點(diǎn)中同步數(shù)據(jù)了。（譯者：實(shí)際上就是要找出經(jīng)過(guò)這段時(shí)間造成的數(shù)據(jù)差異，并將差異部分同步過(guò)來(lái)）。這種情況下Cassandra和Riak都實(shí)現(xiàn)了在Dynamo文檔中提到的一種方法，叫做anti-entropy。在anti-entropy過(guò)程中，節(jié)點(diǎn)間通過(guò)交換Merkle Tree來(lái)找出那些不一致的部分。Merkle Tree是一個(gè)分層的hash校驗(yàn)機(jī)制：如果包含某個(gè)key值范圍的hash值在兩個(gè)數(shù)據(jù)集中不相同，那么不同點(diǎn)就在這個(gè)key值范圍，同理，如果頂層的hash值相同，那么其負(fù)責(zé)的所有key值范圍內(nèi)的值都認(rèn)為是相同的。這種方法的好處是，在節(jié)點(diǎn)恢復(fù)時(shí)，不用把所有的值都傳一遍來(lái)檢查哪些值是有變化的。只需要傳幾個(gè)hash值就能找到不一致的數(shù)據(jù)，重傳這個(gè)數(shù)據(jù)即可。

Gossip

當(dāng)一個(gè)分布式系統(tǒng)越來(lái)越大，就很難搞清集群中的每個(gè)節(jié)點(diǎn)的狀態(tài)了。上面說(shuō)到的類Dynamo 應(yīng)用都采用了Dynamo文檔中說(shuō)到的一種古老的方法：Gossip。通過(guò)這個(gè)方法，節(jié)點(diǎn)間能夠互相保持聯(lián)系并能夠檢測(cè)到故障節(jié)點(diǎn)。其具體做法是，每隔一段時(shí)間（比如一秒），一個(gè)節(jié)點(diǎn)就會(huì)隨便找一個(gè)曾經(jīng)有過(guò)通信的節(jié)點(diǎn)與其交換一下其它節(jié)點(diǎn)的健康狀態(tài)。通過(guò)這種方式，節(jié)點(diǎn)能夠比較快速的了解到集群中哪些節(jié)點(diǎn)故障了，從而把這些節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)分配到其它節(jié)點(diǎn)去。（譯者：Gossip其實(shí)是仿生學(xué)的設(shè)計(jì)，Gossip意思為流言，節(jié)點(diǎn)傳播其它節(jié)點(diǎn)的健康信息，就像一個(gè)小村鎮(zhèn)里的無(wú)聊婦人們互相說(shuō)別人的閑話一樣，基本上誰(shuí)家誰(shuí)人出什么事了，都能比較快地被所有人知道）。

13.6 寫在最后的話

目前NoSQL系統(tǒng)來(lái)處在它的萌芽期，我們上面討論到的很多NoSQL系統(tǒng)，他們的架構(gòu)、設(shè)計(jì)和接口可能都會(huì)改變。本章的目的，不在于讓你了解這些NoSQL系統(tǒng)目前是如何工作的，而在于讓你理解這些系統(tǒng)之所以這樣實(shí)現(xiàn)的原因。NoSQL系統(tǒng)把更多的設(shè)計(jì)工作留給了應(yīng)用開(kāi)發(fā)工作者來(lái)做。理解上面這些組件的架構(gòu)，不僅能讓您寫出下一個(gè)NoSQL系統(tǒng)，更讓您對(duì)現(xiàn)有系統(tǒng)應(yīng)用得更好。

13.7 致謝

非常感謝Jackie Carter, Mihir Kedia，以及所有對(duì)本章進(jìn)行校對(duì)并且提出寶貴意見(jiàn)的人。沒(méi)有這些年來(lái)NoSQL社區(qū)的專注工作，也不會(huì)有這一章內(nèi)容的誕生。各位加油。 相關(guān)信息

原文: http://www.aosabook.org/en/nosql.html 原作者：Adam Marcus 譯者：iammutex 組織：NoSQLFan 翻譯時(shí)間：2011年6月

（編者注：本文根據(jù)NoSQLFan網(wǎng)站原載同名文章http://blog.nosqlfan.com/html/2171.html整理而成，英文原文鏈接為http://www.aosabook.org/en/nosql.html）