海量存储系列上--转载，值得一读
海量存儲之序言
http://qing.blog.sina.com.cn/1765738567/693f0847330005sk.html
今天玩微薄的時候有人問我有沒有數據存儲的相關資料，我想了想。。雖然在這個領域內也算有點積累，以前講課的ppt有200多頁，但畢竟ppt的信息量有限。所以在這里將這個系列的部分內容在這里進行重新編排
主要將涉及到： 1. 數據庫原理 ? http://qing.weibo.com/1765738567/693f0847330005sm.html 關系代數 ? http://qing.weibo.com/1765738567/693f0847330005v7.html 事務 ?http://qing.weibo.com/1765738567/693f084733000672.html k-v存儲的使用?http://qing.weibo.com/1765738567/693f0847330007ki.html 數據存儲模型 數據寫入模式性能和安全性分析 2.?倒排索引 3.?分布式kv系統 數據的切分 數據的管理和擴容 數據安全性 讀寫可用性 4. 硬件存儲在淘寶的測試數據和分析 5. 淘寶在線數據存儲檢索經驗介紹?海量存儲系列之二
http://qing.weibo.com/1765738567/693f0847330005v7.html? 在上一篇里面，我們對數據庫的抽象的組成原理進行了簡單的描述。在這一篇里面，我們一起來看看，如何能夠使用kv這樣的工具。來完成關系代數運算。 那么，讓我們先來熱熱身: 這是一組數據，以pk作為主鍵，user_id和Name是外key. 那么，如果我要運行查詢:Select * from tab where id = ? 應該如何進行呢？ 這里需要一些額外的知識，在數據結構中，有那么一種結構，可以用于處理按照某個key找到value的過程，抽象來看，一種方法是二分查找法，一種方法是hash. 如果各位是java用戶，那么二分查找的實現可以認為是個TreeMap的實現，而Hash的方法則可以認為是hashMap的實現。如果是個c/cpp的用戶，那么就二分查找就對應map實現。而hash實現則對應stl里面的hash_map。 那么，這里的這個問題，我們就很容易可以解決了 以id作為map的key,以其他數據作為value，把所有數據都放入到map里面，然后再使用id=1作為key,從map中找到對應的value返回即可。（這一個部分，我們在后面的章節里面還會介紹，現在大家只需要有個大概的印象即可） 怎么樣？是不是很簡單？那么，我們來討論更進一步的問題： 如果我想找到符合Select * from tab where user_id = 0的所有結果，應該如何去作？ 仔細想想。那么第一種做法一定是這樣。 把整個集合內的所有數據，都拿出來，然后找到user_id的數字，如果user_id=0，那么就認為是符合要求的記錄，直接返回。 如果不是user_id=0，那么不匹配，丟棄這條記錄即可。 這樣一定可以找到所有符合要求的記錄。 然而，這樣作，帶來的問題是，我有多少條記錄，就需要進行多少次這樣的匹配，那么，假設有100000000000000000條記錄，就需要匹配這樣多次，才能找到符合要求的記錄。這是個悲劇。。 那么，怎么解決這個悲劇呢？ 于是有些聰明人就又想起了map結構，hash或tree，不都可以按照k找到value么。那我們這里也可以利用這個map結構嘛。。 也就是說，以user_id作為key,id作為value，構建一個Map.不就又能進行快速查詢了么。 于是，就有了數據庫最重要的一個結構“索引” 這種以外鍵作為key,主鍵作為value的東西，有個專有的名字，叫做二級索引。 有了二級索引，我們的所有查詢，都可以以接近O(LogN)(有序數據)，或O(1)的效率找到我們需要的數據。是不是很爽？ 但這不是銀彈，你付出了空間成本，本質來說就是空間換時間的過程。同時，也會降低寫入的效率。 怎么樣？理解了沒？如果自認為對這些都了解了，那么我們再來看一個問題： 如果我要找的是：Select ...where user_id = ? And name = '襪子' 應該怎么做呢？ 估計很多人都立刻又會想起那個Map，對的，但在這里，我想給出以下的幾種查詢的模式： 1. 遍歷所有數據，取出一條以后，查看user_id = 0 and name='襪子'是否符合要求，如果符合，則返回數據。 這是個合理的策略，空間最為節省，但帶來的損耗是要遍歷所有的數據。 2. 如果有個user_id -> pk的索引 ，那么我們可以先按照user_id，找到一組符合要求的pk list.然后再根據pk list，再回到 取出符合要求的數據后，判斷name=‘襪子’這個條件，如果符合，就返回，不符合，就丟棄。 這是個折衷策略，在空間和性能中，盡可能的找到個合理的區間的策略。 題外話，這個“根據pk list，再回到pk=>整個數據的kv表中，找出符合要求的數據后，判斷name=‘襪子’這個條件，如果符合，就返回，不符合，就丟棄”的策略，在數據庫有個專有名詞，叫回表。 3. 組合索引 這是個新名詞兒，但其實也是個很簡單的概念。 直接上圖： :-)，其實就是個很簡單的策略，先比較user_id進行排序，如果user_id相同，那么比較name排序。 這樣，假定我們有100000條記錄，屬于100個用戶，那么平均來看，每個用戶就只有1000條記錄了。 原來要回表1000條記錄才能找到符合要求的數據，而如果使用組合索引，這1000條，也可以使用O(log2N)或者O(1)的策略進行檢索啦。 在很多場景中，都能夠提升效率和速度。但付出的是更多的存儲空間。 好啦，這篇就介紹到這里，留個題目給大家： 假設有這么一組數據，性別有4種，user_id是一對多的關系，如果我想查詢 select * from tab where user_id in (?,?,?,?) and 性別='不明' 如何進行索引構建能夠獲得比較好的效果呢？海量存儲系列之三
http://qing.weibo.com/1765738567/693f084733000672.html?首先是回答上次的問題。
?
?
假設有這么一組數據，性別有4種，user_id是一對多的關系，如果我想查詢
select * from tabwhere user_id in (?,?,?,?) and 性別='不明'
如何進行索引構建能夠獲得比較好的效果呢？
我個人認為，應該建立的是以user_id作為前導列，性別作為輔助列的索引，在大量單值查詢時會有優勢。
理由如下
1. 假定總數據量為N,user_id的區分度為N/10000 而性別的區分度為N/4
那么如果以user_id作為前導列，性別作為后列，那么查詢的復雜度為O(logN+log(N/10000))。也就是說，第一次二分查找之后，下一次是在第一次的二分查找的基礎上再去查找。而如果以性別作為前導，user_id作為后列，那么復雜度為
O(logN+log(N/4));
效率略差。
然后進入本次正題。上次介紹了關系模型，那么這次我們來介紹一下事務。
在一切之前，我想先給自己解嘲一下。。事務我自己也沒有辦法完全融匯貫通，因為每一個小的選擇，都會導致效果的完全不同，所以有錯請在后面一起探討。
那么我們在這里，主要以單機事務作為入手點，然后闡述一下多機事務相關的知識點。我在這里只是想做一個引導，讓大家能夠對整個的知識體系有一個基本的認識，對于細節問題，會給出一些資料，而不會直接去進行講解，因為篇幅所限.
一般來說，我們一提起事務，就會想到數據庫，確實，事務是數據庫的最重要的一個屬性。但這似乎不是事務的本源，那么，讓我們從更深層次去對事務進行一次思考吧：
事務，本質來說就是一組由一個人（或機器）發起的連續的邏輯操作，共同的完成一件事情，在完成整個事情之前，其所有的改動，都不應該對其他人可見和影響。而在事務結束之后，其一切的改動，都必須“全部”“立刻”對其他的人（或機器）可見。
然后，人們為了描述這一運作,使用了四個詞匯，這也是很多面試的同學們折戟沉沙之處。J 不過這個以前我也不會，后來發現，理解了以后，確實有點用，所以這里也費一些筆墨吧。
原子性(Atomicity)：也就是說，一組操作，要不就都成功，要不就都失敗。不存在中間狀態。
一致性(Consistency)：一致性，也就是說，這個事務在提交或回滾的時候，對其他人（或機器）來說，數據的狀態是同一的，不會出現中間的狀態。最理想的狀態下，就是說，數據提交后，所有的更改立刻同時生效，可惜，在計算機領域，這個做不到。。因為cpu運算，磁盤寫入，內存寫入，都是要時間的，內部一定是個順序化的過程，所以不可能做到絕對的立刻同時生效。
所以一致性一般來說指代的是邏輯上的同時生效，比如，我要改A,B兩行數據，那么，最簡單的一致性保證就是，對A,B加鎖，改A,B，然后對A，B解鎖。
這樣下一個人讀到的一定是A,B的最新值啦。
（但這塊有很多種解釋，一般來說這是個最不明確的詞匯）。
?
隔離性(Isolation)：隔離，這是面試最容易掛的一個問題，其實我認為不怪我們，而是因為本身這個隔離性，是依托鎖來進行設計的。
我們所知道的鎖，主要有以下幾種，1.讀寫鎖，2. 排他鎖
那么這四種級別其實就和這兩種鎖的實現有關，之所以要定義四個級別，其實原因也是因為，鎖的范圍越大，并行效率越低。而范圍越小，那么并行的效率就越高。
讀未提交： 其實就是什么鎖也沒有，所以數據的中間狀態，是可能被其他人讀到的。
讀已提交：就是讀寫鎖實現，讀鎖在查詢之后會被釋放掉，所以這樣其他人可能會更改那些被釋放了讀鎖的數據，這樣當前事務再去讀取的時候，就可能讀取到被別人修改過的數據了，所以一個人在事務中讀取到的某個數據，可能下次讀取就變成別的數據啦。這就是不可重復讀的意思。。
可重復讀：也是個讀寫鎖實現，讀鎖會阻塞其他人（或機器）的寫，于是，只要是事務中讀取到得數據，都被加了鎖，其他人沒辦法改他們，于是就實現了可重復讀咯。
最后是序列化，就是所有都順序，一個大鎖全部鎖住J
?
持久性(Durability)：持久性就是，事務執行后，就丟不了了，就算是整個中國被淹了，機器都沒了，數據也不應該丟掉（不過基本做不到這個，也就是一個機器掛了不會丟數據而已。。）所有機房沒了那數據也就沒了。。
對于這塊，給大家一些參考資料：
http://zh.wikipedia.org/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"這個大怪獸再次吃掉。。我先發這些。
在下一個章節，我們繼續在事務這個領域徜徉，給大家介紹一下，在單機上面，事務是如何進行的。
?
海量存儲系列之四
http://qing.weibo.com/1765738567/693f08473300067j.html?單機事務
單機事務:
其實在上面介紹ACID的時候
我們已經提到了一種最簡單的實現方式，就是鎖的實現方式。
從原理來看，事務是個變態而復雜的事情。其實如果是序列化的話呢，那么實現起來一定是非常簡單的。
但問題就在于，這樣性能實在比較低，于是，就有了非常多的方案，為了能哪怕減少一個地方的鎖，或者降低一個地方的鎖的級別，就付出大量的時間和代碼加以實現。
那么，讓我們以崇敬的心情，去拜讀一下他們的勞動成果吧~
?--------------------------------------------------------------------------------
?
在上一篇中，我們談了事務管理的四個核心要素，其中有兩個要素是和性能緊密相關的，其實也就是需要涉及到鎖的，一個是隔離性，一個是一致性。
一致性問題和隔離性問題，我們都可以歸結為一個問題，他們都用于定義，什么時候數據可被共享，什么時候數據必須被獨占。而這些決策，就最終決定了整個數據庫系統的并行度，也就直接的決定了多線程并發時的性能指標。
?
如果要改一大批數據，又必須保證這些數據要么都出現，要么都不出現，這時候就有個難題了：因為這些數據不可能在同一個時間被選出，更不可能在同一個時間被更改。
于是就必須想個辦法來假裝達到這個狀態，于是我們就需要一種方法，使得針對不同數據的更改，不同人（或機器）不打架。而如果出現對相同數據的更改，則要將更新進行排隊。
這個排隊可供選擇的方法，就我知道的有：1，排他鎖。2. 讀寫鎖。3. Copy on write（MVCC） .4. 隊列。5. 內存事務。這些方式。
?
從性能來說，排他鎖最慢，而讀寫因為讀可以并發，所以效率稍高，但寫和讀不能同時進行。3. Copy on write(MVCC) 則讀取和寫入之間可以互相不影響，所以效率更高。隊列這種方式，內存時效果很好，省去中斷上下文切換的時間。內存事務，目前還在研究階段，具備很大潛力的東西。
?
排他鎖，隊列和內存事務，在目前的數據庫中用的相對較少，我們就不在這里說了。
這里主要說兩種實現，一種是讀寫鎖，一種是MVCC.
?
先說讀寫鎖，也是隔離性中“讀已提交，可重復讀”兩種實現中最重要的底層實現方式。
簡單來說，就是如果一個人在事務中，那么他所有寫過的數據，所有讀過的數據，都給他來個鎖，讓其他小樣兒都只能等在外面，直到數據庫能確定所有更改已經全部完成了，沒有剩下什么半拉子狀態的時候，就解開所有的鎖，讓其他人可以讀取和寫入。Hoho,就是這個了。
?
那么MVCC呢，其實是對讀寫鎖的一個改進，有一批大牛們，說你們這讀寫鎖，寫的時候不能讀，讀的時候不能寫，并行度太低了，我要做個更牛B的，寫不阻塞讀，讀不阻塞寫的東西來超越你們。
于是他們想起了copy-on-write.鼓搗了個MVCC數據庫出來。。。
題外話，現在的甲骨文，之所以能在數據庫領域保持優勢地位，有個很重要的原因也是因為他們是很早就在商業數據庫系統中實現了MVCC的數據寫入引擎。
所以他們的Thomas Kyte?技術副總裁也就有了在他們的最牛逼的oracle專家編程里面有了吹噓的資本 XD .
?
這里我們要著重的介紹一下MVCC，因為這東西看起來非常的精妙而美麗。。?，F在大量的分布式類存儲中，也都在借鑒這套模式中的很多部分來增加自己的并行度，以提升性能。比如megaStore.比如percolator。
我們在讀寫鎖的實現中，提到了寫讀的相互阻塞問題，MVCC則使用copy-on-write來解決這個問題。
如果一個人在事務中，會先申請一個事務ID,這個ID是自增的，每個事務都有他自己的唯一的ID，那么他寫過的數據，都會被轉變為一次帶有當前事務ID的新數據，在讀取的時候，則只會讀取小于等于自己事務ID的數據。這樣實現的東東，語義上來說，與可重復讀就一樣了。而如果讀小于等于全局ID的數據，那么這樣的實現，就是讀已提交了。
?
一般來說，MVCC只實現了四個級別中的第二級和第三級，其他的就沒有啦，不過這兩個是我們最常見的級別。所以也就大家同樂，同樂了~
?
有了這個東西，我們的一致性也就很容易保證了，因為一個事物和他對應的版本號對應，又有更改后的數據和更改前的數據，如果要提交，那么就只需要很簡單的讓更改后的數據生效可見即可，這樣我們可以將大量的更新中要做的事情，都在事務過程中進行，這樣，比原有的基于讀寫鎖的必須在commit時候一起做掉來說，commit這個操作就輕量化了很多，于是，就可以支持更多的人（或機器）持有事務狀態了。
?
很美妙吧？
我一致認為這是oracle當年的核心競爭力，不過現在基本上是個數據庫就用了這一套，我們就不在多嘴啦~
?
解決了一致性和隔離性，剩下的是原子性和持久性，原子性么，一般來說就是要么都成功，也就是新版本數據都讓他生效，要么就都失敗，也就是讓和自己事務ID對應的所有修改都無效即可。也很好就解決掉了。持久性。這個就是后面我們要在寫入模型里面介紹的東西了，基本上來說就是寫磁盤策略的事情。
?
到這里，我們單機ACID的實現大概思路，就給大家介紹過了。下一個章節，我們還要用很多的文字，來向大家介紹在分布式場景中我們面臨的事務的難題，以及“我所知道的”百花齊放的解決方法。
海量存儲系列之五
http://qing.weibo.com/1765738567/693f0847330006ao.html?rnd=0.6134993201121688
在上一章節，我們一起瀏覽了如何進行單機事務操作。下面我們來看一下分布式場景中我們碰到的問題吧。
?
需要說明的一點是，這里涉及到的權衡點非常的多。就我短短的工作經驗里面，也只是能夠簡單的涉獵一部分，因為在事務這個領域，目前大家都在嘗試提出各種各樣的不同的方法，而在taobao，我們目前也沒有完美的解決這個問題，更多的是在權衡，在金錢和開發成本之間，做出選擇。
?
那么，我們就先從問題開始，來看一下原來的事務出了什么問題。
在事務中，有ACID四種屬性。（見上篇文章）
?
在分布式場景中，我們看引入了什么因素，導致了什么樣的新問題：
1.??????延遲因素:光是我們所知最快的信息載體了，各位可能都會從潛意識里面認為光傳輸信息不就是一眨眼的事情而已。那我們做個簡單的計算吧（感謝@淘寶叔度，第一次在分享中讓我對這個問題有了個數值化的印象。）：
北京到杭州，往返距離2600km ，光在真空中的傳輸速度是30wkm/s。在玻璃中的速度是真空的2/3。算下來，最小的請求和響應，之間的延遲就有13ms。并且，因為光在管子里走的不是直線，又有信號干擾等問題，一般來說要乘以2~3倍的因子值。
所以一次最小的請求和響應，時間就差不多有30ms左右了。
再想想TCP的時間窗口的移動策略，相信大家都能意識到，實際上延遲是不可忽略的，尤其在傳輸較多數據的時候，延遲是個重要的因素，不能不加以考慮。
并且，延遲 不是 帶寬，帶寬可以隨便增加，千兆網卡換成萬兆，但延遲卻很難降低。而我們最需要的，是帶寬，更是延遲的降低。因為他直接決定了我們的可用性。
2.??????災備因素：單機的情況下，人們一般不會去追求說一個機器物理上被水沖走了的時候，我的數據要保證不丟（因為沒辦法的嘛。。）。但在分布式場景下，這種追求就成為了可能，而互聯網行業，對這類需求更是非?？粗?#xff0c;恨不能所有的機器都必須是冗余的，可隨意替換的。這樣才能保證7*24小時的正常服務。這無疑增加了復雜度的因素。
3.??????Scale out的問題： 單機總是有瓶頸的，于是，人們的追求就一定是：不管任何一種角色的機器，都應該可以通過簡單的增加新機器的方式來提升整個集群中任何一個角色的性能，容量等指標。這也是互聯網行業的不懈追求。
4.??????性能：更快的響應速度，更低的延遲，就是更好的用戶體驗。（所以google用了個“可憐”到家的簡單input框來提升用戶體驗，笑）。
?
說道這里，大概大家都應該對在分布式場景下的廣大人民群眾的目標有了一個粗略的認識了。
那么我們來看一下原有ACID的問題吧。
?
在上次的章節中，我們也提到了ACID中，A和D相對的，比較容易達到。但C和I都涉及到鎖實現，也就和性能緊密的相關了。
然后，人們就開始了糾結，發掘這個C和I，似乎不是那么容易了。
上次，我們談到，目前主流的實現一次更新大量數據的時候，不同人（或機器）修改數據相互之間不會打架的方法有以下幾種：
1.??????排他鎖
2.??????讀寫鎖
3.??????Copy-on-write
4.??????隊列
5.??????內存事務
?
?
排他鎖和讀寫鎖，本身都是鎖的實現，單機的鎖實現，相對而言是非常簡單的事情，但如果涉及到分布式鎖，那么消耗就很高了，原因是，鎖要在兩邊都達到一致，需要多次機器之間的交互過程，這個交互的過程，再考慮到延遲的因素，基本上一次加鎖請求就要100~200+毫秒的時間了，那么去鎖又要這樣的時間。而要知道，我們在單機做內存鎖操作，最慢也不過10毫秒。。
于是，有一批人就說了，既然這么難，我們不做了！~來個理論證明他很難就行了~。于是就有了CAP和BASE.
所謂CAP，我個人的理解是描述了一種： 在數據存了多份的前提下，一致性和響應時間，讀寫可用性不可兼得的“現象”而已。
在我這里來看CAP的證明過程就是個扯淡的玩意兒，他只是描述了一種現象而已。原因還是網絡延遲，因為延遲，所以如果要做到數據同時出現或消失，那么按照鎖的方式原來可能只需要10ms以內完成的操作，現在要200~400ms才能完成，那自然不能接受了。所謂CAP就是這個現象的英文簡稱，笑。
?
BASE呢，這個理論似乎更老，其實也是個現象，就是基本可用，軟狀態，最終一致的簡稱，也沒個證明，其實就是告訴咱：要權衡一下，原來的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的階段，會對所有該操作所影響的數據加鎖，這樣就可以阻止其他人（或機器）對他的訪問。題外話，問個問題: ）如果這時有其他節點，用相反的方向，進行更新，也就是先更新smith,然后更新bob.會有可能發生什么事情呢？
兩段提交協議是被我們在大部分場景下放棄的一個模型，原因主要是因為
1.??????Tm本身需要記錄事務進行的過程，log要保證安全和可信，性能非常低。
2.??????鎖的利用率和并行性較低。
3.??????網絡開銷較大
4.??????可見性要求實際上就等于讓快的操作等慢的。
?
所以從性能角度來說，這類需求不多也不常見。
既然這樣的模型不行，有沒有其他模型可以使用呢？
?
有的。
?
在事務的過程中，細心的讀者不難發現，實際上事務中并不需要這么強的一致可見性。
Bob是需要強一致的，因為他的操作仰賴于他有多少錢，如果他的錢不夠100，那么是不能讓他的賬戶變為負數的。但smith卻不需要，smith不需要判斷他的賬戶有多少錢，只需要把錢加到他的賬戶里，不少給他，到賬時間盡可能短就可以。
Smith不需要chech賬戶的錢數，這個前提非常重要，這也是我們能使用最終一致性的關鍵因素。
?
下面，我們來看一下另外的選擇吧。
Bob的賬號在機器A上，smith的賬號在機器b上。
首先，我們在機器A上做以下操作:
1.??????本地事務開始
2.??????讀取bob的賬戶
3.??????判斷是否有充足余額
4.??????更新bob的賬號，將bob的錢減少100
5.??????將需要給smith加100塊這個操作，以事務的形式插入到同機(A)的一張log表中，并自動生成一個唯一的transactionID。
6.??????事務關閉
?
然后，異步的發送一個通知，給一個消費者。
消費者接到通知后，從bob的機器上讀取到需要給smith+100這個操作，以及該操作所對應的transactionID。
然后，按照如下方法進行運作
1.??????查看在去重表內是否有對應的transactionID.如果沒有，則
2.??????開啟本地事務
3.??????將smith的賬戶+100
4.??????將transactionID 插入去重表
5.??????事務結束
?
這樣，我們也可以完成一個交易的核心流程了。在交易類過程中的大量事務操作，都是以這樣的方式完成的。
?
下面，我們針對上面的這個流程的一些抉擇的點進行一些探討。
?
首先，是bob這個機器，這里涉及第一個抉擇點。
如果bob是個消費大戶，短時間內進行了大量購買，那么可能會造成的問題是，bob所在的那個機器會成為熱點，如果在某個突發的情況下，某個賬戶突然成為熱點，那么這些有狀態的數據很難快速的反應并加以處理，會造成事務數在某個單節點大量堆積。造成掛掉。
?
可能的解決方法是：
1.??????利用兩段提交協議來讓原來的” 將需要給smith加100塊這個操作，以事務的形式插入到同機(A)的一張log表中，并自動生成一個唯一的transactionID”這步操作放在另外的一臺機器上進行。
這樣做的的好處是，無論bob怎么是熱點，都可以通過水平的加log機器的方式來防止這種熱點的產生。
壞處則有：
???????? 1方案復雜度高
???????? 2額外的網絡開銷
???????? 3消息基于網絡發送后，會可能得到三個可能的反饋：1. 成功 2. 失敗 3. 無反饋。最麻煩的就是這個無反饋，他可能成功，也可能失敗。所以是不確定的狀態，需要進行事務的兩邊進行第二次確認，來確保這個事務的參與方是否都做了該做的事情，如果有一方做了類似commit的操作，那么另外的一方應該commit.如果兩方都沒做commit操作，那么應該回滾。
2.??????讓bob的庫余量更高，并按照訪問壓力進行數據的切分，按照熱度進行數據劃分，放棄原有的簡單取mod的策略。來兼容這種不均勻特性。
?
其次，如果有80個系統都關注著smith加了100這個操作的log，要做對應的處理（比如一些人要針對這個加錢操作做個打款短信推送，有些要做個數據分析等等），那么這里就有另外一個問題，這些系統對bob所在的庫的讀取就會讓該機器成為悲劇的存在。
所以，可以考慮的方式是，增加一個隊列，使用，推，拉，或推拉結合的方式將smith加100這個操作加以分發。這樣就可以減輕主機的壓力。
???????? 壞處則是：
???????? 1方案進一步復雜
???????? 2如何保證log到數據分發服務器之間的數據同步是安全的和準確的？
???????? 3如何保證分發服務器的可靠和冗余？
???????? 4如何保證寫入分發服務器的數據的安全和可靠？
?
再次，smith這邊也有問題，為什么要使用一張去重表呢？其實是因為，在發送端，也就是隊列將數據發送到目標機器后，也可能從目標機獲取到三種不同的反饋，一類是成功（這個占了大多數）。一類是失敗。還有一類是。。。沒反饋。
?
當然，最麻煩的還是這個沒反饋的情況，沒人知道這時候到底對方是做成功了呢？還是沒做成功，為了保證最大的吞吐量，又不能其他人都不做事兒了，就等對方的反饋。所以這里就有另外的權衡了。
?
一般的模型有兩類，一類是用分布式事務來完成。
一類是使用努力送達的模型，說叫努力送達，顧名思義，就是只有得到成功的反饋，才停止投遞，而其他時候則重復投遞消息，直到對方反饋成功為止。
?
兩種模型比較，顯然應該追求速度而放棄方便性，于是我們主要來說說這個努力送達以后所帶來的影響。
影響一 : 會有重復的投遞，也就是說，這個消息可能會投多次，這對于update set version=version+1 這類的操作來說，是個比較毀滅性的打擊。
影響二：如果需要重復投遞的消息過多，會導致log分發的機器消耗大量資源來進行重復投遞。這會影響server的穩定性
影響三：如果大量堆積消息，那么會造成消息的嚴重delay。smith發現自己在1個月后收到了bob的錢，你說他會不會去K咱一頓: ) .
?
最后，額外記的這兩次log其實在某些場景下也是可以省去的。
?
以上，就是我在嘗試還原淘寶的消息和事務系統時所能大概想到的一些非常需要權衡和注意的問題點。
?
小小總結一下，整個問題的核心其實是冪等，說白了就是要能夠理解數據基于網絡的同步過程中，無反饋是一個經常發生的現象，在這種現象中，重復投遞比傻傻等待要有效率的多。所以，重復作為一個side affect也就被默認的存在于系統中，所有的工程師都需要認識到這個問題的客觀存在，并采取方法去解決之。
?
在基于網絡的數據同步過程中，如果需要最大化性能，那么，一致性是第一個被放棄的。然后數據和消息不會出現重復，是第二個被放棄指標。
?
?
使用這種模型，我們可以放棄原來快得等慢的的模式，讓整體的吞吐量和性能不會受制于鎖的限制，所以淘寶和支付寶才能夠支持如此大的交易量。完成大量交易訂單。
?
PS,廣告下，如果各位對以上的這些權衡點感興趣，希望能夠了解，知道他們在淘寶的實際運作情況以及走過的經驗教訓，歡迎私信給我簡歷哦~
?
海量存儲系列之七
http://qing.weibo.com/1765738567/693f0847330007ki.html?
在上一個章節，我們闡述了分布式場景下，事務的問題和一些可能的處理方式后，我們來到了下一章節
?
Key-value存儲
?
這一章，我們將進入k-v場景，其實，在大部分場景下，如果某個產品宣稱自己的寫讀tps超過其他存儲n倍，一般來說都是從k-v這個角度入手進行優化的，主要入手的點是樹的數據結構優化和鎖的細化，一般都能在一些特定的場景獲得5-10倍的性能提升。由此可見key-value存儲對于整個數據存儲模型是多么的重要。
?
好吧，那么我們來進入這個章節，用最簡單和淺顯的話語，闡述這些看起來很高深的理論吧 : )
?
在未來的幾篇中，我們將大概的介紹和分析如下幾種比較有特點的數據結構，并探討其優勢劣勢以及適用的場景。
?
?
?
讓我們先從映射入手吧，所謂映射，就是按照key找到value的過程，這個過程幾乎就是我們處理數據的最核心數據結構了。
?
如何能夠根據一個key找到對應的value呢？
一類是hash map.最簡單的實現就是算一個key數據的hashCode.然后按照桶的大小取mod.塞到其中的一個桶里面去。如果出現沖突怎么辦呢？append到這個桶內鏈表的尾部就行了。
?
還有一類呢，我們可以抽象的認為是一個有序結構。之所以把它歸類到有序結構原因也很簡單，因為只有有序才能做二分查找。。。舉些有序結構的例子吧： 1. 數組 2. 各類平衡二叉樹 3. B-樹類族 4. 鏈表
?
這些數據結構如果想進行快速查找，都需要先讓他們有序。然后再去做log2N的二分查找找到對應的key。
?
從原教旨上來說，這就是我們要用的key-value的主要結構了。
那么，hash和有序結構，他們之間有什么樣的差別呢？我們來進行一下簡單的比較
?
?
?
基本上來說，核心區別就是上面的這點，hash單次查詢效率較高，但為了保證O(1)效率，對空間也有一定要求。而有序結構，查詢效率基本是O(log2N)這個級別。但有序結構可以支持范圍查找，而hash則很難支持。
?
所以，一般來說我們主要在使用的是有序結構來進行索引構建，因為經常需要查詢范圍。
不過，所有數據庫幾乎都支持hash索引，如果你的查詢基本都是單值的，那么可以找一找穩定的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節點，取出root node后，對該數組進行二分查找，發現35>28>17,所以進入branch節點中的第二個節點，取出該節點后再進行二分查找。發現30>28>26，所以進入branch節點的p2 value，取出該節點，對該三個值的數組進行二分查找，從而定位到28這個數據的對應value。
?
而寫入刪除則涉及到分裂和合并這兩個btree最重要的操作，比如，要寫入37，那么會先找到36所應該被插入的數組[36,60]這個數組，然后判斷其是否有空，如果有空，則對該數組進行重新排序。而如果沒有空，則必須要進行分裂。分裂的緣由是因為組成b-tree的每一個node,都是一個數組，數組最大的特性是，數組內元素個數是固定的。因此必須要把原有已經滿掉的數組里面的一半的數據拿出來，放到新的一個新建立的空數組中，然后把要寫入的數據寫入到老或新的這兩個數組里面的一個里面去。
【這里要留個問題給大家了，我想問一下，為什么b-tree要使用數組來存儲數據呢？為什么不選擇鏈表等結構呢？】
對于上面的這個小的b-tree sample里面呢，因為數組[35,60]，數組已經滿了，所以要進行分裂。于是數組在插入了新值以后，變成了兩個[35,36] 和[60] ，然后再改變父節點的指針并依次傳導上去即可。
?
當出現刪除的時候，會可能需要進行合并的工作，也就是寫入這個操作的反向過程。在一些場景中，因為不斷地插入新的id,刪除老的id，會造成b-tree的右傾，這時候需要有后臺進程對這種傾向進行不斷地調整。
?
基本上，這就是b-tree的運轉過程了。
?
B+tree
?
?
?
B+tree 其實就是在原有b-tree的基礎上。增加兩條新的規則
1.??????Branch節點不能直接查到數據后返回，所有數據必須讀穿或寫穿到leaf節點后才能返回成功
2.??????子葉節點的最后一個元素是到下一個leaf節點的指針。
這樣做的原因是，更方便做范圍查詢，在b+樹種，如果要查詢20~56.只需要找到20這個起始節點，然后順序遍歷，不再需要不斷重復的訪問branch和root節點了。
?
?
發現每一種數據結構都需要去進行簡介才能夠比較方便的了解到他們的特性，所以在后續的章節還會介紹幾種有代表性的樹的結構都會針對性的加以介紹。
?
轉載于:https://www.cnblogs.com/davidwang456/p/3856219.html
總結
以上是生活随笔為你收集整理的海量存储系列上--转载，值得一读的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java中的mmap实现--转
- 下一篇： 海量存储系列下--转载，值得一读