NoSQL資料庫筆談
- 序
- 思想篇
- CAP
- 最終一緻性
- 變體
- BASE
- 其他
- I/O的五分鐘法則
- 不要删除資料
- RAM是硬碟,硬碟是錄音帶
- Amdahl定律和Gustafson定律
- 萬兆以太網
- 手段篇
- 一緻性哈希
-
- 亞馬遜的現狀
- 算法的選擇
-
- Quorum NRW
- Vector clock
- Virtual node
- gossip
- Gossip (State Transfer Model)
- Gossip (Operation Transfer Model)
- Merkle tree
- Paxos
- 背景
- DHT
- Map Reduce Execution
- Handling Deletes
- 存儲實作
- 節點變化
- 列存
- 描述
- 特點
- 一緻性哈希
- 軟體篇
- 亞資料庫
- MemCached
- 特點
- 記憶體配置設定
- 緩存政策
- 緩存資料庫查詢
- 資料備援與故障預防
- Memcached用戶端（mc）
- 緩存式的Web應用程式架構
- 性能測試
- dbcached
- Memcached 和 dbcached 在功能上一樣嗎?
- MemCached
- 列存系列
- Hadoop之Hbase
- 耶魯大學之HadoopDB
- GreenPlum
- FaceBook之Cassandra
- Cassandra特點
- Keyspace
- Column family（CF）
- Key
- Column
- Super column
- Sorting
- 存儲
- API
- Google之BigTable
- Yahoo之PNUTS
- 特點
- PNUTS實作
- Record-level mastering 記錄級别主節點
- PNUTS的結構
- Tablets尋址與切分
- Write調用示意圖
- PNUTS感悟
- 微軟之SQL資料服務
- 非雲服務競争者
- 文檔存儲
- CouchDB
- 特性
- Riak
- MongoDB
- Terrastore
- ThruDB
- CouchDB
- Key Value / Tuple 存儲
- Amazon之SimpleDB
- Chordless
- Redis
- Scalaris
- Tokyo cabinet / Tyrant
- CT.M
- Scalien
- Berkley DB
- MemcacheDB
- Mnesia
- LightCloud
- HamsterDB
- Flare
- 最終一緻性Key Value存儲
- Amazon之Dynamo
- 功能特色
- 架構特色
- BeansDB
- 簡介
- 更新
- 特性
- 性能
- Nuclear
- 兩個設計上的Tips
- Voldemort
- Dynomite
- Kai
- Amazon之Dynamo
- 未分類
- Skynet
- Drizzle
- 比較
- 可擴充性
- 資料和查詢模型
- 持久化設計
- 亞資料庫
- 應用篇
- eBay 架構經驗
- 淘寶架構經驗
- Flickr架構經驗
- Twitter運維經驗
- 運維經驗
- Metrics
- 配置管理
- Darkmode
- 程序管理
- 硬體
- 代碼協同經驗
- Review制度
- 部署管理
- 團隊溝通
- Cache
- 運維經驗
- 雲計算架構
- 反模式
- 單點失敗（Single Point of Failure）
- 同步調用
- 不具備復原能力
- 不記錄日志
- 無切分的資料庫
- 無切分的應用
- 将伸縮性依賴于第三方廠商
- OLAP
- OLAP報表産品最大的難點在哪裡？
- NOSQL們背後的共有原則
- 假設失效是必然發生的
- 對資料進行分區
- 儲存同一資料的多個副本
- 動态伸縮
- 查詢支援
- 使用 Map/Reduce 處理彙聚
- 基于磁盤的和記憶體中的實作
- 僅僅是炒作?
- 附
- 感謝
- 版本志
- 引用
序
日前國内沒有一套比較完整的NoSQL資料庫資料，有很多先驅整理發表了很多，但不是很系統。不材嘗試着将各家的資料整合一下，并書寫了一些自己的見解。
本書寫了一些目前的NoSql的一些主要技術，算法和思想。同時列舉了大量的現有的資料庫執行個體。讀完全篇，相信讀者會對NoSQL資料庫了解個大概。
另外我還準備開發一個開源記憶體資料庫galaxydb.本書也是為這個資料庫提供一些架構資料。
思想篇
CAP，BASE和最終一緻性是NoSQL資料庫存在的三大基石。而五分鐘法則是記憶體資料存儲了理論依據。這個是一切的源頭。
CAP
- C: Consistency 一緻性
- A: Availability 可用性(指的是快速擷取資料)
- P: Tolerance of network Partition 分區容忍性(分布式)
10年前，Eric Brewer教授指出了著名的CAP理論，後來Seth Gilbert 和 Nancy lynch兩人證明了CAP理論的正确性。CAP理論告訴我們，一個分布式系統不可能滿足一緻性，可用性和分區容錯性這三個需求，最多隻能同時滿足兩個。 熊掌與魚不可兼得也。關注的是一緻性，那麼您就需要處理因為系統不可用而導緻的寫操作失敗的情況，而如果您關注的是可用性，那麼您應該知道系統的read操作可能不能精确的讀取到write操作寫入的最新值。是以系統的關注點不同，相應的采用的政策也是不一樣的，隻有真正的了解了系統的需求，才有可能利用好CAP理論。
作為架構師，一般有兩個方向來利用CAP理論
- key-value存儲，如Amaze Dynamo等，可根據CAP三原則靈活選擇不同傾向的資料庫産品。
- 領域模型 + 分布式緩存 + 存儲 （Qi4j和NoSql運動），可根據CAP三原則結合自己項目定制靈活的分布式方案，難度高。
我準備提供第三種方案：實作可以配置CAP的資料庫，動态調配CAP。
- CA：傳統關系資料庫
- AP：key-value資料庫
而對大型網站，可用性與分區容忍性優先級要高于資料一緻性，一般會盡量朝着 A、P 的方向設計，然後通過其它手段保證對于一緻性的商務需求。架構設計師不要精力浪費在如何設計能滿足三者的完美分布式系統，而是應該進行取舍。 不同資料對于一緻性的要求是不同的。舉例來講，使用者評論對不一緻是不敏感的，可以容忍相對較長時間的不一緻，這種不一緻并不會影響交易和使用者體驗。而産品價格資料則是非常敏感的，通常不能容忍超過10秒的價格不一緻。
CAP理論的證明：Brewer's CAP Theorem
最終一緻性
一言以蔽之：過程松，結果緊，最終結果必須保持一緻性
為了更好的描述用戶端一緻性，我們通過以下的場景來進行，這個場景中包括三個組成部分：
- 存儲系統
存儲系統可以了解為一個黑盒子，它為我們提供了可用性和持久性的保證。
- 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[email protected] 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。我不大喜歡那種重型的設計就不費筆墨了。
背景
當規模越來越大的時候。
一、Master/slave
這個是多機房資料通路最常用的方案，一般的需求用此方案即可。是以大家也經常提到“premature optimization is the root of all evil”。
優點：利用mysql replication即可實作，成熟穩定。
缺點：寫操作存在單點故障，master壞掉之後slave不能寫。另外slave的延遲也是個困擾人的小問題。
二、Multi-master
Multi-master指一個系統存在多個master, 每個master都具有read-write能力，需根據時間戳或業務邏輯合并版本。比如分布式版本管理系統git可以了解成multi-master模式。具備最終一緻性。多版本資料修改可以借鑒Dynamo的vector clock等方法。
優點：解決了單點故障。
缺點：不易實作一緻性，合并版本的邏輯複雜。
三、Two-phase commit(2PC)
Two-phase commit是一個比較簡單的一緻性算法。由于一緻性算法通常用神話(如Paxos的The Part-Time Parliament論文)來比喻容易了解，下面也舉個類似神話的例子。
某班要組織一個同學聚會，前提條件是所有參與者同意則活動舉行，任意一人拒絕則活動取消。用2PC算法來執行過程如下
Phase 1
Prepare: 組織者(coordinator)打電話給所有參與者(participant) ，同時告知參與者清單。
Proposal: 提出周六2pm-5pm舉辦活動。
Vote: participant需vote結果給coordinator：accept or reject。
Block: 如果accept, participant鎖住周六2pm-5pm的時間，不再接受其他請求。
Phase 2
Commit: 如果所有參與者都同意，組織者coodinator通知所有參與者commit, 否則通知abort，participant解除鎖定。
Failure 典型失敗情況分析
Participant failure:
任一參與者無響應，coordinator直接執行abort
Coordinator failure:
Takeover: 如果participant一段時間沒收到cooridnator确認(commit/abort)，則認為coordinator不在了。這時候可自動成為Coordinator備份(watchdog)
Query: watchdog根據phase 1接收的participant清單發起query
Vote: 所有participant回複vote結果給watchdog, accept or reject
Commit: 如果所有都同意，則commit, 否則abort。
優點：實作簡單。
缺點：所有參與者需要阻塞(block)，throughput低；無容錯機制，一節點失敗則整個事務失敗。
四、Three-phase commit (3PC)
Three-phase commit是一個2PC的改進版。2PC有一些很明顯的缺點，比如在coordinator做出commit決策并開始發送commit之後，某個participant突然crash，這時候沒法abort transaction, 這時候叢集内實際上就存在不一緻的情況，crash恢複後的節點跟其他節點資料是不同的。是以3PC将2PC的commit的過程1分為2,分成preCommit及commit, 如圖。
(圖檔來源：http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png)
從圖來看，cohorts(participant)收到preCommit之後，如果沒收到commit, 預設也執行commit, 即圖上的timeout cause commit。
如果coodinator發送了一半preCommit crash, watchdog接管之後通過query, 如果有任一節點收到commit, 或者全部節點收到preCommit, 則可繼續commit, 否則abort。
優點：允許發生單點故障後繼續達成一緻。
缺點：網絡分離問題，比如preCommit消息發送後突然兩個機房斷開，這時候coodinator所在機房會abort, 另外剩餘replicas機房會commit。
Google Chubby的作者Mike Burrows說過， “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上隻有一種一緻性算法，那就是Paxos”，所有其他一緻性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改進
P1a. 每次Paxos執行個體執行都配置設定一個編号，編号需要遞增，每個replica不接受比目前最大編号小的提案
P2. 一旦一個 value v 被replica通過，那麼之後任何再準許的 value 必須是 v，即沒有拜占庭将軍(Byzantine)問題。拿上面請客的比喻來說，就是一個參與者一旦accept周六2pm-5pm的proposal, 就不能改變主意。以後不管誰來問都是accept這個value。
一個proposal隻需要多數派同意即可通過。是以比2PC/3PC更靈活，在一個2f+1個節點的叢集中，允許有f個節點不可用。
另外Paxos還有很多限制的細節，特别是Google的chubby從工程實作的角度将Paxos的細節補充得非常完整。比如如何避免Byzantine問題，由于節點的持久存儲可能會發生故障，Byzantine問題會導緻Paxos算法P2限制失效。
以上幾種方式原理比較如下
DHT
Distributed hash table
Map Reduce Execution
Map Reduce已經爛大街了，不過還是要提一下。
參見：http://zh.wikipedia.org/wiki/MapReduce
Handling Deletes
但我們執行删除操作的時候必須非常謹慎，以防丢失掉相應的版本資訊。
通常我們給一個Object标注上"已删除"的标簽。在足夠的時間之後，我們在確定版本一緻的情況下可以将它徹底删除。回收他的空間。
存儲實作
One strategy is to use make the storage implementation pluggable. e.g. A local MySQL DB, Berkeley DB, Filesystem or even a in memory Hashtable can be used as a storage mechanism.
Another strategy is to implement the storage in a highly scalable way. Here are some techniques that I learn from CouchDB and Google BigTable.
CouchDB has a MVCC model that uses a copy-on-modified approach. Any update will cause a private copy being made which in turn cause the index also need to be modified and causing the a private copy of the index as well, all the way up to the root pointer.
Notice that the update happens in an append-only mode where the modified data is appended to the file and the old data becomes garbage. Periodic garbage collection is done to compact the data. Here is how the model is implemented in memory and disks
In Google BigTable model, the data is broken down into multiple generations and the memory is use to hold the newest generation. Any query will search the mem data as well as all the data sets on disks and merge all the return results. Fast detection of whether a generation contains a key can be done by checking a bloom filter.
When update happens, both the mem data and the commit log will be written so that if the
節點變化
Notice that virtual nodes can join and leave the network at any time without impacting the operation of the ring.
When a new node joins the network
- 新加入的節點宣告自己的存在(廣播或者其他手段)
- 他的鄰居節點要調整Key的配置設定和複制關系。這個操作通常是同步的
- 這個新加入的節點異步的拷貝資料
- 這個節點變化的操作被釋出到其他節點
Notice that other nodes may not have their membership view updated yet so they may still forward the request to the old nodes. But since these old nodes (which is the neighbor of the new joined node) has been updated (in step 2), so they will forward the request to the new joined node.
On the other hand, the new joined node may still in the process of downloading the data and not ready to serve yet. We use the vector clock (described below) to determine whether the new joined node is ready to serve the request and if not, the client can contact another replica.
When an existing node leaves the network (e.g. crash)
- The crashed node no longer respond to gossip message so its neighbors knows about it.崩潰的節點不再發送Gossip Message的回應，是以他的鄰居都知道他是了
- The neighbor will update the membership changes and copy data asynchronously，他的鄰居處理後事，将他的活分給别人幹，同時調整節點關系。
We haven't talked about how the virtual nodes is mapped into the physical nodes. Many schemes are possible with the main goal that Virtual Node replicas should not be sitting on the same physical node. One simple scheme is to assigned Virtual node to Physical node in a random manner but check to make sure that a physical node doesn't contain replicas of the same key ranges.
Notice that since machine crashes happen at the physical node level, which has many virtual nodes runs on it. So when a single Physical node crashes, the workload (of its multiple virtual node) is scattered across many physical machines. Therefore the increased workload due to physical node crashes is evenly balanced.
列存
描述
資料庫以行、列的二維表的形式存儲資料，但是卻以一維字元串的方式存儲，例如以下的一個表：
| EmpId | Lastname | Firstname | Salary |
|---|---|---|---|
| 1 | Smith | Joe | 40000 |
| 2 | Jones | Mary | 50000 |
| 3 | Johnson | Cathy | 44000 |
這個簡單的表包括員工代碼(EmpId), 姓名字段(Lastname and Firstname)及工資(Salary).
這個表存儲在電腦的記憶體(RAM)和存儲(硬碟)中。雖然記憶體和硬碟在機制上不同，電腦的作業系統是以同樣的方式存儲的。資料庫必須把這個二維表存儲在一系列一維的“位元組”中，又作業系統寫到記憶體或硬碟中。
行式資料庫把一行中的資料值串在一起存儲起來，然後再存儲下一行的資料，以此類推。
1,Smith,Joe,40000;2,Jones,Mary,50000;3,Johnson,Cathy,44000;
列式資料庫把一列中的資料值串在一起存儲起來，然後再存儲下一列的資料，以此類推。
1,2,3;Smith,Jones,Johnson;Joe,Mary,Cathy;40000,50000,44000;
特點
- 良好的壓縮比。由于大多數資料庫設計都有備援，如此一來，壓縮比非常高，把40多M的資料導入infobright，沒想到資料檔案隻有1M多
- 列上的計算非常的快。
- 友善MapReduce和Key-value模型的融合
- 讀取整行的資料較慢，但部分資料較快
簡單分析含源碼
軟體篇
亞資料庫
我發明的新概念，就是稱不上資料庫但有一些資料庫的特征。可以指緩存。
MemCached
Memcached是danga.com（營運LiveJournal的技術團隊）開發的一套分布式記憶體對象緩存系統，用于在動态系統中減少資料庫 負載，提升性能。
特點
- 協定簡單
- 基于libevent的事件處理
- 内置記憶體存儲方式
- memcached不互相通信的分布式
Memcached處理的原子是每一個（key，value）對（以下簡稱kv對），key會通過一個hash算法轉化成hash-key，便于查找、對比以及做到盡可能的散列。同時，memcached用的是一個二級散列，通過一張大hash表來維護。
Memcached有兩個核心元件組成：服務端（ms）和用戶端（mc），在一個memcached的查詢中，mc先通過計算key的hash值來 确定kv對所處在的ms位置。當ms确定後，用戶端就會發送一個查詢請求給對應的ms，讓它來查找确切的資料。因為這之間沒有互動以及多點傳播協定，是以 memcached互動帶給網絡的影響是最小化的。
記憶體配置設定
預設情況下，ms是用一個内置的叫“塊配置設定器”的元件來配置設定記憶體的。舍棄c++标準的malloc/free的記憶體配置設定，而采用塊配置設定器的主要目的 是為了避免記憶體碎片，否則作業系統要花費更多時間來查找這些邏輯上連續的記憶體塊（實際上是斷開的）。用了塊配置設定器，ms會輪流的對記憶體進行大塊的配置設定，并 不斷重用。當然由于塊的大小各不相同，當資料大小和塊大小不太相符的情況下，還是有可能導緻記憶體的浪費。
同時，ms對key和data都有相應的限制，key的長度不能超過250位元組，data也不能超過塊大小的限制 --- 1MB。
因為mc所使用的hash算法，并不會考慮到每個ms的記憶體大小。理論上mc會配置設定機率上等量的kv對給每個ms，這樣如果每個ms的記憶體都不太一樣，那 可能會導緻記憶體使用率的降低。是以一種替代的解決方案是，根據每個ms的記憶體大小，找出他們的最大公約數，然後在每個ms上開n個容量=最大公約數的 instance，這樣就等于擁有了多個容量大小一樣的子ms，進而提供整體的記憶體使用率。
緩存政策
當ms的hash表滿了之後，新的插入資料會替代老的資料，更新的政策是LRU（最近最少使用），以及每個kv對的有效時限。Kv對存儲有效時限是在mc端由app設定并作為參數傳給ms的。
同時ms采用是偷懶替代法，ms不會開額外的程序來實時監測過時的kv對并删除，而是當且僅當，新來一個插入的資料，而此時又沒有多餘的空間放了，才會進行清除動作。
緩存資料庫查詢
現在memcached最流行的一種使用方式是緩存資料庫查詢，下面舉一個簡單例子說明：
App需要得到userid=xxx的使用者資訊，對應的查詢語句類似：
“SELECT * FROM users WHERE userid = xxx”
App先去問cache，有沒有“user:userid”（key定義可預先定義限制好）的資料，如果有，傳回資料；如果沒有，App會從資料庫中讀取資料，并調用cache的add函數，把資料加入cache中。
當取的資料需要更新，app會調用cache的update函數，來保持資料庫與cache的資料同步。
從上面的例子我們也可以發現，一旦資料庫的資料發現變化，我們一定要及時更新cache中的資料，來保證app讀到的是同步的正确資料。當然我們可 以通過定時器方式記錄下cache中資料的失效時間，時間一過就會激發事件對cache進行更新，但這之間總會有時間上的延遲，導緻app可能從 cache讀到髒資料，這也被稱為狗洞問題。（以後我會專門描述研究這個問題）
資料備援與故障預防
從設計角度上，memcached是沒有資料備援環節的，它本身就是一個大規模的高性能cache層，加入資料備援所能帶來的隻有設計的複雜性和提高系統的開支。
當一個ms上丢失了資料之後，app還是可以從資料庫中取得資料。不過更謹慎的做法是在某些ms不能正常工作時，提供額外的ms來支援cache，這樣就不會因為app從cache中取不到資料而一下子給資料庫帶來過大的負載。
同時為了減少某台ms故障所帶來的影響，可以使用“熱備份”方案，就是用一台新的ms來取代有問題的ms，當然新的ms還是要用原來ms的IP位址，大不了資料重新裝載一遍。
另外一種方式，就是提高你ms的節點數，然後mc會實時偵查每個節點的狀态，如果發現某個節點長時間沒有響應，就會從mc的可用server清單裡 删除，并對server節點進行重新hash定位。當然這樣也會造成的問題是，原本key存儲在B上，變成存儲在C上了。是以此方案本身也有其弱點，最好 能和“熱備份”方案結合使用，就可以使故障造成的影響最小化。
Memcached用戶端（mc）
Memcached用戶端有各種語言的版本供大家使用，包括java，c，php，.net等等，具體可參見memcached api page [2]。
大家可以根據自己項目的需要，選擇合适的用戶端來內建。
緩存式的Web應用程式架構
有了緩存的支援，我們可以在傳統的app層和db層之間加入cache層，每個app伺服器都可以綁定一個mc，每次資料的讀取都可以從ms中取得，如果 沒有，再從db層讀取。而當資料要進行更新時，除了要發送update的sql給db層，同時也要将更新的資料發給mc，讓mc去更新ms中的資料。
性能測試
Memcached 寫速度
平均速度: 16222 次/秒
最大速度 18799 次/秒
Memcached 讀速度
平均速度: 20971 次/秒
最大速度 22497 次/秒
Memcachedb 寫速度
平均速度: 8958 次/秒
最大速度 10480 次/秒
Memcachedb 讀速度
平均速度: 6871 次/秒
最大速度 12542 次/秒
源代碼級别的分析
非常好的剖析文章
dbcached
● dbcached 是一款基于 Memcached 和 NMDB 的分布式 key-value 資料庫記憶體緩存系統。
● dbcached = Memcached + 持久化存儲管理器 + NMDB 用戶端接口
● Memcached 是一款高性能的，分布式的記憶體對象緩存系統，用于在動态應用中減少資料庫負載，提升通路速度。
● NMDB 是一款多協定網絡資料庫(dbm類)管理器，它由記憶體緩存和磁盤存儲兩部分構成，使用 QDBM 或 Berkeley DB 作為後端資料庫。
● QDBM 是一個管理資料庫的例程庫，它參照 GDBM 為了下述三點而被開發：更高的處理速度，更小的資料庫檔案大小，和更簡單的API。QDBM 讀寫速度比 Berkeley DB 要快，詳細速度比較見《 Report of Benchmark Test》。
Memcached 和 dbcached 在功能上一樣嗎?
● 相容：Memcached 能做的，dbcached 都能做。除此之外，dbcached 還将“Memcached、持久化存儲管理器、NMDB 用戶端接口”在一個程式中結合起來，對任何原有 Memcached 用戶端來講，dbcached 仍舊是個 Memcached 記憶體對象緩存系統，但是，它的資料可以持久存儲到本機或其它伺服器上的 QDBM 或 Berkeley DB 資料庫中。
● 性能：前端 dbcached 的并發處理能力跟 Memcached 相同；後端 NMDB 跟 Memcached 一樣，采用了libevent 進行網絡IO處理，擁有自己的記憶體緩存機制，性能不相上下。
● 寫入：當“dbcached 的 Memcached 部分”接收到一個 set(add/replace/...) 請求并儲存 key-value 資料到記憶體中後，“dbcached 持久化存儲管理器”能夠将 key-value 資料通過“NMDB 用戶端接口”儲存到 QDBM 或 Berkeley DB 資料庫中。
● 速度：如果加上“-z”參數，采用 UDP 協定“隻發送不接收”模式将 set(add/replace/...) 指令寫入的資料傳遞給 NMDB 伺服器端，對 Memcache 用戶端寫速度的影響幾乎可以忽略不計。在千兆網卡、同一交換機下伺服器之間的 UDP 傳輸丢包率微乎其微。在命中的情況下，讀取資料的速度跟普通的 Memcached 無差别，速度一樣快。
● 讀取：當“dbcached 的 Memcached 部分”接收到一個 get(incr/decr/...) 請求後，如果“dbcached 的 Memcached 部分”查詢自身的記憶體緩存未命中，則“dbcached 持久化存儲管理器”會通過“NMDB 用戶端接口”從 QDBM 或 Berkeley DB 資料庫中取出資料，傳回給使用者，然後儲存到 Memcached 記憶體中。如果有使用者再次請求這個 key，則會直接從 Memcached 記憶體中傳回 Value 值。
● 持久：使用 dbcached，不用擔心 Memcached 伺服器當機、重新開機而導緻資料丢失。
● 變更：使用 dbcached，即使因為故障轉移，添加、減少 Memcached 伺服器節點而破壞了“key 資訊”與對應“Memcached 伺服器”的映射關系也不怕。
● 分布：dbcached 和 NMDB 既可以安裝在同一台伺服器上，也可以安裝在不同的伺服器上，多台 dbcached 伺服器可以對應一台 NMDB 伺服器。
● 特長：dbcached 對于“讀”大于“寫”的應用尤其适用。
● 其他：《 dbcached 的故障轉移支援、設計方向以及與 Memcachedb 的不同之處》
列存系列
Hadoop之Hbase
Hadoop / HBase: API: Java / any writer, Protocol: any write call, Query Method: MapReduce Java / any exec, Replication: HDFS Replication, Written in: Java, Concurrency: ?, Misc: Links: 3 Books [ 1, 2, 3]
耶魯大學之HadoopDB
GreenPlum
FaceBook之Cassandra
Cassandra: API: many Thrift » languages, Protocol: ?, Query Method: MapReduce, Replicaton: , Written in: Java, Concurrency: eventually consistent , Misc: like "Big-Table on Amazon Dynamo alike", initiated by Facebook, Slides » , Clients »
Cassandra是facebook開源出來的一個版本，可以認為是BigTable的一個開源版本，目前twitter和digg.com在使用。
Cassandra特點
- 靈活的schema，不需要象資料庫一樣預先設計schema，增加或者删除字段非常友善（on the fly）。
- 支援range查詢：可以對Key進行範圍查詢。
- 高可用，可擴充：單點故障不影響叢集服務，可線性擴充。
Cassandra的主要特點就是它不是一個資料庫，而是由一堆資料庫節點共同構成的一個分布式網絡服務，對Cassandra的一個寫操作，會 被複制到其他節點上去，對Cassandra的讀操作，也會被路由到某個節點上面去讀取。對于一個Cassandra群集來說，擴充性能是比較簡單的事 情，隻管在群集裡面添加節點就可以了。我看到有文章說Facebook的Cassandra群集有超過100台伺服器構成的資料庫群集。
Cassandra也支援比較豐富的資料結構和功能強大的查詢語言，和MongoDB比較類似，查詢功能比MongoDB稍弱一些，twitter的平台架構部門上司Evan Weaver寫了一篇文章介紹Cassandra： http://blog.evanweaver.com/articles/2009/07/06/up-and-running-with-cassandra/，有非常詳細的介紹。
Cassandra以單個節點來衡量，其節點的并發讀寫性能不是特别好，有文章說評測下來Cassandra每秒大約不到1萬次讀寫請求，我也看 到一些對這個問題進行質疑的評論，但是評價Cassandra單個節點的性能是沒有意義的，真實的分布式資料庫通路系統必然是n多個節點構成的系統，其并 發性能取決于整個系統的節點數量，路由效率，而不僅僅是單節點的并發負載能力。
Keyspace
Cassandra中的最大組織單元，裡面包含了一系列Column family，Keyspace一般是應用程式的名稱。你可以把它了解為Oracle裡面的一個schema，包含了一系列的對象。
Column family（CF）
CF是某個特定Key的資料集合，每個CF實體上被存放在單獨的檔案中。從概念上看，CF有點象資料庫中的Table.
Key
資料必須通過Key來通路，Cassandra允許範圍查詢，例如：start => '10050', :finish => '10070'
Column
在Cassandra中字段是最小的資料單元，column和value構成一個對，比如：name:“jacky”，column是name，value是jacky，每個column:value後都有一個時間戳：timestamp。
和資料庫不同的是，Cassandra的一行中可以有任意多個column，而且每行的column可以是不同的。從資料庫設計的角度，你可以了解 為表上有兩個字段，第一個是Key，第二個是長文本類型，用來存放很多的column。這也是為什麼說Cassandra具備非常靈活schema的原 因。
Super column
Super column是一種特殊的column，裡面可以存放任意多個普通的column。而且一個CF中同樣可以有任意多個Super column，一個CF隻能定義使用Column或者Super column，不能混用。下面是Super column的一個例子，homeAddress這個Super column有三個字段：分别是street，city和zip： homeAddress: {street: "binjiang road",city: "hangzhou",zip: "310052",}
Sorting
不同于資料庫可以通過Order by定義排序規則，Cassandra取出的資料順序是總是一定的，資料儲存時已經按照定義的規則存放，是以取出來的順序已經确定了，這是一個巨大的性能優勢。有意思的是，Cassandra按照column name而不是column value來進行排序，它 定義了以下幾種選項：BytesType, UTF8Type, LexicalUUIDType, TimeUUIDType, AsciiType, 和LongType，用來定義如何按照column name來排序。實際上，就是把column name識别成為不同的類型，以此來達到靈活排序的目的。UTF8Type是把column name轉換為UTF8編碼來進行排序，LongType轉換成為64位long型，TimeUUIDType是按照基于時間的UUID來排序。例如：
Column name按照LongType排序：
{name: 3, value: "jacky"},
{name: 123, value: "hellodba"},
{name: 976, value: "Cassandra"},
{name: 832416, value: "bigtable"}
Column name按照UTF8Type排序：
{name: 123, value: "hellodba"},
{name: 3, value: "jacky"},
{name: 832416, value: "bigtable"}
{name: 976, value: "Cassandra"}
下面我們看twitter的Schema：
<Keyspace Name="Twitter">
<ColumnFamily CompareWith="UTF8Type" Name="Statuses" />
<ColumnFamily CompareWith="UTF8Type" Name="StatusAudits" />
<ColumnFamily CompareWith="UTF8Type" Name="StatusRelationships"
CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" />
<ColumnFamily CompareWith="UTF8Type" Name="Users" />
<ColumnFamily CompareWith="UTF8Type" Name="UserRelationships"
CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" />
</Keyspace>
我們看到一個叫Twitter的keyspace，包含若幹個CF，其中StatusRelationships和 UserRelationships被定義為包含Super column的CF，CompareWith定義了column的排序規則，CompareSubcolumnsWith定義了subcolumn的排序 規則，這裡使用了兩種：TimeUUIDType和UTF8Type。我們沒有看到任何有關column的定義，這意味着column是可以靈活變更的。
為了友善大家了解，我會嘗試着用關系型資料庫的模組化方法去描述Twitter的Schema，但千萬不要誤認為這就是Cassandra的資料模型，對于Cassandra來說，每一行的colunn都可以是任意的，而不是象資料庫一樣需要在建表時就建立好。
Users CF記錄使用者的資訊，Statuses CF記錄tweets的内容，StatusRelationships CF記錄使用者看到的tweets，UserRelationships CF記錄使用者看到的followers。我們注意到排序方式是TimeUUIDType，這個類型是按照時間進行排序的UUID字段，column name是用UUID函數産生（這個函數傳回了一個UUID，這個UUID反映了目前的時間，可以根據這個UUID來排序，有點類似于timestamp 一樣），是以得到結果是按照時間來排序的。使用過twitter的人都知道，你總是可以看到自己最新的tweets或者最新的friends.
存儲
Cassandra是基于列存儲的(Bigtable也是一樣)，這個和基于列的資料庫是一個道理。
API
下面是資料庫，Bigtable和Cassandra API的對比： Relational SELECT `column` FROM `database`.`table` WHERE `id` = key;
BigTable table.get(key, "column_family:column")
Cassandra: standard model keyspace.get("column_family", key, "column")
Cassandra: super column model keyspace.get("column_family", key, "super_column", "column")
我對Cassandra資料模型的了解：
1.column name存放真正的值，而value是空。因為Cassandra是按照column name排序，而且是按列存儲的，是以往往利用column name存放真正的值，而value部分則是空。例如：“jacky”:“null”，“fenng”:”null”
2.Super column可以看作是一個索引，有點象關系型資料庫中的外鍵，利用super column可以實作快速定位，因為它可以傳回一堆column，而且是排好序的。
3.排序在定義時就确定了，取出的資料肯定是按照确定的順序排列的，這是一個巨大的性能優勢。
4. 非常靈活的schema，column可以靈活定義。實際上，colume name在很多情況下，就是value（是不是有點繞）。
5.每個column後面的timestamp，我并沒有找到明确的說明，我猜測可能是資料多版本，或者是底層清理資料時需要的資訊。
最後說說架構，我認為架構的核心就是有所取舍，不管是CAP還是BASE，講的都是這個原則。架構之美在于沒有任何一種架構可以完美的解決各種問題，資料庫和NoSQL都有其應用場景，我們要做的就是為自己找到合适的架構。
Hypertable
Hypertable : (can you help?) Open-Source Google BigTable alike.
它是搜尋引擎公司Zvents根據Google的9位研究人員在2006年發表的一篇論文《 Bigtable：結構化資料的分布存儲系統》 開發的一款開源分布式資料儲存系統。Hypertable是按照1000節點比例設計，以 C++撰寫，可架在 HDFS 和 KFS 上。盡管還在初期階段，但已有不錯的效能：寫入 28M 列的資料，各節點寫入速率可達7MB/s，讀取速率可達 1M cells/s。Hypertable目前一直沒有太多高負載和大存儲的應用執行個體，但是最近，Hypertable項目得到了 百度的贊助支援，相信其會有更好的發展。
Google之BigTable
研究Google的産品總是感激Google給了自己那麼多友善，真心喜歡之。
Google AppEngine Datastore 是在BigTable之上建造出來的，是Google的内部存儲系統，用于處理結構化資料。AppEngine Datastore其自身及其内部都不是直接通路BigTable的實作機制，可被視為BigTable之上的一個簡單接口。
AppEngine Datastore所支援的項目的資料類型要比SimpleDB豐富得多，也包括了包含在一個項目内的資料集合的清單型。
如果你打算在Google AppEngine之内建造應用的話，幾乎可以肯定要用到這個資料存儲。然而，不像SimpleDB，使用谷歌網絡服務平台之外的應用，你并不能并發地與AppEngine Datastore進行接口 (或通過BigTable)。
Yahoo之PNUTS
Yahoo!的PNUTS是一個分布式的資料存儲平台，它是Yahoo!雲計算平台重要的一部分。它的上層産品通常也稱為Sherpa。按照官方的 描述，”PNUTS, a massively parallel and geographically distributed database system for Yahoo!’s web applications.” PNUTS顯然就深谙CAP之道，考慮到大部分web應用對一緻性并不要求非常嚴格，在設計上放棄了對強一緻性的追求。代替的是追求更高的 availability，容錯，更快速的響應調用請求等。
特點
- 地理分布式，分布在全球多個資料中心。由于大部分Web應用都對響應時間要求高，是以最好伺服器部署在離使用者最近的本地機房。
- 可擴充，記錄數可支援從幾萬條到幾億條。資料容量增加不會影響性能。
- schema-free，即非固定表結構。實際使用key/value存儲的，一條記錄的多個字段實際是用json方式合并存在value中。是以delete和update必須指定primary key。但也支援批量查詢。
- 高可用性及容錯。從單個存儲節點到整個資料中心不可用都不會影響前端Web通路。
- 适合存相對小型的記錄，不适合存儲大檔案，流媒體等。
- 弱一緻性保證。
PNUTS實作
Record-level mastering 記錄級别主節點
每一條記錄都有一個主記錄。比如一個印度的使用者儲存的記錄master在印度機房，通常修改都會調用印度。其他地方如美國使用者看這個使用者的資料調用 的是美國資料中心的資料，有可能取到的是舊版的資料。非master機房也可對記錄進行修改，但需要master來統一管理。每行資料都有自己的版本控 制，如下圖所示。
PNUTS的結構
每個資料中心的PNUTS結構由四部分構成
Storage Units (SU) 存儲單元
實體的存儲伺服器，每個存儲伺服器上面含有多個tablets，tablets是PNUTS上的基本存儲單元。一 個tablets是一個yahoo内部格式的hash table的檔案(hash table)或是一個MySQL innodb表(ordered table)。一個Tablet通常為幾百M。一個SU上通常會存在幾百個tablets。
Routers
每個tablets在哪個SU上是通過查詢router獲得。一個資料中心内router通常可由兩台雙機備份的單元提供。
Tablet Controller
router的位置隻是個記憶體快照，實際的位置由Tablet Controller單元決定。
Message Broker
與遠端資料的同步是由YMB提供，它是一個pub/sub的異步消息訂閱系統。
Tablets尋址與切分
存儲分hash和ordered data store。
以hash為例介紹，先對所有的tablets按hash值分片，比如1-10,000屬于tablets 1, 10,000到20,000屬于tablets 2，依此類推配置設定完所有的hash範圍。一個大型的IDC通常會存在100萬以下的tablets, 1,000台左右的SU。tablets屬于哪個SU由routers全部加載到記憶體裡面，是以router通路速度極快，通常不會成為瓶頸。按照官方的 說法，系統的瓶頸隻存在磁盤檔案hash file通路上。
當某個SU通路量過大，則可将SU中部分tablets移到相對空閑的SU，并修改tablet controller的偏移記錄。router定位tablet失效之後會自動通過tablet controller重新加載到記憶體。是以切分也相對容易實作。
Tim也曾經用MySQL實作過類似大規模存儲的系統，當時的做法是把每條記錄的key屬于哪個SU的資訊儲存到 一個字典裡面，好處是切分可以獲得更大的靈活性，可以動态增加新的tablets,而不需要切分舊的tablets。但缺點就是字典沒法像router這 樣，可以高效的全部加載到記憶體中。是以比較而言，在實際的應用中，按段分片會更簡單，且已經足夠使用。
Write調用示意圖
PNUTS感悟
2006年Greg Linden就說I want a big, virtual database
What I want is a robust, high performance virtual relational database that runs transparently over a cluster, nodes dropping in an out of service at will, read-write replication and data migration all done automatically.
I want to be able to install a database on a server cloud and use it like it was all running on one machine.
詳細資料：
http://timyang.net/architecture/yahoo-pnuts/
微軟之SQL資料服務
SQL資料服務 是微軟 Azure 網 絡服務平台的一部分。該SDS服務也是處于測試階段，是以也是免費的，但對資料庫大小有限制。 SQL資料服務其自身實際上是一項處在許多SQL伺服器之上的應用，這些SQL伺服器組成了SDS平台底層的資料存儲。你不需要通路到它們，雖然底層的數 據庫可能是關系式的；SDS是一個鍵/值型倉儲，正如我們迄今所讨論過的其它平台一樣。
微軟看起來不同于前三個供應商，因為雖然鍵/值存儲對于可擴性���言非常棒，相對于RDBMS，在資料管理上卻很困難。微軟的方案似乎是入木三分，在實作可擴性和分布機制的同時，随着時間的推移，不斷增加特性，在鍵/值存儲和關系資料庫平台的鴻溝之間搭起一座橋梁。
非雲服務競争者
在雲之外，也有一些可以獨立安裝的鍵/值資料庫軟體産品。大部分都還很年輕，不是alpha版就是beta版，但大都是開源的；通過看看它的代碼，比起在非開源供應商那裡，你也許更能意識到潛在的問題和限制。
文檔存儲
CouchDB
CouchDB: API: JSON, Protocol: REST, Query Method: MapReduceR of JavaScript Funcs, Replication: Master Master, Written in: Erlang, Concurrency: MVCC, Misc:
Links: 3 CouchDB books », Couch Lounge » (partitioning / clusering), ...
它是Apache社群基于 Erlang/OTP 建構的高性能、分布式容錯非關系型資料庫系統（NRDBMS）。它充分利用 Erlang 本身所提供的高并發、分布式容錯基礎平台，并且參考 Lotus Notes 資料庫實作，采用簡單的文檔資料類型（document-oriented）。在其内部，文檔資料均以 JSON 格式存儲。對外，則通過基于 HTTP 的 REST 協定實作接口，可以用十幾種語言進行自由操作。
CouchDB一種半結構化面向文檔的���布式，高容錯的資料庫系統，其提供RESTFul HTTP/JSON接口。其擁有MVCC特性，使用者可以通過自定義Map/Reduce函數生成對應的View。
在CouchDB中，資料是以JSON字元的方式存儲在檔案中。
特性
- RESTFul API：HTTP GET/PUT/POST/DELETE + JSON
- 基于文檔存儲，資料之間沒有關系範式要求
- 每個資料庫對應單個個檔案(以JSON儲存),Hot backup
- MVCC（Multi-Version-Concurrency-Control），讀寫均不鎖定資料庫
- 使用者自定義View
- 内建備份機制
- 支援附件
- 使用Erlang開發（更多的特性）
應用場景 在我們的生活中，有很多document，比如信件，賬單，筆記等，他們隻是簡單的資訊，沒有關系的需求，我們可能僅僅需要存儲這些資料。 這樣的情況下，CouchDB應該是很好的選擇。當然其他使用關系型資料庫的環境，也可以使用CouchDB來解決。
根據CouchDB的特性，在某些偶 爾連接配接網絡的應用中，我們可以用CouchDB暫存資料，随後進行同步。也可以在Cloud環境中，作為分布式的資料存儲。CouchDB提供給予 HTTP的API，這樣所有的常見語言都可以使用CouchDB。
使用CouchDB，意味着我們不需要在像使用RMDBS一樣，在設計應用前首先設計負責資料Table。我們的開發更加快速，靈活。
詳細參見：
http://www.javaeye.com/topic/319839
Riak
Riak: API: JSON, Protocol: REST, Query Method: MapReduce term matching , Scaling: Multiple Masters; Written in: Erlang, Concurrency: eventually consistent (stronger then MVCC via Vector Clocks), Misc: ... Links: talk »,
MongoDB
MongoDB: API: BSON, Protocol: lots of langs, Query Method: dynamic object-based language, Replication: Master Slave, Written in: C++,Concurrency: Update in Place. Misc: ... Links: Talk »,
MongoDB是一個介于關系資料庫和非關系資料庫之間的産品，是非關系資料庫當中功能最豐富，最像關系資料庫的。他支援的資料結構非常松散，是 類似json的bjson格式，是以可以存儲比較複雜的資料類型。Mongo最大的特點是他支援的查詢語言非常強大，其文法有點類似于面向對象的查詢語 言，幾乎可以實作類似關系資料庫單表查詢的絕大部分功能，而且還支援對資料建立索引。
Mongo主要解決的是海量資料的通路效率問題，根據官方的文檔，當資料量達到50GB以上的時候，Mongo的資料庫通路速度是MySQL的 10倍以上。Mongo的并發讀寫效率不是特别出色，根據官方提供的性能測試表明，大約每秒可以處理0.5萬－1.5次讀寫請求。對于Mongo的并發讀 寫性能，我（robbin）也打算有空的時候好好測試一下。
因為Mongo主要是支援海量資料存儲的，是以Mongo還自帶了一個出色的分布式檔案系統GridFS，可以支援海量的資料存儲，但我也看到有些評論認為GridFS性能不佳，這一點還是有待親自做點測試來驗證了。
最後由于Mongo可以支援複雜的資料結構，而且帶有強大的資料查詢功能，是以非常受到歡迎，很多項目都考慮用MongoDB來替代MySQL來實作不是特别複雜的Web應用，比方說why we migrated from MySQL to MongoDB就是一個真實的從MySQL遷移到MongoDB的案例，由于資料量實在太大，是以遷移到了Mongo上面，資料查詢的速度得到了非常顯著的提升。
MongoDB也有一個ruby的項目MongoMapper，是模仿Merb的DataMapper編寫的MongoDB的接口，使用起來非常簡單，幾乎和DataMapper一模一樣，功能非常強大易用。
Terrastore
Terrastore: API: Java & http, Protocol: http, Language: Java, Querying: Range queries, Predicates, Replication: Partitioned with consistent hashing, Consistency: Per-record strict consistency, Misc: Based on Terracotta
ThruDB
ThruDB: (please help provide more facts!) Uses Apache Thrift to integrate multiple backend databases as BerkeleyDB, Disk, MySQL, S3.
Key Value / Tuple 存儲
Amazon之SimpleDB
Amazon SimpleDB: Misc: not open source, Book »
SimpleDB 是一個亞馬遜網絡服務平台的一個面向屬性的鍵/值資料庫。SimpleDB仍處于公衆測試階段；目前，使用者能線上注冊其“免費”版 --免費的意思是說直到超出使用限制為止。
SimpleDB有幾方面的限制。首先，一次查詢最多隻能執行5秒鐘。其次，除了字元串類型，别無其它資料類型。一切都以字元串形式被存儲、擷取和 比較，是以除非你把所有日期都轉為ISO8601，否則日期比較将不起作用。第三，任何字元串長度都不能超過1024位元組，這限制了你在一個屬性中能存儲 的文本的大小（比如說産品描述等）。不過，由于該模式動态靈活，你可以通過追加“産品描述1”、“産品描述2”等來繞過這類限制。一個項目最多可以有 256個屬性。由于處在測試階段，SimpleDB的域不能大于10GB，整個庫容量則不能超過1TB。
SimpleDB的一項關鍵特性是它使用一種最終一緻性模型。 這個一緻性模型對并發性很有好處，但意味着在你改變了項目屬性之後，那些改變有可能不能立即反映到随後的讀操作上。盡管這種情況實際發生的幾率很低，你也 得有所考慮。比如說，在你的演出訂票系統裡，你不會想把最後一張音樂會門票賣給5個人，因為在售出時你的資料是不一緻的。
Chordless
Chordless: API: Java & simple RPC to vals, Protocol: internal, Query Method: M/R inside value objects, Scaling: every node is master for its slice of namespace, Written in: Java, Concurrency: serializable transaction isolation, Links:
Redis
Redis : (please help provide more facts!) API: Tons of languages, Written in: C, Concurrency: in memory and saves asynchronous disk after a defined time. Append only mode available. Different kinds of fsync policies. Replication: Master / Slave,
Redis是一個很新的項目，剛剛釋出了1.0版本。Redis本質上是一個Key-Value類型的記憶體資料庫，很像memcached，整個資料庫統 統加載在記憶體當中進行操作，定期通過異步操作把資料庫資料flush到硬碟上進行儲存。因為是純記憶體操作，Redis的性能非常出色，每秒可以處理超過 10萬次讀寫操作，是我知道的性能最快的Key-Value DB。
Redis的出色之處不僅僅是性能，Redis最大的魅力是支援儲存List連結清單和Set集合的資料結構，而且還支援對List進行各種操作，例 如從List兩端push和pop資料，取List區間，排序等等，對Set支援各種集合的并集交集操作，此外單個value的最大限制是1GB，不像 memcached隻能儲存1MB的資料，是以Redis可以用來實作很多有用的功能，比方說用他的List來做FIFO雙向連結清單，實作一個輕量級的高性 能消息隊列服務，用他的Set可以做高性能的tag系統等等。另外Redis也可以對存入的Key-Value設定expire時間，是以也可以被當作一 個功能加強版的memcached來用。
Redis的主要缺點是資料庫容量受到實體記憶體的限制，不能用作海量資料的高性能讀寫，并且它沒有原生的可擴充機制，不具有scale（可擴充） 能力，要依賴用戶端來實作分布式讀寫，是以Redis适合的場景主要局限在較小資料量的高性能操作和運算上。目前使用Redis的網站有 github，Engine Yard。
Scalaris
Scalaris: (please help provide more facts!) Written in: Erlang, Replication: Strong consistency over replicas, Concurrency: non blocking Paxos.
Tokyo cabinet / Tyrant
Tokyo Cabinet / Tyrant: Links: nice talk », slides », Misc: Kyoto Cabinet »
它是日本最大的SNS社交網站mixi.jp開發的 Tokyo Cabinet key-value資料庫網絡接口。它擁有Memcached相容協定，也可以通過HTTP協定進行資料交換。對任何原有Memcached用戶端來講， 可以将Tokyo Tyrant看成是一個Memcached，但是，它的資料是可以持久存儲的。Tokyo Tyrant 具有故障轉移、日志檔案體積小、大資料量下表現出色等優勢，詳見：http://blog.s135.com/post/362.htm
Tokyo Cabinet 2009年1月18日釋出的新版本（Version 1.4.0）已經實作 Table Database，将key-value資料庫又擴充了一步，有了MySQL等關系型資料庫的表和字段的概念，相信不久的将來，Tokyo Tyrant 也将支援這一功能。值得期待。
TC除了支援Key-Value存儲之外，還支援儲存Hashtable資料類型，是以很像一個簡單的資料庫表，并且還支援基于column的條 件查詢，分頁查詢和排序功能，基本上相當于支援單表的基礎查詢功能了，是以可以簡單的替代關系資料庫的很多操作，這也是TC受到大家歡迎的主要原因之一， 有一個Ruby的項目 miyazakiresistance将TT的hashtable的操作封裝成和ActiveRecord一樣的操作，用起來非常爽。
TC/TT在mixi的實際應用當中，存儲了2000萬條以上的資料，同時支撐了上萬個并發連接配接，是一個久經考驗的項目。TC在保證了極高的并發 讀寫性能的同時，具有可靠的資料持久化機制，同時還支援類似關系資料庫表結構的hashtable以及簡單的條件，分頁和排序操作，是一個很棒的 NoSQL資料庫。
TC的主要缺點是在資料量達到上億級别以後，并發寫資料性能會大幅度下降， NoSQL: If Only It Was That Easy提到，他們發現在TC裡面插入1.6億條2-20KB資料的時候，寫入性能開始急劇下降。看來是當資料量上億條的時候，TC性能開始大幅度下降，從TC作者自己提供的mixi資料來看，至少上千萬條資料量的時候還沒有遇到這麼明顯的寫入性能瓶頸。
這個是Tim Yang做的一個 Memcached，Redis和Tokyo Tyrant的簡單的性能評測，僅供參考
CT.M
GT.M: API: M, C, Python, Perl, Protocol: native, inprocess C, Misc: Wrappers: M/DB for SimpleDB compatible HTTP », MDB:X for XML », PIP for mapping to tables for SQL », Features: Small footprint (17MB), Terabyte Scalability, Unicode support, Database encryption, Secure, ACID transactions (single node), eventual consistency (replication), License: AGPL v3 on x86 GNU/Linux, Links: Slides »,
Scalien
Scalien: API / Protocol: http (text, html, JSON), C, C++, Python, Concurrency: Paxos.
Berkley DB
Berkley DB: API: Many languages, Written in: C, Replication: Master / Slave, Concurrency: MVCC, License: Sleepycat, BerkleyDB Java Edition: API: Java, Written in: Java, Replication: Master / Slave, Concurrency: serializable transaction isolation, License: Sleepycat
MemcacheDB
MemcacheDB: API: Memcache protocol (get, set, add, replace, etc.), Written in: C, Data Model: Blob, Misc: Is Memcached writing to BerkleyDB.
它是新浪互動社群事業部為在Memcached基礎上，增加Berkeley DB存儲層而開發一款支援高并發的分布式持久存儲系統，對任何原有Memcached用戶端來講，它仍舊是個Memcached，但是，它的資料是可以持久存儲的。
Mnesia
Mnesia: (ErlangDB »)
LightCloud
LightCloud: (based on Tokyo Tyrant)
HamsterDB
HamsterDB: (embedded solution) ACID Compliance, Lock Free Architecture (transactions fail on conflict rather than block), Transaction logging & fail recovery (redo logs), In Memory support – can be used as a non-persisted cache, B+ Trees – supported [Source: Tony Bain »]
Flare
TC是日本第一大SNS網站mixi開發的，而Flare是日本第二大SNS網站green.jp開發的，有意思吧。Flare簡單的說就是給 TC添加了scale功能。他替換掉了TT部分，自己另外給TC寫了網絡伺服器，Flare的主要特點就是支援scale能力，他在網絡服務端之前添加了 一個node server，來管理後端的多個伺服器節點，是以可以動态添加資料庫服務節點，删除伺服器節點，也支援failover。如果你的使用場景必須要讓TC可 以scale，那麼可以考慮flare。
flare唯一的缺點就是他隻支援memcached協定，是以當你使用flare的時候，就不能使用TC的table資料結構了，隻能使用TC的key-value資料結構存儲。
最終一緻性Key Value存儲
Amazon之Dynamo
Amazon Dynamo: Misc: not open source (see KAI below)
功能特色
- 高可用
- 可擴充
- 總是可寫
- 可以根據應用類型優化(可用性，容錯性，高效性配置)
架構特色
- 完全的分布式
- 去中心化(人工管理工作很小)
- Key 唯一代表一個資料對象，對該資料對象的讀寫操通過 Key 來完成.
- 通常是一台自帶硬碟的主機。每個節點有三個 Java 寫的元件：請求協調器(request coordination)、成員與失敗檢測、本地持久引擎(local persistence engine)
- 資料分區并用改進的一緻性哈希(consistent hashing)方式進行複制，利用資料對象的版本化實作一緻性。複制時因為更新産生的一緻性問題的維護采取類似 quorum 的機制以及去中心化的複制同步協定。
- 每個執行個體由一組節點組成，從應用的角度看，執行個體提供 IO 能力。一個執行個體上的節點可能位于不同的資料中心内, 這樣一個資料中心出問題也不會導緻資料丢失。
BeansDB
簡介
BeansDB 是一個主要針對大資料量、高可用性的分布式KeyValue存儲系統，采用HashTree和簡化的版本号來快速同步保證最終一緻性（弱），一個簡化版的Dynamo。
它采用類似memcached的去中心化結構，在用戶端實作資料路由。目前隻提供了Python版本的用戶端，其它語言的用戶端可以由memcached的用戶端稍加改造得到。
Google Group: http://groups.google.com/group/beandb/
更新
2009.12.29 第一個公開版本 0.3
特性
- 高可用：通過多個可讀寫的用于備份實作高可用
- 最終一緻性：通過哈希樹實作快速完整資料同步（短時間内資料可能不一緻）
- 容易擴充：可以在不中斷服務的情況下進行容量擴充。
- 高性能：異步IO和高性能的KeyValue資料TokyoCabinet 可配置的
- 可用性和一緻性：通過N,W,R進行配置 簡單協定：Memcache相容協定，大量可用用戶端
性能
在小資料集上，它跟memcached一樣快：
# memstorm -s localhost:7900 -n 1000
Num of Records : 10000
Non-Blocking IO : 0
TCP No-Delay : 0
Successful [SET] : 10000
Failed [SET] : 0
Total Time [SET] : 0.45493s
Average Time [SET] : 0.00005s
Successful [GET] : 10000
Failed [GET] : 0
Total Time [GET] : 0.28609s
Average Time [GET] : 0.00003s
實際部署情況下的性能（用戶端測量）：
􀂄 伺服器 請求數 評價時間(ms) 中位數(ms) 99% (ms) 99.9%(ms)
􀂄 get A:7900 n=151398, avg=8.89, med=5.94, 99%=115.5, 99.9%=310.2
􀂄 get B:7900 n=100054, avg=6.84, med=0.40, 99%=138.5, 99.9%=483.0
􀂄 get C:7900 n=151250, avg=7.42, med=5.34, 99%=55.2, 99.9%=156.7
􀂄 get D:7900 n=150677, avg=7.63, med=5.09, 99%=97.7, 99.9%=284.7
􀂄 get E:7900 n=3822, avg=3.07, med=0.18, 99%=44.3, 99.9%=170.0
􀂄 get F:7900 n=249973, avg=8.29, med=6.36, 99%=46.8, 99.9%=241.5
􀂄 set A:7900 n=10177, avg=18.53, med=12.78,99%=189.3, 99.9%=513.6
􀂄 set B:7900 n=10431, avg=12.85, med=1.19, 99%=206.1, 99.9%=796.8
􀂄 set C:7900 n=10556, avg=17.29, med=12.97,99%=132.2, 99.9%=322.9
􀂄 set D:7900 n=10164, avg=7.34, med=0.64, 99%=98.8, 99.9%=344.4
􀂄 set E:7900 n=10552, avg=7.18, med=2.33, 99%=73.6, 99.9%=204.8
􀂄 set F:7900 n=10337, avg=17.79, med=15.31, 99%=109.0, 99.9%=369.5
BeansDB設計實作（非常難得的中文資料）
PPT
Nuclear
人人網研發中的資料庫
詳見：
http://ugc.renren.com/2010/01/21/ugc-nuclear-guide-use/
http://ugc.renren.com/2010/01/28/ugc-nuclear-guide-theory/
兩個設計上的Tips
1. 萬事皆異步
我們在編碼的過程中走了一些彎路，同步的操作在高并發的情況下帶來的性能下降是非常恐怖的，于是乎，Nuclear系統中任何的高并發操作都消除了Block。no waiting, no delay。
2. 根據系統負載控制背景線程的資源占用
Nuclear系統中有不少的背景線程默默無聞的做着各種辛苦的工作，但是它們同樣會占用系統資源，我們的解決方案是根據系統負載動态調整線程的運作和停止，并達到平衡。
Voldemort
Voldemort: (can you help)
Voldemort是個和Cassandra類似的面向解決scale問題的分布式資料庫系統，Cassandra來自于Facebook這個 SNS網站，而Voldemort則來自于Linkedin這個SNS網站。說起來SNS網站為我們貢獻了n多的NoSQL資料庫，例如 Cassandar，Voldemort，Tokyo Cabinet，Flare等等。Voldemort的資料不是很多，是以我沒有特别仔細去鑽研，Voldemort官方給出Voldemort的并發讀 寫性能也很不錯，每秒超過了1.5萬次讀寫。
其實作在很多公司可能都面臨着這個抽象架構圖中的類似問題。以 Hadoop 作為後端的計算叢集，計算得出來的資料如果要反向推到前面去，用什麼方式存儲更為恰當? 再放到 DB 裡面的話，建構索引是麻煩事；放到 Memcached 之類的 Key-Value 分布式系統中，畢竟隻是在記憶體裡，資料又容易丢。Voldemort 算是一個不錯的改良方案。
值得借鑒的幾點:
- 鍵(Key)結構的設計，有點技巧；
- 架構師熟知硬體結構是有用的。越大的系統越是如此。
- 用好并行。Amdahl 定律以後出現的場合會更多。
詳細：
http://www.dbanotes.net/arch/voldemort_key-value.html
http://project-voldemort.com/blog/2009/06/building-a-1-tb-data-cycle-at-linkedin-with-hadoop-and-project-voldemort/
Dynomite
Dynomite: (can you help)
Kai
KAI: Open Source Amazon Dnamo implementation, Misc: slides ,
未分類
Skynet
全新的Ruby MapReduce實作
2004年，Google提出用于分布式資料處理的MapReduce設計模式，同時還提供了第一個C++的實作。現在，一個名為Skynet的Ruby實作已經由Adam Pisoni釋出。
Skynet是可适配、可容錯的、可自我更新的，而且完全
是分布式的系統，不存在單一的失敗節點。
Skynet和Google在設計上有兩點重要的差別：
Skynet無法向工作者（Worker）發送原生代碼（Raw code），
Skynet利用結對恢複系統，不同的工作者會互相監控以防失敗：
如果有一個工作者由于某種原因離開或者放棄了，就會有另一個工作者發現并接管它的任務。Skynet 也沒有所謂的“主”管理程序，隻有工作者，它們在任何時間都可以充當任何任務的主管理程序。
Skynet的使用和設定都很容易，這也正是MapReduce這個概念的真正優勢。Skynet還擴充了ActiveRecord，加入了MapReduce的特性，比如distributed_find。
你要為Starfish編寫一些小程式，它們的代碼是你将要建構其中的。如果我沒有弄錯的話，你無法在同一台機器上運作多種類型的MapReduce作業。Skynet是一個更全面的MR系統，可以運作多種類型的多個作業，比如，各種不同的代碼。
Skynet也允許失敗。工作者會互相關照。如果一個工作者失敗了，無法及時完成任務，另一個工作者将會接起這個任務并嘗試完成它。Skynet也支援map_data流，也就是說，即使某個資料集非常龐大，甚至無法放在一個資料結構中，Skynet也可以處理。
什 麼是map_data流？大多數時候，在你準備啟動一個map_reduce作業時，必須提供一個資料的隊列，這些資料已經被分離并将被并行處理。如果隊 列過大，以至于無法适應于記憶體怎麼辦？在這種情況下，你就要不能再用隊列，而應該使用枚舉（Enumerable）。Skynet知道去對象的調 用:next或者:each方法，然後開始為“每一個（each）”分離出map_task來。通過這樣的方式，不會有人再試圖同時建立大量的資料結構。
還 有很多特性值得一提，不過最想提醒大家的是，Skynet能夠與你現有的應用非常完美地內建到一起，其中自然包括Rails應用。Skynet甚 至還提供了一個ActiveRecord的擴充，你可以在模型中以分布式的形式執行一些任務。在Geni中，我們使用這項功能來運作特别複雜的移植，它通 常涉及到在數百萬的模型上執行Ruby代碼。
> Model.distributed_find(:all, :conditions => "id > 20").each(:somemethod)在你運作Skynet的時候，它将在每個模型上執行:somemethod，不過是以分布式的方式（這和你 擁有多少個工作者相關）。它在向模型分發任務前不必進行初始化，甚至不必提前擷取所有的id。是以它可以操作無限大的資料集。 使用者的回報如何？
Drizzle
Drizzle可 被認為是鍵/值存儲要解決的問題的反向方案。Drizzle誕生于MySQL（6.0）關系資料庫的拆分。在過去幾個月裡，它的開發者已經移走了大量非核 心的功能（包括視圖、觸發器、已編譯語句、存儲過程、查詢緩沖、ACL以及一些資料類型），其目标是要建立一個更精簡、更快的資料庫系統。Drizzle 仍能存放關系資料；正如MySQL/Sun的Brian Aker所說那樣：“沒理由潑洗澡水時連孩子也倒掉”。它的目标就是，針對運作于16核（或以上）系統上的以網絡和雲為基礎的應用，建立一個半關系型資料 庫平台。
比較
可擴充性
資料和查詢模型
當你需要查詢或更新一個值的一部分時，Key/value模型是最簡單有效實作。
面向文本資料庫是Key/value的下一步, 允許内嵌和Key關聯的值. 支援查詢這些值資料，這比簡單的每次傳回整個blob類型資料要有效得多。
Neo4J是唯一的存儲對象和關系作為數學圖論中的節點和邊. 對于這些類型資料的查詢，他們能夠比其他競争者快1000s
Scalaris是唯一提供跨越多個key的分布式事務。
持久化設計
記憶體資料庫是非常快的，(Redis在單個機器上可以完成每秒100,000以上操作）但是資料集超過記憶體RAM大小就不行. 而且 Durability (伺服器當機恢複資料)也是一個問題
Memtables和SSTables緩沖 buffer是在記憶體中寫(“memtable”)， 寫之前先追加一個用于durability的日志中.
但有足夠多寫入以後，這個memtable将被排序然後一次性作為“sstable.”寫入磁盤中，這就提供了近似記憶體性能，因為沒有磁盤的查詢seeks開銷, 同時又避免了純記憶體操作的durability問題.(個人點評 其實Java中的Terracotta早就實作這兩者結合)
B-Trees提供健壯的索引，但是性能很差，一般和其他緩存結合起來。
應用篇
eBay 架構經驗
- 1、 Partition Everything 切分萬物
- 2、 Asynchrony Everywhere 處處異步
- 3、 Automate Everything 全部自動
- 4、 Remember Everything Fails 記錄失敗
- 5、 Embrace Inconsistency 親不同是謂大同
- 6、 Expect (R)evolution 預言演變
- 7、 Dependencies Matter 重視依賴
- 8、 Be Authoritative 獨斷專行
- 9、 Never Enough Data
- 10、Custom Infrastructure 自定義基礎設施
淘寶架構經驗
- 1、适當放棄一緻性
- 2、備份和隔離解決穩定性問題
- 3、分割和異步解決性能問題(類似 eBay 的 Asynchrony Everywhere)
- 4、自動化降低人力成本(類似 eBay 的 Automate Everything)
- 5、産品化管理
Flickr架構經驗
- 使得機器自動建構 (Teach machines to build themselves)
- 使得機器自監控(Teach machines to watch themselves)
- 使得機器自修複(Teach machines to fix themselves)
- 通過流程減少 MTTR (Reduce MTTR by streamlining)
Twitter運維經驗
最近看到的另外一個介紹Twitter技術的視訊[Slides] [Video (GFWed)]，這是Twitter的John Adams在Velocity 2009的一個演講，主要介紹了Twitter在系統運維方面一些經驗。 本文大部分整理的觀點都在Twitter(@xmpp)上發過，這裡全部整理出來并補充完整。
Twitter沒有自己的硬體，都是由NTTA來提供，同時NTTA負責硬體相關的網絡、帶寬、負載均衡等業務，Twitter operations team隻關注核心的業務，包括Performance，Availability，Capacity Planning容量規劃，配置管理等，這個可能跟國内一般的網際網路公司有所差別。
運維經驗
Metrics
Twitter的監控背景幾乎都是圖表(critical metrics)，類似駕駛室的轉速表，時速表，讓操作者可以迅速的了解系統目前的運作狀态。聯想到我們做的類似監控背景，資料很多，但往往還需要浏覽者 做二次分析判斷，像這樣滿屏都是圖表的方法做得還不夠，可以學習下這方面經驗。 據John介紹可以從圖表上看到系統的瓶頸-系統最弱的環節(web, mq, cache, db?)
根據圖表可以科學的制定系統容量規劃，而不是事後救火。
配置管理
每個系統都需要一個自動配置管理系統，越早越好，這條一整理發到Twitter上去之後引起很多回應。
Darkmode
配置界面可以enable/disable 高計算消耗或高I/O的功能，也相當于優雅降級，系統壓力過大時取消一些非核心但消耗資源大的功能。
程序管理
Twitter做了一個”Seppaku” patch, 就是将Daemon在完成了n個requests之後主動kill掉，以保持健康的low memory狀态，這種做法據了解國内也有不少公司是這樣做。
硬體
Twitter将CPU由AMD換成Xeon之後，獲得30%性能提升，将CPU由雙核/4核換成8核之後，減少了40%的CPU, 不過John也說，這種更新不适合自己購買硬體的公司。
代碼協同經驗
Review制度
Twitter有上百個子產品，如果沒有一個好的制度，容易引起代碼修改沖突，并把問題帶給最終使用者。是以Twitter有一強制的source code review制度, 如果送出的代碼的svn comment沒有”reviewed by xxx”, 則pre-commit腳本會讓送出失敗, review過的代碼送出後會通過自動配置管理系統應用到上百台伺服器上。 有@xiaomics同學在Twitter上馬上就問，時間成本能否接受？如果有緊急功能怎麼辦？個人認為緊急修改時有兩人在場，一人修改一人 review也不是什麼難事。
部署管理
從部署圖表可以看到每個釋出版本的CPU及latency變化，如果某個新版本latency圖表有明顯的向上跳躍，則說明該釋出版本存在問題。另外在監控首頁列出各個子產品最後deploy版本的時間，可以清楚的看到代碼庫的現狀。
團隊溝通
Campfire來協同工作，campfire有點像群，但是更适合協同工作。對于Campfire就不做更多介紹，可參考Campfire官方說明。
Cache
- Memcache key hash, 使用FNV hash 代替 MD5 hash，因為FNV更快。
- 開發了Cache Money plugin(Ruby), 給應用程式提供read-through, write-through cache, 就像一個db通路的鈎子，當讀寫資料庫的時候會自動更新cache, 避免了繁瑣的cache更新代碼。
- “Evictions make the cache unreliable for important configuration data”，Twitter使用memcache的一條經驗是，不同類型的資料需放在不同的mc,避免eviction，跟作者前文Memcached資料被踢(evictions>0)現象分析中的一些經驗一緻。
- Memcached SEGVs, Memcached崩潰(cold cache problem)據稱會給這種高度依賴Cache的Web 2.0系統帶來災難，不知道Twitter具體怎麼解決。
- 在Web層Twitter使用了Varnish作為反向代理，并對其評價較高。
雲計算架構
作者認為，金字塔概念最能說明每一層的大小，它也表達了每 個層是依賴前層的消息傳遞。在概念上，硬體是基礎和廣泛層。SaaS層是頂峰，也是最輕層。這種觀點是來自于将購買SaaS的的最終使用者角度。對于一個非 常大的企業内部，PaaS平台層将是頂峰。使用内部開發的軟體的内部各部門将實作他們的頂峰SaaS。還要注意：大小和層位置并不一定等同于重要性。硬體 層可能是最重要的，因為它是所有超過一定點的商品。
硬體層The Hardware Layer
必須考慮容錯和備援，大部分人認為沒有容錯硬體廉價商品。備援和容錯處理在軟體層内，硬體預計要失敗的，當然故障多電源容錯伺服器，RAID磁盤陣列也是必要的。
虛拟層The Virtualization Layer
基于作業系統OS的虛拟化層，虛拟資源能夠線上即時增加拓展，允許供應商提供基礎設施作為服務(SaaS)，VMware，Citrix公司，Sun都提供虛拟化産品。
The IaaS Layer
提 供和控制的基于虛拟層的計算方式，終端使用者能夠精确控制每個虛拟機沒分鐘每小時耗費多少錢。比如提供一個共同的接口，如門戶網站暴露的API，允許最終用 戶建立和配置虛拟機模闆的需求。最終使用者還可以控制何時打開或破壞虛拟機，以及如何在虛拟機互相聯網。在這個領域的主要競争者例子是亞馬遜網絡服務的 EC2，S3和資料庫服務。
The PaaS Layer
這一層的目的是盡量減少部署雲的複雜性和麻煩，最終使用者 利用和開發的這層的API和程式設計語言。兩個很好的例子是谷歌的App Engine 和Force.com平台，在App Engine中，谷歌公開雲存儲，平台和資料庫，以及使用Python和Java程式設計語言的API。開發人員能夠編寫應用程式并部署到這一層中，後端可伸縮性架構設計完全交給谷歌負責，最終使用者完全不必擔心管理基礎設施。Force.com平台類似，但采用了自定義的程式設計語言名為Apex。如果你是一個大型企業尋求内部開發應用的部署，這層是你的頂峰。
The SaaS Layer
如 果您是中小型企業（SME）和大企業不希望開發自己的應用程式時，SaaS的層是你的頂峰（是你将直接面對的）。您隻是進行有興趣地采購如電子郵件或客戶 關系管理服務，這些功能服務已經被供應商開發成功，并部署到雲環境中了，您隻需驗證的應用是否符合你的使用需要，帳單可以基于包月租費等各種形式，，作為 最終使用者的您不會産生開發和維護拓展應用程式軟體的任何成本。越來越多的企業訂閱Salesforce.com和Sugar CRM的SaaS産品。
反模式
單點失敗（Single Point of Failure）
大部分的人都堅持在單一的裝置上部署我們的應用，因為這樣部署的費用會比較低，但是我們要清楚任何的硬體裝置都會有失敗的風險的，這種單點失敗會嚴重的影響使用者體驗甚至是拖垮你的應用，是以除非你的應用能容忍失敗帶來的損失，否則得話應該盡量的避免單點風險，比如做備援，熱備等。
同步調用
同步調用在任何軟體系統中都是不可避免的，但是我們軟體工程師必須明白同步調用給軟體系統帶來的問題。如果我們将應用程式串接起來，那麼系統的可用性就會低于任何一個單一元件的可用性。比如元件A同步調用了元件B，元件A的可用性為99.9%，元件B的可用性為99.9%,那麼元件A同步調用元件B的可用性就是99.9% * 99.9%=99.8%。同步調用使得系統的可用性受到了所有串接元件可用性的影響，是以我們在系統設計的時候應該清楚哪些地方應該同步調用，在不需要同步調用的時候盡量的進行異步的調用（而我這裡所說的異步是一種基于應用的異步，是一種設計上的異步，因為J2EE目前的底層系統出了JMS是異步API以外，其它的API都是同步調用的，是以我們也就不能依賴于底層J2EE平台給我們提供異步性，我們必須從應用和設計的角度引入異步性）
不具備復原能力
雖然對應用的每個版本進行復原能力測試是非常耗時和昂貴的，但是我們應該清楚任何的業務操作都有可能失敗，那麼我們必須為這種失敗作好準備，需要對系統的使用者負責，這就要求系統一定要具有復原的能力，當失敗的時候能進行及時的復原。（說到復原大家可能第一時間想到的是事務的復原，其實這裡的復原應該是一種更寬泛意義的復原，比如我們記錄每一次的失敗的業務操作，這樣在出現錯誤的時候就不是依靠于事務這種技術的手段，而是通過系統本身的復原能力來進行復原失敗業務操作）。
不記錄日志
日志記錄對于一個成熟穩定的系統是非常重要的，如果我們不進行日志記錄，那麼我就很難統計系統的行為。
無切分的資料庫
随着系統規模的慢慢變大，我們就需要打破單一資料的限制，需要對其進行切分。
無切分的應用
系統在規模小的時候，也許感覺不出無切分的應用帶來的問題，但是在目前網際網路高速發展的時代，誰能保證一個小應用在一夜或者是幾夜以後還是小應用呢？說不定哪天，我們就發現應用在突如其來的通路量打擊的支離破碎。是以我們就需要讓我們的系統和我們一樣具有生命力，要想讓系統具有應付大負載的能力，這就要求我們的應用具有很好的伸縮性，這也就要求應用需要被良好的切分，隻有進行了切分，我們才能對單一的部門進行伸縮，如果應用是一塊死闆的話，我們是沒有辦法進行伸縮的。就好比火車一樣，如果火車設計之初就把他們設計為一體的，那麼我們還怎麼對火車的車廂進行裁剪？是以一個沒有切分的應用是一個沒有伸縮性和沒有可用性的應用。
将伸縮性依賴于第三方廠商
如果我們的應用系統的伸縮性依賴于第三方的廠商，比如依賴于資料庫叢集，那麼我們就為系統的伸縮性埋下了一個定時炸彈。因為隻有我們自己最清楚我們自己的應用，我們應該從應用和設計的角度出發去伸縮我們的應用，而不是依賴于第三方廠商的特性。
OLAP
聯機分析處理 (OLAP) 的概念最早是由關系資料庫之父E.F.Codd于1993年提出的，他同時提出了關于OLAP的12條準則。OLAP的提出引起了很大的反響，OLAP作為一類産品同聯機事務處理 (OLTP) 明顯區分開來。
OLAP報表産品最大的難點在哪裡？
目前報表工具最大的難點不在于報表的樣式（如斜線等），樣式雖較繁瑣但并非本質困難。最根本的難點在于業務 部門知道報表代表的真正含義，卻不知道報表的資料統計模型模型；而IT部門通過了解業務部門的描述，在資料庫端進行設定資料統計模型，卻對報表本身所代表 的價值很難了解。
說起來有點深奧，其實并不複雜，OLAP最基本的概念隻有三個：多元觀察、資料鑽取、CUBE運算。
關于CUBE運算：OLAP分析所需的原始資料量是非常龐大的。一個分析模型，往往會涉及數百萬、數千萬條資料，甚至更多；而分析模型中包含多個維資料，這些維又可以由浏覽者作任意的提取組合。這樣的結果就是大量的實時運算導緻時間的延滞。
我們可以設想，一個1000萬條記錄的分析模型，如果一次提取4個次元進行組合分析，那麼實際的運算次數将 達到4的1000次方的數量。這樣的運算量将導緻數十分鐘乃至更長的等待時間。如果使用者對維組合次序進行調整，或增加、或減少某些次元的話，又将是一個重 新的計算過程。
從上面的分析中，我們可以得出結論，如果不能解決OLAP運算效率問題的話，OLAP将是一個毫無實用價值的概念。那麼，一個成熟産品是如何解決這個問題的呢？這涉及到OLAP中一個非常重要的技術——資料CUBE預運算。
一個OLAP模型中，度量資料和維資料我們應該事先确定，一旦兩者确定下來，我們可以對資料進行預先的處理。在正式釋出之前，将資料根據維進行最大
限度的聚類運算，運算中會考慮到各種維組合情況，運算結果将生成一個資料CUBE，并儲存在伺服器上。
這樣，當最終使用者在調閱這個分析模型的時候，就可以直接使用這個CUBE，在此基礎上根據使用者的維選擇和維組合進行複運算，進而達到實時響應的效果。
NOSQL們背後的共有原則
幾個星期之前，我寫了一篇文章描述了常被稱作 NOSQL 的一類新型資料庫的背後驅動。幾個星期之前，我在Qcon上發表了一個演講，其中，我介紹了一個可伸縮（scalable）的 twitter 應用的構模組化式，在我們的讨論中，一個顯而易見的問題就是資料庫的可擴充性問題。要解答這個問題，我試圖尋找隐藏在各種 NOSQL 之後的共有模式，并展示他們是如何解決資料庫可擴充性問題的。在本文中，我将盡力勾勒出這些共有的原則。
假設失效是必然發生的
與我們先前通過昂貴硬體之類的手段盡力去避免失效的手段不同，NOSQL實作都建立在硬碟、機器和網絡都會失效這些假設之上。我們需要認定，我們不 能徹底阻止這些時效，相反，我們需要讓我們的系統能夠在即使非常極端的條件下也能應付這些失效。Amazon S3 就是這種設計的一個好例子。你可以在我最近的文章 Why Existing Databases (RAC) are So Breakable! 中找到進一步描述。哪裡，我介紹了一些來自 Jason McHugh 的講演的面向失效的架構設計的内容（Jason 是在 Amazon 做 S3 相關工作的進階工程師）。
對資料進行分區
通過對資料進行分區，我們最小化了失效帶來的影響，也将讀寫操作的負載分布到了不同的機器上。如果一個節點失效了，隻有該節點上存儲的資料受到影響，而不是全部資料。
儲存同一資料的多個副本
大部分 NOSQL 實作都基于資料副本的熱備份來保證連續的高可用性。一些實作提供了 API，可以控制副本的複制，也就是說，當你存儲一個對象的時候，你可以在對象級指定你希望儲存的副本數。在 GigaSpaces，我們還可以立即複制一個新的副本到其他節點，甚至在必要時啟動一台新機器。這讓我們不比在每個節點上儲存太多的資料副本，進而降低 總存儲量以節約成本。
你還可以控制副本複制是同步還是異步的，或者兩者兼有。這決定了你的叢集的一緻性、可用性與性能三者。對于同步複制，可以犧牲性能保障一緻性和可用 性（寫操作之後的任意讀操作都可以保證得到相同版本的資料，即使是發生失效也會如此）。而最為常見的 GigaSpaces 的配置是同步副本到被分界點，異步存儲到後端存儲。
動态伸縮
要掌控不斷增長的資料，大部分 NOSQL 實作提供了不停機或完全重新分區的擴充叢集的方法。一個已知的處理這個問題的算法稱為一緻哈希。有很多種不同算法可以實作一緻哈希。
一個算法會在節點加入或失效時通知某一分區的鄰居。僅有這些節點受到這一變化的影響，而不是整個叢集。有一個協定用于掌控需要在原有叢集和新節點之間重新分布的資料的變換區間。
另一個（簡單很多）的算法使用邏輯分區。在邏輯分區中，分區的數量是固定的，但分區在機器上的分布式動态的。于是，例如有兩台機器和1000個邏輯 分區，那麼每500個邏輯分區會放在一台機器上。當我們加入了第三台機器的時候，就成了每 333 個分區放在一台機器上了。因為邏輯分區是輕量級的（基于記憶體中的哈希表），分布這些邏輯分區非常容易。
第二種方法的優勢在于它是可預測并且一緻的，而使用一緻哈希方法，分區之間的重新分布可能并不平穩，當一個新節點加入網絡時可能會消耗更長時間。一個使用者在這時尋找正在轉移的資料會得到一個異常。邏輯分區方法的缺點是可伸縮性受限于邏輯分區的數量。
更進一步的關于這一問題的讨論，建議閱讀 Ricky Ho 的文章 NOSQL Patterns 。
查詢支援
在這個方面，不同的實作有相當本質的差別。不同實作的一個共性在于哈希表中的 key/value 比對。一些市縣提供了更進階的查詢支援，比如面向文檔的方法，其中資料以 blob 的方式存儲，關聯一個鍵值對屬性清單。這種模型是一種無預定義結構的（schema-less）存儲，給一個文檔增加或删除屬性非常容易，無需考慮文檔結 構的演進。而 GigaSpaces 支援很多 SQL 操作。如果 SQL查詢沒有指出特定的簡直，那麼這個查詢就會被并行地 map 到所有的節點去，由用戶端完成結果的彙聚。所有這些都是發生在幕後的，使用者代碼無需關注這些。
使用 Map/Reduce 處理彙聚
Map/Reduce 是一個經常被用來進行複雜分析的模型，經常會和 Hadoop 聯系在一起。 map/reduce 常常被看作是并行彙聚查詢的一個模式。大部分 NOSQL 實作并不提供 map/reduce 的内建支援，需要一個外部的架構來處理這些查詢。對于 GigaSpaces 來說，我們在 SQL 查詢中隐含了對 map/reduce 的支援，同時也顯式地提供了一個稱為 executors 的 API 來支援 map/reduce。在質疑模型中，你可以将代碼發送到資料所在地地方，并在該節點上直接運作複雜的查詢。
這方面的更多細節，建議閱讀 Ricky Ho 的文章 Query Processing for NOSQL DB 。
基于磁盤的和記憶體中的實作
NOSQL 實作分為基于檔案的方法和記憶體中的方法。有些實作提供了混合模型，将記憶體和磁盤結合使用。兩類方法的最主要差別在于每 GB 成本和讀寫性能。
最近，斯坦福的一項稱為“The Case for RAMCloud”的調查，對磁盤和記憶體兩種方法給出了一些性能和成本方面的有趣的比較。總體上說，成本也是性能的一個函數。對于較低性能的實作，磁盤方 案的成本遠低于基于記憶體的方法，而對于高性能需求的場合，記憶體方案則更加廉價。
記憶體雲的顯而易見的缺點就是機關容量的高成本和高能耗。對于這些名額，記憶體雲會比純粹的磁盤系統差50到100 倍，比使用閃存的系統差5-10倍（典型配置情況和名額參見參考文獻[1]）。記憶體雲同時還比基于磁盤和閃存的系統需要更多的機房面積。這樣，如果一個應 用需要存儲大量的廉價資料，不需要高速通路，那麼，記憶體雲将不是最佳選擇。
然而，對于高吞吐量需求的應用，記憶體雲将更有競争力。當 使用每次操作的成本和能量作為衡量因素的時候，記憶體雲的效率是傳統硬碟系統的 100 到 1000 倍，是閃存系統的 5-10 倍。是以，對于高吞吐量需求的系統來說，記憶體雲不僅提供了高性能，也提供了高能源效率。同時，如果使用 DRAM 晶片提供的低功耗模式，也可以降低記憶體雲的功耗，特别是在系統空閑的時候。此外，記憶體雲還有一些缺點，一些記憶體雲無法支援需要将資料在 多個資料中心之間進行資料複制。對于這些環境，更新的時延将主要取決于資料中心間資料傳輸的時間消耗，這就喪失了記憶體雲的時延方面的優勢。此外，跨資料中 心的資料複制會讓記憶體雲資料一緻性更能難保證。不過，記憶體雲仍然可以在誇資料中心的情況下提供低延遲時間的讀通路。
僅僅是炒作?
近來我見到的最多的問題就是 “NOSQL 是不是就是炒作？” 或 “NOSQL 會不會取代現在的資料庫？”
我的回答是——NOSQL 并非始于今日。很多 NOSQL 實作都已經存在了十多年了，有很多成功案例。我相信有很多原因讓它們在如今比以往更受歡迎了。首先是由于社會化網絡和雲計算的發展，一些原先隻有很高端的 組織才會面臨的問題，如今已經成為普遍問題了。其次，已有的方法已經被發現無法跟随需求一起擴充了。并且，成本的壓力讓很多組織需要去尋找更高成本效益的方 案，并且研究證明基于普通廉價硬體的分布式存儲解決方案甚至比現在的高端資料庫更加可靠。（進一步閱讀）所有這些導緻了對這類“可伸縮性優先資料庫”的需求。這裡，我引用 AWS團隊的接觸工程師、VP， James Hamilton 在他的文章 One Size Does Not Fit All 中的一段話：
“伸縮性優先應用是那些必須具備無限可伸縮性的應用，能夠不受限制的擴充比更豐富的功能更加重要。這些應用包括很多需要高 可伸縮性的網站，如 Facebook, MySpace, Gmail, Yahoo 以及 Amazon.com。有些站點實際上使用了關系型資料庫，而大部分實際上并未使用。這些服務的共性在于可擴充性比功能公衆要，他們無法泡在一個單一的 RDBMS 上。”
總結一下——我認為，現有的 SQL 資料庫可能不會很快淡出曆史舞台，但同時它們也不能解決世上的所有問題。NOSQL 這個名詞現在也變成了 Not Only SQL，這個變化表達了我的觀點。
附
本書不求利，隻圖學術之便。感謝諸位大牛寫了那麼多的資料，如果您不願意被引用，學生會重寫相應的章節。
引用網志多篇，由于涵蓋太廣難以一一校隊，特此緻歉。
感謝
感謝Jdon,dbanotes,infoq和Timyang.您們分享和撰寫了那麼多有用的資料。
版本志
V0.1版本在2010.2.21釋出，提供了本書的主題架構
v0.2版本在2010.2.24釋出，因為一些外界原因，提前釋出。完善各個示例，勘誤，翻譯部分内容。
v0.3版本将在3月份或之後釋出
引用
http://www.jdon.com/jivejdon/thread/37999
http://queue.acm.org/detail.cfm?id=1413264
http://www.dbanotes.net/arch/five-minute_rule.html
http://www.infoq.com/cn/news/2009/09/Do-Not-Delete-Data
http://www.infoq.com/cn/news/2010/02/ec2-oversubscribed
http://timyang.net/architecture/consistent-hashing-practice
http://en.wikipedia.org/wiki/Gossip_protocol
http://horicky.blogspot.com/2009/11/nosql-patterns.html
http://snarfed.org/space/transactions_across_datacenters_io.html
http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf
http://en.wikipedia.org/wiki/Distributed_hash_table
http://hi.baidu.com/knuthocean/blog/item/cca1e711221dcfcca6ef3f1d.html
http://zh.wikipedia.org/wiki/MapReduce
http://labs.google.com/papers/mapreduce.html
http://nosql-database.org/
http://www.rackspacecloud.com/blog/2009/11/09/nosql-ecosystem/
http://www.infoq.com/cn/news/2008/02/ruby-mapreduce-skynet
http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf
http://labs.google.com/papers/bigtable.html
http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
http://www.rackspacecloud.com/blog/2009/11/09/nosql-ecosystem/
http://timyang.net/tech/twitter-operations/
http://blog.s135.com/read.php?394
http://www.programmer.com.cn/1760/