1.架構(gòu)設(shè)計(jì)

這一節(jié)將從一些經(jīng)典的開源系統(tǒng)架構(gòu)設(shè)計(jì)出發(fā)，來看一下，如何設(shè)計(jì)一個(gè)高質(zhì)量的分布式系統(tǒng)；

而一般的設(shè)計(jì)出發(fā)點(diǎn)，無外乎

?冗余：簡單理解為找個(gè)備胎，現(xiàn)任掛掉之后，備胎頂上?拆分：不能讓一個(gè)人承擔(dān)所有的重任，拆分下，每個(gè)人負(fù)擔(dān)一部分，壓力均攤

1.1 主備架構(gòu)

給現(xiàn)有的服務(wù)搭建一個(gè)備用的服務(wù)，兩者功能完全一致，區(qū)別在于平時(shí)只有主應(yīng)用對(duì)外提供服務(wù)能力；而備應(yīng)用則只需要保證與主應(yīng)用能力一致，隨時(shí)待機(jī)即可，并不用對(duì)外提供服務(wù)；當(dāng)主應(yīng)用出現(xiàn)故障之后，將備應(yīng)用切換為主應(yīng)用，原主應(yīng)用下線；迅速的主備切換可以有效的縮短故障時(shí)間

基于上面的描述，主備架構(gòu)特點(diǎn)比較清晰

?采用冗余的方案，加一臺(tái)備用服務(wù)?缺點(diǎn)就是資源浪費(fèi)

其次就是這個(gè)架構(gòu)模型最需要考慮的則是如何實(shí)現(xiàn)主備切換？

?人工?VIP(虛擬ip) + keepalived 機(jī)制

1.2 主從架構(gòu)

主從一般又叫做讀寫分離，主提供讀寫能力，而從則只提供讀能力

鑒于當(dāng)下的互聯(lián)網(wǎng)應(yīng)用，絕大多數(shù)都是讀多寫少的場景；讀更容易成為性能瓶頸，所以采用讀寫分離，可以有效的提高整個(gè)集群的響應(yīng)能力

主從架構(gòu)可以區(qū)分為：一主多從 + 一主一從再多從，以mysql的主從架構(gòu)模型為例進(jìn)行說明

MySql主從

主從模式的主要特點(diǎn)在于

?添加從，源頭依然是數(shù)據(jù)冗余的思想?讀寫分離：主負(fù)責(zé)讀寫，從只負(fù)責(zé)讀，可以視為負(fù)載均衡策略?從需要向主同步數(shù)據(jù)，所若有的從都同步與主，對(duì)主的壓力依然可能很大；所以就有了主從從的模式

關(guān)鍵問題則在于

?主從延遲?主的寫瓶頸?主掛之后如何選主

1.3 多主多從架構(gòu)

一主多從面臨單主節(jié)點(diǎn)的瓶頸問題，那就考慮多主多從的策略，同樣是主負(fù)責(zé)提供讀寫，從提供讀；

但是這里有一個(gè)核心點(diǎn)在于多主之間的數(shù)據(jù)同步，如何保證數(shù)據(jù)的一致性是這個(gè)架構(gòu)模型的重點(diǎn)

如MySql的雙主雙從可以說是一個(gè)典型的應(yīng)用場景，在實(shí)際使用的時(shí)候除了上面的一致性之外，還需要考慮主鍵id沖突的問題

1.4 普通集群模式

無主節(jié)點(diǎn)，集群中所有的應(yīng)用職能對(duì)等，沒有主次之分（當(dāng)下絕大多數(shù)的業(yè)務(wù)服務(wù)都屬于這種），一個(gè)請(qǐng)求可以被集群中任意一個(gè)服務(wù)響應(yīng)；

這種也可以叫做去中心化的設(shè)計(jì)模式，如redis的集群模式，eureka注冊(cè)中心，以可用性為首要目標(biāo)

對(duì)于普通集群模式而言，重點(diǎn)需要考慮的點(diǎn)在于

?資源競爭：如何確保一個(gè)資源在同一時(shí)刻只能被一個(gè)業(yè)務(wù)操作?如現(xiàn)在同時(shí)來了申請(qǐng)退款和貨物出庫的請(qǐng)求，如果不對(duì)這個(gè)訂單進(jìn)行加鎖，兩個(gè)請(qǐng)求同時(shí)響應(yīng)，將會(huì)導(dǎo)致發(fā)貨又退款了，導(dǎo)致財(cái)貨兩失?數(shù)據(jù)一致性：如何確保所有的實(shí)例數(shù)據(jù)都是一致的，或者最終是一致的?如應(yīng)用服務(wù)使用jvm緩存，那么如何確保所有實(shí)例的jvm緩存一致？?如Eureka的分區(qū)導(dǎo)致不同的分區(qū)的注冊(cè)信息表不一致

1.5 數(shù)據(jù)分片架構(gòu)

這個(gè)分片模型的描述可能并不準(zhǔn)確，大家看的時(shí)候重點(diǎn)理解一下這個(gè)思想

前面幾個(gè)的架構(gòu)中，采用的是數(shù)據(jù)冗余的方式，即所有的實(shí)例都有一個(gè)全量的數(shù)據(jù)，而這里的數(shù)據(jù)分片，則從數(shù)據(jù)拆分的思路來處理，將全量的數(shù)據(jù)，通過一定規(guī)則拆分到多個(gè)系統(tǒng)中，每個(gè)系統(tǒng)包含部分的數(shù)據(jù)，減小單個(gè)節(jié)點(diǎn)的壓力，主要用于解決數(shù)據(jù)量大的場景

比如redis的集群方式，通過hash槽的方式進(jìn)行分區(qū)

如es的索引分片存儲(chǔ)

1.6 一灰灰的小結(jié)

這一節(jié)主要從架構(gòu)設(shè)計(jì)層面對(duì)當(dāng)前的分布式系統(tǒng)所采用的方案進(jìn)行了一個(gè)簡單的歸類與小結(jié)，并不一定全面，歡迎各位大佬留言指正

基于冗余的思想：

?主備?主從?多主多從?無中心集群

基于拆分的思想：

?數(shù)據(jù)分片

對(duì)于拆分這一塊，我們常說的分庫分表也體現(xiàn)的是這一思想

2.理論基礎(chǔ)

這一小節(jié)將介紹分布式系統(tǒng)中的經(jīng)典理論，如廣為流程的CAP/BASE理論，一致性理論基礎(chǔ)paxios,raft，信息交換的Gossip協(xié)議，兩階段、三階段等

本節(jié)主要內(nèi)容參考自

?一致性算法-Gossip協(xié)議詳解 - 騰訊云開發(fā)者社區(qū)-騰訊云^[1]?P2P 網(wǎng)絡(luò)核心技術(shù)：Gossip 協(xié)議 - 知乎^[2]?從Paxos到Raft，分布式一致性算法解析_mb5fdb0a87e2fa1的技術(shù)博客_51CTO博客^[3]?【理論篇】淺析分布式中的 CAP、BASE、2PC、3PC、Paxos、Raft、ZAB - 知乎^[4]

