1. 序
2. 思想篇
   1. CAP
   2. 最終一致性
      1. 變體
   3. BASE
   4. 其他
      1. I/O的五分鐘法則
      2. 不要刪除資料
      3. RAM是硬盤,硬盤是磁帶
      4. Amdahl定律和Gustafson定律
      5. 萬兆以太網
3. 手段篇
   1. 一致性哈希
      1.  
         1. 亞馬遜的現狀
         2. 算法的選擇
   2. Quorum NRW
   3. Vector clock
   4. Virtual node
   5. gossip
      1. Gossip (State Transfer Model)
      2. Gossip (Operation Transfer Model)
   6. Merkle tree
   7. Paxos
      1. 背景
   8. DHT
   9. Map Reduce Execution
   10. Handling Deletes
   11. 存儲實現
   12. 節點變化
   13. 列存
       1. 描述
       2. 特點
4. 軟件篇
   1. 亞資料庫
      1. MemCached
         1. 特點
         2. 內存分配
         3. 緩存策略
         4. 緩存資料庫查詢
         5. 資料冗餘與故障預防
         6. Memcached客戶端（mc）
         7. 緩存式的Web應用程序架構
         8. 性能測試
      2. dbcached
         1. Memcached 和 dbcached 在功能上一樣嗎?
   2. 列存系列
      1. Hadoop之Hbase
      2. 耶魯大學之HadoopDB
      3. GreenPlum
      4. FaceBook之Cassandra
         1. Cassandra特點
         2. Keyspace
         3. Column family（CF）
         4. Key
         5. Column
         6. Super column
         7. Sorting
         8. 存儲
         9. API
      5. Google之BigTable
      6. Yahoo之PNUTS
         1. 特點
         2. PNUTS實現
            1. Record-level mastering 記錄級別主節點
            2. PNUTS的結構
            3. Tablets尋址與切分
            4. Write調用示意圖
         3. PNUTS感悟
      7. 微軟之SQL資料服務
   3. 非雲服務競爭者
   4. 文檔存儲
      1. CouchDB
         1. 特性
      2. Riak
      3. MongoDB
      4. Terrastore
      5. ThruDB
   5. Key Value / Tuple 存儲
      1. Amazon之SimpleDB
      2. Chordless
      3. Redis
      4. Scalaris
      5. Tokyo cabinet / Tyrant
      6. CT.M
      7. Scalien
      8. Berkley DB
      9. MemcacheDB
      10. Mnesia
      11. LightCloud
      12. HamsterDB
      13. Flare
   6. 最終一致性Key Value存儲
      1. Amazon之Dynamo
         1. 功能特色
         2. 架構特色
      2. BeansDB
         1. 簡介
         2. 更新
         3. 特性
         4. 性能
      3. Nuclear
         1. 兩個設計上的Tips
      4. Voldemort
      5. Dynomite
      6. Kai
   7. 未分類
      1. Skynet
      2. Drizzle
   8. 比較
      1. 可擴展性
      2. 資料和查詢模型
      3. 持久化設計
5. 應用篇
   1. eBay 架構經驗
   2. 淘寶架構經驗
   3. Flickr架構經驗
   4. Twitter運維經驗
      1. 運維經驗
         1. Metrics
         2. 配置管理
         3. Darkmode
         4. 進程管理
         5. 硬件
      2. 代碼協同經驗
         1. Review制度
         2. 部署管理
         3. 團隊溝通
      3. Cache
   5. 雲計算架構
   6. 反模式
      1. 單點失敗（Single Point of Failure）
      2. 同步調用
      3. 不具備回滾能力
      4. 不記錄日誌
      5. 無切分的資料庫
      6. 無切分的應用
      7. 將伸縮性依賴於第三方廠商
   7. OLAP
      1. OLAP報表產品最大的難點在哪裡？
   8. NOSQL們背後的共有原則
      1. 假設失效是必然發生的
      2. 對資料進行分區
      3. 保存同一資料的多個副本
      4. 動態伸縮
      5. 查詢支持
      6. 使用 Map/Reduce 處理匯聚
      7. 基於磁盤的和內存中的實現
      8. 僅僅是炒作?
