作者：狼-志
鏈接：http://www.cnblogs.com/gowhy/archive/2012/12/28/2837399.html
來源：cnblogs
著作權歸作者所有芍阎。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權滔驾，非商業(yè)轉(zhuǎn)載請注明出處额衙。

一壁榕、分布式系統(tǒng)基礎重要要點：

1. 對外提供無狀態(tài)節(jié)點痴荐，內(nèi)部實現(xiàn)具體有狀態(tài)或者無狀態(tài)節(jié)點邏輯，節(jié)點即可以是提供服務窝撵，也可以是存儲數(shù)據(jù)扩借。

2. 拜占庭問題，在分布式系統(tǒng)中的使用贱鄙，目的是保證服務可用劝贸，而不是找出錯誤的節(jié)點，如果逗宁。

3. 異常常見情況映九，機器宕機、網(wǎng)絡異常瞎颗、消息丟失件甥、消息亂序捌议、數(shù)據(jù)錯誤、不可靠的TCP引有“曷可能是收到消息后宕機、也可能是處理完成以后機器宕機譬正、處理完成任務后發(fā)送確認消息是網(wǎng)絡異常宫补。也有可能是發(fā)出去的消息丟失，或者發(fā)送確認消息時丟失曾我》叟拢可能先發(fā)送出去的數(shù)據(jù)后收到

4. 分布式狀態(tài)、成功抒巢、失敗贫贝、超時。超時的情況蛉谜，不能判斷是否成功稚晚，原有同上。

5. 數(shù)據(jù)存儲在機械硬盤上悦陋，隨時有可能發(fā)生異常蜈彼，導致數(shù)據(jù)沒有能正確存儲筑辨。

6. 無法歸類的異常俺驶，比如，系統(tǒng)的處理能力時高棍辕、時低暮现，的詭異行為。

7. 即使是小概率事件楚昭，在每天百萬栖袋、千萬、及以上的運算量時也會上升為大概率事件抚太。

8. 副本提高數(shù)據(jù)的冗余塘幅，提高系統(tǒng)的可用性，但是在使用副本代來好處的同時尿贫，也導致維護副本需要成本电媳。如副本的一致性，多個副本一致性庆亡，多個副本直接可能到不一致匾乓。

9. 一致性級別：強一致性、單調(diào)一致性又谋，讀取最新數(shù)據(jù)拼缝、會話一致性娱局，通過版本讀取統(tǒng)一值。最終一致性咧七、弱一致性衰齐。

10. 分布式系統(tǒng)性能指標：吞吐量、響應延遲继阻、并發(fā)量娇斩；常用單位QPS，即每秒鐘的處理能力穴翩。高吞吐量會帶來低響應犬第、他們之間是相互制約關系。

11. 可用性指標：可以服務時間和非服務時間的比率和請求的成功和失敗次數(shù)來衡量芒帕。

12. 可擴展性指標：實現(xiàn)能水平擴展歉嗓，增加低配置的機器即可以實現(xiàn)更大的運算量，和更高的處理能力背蟆。

13. 一致性指標：實現(xiàn)副本間的一致性能力鉴分，一致性需要嚴格考量是否業(yè)務允許。

二带膀、分布式系統(tǒng)原理：

1. 哈希方式志珍，把不同的值進行哈希運算，映射到垛叨，不同的機器或者節(jié)點伦糯。考慮冗余的時候可以把多個哈希值映射到同一個地方嗽元。哈希的實現(xiàn)方式敛纲，取余。其實現(xiàn)擴展時剂癌，比較困難淤翔，數(shù)據(jù)分散在很多機器上，擴展的時候要從個機器上獲取數(shù)據(jù)佩谷。而且容易出現(xiàn)分布不均有的情況旁壮。

   常見的哈希，用IP谐檀、URL抡谐、ID、或者固定的值進行哈希稚补，總是得到相同的結果童叠。

2. 按數(shù)據(jù)范圍分布，比如ID在1_{20的在機器A上，ID在21}40的在機器B上厦坛，ID在40_{60的在機器C上實現(xiàn)五垮，ID在60}100的分布在機器D 上，數(shù)據(jù)分布比較均勻杜秸。如果某個節(jié)點處理能力有限放仗，可以直接分裂該節(jié)點。維護數(shù)據(jù)分布的元信息撬碟，可能出現(xiàn)單點瓶頸诞挨。幾千機器，每個機器又劃分為N個范圍呢蛤， 導致需要維護的數(shù)據(jù)分布范圍元數(shù)據(jù)過大惶傻，導致可能需要幾臺機器實現(xiàn)。

   一定要嚴格控制元數(shù)據(jù)量其障，進可能的減少元數(shù)據(jù)的存儲银室。