2.1 CAP定理

CAP 定理指出，分布式系統(tǒng) 不可能 同時(shí)提供下面三個(gè)要求：

?Consistency：一致性?操作更新完成并返回客戶端之后，所有節(jié)點(diǎn)數(shù)據(jù)完全一致?Availability：可用性?服務(wù)一直可用?Partition tolerance：分區(qū)容錯(cuò)性?分布式系統(tǒng)在遇到某節(jié)點(diǎn)或網(wǎng)絡(luò)分區(qū)故障的時(shí)候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務(wù)

通常來講P很難不保證，當(dāng)服務(wù)部署到多臺(tái)實(shí)例上時(shí)，節(jié)點(diǎn)異常、網(wǎng)絡(luò)故障屬于常態(tài)，根據(jù)不同業(yè)務(wù)場景進(jìn)行選擇

對(duì)于服務(wù)有限的應(yīng)用而言，首選AP，保證高可用，即使部分機(jī)器異常，也不會(huì)導(dǎo)致整個(gè)服務(wù)不可用；如絕大多數(shù)的前臺(tái)應(yīng)用都是這種

對(duì)于數(shù)據(jù)一致性要求高的場景，如涉及到錢的支付結(jié)算，CP可能更重要了

對(duì)于CAP的三種組合說明如下

2.2 BASE理論

base理論作為cap的延伸，其核心特點(diǎn)在于放棄強(qiáng)一致性，追求最終一致性

?Basically Available: 基本可用?指分布式系統(tǒng)在出現(xiàn)故障的時(shí)候，允許損失部分可用性，即保證核心可用?如大促時(shí)降級(jí)策略?Soft State：軟狀態(tài)?允許系統(tǒng)存在中間狀態(tài)，而該中間狀態(tài)不會(huì)影響系統(tǒng)整體可用性?MySql異步方式的主從同步，可能導(dǎo)致的主從數(shù)據(jù)不一致?Eventual Consistency：最終一致性?最終一致性是指系統(tǒng)中的所有數(shù)據(jù)副本經(jīng)過一定時(shí)間后，最終能夠達(dá)到一致的狀態(tài)

基于上面的描述，可以看到BASE理論適用于大型高可用可擴(kuò)展的分布式系統(tǒng)

注意其不同于ACID的強(qiáng)一致性模型，而是通過犧牲強(qiáng)一致性 來獲得可用性，并允許數(shù)據(jù)在一段時(shí)間內(nèi)是不一致的，但最終達(dá)到一致狀態(tài)

2.3 PACELEC 定理

這個(gè)真沒聽說過，以下內(nèi)容來自:

?Distributed System Design Patterns | by Nishant | Medium^[5]

?如果有一個(gè)分區(qū)（'P'），分布式系統(tǒng)可以在可用性和一致性（即'A'和'C'）之間進(jìn)行權(quán)衡;?否則（'E'），當(dāng)系統(tǒng)在沒有分區(qū)的情況下正常運(yùn)行時(shí)，系統(tǒng)可以在延遲（'L'）和一致性（'C'）之間進(jìn)行權(quán)衡。

定理（PAC）的第一部分與CAP定理相同，ELC是擴(kuò)展。整個(gè)論點(diǎn)假設(shè)我們通過復(fù)制來保持高可用性。因此，當(dāng)失敗時(shí)，CAP定理占上風(fēng)。但如果沒有，我們?nèi)匀槐仨毧紤]復(fù)制系統(tǒng)的一致性和延遲之間的權(quán)衡。

2.4 Paxos共識(shí)算法

Paxos算法解決的問題是分布式共識(shí)性問題，即一個(gè)分布式系統(tǒng)中的各個(gè)進(jìn)程如何就某個(gè)值（決議）通過共識(shí)達(dá)成一致

基于上面這個(gè)描述，可以看出它非常適用于選舉；其工作流程

?一個(gè)或多個(gè)提議進(jìn)程 (Proposer) 可以發(fā)起提案 (Proposal)，?Paxos算法使所有提案中的某一個(gè)提案，在所有進(jìn)程中達(dá)成一致。系統(tǒng)中的多數(shù)派同時(shí)認(rèn)可該提案，即達(dá)成了一致

角色劃分:

?Proposer: 提出提案Proposal，包含編號(hào) + value?Acceptor: 參與決策，回應(yīng)Proposers的提案；當(dāng)一個(gè)提案，被半數(shù)以上的Acceptor接受，則該提案被批準(zhǔn)?每個(gè)acceptor只能批準(zhǔn)一個(gè)提案?Learner: 不參與決策，獲取最新的提案value

2.5 Raft算法

為了解決paxos的復(fù)雜性，raft算法提供了一套更易理解的算法基礎(chǔ)，其核心流程在于：

leader接受請(qǐng)求，并轉(zhuǎn)發(fā)給follow，當(dāng)大部分follow響應(yīng)之后，leader通知所有的follow提交請(qǐng)求、同時(shí)自己也提交請(qǐng)求并告訴調(diào)用方ok

角色劃分：

?Leader：領(lǐng)導(dǎo)者，接受客戶端請(qǐng)求，并向Follower同步請(qǐng)求，當(dāng)數(shù)據(jù)同步到大多數(shù)節(jié)點(diǎn)上后告訴Follower提交日志?Follow: 接受并持久化Leader同步的數(shù)據(jù)，在Leader告之日志可以提交之后，提交?Candidate：Leader選舉過程中的臨時(shí)角色，向其他節(jié)點(diǎn)拉選票，得到多數(shù)的晉升為leader，選舉完成之后不存在這個(gè)角色

raft共識(shí)流程

2.6 ZAB協(xié)議

ZAB(Zookeeper Atomic Broadcast) 協(xié)議是為分布式協(xié)調(diào)服務(wù)ZooKeeper專門設(shè)計(jì)的一種支持崩潰恢復(fù)的一致性協(xié)議，基于該協(xié)議，ZooKeeper 實(shí)現(xiàn)了一種 主從模式的系統(tǒng)架構(gòu)來保持集群中各個(gè)副本之間的數(shù)據(jù)一致性。

?zookeeper核心之ZAB協(xié)議就這么簡單！^[8]

主要用于zk的數(shù)據(jù)一致性場景，其核心思想是Leader再接受到事務(wù)請(qǐng)求之后，通過給Follower，當(dāng)半數(shù)以上的Follower返回ACK之后，Leader提交提案，并向Follower發(fā)送commit信息

角色劃分