6. 附
   1. 感謝
   2. 版本志
   3. 引用

 序

日前國內沒有一套比較完整的NoSQL資料庫資料，有很多先驅整理髮表了很多，但不是很系統。不材嘗試著將各家的資料整合一下，並書寫了一些自己的見解。
本書寫了一些目前的NoSql的一些主要技術，算法和思想。同時列舉了大量的現有的資料庫實例。讀完全篇，相信讀者會對NoSQL資料庫瞭解個大概。
另外我還準備開發一個開源內存資料庫galaxydb.本書也是為這個資料庫提供一些架構資料。

 思想篇

 CAP

• C: Consistency 一致性
• A: Availability 可用性(指的是快速獲取資料)
• P: Tolerance of network Partition 分區容忍性(分佈式)

 最終一致性

• 存儲系統

存儲系統可以理解為一個黑盒子，它為我們提供了可用性和持久性的保證。

• Process A

ProcessA主要實現從存儲系統write和read操作

• Process B 和ProcessC 

ProcessB和C是獨立於A，並且B和C也相互獨立的，它們同時也實現對存儲系統的write和read操作。

下面以上面的場景來描述下不同程度的一致性：

• 強一致性

強一致性（即時一致性） 假如A先寫入了一個值到存儲系統，存儲系統保證後續A,B,C的讀取操作都將返回最新值

• 弱一致性

假如A先寫入了一個值到存儲系統，存儲系統不能保證後續A,B,C的讀取操作能讀取到最新值。此種情況下有一個“不一致性窗口”的概念，它特指從A寫入值，到後續操作A,B,C讀取到最新值這一段時間。

• 最終一致性

最終一致性是弱一致性的一種特例。假如A首先write了一個值到存儲系統，存儲系統保證如果在A,B,C後續讀取之前沒有其它寫操作更新同樣的值的話，最終所有的讀取操作都會讀取到最A寫入的最新值。此種情況下，如果沒有失敗發生的話，“不一致性窗口”的大小依賴於以下的幾個因素：交互延遲，系統的負載，以及複製技術中replica的個數（這個可以理解為master/salve模式中，salve的個數），最終一致性方面最出名的系統可以說是DNS系統，當更新一個域名的IP以後，根據配置策略以及緩存控制策略的不同，最終所有的客戶都會看到最新的值。

 變體

• Causal consistency（因果一致性）

如果Process A通知Process B它已經更新了資料，那麼Process B的後續讀取操作則讀取A寫入的最新值，而與A沒有因果關係的C則可以最終一致性。

• Read-your-writes consistency

如果Process A寫入了最新的值，那麼Process A的後續操作都會讀取到最新值。但是其它用戶可能要過一會才可以看到。

• Session consistency

此種一致性要求客戶端和存儲系統交互的整個會話階段保證Read-your-writes consistency.Hibernate的session提供的一致性保證就屬於此種一致性。

• Monotonic read consistency

此種一致性要求如果Process A已經讀取了對象的某個值，那麼後續操作將不會讀取到更早的值。

• Monotonic write consistency

此種一致性保證系統會序列化執行一個Process中的所有寫操作。

 BASE

說起來很有趣，BASE的英文意義是鹼，而ACID是酸。真的是水火不容啊。

• Basically Availble --基本可用
• Soft-state --軟狀態/柔性事務

"Soft state" 可以理解為"無連接"的, 而 "Hard state" 是"面向連接"的

•  
• Eventual Consistency --最終一致性

最終一致性， 也是是 ACID 的最終目的。

BASE模型反ACID模型，完全不同ACID模型，犧牲高一致性，獲得可用性或可靠性： Basically Available基本可用。支持分區失敗(e.g. sharding碎片劃分資料庫) Soft state軟狀態 狀態可以有一段時間不同步，異步。 Eventually consistent最終一致，最終資料是一致的就可以了，而不是時時一致。

BASE思想的主要實現有
1.按功能劃分資料庫
2.sharding碎片 

BASE思想主要強調基本的可用性，如果你需要高可用性，也就是純粹的高性能，那麼就要以一致性或容錯性為犧牲，BASE思想的方案在性能上還是有潛力可挖的。

 其他

 I/O的五分鐘法則

