海量存儲(chǔ)系列之三

首先是回答上次的問題。

假設(shè)有這么一組數(shù)據(jù)，性別有4種，user_id是一對多的關(guān)系，如果我想查詢

select * from tabwhere user_id in (?,?,?,?) and 性別='不明'

如何進(jìn)行索引構(gòu)建能夠獲得比較好的效果呢？

我個(gè)人認(rèn)為，應(yīng)該建立的是以user_id作為前導(dǎo)列，性別作為輔助列的索引，在大量單值查詢時(shí)會(huì)有優(yōu)勢。

理由如下

1. 假定總數(shù)據(jù)量為N,user_id的區(qū)分度為N/10000 而性別的區(qū)分度為N/4

那么如果以user_id作為前導(dǎo)列，性別作為后列，那么查詢的復(fù)雜度為O(logN+log(N/10000))。也就是說，第一次二分查找之后，下一次是在第一次的二分查找的基礎(chǔ)上再去查找。而如果以性別作為前導(dǎo)，user_id作為后列，那么復(fù)雜度為

O(logN+log(N/4));

效率略差。

然后進(jìn)入本次正題。上次介紹了關(guān)系模型，那么這次我們來介紹一下事務(wù)。

在一切之前，我想先給自己解嘲一下。。事務(wù)我自己也沒有辦法完全融匯貫通，因?yàn)槊恳粋€(gè)小的選擇，都會(huì)導(dǎo)致效果的完全不同，所以有錯(cuò)請?jiān)诤竺嬉黄鹛接憽?/p>

那么我們在這里，主要以單機(jī)事務(wù)作為入手點(diǎn)，然后闡述一下多機(jī)事務(wù)相關(guān)的知識(shí)點(diǎn)。我在這里只是想做一個(gè)引導(dǎo)，讓大家能夠?qū)φ麄€(gè)的知識(shí)體系有一個(gè)基本的認(rèn)識(shí)，對于細(xì)節(jié)問題，會(huì)給出一些資料，而不會(huì)直接去進(jìn)行講解，因?yàn)槠?

一般來說，我們一提起事務(wù)，就會(huì)想到數(shù)據(jù)庫，確實(shí)，事務(wù)是數(shù)據(jù)庫的最重要的一個(gè)屬性。但這似乎不是事務(wù)的本源，那么，讓我們從更深層次去對事務(wù)進(jìn)行一次思考吧：

事務(wù)，本質(zhì)來說就是一組由一個(gè)人（或機(jī)器）發(fā)起的連續(xù)的邏輯操作，共同的完成一件事情，在完成整個(gè)事情之前，其所有的改動(dòng)，都不應(yīng)該對其他人可見和影響。而在事務(wù)結(jié)束之后，其一切的改動(dòng)，都必須“全部”“立刻”對其他的人（或機(jī)器）可見。

然后，人們?yōu)榱嗣枋鲞@一運(yùn)作,使用了四個(gè)詞匯，這也是很多面試的同學(xué)們折戟沉沙之處。J 不過這個(gè)以前我也不會(huì)，后來發(fā)現(xiàn)，理解了以后，確實(shí)有點(diǎn)用，所以這里也費(fèi)一些筆墨吧。

原子性(Atomicity)：也就是說，一組操作，要不就都成功，要不就都失敗。不存在中間狀態(tài)。

一致性(Consistency)：一致性，也就是說，這個(gè)事務(wù)在提交或回滾的時(shí)候，對其他人（或機(jī)器）來說，數(shù)據(jù)的狀態(tài)是同一的，不會(huì)出現(xiàn)中間的狀態(tài)。最理想的狀態(tài)下，就是說，數(shù)據(jù)提交后，所有的更改立刻同時(shí)生效，可惜，在計(jì)算機(jī)領(lǐng)域，這個(gè)做不到。。因?yàn)閏pu運(yùn)算，磁盤寫入，內(nèi)存寫入，都是要時(shí)間的，內(nèi)部一定是個(gè)順序化的過程，所以不可能做到絕對的立刻同時(shí)生效。

所以一致性一般來說指代的是邏輯上的同時(shí)生效，比如，我要改A,B兩行數(shù)據(jù)，那么，最簡單的一致性保證就是，對A,B加鎖，改A,B，然后對A，B解鎖。

這樣下一個(gè)人讀到的一定是A,B的最新值啦。

（但這塊有很多種解釋，一般來說這是個(gè)最不明確的詞匯）。

隔離性(Isolation)：隔離，這是面試最容易掛的一個(gè)問題，其實(shí)我認(rèn)為不怪我們，而是因?yàn)楸旧磉@個(gè)隔離性，是依托鎖來進(jìn)行設(shè)計(jì)的。

我們所知道的鎖，主要有以下幾種，1.讀寫鎖，2. 排他鎖

那么這四種級別其實(shí)就和這兩種鎖的實(shí)現(xiàn)有關(guān)，之所以要定義四個(gè)級別，其實(shí)原因也是因?yàn)?，鎖的范圍越大，并行效率越低。而范圍越小，那么并行的效率就越高。

讀未提交： 其實(shí)就是什么鎖也沒有，所以數(shù)據(jù)的中間狀態(tài)，是可能被其他人讀到的。

