我們繼續(xù)互聯(lián)網(wǎng)技術(shù)架構(gòu)－分布式存儲(chǔ)。
總目錄：
分布式存儲(chǔ)概述
分布式存儲(chǔ)特性 － 哈希分布/一致性哈希分布
分布式存儲(chǔ)協(xié)議 － 兩階段與Paxos
1. 概述
分布式存儲(chǔ)作為互聯(lián)網(wǎng)之核心基石，沒有分布式海量存儲(chǔ)就好比無源之水。分布式系統(tǒng)不是什么新鮮事物，教科書里已經(jīng)研究了好多年，但是不溫不火，直到近年互聯(lián)網(wǎng)大數(shù)據(jù)應(yīng)用的興起才使得它大規(guī)模的應(yīng)用到工程實(shí)踐中，其主要特點(diǎn)概括為：規(guī)模大＋成本低?，F(xiàn)在的大型互聯(lián)網(wǎng)公司少則幾百幾千個(gè)PC服務(wù)器，多的達(dá)到數(shù)百萬級(jí)別低成本PC服務(wù)器集群;
總體來說，分布式存儲(chǔ)需要具備以下一些要素：
可擴(kuò)展:靈活水平擴(kuò)展到成百上千上萬，并且整體性能線性增長(zhǎng)。
低成本:構(gòu)建與低成本PC，兼?zhèn)?span style="margin:0px; padding:0px; max-width:100%; word-wrap:break-word!important">自動(dòng)容錯(cuò)，自動(dòng)負(fù)載均衡等機(jī)制。
高性能:秒，毫秒，亞秒級(jí)別。
易用:構(gòu)建生態(tài)環(huán)境，與其它系統(tǒng)集成，如監(jiān)控，運(yùn)維，數(shù)據(jù)導(dǎo)入。
分布式存儲(chǔ)的挑戰(zhàn)來源自于其設(shè)計(jì)的兩個(gè)技術(shù)領(lǐng)域：分布式＋ 存儲(chǔ)：
數(shù)據(jù)分布式:數(shù)據(jù)如何分布，數(shù)據(jù)如何跨服務(wù)器讀寫？
一致性：數(shù)據(jù)如何replication，多個(gè)副本之間又如何同步
容錯(cuò)：檢測(cè)，并遷移故障服務(wù)器上的數(shù)據(jù)
負(fù)載均衡：如何“空中加油”，運(yùn)行中添加，卸載服務(wù)器
事務(wù)并發(fā)：分布式事務(wù)，并發(fā)控制
分布式存儲(chǔ)數(shù)據(jù)分類：
按照其所處理的數(shù)據(jù)類型來分的話，大體分為
非結(jié)構(gòu)化數(shù)據(jù)：如文本，圖像，圖片，視頻，音頻等
結(jié)構(gòu)化數(shù)據(jù)：類似關(guān)系型數(shù)據(jù)庫
半結(jié)構(gòu)化數(shù)據(jù)：介于上面二者之間，如HTML文檔，換言之其模式結(jié)構(gòu)于內(nèi)容混合。
分布式存儲(chǔ)系統(tǒng)分類：
有了數(shù)據(jù)，我們看一下容器如何劃分：
分布式文件系統(tǒng):存儲(chǔ)非結(jié)構(gòu)化文件對(duì)象；如FB Haystack; GFS, HDFS
分布式鍵值系統(tǒng)：存儲(chǔ)半結(jié)構(gòu)化數(shù)據(jù)，如Amazon Dynamo, Memcache
分布式表格：存儲(chǔ)半結(jié)構(gòu)化數(shù)據(jù)，如BigTable,HBase, DynamoDB
分布式數(shù)據(jù)庫：存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)，如MySQL Sharding, Amazon RDS,以及阿里OceanBase.
2. 分布式存儲(chǔ)特性
分布式存儲(chǔ)包括了數(shù)據(jù)的分布，復(fù)制，一致性，容錯(cuò)等。
一致性：分布式存儲(chǔ)系統(tǒng)會(huì)將數(shù)據(jù)冗余備份，稱之為replication/copy. 副本是目前分布式存儲(chǔ)系統(tǒng)容錯(cuò)的唯一方法。如有3個(gè)客戶端A,B,C
強(qiáng)一致：如A先寫入，系統(tǒng)保證后續(xù)A,B,C的讀去都返回最新值
弱一致：如A先寫入，系統(tǒng)不保證后續(xù)A,B,C的讀去都返回最新值
最終一致：“最終”只有個(gè)時(shí)間的延遲，如replication等，如A先寫入，同時(shí)假設(shè)后續(xù)無其他更新相同的值，“最終”A,B,C都會(huì)讀到A寫入的最新值
數(shù)據(jù)分布：分布式存儲(chǔ)當(dāng)然會(huì)設(shè)計(jì)數(shù)據(jù)如何分布了，同時(shí)要考慮自動(dòng)負(fù)載均衡
哈希分布：無需多說，類似HashMap的index了，基本思路都是選取某業(yè)務(wù)相關(guān)主鍵key，然后 hash(key)% N(服務(wù)器數(shù)量)， 當(dāng)然如果這里hash函數(shù)的散列性比較好的話，數(shù)據(jù)可以比較均勻的分布到集群。
上面可以么？如果仔細(xì)看過HashMap的極客們應(yīng)該知道，當(dāng)HashMap的數(shù)量超過一定負(fù)載后，需要resize, rehash。這有什么問題么？?jī)?nèi)存處理當(dāng)然沒什么大問題，這可是分布式存儲(chǔ)啊，你這么一resize，rehash可不得了，涉及很多數(shù)據(jù)的遷移，耗時(shí)耗力。況且，分布式會(huì)動(dòng)態(tài)增加，卸載節(jié)點(diǎn)，都不用超過一定數(shù)量限制。如何解決？
一致性哈希(Distributed Hash Table, DHT)：算法如下，給系統(tǒng)每個(gè)節(jié)點(diǎn)分配一個(gè)隨機(jī)token，使得這些token構(gòu)成一個(gè)哈希環(huán)，存放時(shí)，根據(jù)hash(key)的值，存放到順時(shí)針第一個(gè)大于/等于該值的token所在節(jié)點(diǎn)。這樣，每次節(jié)點(diǎn)的變更只會(huì)影響哈希環(huán)中相鄰的節(jié)點(diǎn)，對(duì)其他沒有影響。
如上圖所示，假設(shè)哈?？臻g為0-2^32-1大小：
1>首先求出每個(gè)服務(wù)器node的hash值（一般情況下對(duì)機(jī)器的hash計(jì)算是采用機(jī)器的IP或者機(jī)器唯一的別名作為輸入值），將其分配到圓環(huán)上
2>采用同樣算法計(jì)算待存儲(chǔ)對(duì)象的key的hash值，將其分配到這個(gè)圓環(huán)
3> 開始順時(shí)針查找，并分配到第一個(gè)找到的服務(wù)器節(jié)點(diǎn)
通過上圖可以看出對(duì)象與機(jī)器處于同一哈?？臻g中，在這樣的部署環(huán)境中，
hash環(huán)是不會(huì)變更的，因此，通過算出對(duì)象的hash值就能快速的定位到對(duì)應(yīng)的機(jī)器中，這樣就能找到對(duì)象真正的存儲(chǔ)位置了。
上文提到，普通hash求余最大問題就是當(dāng)count也就是機(jī)器的數(shù)量變化，如添加，刪除后，需要rehash，并進(jìn)行位置調(diào)整。我們來看一下一致性哈希如何處理：
如圖，灰色的node2被刪除，則只需按照瞬時(shí)針遷移，object3則會(huì)被遷移到
node3中，所以僅僅會(huì)影響object3位置，其他對(duì)象無需改動(dòng)。
2.節(jié)點(diǎn)添加
如果我們要在集群中添加一個(gè)新的節(jié)點(diǎn)node4，通過哈希算法得到key4，并映射到環(huán)中。
按照順時(shí)針遷移規(guī)則，我們把object2遷移到node4中，其他object保持原位。
另外，稍微提及一下，當(dāng)一致性哈希算法在服務(wù)節(jié)點(diǎn)太少時(shí)，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問題。為了解決這種數(shù)據(jù)傾斜問題，一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。
參考MIT論文：http://dl.acm.org/citation.cfm?id=258660
順序分布：通常做法是將一個(gè)大表順序劃分成連續(xù)范圍，即子表。如經(jīng)常用來舉例的用戶表，按照主鍵分為1-10000，10001-20000，...80000-90000等。再添加類似B＋樹索引。其中葉子相當(dāng)于子表。
分布式復(fù)制：replication，常見做法類似數(shù)據(jù)庫同步操作日志(commitlog）
容錯(cuò)：容錯(cuò)是分布式存儲(chǔ)系統(tǒng)設(shè)計(jì)的重要目標(biāo)，當(dāng)然是自動(dòng)容錯(cuò)。
故障檢測(cè)：心跳，通用做法。官方叫法是，Lease(租約)協(xié)議，即帶有超時(shí)時(shí)間的一種授權(quán)。
故障恢復(fù)：遷移，通用做法。但是當(dāng)Master節(jié)點(diǎn)/總控節(jié)點(diǎn)出現(xiàn)故障時(shí)，為了HA,我們就要重新選主了，正所謂國(guó)家不可一日無主，當(dāng)然現(xiàn)代社會(huì)，要通過Paxos協(xié)議選舉，如我們介紹過的ZK.
3.分布式協(xié)議
重要的分布式協(xié)議：Paxos選舉協(xié)議與兩階段提交協(xié)議。其中Paxos協(xié)議在我們介紹ZK的時(shí)候，就有小伙伴提出詳細(xì)介紹。
兩階段提交協(xié)議：Two-phaseCommit, 2PC. 主要用來確保多個(gè)節(jié)點(diǎn)或者分布式操作的原子性。如果有使用過JTA或者做過大型銀行轉(zhuǎn)賬系統(tǒng)的應(yīng)該使用過。
如跨數(shù)據(jù)庫操作：
恰如其名，2PC通常分為兩個(gè)階段：
階段1: 請(qǐng)求階段Prepare Phase, 協(xié)調(diào)者通知參與者準(zhǔn)備提交或者取消事務(wù)；
階段2: 提交階段Commit Phase, 協(xié)調(diào)者將階段1的結(jié)果進(jìn)行投票表決，當(dāng)且僅當(dāng)所有參與者同意提交事務(wù)時(shí)，協(xié)調(diào)者才通知所有參與者提交，否則通知所有參與者取消。
如下圖所示：
兩階段提交協(xié)議是阻塞協(xié)議，執(zhí)行過程中需要加鎖，且無法容錯(cuò)，所以... 大多數(shù)分布式存儲(chǔ)系統(tǒng)都避而遠(yuǎn)之。同理可證，JTA。
Paxos協(xié)議：主要用于解決多個(gè)節(jié)點(diǎn)之間一致性問題。如主節(jié)點(diǎn)出現(xiàn)故障時(shí)，其它節(jié)點(diǎn)如何協(xié)調(diào)選主。同時(shí)，當(dāng)做到了多個(gè)節(jié)點(diǎn)之間的操作日志一致性，就能夠在這些節(jié)點(diǎn)上來構(gòu)建高可用服務(wù)包括分布式鎖，分布式命名，配置服務(wù)等。
多數(shù)情況下，系統(tǒng)只有一個(gè)備點(diǎn)提議者Proposer, 所以它的提議總是會(huì)很快被大多數(shù)節(jié)點(diǎn)接受。
執(zhí)行步驟：
批準(zhǔn)(accept): Proposer發(fā)送accept消息給所有其它節(jié)點(diǎn)（acceptor）接受某個(gè)提議，acceptor可以選擇接受或者拒絕
確認(rèn)(acknowledge): 如果超過一半的acceptor接受，則提議生效，proposer發(fā)送acknowledge消息通知所有acceptor提議生效
如果系統(tǒng)有多個(gè)proposer，則各自分別發(fā)起提議，如修改操作或者提議自己選主，如果proposer第一次發(fā)起的accept請(qǐng)求沒有被acceptor中多數(shù)派批準(zhǔn)，則需要進(jìn)行一輪完整的Paxos協(xié)議，如下：
1. 準(zhǔn)備prepare： Proposer首先選擇一個(gè)提議序號(hào)n給其它acceptor節(jié)點(diǎn)發(fā)送
prepare消息，Acceptor收到消息后，如果提議序號(hào)已經(jīng)大于它已經(jīng)回復(fù)的所有prepare消息，則acceptor將自己上次接受的提議回復(fù)給proposer，并承諾不再回復(fù)小于n的提議。
2. 批準(zhǔn)accept：Proposer收到了acceptor中多數(shù)派隊(duì)prepare的回復(fù)后，就進(jìn)入批準(zhǔn)階段。如果在之前的prepare階段acceptor回復(fù)了上次接受的提議，則提議值發(fā)給acceptor批準(zhǔn)。Acceptor在不違背它之前在prepare階段的承諾前提下接受這個(gè)請(qǐng)求。如果超過一半的acceptor接受，提議值生效，Proposer發(fā)送acknowledge消息通知所有acceptor。
稍微有點(diǎn)繞，Paxos需要確保2點(diǎn)，正確性，即只有一個(gè)提議值會(huì)生效；可終止性，即最終會(huì)有一個(gè)提議值生效。數(shù)學(xué)語言，有且只有一個(gè)。
受限與篇幅以及時(shí)間，我們會(huì)分2篇來介紹分布式存儲(chǔ)系統(tǒng)。下一篇將提及著名Google分布式數(shù)據(jù)庫
“The largest single database on earth”。
公眾號(hào)：技術(shù)極客TechBooster
聯(lián)系客服