在 1987 年，Jim Gray 與 Gianfranco Putzolu 發表了這個"五分鐘法則"的觀點，簡而言之，如果一條記錄頻繁被訪問，就應該放到內存裡，否則的話就應該待在硬盤上按需要再訪問。這個臨界點就是五分鐘。 看上去像一條經驗性的法則，實際上五分鐘的評估標準是根據投入成本判斷的，根據當時的硬件發展水準，在內存中保持 1KB 的資料成本相當於硬盤中存據 400 秒的開銷(接近五分鐘)。這個法則在 1997 年左右的時候進行過一次回顧，證實了五分鐘法則依然有效（硬盤、內存實際上沒有質的飛躍)，而這次的回顧則是針對 SSD 這個"新的舊硬件"可能帶來的影響。

隨著閃存時代的來臨，五分鐘法則一分為二：是把 SSD 當成較慢的內存（extended buffer pool ）使用還是當成較快的硬盤（extended disk）使用。小內存頁在內存和閃存之間的移動對比大內存頁在閃存和磁盤之間的移動。在這個法則首次提出的 20 年之後，在閃存時代，5 分鐘法則依然有效，只不過適合更大的內存頁(適合 64KB 的頁，這個頁大小的變化恰恰體現了計算機硬件工藝的發展，以及帶寬、延時)。

 不要刪除資料

Oren Eini（又名Ayende Rahien）建議開發者儘量避免資料庫的軟刪除操作，讀者可能因此認為硬刪除是合理的選擇。作為對Ayende文章的回應，Udi Dahan強烈建議完全避免資料刪除。

所謂軟刪除主張在表中增加一個IsDeleted列以保持資料完整。如果某一行設置了IsDeleted標誌列，那麼這一行就被認為是已刪除的。Ayende覺得這種方法“簡單、容易理解、容易實現、容易溝通”，但“往往是錯的”。問題在於：

刪除一行或一個實體幾乎總不是簡單的事件。它不僅影響模型中的資料，還會影響模型的外觀。所以我們才要有外鍵去確保不會出現“訂單行”沒有對應的父“訂單”的情況。而這個例子只能算是最簡單的情況。……

當採用軟刪除的時候，不管我們是否情願，都很容易出現資料受損，比如誰都不在意的一個小調整，就可能使“客戶”的“最新訂單”指向一條已經軟刪除的訂單。

如果開發者接到的要求就是從資料庫中刪除資料，要是不建議用軟刪除，那就只能硬刪除了。為了保證資料一致性，開發者除了刪除直接有關的資料行，還應該級聯地刪除相關資料。可Udi Dahan提醒讀者注意，真實的世界並不是級聯的：

假設市場部決定從商品目錄中刪除一樣商品，那是不是說所有包含了該商品的舊訂單都要一併消失？再級聯下去，這些訂單對應的所有發票是不是也該刪除？這麼一步步刪下去，我們公司的損益報表是不是應該重做了？

沒天理了。

問題似乎出在對“刪除”這詞的解讀上。Dahan給出了這樣的例子：

我說的“刪除”其實是指這產品“停售”了。我們以後不再賣這種產品，清掉庫存以後不再進貨。以後顧客搜索商品或者翻閱目錄的時候不會再看見這種商品，但管倉庫的人暫時還得繼續管理它們。“刪除”是個貪方便的說法。

他接著舉了一些站在用戶角度的正確解讀：


訂單不是被刪除的，是被“取消”的。訂單取消得太晚，還會產生花費。

員工不是被刪除的，是被“解僱”的（也可能是退休了）。還有相應的補償金要處理。

職位不是被刪除的，是被“填補”的（或者招聘申請被撤回）。

在上面這些例子中，我們的著眼點應該放在用戶希望完成的任務上，而非發生在某個
實體身上的技術動作。幾乎在所有的情況下，需要考慮的實體總不止一個。

為了代替IsDeleted標誌，Dahan建議用一個代表相關資料狀態的字段：有效、停用、取消、棄置等等。用戶可以借助這樣一個狀態字段回顧過去的資料，作為決策的依據。