讀已提交：就是讀寫鎖實(shí)現(xiàn)，讀鎖在查詢之后會(huì)被釋放掉，所以這樣其他人可能會(huì)更改那些被釋放了讀鎖的數(shù)據(jù)，這樣當(dāng)前事務(wù)再去讀取的時(shí)候，就可能讀取到被別人修改過的數(shù)據(jù)了，所以一個(gè)人在事務(wù)中讀取到的某個(gè)數(shù)據(jù)，可能下次讀取就變成別的數(shù)據(jù)啦。這就是不可重復(fù)讀的意思。。

可重復(fù)讀：也是個(gè)讀寫鎖實(shí)現(xiàn)，讀鎖會(huì)阻塞其他人（或機(jī)器）的寫，于是，只要是事務(wù)中讀取到得數(shù)據(jù)，都被加了鎖，其他人沒辦法改他們，于是就實(shí)現(xiàn)了可重復(fù)讀咯。

最后是序列化，就是所有都順序，一個(gè)大鎖全部鎖住J

持久性(Durability)：持久性就是，事務(wù)執(zhí)行后，就丟不了了，就算是整個(gè)中國被淹了，機(jī)器都沒了，數(shù)據(jù)也不應(yīng)該丟掉（不過基本做不到這個(gè)，也就是一個(gè)機(jī)器掛了不會(huì)丟數(shù)據(jù)而已。。）所有機(jī)房沒了那數(shù)據(jù)也就沒了。。

對于這塊，給大家一些參考資料：

http://zh.wikipedia.org/wiki/%E4%BA%8B%E5%8B%99%E9%9A%94%E9%9B%A2

在下一個(gè)章節(jié)，我們繼續(xù)在事務(wù)這個(gè)領(lǐng)域徜徉，給大家介紹一下，在單機(jī)上面，事務(wù)是如何進(jìn)行的。

海量存儲(chǔ)系列之四

http://qing.weibo.com/1765738567/693f08473300067j.html 單機(jī)事務(wù)

單機(jī)事務(wù):

其實(shí)在上面介紹ACID的時(shí)候

我們已經(jīng)提到了一種最簡單的實(shí)現(xiàn)方式，就是鎖的實(shí)現(xiàn)方式。

從原理來看，事務(wù)是個(gè)變態(tài)而復(fù)雜的事情。其實(shí)如果是序列化的話呢，那么實(shí)現(xiàn)起來一定是非常簡單的。

但問題就在于，這樣性能實(shí)在比較低，于是，就有了非常多的方案，為了能哪怕減少一個(gè)地方的鎖，或者降低一個(gè)地方的鎖的級別，就付出大量的時(shí)間和代碼加以實(shí)現(xiàn)。

那么，讓我們以崇敬的心情，去拜讀一下他們的勞動(dòng)成果吧~

 --------------------------------------------------------------------------------

在上一篇中，我們談了事務(wù)管理的四個(gè)核心要素，其中有兩個(gè)要素是和性能緊密相關(guān)的，其實(shí)也就是需要涉及到鎖的，一個(gè)是隔離性，一個(gè)是一致性。

一致性問題和隔離性問題，我們都可以歸結(jié)為一個(gè)問題，他們都用于定義，什么時(shí)候數(shù)據(jù)可被共享，什么時(shí)候數(shù)據(jù)必須被獨(dú)占。而這些決策，就最終決定了整個(gè)數(shù)據(jù)庫系統(tǒng)的并行度，也就直接的決定了多線程并發(fā)時(shí)的性能指標(biāo)。

如果要改一大批數(shù)據(jù)，又必須保證這些數(shù)據(jù)要么都出現(xiàn)，要么都不出現(xiàn)，這時(shí)候就有個(gè)難題了：因?yàn)檫@些數(shù)據(jù)不可能在同一個(gè)時(shí)間被選出，更不可能在同一個(gè)時(shí)間被更改。

于是就必須想個(gè)辦法來假裝達(dá)到這個(gè)狀態(tài)，于是我們就需要一種方法，使得針對不同數(shù)據(jù)的更改，不同人（或機(jī)器）不打架。而如果出現(xiàn)對相同數(shù)據(jù)的更改，則要將更新進(jìn)行排隊(duì)。

這個(gè)排隊(duì)可供選擇的方法，就我知道的有：1，排他鎖。2. 讀寫鎖。3. Copy on write（MVCC） .4. 隊(duì)列。5. 內(nèi)存事務(wù)。這些方式。

從性能來說，排他鎖最慢，而讀寫因?yàn)樽x可以并發(fā)，所以效率稍高，但寫和讀不能同時(shí)進(jìn)行。3. Copy on write(MVCC) 則讀取和寫入之間可以互相不影響，所以效率更高。隊(duì)列這種方式，內(nèi)存時(shí)效果很好，省去中斷上下文切換的時(shí)間。內(nèi)存事務(wù)，目前還在研究階段，具備很大潛力的東西。

排他鎖，隊(duì)列和內(nèi)存事務(wù)，在目前的數(shù)據(jù)庫中用的相對較少，我們就不在這里說了。

這里主要說兩種實(shí)現(xiàn)，一種是讀寫鎖，一種是MVCC.

先說讀寫鎖，也是隔離性中“讀已提交，可重復(fù)讀”兩種實(shí)現(xiàn)中最重要的底層實(shí)現(xiàn)方式。

