分布式K—V系統(tǒng)概述

1、提及分布式key-value存儲(chǔ)系統(tǒng)， Memcached, Voldemort, Cassandra,包括淘寶最近開(kāi)源，我們一直在使用的Tair系統(tǒng)，相信大家都不會(huì)覺(jué)得陌生。本文會(huì)從Tair入手，介紹分析一下傳統(tǒng)分布式鍵-值存儲(chǔ)系統(tǒng)的原理，架構(gòu)和使用技術(shù)。錯(cuò)誤之處，還望大家指正。先看一下Tair的架構(gòu)：乍一看，會(huì)發(fā)現(xiàn)Tair的系統(tǒng)架構(gòu)和TFS一樣，都基于了Google的GFS設(shè)計(jì)，主要包括三部分：其中ConfigServer主要負(fù)責(zé)管理維護(hù)DataServer以及和Client端的部分通信；DataServer則是存儲(chǔ)對(duì)象的地方，數(shù)據(jù)的增/刪/更新都在這里進(jìn)行；Client端向服務(wù)器請(qǐng)求插入

2、/刪除/更新數(shù)據(jù)；看完上面的介紹，你可能會(huì)有以下幾個(gè)疑問(wèn)：1.configServer的真正工作是什么？2. DataServer如何存儲(chǔ)數(shù)據(jù)？3. Client端只需要和dataServer通信嗎?4. 如何實(shí)現(xiàn)分布式？關(guān)于上述第四點(diǎn)如何實(shí)現(xiàn)分布式鍵-值存儲(chǔ)系統(tǒng)，我們又要從分布式系統(tǒng)CAP要求出發(fā)：數(shù)據(jù)一致性，系統(tǒng)可用性，系統(tǒng)分區(qū)寬容度（說(shuō)白了就是如何解決分布式下Server端機(jī)器的增減和容錯(cuò)問(wèn)題）。這幾個(gè)問(wèn)題才是分布式應(yīng)用中最棘手最重要的問(wèn)題。接下來(lái)，依據(jù)個(gè)人的理解，結(jié)合Tair相關(guān)知識(shí)，對(duì)上述問(wèn)題做一下介紹。首先，tair中的configServer在物理上是以Master-Slaver

3、形式部署，作用大家都很清楚，在Master不可用或者宕機(jī)的時(shí)候，slaver轉(zhuǎn)為master對(duì)外提供服務(wù)。那么是不是configServer不能對(duì)外部提供就說(shuō)明所有的客戶端都不再可用？答案是否定的，因?yàn)閏onfigServer在tair中扮演的是一個(gè)非常輕量級(jí)的角色，如何理解？為解決這個(gè)問(wèn)題，我們需要解決另外一個(gè)問(wèn)題，如何保證來(lái)自客戶端的數(shù)據(jù)在tair中均勻的分布，也就是如何對(duì)dataServer進(jìn)行負(fù)載均衡，另外，如何保證dataServer的數(shù)據(jù)不會(huì)失效？一個(gè)簡(jiǎn)單的模型就是取模，通過(guò)對(duì)key的hash值對(duì)機(jī)器個(gè)數(shù)取模，將其存儲(chǔ)到余數(shù)對(duì)應(yīng)的機(jī)器上。比如有a,b,c,d四個(gè)數(shù)據(jù)，3臺(tái)機(jī)器，ha

4、sh取3模后a,c存儲(chǔ)到機(jī)器1，b存儲(chǔ)到機(jī)器2，d存儲(chǔ)到機(jī)器3上。貌似我們已經(jīng)解決了問(wèn)題。經(jīng)過(guò)hash和取模操作后，在大數(shù)據(jù)量情況下，最后數(shù)據(jù)在三臺(tái)機(jī)器上的分布肯定是比較均勻的，達(dá)到負(fù)載均衡的目的了？但是，分布式環(huán)境下，當(dāng)機(jī)器量比較多時(shí)總是不能避免新機(jī)器加入或者某臺(tái)正在使用的機(jī)器不可用了，如果是某臺(tái)機(jī)器不可用，那來(lái)自客戶端對(duì)它的所有請(qǐng)求都會(huì)命中失效；這個(gè)時(shí)候唯一的辦法就是將所有的數(shù)據(jù)重新hash分配，因?yàn)槿∧７帜缸兓耍僭O(shè)你這個(gè)時(shí)候?qū)λ袛?shù)據(jù)是有備份的），如果數(shù)據(jù)量非常大，此項(xiàng)工作也是極其浪費(fèi)時(shí)間的，客戶端不可服務(wù)時(shí)間加長(zhǎng)；如果是因?yàn)閿?shù)據(jù)量增大，需要新增機(jī)器到這個(gè)集群中，我們面臨的問(wèn)題一樣頭

