NoSQL在過去的一年里，逐漸已經(jīng)成為了家喻戶曉的東西，我（54chen）自從去年開始人人網(wǎng)的NoSQL系統(tǒng)Nuclear的研發(fā)以來，一直看NoSQL越來越熱，越來越引來大家的圍觀。受InfoQ中文站編輯之托，特作此文，一來作為過去一年的總結，二來希望對NoSQL系統(tǒng)在國內(nèi)的發(fā)展和推廣盡綿薄之力。
NoSQL背后的兩種模式
NoSQL其實并不是什么妖魔鬼怪，相反，NoSQL的真諦其實應該是Not Only SQL，其產(chǎn)生背景是在數(shù)據(jù)量和訪問量逐漸增大的情況下下，人為地去添加機器或者切分數(shù)據(jù)到不同的機器，變得越來越困難，人力成本越來越高，于是便開始有了這樣的項目，它們的本意是提高數(shù)據(jù)存儲的自動化程度，減少人為干預的時間，讓負載更加均勻等。在國際上，真正的代表之作有來自Google的 BigTable 和Amazon 的Dynamo，他們分別使用了不同的基本原理。
MapReduce
這是歷史最久的一種模型，典型的代表是BigTable。Map表示映射，Reduce表示化簡。MapReduce通過把對數(shù)據(jù)集的大規(guī)模操作分發(fā)給網(wǎng)絡上的每個節(jié)點實現(xiàn)可靠性（Map）；每個節(jié)點會周期性地把完成的工作和狀態(tài)的更新報告回來（Reduce）。大多數(shù)分布式運算可以抽象為MapReduce操作。Map是把輸入Input分解成中間的Key/Value對，Reduce把Key/Value合成最終輸出Output。這兩個函數(shù)由程序員提供給系統(tǒng)，下層設施把Map和Reduce操作分布在集群上運行。
Dynamo
這里我把Dynamo專門歸納成為了一種，其原因是它與MapReduce有很大的不同，自成一派。先說一下歷史，Amazon于2006年推出了自己的云存儲服務S3，2007年其CTO公布了S3的設計方案，從此江湖中就不再太平了，開源項目一個個如雨后春筍般地出現(xiàn)了。比較常見的有Facebook開發(fā)的Cassandra（如果沒有記錯，在去年瀏覽他們項目網(wǎng)頁的時候，上面還寫著他們之中的一個開發(fā)人員是Dynamo的設計人員，現(xiàn)在風頭緊，去掉了），還有Linkedin的voldemort，而在國內(nèi)話，有豆瓣網(wǎng)的beansDB，人人網(wǎng)的nuclear等等。這里我主要討論的也是Dynamo的方案細節(jié)。
入門基礎
Dynamo的意思是發(fā)電機，顧名思義，這一整套的方案都像發(fā)電機一樣，源源不斷地提供服務，永不間斷。以下內(nèi)容看上去有點教條，但基本上如果你要理解原理，這每一項都是必須知道的。
CAP原則
先來看歷史，Eric A. Brewer教授，Inktomi公司的創(chuàng)始人，也是berkeley大學的計算機教授，Inktomi是雅虎搜索現(xiàn)在的臺端技術核心支持。最主要的是，他們 （Inktomi公司）在最早的時間里，開始研究分布計算。CAP原則的提出，可以追溯到2000年的時候（可以想象有多么早�。珺rewer教授在一次談話中，基于他運作Inktomi以及在伯克利大學里的經(jīng)驗，總結出了CAP原則（文末參考資料中有其演講資料鏈接）。圖一是來自Brewer教授當年所畫的圖：
圖一：CAP原則當年的PPT
Consistency（一致性）：即數(shù)據(jù)一致性，簡單的說，就是數(shù)據(jù)復制到了N臺機器，如果有更新，要N機器的數(shù)據(jù)是一起更新的。
Availability（可用性）：好的響應性能，此項意思主要就是速度。
Partition tolerance（分區(qū)容錯性）：這里是說好的分區(qū)方法，體現(xiàn)具體一點，簡單地可理解為是節(jié)點的可擴展性。
定理：任何分布式系統(tǒng)只可同時滿足二點，沒法三者兼顧。
忠告：架構師不要將精力浪費在如何設計能滿足三者的完美分布式系統(tǒng)，而是應該進行取舍。
DHT——分布式哈希表
DHT（Distributed Hash Table，分布式哈希表），它是一種分布式存儲尋址方法的統(tǒng)稱。就像普通的哈希表，里面保存了key與value的對應關系，一般都能根據(jù)一個key去對應到相應的節(jié)點，從而得到相對應的value。
這里隨帶一提，在DHT算法中，一致性哈希作為第一個實用的算法，在大多數(shù)系統(tǒng)中都使用了它。一致性哈�；窘鉀Q了在P2P環(huán)境中最為關鍵的問題——如何在動態(tài)的網(wǎng)絡拓撲中分布存儲和路由。每個節(jié)點僅需維護少量相鄰節(jié)點的信息，并且在節(jié)點加入/退出系統(tǒng)時，僅有相關的少量節(jié)點參與到拓撲的維護中。至于一致性哈希的細節(jié)就不在這里詳細說了，要指明的一點是，在Dynamo的數(shù)據(jù)分區(qū)方式之后，其實內(nèi)部已然是一個對一致性哈希的改造了。
進入Dynamo的世界
有了上面一章里的兩個基礎介紹之后，我們開始進入Dynamo的世界。
Dynamo的數(shù)據(jù)分區(qū)與作用
在Dynamo的實現(xiàn)中提到一個關鍵的東西，就是數(shù)據(jù)分區(qū)。 假設我們的數(shù)據(jù)的key的范圍是0到2的64次方（不用懷疑你的數(shù)據(jù)量會超過它，正常甚至變態(tài)情況下你都是超不過的，甚至像伏地魔等其他類Dynamo系統(tǒng)是使用的 2的32次方），然后設置一個常數(shù)，比如說1000，將我們的key的范圍分成1000份。然后再將這1000份key的范圍均勻分配到所有的節(jié)點（s個節(jié)點），這樣每個節(jié)點負責的分區(qū)數(shù)就是1000/s份分區(qū)。
如圖二，假設我們有A、B、C三臺機器，然后將我們的分區(qū)定義了12個。
圖二：三個節(jié)點分12個區(qū)的數(shù)據(jù)的情況
因為數(shù)據(jù)是均勻離散到這個環(huán)上的（有人開始會認為數(shù)據(jù)的key是從1、2、3、4……這樣子一直下去的，其實不是的，哈希計算出來的值，都是一個離散的結果），所以我們每個分區(qū)的數(shù)據(jù)量是大致相等的。從圖上我們可以得出，每臺機器都分到了三個分區(qū)里的數(shù)據(jù)，并且因為分區(qū)是均勻的，在分區(qū)數(shù)量是相當大的時候，數(shù)據(jù)的分布會更加的均勻，與此同時，負載也被均勻地分開了（當然了，如果硬要說你的負載還是只集中在一個分區(qū)里，那就不是在這里要討論的問題了，有可能是你的哈希函數(shù)是不是有什么樣的問題了）。
為什么要進行這樣的分布呢，分布的好處在于，在有新機器加入的時候，只需要替換原有分區(qū)即可，如圖三所示：
圖三：加入一個新的節(jié)點D的情況
同樣是圖二里的情況，12個分區(qū)分到ABC三個節(jié)點，圖三中就是再進入了一個新的節(jié)點D，從圖上的重新分布情況可以得出，所有節(jié)點里只需要轉(zhuǎn)移四分之一的數(shù)據(jù)到新來的節(jié)點即可，同時，新節(jié)點的負載也伴隨分區(qū)的轉(zhuǎn)移而轉(zhuǎn)移了（這里的12個分區(qū)太少了，如果是1200個分區(qū)甚至是12000個分區(qū)的話，這個結論就是正確的了，12個分區(qū)只為演示用）。
從Dynamo的NRW看CAP法則
在Dynamo系統(tǒng)中，第一次提出來了NRW的方法。
N：復制的次數(shù)；
R：讀數(shù)據(jù)的最小節(jié)點數(shù)；
W：寫成功的最小分區(qū)數(shù)。
這三個數(shù)的具體作用是用來靈活地調(diào)整Dynamo系統(tǒng)的可用性與一致性。
舉個例子來說，如果R=1的話，表示最少只需要去一個節(jié)點讀數(shù)據(jù)即可，讀到即返回，這時是可用性是很高的，但并不能保證數(shù)據(jù)的一致性，如果說W同時為1的 話，那可用性更新是最高的一種情況，但這時完全不能保障數(shù)據(jù)的一致性，因為在可供復制的N個節(jié)點里，只需要寫成功一次就返回了，也就意味著，有可能在讀的這一次并沒有真正讀到需要的數(shù)據(jù)（一致性相當?shù)牟缓茫�。如果W=R=N=3的話，也就是說，每次寫的時候，都保證所有要復制的點都寫成功，讀的時候也是都讀到，這樣子讀出來的數(shù)據(jù)一定是正確的，但是其性能大打折扣，也就是說，數(shù)據(jù)的一致性非常的高，但系統(tǒng)的可用性卻非常低了。如果R + W > N能夠保證我們“讀我們所寫”，Dynamo推薦使用322的組合。
Dynamo系統(tǒng)的數(shù)據(jù)分區(qū)讓整個網(wǎng)絡的可擴展性其實是一個固定值（你分了多少區(qū)，實際上網(wǎng)絡里擴展節(jié)點的上限就是這個數(shù)），通過NRW來達到另外兩個方 向上的調(diào)整。
Dynamo的一些增加可用性的補救
針對一些經(jīng)�？赡艹霈F(xiàn)的問題，Dynamo還提供了一些解決的方法。
第一個是hinted handoff數(shù)據(jù)的加入：在一個節(jié)點出現(xiàn)臨時性故障時，數(shù)據(jù)會自動進入列表中的下一個節(jié)點進行寫操作，并標記為handoff數(shù)據(jù)，在收到通知需要原節(jié)點恢復時重新把數(shù)據(jù)推回去。這能使系統(tǒng)的寫入成功大大提升。
第二個是向量時鐘來做版本控制：用一個向量（比如說[a,1]表示這個數(shù)據(jù)在a節(jié)點第一次寫入）來標記數(shù)據(jù)的版本，這樣在有版本沖突的時候，可以追溯到出現(xiàn)問題的地方。這可以使數(shù)據(jù)的最終一致成為可能。（Cassandra未用vector clock，而只用client timestamps也達到了同樣效果。）
第三個是Merkle tree來提速數(shù)據(jù)變動時的查找：使用Merkle tree為數(shù)據(jù)建立索引，只要任意數(shù)據(jù)有變動，都將快速反饋出來。
第四個是Gossip協(xié)議：一種通訊協(xié)議，目標是讓節(jié)點與節(jié)點之間通信，省略中心節(jié)點的存在，使網(wǎng)絡達到去中心化。提高系統(tǒng)的可用性。
后記
Dynamo的理論對CAP原則里的可擴展性做到了很方便的實現(xiàn)，通過創(chuàng)造性的NRW來平衡系統(tǒng)的可用性和一致性，增加了系統(tǒng)在實際情況下遇到問題的可選擇方案�？梢韵嘞�，在NoSQL的道路上，這只是個開端，在分布式計算的道路上，已經(jīng)是MapReduce之后的再次革命。
喜歡 
頂
難過
囧
圍觀
無聊