簡單來說，就是如果一個(gè)人在事務(wù)中，那么他所有寫過的數(shù)據(jù)，所有讀過的數(shù)據(jù)，都給他來個(gè)鎖，讓其他小樣兒都只能等在外面，直到數(shù)據(jù)庫能確定所有更改已經(jīng)全部完成了，沒有剩下什么半拉子狀態(tài)的時(shí)候，就解開所有的鎖，讓其他人可以讀取和寫入。Hoho,就是這個(gè)了。

那么MVCC呢，其實(shí)是對讀寫鎖的一個(gè)改進(jìn)，有一批大牛們，說你們這讀寫鎖，寫的時(shí)候不能讀，讀的時(shí)候不能寫，并行度太低了，我要做個(gè)更牛B的，寫不阻塞讀，讀不阻塞寫的東西來超越你們。

于是他們想起了copy-on-write.鼓搗了個(gè)MVCC數(shù)據(jù)庫出來。。。

題外話，現(xiàn)在的甲骨文，之所以能在數(shù)據(jù)庫領(lǐng)域保持優(yōu)勢地位，有個(gè)很重要的原因也是因?yàn)樗麄兪呛茉缇驮谏虡I(yè)數(shù)據(jù)庫系統(tǒng)中實(shí)現(xiàn)了MVCC的數(shù)據(jù)寫入引擎。

所以他們的Thomas Kyte 技術(shù)副總裁也就有了在他們的最牛逼的oracle專家編程里面有了吹噓的資本 XD .

這里我們要著重的介紹一下MVCC，因?yàn)檫@東西看起來非常的精妙而美麗。?！，F(xiàn)在大量的分布式類存儲(chǔ)中，也都在借鑒這套模式中的很多部分來增加自己的并行度，以提升性能。比如megaStore.比如percolator。

我們在讀寫鎖的實(shí)現(xiàn)中，提到了寫讀的相互阻塞問題，MVCC則使用copy-on-write來解決這個(gè)問題。

如果一個(gè)人在事務(wù)中，會(huì)先申請一個(gè)事務(wù)ID,這個(gè)ID是自增的，每個(gè)事務(wù)都有他自己的唯一的ID，那么他寫過的數(shù)據(jù)，都會(huì)被轉(zhuǎn)變?yōu)橐淮螏в挟?dāng)前事務(wù)ID的新數(shù)據(jù)，在讀取的時(shí)候，則只會(huì)讀取小于等于自己事務(wù)ID的數(shù)據(jù)。這樣實(shí)現(xiàn)的東東，語義上來說，與可重復(fù)讀就一樣了。而如果讀小于等于全局ID的數(shù)據(jù)，那么這樣的實(shí)現(xiàn)，就是讀已提交了。

一般來說，MVCC只實(shí)現(xiàn)了四個(gè)級別中的第二級和第三級，其他的就沒有啦，不過這兩個(gè)是我們最常見的級別。所以也就大家同樂，同樂了~

有了這個(gè)東西，我們的一致性也就很容易保證了，因?yàn)橐粋€(gè)事物和他對應(yīng)的版本號(hào)對應(yīng)，又有更改后的數(shù)據(jù)和更改前的數(shù)據(jù)，如果要提交，那么就只需要很簡單的讓更改后的數(shù)據(jù)生效可見即可，這樣我們可以將大量的更新中要做的事情，都在事務(wù)過程中進(jìn)行，這樣，比原有的基于讀寫鎖的必須在commit時(shí)候一起做掉來說，commit這個(gè)操作就輕量化了很多，于是，就可以支持更多的人（或機(jī)器）持有事務(wù)狀態(tài)了。

很美妙吧？

我一致認(rèn)為這是oracle當(dāng)年的核心競爭力，不過現(xiàn)在基本上是個(gè)數(shù)據(jù)庫就用了這一套，我們就不在多嘴啦~

解決了一致性和隔離性，剩下的是原子性和持久性，原子性么，一般來說就是要么都成功，也就是新版本數(shù)據(jù)都讓他生效，要么就都失敗，也就是讓和自己事務(wù)ID對應(yīng)的所有修改都無效即可。也很好就解決掉了。持久性。這個(gè)就是后面我們要在寫入模型里面介紹的東西了，基本上來說就是寫磁盤策略的事情。

到這里，我們單機(jī)ACID的實(shí)現(xiàn)大概思路，就給大家介紹過了。下一個(gè)章節(jié)，我們還要用很多的文字，來向大家介紹在分布式場景中我們面臨的事務(wù)的難題，以及“我所知道的”百花齊放的解決方法。

海量存儲(chǔ)系列之五

http://qing.weibo.com/1765738567/693f0847330006ao.html?rnd=0.6134993201121688

在上一章節(jié)，我們一起瀏覽了如何進(jìn)行單機(jī)事務(wù)操作。下面我們來看一下分布式場景中我們碰到的問題吧。

需要說明的一點(diǎn)是，這里涉及到的權(quán)衡點(diǎn)非常的多。就我短短的工作經(jīng)驗(yàn)里面，也只是能夠簡單的涉獵一部分，因?yàn)樵谑聞?wù)這個(gè)領(lǐng)域，目前大家都在嘗試提出各種各樣的不同的方法，而在taobao，我們目前也沒有完美的解決這個(gè)問題，更多的是在權(quán)衡，在金錢和開發(fā)成本之間，做出選擇。

那么，我們就先從問題開始，來看一下原來的事務(wù)出了什么問題。

