1.CAP原理

要想數(shù)據(jù)高可用，就得寫多份數(shù)據(jù)

寫多分?jǐn)?shù)據(jù)就會(huì)導(dǎo)致數(shù)據(jù)一致性問(wèn)題

數(shù)據(jù)一致性問(wèn)題會(huì)引起性能問(wèn)題

2.一致性模型

弱一致性

最終一致性（一段時(shí)間達(dá)到一致性）

強(qiáng)一致

1吠卷、2 異步冗余；3是同步冗余

3. 擴(kuò)展服務(wù)的方案

數(shù)據(jù)分區(qū)： uid % 16

數(shù)據(jù)鏡像：讓多有的服務(wù)器都有相同的數(shù)據(jù)破镰，提供相當(dāng)?shù)姆?wù)（冗余存儲(chǔ)，一般3份為好）

4.兩種方案的事務(wù)問(wèn)題

A向B匯錢压储，兩個(gè)用戶不在一個(gè)服務(wù)器上

鏡像：在不同的服務(wù)器上對(duì)同一數(shù)據(jù)的寫操作如何保證一致性鲜漩。

image

5. 解決一致性事務(wù)問(wèn)題的技術(shù)

1. Master -Slave

讀寫請(qǐng)求由Master負(fù)責(zé)

寫請(qǐng)求寫到Master后，由Master同步到Slave上

由Master push or Slave pull

通常是由Slave 周期性來(lái)pull集惋，所以是最終一致性

問(wèn)題： 若在 pull 周期內(nèi)（不是期間孕似？），master掛掉刮刑，那么會(huì)導(dǎo)致這個(gè)時(shí)間片內(nèi)的數(shù)據(jù)丟失

若不想讓數(shù)據(jù)丟掉喉祭，Slave 只能成為 ReadOnly方式等Master恢復(fù)

若容忍數(shù)據(jù)丟失，可以讓 Slave代替Master工作

如何保證強(qiáng)一致性为朋？

Master 寫操作臂拓，寫完成功后，再寫 Slave习寸，兩者成功后返回成功。若 Slave失敗傻工，兩種方法

標(biāo)記 Slave 不可用報(bào)錯(cuò)霞溪，并繼續(xù)服務(wù)（等恢復(fù)后，再同步Master的數(shù)據(jù)中捆，多個(gè)Slave少了一個(gè)而已）

回滾自己并返回失敗

2. Master-Master

數(shù)據(jù)同步一般是通過(guò) Master 間的異步完成鸯匹，所以是最終一致

好處： 一臺(tái)Master掛掉，另外一臺(tái)照樣可以提供讀寫服務(wù)泄伪。當(dāng)數(shù)據(jù)沒(méi)有被賦值到別的Master上時(shí)殴蓬，數(shù)據(jù)會(huì)丟失。

對(duì)同一數(shù)據(jù)的處理問(wèn)題：Dynamo的Vector Clock的設(shè)計(jì)（記錄數(shù)據(jù)的版本號(hào)和修改者）蟋滴，當(dāng)數(shù)據(jù)發(fā)生沖突時(shí)染厅，要開(kāi)發(fā)者自己來(lái)處理

3.兩階段提交 Two Phase Commit _ 2PC

第一階段：針對(duì)準(zhǔn)備工作

協(xié)調(diào)者問(wèn)所有節(jié)點(diǎn)是否可以執(zhí)行提交

參與者開(kāi)始事務(wù)，執(zhí)行準(zhǔn)備工作：鎖定資源（獲取鎖操作）

參與者響應(yīng)協(xié)調(diào)者津函，如果事務(wù)的準(zhǔn)備工作成功肖粮，則回應(yīng)"可以提交"，否則尔苦，拒絕提交

第二階段：

若都響應(yīng)可以提交涩馆，則協(xié)調(diào)者項(xiàng)多有參與者發(fā)送正式提交的命令（更新值）行施，參與者完成正式提交，釋放資源魂那，回應(yīng)完成蛾号。協(xié)調(diào)者收到所有節(jié)點(diǎn)的完成響應(yīng)后結(jié)束這個(gè)全局事務(wù).。若參與者回應(yīng)拒絕提交涯雅，則協(xié)調(diào)者向所有的參與者發(fā)送回滾操作鲜结，并釋放資源，當(dāng)收到全部節(jié)點(diǎn)的回滾回應(yīng)后斩芭，取消全局事務(wù)