?Leader: 負(fù)責(zé)整個(gè)Zookeeper 集群工作機(jī)制中的核心?事務(wù)請(qǐng)求的唯一調(diào)度和處理者，保證集群事務(wù)處理的順序性?集群內(nèi)部各服務(wù)器的調(diào)度者?Follower：Leader的追隨者?處理客戶端的非實(shí)物請(qǐng)求，轉(zhuǎn)發(fā)事務(wù)請(qǐng)求給 Leader 服務(wù)器?參與事務(wù)請(qǐng)求 Proposal 的投票?參與 Leader 選舉投票?Observer：是 zookeeper 自 3.3.0 開始引入的一個(gè)角色，?它不參與事務(wù)請(qǐng)求 Proposal 的投票，?也不參與 Leader 選舉投票?只提供非事務(wù)的服務(wù)（查詢），通常在不影響集群事務(wù)處理能力的前提下提升集群的非事務(wù)處理能力。

ZAB消息廣播

2.7 2PC協(xié)議

two-phase commit protocol，兩階段提交協(xié)議，主要是為了解決強(qiáng)一致性，中心化的強(qiáng)一致性協(xié)議

角色劃分

?協(xié)調(diào)節(jié)點(diǎn)(coordinator)：中心化?參與者節(jié)點(diǎn)(partcipant)：多個(gè)

執(zhí)行流程

協(xié)調(diào)節(jié)點(diǎn)接收請(qǐng)求，然后向參與者節(jié)點(diǎn)提交 ??precommit???，當(dāng)所有的參與者都回復(fù)ok之后，協(xié)調(diào)節(jié)點(diǎn)再給所有的參與者節(jié)點(diǎn)提交??commit??，所有的都返回ok之后，才表明這個(gè)數(shù)據(jù)確認(rèn)提交

當(dāng)?shù)谝粋€(gè)階段，有一個(gè)參與者失敗，則所有的參與者節(jié)點(diǎn)都回滾

2pc流程

特點(diǎn)

優(yōu)點(diǎn)在于實(shí)現(xiàn)簡單

缺點(diǎn)也很明顯

?協(xié)調(diào)節(jié)點(diǎn)的單點(diǎn)故障?第一階段全部ack正常，第二階段存在部分參與者節(jié)點(diǎn)異常時(shí)，可能出現(xiàn)不一致問題

2.8 3PC協(xié)議

分布式事務(wù)：兩階段提交與三階段提交 - SegmentFault 思否^[9]

在兩階段的基礎(chǔ)上進(jìn)行擴(kuò)展，將第一階段劃分兩部，cancommit + precommit，第三階段則為 docommit

第一階段 cancommit

該階段協(xié)調(diào)者會(huì)去詢問各個(gè)參與者是否能夠正常執(zhí)行事務(wù)，參與者根據(jù)自身情況回復(fù)一個(gè)預(yù)估值，相對(duì)于真正的執(zhí)行事務(wù)，這個(gè)過程是輕量的

第二階段 precommit

本階段協(xié)調(diào)者會(huì)根據(jù)第一階段的詢盤結(jié)果采取相應(yīng)操作，若所有參與者都返回ok，則協(xié)調(diào)者向參與者提交事務(wù)執(zhí)行(單不提交)通知；否則通知參與者abort回滾

第三階段 docommit

如果第二階段事務(wù)未中斷，那么本階段協(xié)調(diào)者將會(huì)依據(jù)事務(wù)執(zhí)行返回的結(jié)果來決定提交或回滾事務(wù)，若所有參與者正常執(zhí)行，則提交；否則協(xié)調(diào)者+參與者回滾

在本階段如果因?yàn)閰f(xié)調(diào)者或網(wǎng)絡(luò)問題，導(dǎo)致參與者遲遲不能收到來自協(xié)調(diào)者的 commit 或 rollback 請(qǐng)求，那么參與者將不會(huì)如兩階段提交中那樣陷入阻塞，而是等待超時(shí)后繼續(xù) commit，相對(duì)于兩階段提交雖然降低了同步阻塞，但仍然無法完全避免數(shù)據(jù)的不一致

特點(diǎn)

?降低了阻塞與單點(diǎn)故障：?參與者返回 CanCommit 請(qǐng)求的響應(yīng)后，等待第二階段指令，若等待超時(shí)/協(xié)調(diào)者宕機(jī)，則自動(dòng) abort，降低了阻塞；?參與者返回 PreCommit 請(qǐng)求的響應(yīng)后，等待第三階段指令，若等待超時(shí)/協(xié)調(diào)者宕機(jī)，則自動(dòng) commit 事務(wù)，也降低了阻塞；?數(shù)據(jù)不一致問題依然存在?比如第三階段協(xié)調(diào)者發(fā)出了 abort 請(qǐng)求，然后有些參與者沒有收到 abort，那么就會(huì)自動(dòng) commit，造成數(shù)據(jù)不一致

2.9 Gossip協(xié)議

Gossip 協(xié)議，顧名思義，就像流言蜚語一樣，利用一種隨機(jī)、帶有傳染性的方式，將信息傳播到整個(gè)網(wǎng)絡(luò)中，并在一定時(shí)間內(nèi)，使得系統(tǒng)內(nèi)的所有節(jié)點(diǎn)數(shù)據(jù)一致。Gossip 協(xié)議通過上面的特性，可以保證系統(tǒng)能在極端情況下（比如集群中只有一個(gè)節(jié)點(diǎn)在運(yùn)行）也能運(yùn)行

?P2P 網(wǎng)絡(luò)核心技術(shù)：Gossip 協(xié)議 - 知乎^[10]

主要用在分布式數(shù)據(jù)庫系統(tǒng)中各個(gè)副本節(jié)點(diǎn)同步數(shù)據(jù)之用，這種場景的一個(gè)最大特點(diǎn)就是組成的網(wǎng)絡(luò)的節(jié)點(diǎn)都是對(duì)等節(jié)點(diǎn)，是非結(jié)構(gòu)化網(wǎng)絡(luò)

工作流程

?周期性的傳播消息，通常周期時(shí)間為1s?被感染的節(jié)點(diǎn)，隨機(jī)選擇n個(gè)相鄰節(jié)點(diǎn)，傳播消息?每次傳播消息都選擇還沒有發(fā)送過的節(jié)點(diǎn)進(jìn)行傳播?收單消息的節(jié)點(diǎn)，不會(huì)傳播給向它發(fā)送消息的節(jié)點(diǎn)

Gossip傳播示意圖

特點(diǎn)

?擴(kuò)展性：允許節(jié)點(diǎn)動(dòng)態(tài)增加、減少，新增的節(jié)點(diǎn)狀態(tài)最終會(huì)與其他節(jié)點(diǎn)一致?容錯(cuò)：網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)宕機(jī)重啟都不會(huì)影響消息傳播?去中心化：不要求中心節(jié)點(diǎn)，所有節(jié)點(diǎn)對(duì)等，任何一個(gè)節(jié)點(diǎn)無需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)連通，則一個(gè)節(jié)點(diǎn)的消息最終會(huì)散播到整個(gè)網(wǎng)絡(luò)?一致性收斂：協(xié)議中的消息會(huì)以一傳十、十傳百一樣的指數(shù)級(jí)速度在網(wǎng)絡(luò)中快速傳播，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致。消息傳播速度達(dá)到了 logN?簡單：Gossip 協(xié)議的過程極其簡單，實(shí)現(xiàn)起來幾乎沒有太多復(fù)雜性