在事務(wù)中，有ACID四種屬性。（見上篇文章）

在分布式場景中，我們看引入了什么因素，導(dǎo)致了什么樣的新問題：

1.      延遲因素:光是我們所知最快的信息載體了，各位可能都會(huì)從潛意識(shí)里面認(rèn)為光傳輸信息不就是一眨眼的事情而已。那我們做個(gè)簡單的計(jì)算吧（感謝@淘寶叔度，第一次在分享中讓我對這個(gè)問題有了個(gè)數(shù)值化的印象。）：

北京到杭州，往返距離2600km ，光在真空中的傳輸速度是30wkm/s。在玻璃中的速度是真空的2/3。算下來，最小的請求和響應(yīng)，之間的延遲就有13ms。并且，因?yàn)楣庠诠茏永镒叩牟皇侵本€，又有信號(hào)干擾等問題，一般來說要乘以2~3倍的因子值。

所以一次最小的請求和響應(yīng)，時(shí)間就差不多有30ms左右了。

再想想TCP的時(shí)間窗口的移動(dòng)策略，相信大家都能意識(shí)到，實(shí)際上延遲是不可忽略的，尤其在傳輸較多數(shù)據(jù)的時(shí)候，延遲是個(gè)重要的因素，不能不加以考慮。

并且，延遲 不是 帶寬，帶寬可以隨便增加，千兆網(wǎng)卡換成萬兆，但延遲卻很難降低。而我們最需要的，是帶寬，更是延遲的降低。因?yàn)樗苯記Q定了我們的可用性。

2.      災(zāi)備因素：單機(jī)的情況下，人們一般不會(huì)去追求說一個(gè)機(jī)器物理上被水沖走了的時(shí)候，我的數(shù)據(jù)要保證不丟（因?yàn)闆]辦法的嘛。。）。但在分布式場景下，這種追求就成為了可能，而互聯(lián)網(wǎng)行業(yè)，對這類需求更是非?？粗?，恨不能所有的機(jī)器都必須是冗余的，可隨意替換的。這樣才能保證7*24小時(shí)的正常服務(wù)。這無疑增加了復(fù)雜度的因素。

3.      Scale out的問題： 單機(jī)總是有瓶頸的，于是，人們的追求就一定是：不管任何一種角色的機(jī)器，都應(yīng)該可以通過簡單的增加新機(jī)器的方式來提升整個(gè)集群中任何一個(gè)角色的性能，容量等指標(biāo)。這也是互聯(lián)網(wǎng)行業(yè)的不懈追求。

4.      性能：更快的響應(yīng)速度，更低的延遲，就是更好的用戶體驗(yàn)。（所以google用了個(gè)“可憐”到家的簡單input框來提升用戶體驗(yàn)，笑）。

說道這里，大概大家都應(yīng)該對在分布式場景下的廣大人民群眾的目標(biāo)有了一個(gè)粗略的認(rèn)識(shí)了。

那么我們來看一下原有ACID的問題吧。

在上次的章節(jié)中，我們也提到了ACID中，A和D相對的，比較容易達(dá)到。但C和I都涉及到鎖實(shí)現(xiàn)，也就和性能緊密的相關(guān)了。

然后，人們就開始了糾結(jié)，發(fā)掘這個(gè)C和I，似乎不是那么容易了。

上次，我們談到，目前主流的實(shí)現(xiàn)一次更新大量數(shù)據(jù)的時(shí)候，不同人（或機(jī)器）修改數(shù)據(jù)相互之間不會(huì)打架的方法有以下幾種：

1.      排他鎖

2.      讀寫鎖

3.      Copy-on-write

4.      隊(duì)列

5.      內(nèi)存事務(wù)

排他鎖和讀寫鎖，本身都是鎖的實(shí)現(xiàn)，單機(jī)的鎖實(shí)現(xiàn)，相對而言是非常簡單的事情，但如果涉及到分布式鎖，那么消耗就很高了，原因是，鎖要在兩邊都達(dá)到一致，需要多次機(jī)器之間的交互過程，這個(gè)交互的過程，再考慮到延遲的因素，基本上一次加鎖請求就要100~200+毫秒的時(shí)間了，那么去鎖又要這樣的時(shí)間。而要知道，我們在單機(jī)做內(nèi)存鎖操作，最慢也不過10毫秒。。

于是，有一批人就說了，既然這么難，我們不做了！~來個(gè)理論證明他很難就行了~。于是就有了CAP和BASE.

所謂CAP，我個(gè)人的理解是描述了一種： 在數(shù)據(jù)存了多份的前提下，一致性和響應(yīng)時(shí)間，讀寫可用性不可兼得的“現(xiàn)象”而已。

在我這里來看CAP的證明過程就是個(gè)扯淡的玩意兒，他只是描述了一種現(xiàn)象而已。原因還是網(wǎng)絡(luò)延遲，因?yàn)檠舆t，所以如果要做到數(shù)據(jù)同時(shí)出現(xiàn)或消失，那么按照鎖的方式原來可能只需要10ms以內(nèi)完成的操作，現(xiàn)在要200~400ms才能完成，那自然不能接受了。所謂CAP就是這個(gè)現(xiàn)象的英文簡稱，笑。

