參考：https://mp.weixin.qq.com/s/rv7qMyGQuVwiFfPUeKeQ2w
1. 概念
1.1. 節(jié)點
1.2 異常情況
? ? 分布式環(huán)境下會遇到的問題
? ? 機器宕機
? ? 網(wǎng)路異常
? ? 分布式三態(tài)：RPC調(diào)用執(zhí)行的結(jié)果可能有三個情況：成功、失敗谷朝、未知（超時）
? ? 存儲數(shù)據(jù)丟失：對于有狀態(tài)的節(jié)點來說，內(nèi)存數(shù)據(jù)丟失他炊，則狀態(tài)也會丟失，通常只能從其他節(jié)點讀取漾橙、恢復(fù)啦桌。
? ? 異常處理原則
1.3 副本
? ? 在分布式視同中為數(shù)據(jù)或服務(wù)提供的冗余。
? ? 副本一致性：幾種一致性
? ? ? ? ? ? 1. 強一致性
? ? ? ? ? ? 2. 單調(diào)一致性瑟慈。任何時刻航唆，任何用戶一旦讀到某個數(shù)據(jù)在某次更新后的值，這個用戶不會再讀到比這個值更舊的值渐白。
? ? ? ? ? ? 3. 會話一致性。任何用戶在某次會話內(nèi)的單調(diào)一致性纯衍。
? ? ? ? ? ? 4. 最終一致性栋齿。一旦更新成功，各個副本上的數(shù)據(jù)最終將達到完全一致的狀態(tài)襟诸，但是達到的時間不能保證瓦堵。
? ? ? ? ? ? 5. 弱一致性歌亲。
1.4 衡量分布式系統(tǒng)的指標(biāo)
? ? 性能：主要是吞吐量菇用、延遲、并發(fā)
? ? 可用性：可以用正常提供服務(wù)的時間和總時間的比例或者某個功能成功的次數(shù)和失敗次數(shù)的比例來衡量
? ? 可擴展性：通過擴展集群里的機器數(shù)量來提供系統(tǒng)性能惋鸥、存儲容量、計算能力的特性鹅龄。
? ? 一致性：一致性越高揩慕，使用起來約簡單。
2. 分布式系統(tǒng)原理
2.1 數(shù)據(jù)分布的方式
? ? 哈希算法
? ? 按數(shù)據(jù)范圍分布：IDC與LDC的實踐
? ? 按數(shù)據(jù)量分布
? ? 一致性哈希：1997年扮休，MIT的論文迎卤。為了在移除或者添加新服務(wù)器時玷坠，能盡量減少影響蜗搔。
????對存儲節(jié)點的哈希值進行計算八堡，將其存儲空間抽象為一個閉環(huán)樟凄，將存儲節(jié)點分配到環(huán)上兄渺。環(huán)上所有節(jié)點都有一個值缝龄。
? ? 對數(shù)據(jù)進行哈希計算挂谍，按順時針方向?qū)⑵溆成涞诫x其最近的節(jié)點上去叔壤。
? ? 如下圖口叙，節(jié)點計算的值如下炼绘，1，2妄田，3驮捍，…… 0 .數(shù)據(jù)hash值為1.3脚曾。則將該數(shù)據(jù)分配給節(jié)點2處理东且。
? ? 如果節(jié)點出現(xiàn)異常斟珊，影響范圍則是從該故障節(jié)點開始逆時針方向到上個節(jié)點內(nèi)的數(shù)據(jù)對象不可用苇倡。
? ? 如果需要增加新節(jié)點囤踩，則影響的是該新增的節(jié)點逆時針到上個節(jié)點內(nèi)的數(shù)據(jù)對象旨椒。
? ? 缺點：1. 當(dāng)節(jié)點規(guī)模很大時堵漱，遍歷節(jié)點的時間復(fù)雜度是O(n)综慎；2. 新增和移除節(jié)點還是需要進行數(shù)據(jù)遷移。
2.2. 基本副本協(xié)議
? ? 分類：
? ? 中心化副本控制協(xié)議：主要有primary-secondary協(xié)議示惊。中心節(jié)點負(fù)責(zé)維護數(shù)據(jù)的更新、并發(fā)控制米罚、協(xié)調(diào)副本的一致性。主要解決的問題：數(shù)據(jù)更新流程丈探、數(shù)據(jù)讀取方式、primary選擇碗降、數(shù)據(jù)同步。
? ? 去中心化副本控制協(xié)議：
2.3 常見的分布式共識協(xié)議或機制
? ? 1. lease機制讼渊。Lease 是由頒發(fā)者授予的在某一有效期內(nèi)的承諾。頒發(fā)者一旦發(fā)出lease爪幻，則無論接受方是否收到菱皆，也無論后續(xù)接收方處于何種狀態(tài)挨稿，只要lease 不過期仇轻，頒發(fā)者一定嚴(yán)守承諾叶组；另一方面，接收方在lease 的有效期內(nèi)可以使用頒發(fā)者的承諾历造，但一旦lease 過期船庇，接收方一定不能繼續(xù)使用頒發(fā)者的承諾。
? ? 2. Quorum機制鸭轮。一共有N個副本，每次更新操作會在W個副本上成功橄霉。則最多需要讀取R個副本，其中R+W>N 則一定能讀取到某次更新后的數(shù)據(jù)姓蜂。(因為R和W一定有交集)按厘。
????????由于更新 操作需要在W 個副本上都成功钱慢，更新操作才能成功逮京，所以一旦N-W+1 （因為W+N-W+1 = N+1> N）個副本異常，更新操作始終無法在W 個副本上成功束莫，更新服務(wù)不可用。另一方面览绿，一旦N-R+1 個副本異常策严，則無法保證一定可以讀到與W 個副本有交集的副本集合饿敲，則讀服務(wù)的一致性下降妻导。所以N诀蓉、W栗竖、R 控制了系統(tǒng)的可用性，也是系統(tǒng)對用戶的服務(wù)承諾狐肢。
? ? 3. 日志技術(shù)（應(yīng)用在mysql中）
? ? ? ? redo log
? ? ? ? check point
? ? 4. 兩階段提交協(xié)議（2PC）（中心化副本控制協(xié)議）、3PC沥曹、TCC（XTS是基于TCC的）
? ? 5. MVCC（多版本并發(fā)控制，也是應(yīng)用在DB中的 ）
? ? 6. Paxos協(xié)議妓美。強一致性、高可用的去中心化的分布式協(xié)議壶栋。
有一組完全對等的參與節(jié)點（稱為accpetor）辰如，這組節(jié)點各自就某一事件做出決議贵试，如果某個決議獲得了超過半數(shù)節(jié)點的同意則生效琉兜。Paxos 協(xié)議中只要有超過一半的節(jié)點正常，就可以工作豌蟋。
角色：Proposer廊散、Acceptor、Listener
利用了Quorom機制：另W=R=N/2+1
? ? ? 協(xié)議通過引入輪次梧疲，使得高輪次的提議搶占低輪次的提議來避免死鎖。協(xié)議設(shè)計關(guān)鍵點是如何滿足“在一次Paxos 算法實例過程中只批準(zhǔn)一個Value”這一約束條件幌氮。
2.4 CAP理論
Consistency (一致性)：CAP 理論中的副本一致性特指強一致性；
Availiablity(可用性)：指系統(tǒng)在出現(xiàn)異常時已經(jīng)可以提供服務(wù)浩销；
Tolerance to the partition of network (分區(qū)容忍)：指系統(tǒng)可以在網(wǎng)絡(luò)分區(qū)(節(jié)點間網(wǎng)絡(luò)不通，整個集群被分成了多個區(qū)域)這種異常情況下慢洋，具有的容錯能力塘雳；
無法設(shè)計一種分布式協(xié)議普筹，使得同時完全具備CAP三個屬性
? ? ? ? ? ? ? ? ? ? ? ? C? ? ? ?A? ? ? ? P
Lease機制：滿足? ? 完全? ?部分
Quorum：? ? 部分? ? 部分? ?部分
兩階段：? ? ? ?完全? ?差? ? ? 差
Paxos：? ? ? ? 完全? ? 部分? ? 部分
在CAP之后败明，BASE理論（Basic Availiablity太防，Soft status妻顶，Eventually consistent）