刪除資料除了破壞資料一致性，還有其它負面的後果。Dahan建議把所有資料都留在資料庫裡：“別刪除。就是別
刪除。”

 RAM是硬盤,硬盤是磁帶

Jim Gray在過去40年中對技術發展有過巨大的貢獻，“內存是新的硬盤，硬盤是新的磁帶”是他的名言。“實時”Web應用不斷湧現，達到海量規模的系統越來越多，這種後浪推前浪的發展模式對軟硬件又有何影響？

Tim Bray早在網格計算成為熱門話題之前，就討論過以RAM和網絡為中心的硬件結構的優勢，可以用這種硬件建立比磁盤集群速度更快的RAM集群。

對於資料的隨機訪問，內存的速度比硬盤高幾個數量級（即使是最高端的磁盤存儲系統也只是勉強達到1,000次尋道/秒）。其次， 隨著資料中心的網絡速度提高，訪問內存的成本更進一步降低。通過網絡訪問另一台機器的內存比訪問磁盤成本更低。就在我寫下這段話的時候，Sun的 Infiniband產品線中有一款具備9個全互聯非阻塞端口交換機，每個端口的速度可以達到30Gbit/sec！Voltaire產品的端口甚至更多；簡直不敢想像。（如果你想瞭解這類超高性能網絡的最新進展，請關注Andreas Bechtolsheim在Standford開設的課程。）

各種操作的時間，以2001年夏季，典型配置的 1GHz 個人計算機為標準：

執行單一指令	1 納秒
從L1 高速緩存取一個字	2 納秒
從內存取一個字	10 納秒
從磁盤取連續存放的一個字	200 納秒
磁盤尋址並取字	8 毫秒
以太網	2GB/s

Tim還指出Jim Gray的
名言中後半句所闡述的真理：“對於隨機訪問，硬盤慢得不可忍受；但如果你把硬盤當成磁帶來用，它吞吐連續資料的速率令人震驚；它天生適合用來給以RAM為主的應用做日誌（logging and journaling）。” 

時間閃到幾年之後的今天，我們發現硬件的發展趨勢在RAM和網絡領域勢頭不減，而在硬盤領域則止步不前。Bill McColl提到用於並行計算的海量內存系統已經出現：

內存是新的硬盤！硬盤速度提高緩慢，內存芯片容量指數上升，in-memory軟件架構有望給各類資料密集的應用帶來數量級的性能提升。小型機架服務器（1U、2U）很快就會具備T字節、甚至更大量的內存，這將會改變服務器架構中內存和硬盤之間的平衡。硬盤將成為新的磁帶，像磁帶一樣作為順序存儲介質使用（硬盤的順序訪問相當快速），而不再是隨機存儲介質（非常慢）。這裡面有著大量的機會，新產品的性能有望提高10倍、100倍。

Dare Obsanjo指出如果不把這句真言當回事，會帶來什麼樣的惡劣後果—— 也就是Twitter正面臨的麻煩。論及Twitter的內容管理，Obsanjo說，“如果一個設計只是簡單地反映了問題描述，你去實現它就會落入磁盤 I/O的地獄。不管你用Ruby on Rails、Cobol on Cogs、C++還是手寫彙編都一樣，讀寫負載照樣會害死你。”換言之，應該把隨機操作推給RAM，只給硬盤留下順序操作。 

Tom White是Hadoop Core項目的提交者，也是Hadoop項目管理委員會的成員。他對Gray的真言中“硬盤是新的磁帶”部分作了更深入地探討。White在討論MapReduce編程模型的時候指出，為何對於Hadloop這類工具來說，硬盤仍然是可行的應用程序資料存儲介質：

本質上，在MapReduce的工作方式中，資料流式地讀出和寫入硬盤，MapReduce是以硬盤的傳輸速率不斷地對這些資料進行排序和合併。 與之相比，訪問關係資料庫中的資料，其速率則是硬盤的尋道速率（尋道指移動磁頭到盤面上的指定位置讀取或寫入資料的過程）。為什麼要強調這一點？請看看尋道時間和磁盤傳輸率的發展曲線。尋道時間每年大約提高5%，而資料傳輸率每年大約提高20%。尋道時間的進步比資料傳輸率慢——因此採用由資料傳輸率決定性能的模型是有利的。MapReduce正是如此。