缺點(diǎn)

?消息延遲：節(jié)點(diǎn)只會(huì)隨機(jī)向少數(shù)幾個(gè)節(jié)點(diǎn)發(fā)送消息，消息最終是通過多個(gè)輪次的散播而到達(dá)全網(wǎng)的，因此使用 Gossip 協(xié)議會(huì)造成不可避免的消息延遲?消息冗余：節(jié)點(diǎn)會(huì)定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息，而收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該步驟，導(dǎo)致消息的冗余

2.10 一灰灰的小結(jié)

本節(jié)主要介紹的是分布式系統(tǒng)設(shè)計(jì)中的一些常見的理論基石，如分布式中如何保障一致性，如何對(duì)一個(gè)提案達(dá)成共識(shí)

?BASE，CAP，PACELEC理論：構(gòu)建穩(wěn)定的分布式系統(tǒng)應(yīng)該考慮的方向?paxos,raft共識(shí)算法?zab一致性協(xié)議?gossip消息同步協(xié)議

3.算法

這一節(jié)將主要介紹下分布式系統(tǒng)中的經(jīng)典的算法，比如常用于分區(qū)的一致性hash算法，適用于一致性的Quorum NWR算法，PBFT拜占庭容錯(cuò)算法，區(qū)塊鏈中大量使用的工作量證明PoW算法等

3.1 一致性hash算法

一致性hash算法，主要應(yīng)用于數(shù)據(jù)分片場景下，有效降低服務(wù)的新增、刪除對(duì)數(shù)據(jù)復(fù)制的影響

通過對(duì)數(shù)據(jù)項(xiàng)的鍵進(jìn)行哈希處理映射其在環(huán)上的位置，然后順時(shí)針遍歷環(huán)以查找位置大于該項(xiàng)位置的第一個(gè)節(jié)點(diǎn)，將每個(gè)由鍵標(biāo)識(shí)的數(shù)據(jù)分配給hash環(huán)中的一個(gè)節(jié)點(diǎn)

一致性hash算法

一致散列的主要優(yōu)點(diǎn)是增量穩(wěn)定性; 節(jié)點(diǎn)添加刪除，對(duì)整個(gè)集群而言，僅影響其直接鄰居，其他節(jié)點(diǎn)不受影響。

注意：

?redis集群實(shí)現(xiàn)了一套hash槽機(jī)制，其核心思想與一致性hash比較相似

3.2 Quorum NWR算法

用來保證數(shù)據(jù)冗余和最終一致性的投票算法，其主要數(shù)學(xué)思想來源于鴿巢原理

?分布式系統(tǒng)之Quorum （NRW）算法-阿里云開發(fā)者社區(qū)^[11]

?N 表示副本數(shù)，又叫做復(fù)制因子（Replication Factor）。也就是說，N 表示集群中同一份數(shù)據(jù)有多少個(gè)副本?W，又稱寫一致性級(jí)別（Write Consistency Level），表示成功完成 W 個(gè)副本更新寫入，才會(huì)視為本次寫操作成功?R 又稱讀一致性級(jí)別（Read Consistency Level），表示讀取一個(gè)數(shù)據(jù)對(duì)象時(shí)需要讀 R 個(gè)副本, 才會(huì)視為本次讀操作成功

Quorum NWR算法要求每個(gè)數(shù)據(jù)拷貝對(duì)象 都可以投1票，而每一個(gè)操作的執(zhí)行則需要獲取最小的讀票數(shù)，寫票數(shù)；通常來講寫票數(shù)W一般需要超過N/2，即我們通常說的得到半數(shù)以上的票才表示數(shù)據(jù)寫入成功

事實(shí)上當(dāng)W=N、R=1時(shí)，即所謂的WARO(Write All Read One)。就是CAP理論中CP模型的場景

3.3 PBFT拜占庭算法

拜占庭算法主要針對(duì)的是分布式場景下無響應(yīng)，或者響應(yīng)不可信的情況下的容錯(cuò)問題，其核心分三段流程，如下

拜占庭算法

假設(shè)集群節(jié)點(diǎn)數(shù)為 N，f個(gè)故障節(jié)點(diǎn)(無響應(yīng))和f個(gè)問題節(jié)點(diǎn)(無響應(yīng)或錯(cuò)誤響應(yīng)),f+1個(gè)正常節(jié)點(diǎn)，即 3f+1=n

?客戶端向主節(jié)點(diǎn)發(fā)起請(qǐng)求，主節(jié)點(diǎn)接受請(qǐng)求之后，向其他節(jié)點(diǎn)廣播 pre-prepare 消息?節(jié)點(diǎn)接受pre-prepare消息之后，若同意請(qǐng)求，則向其他節(jié)點(diǎn)廣播 prepare 消息；?當(dāng)一個(gè)節(jié)點(diǎn)接受到2f+1個(gè)prepare新消息，則進(jìn)入commit階段，并廣播commit消息?當(dāng)收到 2f+1 個(gè) commit 消息后（包括自己），代表大多數(shù)節(jié)點(diǎn)已經(jīng)進(jìn)入 commit 階段，這一階段已經(jīng)達(dá)成共識(shí)，于是節(jié)點(diǎn)就會(huì)執(zhí)行請(qǐng)求，寫入數(shù)據(jù)

相比 Raft 算法完全不適應(yīng)有人作惡的場景，PBFT 算法能容忍 (n 1)/3 個(gè)惡意節(jié)點(diǎn) (也可以是故障節(jié)點(diǎn))。另外，相比 PoW 算法，PBFT 的優(yōu)點(diǎn)是不消耗算 力。PBFT 算法是O(n ^ 2) 的消息復(fù)雜度的算法，所以以及隨著消息數(shù) 的增加，網(wǎng)絡(luò)時(shí)延對(duì)系統(tǒng)運(yùn)行的影響也會(huì)越大，這些都限制了運(yùn)行 PBFT 算法的分布式系統(tǒng) 的規(guī)模，也決定了 PBFT 算法適用于中小型分布式系統(tǒng)

3.4 PoW算法

工作量證明 (Proof Of Work，簡稱 PoW)，同樣應(yīng)用于分布式下的一致性場景，區(qū)別于前面的raft, pbft, paxos采用投票機(jī)制達(dá)成共識(shí)方案，pow采用工作量證明