5、疼無(wú)助。問(wèn)題在哪里？因?yàn)槲覀兠看稳∧５膯挝皇菣C(jī)器個(gè)數(shù)，而機(jī)器個(gè)數(shù)是在不停變化的。所以簡(jiǎn)單的解決方案就是不要以機(jī)器個(gè)數(shù)取模，取一個(gè)恒定不變的值，但是如何應(yīng)對(duì)動(dòng)態(tài)變化的數(shù)據(jù)？又如何將數(shù)據(jù)與機(jī)器對(duì)應(yīng)起來(lái)呢？二次轉(zhuǎn)換是不可避免的了，看來(lái)這個(gè)解決方案不太可行。到這里，可能你會(huì)問(wèn)，memcached,cassandra是如何處理這種問(wèn)題的呢？答案是Consistent Hashing：一致性hash簡(jiǎn)單的說(shuō)就是把數(shù)據(jù)對(duì)象和服務(wù)器(ip or name)都映射到一個(gè)32位的數(shù)值空間，即0232-1，然后將這個(gè)范圍首尾相連，組成一個(gè)圓環(huán)。這樣，無(wú)論是數(shù)據(jù)還是機(jī)器都被映射到如下的圓環(huán)上。然后以每個(gè)數(shù)據(jù)為起點(diǎn)，沿

6、順時(shí)針?lè)较蛘业诫x其最近的下一個(gè)服務(wù)器節(jié)點(diǎn)，那么這個(gè)數(shù)據(jù)就存儲(chǔ)到這臺(tái)機(jī)器上面；一致性，簡(jiǎn)單理解就是數(shù)據(jù)和服務(wù)器同時(shí)hash。如下圖所示然后，假設(shè)node2不可用，按照上述原則，只需要將node1和node2之間的數(shù)據(jù)遷移到node4上即可；如果在node2和node4之間添加一個(gè)節(jié)點(diǎn)node5，只需要將node4和node5之間的數(shù)據(jù)遷移到node5上，這樣，一來(lái)保證其他所有結(jié)點(diǎn)都是可用的（當(dāng)然如果要保證當(dāng)前正在遷移的節(jié)點(diǎn)也可用，只需要保證在遷移完成之前數(shù)據(jù)不刪除即可）；另外一方面，我們需要遷移的數(shù)據(jù)量只是其中的一小部分而已，對(duì)性能要求不再那么高。然而，當(dāng)前這個(gè)模型還是存在一個(gè)問(wèn)題,如何保證數(shù)據(jù)

7、在各個(gè)節(jié)點(diǎn)上分布平衡？一種完善方案是對(duì)每個(gè)節(jié)點(diǎn)設(shè)置多個(gè)虛擬的結(jié)點(diǎn)，以其ip+后綴hash均勻映射到圓環(huán)的各處。這樣原本可能存儲(chǔ)很多數(shù)據(jù)的節(jié)點(diǎn)就有可能被虛擬節(jié)點(diǎn)分成，從而達(dá)到一定的數(shù)據(jù)平衡。 Consistent Hash實(shí)現(xiàn)其實(shí)不復(fù)雜，可以參照以下例子：java view plaincopyprint?1. importjava.util.Collection;2. importjava.util.SortedMap;3. importjava.util.TreeMap;4. publicclassConsistentHash5. privatefinalHashFunctionhashFun

