海量存儲系列之三

首先是回答上次的問題。

假設有這么一組數據，性別有4種，user_id是一對多的關系，如果我想查詢

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

如何進行索引構建能夠獲得比較好的效果呢？

我個人認為，應該建立的是以user_id作為前導列，性別作為輔助列的索引，在大量單值查詢時會有優(yōu)勢。

理由如下

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

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

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

效率略差。

然后進入本次正題。上次介紹了關系模型，那么這次我們來介紹一下事務。

在一切之前，我想先給自己解嘲一下。。事務我自己也沒有辦法完全融匯貫通，因為每一個小的選擇，都會導致效果的完全不同，所以有錯請在后面一起探討。

那么我們在這里，主要以單機事務作為入手點，然后闡述一下多機事務相關的知識點。我在這里只是想做一個引導，讓大家能夠對整個的知識體系有一個基本的認識，對于細節(jié)問題，會給出一些資料，而不會直接去進行講解，因為篇幅所限.

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

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

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

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

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

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

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

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

隔離性(Isolation)：隔離，這是面試最容易掛的一個問題，其實我認為不怪我們，而是因為本身這個隔離性，是依托鎖來進行設計的。

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

那么這四種級別其實就和這兩種鎖的實現有關，之所以要定義四個級別，其實原因也是因為，鎖的范圍越大，并行效率越低。而范圍越小，那么并行的效率就越高。

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

讀已提交：就是讀寫鎖實現，讀鎖在查詢之后會被釋放掉，所以這樣其他人可能會更改那些被釋放了讀鎖的數據，這樣當前事務再去讀取的時候，就可能讀取到被別人修改過的數據了，所以一個人在事務中讀取到的某個數據，可能下次讀取就變成別的數據啦。這就是不可重復讀的意思。。

可重復讀：也是個讀寫鎖實現，讀鎖會阻塞其他人（或機器）的寫，于是，只要是事務中讀取到得數據，都被加了鎖，其他人沒辦法改他們，于是就實現了可重復讀咯。

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

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

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

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

http://www.cnblogs.com/wangiqngpei557/archive/2011/11/19/2255132.html

這些講的不錯，淺顯易懂是我的最愛.

好啦，為了保證我寫的東西不會被"qing"這個大怪獸再次吃掉。。我先發(fā)這些。

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

海量存儲系列之四

http://qing.weibo.com/1765738567/693f08473300067j.html 單機事務

單機事務:

其實在上面介紹ACID的時候

我們已經提到了一種最簡單的實現方式，就是鎖的實現方式。

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

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

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

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

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

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

如果要改一大批數據，又必須保證這些數據要么都出現，要么都不出現，這時候就有個難題了：因為這些數據不可能在同一個時間被選出，更不可能在同一個時間被更改。

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

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

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

排他鎖，隊列和內存事務，在目前的數據庫中用的相對較少，我們就不在這里說了。

這里主要說兩種實現，一種是讀寫鎖，一種是MVCC.

先說讀寫鎖，也是隔離性中“讀已提交，可重復讀”兩種實現中最重要的底層實現方式。

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

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

于是他們想起了copy-on-write.鼓搗了個MVCC數據庫出來。。。

題外話，現在的甲骨文，之所以能在數據庫領域保持優(yōu)勢地位，有個很重要的原因也是因為他們是很早就在商業(yè)數據庫系統中實現了MVCC的數據寫入引擎。

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

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

我們在讀寫鎖的實現中，提到了寫讀的相互阻塞問題，MVCC則使用copy-on-write來解決這個問題。

如果一個人在事務中，會先申請一個事務ID,這個ID是自增的，每個事務都有他自己的唯一的ID，那么他寫過的數據，都會被轉變?yōu)橐淮螏в挟斍笆聞誌D的新數據，在讀取的時候，則只會讀取小于等于自己事務ID的數據。這樣實現的東東，語義上來說，與可重復讀就一樣了。而如果讀小于等于全局ID的數據，那么這樣的實現，就是讀已提交了。

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

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

很美妙吧？

我一致認為這是oracle當年的核心競爭力，不過現在基本上是個數據庫就用了這一套，我們就不在多嘴啦~

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

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

海量存儲系列之五

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

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

需要說明的一點是，這里涉及到的權衡點非常的多。就我短短的工作經驗里面，也只是能夠簡單的涉獵一部分，因為在事務這個領域，目前大家都在嘗試提出各種各樣的不同的方法，而在taobao，我們目前也沒有完美的解決這個問題，更多的是在權衡，在金錢和開發(fā)成本之間，做出選擇。

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

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

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

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

北京到杭州，往返距離2600km ，光在真空中的傳輸速度是30wkm/s。在玻璃中的速度是真空的2/3。算下來，最小的請求和響應，之間的延遲就有13ms。并且，因為光在管子里走的不是直線，又有信號干擾等問題，一般來說要乘以2~3倍的因子值。

所以一次最小的請求和響應，時間就差不多有30ms左右了。

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

并且，延遲 不是 帶寬，帶寬可以隨便增加，千兆網卡換成萬兆，但延遲卻很難降低。而我們最需要的，是帶寬，更是延遲的降低。因為他直接決定了我們的可用性。

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

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

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

說道這里，大概大家都應該對在分布式場景下的廣大人民群眾的目標有了一個粗略的認識了。

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

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

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

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

1.      排他鎖

2.      讀寫鎖

3.      Copy-on-write

4.      隊列

5.      內存事務

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

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