存在的問(wèn)題：若一個(gè)沒(méi)提交轻腺，就會(huì)進(jìn)行回滾

第一階段：若消息的傳遞未接收到，則需要協(xié)調(diào)者作超時(shí)處理划乖，要么當(dāng)做失敗贬养，要么重載

第二階段：若參與者的回應(yīng)超時(shí)，要么重試琴庵，要么把那個(gè)參與者即為問(wèn)題節(jié)點(diǎn)误算，提出整個(gè)集群

在第二階段中，參與者未收到協(xié)調(diào)者的指示（也許協(xié)調(diào)者掛掉）迷殿，則所有參與者會(huì)進(jìn)入“不知所措” 的狀態(tài)（但是已經(jīng)鎖定了資源）儿礼，所以引入了三段提交

4. 三段提交：把二段提交的第一階段 break 成了兩段

詢問(wèn)

鎖定資源（獲取鎖）

提交

核心理念：在詢問(wèn)的時(shí)候并不鎖定資源，除非所有人都同意了庆寺，才開(kāi)始鎖定

好處：當(dāng)發(fā)生了失敗或超時(shí)時(shí)蚊夫，三段提交可以繼續(xù)把狀態(tài)變?yōu)镃ommit 狀態(tài)，而二段提交則不知所措懦尝？

5. Raxos 算法（少數(shù)服從多數(shù)）

解決的問(wèn)題：在一個(gè)可能發(fā)生異常的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致知纷，讓整個(gè)集群的節(jié)點(diǎn)對(duì)某個(gè)值的變更達(dá)成一致

任何一個(gè)節(jié)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案,是否通過(guò)這個(gè)提案取決于這個(gè)集群中是否有超過(guò)半數(shù)的節(jié)點(diǎn)同意（所以節(jié)點(diǎn)數(shù)總是單數(shù)）—— 版本標(biāo)記。雖然一致性陵霉，但是只能對(duì)一個(gè)操作進(jìn)行操作袄旁？踊挠？

當(dāng)一個(gè)Server接收到比當(dāng)前版本號(hào)小的提案時(shí)乍桂，則拒絕。當(dāng)收到比當(dāng)前大的版本號(hào)的提案時(shí)效床，則鎖定資源睹酌，進(jìn)行修改，返回OK. 也就是說(shuō)收到超過(guò)一半的最大版本的提案才算成功扁凛。

核心思想：

在搶占式訪問(wèn)權(quán)的基礎(chǔ)上引入多個(gè)acceptor忍疾，也就是說(shuō)當(dāng)一個(gè)版本號(hào)更大的提案可以剝奪版本號(hào)已經(jīng)獲取的鎖。

后者認(rèn)同前者的原則：

在肯定舊epoch 無(wú)法生成確定性取值時(shí)谨朝，新的 epoch 會(huì)提交自己的valu

一旦 舊epoch形成確定性取值卤妒，新的 epoch肯定可以獲取到此取值甥绿，并且會(huì)認(rèn)同此取值，不會(huì)被破壞则披。

步驟

P1 請(qǐng)求Acceptor的 #1,Acceptor 這時(shí)并沒(méi)有其他線程獲取到鎖共缕，所以把鎖交給 P1，并返回這時(shí) #1 的值為null

image

然后 P1 向 第一個(gè) Acceptor 提交 #1 的值士复，Acceptor 接受并返回 OK

image

這個(gè)時(shí)候图谷，P2向Acceptor請(qǐng)求#1上的鎖，因?yàn)榘姹咎?hào)更大阱洪，所以直接搶占了 P1 的鎖便贵。這時(shí) Acceptor 返回了 OK并且返回了 #1 的值

image

這時(shí) P1 P向 后面兩個(gè) Acceptor 提交 #1 的值，但是由于中間的那個(gè)Acceptor 版本號(hào)已經(jīng)更改為 2 了冗荸，所以拒絕P1承璃。第三個(gè) Acceptor 接受了，并且返回了 OK

image

由于后者認(rèn)同前者的原則蚌本，這時(shí) P1 已經(jīng)形成確定性取值了 V1 了盔粹，這時(shí)新的 P2 會(huì)認(rèn)同此取值，而不是提交自己的取值程癌。所以舷嗡，P2會(huì)選擇最新的那個(gè)取值 也就是V1 進(jìn)行提交。這時(shí)Acceptor 返回 OK

image

