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

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

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

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

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

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

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

7、在各個(gè)節(jié)點(diǎn)上分布平衡？一種完善方案是對每個(gè)節(jié)點(diǎn)設(shè)置多個(gè)虛擬的結(jié)點(diǎn)，以其ip+后綴hash均勻映射到圓環(huán)的各處。這樣原本可能存儲很多數(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源碼你會發(fā)現(xiàn)它其實(shí)沒有用到一致性hash算法；它采用了另外一

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

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

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

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

15、引擎，或者是換成mysql（當(dāng)然性能不一定能保證）。目前tair主要有兩個(gè)存儲引擎：基于內(nèi)存的key-value存儲mdb和基于文件的key-value存儲fdb。Mdb實(shí)現(xiàn)類似memcached，使用到了slab內(nèi)存管理技術(shù)，每個(gè)slab一個(gè)內(nèi)存塊，包含了多個(gè)chunk，通過slab技術(shù)，減少了內(nèi)存碎片，大大提高了內(nèi)存使用率。但是mdb優(yōu)于memcached的優(yōu)點(diǎn)是它支持shared memory，所以即便是重啟服務(wù)，數(shù)據(jù)在共享內(nèi)存中，也不會使命中率降低很多，而memcached一旦重啟，之前所有數(shù)據(jù)都會miss。Fdb是一個(gè)高效的持久化存儲引擎，采用了樹型的數(shù)據(jù)結(jié)構(gòu)存儲數(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;為了快速訪問到文件數(shù)據(jù)，首先以數(shù)據(jù)key的哈希值索引數(shù)據(jù)，同時(shí)將索引文件和數(shù)據(jù)文件隔離開，然后將索引文件放到內(nèi)存中，減少io操作。這里可以看一下Cassandra數(shù)據(jù)的本地持久化實(shí)現(xiàn)原理：它將客戶端提交的數(shù)據(jù)寫到內(nèi)存中，當(dāng)內(nèi)存中數(shù)據(jù)達(dá)到一定量時(shí)才會寫入到本地文件中，然后有后臺合并進(jìn)程負(fù)責(zé)對這些文件的合并。在對磁盤數(shù)據(jù)進(jìn)行檢索時(shí)會先去內(nèi)存中查找，沒有才到本地文件中搜索。為了快速查找文件，Cassandra使用了搜索引擎中用到的詞典技術(shù)，將所有數(shù)據(jù)的key緩存到內(nèi)存中，這樣可以通過查詢詞典快速訪問到數(shù)據(jù)在磁盤中的位置。此外，Cassandra還用到了很多非常優(yōu)秀的開源技術(shù)，比如我之前介紹的ZooKeeper，還有用于檢測故障的Accrual，非堵塞NIO技術(shù)等。由此可見，很