雖然固態硬盤（SSD）能否改變尋道時間/傳輸率的對比還有待觀察，White文章的跟貼中，很多人都認為SSD會成為RAM/硬盤之爭中的平衡因素。 

Nati Shalom對內存和硬盤在資料庫部署和使用中的角色作了一番有理有據的評述。 Shalom著重指出用資料庫集群和分區來解決性能和可伸縮性的侷限。他說，“資料庫複製和資料庫分區都存在相同的基本問題，它們都依賴於文件系統/硬盤 的性能，建立資料庫集群也非常複雜”。他提議的方案是轉向In-Memory Data Grid（IMDG），用Hibernate二級緩存或者GigaSpaces Spring DAO之類的技術作支撐，將持久化作為服務（Persistence as a Service）提供給應用程序。Shalom解釋說，IMDG

提供在內存中的基於對象的資料庫能力，支持核心的資料庫功能，諸如高級索引和查詢、事務語義和鎖。IMDG還從應用程序的代碼中抽象出了資料的拓撲。通過這樣的方式，資料庫不會完全消失，只是挪到了“正確的”位置。

IMDG相比直接RDBMS訪問的優勢列舉如下：

• 位於內存中，速度和並發能力都比文件系統優越得多
• 資料可通過引用訪問
• 直接對內存中的對象執行資料操作
• 減少資料的爭用
• 並行的聚合查詢
• 進程內（In-process）的局部緩存
• 免除了對象-關係映射（ORM）

你是否需要改變對應用和硬件的思維方式，最終取決於你要用它們完成的工作。但似乎公論認為，開發者解決性能和可伸縮性的思路已經到了該變一變的時候。

 Amdahl定律和Gustafson定律

這裡，我們都以S(n)表示n核系統對具體程序的加速比，K表示串行部分計算時間比例。

Amdahl 定律的加速比：S(n) ＝ 使用1個處理器的串行計算時間 / 使用n個處理器的並行計算時間

S(n) = 1/(K+(1-K)/n) = n/(1+(n-1)K)

Gustafson定律的加速比：S(n) ＝ 使用n個處理器的並行計算量 / 使用1個處理器的串行計算量

S(n) = K+(1-K)n

有點冷是不是？

通俗的講，Amdahl 定律將工作量看作1，有n核也只能分擔1-K的工作量；而Gustafson定律則將單核工作量看作1，有n核，就可以增加n(1-K)的工作量。

這裡沒有考慮引進分佈式帶來的開銷，比如網絡和加鎖。成本還是要仔細核算的，不是越分佈越好。

控制算法的複雜性在常數範圍之內。

 萬兆以太網

 

 手段篇

 一致性哈希

考慮到單服務器不能承載，因此使用了分佈式架構，最初的算法為 hash() mod n, hash()通常取用戶ID，n為節點數。此方法容易實現且能夠滿足運營要求。缺點是當單點發生故障時，系統無法自動恢復。

 

 

第二階段
為瞭解決單點故障，使用 hash() mod (n/2), 這樣任意一個用戶都有2個服務器備選，可由client隨機選取。由於不同服務器之間的用戶需要彼此交互，所以所有的服務器需要確切的知道用戶所在的位置。因此用戶位置被保存到memcached中。

當一台發生故障，client可以自動切換到對應backup，由於切換前另外1台沒有用戶的session，因此需要client自行重新登錄。

 

 

這個階段的設計存在以下問題
負載不均衡，尤其是單台發生故障後剩下一台會壓力過大。
不能動態增刪節點
節點發生故障時需要client重新登錄

第三階段
打算去掉硬編碼的hash() mod n 算法，改用一致性哈希(consistent hashing)分佈
假如採用Dynamo中的strategy 1
我們把每台server分成v個虛擬節點，再把所有虛擬節點(n*v)隨機分配到一致性哈希的圓環上，這樣所有的用戶從自己圓環上的位置順時針往下取到第一個vnode就是自己所屬節點。當此節點存在故障時，再順時針取下一個作為替代節點。

 

 

 