6.ZAB 協(xié)議 ( Zookeeper Atomic Broadcast) 原子廣播協(xié)議：保證了發(fā)給各副本的消息順序相同

定義：原子廣播協(xié)議 ZAB 是一致性協(xié)議嵌莉，Zookeeper 把其作為數(shù)據(jù)一致性的算法进萄。ZAB 是在 Paxos 算法基礎(chǔ)上進(jìn)行擴(kuò)展而來(lái)的。Zookeeper 使用單一主進(jìn)程 Leader用于處理客戶端所有事務(wù)請(qǐng)求锐峭，采用 ZAB 協(xié)議將服務(wù)器狀態(tài)以事務(wù)形式廣播到所有 Follower 上垮斯，由于事務(wù)間可能存在著依賴關(guān)系，ZAB協(xié)議保證 Leader 廣播的變更序列被順序的處理只祠，一個(gè)狀態(tài)被處理那么它所依賴的狀態(tài)也已經(jīng)提前被處理

核心思想：保證任意時(shí)刻只有一個(gè)節(jié)點(diǎn)是Leader，所有更新事務(wù)由Leader發(fā)起去更新所有副本 Follower扰肌，更新時(shí)用的是 兩段提交協(xié)議抛寝，只要多數(shù)節(jié)點(diǎn) prepare 成功，就通知他們commit曙旭。各個(gè)follower 要按當(dāng)初 leader 讓他們 prepare 的順序來(lái) apply 事務(wù)

協(xié)議狀態(tài)

Looking:系統(tǒng)剛啟動(dòng)時(shí) 或者 Leader 崩潰后正處于選舉狀態(tài)

Following：Follower 節(jié)點(diǎn)所處的狀態(tài)盗舰，F(xiàn)ollower與 Leader處于數(shù)據(jù)同步狀態(tài)

Leading：Leader 所處狀態(tài)，當(dāng)前集群中有一個(gè) Leader 為主進(jìn)程

ZooKeeper啟動(dòng)時(shí)所有節(jié)點(diǎn)初始狀態(tài)為L(zhǎng)ooking桂躏，這時(shí)集群會(huì)嘗試選舉出一個(gè)Leader節(jié)點(diǎn)钻趋，選舉出的Leader節(jié)點(diǎn)切換為L(zhǎng)eading狀態(tài)；當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)集群中已經(jīng)選舉出Leader則該節(jié)點(diǎn)會(huì)切換到Following狀態(tài)剂习，然后和Leader節(jié)點(diǎn)保持同步蛮位；當(dāng)Follower節(jié)點(diǎn)與Leader失去聯(lián)系時(shí)Follower節(jié)點(diǎn)則會(huì)切換到Looking狀態(tài)较沪，開(kāi)始新一輪選舉；在ZooKeeper的整個(gè)生命周期中每個(gè)節(jié)點(diǎn)都會(huì)在Looking失仁、Following尸曼、Leading狀態(tài)間不斷轉(zhuǎn)換。

image

選舉出Leader節(jié)點(diǎn)后 ZAB 進(jìn)入原子廣播階段萄焦，這時(shí)Leader為和自己同步每個(gè)節(jié)點(diǎn) Follower 創(chuàng)建一個(gè)操作序列控轿，一個(gè)時(shí)期一個(gè) Follower 只能和一個(gè)Leader保持同步

階段

Election： 在 Looking狀態(tài)中選舉出 Leader節(jié)點(diǎn)，Leader的LastZXID總是最新的（只有l(wèi)astZXID的節(jié)點(diǎn)才有資格成為L(zhǎng)eade,這種情況下選舉出來(lái)的Leader總有最新的事務(wù)日志）拂封。在選舉的過(guò)程中會(huì)對(duì)每個(gè)Follower節(jié)點(diǎn)的ZXID進(jìn)行對(duì)比只有highestZXID的Follower才可能當(dāng)選Leader

每個(gè)Follower都向其他節(jié)點(diǎn)發(fā)送選自身為L(zhǎng)eader的Vote投票請(qǐng)求茬射，等待回復(fù)；

Follower接受到的Vote如果比自身的大（ZXID更新）時(shí)則投票冒签，并更新自身的Vote在抛，否則拒絕投票；

每個(gè)Follower中維護(hù)著一個(gè)投票記錄表镣衡，當(dāng)某個(gè)節(jié)點(diǎn)收到過(guò)半的投票時(shí)霜定，結(jié)束投票并把該Follower選為L(zhǎng)eader，投票結(jié)束廊鸥；