3. 按數(shù)據(jù)量分布，另一類常用的數(shù)據(jù)分布方式則是按照數(shù)據(jù)量分布數(shù)據(jù)励翼。與哈希方式和按數(shù)據(jù)范圍方式不同蜈敢，數(shù)據(jù)量分布數(shù)據(jù)與具體的數(shù)據(jù)特征無關，而是將數(shù)據(jù)視為 一個順序增長的文件汽抚，并將這個文件按照某一較為固定的大小劃分為若干數(shù)據(jù)塊（chunk）抓狭，不同的數(shù)據(jù)塊分布到不同的服務器上。與按數(shù)據(jù)范圍分布數(shù)據(jù)的方 式類似的是造烁，按數(shù)據(jù)量分布數(shù)據(jù)也需要記錄數(shù)據(jù)塊的具體分布情況否过，并將該分布信息作為元數(shù)據(jù)使用元數(shù)據(jù)服務器管理。

   由于與具體的數(shù)據(jù)內(nèi)容無關膨蛮，按數(shù)據(jù)量分布數(shù)據(jù)的方式一般沒有數(shù)據(jù)傾斜的問題叠纹，數(shù)據(jù)總是被均勻切分并分布到集群中。當集群需要重新負載均衡時敞葛，只需通過遷移 數(shù)據(jù)塊即可完成。集群擴容也沒有太大的限制与涡，只需將部分數(shù)據(jù)庫遷移到新加入的機器上即可以完成擴容惹谐。按數(shù)據(jù)量劃分數(shù)據(jù)的缺點是需要管理較為復雜的元信息， 與按范圍分布數(shù)據(jù)的方式類似驼卖，當集群規(guī)模較大時氨肌，元信息的數(shù)據(jù)量也變得很大，高效的管理元信息成為新的課題酌畜。

4. 一致性哈希怎囚，構造哈希環(huán)，有哈希域[0,10]，則構造3個部分恳守，[1,4)/[4,9)/[9,10),[0,1)/分成了3個部分考婴，這3部分是一個環(huán) 狀，增加機器時催烘，變動的是其附近的節(jié)點沥阱，分擔的是附近節(jié)點的壓力，其元數(shù)據(jù)的維護和按數(shù)據(jù)量分布一樣伊群。其未來的擴展考杉，可以實現(xiàn)多個需節(jié)點。

5. 構建映射元數(shù)據(jù)舰始，建立映射表的方式崇棠。

6. 副本與數(shù)據(jù)分布，把一個數(shù)據(jù)副本分散到多臺服務器上丸卷。比如應用A的數(shù)據(jù)易茬，存儲在A、B及老、C 抽莱，3臺機器上，如果3臺機器中骄恶，其中一臺出現(xiàn)問題食铐，請求被處理到其他2臺機器上，如果加機器恢復僧鲁，還需要從另外2臺機器上虐呻，Copy數(shù)據(jù)，又增加了這2臺 機器的負擔寞秃。如果我們有應用A和應用B斟叼，各自有3臺機器，那么我們可以把A應用分散在6臺機器上春寿，B應用也分散在6臺機器上朗涩，可以實現(xiàn)相同的數(shù)據(jù)備份，但 是應用存儲的數(shù)據(jù)被分散了绑改。某臺機器損害谢床，只是把該機器所承擔的負載平均分配到了，另外5臺機器上厘线∈锻龋恢復數(shù)據(jù)從5臺機器恢復，其速度快和給各臺服務器的壓 力都不大造壮，而且可以實現(xiàn)機器損害渡讼，更換完全不影響應用。

   其原理是多個機器互為副本，是比較理想的實現(xiàn)負載分壓的方式成箫。

7. 分布式計算思想展箱，移動數(shù)據(jù)不如移動計算，就進計算原則伟众，減少跨進程析藕、跨網(wǎng)絡、等跨度較大的實現(xiàn)凳厢，把計算所需的資源盡可能的靠近账胧。因為可能出現(xiàn)網(wǎng)絡、遠程機器的瓶頸先紫。