客戶端需要做一定難度的工作才能得出一個(gè)結(jié)果，驗(yàn)證方卻很容易通過結(jié)果來檢查出客戶端是不是做了相應(yīng)的工作，通過消耗一定工作浪，增加消息偽造的成本，PoW以區(qū)塊鏈中廣泛應(yīng)用而廣為人知，下面以區(qū)塊鏈來簡單說一下PoW的算法應(yīng)用場景

以BTC的轉(zhuǎn)賬為例，A轉(zhuǎn)n個(gè)btc給B，如何保證不會(huì)同時(shí)將這n個(gè)幣轉(zhuǎn)給C？

?A轉(zhuǎn)賬給B，交易信息記錄在一個(gè)區(qū)塊1中?A轉(zhuǎn)賬給C，交易信息被記錄在另一個(gè)區(qū)塊2中?當(dāng)區(qū)塊1被礦工成功提交到鏈上，并被大多數(shù)認(rèn)可（通過校驗(yàn)區(qū)塊鏈上的hash值驗(yàn)證是否準(zhǔn)確，而這個(gè)hash值體現(xiàn)的是礦工的工作量），此時(shí)尚未提交的區(qū)塊2則會(huì)被拋棄?若區(qū)塊1被提交，區(qū)塊2也被提交，各自有部分人認(rèn)可，就會(huì)導(dǎo)致分叉，區(qū)塊鏈中采用的是優(yōu)選最長的鏈作為主鏈，丟棄分叉的部分（這就屬于區(qū)塊鏈的知識(shí)點(diǎn)了，有興趣的小伙伴可以擴(kuò)展下相關(guān)知識(shí)點(diǎn)，這里就不展開了）

PoW的算法，主要應(yīng)用在上面的區(qū)塊提交驗(yàn)證，通過hash值計(jì)算來消耗算力，以此證明礦工確實(shí)有付出，得到多數(shù)認(rèn)可的可以達(dá)成共識(shí)

3.5 一灰灰的小結(jié)

本節(jié)主要介紹了下當(dāng)前分布式下常見的算法，

?分區(qū)的一致性hash算法: 基于hash環(huán)，減少節(jié)點(diǎn)動(dòng)態(tài)增加減少對(duì)整個(gè)集群的影響；適用于數(shù)據(jù)分片的場景?適用于一致性的Quorum NWR算法: 投票算法，定義如何就一個(gè)提案達(dá)成共識(shí)?PBFT拜占庭容錯(cuò)算法: 適用于集群中節(jié)點(diǎn)故障、或者不可信的場景?區(qū)塊鏈中大量使用的工作量證明PoW算法: 通過工作量證明，認(rèn)可節(jié)點(diǎn)的提交

4.技術(shù)思想

這一節(jié)的內(nèi)容相對(duì)前面幾個(gè)而言，并不太容易進(jìn)行清晰的分類；主要包含一些高質(zhì)量的分布式系統(tǒng)的實(shí)踐中，值得推薦的設(shè)計(jì)思想、技術(shù)細(xì)節(jié)

4.1 CQRS

?DDD 中的那些模式 — CQRS - 知乎^[12]?詳解CQRS架構(gòu)模式_架構(gòu)_Kislay Verma_InfoQ精選文章^[13]

Command Query Responsibility Segregation 即我們通俗理解的讀寫分離，其核心思想在于將兩類不同操作進(jìn)行分離，在獨(dú)立的服務(wù)中實(shí)現(xiàn)

cqrs

用途在于將領(lǐng)域模型與查詢功能進(jìn)行分離，讓一些復(fù)雜的查詢擺脫領(lǐng)域模型的限制，以更為簡單的 DTO 形式展現(xiàn)查詢結(jié)果。同時(shí)分離了不同的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，讓開發(fā)者按照查詢的功能與要求更加自由的選擇數(shù)據(jù)存儲(chǔ)引擎

4.2 復(fù)制負(fù)載平衡服務(wù)

?分布式系統(tǒng)設(shè)計(jì):服務(wù)模式之復(fù)制負(fù)載平衡服務(wù) - 知乎^[14]?負(fù)載均衡調(diào)度算法大全 | 菜鳥教程^[15]

復(fù)制負(fù)載平衡服務(wù)(Replication Load Balancing Service, RLBS)，可以簡單理解為我們常說的負(fù)載均衡，多個(gè)相同的服務(wù)實(shí)例構(gòu)建一個(gè)集群，每個(gè)服務(wù)都可以響應(yīng)請(qǐng)求，負(fù)載均衡器負(fù)責(zé)請(qǐng)求的分發(fā)到不同的實(shí)例上，常見的負(fù)載算法

4.3 心跳機(jī)制

在分布式環(huán)境里中，如何判斷一個(gè)服務(wù)是否存活，當(dāng)下最常見的方案就是心跳

比如raft算法中的leader向所有的follow發(fā)送心跳，表示自己還健在，避免發(fā)生新的選舉；

比如redis的哨兵機(jī)制，也是通過ping/pong的心跳來判斷節(jié)點(diǎn)是否下線，是否需要選新的主節(jié)點(diǎn)；

再比如我們?nèi)粘５臉I(yè)務(wù)應(yīng)用得健康監(jiān)測，判斷服務(wù)是否正常

4.4 租約機(jī)制

租約就像一個(gè)鎖，但即使客戶端離開，它也能工作?？蛻舳苏?qǐng)求有限期限的租約，之后租約到期。如果客戶端想要延長租約，它可以在租約到期之前續(xù)訂租約。

租約主要是了避免一個(gè)資源長久被某個(gè)對(duì)象持有，一旦對(duì)方掛了且不會(huì)主動(dòng)釋放的問題；在實(shí)際的場景中，有兩個(gè)典型的應(yīng)用

case1 分布式鎖

業(yè)務(wù)獲取的分布式鎖一般都有一個(gè)有效期，若有效期內(nèi)沒有主動(dòng)釋放，這個(gè)鎖依然會(huì)被釋放掉，其他業(yè)務(wù)也可以搶占到這把鎖；因此對(duì)于持有鎖的業(yè)務(wù)方而言，若發(fā)現(xiàn)在到期前，業(yè)務(wù)邏輯還沒有處理完，則可以續(xù)約，讓自己繼續(xù)持有這把鎖

典型的實(shí)現(xiàn)方式是redisson的看門狗機(jī)制

case2 raft算法的任期

在raft算法中，每個(gè)leader都有一個(gè)任期，任期過后會(huì)重新選舉，而Leader為了避免重新選舉，一般會(huì)定時(shí)發(fā)送心跳到Follower進(jìn)行續(xù)約

4.5 Leader & Follow

這個(gè)比較好理解，上面很多系統(tǒng)都采用了這種方案，特別是在共識(shí)算法中，由領(lǐng)導(dǎo)者負(fù)責(zé)代表整個(gè)集群做出決策，并將決策傳播到所有其他服務(wù)器

