海量存储系列下--转载，值得一读
海量存儲(chǔ)系列之八
http://qing.blog.sina.com.cn/1765738567/693f0847330008ii.html
首先來回答一個(gè)問題：為什么在磁盤中要使用b+樹來進(jìn)行文件存儲(chǔ)呢？
原因還是因?yàn)闃涞母叨鹊偷镁壒?#xff0c;磁盤本身是一個(gè)順序讀寫快，隨機(jī)讀寫慢的系統(tǒng)，那么如果想高效的從磁盤中找到數(shù)據(jù)，勢(shì)必需要滿足一個(gè)最重要的條件：減少尋道次數(shù)。
我們以平衡樹為例進(jìn)行對(duì)比，就會(huì)發(fā)現(xiàn)問題所在了：
?
先上個(gè)圖
?
?
?
?
?
這是個(gè)平衡樹，可以看到基本上一個(gè)元素下只有兩個(gè)子葉節(jié)點(diǎn)
?
?
抽象的來看，樹想要達(dá)成有效查找，勢(shì)必需要維持如下一種結(jié)構(gòu)：
樹的子葉節(jié)點(diǎn)中，左子樹一定小于等于當(dāng)前節(jié)點(diǎn)，而當(dāng)前節(jié)點(diǎn)的右子樹則一定大于當(dāng)前節(jié)點(diǎn)。只有這樣，才能夠維持全局有序，才能夠進(jìn)行查詢。
?
這也就決定了只有取得某一個(gè)子葉節(jié)點(diǎn)后，才能夠根據(jù)這個(gè)節(jié)點(diǎn)知道他的子樹的具體的值情況。這點(diǎn)非常之重要，因?yàn)槎嫫胶鈽?#xff0c;只有兩個(gè)子葉節(jié)點(diǎn)，所以如果想找到某個(gè)數(shù)據(jù)，他必須重復(fù)更多次“拿到一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)，判斷大小，再?gòu)钠渲幸粋€(gè)子節(jié)點(diǎn)取出他的兩個(gè)子節(jié)點(diǎn)，判斷大小。”這一過程。
?
這個(gè)過程重復(fù)的次數(shù)，就是樹的高度。那么既然每個(gè)子樹只有兩個(gè)節(jié)點(diǎn)，那么N個(gè)數(shù)據(jù)的樹的高度也就很容易可以算出了。
?
平衡二叉樹這種結(jié)構(gòu)的好處是，沒有空間浪費(fèi)，不會(huì)存在空余的空間，但壞處是需要取出多個(gè)節(jié)點(diǎn)，且無法預(yù)測(cè)下一個(gè)節(jié)點(diǎn)的位置。這種取出的操作，在內(nèi)存內(nèi)進(jìn)行的時(shí)候，速度很快，但如果到磁盤，那么就意味著大量隨機(jī)尋道。基本磁盤就被查死了。
?
而b樹，因?yàn)槠錁?gòu)建過程中引入了有序數(shù)組，從而有效的降低了樹的高度，一次取出一個(gè)連續(xù)的數(shù)組，這個(gè)操作在磁盤上比取出與數(shù)組相同數(shù)量的離散數(shù)據(jù)，要便宜的多。因此磁盤上基本都是b樹結(jié)構(gòu)。
?
不過，b樹結(jié)構(gòu)也不是完美的，與二叉樹相比，他會(huì)耗費(fèi)更多的空間。在最惡劣的情況下，要有幾乎是元數(shù)據(jù)兩倍的格子才能裝得下整個(gè)數(shù)據(jù)集（當(dāng)樹的所有節(jié)點(diǎn)都進(jìn)行了分裂后）。
?
?
以上，我們就對(duì)二叉樹和b樹進(jìn)行了簡(jiǎn)要的分析，當(dāng)然里面還有非常多的知識(shí)我這里沒有提到，我希望我的這個(gè)系列能夠成為讓大家入門的材料，如果感興趣可以知道從哪里著手即可。如果您通過我的文章發(fā)現(xiàn)對(duì)這些原來枯燥的數(shù)據(jù)結(jié)構(gòu)有了興趣，那么我的目標(biāo)就達(dá)到了: )
?
在這章中，我們還將對(duì)b數(shù)的問題進(jìn)行一下剖析，然后給出幾個(gè)解決的方向
?
其實(shí)toku DB的網(wǎng)站上有個(gè)非常不錯(cuò)的對(duì)b樹問題的說明，我在這里就再次侵權(quán)一下，將他們的圖作為說明b樹問題的圖譜吧，因?yàn)檎娴姆浅Ｇ逦?/p>
http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf
?
?
?
?
B樹在插入的時(shí)候，如果是最后一個(gè)node,那么速度非常快，因?yàn)槭琼樞驅(qū)憽?/p>
?
?
?
?
但如果有更新插入刪除等綜合寫入，最后因?yàn)樾枰h(huán)利用磁盤塊，所以會(huì)出現(xiàn)較多的隨機(jī)io.大量時(shí)間消耗在磁盤尋道時(shí)間上。
?
?
?
如果是一個(gè)運(yùn)行時(shí)間很長(zhǎng)的b樹，那么幾乎所有的請(qǐng)求，都是隨機(jī)io。因?yàn)榇疟P塊本身已經(jīng)不再連續(xù)，很難保證可以順序讀取。
?
以上就是b樹在磁盤結(jié)構(gòu)中最大的問題了。
?
那么如何能夠解決這個(gè)問題呢？
目前主流的思路有以下幾種
1.??????放棄部分讀性能，使用更加面向順序?qū)懙臉涞慕Y(jié)構(gòu)來提升寫性能。
這個(gè)類別里面，從數(shù)據(jù)結(jié)構(gòu)來說，就我所知并比較流行的是兩類，
一類是COLA（Cache-Oblivious?Look?ahead?Array）（代表應(yīng)用自然是tokuDB）。
一類是LSM tree(Log-structured merge Tree)或SSTABLE
(代表的數(shù)據(jù)集是cassandra,hbase,bdb java editon,levelDB etc.).
2.??????使用ssd，讓尋道成為往事。
?
我們?cè)谶@個(gè)系列里，主要還是講LSM tree吧，因?yàn)檫@個(gè)東西幾乎要一桶漿糊了。幾乎所有的nosql都在使用，然后利用這個(gè)宣稱自己比mysql的innodb快多少多少倍。。我對(duì)此表示比較無語。因?yàn)閚osql本身似乎應(yīng)該是以省去解析和事務(wù)鎖的方式來提升效能。怎么最后卻改了底層數(shù)據(jù)結(jié)構(gòu)，然后宣稱這是nosql比mysql快的原因呢？
畢竟Mysql又不是不能掛接LSM tree的引擎。。。
?
好吧，牢騷我不多說，畢竟還是要感謝nosql運(yùn)動(dòng)，讓數(shù)據(jù)庫團(tuán)隊(duì)都重新審視了一下數(shù)據(jù)庫這個(gè)產(chǎn)品的本身。
?
那么下面，我們就來介紹一下LSM Tree的核心思想吧。
?
首先來分析一下為什么b+樹會(huì)慢。
?
從原理來說，b+樹在查詢過程中應(yīng)該是不會(huì)慢的，但如果數(shù)據(jù)插入比較無序的時(shí)候，比如先插入5 然后10000然后3然后800 這樣跨度很大的數(shù)據(jù)的時(shí)候，就需要先“找到這個(gè)數(shù)據(jù)應(yīng)該被插入的位置”，然后插入數(shù)據(jù)。這個(gè)查找到位置的過程，如果非常離散，那么就意味著每次查找的時(shí)候，他的子葉節(jié)點(diǎn)都不在內(nèi)存中，這時(shí)候就必須使用磁盤尋道時(shí)間來進(jìn)行查找了。更新基本與插入是相同的
?
?
?
?
?
那么，LSM Tree采取了什么樣的方式來優(yōu)化這個(gè)問題呢？
簡(jiǎn)單來說，就是放棄磁盤讀性能來換取寫的順序性。
乍一看，似乎會(huì)認(rèn)為讀應(yīng)該是大部分系統(tǒng)最應(yīng)該保證的特性，所以用讀換寫似乎不是個(gè)好買賣。但別急，聽我分析之。
1.??????內(nèi)存的速度遠(yuǎn)超磁盤，1000倍以上。而讀取的性能提升，主要還是依靠?jī)?nèi)存命中率而非磁盤讀的次數(shù)
2.??????寫入不占用磁盤的io，讀取就能獲取更長(zhǎng)時(shí)間的磁盤io使用權(quán)，從而也可以提升讀取效率。
因此，雖然SSTable降低了了讀的性能，但如果數(shù)據(jù)的讀取命中率有保障的前提下，因?yàn)樽x取能夠獲得更多的磁盤io機(jī)會(huì)，因此讀取性能基本沒有降低，甚至還會(huì)有提升。
而寫入的性能則會(huì)獲得較大幅度的提升，基本上是5~10倍左右。
?
下面來看一下細(xì)節(jié)
其實(shí)從本質(zhì)來說，k-v存儲(chǔ)要解決的問題就是這么一個(gè)：盡可能快得寫入，以及盡可能快的讀取。
讓我從寫入最快的極端開始說起，闡述一下k-v存儲(chǔ)的核心之一—樹這個(gè)組件吧。
?
我們假設(shè)要寫入一個(gè)1000個(gè)節(jié)點(diǎn)的key是隨機(jī)數(shù)的數(shù)據(jù)。
?
對(duì)磁盤來說，最快的寫入方式一定是順序的將每一次寫入都直接寫入到磁盤中即可。
但這樣帶來的問題是，我沒辦法查詢，因?yàn)槊看尾樵円粋€(gè)值都需要遍歷整個(gè)數(shù)據(jù)才能找到，這個(gè)讀性能就太悲劇了。。
?
那么如果我想獲取磁盤讀性能最高，應(yīng)該怎么做呢？把數(shù)據(jù)全部排序就行了，b樹就是這樣的結(jié)構(gòu)。
?
那么，b樹的寫太爛了，我需要提升寫，可以放棄部分磁盤讀性能，怎么辦呢？
?
簡(jiǎn)單，那就弄很多個(gè)小的有序結(jié)構(gòu)，比如每m個(gè)數(shù)據(jù)，在內(nèi)存里排序一次，下面100個(gè)數(shù)據(jù)，再排序一次……這樣依次做下去，我就可以獲得N/m個(gè)有序的小的有序結(jié)構(gòu)。
?
在查詢的時(shí)候，因?yàn)椴恢肋@個(gè)數(shù)據(jù)到底是在哪里，所以就從最新的一個(gè)小的有序結(jié)構(gòu)里做二分查找，找得到就返回，找不到就繼續(xù)找下一個(gè)小有序結(jié)構(gòu)，一直到找到為止。
?
很容易可以看出，這樣的模式，讀取的時(shí)間復(fù)雜度是(N/m)*log2N 。讀取效率是會(huì)下降的。
這就是最本來意義上的LSM tree的思路。
那么這樣做，性能還是比較慢的，于是需要再做些事情來提升，怎么做才好呢？
?
于是引入了以下的幾個(gè)東西來改進(jìn)它
1.??????Bloom filter : 就是個(gè)帶隨即概率的bitmap,可以快速的告訴你，某一個(gè)小的有序結(jié)構(gòu)里有沒有指定的那個(gè)數(shù)據(jù)的。于是我就可以不用二分查找，而只需簡(jiǎn)單的計(jì)算幾次就能知道數(shù)據(jù)是否在某個(gè)小集合里啦。效率得到了提升，但付出的是空間代價(jià)。
2.??????小樹合并為大樹： 也就是大家經(jīng)常看到的compact的過程，因?yàn)樾渌阅苡袉栴}，所以要有個(gè)進(jìn)程不斷地將小樹合并到大樹上，這樣大部分的老數(shù)據(jù)查詢也可以直接使用log2N的方式找到，不需要再進(jìn)行(N/m)*log2n的查詢了。
?
這就是LSMTree的核心思路和優(yōu)化方式。
不過，LSMTree也有個(gè)隱含的條件，就是他實(shí)現(xiàn)數(shù)據(jù)庫的insert語義時(shí)性能不會(huì)很高，原因是，insert的含義是： 事務(wù)中，先查找該插入的數(shù)據(jù)，如果存在，則拋出異常，如果不存在則寫入。這個(gè)“查找”的過程，會(huì)拖慢整個(gè)寫入。
?
?
這樣，我們就又介紹了一種k-v寫入的模型啦。在下一次，我們將再去看看另外一種使用了類似思路，但方法完全不同的b樹優(yōu)化方式 COLA樹系。敬請(qǐng)期待 ~
?
?
海量存儲(chǔ)系列之九
?http://qing.weibo.com/1765738567/693f0847330008x6.html?
終于來到了COLA樹系，這套東西目前來看呢，確實(shí)不如LSM火，不過作為可選方案，也是個(gè)值得了解的嘗試，不過這塊因?yàn)橹挥幸唤MMIT的人搞了個(gè)東西出來，所以其實(shí)真正的方案也語焉不詳?shù)摹?/p>
?
從性能來說，tokuDB的寫入性能很高，但更新似乎不是很給力，查詢較好，占用較少的內(nèi)存。
?
http://www.mysqlperformanceblog.com/2009/04/28/detailed-review-of-tokutek-storage-engine/
這里有一些性能上的指標(biāo)和分析性文字。確實(shí)看起來很心動(dòng)，不過這東西只適合磁盤結(jié)構(gòu)，到了SSD似乎就掛了。原因不詳，因?yàn)闆]有實(shí)際的看過他們的代碼，所以一切都是推測(cè)，如果有問題，請(qǐng)告知我。
?
?
先說原理，上ppt?http://tokutek.com/presentations/bender-Scalperf-9-09.pdf，簡(jiǎn)單來說，就是一幫MIT的小子們，分析了一下為什么磁盤寫性能這么慢，讀的性能也這么慢，然后一拍腦袋，說：“哎呀，我知道了，對(duì)于兩級(jí)的存儲(chǔ)（比如磁盤對(duì)應(yīng)內(nèi)存，或內(nèi)存對(duì)于緩存，有兩個(gè)屬性是會(huì)對(duì)整個(gè)查詢和寫入造成影響的，一個(gè)是容量空間小但速度更快的存儲(chǔ)的size，另外一個(gè)則是一次傳輸?shù)腷lock的size.而我們要做的事情，就是盡可能讓每次的操作傳輸盡可能少的數(shù)據(jù)塊。
?
傳輸?shù)脑缴?#xff0c;那么查詢的性能就越好。
?
?
進(jìn)而，有人提出了更多種的解決方案。
?B-tree [Bayer, McCreight 72]
? cache-oblivious B-tree [Bender, Demaine, Farach-Colton 00]
? buffer tree [Arge 95]
? buffered-repositorytree[Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook 00]
? Bε
?tree[Brodal, Fagerberg 03]
? log-structured merge tree [O'Neil, Cheng, Gawlick, O'Neil 96]
? string B-tree [Ferragina, Grossi 99]
?
這些結(jié)構(gòu)都是用于解決這樣一個(gè)問題，在磁盤上能夠創(chuàng)建動(dòng)態(tài)的有序查詢結(jié)構(gòu)。
?
在今天，主要想介紹的就是COLA，所謂cache-oblivious 就是說，他不需要知道具體的內(nèi)存大小和一個(gè)塊的大小，或者說，無論內(nèi)存多大，塊有多大，都可以使用同一套邏輯進(jìn)行處理，這無疑是具有優(yōu)勢(shì)的，因?yàn)閮?nèi)存大小雖然可以知道，但內(nèi)存是隨時(shí)可能被臨時(shí)的占用去做其他事情的，這時(shí)候，CO就非常有用了。
?
其他我就不多說了，看一下細(xì)節(jié)吧~再說這個(gè)我自己都快繞進(jìn)去了。
?
眾所周知的，磁盤需要的是順序?qū)懭?#xff0c;下一個(gè)問題就是，怎么能夠保證數(shù)據(jù)的順序?qū)憽?/p>
我們假定有這樣一個(gè)空的數(shù)據(jù)集合
?
?
?
?
?
可以認(rèn)為樹的高度是log2N。
每行要么就是空的，要么就是滿的，每行數(shù)據(jù)都是排序后的數(shù)據(jù)。
?
如果再寫一個(gè)值的時(shí)候，會(huì)寫在第一行，比如寫了3。
再寫一個(gè)值11的時(shí)候，因?yàn)榈谝恍幸呀?jīng)寫滿了，所以將3取出來，和11做排序，嘗試寫第二行。又因?yàn)榈诙幸矟M了，所以將第二行的5和10也取出，對(duì)3,11,5,10 進(jìn)行排序。寫入第四行
?
?
?
?
這就是COLA的寫入過程。
可以很清楚的看出，COLA的核心其實(shí)和LSM類似，每次“將數(shù)據(jù)從上一層取出，與外部數(shù)據(jù)進(jìn)行歸并排序后寫入新的array”的這個(gè)操作，對(duì)sas磁盤非常友好。因此，寫入性能就會(huì)有非常大的提升。
?
并且因?yàn)閿?shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，沒有維持太多額外的指針，所以相對(duì)的比較節(jié)省空間。
?
但這樣查詢會(huì)需要針對(duì)每個(gè)array都進(jìn)行一次二分查找。
性能似乎還不是很高，所以，他們想到了下面這種方式，把它的命名為fractal tree,分形樹。
用更簡(jiǎn)單的方法來說的話呢，就是在merge的時(shí)候，上層持有下層數(shù)據(jù)的一個(gè)額外的指針。
來協(xié)助進(jìn)行二分查找。
?
?
?
?
這樣，利用空間換時(shí)間，他的查詢速度就又回到了log2N這個(gè)級(jí)別了。
?
到此，又一個(gè)有序結(jié)構(gòu)被我囫圇吞棗了。
?
嘿嘿
?
在下一篇，我們將進(jìn)入大家期待的分布式k-V場(chǎng)景，也就是noSQL的范疇了，讓我們撥開nosql的神秘面紗，看看這東西到底意味著什么。
?
海量存儲(chǔ)系列之十
http://qing.weibo.com/1765738567/693f084733000963.html
上一次，我們介紹了幾種常見的kv存儲(chǔ)模型，下面我們就正式進(jìn)入到分布式存儲(chǔ)的場(chǎng)景里去看看這套東西在分布式場(chǎng)景下的運(yùn)作方式吧。
?
在分布式key-value中，很多原來的知識(shí)是可以繼續(xù)復(fù)用的。因?yàn)閗-v解決的問題實(shí)在是非常的簡(jiǎn)單，只不過是根據(jù)一個(gè)key找到value的過程，所以原來的知識(shí)，現(xiàn)在也繼續(xù)的可以用。
但有兩個(gè)額外的因素需要考慮
網(wǎng)絡(luò)延遲
? ? ? ? ?TCP/IP –公用網(wǎng)絡(luò)，ip跳轉(zhuǎn)慢，tcp包頭大
可能出現(xiàn)不可達(dá)問題
???????? 這其實(shí)是狀態(tài)機(jī)同步中最難的一個(gè)問題，也就是，A給B消息，B可能給A的反饋可能是:1. 成功 2. 失敗 3. 無響應(yīng)。最難處理的是這個(gè)無響應(yīng)的問題。以前的文章中我們討論過這個(gè)問題，以后還會(huì)碰到。這里暫且hold住。
?
先上圖一張，在未來的幾周內(nèi)，我們都會(huì)依托這張圖來解釋分布式K-V系統(tǒng)
?
?
?
?
可以看到，在客戶機(jī)到服務(wù)器端，有這么幾個(gè)東西
一，規(guī)則引擎
二，數(shù)據(jù)節(jié)點(diǎn)間的同步
?
抽象的來看，分布式K-V系統(tǒng)和傳統(tǒng)的單機(jī)k-v系統(tǒng)的差別，也就只在于上面的兩個(gè)地方的選擇。
?
?
今天先來談規(guī)則引擎
?
抽象的來看，規(guī)則引擎面向的場(chǎng)景應(yīng)該被這樣的描述：對(duì)于有狀態(tài)的數(shù)據(jù)，需要一套機(jī)制以保證其針對(duì)同一個(gè)數(shù)據(jù)的多次請(qǐng)求，應(yīng)該物理上被發(fā)送到同一個(gè)邏輯區(qū)塊內(nèi)的同一個(gè)數(shù)據(jù)上。
?
舉例子來說，一個(gè)人進(jìn)行了三筆交易，每筆交易都是這個(gè)人給其他人100元。那么，這三比交易的更新(update set money = money – 100 where userid = ?) 必須被發(fā)到同一臺(tái)機(jī)器上執(zhí)行，才能拿到正確的結(jié)果。【不考慮讀性能的gossip模型除外】
?
這種根據(jù)一個(gè)userid 找到其對(duì)應(yīng)的機(jī)器的過程，就是規(guī)則引擎所要處理的事情。
?
我們對(duì)于規(guī)則引擎的需求，一般來說也就是要查的快，第二個(gè)是要能盡可能的將數(shù)據(jù)平均的分配到所有的節(jié)點(diǎn)中去。第三個(gè)，如果新的節(jié)點(diǎn)加入進(jìn)去，希望能夠只移動(dòng)那些需要移動(dòng)的數(shù)據(jù)，不需要移動(dòng)的數(shù)據(jù)則不要去移動(dòng)他。
?
那么一想到“根據(jù)xxx找到xxx”相信大家第一個(gè)想到的一定又是以前說過的K-V了。所以我們就再?gòu)?fù)習(xí)一遍: )
?
Hash?
O(1)效率
不支持范圍查詢（時(shí)間這樣的查詢條件不要考慮了）
不需要頻繁調(diào)整數(shù)據(jù)分布
順序
主要是B-Tree
O(logN)效率
支持范圍查詢
需要頻繁調(diào)整節(jié)點(diǎn)指針以適應(yīng)數(shù)據(jù)分布
?
這也就是我們最常用的兩種分布式k-value所使用的數(shù)據(jù)結(jié)構(gòu)了
?
首先來看HASH的方法。Hash其實(shí)很容易理解，但我跟不少人交流，發(fā)現(xiàn)大家可能對(duì)一致性hash的理解有一定的誤解。下面請(qǐng)?jiān)试S我給大家做個(gè)簡(jiǎn)單的介紹。
?
簡(jiǎn)單取模:
最簡(jiǎn)單的HASH 就是取mod,user_id % 3 。這樣，會(huì)將數(shù)據(jù)平均的分配到0,1,2 這三臺(tái)機(jī)器中。
這也是我們目前最常用的，最好用的方案。但這套方案也會(huì)有一個(gè)問題，就是如果id % 3 -> id % 4 總共會(huì)有75%的數(shù)據(jù)需要變動(dòng)hash桶，想一想，只增加了一臺(tái)機(jī)器，但80的數(shù)據(jù)需要從一個(gè)機(jī)器移動(dòng)到另外一個(gè)機(jī)器，這無疑是不夠經(jīng)濟(jì)的，也是對(duì)遷移不友好的方案。
不過，雖然增加一臺(tái)機(jī)器，會(huì)發(fā)生無謂的數(shù)據(jù)移動(dòng)，但取模的方案在一些特殊的場(chǎng)景下，也能很好的滿足實(shí)際的需要，如id % 3 -> id % 6，這種情況下，只需要有50%的數(shù)據(jù)移動(dòng)到新的機(jī)器上就可以了。這也就是正常的hash取模最合適的擴(kuò)容方式-----> 倍分?jǐn)U容。我們一般把這種擴(kuò)容的方式叫做”N到2N”的擴(kuò)容方案。
?
取模Hash還有個(gè)無法解決的問題，就是無法處理熱點(diǎn)的問題，假設(shè)有一個(gè)賣家有N個(gè)商品。如果按照賣家ID進(jìn)行切分，那么就有可能會(huì)造成數(shù)據(jù)不均勻的問題。有些賣家可能有10000000個(gè)商品，而有些賣家只會(huì)有10個(gè)。這種情況下如果有大量商品的賣家針對(duì)他的商品做了某種操作，那這樣無疑會(huì)產(chǎn)生數(shù)據(jù)熱點(diǎn)。如何解決這類問題，也是分布式場(chǎng)景中面臨的一個(gè)重要的問題。
?
既然簡(jiǎn)單取模有這么多的問題，那有沒有辦法解決這些問題呢？
?
首先，我們來介紹第一種解決這個(gè)問題的嘗試。
?
一致性Hash.
先來個(gè)圖，這套圖估計(jì)幾乎所有對(duì)Nosql稍有了解的人都應(yīng)該看過，在這里我會(huì)用另外的方式讓大家更容易理解
?
?
?
上面這個(gè)圖，用代碼來表示，可以認(rèn)為是這樣一套偽碼
?
Def idmod = id % 1000 ;
If(id >= 0 and id < 250)
???????? returndb1;
Else if (id >= 250 and id < 500)
???????? returndb2;
Else if (id >= 500 and id < 750)
???????? returndb3;
Else
???????? returndb4;
?
這個(gè)return db1 db2 db3 db4 就對(duì)應(yīng)上面圖中的四個(gè)淺藍(lán)色的點(diǎn)兒。
而如果要加一個(gè)node5 ，那么偽碼會(huì)轉(zhuǎn)變?yōu)?/strong>
?
Def idmod = id % 1000 ;
If(id >= 0 and id < 250)
???????? returndb1;
Else if (id >= 250 and id < 500)
???????? returndb2;
Else if (id >= 500 and id < 625)
???????? returndb5;
else if(id >= 625 and id <750)
???????? returndb3
Else
???????? returndb4;
?
從這種結(jié)構(gòu)的變化中，其實(shí)就可以解決我們?cè)谄胀╤ash時(shí)候的面臨的兩個(gè)問題了。
1.??????可以解決熱點(diǎn)問題，只需要對(duì)熱點(diǎn)的數(shù)據(jù)，單獨(dú)的給他更多的計(jì)算和存儲(chǔ)資源，就能部分的解決問題（但不是全部，因?yàn)檫w移數(shù)據(jù)不是無成本的，相反，成本往往比較高昂）
2.??????部分的能夠解決擴(kuò)容的問題，如果某個(gè)點(diǎn)需要加機(jī)器，他只會(huì)影響一個(gè)節(jié)點(diǎn)內(nèi)的數(shù)據(jù)，只需要將那個(gè)節(jié)點(diǎn)的數(shù)據(jù)移動(dòng)到新節(jié)點(diǎn)就可以了。
?
但一致性hash也會(huì)帶來問題，如果數(shù)據(jù)原本分布就非常均勻，那么加一臺(tái)機(jī)器，只能解決臨近的一個(gè)節(jié)點(diǎn)上的熱點(diǎn)問題，不會(huì)影響其他節(jié)點(diǎn)，這樣，熱點(diǎn)擴(kuò)容在數(shù)據(jù)分布均勻的情況下基本等于n->2n方案。因?yàn)橐诿總€(gè)環(huán)上都加一臺(tái)機(jī)器，才能保證所有節(jié)點(diǎn)的數(shù)據(jù)的一部分遷移到新加入的機(jī)器上。
?
這無疑對(duì)也會(huì)浪費(fèi)機(jī)器。
?
于是，我們又引入了第三套機(jī)制:
?
虛擬節(jié)點(diǎn)hash
Def hashid = Id % 65536
?
?
?
可以很容易的看出，上面這套虛擬節(jié)點(diǎn)的方案，其實(shí)與id % 4的結(jié)果等價(jià)。
可以認(rèn)為一致性hash和普通節(jié)點(diǎn)hash，都是虛擬節(jié)點(diǎn)hash的特例而已。
?
使用虛擬節(jié)點(diǎn)hash,我們就可以很容易的解決幾乎所有在擴(kuò)容上的問題了。
碰到熱點(diǎn)？只需要調(diào)整虛擬節(jié)點(diǎn)map中的映射關(guān)系就行了
碰到擴(kuò)容？只需要移動(dòng)一部分節(jié)點(diǎn)的映射關(guān)系，讓其進(jìn)入新的機(jī)器即可
?
可以說是一套非常靈活的方案，但帶來的問題是方案有點(diǎn)復(fù)雜了。
所以，我們一般在使用的方式是，首先使用簡(jiǎn)單的取模方案，如id % 4。在擴(kuò)容的時(shí)候也是用N->2N的方案進(jìn)行擴(kuò)容。但如果碰到需求復(fù)雜的場(chǎng)景，我們會(huì)“無縫”的將業(yè)務(wù)方原來的簡(jiǎn)單取模方案，直接變?yōu)槭褂锰摂M節(jié)點(diǎn)hash的方案，這樣就可以支持更復(fù)雜的擴(kuò)容和切分規(guī)則，又不會(huì)對(duì)業(yè)務(wù)造成任何影響了。
?
好，到這，我基本上就給大家介紹了如何使用Hash來完成分布式k-value系統(tǒng)的規(guī)則引擎構(gòu)建了。
下一期我們來看一下使用樹的方案，當(dāng)然，主要也就是hbase這個(gè)東西了，可能會(huì)再介紹一下mongodb的自動(dòng)擴(kuò)容方案。睡覺睡覺: )
?
海量存儲(chǔ)系列之十一
http://qing.weibo.com/1765738567/693f084733000a5w.html
ps : 最近霸神推了一把，粉絲增加不少，頓時(shí)亞歷山大。。還是希望大家用輕松一點(diǎn)的心態(tài)來看待我的這些科普文。
如果想精細(xì)推敲，歡迎在后面留言，我一定會(huì)與您討論與分享。上一期我們主要在介紹hash相關(guān)的切分方式，那么這次我們來看一下有序結(jié)構(gòu)的切分
?
有序結(jié)構(gòu)的拆分，目前主要就是使用樹或類似樹的結(jié)構(gòu)進(jìn)行拆分，這里主要就是指HBase和MongoDB.
?
使用樹結(jié)構(gòu)切分，帶來的好處就如hbase和mongoDB的宣傳標(biāo)語一樣，可以無縫的實(shí)現(xiàn)自由擴(kuò)展。但反過來，帶來的問題其實(shí)也不少，下面我們一起來看一看吧。
?
首先復(fù)習(xí)B樹知識(shí)http://qing.weibo.com/1765738567/693f0847330008ii.html
?
在B樹中，最關(guān)鍵的處理邏輯是如果單個(gè)節(jié)點(diǎn)數(shù)據(jù)滿的時(shí)候，應(yīng)該進(jìn)行節(jié)點(diǎn)分裂和節(jié)點(diǎn)合并。
?
那么，其實(shí)在HBase中也有類似這樣的過程。
?
對(duì)于巨大量的數(shù)據(jù)來說，整個(gè)樹的Branch節(jié)點(diǎn)都有可能超過單機(jī)的內(nèi)存大小上限，甚至超過單機(jī)的硬盤大小上限。
這時(shí)候就需要把BTree進(jìn)行拆分，這種拆分的最標(biāo)準(zhǔn)實(shí)現(xiàn)映射，就是HBase.
(圖片版權(quán)方在：http://blog.csdn.net/HEYUTAO007/article/details/5766951)
?
?
?
看這個(gè)圖可能會(huì)比較暈，沒關(guān)系，聽我分析之。
首先，整個(gè)Hbase就是為了解決一個(gè)B樹非常巨大，以至于單機(jī)無法承載其branch and root節(jié)點(diǎn)之后，使用分布式存儲(chǔ)的方式來提升整個(gè)樹的容災(zāi)量的一種嘗試。
?
抽象的來看，每一個(gè)HRegion都是一個(gè)Btree的Node，這個(gè)Node會(huì)掛在在某個(gè)Region server上面，RangeServer內(nèi)可以存放多個(gè)Hregion ,其實(shí)就是Btree的branch節(jié)點(diǎn)了，但因?yàn)锽ranch也很多，以至于單機(jī)無法存放所有branch節(jié)點(diǎn)，因此就還需要一層結(jié)構(gòu)來處理這個(gè)問題。這就是HMaster 。
上圖
?
?
?
雖然可能有點(diǎn)抽象，不過本質(zhì)來說就是這樣一個(gè)東西。
當(dāng)然，細(xì)節(jié)有點(diǎn)變化：
HMaster ，在上面的圖中是單個(gè)點(diǎn)，實(shí)際的實(shí)現(xiàn)是一個(gè)btree,三層結(jié)構(gòu)的。
?
因?yàn)镠Master的數(shù)據(jù)不經(jīng)常發(fā)生變化，同時(shí)，每次請(qǐng)求都去訪問HMaster，那么HMaster所承擔(dān)的讀寫壓力就過大了。所以，HBase增加了一個(gè)客戶端的Cache.來存HMaster中的這幾層BTree.
?
于是，可憐的Hbase又得考慮如何能夠?qū)Client和HMaster中的數(shù)據(jù)進(jìn)行同步的問題。
?
針對(duì)這個(gè)問題，Hbase提出的解決思路是，既然變動(dòng)不大，那就允許他錯(cuò)吧，只要咱知道出錯(cuò)了，改正了就行了。
也即，允許HClient根據(jù)錯(cuò)誤的Btree選擇到錯(cuò)誤的Region Server,但一旦發(fā)現(xiàn)自己所選的數(shù)據(jù)在那臺(tái)Region server上無法找到，則立刻重新更新自己的HMaster表。已達(dá)到同步。
?
?
這基本上就是BTree的分布式實(shí)踐中做的最好的HBase的一些過程了。
?
然后然后，私貨時(shí)間開始: )
?
借助HDFS,Hbase幾乎實(shí)現(xiàn)了無限的擴(kuò)展性，但整體結(jié)構(gòu)過于復(fù)雜和龐大了，最終，他只解決了一個(gè)K-V寫入的問題，同時(shí)又希望對(duì)所有用戶屏蔽底層的所有數(shù)據(jù)節(jié)點(diǎn)的具體位置。
這套思路有其優(yōu)勢(shì)之處（也就是Btree的優(yōu)勢(shì)）：
1.??????純粹log場(chǎng)景，btree管理起來非常方便
2.??????支持范圍查詢
?
但可能的劣勢(shì)其實(shí)也很多
1.??????結(jié)構(gòu)繁雜，在各種角色中進(jìn)行數(shù)據(jù)同步，這件事本身聽起來就已經(jīng)很嚇人了。然而，最終，他只是解決了一個(gè)按照K找到V的過程。。Hash一樣可以做到
2.??????Region server ，維護(hù)難度較高，核心數(shù)據(jù)結(jié)構(gòu)點(diǎn)，雖然該機(jī)器可以認(rèn)為是個(gè)接近無狀態(tài)的機(jī)器，但如果想拿一臺(tái)空機(jī)器恢復(fù)到可以承擔(dān)某個(gè)Region server的指責(zé)，這個(gè)過程需要的時(shí)間會(huì)很長(zhǎng)，導(dǎo)致的問題就是，系統(tǒng)的一部分?jǐn)?shù)據(jù)不可用，甚至發(fā)生雪崩。
3.??????BTree 在不斷追加append的時(shí)候，其實(shí)是有熱點(diǎn)的，目前沒有很好地辦法能在按照時(shí)間序或按照自增id序列的時(shí)候保證所有的數(shù)據(jù)存儲(chǔ)機(jī)都能夠比較均衡的寫入數(shù)據(jù)。會(huì)存在熱點(diǎn)問題，這個(gè)問題的源頭在BTree需要有序并連續(xù)，這意味著連續(xù)的數(shù)據(jù)只會(huì)被寫在一個(gè)region塊內(nèi)，這個(gè)問題在單機(jī)btree其實(shí)也是存在的，但有raid技術(shù)，以及有二級(jí)索引，所以問題沒有那么明顯。（感謝@bluedavy)
?
綜上，HBase其實(shí)從一開始是一個(gè)面向后端處理的數(shù)據(jù)引擎，在數(shù)據(jù)一致性上是可以期待的，但對(duì)于線上系統(tǒng)來說，他違背了重要的一個(gè)原則：簡(jiǎn)單。所以我“個(gè)人”對(duì)這一點(diǎn)持保留態(tài)度。
?
不過，這么多大牛在努力的經(jīng)營(yíng)HBase這個(gè)產(chǎn)品，那么我也樂觀其成，畢竟能把這么復(fù)雜的東西整的能在這么多臺(tái)機(jī)器上用，也是個(gè)巨大成就了。
?
MongoDB其實(shí)也是在學(xué)Hbase的這種有序的BTree結(jié)構(gòu)，不過它的實(shí)現(xiàn)就簡(jiǎn)單的多了。
就是把數(shù)據(jù)拆分成一段一段的數(shù)據(jù)，用一個(gè)公用的配置角色存儲(chǔ)這段數(shù)據(jù)所在的分片。查詢時(shí)進(jìn)行二分查找找到。
思路類似。
?
從角色來看
他的規(guī)則引擎實(shí)現(xiàn)就是個(gè)有序數(shù)據(jù)的實(shí)現(xiàn)，可以認(rèn)為是個(gè)兩層有序結(jié)構(gòu)查找.第一層決定數(shù)據(jù)的具體機(jī)器(Mongos+config server)，第二層決定數(shù)據(jù)在該機(jī)的具體位置MongoServer。
?
?
好了，畫個(gè)圖用了20分鐘，今天的介紹就到這里，下期我們來探討分布式場(chǎng)景下一個(gè)必要的過程。數(shù)據(jù)的遷移方式討論。
海量存儲(chǔ)系列之十二
http://qing.weibo.com/1765738567/693f084733000bxj.html?
時(shí)間隔了比較久了，因?yàn)樽罱谶^年臨近，所以都在準(zhǔn)備這方面的事情。這里提前祝大家新年快樂。
然后還是回到我們的正題兒吧:)
?
本章，我們主要來討論數(shù)據(jù)的管理和擴(kuò)容中最重要的一個(gè)部分，數(shù)據(jù)遷移。
?
數(shù)據(jù)遷移是數(shù)據(jù)運(yùn)維中最為重要的一個(gè)部分，在前面的文章中已經(jīng)提到過，作為有狀態(tài)的數(shù)據(jù)節(jié)點(diǎn)，在互聯(lián)網(wǎng)行業(yè)的主要追求就是，無限的水平擴(kuò)展能力，這種水平擴(kuò)展，主要用于解決兩類問題，一類是磁盤空間不足的問題，一類是性能不足的問題。
?
?
為了達(dá)到這種能力，一般來說主要也就是這樣一個(gè)思路，盡可能的讓數(shù)據(jù)不動(dòng)，只通過規(guī)則變動(dòng)的方式來完成擴(kuò)容，如果這種方式無法滿足要求，那么再通過移動(dòng)數(shù)據(jù)的方式，來滿足其他的一些需求。
?
下面來進(jìn)行下分析。
只通過變動(dòng)規(guī)則的方式擴(kuò)容，舉個(gè)最簡(jiǎn)單的例子，就是一組按照時(shí)間或自增id的數(shù)據(jù)。那么最簡(jiǎn)單的切分方式，就是按照時(shí)間或id的范圍，將一組數(shù)據(jù)直接映射到某個(gè)具體的機(jī)器上，類似
if(gmt> = 2010 and gmt < 2011)
returndataNode1;
elseif( gmt >= 2011 and gmt < 2012)
returndataNode2;
elseif(gmt >= 2012 and gmt < 20121223)
returndataNode3;
…
?
使用這種方式的好處，顯而易見，就是不用動(dòng)數(shù)據(jù)，方法簡(jiǎn)單。
但帶來的壞處也明顯，就是不移動(dòng)數(shù)據(jù)，那么如果一組數(shù)據(jù)已經(jīng)成為熱點(diǎn)，那么永遠(yuǎn)也沒有機(jī)會(huì)將熱點(diǎn)數(shù)據(jù)分開到不同的機(jī)器里用以減輕熱點(diǎn)的損耗了。而，這種情況是非常有可能的，對(duì)于一對(duì)多的模型，如果按照一去存儲(chǔ)數(shù)據(jù)，那么因?yàn)槎嗟臄?shù)據(jù)量的不斷擴(kuò)展，會(huì)最終導(dǎo)致單個(gè)機(jī)器的數(shù)據(jù)量和io超限。
?
為了解決上述矛盾，就需要引入數(shù)據(jù)的遷移的方法了，簡(jiǎn)單來說，就是按照規(guī)則將數(shù)據(jù)從原來的一組機(jī)器上，遷移到新的一組機(jī)器上去，這樣規(guī)則和數(shù)據(jù)一起變動(dòng)，就可以有效的解決上面所說的熱點(diǎn)問題，盡可能讓所有的機(jī)器均勻的發(fā)揮效用。
?
思路很簡(jiǎn)單，但工程實(shí)踐就復(fù)雜多了，下面來描述幾種擴(kuò)容的模式，希望大家能針對(duì)這幾種場(chǎng)景以及我的分析，對(duì)如何解決這個(gè)問題有個(gè)更深入的認(rèn)識(shí)。
?
所有有狀態(tài)的數(shù)據(jù)，其實(shí)都需要有擴(kuò)容的策略，在這些擴(kuò)容的模式中，最簡(jiǎn)單的莫過于對(duì)cache節(jié)點(diǎn)的擴(kuò)容了。因?yàn)閏ache本身其實(shí)只是一個(gè)一致的數(shù)據(jù)的一個(gè)快照，快照的意義就在于：如果你對(duì)快照的數(shù)據(jù)是否正確有異議，可以直接去從數(shù)據(jù)的源頭再查一次寫回快照中，即可保證數(shù)據(jù)的最新。
?
那么對(duì)于緩存數(shù)據(jù)，一般來說緩存的更新邏輯有兩種，一種是寫的時(shí)候同步更新緩存。一種是先讀緩存，緩存沒有的時(shí)候讀數(shù)據(jù)庫讀出最新值后更新緩存，一般來說是兩種緩存模式組合使用，因?yàn)闆]有副作用。對(duì)于這種情況的緩存節(jié)點(diǎn)擴(kuò)容，最簡(jiǎn)單的做法是，只需要直接改變規(guī)則即可。
?
如，假設(shè)原來的數(shù)據(jù)是按照id% 4進(jìn)行切分的，那么如果規(guī)則換為id% 8.那么有一半的數(shù)據(jù)就無法被訪問到。但沒關(guān)系，因?yàn)闃I(yè)務(wù)的實(shí)際邏輯是，如果讀不到，就讀穿緩存去數(shù)據(jù)庫里面取數(shù)據(jù)再更新回緩存，所以很快，數(shù)據(jù)會(huì)按照新的id% 8 進(jìn)行填充，擴(kuò)容就完成了。
?
當(dāng)然，實(shí)際的擴(kuò)容比這個(gè)要復(fù)雜一點(diǎn)，因?yàn)?#xff0c;要考慮規(guī)則變動(dòng)后，讀穿的次數(shù)增多，導(dǎo)致數(shù)據(jù)庫壓力上升的問題，所以要盡可能的避免過多的數(shù)據(jù)讀穿緩存，這時(shí)候會(huì)使用我們?cè)谝郧暗奈恼轮杏懻撨^的一致性hash或虛擬節(jié)點(diǎn)hash，使用緩慢更新映射關(guān)系的方式，來降低擴(kuò)容對(duì)數(shù)據(jù)庫帶來的壓力。
?
以上是最簡(jiǎn)單的規(guī)則和數(shù)據(jù)一起移動(dòng)的例子，從上述例子可以分析出，其實(shí)規(guī)則遷移的最主要問題在于如何保證規(guī)則變更時(shí)，數(shù)據(jù)能夠在規(guī)則發(fā)生變動(dòng)的時(shí)候?qū)ν獠勘ＷC數(shù)據(jù)是最新的讀取，在緩存擴(kuò)容的case中，這個(gè)數(shù)據(jù)保證最新的任務(wù)，是由數(shù)據(jù)庫這個(gè)組件來完成的。所以緩存擴(kuò)容是相對(duì)最為簡(jiǎn)單的。
?
那么，自然的就會(huì)產(chǎn)生另外一個(gè)疑問：對(duì)于數(shù)據(jù)庫，怎么保證這個(gè)一致性的讀取呢？這也是我們這一章要闡明的最重要的問題。
?
數(shù)據(jù)的一致性讀，一般來說就只有兩種做法。第一種是共享內(nèi)存指針，說白了就是數(shù)據(jù)只有一份，但指向該數(shù)據(jù)的指針可能是多個(gè)。還有一種就是數(shù)據(jù)復(fù)制，數(shù)據(jù)的復(fù)制，保證一致性的難度會(huì)很大。更多的情況是按照實(shí)際的需求，取兩種模式的折衷。
?
對(duì)數(shù)據(jù)節(jié)點(diǎn)的擴(kuò)容而言，其實(shí)核心就是數(shù)據(jù)的復(fù)制，既然復(fù)制，那么一致性就非常難以保證，于是我們也就只能盡可能巧妙地利用手頭的工具，取折衷，用以盡可能的減少不一致的影響。
?
為了解決這個(gè)一致性的問題，我們需要在規(guī)則上引入版本，這個(gè)概念，主要是用于規(guī)定什么時(shí)候數(shù)據(jù)應(yīng)該以什么規(guī)則進(jìn)行訪問。這樣，就可以避免數(shù)據(jù)復(fù)制過程中所帶來的不一致的問題了。
?
假設(shè)，我們?cè)瓉淼囊?guī)則，版本號(hào)為0，新的規(guī)則，版本號(hào)為1.那么，開始的時(shí)候，客戶端所持有的數(shù)據(jù)的切分規(guī)則是版本0，所有數(shù)據(jù)在老的一組機(jī)器上進(jìn)行讀取和寫入，不會(huì)出現(xiàn)問題。當(dāng)我給定v0和v1兩個(gè)版本同時(shí)存在時(shí)，從客戶端就可以意識(shí)到，目前的規(guī)則是兩份并存，數(shù)據(jù)可能是不一致的，這時(shí)候最簡(jiǎn)單的處理策略是，阻止一切讀取和寫入，這樣數(shù)據(jù)的不一致就不會(huì)發(fā)生了（哈哈，因?yàn)楸旧聿辉试S讀寫了嘛。。），而當(dāng)規(guī)則變?yōu)橹挥衯1的時(shí)候，那么客戶端就可以知道，目前只有一個(gè)規(guī)則了，按照這個(gè)規(guī)則，進(jìn)行數(shù)據(jù)訪問就可以了。
?
使用版本號(hào)，就可以讓客戶端能夠有機(jī)會(huì)意識(shí)到數(shù)據(jù)在某個(gè)時(shí)間段可能存在著不一致，應(yīng)該加以針對(duì)性的處理，這樣就可以規(guī)避數(shù)據(jù)讀寫的不一致的問題了。
?
解決了不一致的問題，下面緊接著要解決的問題有兩個(gè)：
我如何知道應(yīng)該讓哪些數(shù)據(jù)移動(dòng)到哪臺(tái)機(jī)器上？
我如何盡可能的減小規(guī)則并存時(shí)的停寫的數(shù)據(jù)范圍？
?
針對(duì)這個(gè)問題，外面開源的社區(qū)，最常用的解決方法是一致性hash。
?
?
?
?
在一致性hash中，在某個(gè)地方加一組機(jī)器，可以很容易的預(yù)測(cè)應(yīng)該將哪個(gè)節(jié)點(diǎn)的數(shù)據(jù)移動(dòng)到新的節(jié)點(diǎn)上。同時(shí)，又可以預(yù)測(cè)，哪些節(jié)點(diǎn)不會(huì)受到影響，哪些不受到影響的節(jié)點(diǎn)，完全可以開放讀取，而受到影響的節(jié)點(diǎn)，則阻止訪問即可。
?
如上圖中，
node4和node2中間，加了一個(gè)node5,那么很容易的可以知道，只需要將node4中的一部分?jǐn)?shù)據(jù)，寫入新的node5即可。而node2,node1,node3的數(shù)據(jù)不受到影響，可以繼續(xù)允許訪問。
?
這樣就可以比較成功的解決上面提到的兩個(gè)問題了。
?
但從http://qing.weibo.com/1765738567/693f084733000963.html這篇文章的討論中，我們也很容易可以看到，一致性hash也有他自己的問題。
?
于是，自然就有人要問，有沒有其他的做法呢？
?
自然是有啦，下面來介紹一下淘寶TDDL在這方面的工程實(shí)踐吧。以下是純粹干貨，目前暫時(shí)沒見過業(yè)內(nèi)使用類似方式，這種模式在淘寶也經(jīng)歷了較多次的自動(dòng)擴(kuò)容考驗(yàn)，能夠滿足我們的需求，相信也一定能滿足您的需求，因?yàn)樗裁炊紱]做，也什么都做了:).
?
首先是需求描述：分析淘寶的需求，簡(jiǎn)單概括就是一句話，業(yè)務(wù)方的規(guī)則需求，復(fù)雜到無以復(fù)加，絕非簡(jiǎn)單一致性hash或簡(jiǎn)單btree可以滿足，為了不同的業(yè)務(wù)需求，會(huì)有種類很多的切分規(guī)則。
?
需求分析：
需求分析其實(shí)就是挖掘需求的含義，找到哪些是真實(shí)的需求，哪些不是，將不是的砍掉，看看剩下的能不能滿足的過程:)
?
擴(kuò)容系統(tǒng)的技術(shù)特點(diǎn)：
規(guī)則系統(tǒng)要自定義，因?yàn)檫@是業(yè)務(wù)核心，只有業(yè)務(wù)知道他們的數(shù)據(jù)怎么分配會(huì)獲得比較均勻的訪問模型。
擴(kuò)容“不是”常態(tài)，一般來說擴(kuò)容的周期是3個(gè)月～6個(gè)月，甚至更長(zhǎng)。如果一個(gè)業(yè)務(wù)，每6天要擴(kuò)容一次，那采購(gòu)人員絕對(duì)會(huì)抄家伙找他們team干架去了
擴(kuò)容本身不是不能做，但難度較大，一般來說需要幾個(gè)人一起參與，最少有數(shù)據(jù)運(yùn)維人員，系統(tǒng)運(yùn)維人員以及開發(fā)人員參與，一幫苦13程序員夜里3點(diǎn)多鬧鐘叫起來，睡眼朦朧的進(jìn)行機(jī)械的操作。難度可想而知。
?
基于這些技術(shù)特點(diǎn)，可以作如下分析
業(yè)務(wù)的變化要求數(shù)據(jù)擴(kuò)容的規(guī)則要盡可能的自定義，可以有些預(yù)先定義好的規(guī)則模型，但不能強(qiáng)制要求業(yè)務(wù)必須走定義好的模型。
自動(dòng)擴(kuò)容，意義不大，如果只是讓業(yè)務(wù)人員根據(jù)數(shù)據(jù)點(diǎn)個(gè)確定，是最容易被接受的擴(kuò)容模式
要盡可能的避免擴(kuò)容本身對(duì)業(yè)務(wù)本身帶來的影響，同時(shí)要盡可能減輕開發(fā)人員的熬夜次數(shù)。
?
所以我們?cè)O(shè)計(jì)了如下的系統(tǒng)，他滿足以下特性
規(guī)則完全自定義，你可以隨便寫任何的ifelse等腳本代碼。
只對(duì)擴(kuò)容需求提供決策支持和方案生成，但決策由人進(jìn)行。
除了決策，其余全部自動(dòng)化。
?
?
這套系統(tǒng)就是我們的自動(dòng)擴(kuò)容系統(tǒng)。
?
因?yàn)槲覀儗⒁赒1～Q2完全開源目前淘寶在300～400個(gè)系統(tǒng)中所使用的所有中間件，包括rpc調(diào)用框架，消息系統(tǒng)以及數(shù)據(jù)庫切分中間件，所以我的介紹本身將是對(duì)實(shí)現(xiàn)思路與細(xì)節(jié)的描述，無保留。
?
不過在這里，讓我懸念留給下一篇（喂喂喂，難道不是文章太長(zhǎng)導(dǎo)致的么？嘿嘿），在下一篇，我們將仔細(xì)介紹一下TDDL的規(guī)則引擎系統(tǒng)。
?
海量存儲(chǔ)之十三
http://qing.weibo.com/1765738567/693f084733000dby.html?
?在上一章中，我們主要介紹了規(guī)則引擎中最重要的一個(gè)部分，自動(dòng)擴(kuò)容，在今天的章節(jié)，我們主要還是介紹一下我們?cè)谔詫歍DDL中的工程實(shí)踐吧。
首先從原理開始吧。
先來一張圖
規(guī)則引擎是什么呢？
對(duì)應(yīng)在上述例子里面，其實(shí)就是DBNum = pk % 3 這個(gè)規(guī)則。
他的變化可能很多，比如對(duì)于一致性hash則變?yōu)橐粋€(gè)if - else 的表達(dá)式（見前面）
也可能有其他的變化。
所以，我們要回歸本源，問一個(gè)問題，什么是規(guī)則引擎？
抽象來看，規(guī)則引擎在做的事情是，根據(jù)一組輸入條件（例如主鍵id,或者用戶id+時(shí)間,或者一個(gè)rowKey），進(jìn)行了一種計(jì)算，然后返回在某個(gè)機(jī)器某個(gè)表上執(zhí)行的結(jié)果。這種計(jì)算要保證，在規(guī)則本身不發(fā)生變動(dòng)的情況下，同一組輸入條件，返回的永遠(yuǎn)是相同的結(jié)果。
想想這種描述像什么？:-) 我個(gè)人認(rèn)為很像函數(shù)的定義，那么讓我們換一下表述方式吧:
假設(shè)輸入數(shù)據(jù)為x(主鍵id,用戶id_時(shí)間，或者rowKey) ，經(jīng)過運(yùn)算F,返回了該數(shù)據(jù)在某臺(tái)機(jī)器上這個(gè)結(jié)果y.那么表達(dá)式就是
y = F(x)
這是第一層抽象，為了方便表述，我們后面都以這種方式進(jìn)行表述。
這種規(guī)則引擎，在幾乎所有“有狀態(tài)”的數(shù)據(jù)存儲(chǔ)中都會(huì)用到，在我們的工程實(shí)踐中，我們發(fā)現(xiàn)這套引擎需要非常靈活的表現(xiàn)能力，才能適應(yīng)不同用戶的不同需求，比如有些場(chǎng)景中，業(yè)務(wù)方會(huì)給出一批經(jīng)過數(shù)據(jù)分析以后的大賣家，他們固定的就擁有大量數(shù)據(jù)，會(huì)對(duì)其他人造成影響，這時(shí)候規(guī)則引擎必須能夠?qū)Ω鞣N不同的場(chǎng)景進(jìn)行適應(yīng)。
因?yàn)橐?guī)則能夠決定數(shù)據(jù)的分布是否均勻，因此規(guī)則是整套系統(tǒng)中最重要的核心組件。
有了規(guī)則引擎，我們要追尋的下一個(gè)目標(biāo)就是，如何能夠在盡量少的影響業(yè)務(wù)的正常使用的前提下，改變規(guī)則，以達(dá)到均衡訪問或擴(kuò)容的目標(biāo)。
要達(dá)到這個(gè)規(guī)則，第一個(gè)需要做的事情就是要能夠分辨，哪些數(shù)據(jù)應(yīng)該被移動(dòng)，以及從哪個(gè)源頭移動(dòng)到哪個(gè)目標(biāo)去。
要解決這個(gè)問題，在當(dāng)時(shí)能夠想到的方法有兩個(gè)，一個(gè)是定死的規(guī)則，比如一致性hash,一致性hash，因?yàn)橐?guī)則本身的入?yún)⑹嵌ㄋ赖?#xff0c;輸出也是定死的，所以可以知道從哪里移動(dòng)到哪里。但這也會(huì)帶來問題，因?yàn)橛行I(yè)務(wù)根本不是使用一致性hash來完成的，他們可能有自定義的函數(shù)（如：如果賣家id=2000，那么走特殊的機(jī)器） 。
一旦有這樣的自定義函數(shù)，那么就很難通過分析規(guī)則來獲取需要遷移的數(shù)據(jù)是哪些以及應(yīng)該從哪里移動(dòng)到哪里這些屬性了。
于是，就必須有另外的方法。
我們采取的方案，是完全放開F，采取多版本的方式來獲得“哪些數(shù)據(jù)應(yīng)該被移動(dòng)，以及從哪個(gè)源頭移動(dòng)到哪個(gè)目標(biāo)去”，這兩個(gè)信息。
原理如下:
我們假設(shè)有老規(guī)則 F0 ,以及新規(guī)則F1.
對(duì)于相同的輸入X,我們能得到兩個(gè)y，也即
y0 = F0(x) 以及y1 = F1(x)
對(duì)兩個(gè)y進(jìn)行比較(compare) ，能夠獲取兩種結(jié)果: 結(jié)果1 ： y0 == y1. 結(jié)果2 ： y0 != y1.
思考這兩種結(jié)果的含義，不難明白其中的含義：
如果y0 == y1,那么意味著，對(duì)于相同的數(shù)據(jù)x，在老規(guī)則和新規(guī)則中，數(shù)據(jù)都在同一個(gè)庫的同一張表上(y相同)，這條數(shù)據(jù)在老規(guī)則換為新規(guī)則的時(shí)候是不需要移動(dòng)的。
而，如果y0 != y1，那么意味著，這條數(shù)據(jù)，如果將規(guī)則從F0換為F1,則數(shù)據(jù)需要被移動(dòng)，移動(dòng)的方向應(yīng)該是從y0到y(tǒng)1.
這樣，我們就很輕松的使用多版本的方式，獲得了“哪些數(shù)據(jù)應(yīng)該被移動(dòng)，以及從哪個(gè)源頭移動(dòng)到哪個(gè)目標(biāo)去”，這兩個(gè)信息。
最后，在知道了上面的兩個(gè)關(guān)鍵的信息后，還需要一套東西來幫用戶把數(shù)據(jù)盡可能平滑的從一個(gè)源機(jī)器中移動(dòng)到目標(biāo)機(jī)器中。
這就是我們?cè)谄胶膺w移中進(jìn)行的思考，如果有想探討的歡迎一起參與。
下面，我們進(jìn)入工程實(shí)踐，來看一下我們的規(guī)則引擎在做的事情吧。
角色介紹
對(duì)于規(guī)則引擎，它實(shí)現(xiàn)了如下特性：
多版本支持
只有支持多版本，才能夠方便的知道哪些數(shù)據(jù)應(yīng)該從哪里移動(dòng)到哪里去。
枚舉支持
用來支持用戶按照日期進(jìn)行切分，但需要注意的是，這里的日期切分不是傳統(tǒng)意義上B樹模型的那種切分方式，原因見后續(xù)分析。
內(nèi)建多種切分函數(shù)支持
允許方便的直接使用內(nèi)置定義的一致性hash,虛擬節(jié)點(diǎn)hash等函數(shù)方法，減少代碼量。
與規(guī)則引擎配套的，還有一套我們目前叫做“大禹”的項(xiàng)目工程，他主要完成了以下幾件事：
切分?jǐn)?shù)據(jù)收集
能夠協(xié)助收集用戶切分后的數(shù)據(jù)狀態(tài)，如訪問熱點(diǎn)情況，硬件情況等。
決策支持
能夠幫助用戶定義新的擴(kuò)容策略，但我們不做“自動(dòng)化擴(kuò)容”，因?yàn)閿U(kuò)容本身不是常態(tài)。
自動(dòng)遷移
能夠根據(jù)用戶的多版本規(guī)則，協(xié)助用戶自動(dòng)化的進(jìn)行規(guī)則遷移，最終能夠?qū)?shù)據(jù)遷移導(dǎo)致的不可用時(shí)間降低到深夜1分鐘內(nèi)，基本不造成影響。
工程實(shí)踐描述
在我們的工程實(shí)踐中，我們選擇了groovy來實(shí)現(xiàn)java的規(guī)則引擎，使用javaScript來實(shí)現(xiàn)跨平臺(tái)的規(guī)則引擎。
從規(guī)則引擎來看，他只需要一個(gè)引擎，能夠運(yùn)行一個(gè)函數(shù)就可以了，所以上述平臺(tái)都可以滿足我們的需求，從速度角度考慮，我們選擇了可靜態(tài)編譯的groovy和js v8引擎。
在這個(gè)引擎之上，我們對(duì)引擎進(jìn)行了包裝，針對(duì)淘寶的特殊需求進(jìn)行了二次開發(fā)：
在淘寶，有很大一批數(shù)據(jù)是需要按照多個(gè)條件進(jìn)行切分的，如，按照用戶切庫后，按照時(shí)間切表等，針對(duì)這種需求，我們要擴(kuò)展原來的函數(shù)定義，允許用戶使用類似table+"_"+ #userid# % 1024 +"_" + dayofmonth(#gmt#);
這樣的方式來拼裝類似table_0001_23這樣的表后綴.實(shí)現(xiàn)多維度的切分。
同時(shí)，還需要滿足用戶的范圍查詢需求，如，返回一個(gè)用戶在某個(gè)時(shí)間段內(nèi)的所有數(shù)據(jù)。這往往意味著可能要遍歷多個(gè)分表的需求，針對(duì)這種需求，我們?cè)试S用戶使用表達(dá)式的方式填入y = F(x)中的'x' ,如 'x' = (gmt <= now() ) and (gmt >'2012-01-01' ) 這樣的輸入?yún)?shù)。
針對(duì)這樣的參數(shù)，傳統(tǒng)的解決方案是使用排序后的樹形結(jié)構(gòu)來滿足查詢（如hbase），我們認(rèn)為，因?yàn)閿?shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)本身是有限的，我們沒有必要維持復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，只需要使用枚舉的方式就可以達(dá)到類似的效果，因?yàn)轭w粒度可控。
對(duì)于大禹工程
排開數(shù)據(jù)收集以及分析后展現(xiàn)之外，最重要的部分無疑是能夠根據(jù)多版本的規(guī)則進(jìn)行自動(dòng)化的擴(kuò)容和遷移這一塊了。
他的主要流程如下: 舉個(gè)例子來說明這個(gè)流程
從整體來看，大禹在做的事情就是，全量遷移所有需要移動(dòng)的數(shù)據(jù)，然后將在全量過程中產(chǎn)生的增量數(shù)據(jù)append到新節(jié)點(diǎn)上，然后部分停寫1分鐘，推送規(guī)則的新版本。完成遷移。
我們假定原來有一臺(tái)機(jī)器，里面有兩條記錄:
row a : id = 0 ,name = "a"
row b : id = 1 ,name = "b"
切分的規(guī)則為 id % 1 ,
那么我們根據(jù)表達(dá)式 y0 = id % 1 ,分別將id(row a) = 0 ;id(row b) = 1代入表達(dá)式，得到y(tǒng)0(row a) = 0; y0(row b) = 0;
這兩個(gè)結(jié)果。
然后，我們要將機(jī)器擴(kuò)容為兩臺(tái)，
這時(shí)候規(guī)則變?yōu)?y1 = id % 2,分別將id(row a) = 0 ;id(row b) = 1代入表達(dá)式，得到y(tǒng)0(row a) = 0; y0(row b) = 1;
這時(shí)候，用戶新寫入了一條數(shù)據(jù)row c : id = 3 , name="c"
因?yàn)橛脩粼谑褂美弦?guī)則寫入，所以使用老規(guī)則后，數(shù)據(jù)應(yīng)該通過老規(guī)則計(jì)算出結(jié)果y0(row c) = id % 1 = 0;
在按老規(guī)則寫入后，數(shù)據(jù)就已經(jīng)可見了，這時(shí)候，大禹會(huì)讀取這條記錄，按照新規(guī)則進(jìn)行計(jì)算，y1(row c) = id % 2 = 1; 因?yàn)? != 0,所以row c 需要進(jìn)行遷移，遷移目標(biāo)是從0機(jī)器--> 1機(jī)器。
這時(shí)候大禹會(huì)將這條數(shù)據(jù)保存在本地磁盤中。
而如果假定row d 通過新老規(guī)則計(jì)算出的結(jié)果y0 (row c) == y1 ( row c) 則該數(shù)據(jù)會(huì)被大禹增量復(fù)制組件丟棄，因?yàn)閿?shù)據(jù)在規(guī)則變動(dòng)后不需要移動(dòng)位置。
在增量開啟后，會(huì)進(jìn)行全量的遷移。
全量的過程與增量類似，是按照選擇條件，將老機(jī)器內(nèi)的指定數(shù)據(jù)遍歷一次，對(duì)每一條記錄，進(jìn)行老規(guī)則和新規(guī)則的計(jì)算，如果計(jì)算結(jié)果相同則丟棄，計(jì)算結(jié)果不同，則將數(shù)據(jù)寫入新規(guī)則算出后的結(jié)果。
當(dāng)全量結(jié)束后，大禹增量復(fù)制組件會(huì)將記錄在本地磁盤中的增量數(shù)據(jù)覆蓋到全量后的數(shù)據(jù)上，并且繼續(xù)隨著新的數(shù)據(jù)產(chǎn)生，將數(shù)據(jù)雙寫在老規(guī)則和新規(guī)則所對(duì)應(yīng)的機(jī)器上。并發(fā)出catch up的狀態(tài)指令。
在catch up后，我們可以認(rèn)為，老規(guī)則內(nèi)的數(shù)據(jù)和新規(guī)則內(nèi)的數(shù)據(jù)，是異步一致的，中間的數(shù)據(jù)延遲是異步復(fù)制的延遲，一般來說在幾百個(gè)毫秒內(nèi)。
這時(shí)候，就可以選擇一個(gè)合適的時(shí)機(jī)，比如夜里5點(diǎn)，進(jìn)行部分停寫，等待新老數(shù)據(jù)絕對(duì)一致以后，發(fā)布新規(guī)則。完成遷移。
整個(gè)遷移過程，只有最后的“部分停寫，等待新老數(shù)據(jù)絕對(duì)一致以后，發(fā)布新規(guī)則。完成遷移“ 是會(huì)影響業(yè)務(wù)應(yīng)用的，這之前的所有過程都是個(gè)外加過程，對(duì)業(yè)務(wù)完全沒有影響，就算異常失敗了，也可以全部放棄掉以后重新來過，這就保證了整套邏輯的盡可能簡(jiǎn)單清晰。
好的軟件就是少做不該做的事情的軟件嘛 :)
以上是好的地方，下面來自暴家丑，說說不足。
規(guī)則引擎所面向的目標(biāo)，其實(shí)是有狀態(tài)數(shù)據(jù)的節(jié)點(diǎn)管理，對(duì)于節(jié)點(diǎn)管理來說，大家的追求一般都是有共識(shí)的，也就是說，可以按照需求，隨便的增加或減少節(jié)點(diǎn)。但遺憾的是，目前在我們的工程實(shí)踐中，目前還沒能很好的解決“隨便”這個(gè)需求。
所謂隨便，就是指可以達(dá)到這樣一個(gè)效果，某天某個(gè)監(jiān)控人員，發(fā)現(xiàn)某些數(shù)據(jù)突然的成為熱點(diǎn)了，那么它可以快速反應(yīng)，點(diǎn)個(gè)按鈕，上線100臺(tái)機(jī)器，立刻load下降，保證了系統(tǒng)穩(wěn)定。然后呢，發(fā)現(xiàn)某個(gè)集群load很低，就點(diǎn)個(gè)按鈕，下線100臺(tái)機(jī)器作戰(zhàn)略儲(chǔ)備。
可惜，這樣的事情在有狀態(tài)的機(jī)器中是很難做到的，原因很簡(jiǎn)單，有狀態(tài)節(jié)點(diǎn)的數(shù)據(jù)遷移是需要成本的，而且成本不小，這也是為什么foursquare會(huì)掛的原因。
以上，就是我對(duì)淘寶TDDL 數(shù)據(jù)庫切分tool kits中規(guī)則引擎和配套的自動(dòng)擴(kuò)容組件的介紹了。
目前淘寶的TDDL組件被廣泛的使用在淘寶300多個(gè)不同的業(yè)務(wù)系統(tǒng)中，并且沒有使用過強(qiáng)制命令進(jìn)行推廣。
在未來的一個(gè)Q內(nèi)，我們會(huì)逐漸的開源我們目前的這套工程實(shí)踐產(chǎn)品，希望有更多的人能夠受益。
轉(zhuǎn)載于:https://www.cnblogs.com/davidwang456/p/3856233.html
總結(jié)
以上是生活随笔為你收集整理的海量存储系列下--转载，值得一读的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 海量存储系列上--转载，值得一读
- 下一篇： 独立硬盘冗余阵列与HDFS