8. 常見分布式系統(tǒng)數(shù)據(jù)分布方式: GFS治泥、HDFS:按數(shù)據(jù)量分布；Map reduce 按GFS的數(shù)據(jù)分布做本地化遮精；BigTable居夹、HBase按數(shù)據(jù)范圍分布；Pnuts按哈希方式或者數(shù)據(jù)范圍分布本冲，可以選擇准脂；Dynamo、 Cassndra按一致性哈希檬洞；Mola狸膏、Armor、BigPipe按哈希方式分布添怔；Doris按哈希方式和按數(shù)據(jù)量分布組合湾戳。

三、數(shù)據(jù)副本協(xié)議

1. 副本一定要滿足一定的可用性和一致性要求广料、具體容錯能力砾脑，即使出現(xiàn)一些問題也能提供可靠服務。

2. 數(shù)據(jù)副本的基本協(xié)議艾杏，中心化和去中心化2種基本的副本控制協(xié)議吮龄。

3. 中心化副本控制協(xié)議的基本思路是由一個中心節(jié)點協(xié)調(diào)副本數(shù)據(jù)的更新溺森、維護副本之間的一致性贡未。中心化副本控制協(xié)議的優(yōu)點是協(xié)議相對較為簡單讼昆，所有的副本相關 的控制交由中心節(jié)點完成。并發(fā)控制將由中心節(jié)點完成其兴，從而使得一個分布式并發(fā)控制問題，簡化為一個單機并發(fā)控制問題夸政≡控制問題，簡化為一個單機并發(fā)控制問 題。所謂并發(fā)控制匀归，即多個節(jié)點同時需要修改副本數(shù)據(jù)時坑资，需要解決“寫寫”、“讀寫”等并發(fā)沖突穆端。單機系統(tǒng)上常用加鎖等方式進行并發(fā)控制袱贮。對于分布式并發(fā)控 制，加鎖也是一個常用的方法体啰，但如果沒有中心節(jié)點統(tǒng)一進行鎖管理攒巍，就需要完全分布式化的鎖系統(tǒng)，會使得協(xié)議非常復雜荒勇。中心化副本控制協(xié)議的缺點是系統(tǒng)的可 用性依賴于中心化節(jié)點柒莉，當中心節(jié)點異常或與中心節(jié)點通信中斷時沽翔，系統(tǒng)將失去某些服務（通常至少失去更新服務）兢孝，所以中心化副本控制協(xié)議的缺點正是存在一定 的停服務時間。即存在單點問題仅偎，即使中心化節(jié)點是一個集群跨蟹，也只不過是一個大的單點。

4. 副本數(shù)據(jù)同步常見問題:

   1)網(wǎng)絡異常橘沥，導致副本沒有得到數(shù)據(jù)窗轩；
   2）數(shù)據(jù)臟讀，主節(jié)點數(shù)據(jù)已經(jīng)更新威恼，但是由于某種原因品姓，沒有得到最新數(shù)據(jù)
   3）增加新節(jié)點沒有得到主節(jié)點數(shù)據(jù)，而讀數(shù)據(jù)時從新節(jié)點讀數(shù)據(jù)導致箫措，沒有得到數(shù)據(jù)腹备。

5. 去中心化副本控制協(xié)議沒有中心節(jié)點，協(xié)議中所有的節(jié)點都是完全對等的斤蔓，節(jié)點之間通過平等協(xié)商達到一致植酥。從而去中心化協(xié)議沒有因為中心化節(jié)點異常而帶來的停 服務等問題。然而弦牡，沒有什么事情是完美的友驮，去中心化協(xié)議的最大的缺點是協(xié)議過程通常比較復雜。尤其當去中心化協(xié)議需要實現(xiàn)強一致性時驾锰，協(xié)議流程變得復雜且 不容易理解卸留。由于流程的復雜，去中心化協(xié)議的效率和性能較低椭豫。