領(lǐng)導(dǎo)者選舉在服務(wù)器啟動(dòng)時(shí)進(jìn)行。每個(gè)服務(wù)器在啟動(dòng)時(shí)都會(huì)啟動(dòng)領(lǐng)導(dǎo)者選舉，并嘗試選舉領(lǐng)導(dǎo)者。除非選出領(lǐng)導(dǎo)者，否則系統(tǒng)不接受任何客戶端請(qǐng)求

4.6 Fencing

在領(lǐng)導(dǎo)者-追隨者模式中，當(dāng)領(lǐng)導(dǎo)者失敗時(shí)，不可能確定領(lǐng)導(dǎo)者已停止工作，如慢速網(wǎng)絡(luò)或網(wǎng)絡(luò)分區(qū)可能會(huì)觸發(fā)新的領(lǐng)導(dǎo)者選舉，即使前一個(gè)領(lǐng)導(dǎo)者仍在運(yùn)行并認(rèn)為它仍然是活動(dòng)的領(lǐng)導(dǎo)者

Fencint是指在以前處于活動(dòng)狀態(tài)的領(lǐng)導(dǎo)者周圍設(shè)置圍欄，使其無法訪問集群資源，從而停止為任何讀/寫請(qǐng)求提供服務(wù)

?資源屏蔽：系統(tǒng)會(huì)阻止以前處于活動(dòng)狀態(tài)的領(lǐng)導(dǎo)者訪問執(zhí)行基本任務(wù)所需的資源。?節(jié)點(diǎn)屏蔽：系統(tǒng)會(huì)阻止以前處于活動(dòng)狀態(tài)的領(lǐng)導(dǎo)者訪問所有資源。執(zhí)行此操作的常見方法是關(guān)閉節(jié)點(diǎn)電源或重置節(jié)點(diǎn)。

4.7 Quorum法定人數(shù)

法定人數(shù)，常見于選舉、共識(shí)算法中，當(dāng)超過Quorum的節(jié)點(diǎn)數(shù)確認(rèn)之后，才表示這個(gè)提案通過(數(shù)據(jù)更新成功)，通常這個(gè)法定人數(shù)為 = 半數(shù)節(jié)點(diǎn) + 1

4.8 High-Water mark高水位線

高水位線，跟蹤Leader（領(lǐng)導(dǎo)者）上的最后一個(gè)日志條目，且該條目已成功復(fù)制到>quorum（法定人數(shù)）的Follow（跟誰者），即表示這個(gè)日志被整個(gè)集群接受

日志中此條目的索引稱為高水位線索引。領(lǐng)導(dǎo)者僅公開到高水位線索引的數(shù)據(jù)。

如Kafka：為了處理非可重復(fù)讀取并確保數(shù)據(jù)一致性，Kafka broker會(huì)跟蹤高水位線，這是特定分區(qū)的最大偏移量。使用者只能看到高水位線之前的消息。

4.9 Phi 累計(jì)故障檢測

Phi Accrual Failure Detection,使用歷史檢測信號(hào)信息使閾值自適應(yīng)

通用的應(yīng)計(jì)故障檢測器不會(huì)判斷服務(wù)器是否處于活動(dòng)狀態(tài)，而是輸出有關(guān)服務(wù)器的可疑級(jí)別。

如Cassandra（Facebook開源的分布式NoSql數(shù)據(jù)庫）使用 Phi 應(yīng)計(jì)故障檢測器算法來確定群集中節(jié)點(diǎn)的狀態(tài)

4.10 Write-ahead Log預(yù)寫日志

預(yù)寫日志記錄是解決操作系統(tǒng)中文件系統(tǒng)不一致的問題的高級(jí)解決方案，當(dāng)我們提交寫到操作系統(tǒng)的文件緩存，此時(shí)業(yè)務(wù)會(huì)認(rèn)為已經(jīng)提交成功；但是在文件緩存與實(shí)際寫盤之間會(huì)有一個(gè)時(shí)間差，若此時(shí)機(jī)器宕機(jī)，會(huì)導(dǎo)致緩存中的數(shù)據(jù)丟失，從而導(dǎo)致完整性缺失

為了解決這個(gè)問題，如mysql，es等都采用了預(yù)寫日志的機(jī)制來避免這個(gè)問題

MySql：

?事務(wù)提交的流程中，先寫redolog precommit， 然后寫binlog，最后再redolog commit；當(dāng)redolog記錄成功之后，才表示事務(wù)執(zhí)行成功；?因此當(dāng)出現(xiàn)上面的宕機(jī)恢復(fù)時(shí)，則會(huì)加載redologo，然后重放對(duì)應(yīng)的命令，來恢復(fù)未持久化的數(shù)據(jù)

ElasticSearch:

?在內(nèi)存中數(shù)據(jù)生成段寫到操作系統(tǒng)文件緩存前，會(huì)先寫事務(wù)日志，出現(xiàn)異常時(shí)，也是從事務(wù)日志進(jìn)行恢復(fù)

4.11 分段日志

將日志拆分為多個(gè)較小的文件，而不是單個(gè)大文件，以便于操作。

單個(gè)日志文件在啟動(dòng)時(shí)讀取時(shí)可能會(huì)增長并成為性能瓶頸。較舊的日志會(huì)定期清理，并且很難對(duì)單個(gè)大文件執(zhí)行清理操作。

單個(gè)日志拆分為多個(gè)段。日志文件在指定的大小限制后滾動(dòng)。使用日志分段，需要有一種將邏輯日志偏移量（或日志序列號(hào)）映射到日志段文件的簡單方法。

這個(gè)其實(shí)也非常常見，比如我們實(shí)際業(yè)務(wù)應(yīng)用配置的log，一般都是按天、固定大小進(jìn)行拆分，并不會(huì)把所有的日志都放在一個(gè)日志文件中

再比如es的分段存儲(chǔ)，一個(gè)段就是一個(gè)小的存儲(chǔ)文件

4.12 checksum校驗(yàn)

在分布式系統(tǒng)中，在組件之間移動(dòng)數(shù)據(jù)時(shí)，從節(jié)點(diǎn)獲取的數(shù)據(jù)可能會(huì)損壞。

計(jì)算校驗(yàn)和并將其與數(shù)據(jù)一起存儲(chǔ)。

要計(jì)算校驗(yàn)和，請(qǐng)使用 MD5、SHA-1、SHA-256 或 SHA-512 等加密哈希函數(shù)。哈希函數(shù)獲取輸入數(shù)據(jù)并生成固定長度的字符串（包含字母和數(shù)字）;此字符串稱為校驗(yàn)和。

當(dāng)系統(tǒng)存儲(chǔ)某些數(shù)據(jù)時(shí)，它會(huì)計(jì)算數(shù)據(jù)的校驗(yàn)和，并將校驗(yàn)和與數(shù)據(jù)一起存儲(chǔ)。當(dāng)客戶端檢索數(shù)據(jù)時(shí)，它會(huì)驗(yàn)證從服務(wù)器接收的數(shù)據(jù)是否與存儲(chǔ)的校驗(yàn)和匹配。如果沒有，則客戶端可以選擇從另一個(gè)副本檢索該數(shù)據(jù)。