BASE呢，這個(gè)理論似乎更老，其實(shí)也是個(gè)現(xiàn)象，就是基本可用，軟狀態(tài)，最終一致的簡稱，也沒個(gè)證明，其實(shí)就是告訴咱：要權(quán)衡一下，原來的ACID不太容易實(shí)現(xiàn)啦，我們得適當(dāng)放棄一些啦。但請各位注意，ACID實(shí)際上是能夠指導(dǎo)我們在什么情況下做什么樣的事情能夠獲取什么樣的結(jié)果的。而BASE則不行，這也說明BASE不是個(gè)經(jīng)典的理論。

好啦。廢話了這么多，其實(shí)就是想說，分布式場景沒有銀彈啦，你們自己權(quán)衡去吧。我們大牛們救不了你們啦的意思。。

既然大牛救不了咱，咱就只能自救了。。。

好，好的文章就要在關(guān)鍵的地方恰然而止，留下懸念，我們也就在這里留下點(diǎn)懸念吧。

在這篇中，主要是想給大家介紹一下，目前在分布式場景中，事務(wù)碰到了什么問題，出現(xiàn)這些問題的原因是什么。

在下一篇中，我將嘗試從原理的角度，去分析目前的幾類常見的在分布式場景中完成原有事務(wù)需求的方法。敬請期待 : ) 

海量存儲(chǔ)系列之六

http://qing.weibo.com/1765738567/693f0847330007ay.html

抱歉大家，間隔有點(diǎn)久，因?yàn)檫@一章要比較細(xì)致的總結(jié)，所以有些時(shí)間耽誤。上次我們講到，單機(jī)事務(wù)個(gè)我們面臨的問題，下面我們來說一些我所知的解決的方法。

在我開始做淘寶數(shù)據(jù)層的時(shí)候，被問得最多的無非也就是：如何做事務(wù)，如何做join.至今仍然如此，我一般都會(huì)簡單而明確的跟對方說：沒有高效的實(shí)現(xiàn)方法。

雖然沒有高效的實(shí)現(xiàn)，但實(shí)現(xiàn)還是有的。作為引子，我們先來介紹一下這種實(shí)現(xiàn)的方式。

我們?nèi)匀灰陨弦淮沃v到的bob和smith為例子來說明好了。

開始的時(shí)候。Bob要給smith100塊，那么實(shí)際上事務(wù)中要做的事情是

事務(wù)開始時(shí)查詢bob有多少錢。如果有足夠多的錢讓bob的賬戶 -100 ,然后給smith 的賬戶+100 。最后事務(wù)結(jié)束。

如果這個(gè)事情在單機(jī)，那么事情可以使用鎖的方式加以解決。

但如果bob在一臺(tái)機(jī)器，smith在另外一臺(tái)機(jī)器，我們應(yīng)該怎么做呢？

第一種最常被人想起的方法，就是兩段提交協(xié)議。

兩段提交協(xié)議從原理上來說是非常簡單的一套協(xié)議。

Prepare(bob-100) at 機(jī)器A->prepare (smith+100) at 機(jī)器b ->commit(bob) ->commit(smith)

事務(wù)結(jié)束。

兩段提交的核心，是在prepare的階段，會(huì)對所有該操作所影響的數(shù)據(jù)加鎖，這樣就可以阻止其他人（或機(jī)器）對他的訪問。題外話，問個(gè)問題: ）如果這時(shí)有其他節(jié)點(diǎn)，用相反的方向，進(jìn)行更新，也就是先更新smith,然后更新bob.會(huì)有可能發(fā)生什么事情呢？

兩段提交協(xié)議是被我們在大部分場景下放棄的一個(gè)模型，原因主要是因?yàn)?/p>

1.      Tm本身需要記錄事務(wù)進(jìn)行的過程，log要保證安全和可信，性能非常低。

2.      鎖的利用率和并行性較低。

3.      網(wǎng)絡(luò)開銷較大

4.      可見性要求實(shí)際上就等于讓快的操作等慢的。

所以從性能角度來說，這類需求不多也不常見。

既然這樣的模型不行，有沒有其他模型可以使用呢？

有的。

在事務(wù)的過程中，細(xì)心的讀者不難發(fā)現(xiàn)，實(shí)際上事務(wù)中并不需要這么強(qiáng)的一致可見性。

Bob是需要強(qiáng)一致的，因?yàn)樗牟僮餮鲑囉谒卸嗌馘X，如果他的錢不夠100，那么是不能讓他的賬戶變?yōu)樨?fù)數(shù)的。但smith卻不需要，smith不需要判斷他的賬戶有多少錢，只需要把錢加到他的賬戶里，不少給他，到賬時(shí)間盡可能短就可以。

Smith不需要chech賬戶的錢數(shù)，這個(gè)前提非常重要，這也是我們能使用最終一致性的關(guān)鍵因素。

下面，我們來看一下另外的選擇吧。

Bob的賬號(hào)在機(jī)器A上，smith的賬號(hào)在機(jī)器b上。

首先，我們在機(jī)器A上做以下操作:

1.      本地事務(wù)開始

2.      讀取bob的賬戶

3.      判斷是否有充足余額

4.      更新bob的賬號(hào)，將bob的錢減少100

5.      將需要給smith加100塊這個(gè)操作，以事務(wù)的形式插入到同機(jī)(A)的一張log表中，并自動(dòng)生成一個(gè)唯一的transactionID。

6.      事務(wù)關(guān)閉

