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