6. Paxos是唯一在工程中得到應用的強一致性去中心化副本控制協(xié)議耻瑟。ZooKeeper旨指、Chubby，就是該協(xié)議的應用喳整。

   Zookeeper用Paxos協(xié)議選擇Leader谆构，用Lease協(xié)議控制數(shù)據(jù)是否有效。用Quorum協(xié)議把Leader的數(shù)據(jù)同步到follow框都。
   Zeekeeper搬素，實現(xiàn)Quorum寫入時，如果沒有完全寫入成功魏保，則所有的follow機器熬尺，反向向Leader寫數(shù)據(jù)，寫入數(shù)據(jù)后 follow又向Leader同步數(shù)據(jù)囱淋，保持一致猪杭，如果是失敗的數(shù)據(jù)先寫入，你們follow同步到原來的數(shù)據(jù)妥衣，相對于回滾皂吮；如是是最新的數(shù)據(jù)先寫入 Leader則就是完成了最新數(shù)據(jù)的更新。

7. Megastore税手，使用的是改進型行Paxos協(xié)議蜂筹。

8. Dynamo / Cassandra使用基于一致性哈希的去中心化協(xié)議。Dynamo使用Quorum機制來管理副本芦倒。

9. Lease機制是最重要的分布式協(xié)議艺挪，廣泛應用于各種實際的分布式系統(tǒng)中。1）Lease通常定義為：頒發(fā)者在一定期限內(nèi)給予持有者一定權利的協(xié)議兵扬。 2）Lease 表達了頒發(fā)者在一定期限內(nèi)的承諾麻裳，只要未過期頒發(fā)者必須嚴格遵守 lease 約定的承諾；3）Lease 的持有者在期限內(nèi)使用頒發(fā)者的承諾器钟，但 lease 一旦過期必須放棄使用或者重新和頒發(fā)者續(xù)約津坑。4）的影響。中心服務器發(fā)出的lease的含義為：在lease的有效期內(nèi)傲霸，中心服務器保證不會修改對應數(shù)據(jù) 的值疆瑰。5）可以通過版本號、過多上時間昙啄、或者到某個固定時間點認為Lease證書失效穆役。

   其原理和我們的Cache一樣，比如瀏覽器緩存道理一致梳凛。其要求時間時鐘同步耿币，因為數(shù)據(jù)完全依賴于期限。

10. 心跳（heartbeat）檢測不可靠,假如檢測及其Q韧拒，被檢測機器A掰读，可能由于Q發(fā)起檢測秘狞，但是A的回應被阻塞叭莫，導致Q 認為A宕機蹈集，阻塞很快恢復，導致根據(jù)心跳檢測來做判斷不可靠雇初；也可能是他們之間的網(wǎng)絡斷開拢肆；也可能是Q機器本身異常導致認為A機器宕機；如果根據(jù)Q的檢測 結果靖诗，來判斷很可能出現(xiàn)多個主機的情況郭怪。

11. Write-all-read-one（簡稱WARO）是一種最簡單的副本控制規(guī)則，顧名思義即在更新時寫所有的副本刊橘，只有在所有的副本上更新成功鄙才，才認 為更新成功，從而保證所有的副本一致促绵，這樣在讀取數(shù)據(jù)時可以讀任一副本上的數(shù)據(jù)攒庵。寫多份，讀從其中一份讀取败晴。

12. quorum協(xié)議浓冒，其實就是讀取成功的副本數(shù)大于失敗的副本數(shù)，你們讀取的副本里面一定包含了最新的副本尖坤。

13. Mola和Armor系統(tǒng)中所有的副本管理都是基于Quorum稳懒，即數(shù)據(jù)在多數(shù)副本上更新成功則認為成功。

14. Big Pipe*中的副本管理也是采用了WARO機制慢味。

四场梆、日志技術