HDFS和Chubby將每個(gè)文件的校驗(yàn)和與數(shù)據(jù)一起存儲(chǔ)。

4.13 一灰灰的小結(jié)

這一節(jié)很多內(nèi)容來自下面這篇博文，推薦有興趣的小伙伴查看原文

?Distributed System Design Patterns | by Nishant | Medium^[16]

這一節(jié)主要簡單的介紹了下分布式系統(tǒng)中應(yīng)用到的一些技術(shù)方案，如有對(duì)其中某個(gè)技術(shù)有興趣的小伙伴可以留言，后續(xù)會(huì)逐一進(jìn)行補(bǔ)全

5.分布式系統(tǒng)解決方案

最后再介紹一些常見的分布式業(yè)務(wù)場景及對(duì)應(yīng)的解決方案，比如全局唯一的遞增ID-雪花算法，分布式系統(tǒng)的資源搶占-分布式鎖，分布式事務(wù)-2pc/3pc/tcc ，分布式緩存等

5.1 緩存

緩存實(shí)際上并不是分布式獨(dú)有的，這里把它加進(jìn)來，主要是因?yàn)閷?shí)在是應(yīng)用得太廣了，無論是應(yīng)用服務(wù)、基礎(chǔ)軟件工具還是操作系統(tǒng)，大量都可以見到緩存的身影

緩存的核心思想在于：借助更高效的IO方式，來替代代價(jià)昂貴的IO方式

如：

?redis的性能高于mysql?如內(nèi)存的讀寫，遠(yuǎn)高于磁盤IO，文件IO?磁盤順序讀寫 > 隨機(jī)讀寫

用好緩存可以有效提高應(yīng)用性能，下面以一個(gè)普通的java前臺(tái)應(yīng)用為例說明

?JVM緩存 -> 分布式緩存(redis/memcache) -> mysql緩存 -> 操作系統(tǒng)文件緩存 -> 磁盤文件

緩存面臨的核心問題，則在于

?一致性問題：緩存與db的一致性如何保障（相信大家都聽說過或者實(shí)際處理過這種問題）?數(shù)據(jù)完整性：比如常見的先寫緩存，異步刷新到磁盤，那么緩存到磁盤刷新這段時(shí)間內(nèi)，若宕機(jī)導(dǎo)致數(shù)據(jù)丟失怎么辦？?TIP: 上面這個(gè)問題可以參考mysql的redolog

5.2 全局唯一ID

在傳統(tǒng)的單體架構(gòu)中，業(yè)務(wù)id基本上是依賴于數(shù)據(jù)庫的自增id來處理；當(dāng)我們進(jìn)入分布式場景時(shí)，如我們常說的分庫分表時(shí)，就需要我們來考慮如何實(shí)現(xiàn)全局唯一的業(yè)務(wù)id了，避免出現(xiàn)在分表中出現(xiàn)沖突

全局唯一ID解決方案：

?uuid?數(shù)據(jù)庫自增id表?redis原子自增命令?雪花算法 (原生的，擴(kuò)展的百度UidGenerator, 美團(tuán)Leaf等)?Mist 薄霧算法

5.3 分布式鎖

常用于分布式系統(tǒng)中資源控制，只有持有鎖的才能繼續(xù)操作，確保同一時(shí)刻只會(huì)有一個(gè)實(shí)例訪問這個(gè)資源

常見的分布式鎖有

?基于數(shù)據(jù)庫實(shí)現(xiàn)分布式鎖?Redis實(shí)現(xiàn)分布式鎖（應(yīng)用篇） | 一灰灰Learning^[17]?從0到1實(shí)現(xiàn)一個(gè)分布式鎖 | 一灰灰Learning^[18]?etcd實(shí)現(xiàn)分布式鎖?基于consul實(shí)現(xiàn)分布式鎖

5.4 分布式事務(wù)

事務(wù)表示一組操作，要么全部成功，要么全部不成功；單機(jī)事務(wù)通常說的是數(shù)據(jù)庫的事務(wù)；而分布式事務(wù)，則可以簡單理解為多個(gè)數(shù)據(jù)庫的操作，要么同時(shí)成功，要么全部不成功

更確切一點(diǎn)的說法，分布式事務(wù)主要是要求事務(wù)的參與方，可能涉及到多個(gè)系統(tǒng)、多個(gè)數(shù)據(jù)資源，要求它們的操作要么都成功，要么都回滾；

一個(gè)簡單的例子描述下分布式事務(wù)場景：

下單扣庫存

?用戶下單，付錢?此時(shí)訂單服務(wù)，會(huì)生成訂單信息?支付網(wǎng)關(guān)，會(huì)記錄付款信息，成功or失敗?庫存服務(wù)，扣減對(duì)應(yīng)的庫存

一個(gè)下單支付操作，涉及到三個(gè)系統(tǒng)，而分布式事務(wù)則是要求，若支付成功，則上面三個(gè)系統(tǒng)都應(yīng)該更新成功；若有一個(gè)操作失敗，如支付失敗，則已經(jīng)扣了庫存的要回滾（還庫存），生成的訂單信息回滾（刪掉--注：現(xiàn)實(shí)中并不會(huì)去刪除訂單信息，這里只是用于說明分布式事務(wù)，請(qǐng)勿帶入實(shí)際的實(shí)現(xiàn)方案）

分布式事務(wù)實(shí)現(xiàn)方案：

?2PC: 前面說的兩階段提交，就是實(shí)現(xiàn)分布式事務(wù)的一個(gè)經(jīng)典解決方案?3PC: 三階段提交?TCC：補(bǔ)償事務(wù)，簡單理解為應(yīng)用層面的2PC?SAGA事務(wù)?本地消息表?MQ事務(wù)方案

5.5 分布式任務(wù)

分布式任務(wù)相比于我們常說單機(jī)的定時(shí)任務(wù)而言，可以簡單的理解為多臺(tái)實(shí)例上的定時(shí)任務(wù)，從應(yīng)用場景來說，可以區(qū)分兩種

?互斥性的分布式任務(wù)?即同一時(shí)刻，集群內(nèi)只能有一個(gè)實(shí)例執(zhí)行這個(gè)任務(wù)?并存式的分布式任務(wù)?同一時(shí)刻，所有的實(shí)例都可以執(zhí)行這個(gè)任務(wù)?續(xù)考慮如何避免多個(gè)任務(wù)操作相同的資源

分布式任務(wù)實(shí)現(xiàn)方案：

?Quartz Cluster?XXL-Job?Elastic-Job?自研：?資源分片策略?分布式鎖控制的唯一任務(wù)執(zhí)行策略

5.6 分布式Session