優點：發生單點故障時負載會均衡分散到其他所有節點，程序實現也比較優雅。

 

 亞馬遜的現狀

aw2.0公司的Alan Williamson撰寫了一篇報導，主要是關於他在Amazon EC2上的體驗的，他抱怨說，Amazon是公司唯一使用的雲提供商，看起來它在開始時能夠適應得很好，但是有一個臨界點：

在開始的日子裡Amazon的表現非常棒。實例在幾分鐘內啟動，幾乎沒有遇到任何問題，即便是他們的小實例（SMALL INSTANCE）也很健壯，足以支持適當使用的MySQL資料庫。在20個月內，Amazon雲系統一切運轉良好，不需要任何的關心和抱怨。

……

然而，在最後的八個月左右，他們“盔甲”內的漏洞開始呈現出來了。第一個弱點前兆是，新加入的Amazon SMALL實例的性能出現了問題。根據我們的監控，在服務器場中新添加的機器，與原先的那些相比性能有所下降。開始我們認為這是自然出現的怪現象，只是碰 巧發生在“吵鬧的鄰居”（Noisy Neighbors）旁邊。根據隨機法則，一次快速的停機和重新啟動經常就會讓我們回到“安靜的鄰居”旁邊，那樣我們可以達到目的。

……

然而，在最後的一兩個月中，我們發現，甚至是這些“使用高級CPU的中等實例”也遭受了與小實例相同的命運，其中，新的實例不管處於什麼位置，看起來似乎都表現得一樣。經過調查，我們還發現了一個新問題，它已經悄悄滲透到到Amazon的世界中，那就是內部網絡延遲。

 

 算法的選擇

不同的哈希算法可以導致資料分佈的不同位置，如果十分均勻，那麼一次MapReduce就涉及節點較多，但熱點均勻，方便管理。反之，熱點不均，會大致機器效率發揮不完全。

 Quorum NRW

• N: 複製的節點數量
• R: 成功讀操作的最小節點數
• W: 成功寫操作的最小節點數

只需W + R > N，就可以保證強一致性。

第一個關鍵參數是 N，這個 N 指的是資料對象將被覆制到 N 台主機上，N 在實例級別配置，協調器將負責把資料複製到 N-1 個節點上。N 的典型值設置為 3.

復 制中的一致性，採用類似於 Quorum 系統的一致性協議實現。這個協議有兩個關鍵值：R 與 W。R 代表一次成功的讀取操作中最小參與節點數量，W 代表一次成功的寫操作中最小參與節點數量。R + W>N ，則會產生類似 quorum 的效果。該模型中的讀(寫)延遲由最慢的 R(W)複製決定，為得到比較小的延遲，R 和 W 有的時候的和又設置比 N 小。

如果N中的1台發生故障，Dynamo立即寫入到preference list中下一台，確保永遠可寫入

如 果W+R>N，那麼分佈式系統就會提供強一致性的保證，因為讀取資料的節點和被同步寫入的節點是有重疊的。在一個RDBMS的複製模型中 （Master/salve)，假如N=2,那麼W=2,R=1此時是一種強一致性,但是這樣造成的問題就是可用性的減低，因為要想寫操作成功，必須要等 2個節點都完成以後才可以。

在分佈式系統中，一般都要有容錯性，因此一般N都是大於3的，此時根據CAP理論，一致性，可用性和分區容錯 性最多只能滿足兩個，那麼我們就需要在一致性和分區容錯性之間做一平衡，如果要高的一致性，那麼就配置N=W，R=1,這個時候可用性就會大大降低。如果 想要高的可用性，那麼此時就需要放鬆一致性的要求，此時可以配置W=1，這樣使得寫操作延遲最低，同時通過異步的機制更新剩餘的N-W個節點。

當存儲系統保證最終一致性時，存儲系統的配置一般是W+R<=N,此時讀取和寫入操作是不重疊的，不一致性的窗口就依賴於存儲系統的異步實現方式，不一致性的窗口大小也就等於從更新開始到所有的節點都異步更新完成之間的時間。