然后，異步的發(fā)送一個(gè)通知，給一個(gè)消費(fèi)者。

消費(fèi)者接到通知后，從bob的機(jī)器上讀取到需要給smith+100這個(gè)操作，以及該操作所對應(yīng)的transactionID。

然后，按照如下方法進(jìn)行運(yùn)作

1.      查看在去重表內(nèi)是否有對應(yīng)的transactionID.如果沒有，則

2.      開啟本地事務(wù)

3.      將smith的賬戶+100

4.      將transactionID 插入去重表

5.      事務(wù)結(jié)束

這樣，我們也可以完成一個(gè)交易的核心流程了。在交易類過程中的大量事務(wù)操作，都是以這樣的方式完成的。

下面，我們針對上面的這個(gè)流程的一些抉擇的點(diǎn)進(jìn)行一些探討。

首先，是bob這個(gè)機(jī)器，這里涉及第一個(gè)抉擇點(diǎn)。

如果bob是個(gè)消費(fèi)大戶，短時(shí)間內(nèi)進(jìn)行了大量購買，那么可能會(huì)造成的問題是，bob所在的那個(gè)機(jī)器會(huì)成為熱點(diǎn)，如果在某個(gè)突發(fā)的情況下，某個(gè)賬戶突然成為熱點(diǎn)，那么這些有狀態(tài)的數(shù)據(jù)很難快速的反應(yīng)并加以處理，會(huì)造成事務(wù)數(shù)在某個(gè)單節(jié)點(diǎn)大量堆積。造成掛掉。

可能的解決方法是：

1.      利用兩段提交協(xié)議來讓原來的” 將需要給smith加100塊這個(gè)操作，以事務(wù)的形式插入到同機(jī)(A)的一張log表中，并自動(dòng)生成一個(gè)唯一的transactionID”這步操作放在另外的一臺(tái)機(jī)器上進(jìn)行。

這樣做的的好處是，無論bob怎么是熱點(diǎn)，都可以通過水平的加log機(jī)器的方式來防止這種熱點(diǎn)的產(chǎn)生。

壞處則有：

         1方案復(fù)雜度高

         2額外的網(wǎng)絡(luò)開銷

         3消息基于網(wǎng)絡(luò)發(fā)送后，會(huì)可能得到三個(gè)可能的反饋：1. 成功 2. 失敗 3. 無反饋。最麻煩的就是這個(gè)無反饋，他可能成功，也可能失敗。所以是不確定的狀態(tài)，需要進(jìn)行事務(wù)的兩邊進(jìn)行第二次確認(rèn)，來確保這個(gè)事務(wù)的參與方是否都做了該做的事情，如果有一方做了類似commit的操作，那么另外的一方應(yīng)該commit.如果兩方都沒做commit操作，那么應(yīng)該回滾。

2.      讓bob的庫余量更高，并按照訪問壓力進(jìn)行數(shù)據(jù)的切分，按照熱度進(jìn)行數(shù)據(jù)劃分，放棄原有的簡單取mod的策略。來兼容這種不均勻特性。

其次，如果有80個(gè)系統(tǒng)都關(guān)注著smith加了100這個(gè)操作的log，要做對應(yīng)的處理（比如一些人要針對這個(gè)加錢操作做個(gè)打款短信推送，有些要做個(gè)數(shù)據(jù)分析等等），那么這里就有另外一個(gè)問題，這些系統(tǒng)對bob所在的庫的讀取就會(huì)讓該機(jī)器成為悲劇的存在。

所以，可以考慮的方式是，增加一個(gè)隊(duì)列，使用，推，拉，或推拉結(jié)合的方式將smith加100這個(gè)操作加以分發(fā)。這樣就可以減輕主機(jī)的壓力。

         壞處則是：

         1方案進(jìn)一步復(fù)雜

         2如何保證log到數(shù)據(jù)分發(fā)服務(wù)器之間的數(shù)據(jù)同步是安全的和準(zhǔn)確的？

         3如何保證分發(fā)服務(wù)器的可靠和冗余？

         4如何保證寫入分發(fā)服務(wù)器的數(shù)據(jù)的安全和可靠？

再次，smith這邊也有問題，為什么要使用一張去重表呢？其實(shí)是因?yàn)?，在發(fā)送端，也就是隊(duì)列將數(shù)據(jù)發(fā)送到目標(biāo)機(jī)器后，也可能從目標(biāo)機(jī)獲取到三種不同的反饋，一類是成功（這個(gè)占了大多數(shù)）。一類是失敗。還有一類是。。。沒反饋。

當(dāng)然，最麻煩的還是這個(gè)沒反饋的情況，沒人知道這時(shí)候到底對方是做成功了呢？還是沒做成功，為了保證最大的吞吐量，又不能其他人都不做事兒了，就等對方的反饋。所以這里就有另外的權(quán)衡了。

一般的模型有兩類，一類是用分布式事務(wù)來完成。

一類是使用努力送達(dá)的模型，說叫努力送達(dá)，顧名思義，就是只有得到成功的反饋，才停止投遞，而其他時(shí)候則重復(fù)投遞消息，直到對方反饋成功為止。

兩種模型比較，顯然應(yīng)該追求速度而放棄方便性，于是我們主要來說說這個(gè)努力送達(dá)以后所帶來的影響。