8、ction;6. privatefinalintnumberOfReplicas;7. privatefinalSortedMapcircle=newTreeMap();8. 9. publicConsistentHash(HashFunctionhashFunction,intnumberOfReplicas,10. Collectionnodes)11. this.hashFunction=hashFunction;12. this.numberOfReplicas=numberOfReplicas;13. 14. for(Tnode:nodes)15. add(node);16. 17.

9、 18. 19. publicvoidadd(Tnode)20. for(inti=0;inumberOfReplicas;i+)21. circle.put(hashFunction.hash(node.toString()+i),node);22. 23. 24. 25. publicvoidremove(Tnode)26. for(inti=0;inumberOfReplicas;i+)27. circle.remove(hashFunction.hash(node.toString()+i);28. 29. 30. 31. publicTget(Objectkey)32. if(cir

10、cle.isEmpty()33. returnnull;34. 35. inthash=hashFunction.hash(key);36. if(!circle.containsKey(hash)37. SortedMaptailMap=circle.tailMap(hash);38. hash=tailMap.isEmpty()?circle.firstKey():tailMap.firstKey();39. 40. returncircle.get(hash);41. 42. 了解了傳統(tǒng)應(yīng)用的分布式負(fù)載均衡算法，但是查看tair源碼你會(huì)發(fā)現(xiàn)它其實(shí)沒(méi)有用到一致性hash算法；它采用了另外一

11、種解決方案。那就是ConfigServer。它通過(guò)configServer生成關(guān)于各個(gè)dataServer的對(duì)照表。對(duì)照表的數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的key和各臺(tái)dataServer的ip映射表；當(dāng)然，為了保證容錯(cuò)，每個(gè)數(shù)據(jù)除了在主dataServer上存儲(chǔ)數(shù)據(jù)，還會(huì)存儲(chǔ)在多個(gè)副dataServer上，這樣，如果主dataServer失效，那么副dataServer就升級(jí)成為主dataServer，主-備之間切換變得很容易，所以在對(duì)照表中，還會(huì)有多列ip列表對(duì)應(yīng)該數(shù)據(jù)在副dataServer上的存儲(chǔ)節(jié)點(diǎn)；此外，一個(gè)對(duì)照表需要一個(gè)版本標(biāo)識(shí)，以便客戶端更新；每次configServer生成一個(gè)新的對(duì)照表后，

12、會(huì)通過(guò)心跳方式將新的對(duì)照表同步到各臺(tái)dataServer。而客戶端在第一次連接tair時(shí)會(huì)先去configServer請(qǐng)求，configServer將最新的對(duì)照表返回給客戶端，客戶端將其緩存到本地。當(dāng)client有數(shù)據(jù)請(qǐng)求時(shí)，只會(huì)去本地對(duì)照表查找對(duì)應(yīng)的dataServer，然后和定位的dataServer通信，所以之前我們說(shuō)即便是configServer暫時(shí)不可用，client端依舊可用。在這整個(gè)過(guò)程中，client和server端的通信都是通過(guò)基于TCP的Socket進(jìn)行的，所以只要你的客戶端是支持Socket的編程語(yǔ)言，都可以使用tair。當(dāng)然，在這整一個(gè)過(guò)程當(dāng)中，會(huì)有一些問(wèn)題：當(dāng)data

13、Server發(fā)生變化時(shí)，configServer會(huì)重新生成新的對(duì)照表，如果此時(shí)client端請(qǐng)求數(shù)據(jù)操作，一種情況是原本的dataServer不可用，此時(shí)client端會(huì)主動(dòng)去configServer請(qǐng)求新的對(duì)照表版本；如果此dataServer依舊可用，但是在處理來(lái)自dataServer的response時(shí)出校驗(yàn)client端和server端的對(duì)照表版本不一致時(shí)，client也會(huì)主動(dòng)去configServer請(qǐng)求更新對(duì)照表。然而，即便是這樣，我們的tair似乎還是不滿足一點(diǎn)：數(shù)據(jù)在各個(gè)節(jié)點(diǎn)上平衡。一致性哈希采用的是虛擬結(jié)點(diǎn)來(lái)改善不平衡數(shù)據(jù)的問(wèn)題，而tair和我們知道的Cassandra都是通

14、過(guò)分析各個(gè)節(jié)點(diǎn)的負(fù)載情況，從而調(diào)整節(jié)點(diǎn)的數(shù)據(jù)平衡問(wèn)題；對(duì)于ConfigServer和它的作用我們已經(jīng)說(shuō)的差不多，接下來(lái)看看DataServer：DataServer其實(shí)也是Master_Slaver復(fù)制模式。Master除了處理來(lái)自客戶端的數(shù)據(jù)操作請(qǐng)求，和configServer通信，聽(tīng)從configServer調(diào)遣（比如各個(gè)節(jié)點(diǎn)間數(shù)據(jù)遷移以達(dá)到盡可能的負(fù)載均衡），還要負(fù)責(zé)將數(shù)據(jù)更新操作復(fù)制到它的slaver上。當(dāng)然，dataServer需要做到非常重要的一點(diǎn)：高效的讀寫數(shù)據(jù)性能。還是先來(lái)看一下tair存儲(chǔ)引擎是如何實(shí)現(xiàn)的：tair將存儲(chǔ)引擎抽象化，也就是說(shuō)你可以在tair中使用自己實(shí)現(xiàn)的存儲(chǔ)

15、引擎，或者是換成mysql（當(dāng)然性能不一定能保證）。目前tair主要有兩個(gè)存儲(chǔ)引擎：基于內(nèi)存的key-value存儲(chǔ)mdb和基于文件的key-value存儲(chǔ)fdb。Mdb實(shí)現(xiàn)類似memcached，使用到了slab內(nèi)存管理技術(shù)，每個(gè)slab一個(gè)內(nèi)存塊，包含了多個(gè)chunk，通過(guò)slab技術(shù)，減少了內(nèi)存碎片，大大提高了內(nèi)存使用率。但是mdb優(yōu)于memcached的優(yōu)點(diǎn)是它支持shared memory，所以即便是重啟服務(wù)，數(shù)據(jù)在共享內(nèi)存中，也不會(huì)使命中率降低很多，而memcached一旦重啟，之前所有數(shù)據(jù)都會(huì)miss。Fdb是一個(gè)高效的持久化存儲(chǔ)引擎，采用了樹(shù)型的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)索引。cpp v

16、iew plaincopyprint?1. typedefstruct_item_index 2. 3. uint32_tleft; 4. uint32_tright; 5. uint64_tsize:24; 6. uint64_toffset:40; 7. uint64_thashcode; 8. item_index;為了快速訪問(wèn)到文件數(shù)據(jù)，首先以數(shù)據(jù)key的哈希值索引數(shù)據(jù)，同時(shí)將索引文件和數(shù)據(jù)文件隔離開(kāi)，然后將索引文件放到內(nèi)存中，減少io操作。這里可以看一下Cassandra數(shù)據(jù)的本地持久化實(shí)現(xiàn)原理：它將客戶端提交的數(shù)據(jù)寫到內(nèi)存中，當(dāng)內(nèi)存中數(shù)據(jù)達(dá)到一定量時(shí)才會(huì)寫入到本地文件中，然后有后臺(tái)合并進(jìn)程負(fù)責(zé)對(duì)這些文件的合并。在對(duì)磁盤數(shù)據(jù)進(jìn)行檢索時(shí)會(huì)先去內(nèi)存中查找，沒(méi)有才到本地文件中搜索。為了快速查找文件，Cassandra使用了搜索引擎中用到的詞典技術(shù)，將所有數(shù)據(jù)的key緩存到內(nèi)存中，這樣可以通過(guò)查詢?cè)~典快速訪問(wèn)到數(shù)據(jù)在磁盤中的位置。此外，Cassandra還用到了很多非常優(yōu)秀的開(kāi)源技術(shù)，比如我之前介紹的ZooKeeper，還有用于檢測(cè)故障的Accrual，非堵塞NIO技術(shù)等。由此可見(jiàn)，很