(N,R,W) 的值典型設置為 (3, 2 ,2),兼顧性能與可用性。R 和 W 直接影響性能、擴展性、一致性，如果 W 設置 為 1，則一個實例中只要有一個節點可用，也不會影響寫操作，如果 R 設置為 1 ，只要有一個節點可用，也不會影響讀請求，R 和 W 值過小則影響一致性，過大也不好，這兩個值要平衡。對於這套系統的典型的 SLA 要求 99.9% 的讀寫操作在 300ms 內完成。

無 論是Read-your-writes-consistency,Session consistency,Monotonic read consistency,它們都通過黏貼（stickiness)客戶端到執行分佈式請求的服務器端來實現的，這種方式簡單是簡單，但是它使得負載均衡以 及分區容錯變的更加難於管理，有時候也可以通過客戶端來實現Read-your-writes-consistency和Monotonic read consistency,此時需要對寫的操作的資料加版本號，這樣客戶端就可以遺棄版本號小於最近看到的版本號的資料。

在系統開發過程 中，根據CAP理論，可用性和一致性在一個大型分區容錯的系統中只能滿足一個，因此為了高可用性，我們必須放低一致性的要求，但是不同的系統保證的一致性 還是有差別的，這就要求開發者要清楚自己用的系統提供什麼樣子的最終一致性的保證，一個非常流行的例子就是web應用系統，在大多數的web應用系統中都 有“用戶可感知一致性”的概念，這也就是說最終一致性中的“一致性窗口"大小要小於用戶下一次的請求，在下次讀取操作來之前，資料可以在存儲的各個節點之 間複製。還比如假如存儲系統提供了

read-your-write-consistency一致性，那麼當一個用戶寫操作完成以後可以立馬看到自己的更 新，但是其它的用戶要過一會才可以看到更新。

幾種特殊情況：
W = 1, R = N,對寫操作要求高性能高可用。
R = 1, W = N , 對讀操作要求高性能高可用，比如類似cache之類業務。
W = Q, R = Q where Q = N / 2 + 1 一般應用適用，讀寫性能之間取得平衡。如N=3,W=2,R=2

 Vector clock

vector clock算法。可以把這個vector clock想像成每個節點都記錄自己的版本信息，而一個資料，包含所有這些版本信息。來看一個例子：假設一個寫請求，第一次被節點A處理了。節點A會增加一個版本信息(A，1)。我們把這個時候的資料記做D1(A，1)。 然後另外一個對同樣key(這一段討論都是針對同樣的key的)的請求還是被A處理了於是有D2(A，2)。

這個時候，D2是可以覆蓋D1的，不會有衝突產生。現在我們假設D2傳播到了所有節點(B和C)，B和C收到的資料不是從客戶產生的，而是別人複製給他們的，所以他們不產生新的版本信息，所以現在B和C都持有資料D2(A，2)。好，繼續，又一個請求，被B處理了，生成資料D3(A，2;B，1)，因為這是一個新版本的資料，被B處理，所以要增加B的版本信息。

假設D3沒有傳播到C的時候又一個請求被C處理記做D4(A，2;C，1)。假設在這些版本沒有傳播開來以前，有一個讀取操作，我們要記得，我們的W=1 那麼R=N=3，所以R會從所有三個節點上讀，在這個例子中將讀到三個版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2;C，1)這個時候可以判斷出，D2已經是舊版本，可以捨棄，但是D3和D4都是新版本，需要應用自己去合併。

如果需要高可寫性，就要處理這種合併問題。好假設應用完成了衝入解決，這裡就是合併D3和D4版本，然後重新做了寫入，假設是B處理這個請求，於是有D5(A，2;B，2;C，1);這個版本將可以覆蓋掉D1-D4那四個版本。這個例子只舉了一個客戶的請求在被不同節點處理時候的情況， 而且每次寫更新都是可接受的，大家可以自己更深入的演算一下幾個並發客戶的情況，以及用一個舊版本做更新的情況。