Session一般叫做會(huì)話，Session技術(shù)是http狀態(tài)保持在服務(wù)端的解決方案，它是通過服務(wù)器來保持狀態(tài)的。我們可以把客戶端瀏覽器與服務(wù)器之間一系列交互的動(dòng)作稱為一個(gè) Session。是服務(wù)器端為客戶端所開辟的存儲(chǔ)空間，在其中保存的信息就是用于保持狀態(tài)。因此，session是解決http協(xié)議無狀態(tài)問題的服務(wù)端解決方案，它能讓客戶端和服務(wù)端一系列交互動(dòng)作變成一個(gè)完整的事務(wù)。

單機(jī)基于session/cookie來實(shí)現(xiàn)用戶認(rèn)證，那么在分布式系統(tǒng)的多實(shí)例之間，如何驗(yàn)證用戶身份呢？這個(gè)就是我們說的分布式session

分布式session實(shí)現(xiàn)方案：

?session stick：客戶端每次請(qǐng)求都轉(zhuǎn)發(fā)到同一臺(tái)服務(wù)器(如基于ip的hash路由轉(zhuǎn)發(fā)策略）?session復(fù)制: session生成之后，主動(dòng)同步給其他服務(wù)器?session集中保存：用戶信息統(tǒng)一存儲(chǔ)，每次需要時(shí)統(tǒng)一從這里取(也就是常說的redis實(shí)現(xiàn)分布式session方案)?cookie: 使用客戶端cookie存儲(chǔ)session數(shù)據(jù)，每次請(qǐng)求時(shí)攜帶這個(gè)

5.7 分布式鏈路追蹤

分布式鏈路追蹤也可以叫做全鏈路追中，而它可以說是每個(gè)開發(fā)者的福音，通常指的是一次前端的請(qǐng)求，將這個(gè)請(qǐng)求過程中，所有涉及到的系統(tǒng)、鏈路都串聯(lián)起來，可以清晰的知道這一次請(qǐng)求中，調(diào)用了哪些服務(wù)，有哪些IO交互，瓶頸點(diǎn)在哪里，什么地方拋出了異常

當(dāng)前主流的全鏈路方案大多是基于google的??Dapper?? 論文實(shí)現(xiàn)的

全鏈路實(shí)現(xiàn)方案

?zipkin?pinpoint?SkyWalking?CAT?jaeger

5.8 布隆過濾器

Bloom過濾器是一種節(jié)省空間的概率數(shù)據(jù)結(jié)構(gòu)，用于測試元素是否為某集合的成員。

布隆過濾器由一個(gè)長度為 m 比特的位數(shù)組（bit array）與 k 個(gè)哈希函數(shù)（hash function）組成的數(shù)據(jù)結(jié)構(gòu)。

原理是當(dāng)一個(gè)元素被加入集合時(shí)，通過 K 個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的 K 個(gè)點(diǎn)，把它們置為 1。

檢索時(shí)，我們只要看看這些點(diǎn)是不是都是 1 就大約知道集合中有沒有它了，也就是說，如果這些點(diǎn)有任何一個(gè) 0 ，則被檢元素一定不在；如果都是 1 ，則被檢元素很可能在。

關(guān)于布隆過濾器，請(qǐng)牢記一點(diǎn)

?判定命中的，不一定真的命中?判定沒有命中的，則一定不在里面

布隆過濾器

常見的應(yīng)用場景，如

?防止緩存穿透?爬蟲時(shí)重復(fù)檢測

5.9 一灰灰的小結(jié)

分布式系統(tǒng)的解決方案當(dāng)然不局限于上面幾種，比如分布式存儲(chǔ)、分布式計(jì)算等也屬于常見的場景，當(dāng)然在我們實(shí)際的業(yè)務(wù)支持過程中，不太可能需要讓我們自己來支撐這種大活；而上面提到的幾個(gè)點(diǎn)，基本上或多或少會(huì)與我們?nèi)粘９ぷ飨嚓P(guān)，這里列出來當(dāng)然是好為了后續(xù)的詳情做鋪墊

6.一灰灰的總結(jié)

6.1 綜述

這是一篇概括性的綜述類文章，可能并沒有很多的干貨，當(dāng)然也限于“一灰灰”我個(gè)人的能力，上面的總結(jié)可能并不準(zhǔn)確，如有發(fā)現(xiàn)，請(qǐng)不吝賜教

全文總結(jié)如下

常見的分布式架構(gòu)設(shè)計(jì)方案：

?主備，主從，多主多從，普通無中心集群，數(shù)據(jù)分片架構(gòu)

分布式系統(tǒng)中的理論基石：

?CAP， BASE, PACELEC?共識(shí)算法：paxos, raft, zab?一致性協(xié)議：2pc, 3pc?數(shù)據(jù)同步：gossip

分布式系統(tǒng)中的算法：

?分區(qū)的一致性hash算法: 基于hash環(huán)，減少節(jié)點(diǎn)動(dòng)態(tài)增加減少對(duì)整個(gè)集群的影響；適用于數(shù)據(jù)分片的場景?適用于一致性的Quorum NWR算法: 投票算法，定義如何就一個(gè)提案達(dá)成共識(shí)?PBFT拜占庭容錯(cuò)算法: 適用于集群中節(jié)點(diǎn)故障、或者不可信的場景?區(qū)塊鏈中大量使用的工作量證明PoW算法: 通過工作量證明，認(rèn)可節(jié)點(diǎn)的提交

分布式系統(tǒng)解決方案：

?分布式緩存?全局唯一ID?分布式鎖?分布式事務(wù)?分布式任務(wù)?分布式會(huì)話?分布式鏈路追蹤?布隆過濾器

6.2 題外話

最后總結(jié)一下這篇耗時(shí)兩周寫完的“心血巨作”（有點(diǎn)自吹了哈），準(zhǔn)備這篇文章確實(shí)花了很大的精力，首先我個(gè)人對(duì)于分布式這塊的理解并不能算深刻，其次分布式這塊的理論+實(shí)踐知識(shí)特別多，而且并不是特別容易上手理解，在輸出這篇文章的同時(shí)，遇到一些疑問點(diǎn)我也會(huì)去查閱相關(guān)資料去確認(rèn)，整個(gè)過程并不算特別順利；那么為什么還要去做這個(gè)事情呢？

1.咸魚太久了，想做一些有意思的東西，活躍一下大腦2.準(zhǔn)備依托于《分布式專欄》來將自己的知識(shí)體系進(jìn)行歸納匯總，讓零散分布在大腦中的知識(shí)點(diǎn)能有一個(gè)脈絡(luò)串聯(lián)起來3.不想做架構(gòu)的碼農(nóng)不是好碼農(nóng)，而想成為一個(gè)好的架構(gòu)，當(dāng)然得做一些基礎(chǔ)準(zhǔn)備，向業(yè)務(wù)精品學(xué)習(xí)取經(jīng)