影響一 : 會(huì)有重復(fù)的投遞，也就是說，這個(gè)消息可能會(huì)投多次，這對于update set version=version+1 這類的操作來說，是個(gè)比較毀滅性的打擊。

影響二：如果需要重復(fù)投遞的消息過多，會(huì)導(dǎo)致log分發(fā)的機(jī)器消耗大量資源來進(jìn)行重復(fù)投遞。這會(huì)影響server的穩(wěn)定性

影響三：如果大量堆積消息，那么會(huì)造成消息的嚴(yán)重delay。smith發(fā)現(xiàn)自己在1個(gè)月后收到了bob的錢，你說他會(huì)不會(huì)去K咱一頓: ) .

最后，額外記的這兩次log其實(shí)在某些場景下也是可以省去的。

以上，就是我在嘗試還原淘寶的消息和事務(wù)系統(tǒng)時(shí)所能大概想到的一些非常需要權(quán)衡和注意的問題點(diǎn)。

小小總結(jié)一下，整個(gè)問題的核心其實(shí)是冪等，說白了就是要能夠理解數(shù)據(jù)基于網(wǎng)絡(luò)的同步過程中，無反饋是一個(gè)經(jīng)常發(fā)生的現(xiàn)象，在這種現(xiàn)象中，重復(fù)投遞比傻傻等待要有效率的多。所以，重復(fù)作為一個(gè)side affect也就被默認(rèn)的存在于系統(tǒng)中，所有的工程師都需要認(rèn)識(shí)到這個(gè)問題的客觀存在，并采取方法去解決之。

在基于網(wǎng)絡(luò)的數(shù)據(jù)同步過程中，如果需要最大化性能，那么，一致性是第一個(gè)被放棄的。然后數(shù)據(jù)和消息不會(huì)出現(xiàn)重復(fù)，是第二個(gè)被放棄指標(biāo)。

使用這種模型，我們可以放棄原來快得等慢的的模式，讓整體的吞吐量和性能不會(huì)受制于鎖的限制，所以淘寶和支付寶才能夠支持如此大的交易量。完成大量交易訂單。

PS,廣告下，如果各位對以上的這些權(quán)衡點(diǎn)感興趣，希望能夠了解，知道他們在淘寶的實(shí)際運(yùn)作情況以及走過的經(jīng)驗(yàn)教訓(xùn)，歡迎私信給我簡歷哦~

海量存儲(chǔ)系列之七

http://qing.weibo.com/1765738567/693f0847330007ki.html 

在上一個(gè)章節(jié)，我們闡述了分布式場景下，事務(wù)的問題和一些可能的處理方式后，我們來到了下一章節(jié)

Key-value存儲(chǔ)

這一章，我們將進(jìn)入k-v場景，其實(shí)，在大部分場景下，如果某個(gè)產(chǎn)品宣稱自己的寫讀tps超過其他存儲(chǔ)n倍，一般來說都是從k-v這個(gè)角度入手進(jìn)行優(yōu)化的，主要入手的點(diǎn)是樹的數(shù)據(jù)結(jié)構(gòu)優(yōu)化和鎖的細(xì)化，一般都能在一些特定的場景獲得5-10倍的性能提升。由此可見key-value存儲(chǔ)對于整個(gè)數(shù)據(jù)存儲(chǔ)模型是多么的重要。

好吧，那么我們來進(jìn)入這個(gè)章節(jié)，用最簡單和淺顯的話語，闡述這些看起來很高深的理論吧 : )

在未來的幾篇中，我們將大概的介紹和分析如下幾種比較有特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，并探討其優(yōu)勢劣勢以及適用的場景。

讓我們先從映射入手吧，所謂映射，就是按照key找到value的過程，這個(gè)過程幾乎就是我們處理數(shù)據(jù)的最核心數(shù)據(jù)結(jié)構(gòu)了。

如何能夠根據(jù)一個(gè)key找到對應(yīng)的value呢？

一類是hash map.最簡單的實(shí)現(xiàn)就是算一個(gè)key數(shù)據(jù)的hashCode.然后按照桶的大小取mod.塞到其中的一個(gè)桶里面去。如果出現(xiàn)沖突怎么辦呢？append到這個(gè)桶內(nèi)鏈表的尾部就行了。

還有一類呢，我們可以抽象的認(rèn)為是一個(gè)有序結(jié)構(gòu)。之所以把它歸類到有序結(jié)構(gòu)原因也很簡單，因?yàn)橹挥杏行虿拍茏龆植檎?。。。舉些有序結(jié)構(gòu)的例子吧： 1. 數(shù)組 2. 各類平衡二叉樹 3. B-樹類族 4. 鏈表

這些數(shù)據(jù)結(jié)構(gòu)如果想進(jìn)行快速查找，都需要先讓他們有序。然后再去做log2N的二分查找找到對應(yīng)的key。

從原教旨上來說，這就是我們要用的key-value的主要結(jié)構(gòu)了。

那么，hash和有序結(jié)構(gòu)，他們之間有什么樣的差別呢？我們來進(jìn)行一下簡單的比較

基本上來說，核心區(qū)別就是上面的這點(diǎn)，hash單次查詢效率較高，但為了保證O(1)效率，對空間也有一定要求。而有序結(jié)構(gòu)，查詢效率基本是O(log2N)這個(gè)級別。但有序結(jié)構(gòu)可以支持范圍查找，而hash則很難支持。

