[譯] NoSQL生態系統
NoSQL相關論壇 bbs. 開通！歡迎參與討論。
本文原文出自《The Architecture of Open Source Applications》一書第13章《The NoSQL Ecosystem》，由NoSQLFan的@iammutex，也就是正在碼字的我，利用業余時間零碎時間經過半個月左右翻譯完成。
不得不說這是一個非常有意思的過程，凡是做過翻譯的人應該都能理解翻譯與閱讀在深度和細度上的差別，通過對本章內容的翻譯，我的收獲很多，一些錯誤想法得到糾正，很多理論的理解也更清晰了。當然，不排除中間有用詞不當語句不通甚至是理解不正確的情況，請各位讀者多提意見。
聲明：本文在NoSQLFan首發，一切轉載行為須注明作者及出處。
下面就看正文吧～
NoSQL生態系統
與本書中提到的其它主題不同，NoSQL不是一個工具，而是由一些具有互補性和競爭性的工具組成的一個概念，是一個生態圈。這些被稱作NoSQL的 工具，在存儲數據的方式上，提供了一種與基于SQL語言的關系型數據截然不同的思路。要想了解NoSQL，我們必須先了解現有的這些工具，去理解那些讓他 們開拓出新的存儲領域的設計思路。
如果你正在考慮使用NoSQL，你應該會馬上發現你有很多種選擇。NoSQL系統舍棄了許了傳統關系型數據庫的方便之處，而把一些通常由關系型數據庫本身來完成的任務交給了應用層來完成。這需要開發人員更深入的去了解存儲系統的架構和具體實現。
13.1 NoSQL其名
在給NoSQL下定義之前，我們先來試著從它的名字上做一下解讀，顧名思義，NoSQL系統的數據操作接口應該是非SQL類型的。但在NoSQL社 區，NoSQL被賦予了更具有包容性的含義，其意為Not Only SQL，即NoSQL提供了一種與傳統關系型數據庫不太一樣的存儲模式，這為開發者提供了在關系型數據庫之外的另一種選擇。有時候你可能會完全用 NoSQL數據庫代替關系型數據加，但你也可以同時使用關系型和非關系型存儲來解決具體的問題。
在進入NoSQL的大門之前，我們先來看看哪些場景下使用關系型數據庫更合適，哪些使用NoSQL更合適。
13.1.1 SQL及其關聯型結構
SQL是一種任務描述性的查詢語言，所謂任務描述性的查詢語言，就是說它只描述他需要系統做什么，而不告訴系統如何去做。例如：查出39號員工的信息，查出員工的名字和電話，只查找做會計工作的員工信息，計算出每個部門的員工總數，或者是對員工表和經理表做一個聯合查詢。
簡單的說，SQL讓我們可以直接向數據庫提出上述問題而不必考慮數據是如何在磁盤上存儲的，使用哪些索引來查詢數據，或者說用哪種算法來處理數據。 在關系型數據庫中有一個重要的組件，叫做查詢優化器，正是它來推算用哪種操作方式能夠更快的完成操作。查詢優化器通常比一般的數據庫用戶更聰明，但是有時 候由于沒有充足的信息或者系統模型過于簡單，也會導致查詢優化器不能得出最有效的操作方式。
作為目前應用最廣的數據庫系統，關系型數據庫系統以其關聯型的數據模型而命名。在關聯型的數據模型中，在現實世界中的不同類型的個體被存儲在不同的 表里。比如有一個專門存員工的員工表，有一個專門存部門的部門表。每一行數據又包含多個列，比如員工表里可能包含了員工號，員工工資，生日以及姓名等，這 些信息項被存在員工表中的某一列中。
關聯型的模型與SQL是緊密想連的。簡單的查詢操作，比如查詢符合某個條件的所有行（例：employeeid = 3, 或者 salary > $20000）。更復雜一些的任務會讓數據庫做一些額外的工作，比如跨表的聯合查詢（例：查出3號員的部門名稱是什么）。一些復雜的查詢，比如統計操作 （例：算出所有員工的平均工資），甚至可能會導致全表掃描。
關聯型的數據模型定義了高度結構化的數據結構，以及對這些結構之間關系的嚴格定義。在這樣的數據模型上執行的查詢操作會比較局限，而且可能會導致復雜的數據遍歷操作。數據結構的復雜性及查詢的復雜性，會導致系統產生如下的一些限制：
- 復雜導致不確定性。使用SQL的一個問題就是計算某個查詢的代價或者產生的負載幾乎是不可能的。使用簡單的查詢語言可能會導致應用層的邏輯更復雜，但是這樣可以將存儲系統的工作簡單化，讓它只需要響應一些簡單的請求。
- 對一個問題建模有很多種方式。其中關聯型的數據模型是非常嚴格的一種：表結構的定義規定了表中每一行數據的存儲內容。如果你的數據結構化并沒有那 么強，或者對每一行數據的要求比較靈活，那可能關聯型的數據模型就太過嚴格了。類似的，應用層的開發人員可能對關聯型的數據結構并不滿意。比如很多應用程 序是用面向對象的語言寫的，數據在這些語言中通常是以列表、隊列或集合的形式組織的，程序員們當然希望他們的數據存儲層也能和應用層的數據模型一致。
- 當數據量增長到一臺機器已經不能容納，我們需要將不同的數據表分布到不同的機器。而為了避免在不同機器上的數據表在進行聯合查詢時需要跨網絡進 行。我們必須進行反范式的數據庫設計，這種設計方式要求我們把需要一次性查詢到的數據存儲在一起。這樣做使得我們的系統變得就像一個主鍵查詢系統一樣，于 是我們開始思考，是否有其它更適合我們數據的數據模型。
通常來說，舍棄多年以來的設計思路是不明智的。當你要把數據存到數據庫，當考慮到SQL與關聯型的數據模型，這些都是數十年的研究的開發成果，提供 豐富的數據模型，提供復雜操作的保證。而當你的問題涉及到大數據量，高負載或者說你的數據結構在SQL與關聯型數據模型下很難得到優化，NoSQL可能是 更好的選擇。
13.1.2 NoSQL的啟示
NoSQL運動受到了很多相關研究論文的啟示，這所有論文中，最核心的有兩個。
Google的BigTable[CDG+06]提出了一種很有趣的數據模型，它將各列數據進行排序存儲。數據值按范圍分布在多臺機器，數據更新操作有嚴格的一致性保證。
Amazon的Dynamo[DHJ+07]使用的是另外一種分布式模型。Dynamo的模型更簡單，它將數據按key進行hash存儲。其數據分片模型有比較強的容災性，因此它實現的是相對松散的弱一致性：最終一致性。
接下來我們會深入介紹這些設計思想，而實際上在現實中這些思想經常是混搭使用的。比如像HBase及其它一些NoSQL系統他們在設計上更接受 BigTable的模型，而像Voldemort 系統它就和Dynamo更像。同時還有像Cassandra這種兩種特性都具備的實現（它的數據模型和BigTable類似，分片策略和一致性機制和 Dynamo類似）。
13.1.3 特性概述
NoSQL系統舍棄了一些SQL標準中的功能，取而代之的是提供了一些簡單靈活的功能。NoSQL 的構建思想就是盡量簡化數據操作，盡量讓執行操作的效率可預知。在很多NoSQL系統里，復雜的操作都是留給應用層來做的，這樣的結果就是我們對數據層進 行的操作得到簡化，讓操作效率可預知。
NoSQL系統不僅舍棄了很多關系數據庫中的操作。它還可能不具備關系數據庫以下的一些特性：比如通常銀行系統中要求的事務保證，一致性保證以及數 據可靠性的保證等。事務機制提供了在執行多個命令時的all-or-nothing保證。一致性保證了如果一個數據更新后，那么在其之后的操作中都能看到 這個更新。可靠性保證如果一個數據被更新，它就會被寫到持久化的存儲設備上（比如說磁盤），并且保證在數據庫崩潰后數據可恢復。
通過放寬對上述幾點特性的要求，NoSQL系統可以為一些非銀行類的業務提供以性能換穩定的策略。而同時，對這幾點要求的放寬，又使得NoSQL系統能夠輕松的實現分片策略，將遠遠超出單機容量的大量數據分布在多臺機器上的。
由于NoSQL系統還處在萌芽階段，本章中提到的很多NoSQL架構都是用于滿足各種不同用戶的需求的。對這些架構進行總結不太可能，因為它們總在 變化。所以希望你能記住的一點是，不同的NoSQL系統的特點是不同的，通過本章的內容，希望你能該根據自己的業務情況來選擇合適的NoSQL系統，而本 章內容不可能給你直接的答案。
當你去考查一個NoSQL系統的時候，下面的的幾點是值得注意的：
- 數據模型及操作模型：你的應用層數據模型是行、對象還是文檔型的呢？這個系統是否能支持你進行一些統計工作呢？
- 可靠性：當你更新數據時，新的數據是否立刻寫到持久化存儲中去了？新的數據是否同步到多臺機器上了？
- 擴展性：你的數據量有多大，單機是否能容下？你的讀寫量求單機是否能支持？
- 分區策略：考慮到你對擴展性，可用性或者持久性的要求，你是否需要一份數據被存在多臺機器上？你是否需要知道數據在哪臺機器上，以及你能否知道。
- 一致性：你的數據是否被復制到了多臺機器上，這些分布在不同點的數據如何保證一致性？
- 事務機制：你的業務是否需要ACID的事務機制？
- 單機性能：如果你打算持久化的將數據存在磁盤上，哪種數據結構能滿足你的需求（你的需求是讀多還是寫多）？寫操作是否會成為磁盤瓶頸？
- 負載可評估：對于一個讀多寫少的應用，諸如響應用戶請求的web應用，我們總會花很多精力來關注負載情況。你可能需要進行數據規模的監控，對多個用戶的數據進行匯總統計。你的應用場景是否需要這樣的功能呢？
盡管后三點在本章沒有獨立的小節進行描述，但它們和其它幾點一樣重要，下面就讓我們對以上的幾點進行闡述。
13.2 NoSQL數據模型及操作模型
數據庫的數據模型指的是數據在數據庫中的組織方式，數據庫的操作模型指的是存取這些數據的方式。通常數據模型包括關系模型、鍵值模型以及各種圖結構 模型。的操作語言可能包括SQL、鍵值查詢及MapReduce等。NoSQL通常結合了多種數據模型和操作模型，提供了不一樣的架構方式。
13.2.1 基于key值存儲的NoSQL數據模型
在鍵值型系統中，復雜的聯合操作以及滿足多個條件的取數據操作就不那么容易了，需要我們創造性的建立和使用鍵名。如果一個程序員既想通過員工號查到 員工信息，又想通過部門號查到員工信息，那么他必須建立兩種類型的鍵值對。例如 emplyee:30 這個鍵用于指向員工號為30的員工信息。employee_departments:20 可能用到指向一個包含在20號部門工作的所有員工工號的列表。這樣數據庫中的聯合操作就被轉換成業務層的邏輯了：要獲取部門號為20的所有員工的信息，應 用層可以先獲取employee_departments:20 這個列表，然后再循環地拿這個列表中的ID通過獲取employee:ID得到所有員工的信息。
鍵值查找的一個好處是，對數據庫的操作模式是固定的，這些操作所產生的負載也是相對固定且可預知的。這樣像分析整個應用中的性能瓶頸這種事，就變得簡單多了。因為復雜的邏輯操作并不是放在數據庫里面黑箱操作了。不過這樣做之后，業務邏輯和數據邏輯可能就沒那么容易分清了。
下面我們快速地把各種鍵值模型的數據結構簡單描述一下。看看不同的NoSQL系統的在這方面的不同實現方式。
Key-Value 存儲
Key-Value存儲可以說是最簡單的NoSQL存儲。每個key值對應一個任意的數據值。對NoSQL 系統來說，這個任意的數據值是什么，它并不關心。比如在員工信念數據庫里，exployee:30 這個key對應的可能就是一段包含員工所有信息的二進制數據。這個二進制的格式可能是Protocol Buffer、Thrift或者Avro都無所謂。
如果你使用上面說的Key-Value存儲來保存你的結構化數據，那么你就得在應用層來處理具體的數據結構：單純的Key-Value存儲是不提供 針對數據中特定的某個屬性值來進行操作。通常它只提供像set、get和delete這樣的操作。以Dynamo為原型的Voldemort數據庫，就只 提供了分布式的Key-Value存儲功能。BDB 是一個提供Key-Value操作的持久化數據存儲引擎。
Key – 結構化數據 存儲
Key對應結構化數據存儲，其典型代表是Redis，Redis將Key-Value存儲的Value變成了結構化的數據類型。Value的類型包 括數字、字符串、列表、集合以及有序集合。除了set/get/delete 操作以為，Redis還提供了很多針對以上數據類型的特殊操作，比如針對數字可以執行增、減操作，對list可以執行 push/pop 操作，而這些對特定數據類型的特定操作并沒有對性能造成多大的影響。通過提供這種針對單個Value進行的特定類型的操作，Redis可以說實現了功能與 性能的平衡。
Key – 文檔 存儲
Key – 文檔存儲的代表有CouchDB、MongoDB和Riak。這種存儲方式下Key-Value的Value是結構化的文檔，通常這些文檔是被轉換成JSON或者類似于JSON的結構進行存儲。文檔可以存儲列表，鍵值對以及層次結構復雜的文檔。
MongoDB 將Key按業務分到各個collection里，這樣以collection作為命名空間，員工信息和部門信息的Key就被隔開了。CouchDB和 Riak把類型跟蹤這種事留給了開發者去完成。文檔型存儲的靈活性和復雜性是一把雙刃劍：一方面，開發者可以任意組織文檔的結構，另一方面，應用層的查詢 需求會變得比較復雜。
BigTable 的列簇式存儲
HBase和Cassandra的數據模型都借鑒自Google 的BigTable。這種數據模型的特點是列式存儲，每一行數據的各項被存儲在不同的列中（這些列的集合稱作列簇）。而每一列中每一個數據都包含一個時間 戳屬性，這樣列中的同一個數據項的多個版本都能保存下來。
列式存儲可以理解成這樣，將行ID、列簇號，列號以及時間戳一起，組成一個Key，然后將Value按Key的順序進行存儲。Key值的結構化使這 種數據結構能夠實現一些特別的功能。最常用的就是將一個數據的多個版本存成時間戳不同的幾個值，這樣就能很方便的保存歷史數據。這種結構也能天然地進行高 效的松散列數據（在很多行中并沒有某列的數據）存儲。當然，另一方面，對于那些很少有某一行有NULL值的列，由于每一個數據必須包含列標識，這又會造成 空間的浪費。
這些NoSQL系統對BigTable數據模型的實現多少有些差別，這其中以Cassandra進行的變更最為顯著。Cassandra引入了超級 列（supercolumn）的概念，通過將列組織到相應的超級列中，可以在更高層級上進行數據的組織，索引等。這一做法也取代了locality groups的概念（這一概念的實現可以讓相關的幾個行的數據存儲在一起，以提高存取性能）。
13.2.2 圖結構存儲
圖結構存儲是NoSQL的另一種存儲實現。圖結構存儲的一個指導思想是：數據并非對等的，關系型的存儲或者鍵值對的存儲，可能都不是最好的存儲方 式。圖結構是計算機科學的基礎結構之一，Neo4j和HyperGraphDB是當前最流行的圖結構數據庫。圖結構的存儲與我們之前討論過的幾種存儲方式 很不同，這種不同幾乎體現在每一個方面，包括：數據模型、數據查詢方式、數據在磁盤上的組織方式、在多個結點上的分布方式，甚至包括對事務機制的實現等 等。由于篇幅的限制，對這些方面我們暫時不做深入的討論，這里需要你了解的是，某些數據結構使用圖結構的數據庫進行存儲可能會更好。
13.2.3 復雜查詢
在NoSQL存儲系統中，有很多比鍵值查找更復雜的操作。比如MongoDB可以在任意數據行上建立索引，可以使用Javascript語法設定復 雜的查詢條件。BigTable型的系統通常支持對單獨某一行的數據進行遍歷，允許對單列的數據進行按特定條件地篩選。CouchDB允許你創建同一份數 據的多個視圖，通過運行MapReduce任務來實現一些更為復雜的查詢或者更新操作。很多NoSQL系統都支持與Hadoop或者其它一些 MapReduce框架結合來進行一些大規模數據分析工作。
13.2.4 事務機制
傳統的關系型數據庫在功能支持上通常很寬泛，從簡單的鍵值查詢，到復雜的多表聯合查詢再到事務機制的支持。而與之不同的是，NoSQL系統通常注重性能和擴展性，而非事務機制。
傳統的SQL數據庫的事務通常都是支持ACID的強事務機制。A代表原子性，即在事務中執行多個操作是原子性的，要么事務中的操作全部執行，要么一 個都不執行;C代表一致性，即保證進行事務的過程中整個數據加的狀態是一致的，不會出現數據花掉的情況;I代表隔離性，即兩個事務不會相互影響，覆蓋彼此 數據等;D表示持久化，即事務一量完成，那么數據應該是被寫到安全的，持久化存儲的設備上（比如磁盤）。
ACID的支持使得應用者能夠很清楚他們當前的數據狀態。即使如對于多個事務同時執行的情況下也能夠保證數據狀態的正常性。但是如果要保證數據的一致性，通常多個事務是不可能交叉執行的，這樣就導致了可能一個很簡單的操作需要等等一個復雜操作完成才能進行的情況。
對很多NoSQL系統來說，對性能的考慮遠在ACID的保證之上。通常NoSQL系統僅提供對行級別的原子性保證，也就是說同時對同一個Key下的 數據進行的兩個操作，在實際執行的時候是會串行的執行，保證了每一個Key-Value對不會被破壞。對絕大多數應用場景來說，這樣的保證并不會引起多大 的問題，但其換來的執行效率卻是非常可觀的。當然，使用這樣的系統可能需要我們在應用層的設計上多做容錯性和修正機制的考慮。
在NoSQL中，Redis在事務支持這方面上不太一樣，它提供了一個MULTI命令用來將多個命令進行組合式的操作，通過一個WATCH命令提供操作隔離性。這和其它一些提供test-and-set這樣的低層級的隔離機制類似。
13.2.5 Schema-free的存儲
還有一個很多NoSQL都有的共同點，就是它通常并沒有強制的數據結構約束。即使是在文檔型存儲或者列式存儲上，也不會要求某一個數據列在每一行數 據上都必須存在。這在非結構化數據的存儲上更方便，同時也省去了修改表結構的代價。而這一機制對應用層的容錯性要求可能會更高。比如程序可能得確定如果某 一個員工的信息里缺少lastname這一項，是否算是錯誤。或者說某個表結構的變更是否對所有數據行起了作用。還有一個問題，就是數據庫的表結構可能會 因為項目的多次迭代而變得混亂不堪。
13.3 數據可靠性
最理想狀態是，數據庫會把所有寫操作立刻寫到持久化存儲的設備，同時復制多個副本到不同地理位置的不同節點上以防止數據丟失。但是這種對數據安全性的要求對性能是有影響的，所以不同的NoSQL系統在自身性能的考慮下，在數據安全上采取了不太一樣的策略。
一種典型的出錯情況是重啟機器或者機器斷電了，這時候需要讓數據從內存轉存到磁盤才能保證數據的安全性，因為磁盤數據不會因斷電而丟失。而要避免磁 盤損壞這種故障，就需要將數據冗余的存在其它磁盤上，比如使用RAID來做鏡像，或者將數據同步到不同機器。但是有些時候針對同一個數據中心來說，是不可 能做到完全的數據安全的，比如一旦發生颶風地震這種天災，整個機房機器可能都會損壞，所以，在這種情況下要保證數據的安全性，就必須將數據備份存儲到其它 地理位置上比較遠的數據中心。所以，具體各個NoSQL系統在數據安全性和性能上的權衡策略也不太一樣。
13.3.1 單機可靠性
單機可靠性理解起來非常簡單，它的定義是寫操作不會由于機器重啟或者斷電而丟失。通常單機可靠性的保證是通過把數據寫到磁盤來完成的，而這通常會造 成磁盤IO成為整個系統的瓶頸。而事實上，即使你的程序每次都把數據寫到了磁盤，實際上由于操作系統buffer層的存在，數據還是不會立刻被寫到物理磁 盤上，只有當你調用fsync這個系統調用的時候，操作系統才會盡可能的把數據寫到磁盤。
一般的磁盤大概能進行每秒100-200次的隨機訪問，每秒30-100MB的順序寫入速度。而內存在這兩方面的性能都有數量級上的提升。通過盡量 減少隨機寫，取而代之的對每個磁盤設備進行順序寫，這樣能夠減少單機可靠性保證的代價。也就是說我們需要減少在兩次fsync調用之間的寫操作次數，而增 加順序寫操作的數量。下面我們說一下一些在單機可靠性的保證下提高性能的方法。
控制fsync的調用頻率
Memcached是一個純內存的存儲，由于其不進行磁盤上的持久化存儲，從而換來了很高的性能。當然，在我們進行服務器重啟或者服務器意外斷電后，這些數據就全丟了。因此Memcached 是一個非常不錯的緩存，但是做不了持久化存儲。
Redis則提供了幾種對fsync調用頻率的控制方法。應用開發者可以配置Redis在每次更新操作后都執行一次fsync，這樣會比較安全，當 然也就比較慢。Redis也可以設置成N秒種調用一次fsync，這樣性能會更好一點。但這樣的后果就是一旦出現故障，最多可能導致N秒內的數據丟失。而 對一些可靠性要求不太高的場合（比如僅僅把Redis當Cache用的時候），應用開發者甚至可以直接關掉fsync的調用：讓操作系統來決定什么時候需 要把數據flush到磁盤。
（譯者：這只是Redis append only file的機制，Redis是可以關閉aof日志的，另外請注意：Redis 本身支持將內存中數據dump成rdb文件的機制，和上面說的不是一回事。）使用日志型的數據結構
像B+ 樹這樣的一些數據結構，使得NoSQL系統能夠快速的定位到磁盤上的數據，但是通常這些數據結構的更新操作是隨機寫操作，如果你在每次操作后再調用一次 fsync，那就會造成頻繁的磁盤隨機訪問了。為了避免產生這樣的問題，像Cassandra、HBase、Redis和Riak都會把寫操作順序的寫入 到一個日志文件中。相對于存儲系統中的其它數據結構，上面說到的日志文件可以頻繁的進行fsync操作。這個日志文件記錄了操作行為，可以用于在出現故障 后恢復丟失那段時間的數據，這樣就把隨機寫變成順序寫了。
雖然有的NoSQL系統，比如MongoDB，是直接在原數據上進行更新操作的，但也有許多NoSQL系統是采用了上面說到的日志策略。 Cassandra和HBase借鑒了BigTable的做法，在數據結構上實現了一個日志型的查找樹。Riak也使用了類似的方法實現了一個日志型的 hash表（譯者：也就是Riak的BitCask模型）。CouchDB對傳統的B+樹結構進行了修改，使得對樹的更新可以使用順序的追加寫操作來實現（譯者：這種B+樹被稱作append-only B-Tree）。這些方法的使用，使得存儲系統的寫操作承載力更高，但同時為了防止數據異構后膨脹得過大，需要定時進行一些合并操作。
通過合并寫操作提高吞吐性能
Cassandra有一個機制，它會把一小段時間內的幾個并發的寫操作放在一起進行一次fsync調用。這種做法叫group commit，它導致的一個結果就是更新操作的返回時間可能會變長，因為一個更新操作需要等就近的幾個更新操作一起進行提交。這樣做的好處是能夠提高寫操 作承載力。作為HBase底層數據支持的Hadoop 分布式文件系統HDFS，它最近的一些補丁也在實現一些順序寫和group commit的機制。
13.3.2 多機可靠性
由于硬件層面有時候會造成無法恢復的損壞，單機可靠性的保證在這方面就鞭長莫及了。對于一些重要數據，跨機器做備份保存是必備的安全措施。一些NoSQL系統提供了多機可靠性的支持。
Redis采用了傳統的主從數據同步的方式。所有在master上執行的操作，都會通過類似于操作日志的結構順序地傳遞給slave上再執行一遍。 如果master發生宕機等事故，slave可以繼續執行完master傳來的操作日志并且成為新的master。可能這中間會導致一些數據丟失，因為 master同步操作到slave是非阻塞的，master并不知道操作是否已經同步線slave了。CouchDB 實現了一個類似的指向性的同步功能，它使得一個寫操作可以同步到其它節點上。
MongoDB提供了一個叫Replica Sets的架構方制，這個架構策略使得每一個文檔都會保存在組成Replica Sets的所有機器上。MongoDB提供了一些選項，讓開發者可以確定一個寫操作是否已經同步到了所有節點上，也可以在節點數據并不是最新的情況下執行 一些操作。很多其它的分布式NoSQL存儲都提供了類似的多機可靠性支持。由于HBase的底層存儲是HDFS，它也就自然的獲得了HDFS提供的多機可 靠性保證。HDFS的多機可靠性保證是通過把每個寫操作都同步到兩個以上的節點來實現的。
Riak、Cassandra和Voldemort提供了一些更靈活的可配置策略。這三個系統提供一個可配置的參數N，代表每一個數據會被備份的份數，然后還可以配置一個參數W，代表每個寫操作需要同步到多少能機器上才返回成功。當然W是小于N的。
為了應對整個數據中心出現故障的情況，需要實現跨數據中心的多機備份功能。Cassandra、HBase和Voldemort都實現了一個機架位 置可知的配置，這種配置方式使得整個分布式系統可以了解各個節點的地理位置分布情況。如果一個操作需要等待另外的數據中心的同步操作成功才返回給用戶，那 時間就太長了，所以通常跨數據中心的同步備份操作都是異步進行的。用戶并不需要等待另一個數據中心同步的同步操作執行成功。
13.4 橫向擴展帶來性能提升
上面我們討論了對出錯情況的處理，下面我們討論另一種情況：成功！如果數據存儲操作成功執行了，那么你的系統就要負責對這些數據進行處理。就要承擔 數據帶來的負載。一個比較粗暴的解決方法是通過升級你的機器來提升單機性能：通過加大內存和添加硬盤來應對越來越大的負載。但是隨著數據量的增大，投入在 升級機器上的錢將將不會產生原來那么大的效果。這時候你就必須考慮把數據同步到不同的機器上，利用橫向擴展來分擔訪問壓力。
橫向擴展的目標是達到線性的效果，即如果你增加一倍的機器，那么負載能力應該也能相應的增加一倍。其主要需要解決的問題是如何讓數據在多臺機器間分 布。數據分片技術實際上就是將對數據和讀寫請求在多個機器節點上進行分配的技術，分片技術在很多NoSQL系統中都有實現，比如Cassandra、 HBase、Voldemort和Riak等等，最近MongoDB和Redis也在做相應的實現。而有的項目并不提供內置的分片支持，比如 CouchDB更加注重單機性能的提升。對于這些項目，通常我們可以借助一些其它的技術在上層來進行負載分配。
下面讓我們來整理一些通用的概念。對于數據分片和分區，我們可以做同樣的理解。對機器，服務器或者節點，我們可以統一的理解成物理上的存儲數據的機器。最后，集群或者機器環都可以理解成為是組成你存儲系統的集合。
分片的意思是，沒有任何一臺機器可以處理所有寫請求，也沒有任何一臺機器可以處理對所有數據的讀請求。很多NoSQL系統都是基于鍵值模型的，因此 其查詢條件也基本上是基于鍵值的查詢，基本不會有對整個數據進行查詢的時候。由于基本上所有的查詢操作都是基本鍵值形式的，因此分片通常也基于數據的鍵來 做：鍵的一些屬性會決定這個鍵值對存儲在哪臺機器上。下面我們將會對hash分片和范圍分片兩種分片方式進行描述。
13.4.1 如非必要，請勿分片
分片會導致系統復雜程序大增，所以，如果沒有必要，請不要使用分片。下面我們先講兩種不用分片就能讓系統具有擴展性的方法。
讀寫分離
大多數應用場景都是讀多寫少的場景。所以在這種情況下，可以用一個簡單的方法來分擔負載，就是把數據同步到多臺機器上。這時候寫請求還是由master機器處理，而讀請求則可以分擔給那些同步到數據的機器了。而同步數據的操作，通常是不會對master帶來多大的壓力的。
如果你已經使用了主從配置，將數據同步到多臺機器以提供高可靠性了，那么你的slave機器應該能夠為master分擔不少壓力了。對有些實時性要 求不是非常高的查詢請求，比如一些統計操作，你完全可以放到slave上來執行。通常來說，你的應用對實時性要求越低，你的slave機器就能承擔越多的 任務。
使用緩存
將一些經常訪問的數據放到緩存層中，通常會帶來很好的效果。Memcached 主要的作用就是將數據層的數據進行分布式的緩存。Memcached 通過客戶端的算法（譯者： 常見的一致性hash算法）來實現橫向擴展，這樣當你想增大你緩存池的大小時，只需要添加一臺新的緩存機器即可。
由于Memcached僅僅是一個緩存存儲，它并不具備一些持久存儲的復雜特性。當你在考慮使用復雜的擴展方案時，希望你先考慮一下使用緩存來解決你的負載問題。注意，緩存并不是臨時的處理方案：Facebook 就部署了總容量達到幾十TB的Memcahced內存池。
通過讀寫分離和構建有效的緩存層，通常可以大大分擔系統的讀負載，但是當你的寫請求越來越頻繁的時候，你的master機器還是會承受越來越大的壓力。對于這種情況，我們可能就要用到下面說到的數據分片技術了。
13.4.2 通過協調器進行數據分片
由于CouchDB專注于單機性能，沒有提供類似的橫向擴展方案，于是出現了兩個項目：Lounge 和 BigCouch，他們通過提供一個proxy層來對CouchDB中的數據進行分片。在這種架構中，proxy作為CouchDB集群的前端機器，接受 和分配請求到后端的多臺CouchDB上。后端的CouchDB 之間并沒有交互。協調器會將按操作的key值將請求分配到下層的具體某臺機器。
Twitter 自己實現了一個叫Gizzard的協調器，可以實現數據分片和備份功能。Gizzard不關心數據類型，它使用樹結構來存儲數據范圍標識，你可以用它來對 SQL或者NoSQL系統進行封裝。通過對 Gizzard 進行配置，可以實現將特定范圍內的數據進行冗余存儲，以提高系統的容災能力。
13.4.3 一致性hash環算法
好的hash算法可以使數據保持比較均勻的分布。這使得我們可以按這種分布將數據保存布多臺機器上。一致性hash是一種被廣泛應用的技術，其最早 在一個叫distributed hash tables (DHTs)的系統中進行使用。那些類Dynamo的應用，比如Cassandra、Voldemort和Riak，基本上都使用了一致性hash算法。
Hash環圖
一致性hash算法的工作原理如下：首先我們有一個hash函數H，可以通過數據的key值計算出一個數字型的hash值。然后我們將整個hash 環的范圍定義為［1，L］這個區間，我們將剛才算出的hash值對L進行取余，就能算出一個key值在這個環上的位置。而每一臺真實服務器結點就會負責 ［1-L］之間的某個區間的數據。如上圖，就是一個五個結點的hash環。
上面hash環的L值為1000，然后我們對ABCDE 5個點分別進行hash運算，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之間的所有數據，我們都讓它保存在A節點上。在實際動作中，我們對數據進行hash，算出其應該在哪個節點存儲即可， 例：H(‘employee30′) mod L = 899 那么它應該在E節點上，H(‘employee31′) mod L = 234 那么這個數據應該在B節點上。
備份數據
一致性hash下的數據備份通常采用下面的方法：將數據冗余的存在其歸屬的節點的順序往下的節點，例如你的冗余系數為3（即數據會在不同節點中保存 三份），那么如果通過hash計算你的數據在A區間［7，233］，你的數據會被同時保存在A，B，C三個節點上。這樣如果A節點出現故障，那么B，C節 點就能處理這部分數據的請求了。而某些設計會使E節點將自己的范圍擴大到A233，以接受對出故障的A節點的請求。
優化的數據分配策略
雖然hash算法能夠產生相對均勻的hash值。而且通常是節點數量越多，hash算法會越平均的分配key值。然而通常在項目初期不會有太多的數 據，當然也不需要那么多的機器節點，這時候就會造成數據分配不平均的問題。比如上面的5個節點，其中A節點需要負責的hash區間范圍大小為227，而E 節點負責的區間范圍為132。同時在這種情況下，出故障后數據請求轉移到相鄰節點的策略也可能不好實施了。
為了解決由于節點比較少導致數據分配不均的問題，很多DHT系統都實現了一種叫做虛擬節點的技術。例如4個虛擬節點的系統中，A節點可能被虛擬化成 A_1，A_2，A_3，A_4這四個虛擬節點，然后對這四個虛擬節點再進行hash運算，A節點負責的key值區間就比較分散了。Voldemort 使用了與上面類似的策略，它允許對虛擬節點數進行配置，通常這個節點數會大于真實節點數，這樣每個真實節點實際上是負責了N個虛擬節點上的數據。
Cassandra 并沒有使用虛擬節點到真實節點映射的方法。這導致它的數據分配是不均勻的。為了解決這種不平衡，Cassandra 利用一個異步的進程根據各節點的歷史負載情況來調節數據的分布。
13.4.4 連續范圍分區
使用連續范圍分區的方法進行數據分片，需要我們保存一份映射關系表，標明哪一段key值對應存在哪臺機器上。和一致性hash類似，連續范圍分區會 把key值按連續的范圍分段，每段數據會被指定保存在某個節點上，然后會被冗余備份到其它的節點。和一致性hash不同的是，連續范圍分區使得key值上 相鄰的兩個數據在存儲上也基本上是在同一個數據段。這樣數據路由表只需記錄某段數據的開始和結束點［start，end］就可以了。
通過動態調整數據段到機器結點的映射關系，可以更精確的平衡各節點機器負載。如果某個區段的數據負載比較大，那么負載控制器就可以通過縮短其所在節 點負責的數據段，或者直接減少其負責的數據分片數目。通過添加這樣一個監控和路由模塊，使我們能夠更好的對數據節點進行負載均衡。
BigTable的處理方式
Google BigTable 論文中描述了一種范圍分區方式，它將數據切分成一個個的tablet數據塊。每個tablet保存一定數量的鍵值對。然后每個Tablet 服務器會存儲多個tablet塊，具體每個Tablet服務器保存的tablet數據塊數，則是由服務器壓力來決定的。
每個tablet大概100-200MB大。如果tablet的尺寸變小，那么兩個tablet可能會合并成一個tablet，同樣的如果一個 tablet過大，它也會被分裂成兩個tablet，以保持每個tablet的大小在一定范圍內。在整個系統中有一個master機器，會根據 tablet的大小、負載情況以及機器的負載能力等因素動態地調整tablet在各個機器上的分布。
master服務器會把 tablet 的歸屬關系存在元數據表里。當數據量非常大時，這個元數據表實際也會變得非常大，所以歸屬關系表實際上也是被切分成一個個的tablet保存在tablet服務器中的。這樣整個數據存儲就被分成了如上圖的三層模型。下面我們解釋一下上面圖中的例子。當某個客戶端要從BigTable系統中獲取key值為900的數據時，首先他會到第一級元數據服務器 A（METADATA0）去查詢，第一級元數據服務器查詢自己的元數據表，500-1500這個區間中的所有元數據都存在B服務器中，于是會返回客戶端說 去B服務器查詢，客戶端再到B服務器中進行查詢，B服務器判斷到850-950這個區間中的數據都存在tablet服務器C中，于是會告知客戶端到具體的 tablet服務器C去查詢。然后客戶端再發起一次向C服務器的請求，就能獲取到900對應的數據了。然后，客戶端會把這個查詢結果進行緩存，以避免對元 數據服務器的頻繁請求。在這樣的三層架構下，只需要128MB的元數據存儲，就能定位234 個tablet數據塊了（按128MB一個數據塊算，是261bytes的數據）。
故障處理
在BigTable中，master機器是一個故障單點，不過系統可以容忍短時間的master故障。另一方面，如果tablet 服務器故障，那么master可以把對其上tablet的所有請求分配到其它機器節點。
為了監測和處理節點故障，BigTable實現了一個叫Chubby的模塊，Chubby是一個分布式的鎖系統，用于管理集群成員及檢測各成員是否 存活。ZooKeeper是Chubby的一個開源實現，有很多基于 Hadoop 的項目都使用它來進行二級master和tablet節點的調度。
基于范圍分區的NoSQL項目
HBase 借鑒了BigTable的分層理論來實現范圍分區策略。tablet相關的數據存在HDFS里。HDFS 會處理數據的冗余備份，并負責保證各備份的一致性。而像處理數據請求，修改存儲結構或者執行tablet的分裂和合并這種事，是具體的tablet服務器 來負責的。
MongoDB也用了類似于BigTable的方案來實現范圍分區。他用幾臺配置機器組成集群來管理數據在節點上的分布。這幾臺機器保存著一樣的配 置信息，他們采用 two-phase commit 協議來保證數據的一致性。這些配置節點實際上同時扮演了BigTable中的master的路由角色，及Chubby 的高可用性調度器的角色。而MongoDB具體的數據存儲節點是通過其Replica Sets方案來實現數據冗余備份的。
Cassandra 提供了一個有序的分區表，使你可以快速對數據進行范圍查詢。Cassandra也使用了一致性hash算法進行數據分配，但是不同的是，它不是直接按單條 數據進行hash，而是對一段范圍內的數據進行hash，也就是說20號數據和21號數據基本上會被分配在同一臺機器節點上。
Twitter的Gizzard框架也是通過使用范圍分區來管理數據在多個節點間的備份與分配。路由服務器可以部署成多層，任何一層只負責對key 值進行按范圍的分配到下層的不同節點。也就是說路由服務器的下層既可以是真實的數據存儲節點，也可能是下層的路由節點。Gizzard的數據備份機制是通 過將寫操作在多臺機器上執行多次來實現的。Gizzard的路由節點處理失敗的寫操作的方式和其它NoSQL不太一樣，他要求所有更新都是冪等的（意思是 可以重復執行而不會出錯）。于是當一個節點故障后，其上層的路由節點會把當前的寫操作cache起來并且重復地讓這個節點執行，直到其恢復正常。
13.4.5 選擇哪種分區策略
上面我們說到了Hash分區和范圍分區兩種策略，哪種更好呢？這要看情況了，如果你需要經常做范圍查詢，需要按順序對key值進行操作，那么你選擇范圍分區會比較好。因為如果選擇hash分區的話，要查詢一個范圍的數據可能就需要跨好幾個節點來進行了。
那如果我不會進行范圍查詢或者順序查詢呢？這時候hash分區相對來說可能更方便一點，而且hash分區時可能通過虛擬結點的設置來解決hash不 均的問題。在hash分區中，基本上只要在客戶端執行相應的hash函數就能知道對應的數據存在哪個節點上了。而如果考慮到節點故障后的數據轉移情況，可 能獲取到數據存放節點就會麻煩一些了。
范圍分區要求在查詢數據前對配置節點還要進行一次查詢，如果沒有特別好的高可用容災方案，配置節點將會是一個危險的故障單點。當然，你可以把配置節 點再進行一層負載均衡來減輕負載。而范圍分區時如果某個節點故障了，它上面的數據可以被分配到多個節點上，而不像在一致性hash時，只能遷移到其順序的 后一個節點，造成下一個節點的負載飆升。
13.5 一致性
上面我們講到了通過將數據冗余存儲到不同的節點來保證數據安全和減輕負載，下面我們來看看這樣做引發的一個問題：保證數據在多個節點間的一致性是非 常困難的。在實際應用中我們會遇到很多困難，同步節點可能會故障，甚至會無法恢復，網絡可能會有延遲或者丟包，網絡原因導致集群中的機器被分隔成兩個不能 互通的子域等等。在NoSQL中，通常有兩個層次的一致性：第一種是強一致性，既集群中的所有機器狀態同步保持一致。第二種是最終一致性，既可以允許短暫 的數據不一致，但數據最終會保持一致。我們先來講一下，在分布式集群中，為什么最終一致性通常是更合理的選擇，然后再來討論兩種一致性的具體實現結節。
13.5.1 關于CAP理論
為什么我們會考慮削弱數據的一致性呢？其實這背后有一個關于分布式系統的理論依據。這個理論最早被 Eric Brewer 提出，稱為CAP理論，爾后Gilbert 和 Lynch 對CAP進行了理論證明。這一理論首先把分布式系統中的三個特性進行了如下歸納：
- 一致性（C）：在分布式系統中的所有數據備份，在同一時刻是否同樣的值。
- 可用性（A）：在集群中一部分節點故障后，集群整體是否還能響應客戶端的讀寫請求。
- 分區容忍性（P）：集群中的某些節點在無法聯系后，集群整體是否還能繼續進行服務。
而CAP理論就是說在分布式存儲系統中，最多只能實現上面的兩點。而由于當前的網絡硬件肯定會出現延遲丟包等問題，所以分區容忍性是我們必須需要實現的。所以我們只能在一致性和可用性之間進行權衡，沒有NoSQL系統能同時保證這三點。
要保證數據一致性，最簡單的方法是令寫操作在所有數據節點上都執行成功才能返回成功。而這時如果某個結點出現故障，那么寫操作就成功不了了，需要一直等到這個節點恢復。也就是說，如果要保證強一致性，那么就無法提供7×24的高可用性。
而要保證可用性的話，就意味著節點在響應請求時，不用完全考慮整個集群中的數據是否一致。只需要以自己當前的狀態進行請求響應。由于并不保證寫操作在所有節點都寫成功，這可能會導致各個節點的數據狀態不一致。
CAP理論導致了最終一致性和強一致性兩種選擇。當然，事實上還有其它的選擇，比如在Yahoo! 的PNUTS中，采用的就是松散的一致性和弱可用性結合的方法。但是我們討論的NoSQL系統沒有類似的實現，所以我們在后續不會對其進行討論。
13.5.2 強一致性
強一致性的保證，要求所有數據節點對同一個key值在同一時刻有同樣的value值。雖然實際上可能某些節點存儲的值是不一樣的，但是作為一個整 體，當客戶端發起對某個key的數據請求時，整個集群對這個key對應的數據會達成一致。下面就舉例說明這種一致性是如何實現的。
假設在我們的集群中，一個數據會被備份到N個結點。這N個節點中的某一個可能會扮演協調器的作用。它會保證每一個數據寫操作會在成功同步到W個節點 后才向客戶端返回成功。而當客戶端讀取數據時，需要至少R個節點返回同樣的數據才能返回讀操作成功。而NWR之間必須要滿足下面關系：R＋W>N
下面舉個實在的例子。比如我們設定N＝3（數據會備份到A、B、C三個結點）。比如值 employee30:salary 當前的值是20000，我們想將其修改為30000。我們設定W＝2，下面我們會對A、B、C三個節點發起寫操作（employee30:salary, 30000），當A、B兩個節點返回寫成功后，協調器就會返回給客戶端說寫成功了。至于節點C，我們可以假設它從來沒有收到這個寫請求，他保存的依然是 20000那個值。之后，當一個協調器執行一個對employee30:salary的讀操作時，他還是會發三個請求給A、B、C三個節點：
- 如果設定R＝1，那么當C節點先返回了20000這個值時，那我們客戶端實際得到了一個錯誤的值。
- 如果設定R＝2，則當協調器收到20000和30000兩個值時，它會發現數據不太正確，并且會在收到第三個節點的30000的值后判斷20000這個值是錯誤的。
所以如果要保證強一致性，在上面的應用場景中，我們需要設定R＝2，W＝2
如果寫操作不能收到W個節點的成功返回，或者寫操作不能得到R個一致的結果。那么協調器可能會在某個設定的過期時間之后向客戶端返回操作失敗，或者是等到系統慢慢調整到一致。這可能就導致系統暫時處于不可用狀態。
對于R和W的不同設定，會導致系統在進行不同操作時需要不同數量的機器節點可用。比如你設定在所有備份節點上都寫入才算寫成功，既W＝N，那么只要 有一個備份節點故障，寫操作就失敗了。一般設定是R＋W = N+1，這是保證強一致性的最小設定了。一些強一致性的系統設定W＝N，R＝1，這樣就根本不用考慮各個節點數據可能不一致的情況了。
HBase是借助其底層的HDFS來實現其數據冗余備份的。HDFS采用的就是強一致性保證。在數據沒有完全同步到N個節點前，寫操作是不會返回成 功的。也就是說它的W＝N，而讀操作只需要讀到一個值即可，也就是說它R＝1。為了不至于讓寫操作太慢，對多個節點的寫操作是并發異步進行的。在直到所有 的節點都收到了新的數據后，會自動執行一個swap操作將新數據寫入。這個操作是原子性和一致性的。保證了數據在所有節點有一致的值。
13.5.3 最終一致性
像Voldemort，Cassandra和Riak這些類Dynamo的系統，通常都允許用戶按需要設置N，R，W三個值，即使是設置成 W＋R<= N也是可以的。也就是說他允許用戶在強一致性和最終一致性之間自由選擇。而在用戶選擇了最終一致性，或者是W<N的強一致性時，則總會出現一段各個 節點數據不同步導致系統處理不一致的時間。為了提供最終一致性的支持，這些系統會提供一些工具來使數據更新被最終同步到所有相關節點。
下面我們會先講一講如何判斷數據是最新的還是陳舊的，然后我們再討論一下如何進行數據同步，最后我們再列舉一些Dynamo里使用的加速同步過程的巧妙方法。
版本控制與沖突
由于同一份數據在不同的節點可能存在不同值，對數據的版本控制和沖突監測就變得尤為重要。類Dynamo的系統通常都使用了一種叫vector clock（向量時鐘）的版本控制機制。一個vector clock可以理解成是一個向量，它包含了這個值在每一個備份節點中修改的次數。比如說有的數據會備份到A，B，C三個節點，那么這些值的vector clock值就是類似（NA，NB，NC），而其初始值為（0，0，0）。
每次一個key的值被修改，其vector clock相應的值就會加1。比如有一個key值當前的vector clock值為（39，1，5），然后他在B節點被修改了一次，那么它的cector clock值就會相應的變成（39，2，5）。而當另一個節點C在收到B節點的同步請求時，他會先用自己保存的vector clock值與B傳來的vector clock值進行對比，如果自己的vector clock值的每一項都小于等于B傳來的這個值，那么說明這次的修改值是在自已保存的值上的修改，不會有沖突，直接進行相應的修改，并把自己的 vector clock值更新。但是如果C發現自己的vector clock有些項比B大，而某些項比B小，比如B的是（39，2，5）C的是（39，1，6），那么這時候說明B的這次修改并不是在C的基礎上改的，數據 出現沖突了。
沖突解決
不同的系統有不同的沖突解決策略。Dynamo選擇把沖突留給應用層來解決。如果是兩個節點保存的購物車信息沖突了，可以選擇簡單的通過把兩個數據 合并進行解決。但如果是對同一份文檔進行的修改沖突了，可能就需要人工來解決沖突了（譯者：像我們在SVN中做的一樣）。Voldemort就是采用的后 者，它在發現沖突后，會把有沖突的幾份數據一起返回給應用層，把沖突解決留給應用層來做。
Cassandra通過為每一個操作保存一個時間戳的方法來解決沖突，在沖突的幾個版本里，最后修改的一個會獲勝成為新的值。相對于上面的方式，它 減少了通過應用層解決沖突時需要的網絡訪問，同時也簡化了客戶端的操作API。但這種策略并不適合用來處理一些需要合并沖突的場合，比如上面的購物車的例 子，或者是分布式的計數器這樣的應用。而Riak把Voldemort和 Cassandra 的策略都實現了。CouchDB會把沖突的key進行標識，以便應用層可以主動進行人工修復，在修復完成前，客戶端的請求是無法得到確定值的。
讀時修復
在數據讀取時，如果有R個節點返回了一致的數據，那么協調器就可以認為這個值是正確的并返回給客戶端了。但是在總共返回的N個值中，如果協調器發現 有的數據不是最新的。那么它可以通過讀時修復機制來對這些節點進行處理。這種方式在Dynamo中有描述，在Voldemort 、 Cassandra和Riak中都得到了實現。當協調器發現有的節點數據不是最新時，它會在數據不一致的節點間啟動一個沖突解決過程。這樣主動的修復策略 并不會有多大的工作量。因為讀取操作時，各個節點都已經把數據返回給協調器了，所以解決沖突越快，實際上可能造成的后續的不一致的可能性也就越小。
Hinted Handoff
Cassandra、Riak和Voldemort都實現了一種叫Hinted Handoff的技術，用來保證在有節點故障后系統的寫操作不受太大影響。它的過程是如果負責某個key值的某個節點宕機了，另一個節點會被選擇作為其臨 時切換點，以臨時保存在故障節點上面的寫操作。這些寫操作被單獨保存起來，直到故障節點恢復正常，臨時節點會把這些寫操作重新遷移給剛剛恢復的節點。 Dynamo 論文中提到一種叫“sloppy quorum”的方法，它會把通過 Hinted Handoff 寫成功的臨時節點也計算在成功寫入數中。但是Cassandra和Voldemort并不會將臨時節點也算在寫入成功節點數內，如果寫入操作并沒有成功寫 在W個正式節點中，它們會返回寫入失敗。當然，Hinted Handoff 策略在這些系統中也有使用，不過只是用在加速節點恢復上。
Anti-Entropy
如果一個節點故障時間太長，或者是其 Hinted Handoff 臨時替代節點也故障了，那么新恢復的節點就需要從其它節點中同步數據了。（譯者：實際上就是要找出經過這段時間造成的數據差異，并將差異部分同步過來）。 這種情況下Cassandra和Riak都實現了在Dynamo文檔中提到的一種方法，叫做anti-entropy。在anti-entropy過程 中，節點間通過交換Merkle Tree來找出那些不一致的部分。Merkle Tree是一個分層的hash校驗機制：如果包含某個key值范圍的hash值在兩個數據集中不相同，那么不同點就在這個key值范圍，同理，如果頂層的 hash值相同，那么其負責的所有key值范圍內的值都認為是相同的。這種方法的好處是，在節點恢復時，不用把所有的值都傳一遍來檢查哪些值是有變化的。 只需要傳幾個hash值就能找到不一致的數據，重傳這個數據即可。
Gossip
當一個分布式系統越來越大，就很難搞清集群中的每個節點的狀態了。上面說到的類Dynamo 應用都采用了Dynamo文檔中說到的一種古老的方法：Gossip。通過這個方法，節點間能夠互相保持聯系并能夠檢測到故障節點。其具體做法是，每隔一 段時間（比如一秒），一個節點就會隨便找一個曾經有過通信的節點與其交換一下其它節點的健康狀態。通過這種方式，節點能夠比較快速的了解到集群中哪些節點 故障了，從而把這些節點負責的數據分配到其它節點去。（譯者：Gossip其實是仿生學的設計，Gossip意思為流言，節點傳播其它節點的健康信息，就 像一個小村鎮里的無聊婦人們互相說別人的閑話一樣，基本上誰家誰人出什么事了，都能比較快地被所有人知道）。
13.6 寫在最后的話
目前NoSQL系統來處在它的萌芽期，我們上面討論到的很多NoSQL系統，他們的架構、設計和接口可能都會改變。本章的目的，不在于讓你了解這些 NoSQL系統目前是如何工作的，而在于讓你理解這些系統之所以這樣實現的原因。NoSQL系統把更多的設計工作留給了應用開發工作者來做。理解上面這些 組件的架構，不僅能讓您寫出下一個NoSQL系統，更讓您對現有系統應用得更好。
13.7 致謝
非常感謝Jackie Carter, Mihir Kedia，以及所有對本章進行校對并且提出寶貴意見的人。沒有這些年來NoSQL社區的專注工作，也不會有這一章內容的誕生。各位加油。
相關信息
原文: http://www./en/nosql.html
原作者：Adam Marcus
譯者：iammutex
組織：NoSQLFan
翻譯時間：2011年6月