上面問題看似好像可以通過在三個節點裡選擇一個主節點來解決，所有的讀取和寫入都從主節點來進行。但是這樣就違背了W=1這個約定，實際上還是退化到W=N的情況了。所以如果系統不需要很大的彈性，W=N為所有應用都接受，那麼系統的設計上可以得到很大的簡化。Dynamo 為了給出充分的彈性而被設計成完全的對等集群(peer to peer)，網絡中的任何一個節點都不是特殊的。

 Virtual node

虛擬節點，未完成

 gossip

Gossip協議是一個Gossip思想的P2P實現。現代的分佈式系統經常使用這個協議，他往往是唯一的手段。因為底層的結構非常複雜，而且Gossip也很有效。

Gossip協議也被戲稱為病毒式傳播，因為他的行為生物界的病毒很相似。

 Gossip (State Transfer Model)

在狀態轉移到模式下，每個重複節點都保持的一個Vector clock和一個state version tree。每個節點的狀態都是相同的(based on vector clock comparison),換句話說，state version tree包含有全部的衝突updates.

At query time, the client will attach its vector clock and the replica will send back a subset of the state tree which precedes the client's vector clock (this will provide monotonic read consistency). The client will then advance its vector clock by merging all the versions. This means the client is responsible to resolve the conflict of all these versions because when the client sends the update later, its vector clock will precede all these versions.

At update, the client will send its vector clock and the replica will check whether the client state precedes any of its existing version, if so, it will throw away the client's update.

Replicas also gossip among each other in the background and try to merge their version tree together.

 Gossip (Operation Transfer Model)

In an operation transfer approach, the sequence of applying the operations is very important. At the minimum causal order need to be maintained. Because of the ordering issue, each replica has to defer executing the operation until all the preceding operations has been executed. Therefore replicas save the operation request to a log file and exchange the log among each other and consolidate these operation logs to figure out the right sequence to apply the operations to their local store in an appropriate order.

"Causal order" means every replica will apply changes to the "causes" before apply changes to the "effect". "Total order" requires that every replica applies the operation in the same sequence.

In this model, each replica keeps a list of vector clock, Vi is the vector clock the replica itself and Vj is the vector clock when replica i receive replica j's gossip message. There is also a V-state that represent the vector clock of the last updated state.

When a query is submitted by the client, it will also send along its vector clock which reflect the client's view of the world. The replica will check if it has a view of the state that is later than the client's view.

When an update operation is received, the replica will buffer the update operation until it can be applied to the local state. Every submitted operation will be tag with 2 timestamp, V-client indicates the client's view when he is making the update request. V-@receive is the replica's view when it receives the submission.

This update operation request will be sitting in the queue until the replica has received all the other updates that this one depends on. This condition is reflected in the vector clock Vi when it is larger than V-client

On the background, different replicas exchange their log for the queued updates and update each other's vector clock. After the log exchange, each replica will check whether certain operation can be applied (when all the dependent operation has been received) and apply them accordingly. Notice that it is possible that multiple operations are ready for applying at the same time, the replica will sort these operation in causal order (by using the Vector clock comparison) and apply them in the right order.

The concurrent update problem at different replica can also happen. Which means there can be multiple valid sequences of operation. In order for different replica to apply concurrent update in the same order, we need a total ordering mechanism.

One approach is whoever do the update first acquire a monotonic sequence number and late comers follow the sequence. On the other hand, if the operation itself is commutative, then the order to apply the operations doesn't matter

After applying the update, the update operation cannot be immediately removed from the queue because the update may not be fully exchange to every replica yet. We continuously check the Vector clock of each replicas after log exchange and after we confirm than everyone has receive this update, then we'll remove it from the queue.

 Merkle tree

有資料存儲成樹狀結構，每個節點的Hash是其所有子節點的Hash的Hash，葉子節點的Hash是其內容的Hash。這樣一旦某個節點發生變化，其Hash的變化會迅速傳播到根節點。需要同步的系統只需要不斷查詢跟節點的hash，一旦有變化，順著樹狀結構就能夠在logN級別的時間找到發生變化的內容，馬上同步。

 Paxos

paxos是一種處理一致性的手段，可以理解為事務吧。
其他的手段不要Google GFS使用的Chubby的Lock service。我不大喜歡那種重型的設計就不費筆墨了。