所以，一般來說我們主要在使用的是有序結(jié)構(gòu)來進(jìn)行索引構(gòu)建，因?yàn)榻?jīng)常需要查詢范圍。

不過，所有數(shù)據(jù)庫幾乎都支持hash索引，如果你的查詢基本都是單值的，那么可以找一找穩(wěn)定的hash索引，他們能從一定程度上提升查詢的效率。

在這里，我們主要討論有序結(jié)構(gòu)，對于數(shù)據(jù)庫或nosql來說，有序結(jié)構(gòu)主要就是指b-tree或b-tree變種。那么我們先來介紹一下什么叫b-tree作為討論磁盤結(jié)構(gòu)的入門吧。

先上圖(copy的，這是個(gè)b-tree。版權(quán)方請找我)

首先進(jìn)行詞匯科普：b-tree只有兩類，一類叫b-tree，就是btree，還有一類是b+tree，但b-tree不是b”減”樹的意思。這個(gè)大家不要再跟當(dāng)年的我犯同樣的錯(cuò)誤喲 :__0

那么b樹的核心是幾個(gè)關(guān)鍵詞

1.      樹高:一般來說，樹的高度比較低。三到五層

2.      數(shù)組:每一個(gè)node，都是一個(gè)“數(shù)組”，數(shù)組是很關(guān)鍵的決定性因素，我們后面寫入和讀取分析的時(shí)候會(huì)講到。

沒了呵呵

然后我們進(jìn)行一下讀取和寫入的模擬。

讀取來說：如果我要查找28這個(gè)數(shù)據(jù)對應(yīng)的value是多少，路徑大概是：首先走root節(jié)點(diǎn)，取出root node后，對該數(shù)組進(jìn)行二分查找，發(fā)現(xiàn)35>28>17,所以進(jìn)入branch節(jié)點(diǎn)中的第二個(gè)節(jié)點(diǎn)，取出該節(jié)點(diǎn)后再進(jìn)行二分查找。發(fā)現(xiàn)30>28>26，所以進(jìn)入branch節(jié)點(diǎn)的p2 value，取出該節(jié)點(diǎn)，對該三個(gè)值的數(shù)組進(jìn)行二分查找，從而定位到28這個(gè)數(shù)據(jù)的對應(yīng)value。

而寫入刪除則涉及到分裂和合并這兩個(gè)btree最重要的操作，比如，要寫入37，那么會(huì)先找到36所應(yīng)該被插入的數(shù)組[36,60]這個(gè)數(shù)組，然后判斷其是否有空，如果有空，則對該數(shù)組進(jìn)行重新排序。而如果沒有空，則必須要進(jìn)行分裂。分裂的緣由是因?yàn)榻M成b-tree的每一個(gè)node,都是一個(gè)數(shù)組，數(shù)組最大的特性是，數(shù)組內(nèi)元素個(gè)數(shù)是固定的。因此必須要把原有已經(jīng)滿掉的數(shù)組里面的一半的數(shù)據(jù)拿出來，放到新的一個(gè)新建立的空數(shù)組中，然后把要寫入的數(shù)據(jù)寫入到老或新的這兩個(gè)數(shù)組里面的一個(gè)里面去。

【這里要留個(gè)問題給大家了，我想問一下，為什么b-tree要使用數(shù)組來存儲(chǔ)數(shù)據(jù)呢？為什么不選擇鏈表等結(jié)構(gòu)呢？】

對于上面的這個(gè)小的b-tree sample里面呢，因?yàn)閿?shù)組[35,60]，數(shù)組已經(jīng)滿了，所以要進(jìn)行分裂。于是數(shù)組在插入了新值以后，變成了兩個(gè)[35,36] 和[60] ，然后再改變父節(jié)點(diǎn)的指針并依次傳導(dǎo)上去即可。

當(dāng)出現(xiàn)刪除的時(shí)候，會(huì)可能需要進(jìn)行合并的工作，也就是寫入這個(gè)操作的反向過程。在一些場景中，因?yàn)椴粩嗟夭迦胄碌膇d,刪除老的id，會(huì)造成b-tree的右傾，這時(shí)候需要有后臺(tái)進(jìn)程對這種傾向進(jìn)行不斷地調(diào)整。

基本上，這就是b-tree的運(yùn)轉(zhuǎn)過程了。

B+tree

B+tree 其實(shí)就是在原有b-tree的基礎(chǔ)上。增加兩條新的規(guī)則

1.      Branch節(jié)點(diǎn)不能直接查到數(shù)據(jù)后返回，所有數(shù)據(jù)必須讀穿或?qū)懘┑絣eaf節(jié)點(diǎn)后才能返回成功

2.      子葉節(jié)點(diǎn)的最后一個(gè)元素是到下一個(gè)leaf節(jié)點(diǎn)的指針。

這樣做的原因是，更方便做范圍查詢，在b+樹種，如果要查詢20~56.只需要找到20這個(gè)起始節(jié)點(diǎn)，然后順序遍歷，不再需要不斷重復(fù)的訪問branch和root節(jié)點(diǎn)了。

發(fā)現(xiàn)每一種數(shù)據(jù)結(jié)構(gòu)都需要去進(jìn)行簡介才能夠比較方便的了解到他們的特性，所以在后續(xù)的章節(jié)還會(huì)介紹幾種有代表性的樹的結(jié)構(gòu)都會(huì)針對性的加以介紹。