所謂CAP，我個人的理解是描述了一種： 在數據存了多份的前提下，一致性和響應時間，讀寫可用性不可兼得的“現象”而已。

在我這里來看CAP的證明過程就是個扯淡的玩意兒，他只是描述了一種現象而已。原因還是網絡延遲，因為延遲，所以如果要做到數據同時出現或消失，那么按照鎖的方式原來可能只需要10ms以內完成的操作，現在要200~400ms才能完成，那自然不能接受了。所謂CAP就是這個現象的英文簡稱，笑。

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

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

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

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

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

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

海量存儲系列之六

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

抱歉大家，間隔有點久，因為這一章要比較細致的總結，所以有些時間耽誤。上次我們講到，單機事務個我們面臨的問題，下面我們來說一些我所知的解決的方法。

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

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

我們仍然以上一次講到的bob和smith為例子來說明好了。

開始的時候。Bob要給smith100塊，那么實際上事務中要做的事情是

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

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

但如果bob在一臺機器，smith在另外一臺機器，我們應該怎么做呢？

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

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

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

事務結束。

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

兩段提交協議是被我們在大部分場景下放棄的一個模型，原因主要是因為

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

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

3.      網絡開銷較大

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

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

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

有的。

在事務的過程中，細心的讀者不難發(fā)現，實際上事務中并不需要這么強的一致可見性。

Bob是需要強一致的，因為他的操作仰賴于他有多少錢，如果他的錢不夠100，那么是不能讓他的賬戶變?yōu)樨摂档摹５玸mith卻不需要，smith不需要判斷他的賬戶有多少錢，只需要把錢加到他的賬戶里，不少給他，到賬時間盡可能短就可以。

Smith不需要chech賬戶的錢數，這個前提非常重要，這也是我們能使用最終一致性的關鍵因素。

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

Bob的賬號在機器A上，smith的賬號在機器b上。

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

1.      本地事務開始

2.      讀取bob的賬戶

3.      判斷是否有充足余額

4.      更新bob的賬號，將bob的錢減少100

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

6.      事務關閉

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

消費者接到通知后，從bob的機器上讀取到需要給smith+100這個操作，以及該操作所對應的transactionID。

然后，按照如下方法進行運作

1.      查看在去重表內是否有對應的transactionID.如果沒有，則

2.      開啟本地事務

3.      將smith的賬戶+100

4.      將transactionID 插入去重表

5.      事務結束

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

下面，我們針對上面的這個流程的一些抉擇的點進行一些探討。

首先，是bob這個機器，這里涉及第一個抉擇點。

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

可能的解決方法是：

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

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

壞處則有：

         1方案復雜度高

         2額外的網絡開銷

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

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

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

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

         壞處則是：

         1方案進一步復雜

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

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

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

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

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

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

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

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

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

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

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

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

以上，就是我在嘗試還原淘寶的消息和事務系統時所能大概想到的一些非常需要權衡和注意的問題點。

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

在基于網絡的數據同步過程中，如果需要最大化性能，那么，一致性是第一個被放棄的。然后數據和消息不會出現重復，是第二個被放棄指標。

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

PS,廣告下，如果各位對以上的這些權衡點感興趣，希望能夠了解，知道他們在淘寶的實際運作情況以及走過的經驗教訓，歡迎私信給我簡歷哦~

海量存儲系列之七

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

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

Key-value存儲

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

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

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

讓我們先從映射入手吧，所謂映射，就是按照key找到value的過程，這個過程幾乎就是我們處理數據的最核心數據結構了。

如何能夠根據一個key找到對應的value呢？

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

還有一類呢，我們可以抽象的認為是一個有序結構。之所以把它歸類到有序結構原因也很簡單，因為只有有序才能做二分查找。。。舉些有序結構的例子吧： 1. 數組 2. 各類平衡二叉樹 3. B-樹類族 4. 鏈表

這些數據結構如果想進行快速查找，都需要先讓他們有序。然后再去做log2N的二分查找找到對應的key。

從原教旨上來說，這就是我們要用的key-value的主要結構了。

那么，hash和有序結構，他們之間有什么樣的差別呢？我們來進行一下簡單的比較

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

所以，一般來說我們主要在使用的是有序結構來進行索引構建，因為經常需要查詢范圍。

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

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

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

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

那么b樹的核心是幾個關鍵詞

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

2.      數組:每一個node，都是一個“數組”，數組是很關鍵的決定性因素，我們后面寫入和讀取分析的時候會講到。

沒了呵呵

然后我們進行一下讀取和寫入的模擬。

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

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

【這里要留個問題給大家了，我想問一下，為什么b-tree要使用數組來存儲數據呢？為什么不選擇鏈表等結構呢？】

對于上面的這個小的b-tree sample里面呢，因為數組[35,60]，數組已經滿了，所以要進行分裂。于是數組在插入了新值以后，變成了兩個[35,36] 和[60] ，然后再改變父節(jié)點的指針并依次傳導上去即可。

當出現刪除的時候，會可能需要進行合并的工作，也就是寫入這個操作的反向過程。在一些場景中，因為不斷地插入新的id,刪除老的id，會造成b-tree的右傾，這時候需要有后臺進程對這種傾向進行不斷地調整。

基本上，這就是b-tree的運轉過程了。

B+tree

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

1.      Branch節(jié)點不能直接查到數據后返回，所有數據必須讀穿或寫穿到leaf節(jié)點后才能返回成功

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

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

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