1. 日志技術是宕機恢復的主要技術之一。日志技術最初使用在數(shù)據(jù)庫系統(tǒng)中纯路。嚴格來說日志技術不是一種分布式系統(tǒng)的技術或油，但在分布式系統(tǒng)的實踐中，卻廣泛使用了日志技術做宕機恢復感昼，甚至如BigTable等系統(tǒng)將日志保存到一個分布式系統(tǒng)中進一步增強了系統(tǒng)容錯能力装哆。
2. 兩種比較實用的日志技術Redo Log與No Redo/No undo Log。
3. 數(shù)據(jù)庫的日志主要分為Undo Log定嗓、Redo Log蜕琴、Redo/Undo Log與No Redo/No Undo Log。這四類日志的區(qū)別在更新日志文件和數(shù)據(jù)文件的時間點要求不同宵溅，從而造成性能和效率也不相同凌简。
4. 本節(jié)介紹另一種特殊的日志技術“No Undo/No Redo log”，這種技術也稱之為“0/1目錄”(0/1 directory)恃逻。還有一個主記錄雏搂，記錄當前工作目錄藕施，比如老數(shù)據(jù)在0目錄下，新數(shù)據(jù)在1目錄下凸郑，我們訪問數(shù)據(jù)時裳食，通過主紀錄，記錄當前是工作在那個 目錄下芙沥，如果是工作在目錄0下诲祸，取目錄0數(shù)據(jù)，反之取1目錄數(shù)據(jù)而昨。
5. MySQL的主從庫設計也是基于日志救氯。從庫只需通過回放主庫的日志，就可以實現(xiàn)與主庫的同步歌憨。由于從庫同步的速度與主庫更新的速度沒有強約束着憨，這種方式只能實現(xiàn)最終一致性。
6. 在單機上务嫡，事務靠日志技術或MVCC等技術實現(xiàn)甲抖。
7. 兩階段提交的思路比較簡單，在第一階段植袍，協(xié)調(diào)者詢問所有的參與者是否可以提交事務（請參與者投票）惧眠，所有參與者向協(xié)調(diào)者投票。在第二階段于个，協(xié)調(diào)者根據(jù)所有 參與者的投票結果做出是否事務可以全局提交的決定氛魁，并通知所有的參與者執(zhí)行該決定。在一個兩階段提交流程中厅篓，參與者不能改變自己的投票結果秀存。兩階段提交協(xié) 議的可以全局提交的前提是所有的參與者都同意提交事務，只要有一個參與者投票選擇放棄(abort)事務羽氮，則事務必須被放棄或链。可以這么認為档押，兩階段提交協(xié) 議對于這種超時的相關異常也沒有很好的容錯機制澳盐，整個流程只能阻塞在這里，且對于參與者而言流程狀態(tài)處于未知令宿，參與者即不能提交本地節(jié)點上的事務叼耙，也不能 放棄本地節(jié)點事務。
8. 第一粒没、兩階段提交協(xié)議的容錯能力較差筛婉。
9. 第二、兩階段提交協(xié)議的性能較差癞松。一次成功的兩階段提交協(xié)議流程中爽撒，協(xié)調(diào)者與每個參與者之間至少需要兩輪交互4個消息“prepare”入蛆、“vote- commit”、“global-commit”硕勿、“確認global-commit”哨毁。過多的交互次數(shù)會降低性能。另一方面首尼，協(xié)調(diào)者需要等待所有的參與 者的投票結果挑庶，一旦存在較慢的參與者，會影響全局流程執(zhí)行速度软能。
10. 顧名思義，MVCC即多個不同版本的數(shù)據(jù)實現(xiàn)并發(fā)控制的技術举畸，其基本思想是為每次事務生成一個新版本的數(shù)據(jù)查排，在讀數(shù)據(jù)時選擇不同版本的數(shù)據(jù)即可以實現(xiàn)對事 務結果的完整性讀取。在使用MVCC時抄沮，每個事務都是基于一個已生效的基礎版本進行更新跋核，事務可以并行進行。其思想是根據(jù)版本號叛买，在多個節(jié)點取同一個版本 號的數(shù)據(jù)砂代。
11. MVCC的流程過程非常類似于SVN等版本控制系統(tǒng)的流程，或者說SVN等版本控制系統(tǒng)就是使用的MVCC思想率挣。

五刻伊、CAP理論

1. CAP理論的定義很簡單，CAP三個字母分別代表了分布式系統(tǒng)中三個相互矛盾的屬性：

   Consistency (一致性)：CAP理論中的副本一致性特指強一致性（1.3.4 ）
   Availiablity(可用性)：指系統(tǒng)在出現(xiàn)異常時已經(jīng)可以提供服務椒功；
   Toleranceto the partition of network (分區(qū)容忍)：指系統(tǒng)可以對網(wǎng)絡分區(qū)捶箱，這種異常情況進行容錯處理。

2. CAP理論指出：無法設計一種分布式協(xié)議动漾，使得同時完全具備CAP三個屬性丁屎，即1)該種協(xié)議下的副本始終是強一致性，2)服務始終是可用的旱眯，3)協(xié)議可以容忍任何網(wǎng)絡分區(qū)異常晨川；分布式系統(tǒng)協(xié)議只能在CAP這三者間所有折中。