Discovery:Follower 節(jié)點(diǎn)向準(zhǔn) Leader推送 FollwerInfo,該信息包含了上一周期的epoch望浩，接受準(zhǔn) Leader 的 NEWLEADER 指令

Sync：將 Follower 與 Leader的數(shù)據(jù)進(jìn)行同步，由Leader發(fā)起同步指令惰说，最終保持?jǐn)?shù)據(jù)的一致性

Broadcast：Leader廣播 Proposal 與 Commit磨德，F(xiàn)ollower 接受 Proposal 與 commit。因?yàn)橐粋€(gè)時(shí)刻只有一個(gè)Leader節(jié)點(diǎn)吆视，若是更新請(qǐng)求典挑，只能由Leader節(jié)點(diǎn)執(zhí)行（若連到的是 Follower 節(jié)點(diǎn)，則需轉(zhuǎn)發(fā)到Leader節(jié)點(diǎn)執(zhí)行啦吧；讀請(qǐng)求可以從Follower 上讀取您觉，若是要最新的數(shù)據(jù)，則還是需要在 Leader上讀仁谧摇）

消息廣播使用了TCP協(xié)議進(jìn)行通訊所有保證了接受和發(fā)送事務(wù)的順序性琳水。廣播消息時(shí)Leader節(jié)點(diǎn)為每個(gè)事務(wù)Proposal分配一個(gè)全局遞增的ZXID（事務(wù)ID），每個(gè)事務(wù)Proposal都按照Z(yǔ)XID順序來(lái)處理（Paxos 保證不了）

Leader節(jié)點(diǎn)為每一個(gè)Follower節(jié)點(diǎn)分配一個(gè)隊(duì)列按事務(wù)ZXID順序放入到隊(duì)列中般堆，且根據(jù)隊(duì)列的規(guī)則FIFO來(lái)進(jìn)行事務(wù)的發(fā)送在孝。

Recovery ：根據(jù)Leader的事務(wù)日志對(duì)Follower 節(jié)點(diǎn)數(shù)據(jù)進(jìn)行同步更新

同步策略：

SNAP ：如果Follower數(shù)據(jù)太老，Leader將發(fā)送快照SNAP指令給Follower同步數(shù)據(jù)淮摔；

DIFF ：Leader發(fā)送從Follolwer.lastZXID到Leader.lastZXID議案的DIFF指令給Follower同步數(shù)據(jù)私沮；

TRUNC ：當(dāng)Follower.lastZXID比Leader.lastZXID大時(shí)，Leader發(fā)送從Leader.lastZXID到Follower.lastZXID的TRUNC指令讓Follower丟棄該段數(shù)據(jù)和橙；（當(dāng)老Leader在Commit前掛掉仔燕，但是已提交到本地）

Follower將所有事務(wù)都同步完成后Leader會(huì)把該節(jié)點(diǎn)添加到可用Follower列表中造垛；

Follower接收Leader的NEWLEADER指令，如果該指令中epoch比當(dāng)前Follower的epoch小那么Follower轉(zhuǎn)到Election階段

7. Raft 算法

Raft 算法也是一種少數(shù)服從多數(shù)的算法涨享，在任何時(shí)候一個(gè)服務(wù)器可以扮演以下角色之一：

Leader：負(fù)責(zé) Client 交互 和 log 復(fù)制筋搏，同一時(shí)刻系統(tǒng)中最多存在一個(gè)

Follower：被動(dòng)響應(yīng)請(qǐng)求 RPC，從不主動(dòng)發(fā)起請(qǐng)求 RPC

Candidate : 由Follower 向Leader轉(zhuǎn)換的中間狀態(tài)

在選舉Leader的過(guò)程中厕隧，是有時(shí)間限制的奔脐，raft 將時(shí)間分為一個(gè)個(gè) Term，可以認(rèn)為是“邏輯時(shí)間”：

每個(gè) Term中至多存在1個(gè) Leader

某些 Term由于不止一個(gè)得到的票數(shù)一樣吁讨，就會(huì)選舉失敗髓迎，不存在Leader。則會(huì)出現(xiàn) Split Vote 建丧，再由候選者發(fā)出邀票

每個(gè) Server 本地維護(hù) currentTerm

image

選舉過(guò)程：

自增 CurrentTerm排龄，由Follower 轉(zhuǎn)換為 Candidate，設(shè)置 votedFor 為自身翎朱，并行發(fā)起 RequestVote RPC,不斷重試橄维，直至滿足下列條件之一為止：

獲得超過(guò)半數(shù)的Server的投票，轉(zhuǎn)換為 Leader拴曲，廣播 HeatBeat

接收到 合法 Leader 的 AppendEnties RPC争舞，轉(zhuǎn)換為Follower

選舉超時(shí)，沒(méi)有 Server選舉成功澈灼，自增 currentTerm ,重新選舉

當(dāng)Candidate 在等待投票結(jié)果的過(guò)程中竞川，可能會(huì)接收到來(lái)自其他Leader的 AppendEntries RPC ,如果該 Leader 的 Term 不小于本地的 Current Term，則認(rèn)可該Leader身份的合法性叁熔，主動(dòng)降級(jí)為Follower委乌，反之，則維持 candida 身份繼續(xù)等待投票結(jié)果

Candidate 既沒(méi)有選舉成功荣回，也沒(méi)有收到其他 Leader 的 RPC (多個(gè)節(jié)點(diǎn)同時(shí)發(fā)起選舉遭贸，最終每個(gè) Candidate都將超時(shí))，為了減少?zèng)_突心软，采取隨機(jī)退讓策略革砸，每個(gè) Candidate 重啟選舉定時(shí)器

日志更新問(wèn)題：

如果在日志復(fù)制過(guò)程中，發(fā)生了網(wǎng)絡(luò)分區(qū)或者網(wǎng)絡(luò)通信故障糯累，使得Leader不能訪問(wèn)大多數(shù)Follwers了，那么Leader只能正常更新它能訪問(wèn)的那些Follower服務(wù)器册踩，而大多數(shù)的服務(wù)器Follower因?yàn)闆](méi)有了Leader泳姐，他們重新選舉一個(gè)候選者作為L(zhǎng)eader，然后這個(gè)Leader作為代表于外界打交道暂吉，如果外界要求其添加新的日志胖秒，這個(gè)新的Leader就按上述步驟通知大多數(shù)Followers缎患，如果這時(shí)網(wǎng)絡(luò)故障修復(fù)了，那么原先的Leader就變成Follower阎肝，在失聯(lián)階段這個(gè)老Leader的任何更新都不能算commit挤渔，都回滾，接受新的Leader的新的更新风题。

流程：

Client 發(fā)送command 命令給 Leader

Leader追加日志項(xiàng)判导，等待 commit 更新本地狀態(tài)機(jī)，最終響應(yīng) Client

若 Client超時(shí)沛硅，則不斷重試眼刃，直到收到響應(yīng)為止（重發(fā) command，可能被執(zhí)行多次摇肌，在被執(zhí)行但是由于網(wǎng)絡(luò)通信問(wèn)題未收到響應(yīng)）

解決辦法：Client 賦予每個(gè) Command唯一標(biāo)識(shí)擂红，Leader在接收 command 之前首先檢查本地log

9. paxos 算法與 raft 算法的差異

raft強(qiáng)調(diào)是唯一leader的協(xié)議，此leader至高無(wú)上

raft：新選舉出來(lái)的leader擁有全部提交的日志围小，而 paxos 需要額外的流程從其他節(jié)點(diǎn)獲取已經(jīng)被提交的日志昵骤，它允許日志有空洞

相同點(diǎn)：得到大多數(shù)的贊成，這個(gè) entries 就會(huì)定下來(lái)肯适，最終所有節(jié)點(diǎn)都會(huì)贊成

NWR模型

N： N個(gè)備份

W：要寫入至少 w 份才認(rèn)為成功

R : 至少讀取 R 個(gè)備份

W+ R > N ——> R > N - W(未更新成功的) 变秦，代表每次讀取，都至少讀取到一個(gè)最新的版本（更新成功的）疹娶，從而不會(huì)讀到一份舊數(shù)據(jù)

問(wèn)題：并非強(qiáng)一致性伴栓，會(huì)出現(xiàn)一些節(jié)點(diǎn)上的數(shù)據(jù)并不是最新版本，但卻進(jìn)行了最新的操作

版本沖突問(wèn)題：矢量鐘 Vector Clock ： 誰(shuí)更新的我雨饺，我的版本號(hào)是什么（對(duì)于同一個(gè)操作者的同一操作钳垮，版本號(hào)遞增）