整理下分布式系統(tǒng)問(wèn)題的答案(1)

分布式系統(tǒng)主要為了解決集中式系統(tǒng)的性能瓶頸，支持高并發(fā)及海量數(shù)據(jù)處理，需要做到高可擴(kuò)展性、高可用、服務(wù)和存儲(chǔ)無(wú)狀態(tài)。

分布式系統(tǒng)中經(jīng)常會(huì)出現(xiàn)網(wǎng)絡(luò)故障、通信失敗、數(shù)據(jù)不一致等問(wèn)題，為此提出了 CAP 理論：一個(gè)分布式系統(tǒng)最多只能同時(shí)滿足一致性（Consistency）、可用性（Availability）和分區(qū)容忍性（Partition Tolerance）這三項(xiàng)中的兩項(xiàng)。

C：所有節(jié)點(diǎn)同時(shí)看到相同的數(shù)據(jù)
A：任何時(shí)候，讀寫(xiě)都是成功的
P：當(dāng)部分節(jié)點(diǎn)出現(xiàn)消息丟失或者分區(qū)故障時(shí)，分布式系統(tǒng)仍然能夠繼續(xù)運(yùn)行

分布式系統(tǒng)中 P 基本是必需，所以 CAP 模型的應(yīng)用的一般是 CP 或 AP 架構(gòu)。

用反證法理解 CAP 最為簡(jiǎn)單與直接，假設(shè)分布式系統(tǒng)滿足了分區(qū)容錯(cuò)，
client1 寫(xiě)入x=1成功 -> server1(x=1) <- client2讀x=1

client3 寫(xiě)入x=1失敗 -> server2(x=0) <- client4讀x=0
為了提高一致性，就要回滾 server1 -> x = 0，降低了可用性；
為了提高可用性，就要降低對(duì)一致性的要求，server1 x=1,server2 x=0。

其他場(chǎng)景證明類似。

CAP 理論是絕對(duì)情況，工程上一般關(guān)注相對(duì)一致的情況下，提高系統(tǒng)的可用性，所以就有了對(duì)一致性和可用性的取舍。

ZooKeeper 就為了解決應(yīng)用系統(tǒng)的協(xié)調(diào)和一致性問(wèn)題的框架，屬于 CP 架構(gòu)，其核心算法就是 Zab，來(lái)保證一致性。

AP 架構(gòu)放棄強(qiáng)一致性，保證分區(qū)容錯(cuò)和可用性，Base 理論就是從 AP 擴(kuò)展而來(lái)；Spring Cloud 中的 Eureka 屬于 AP 架構(gòu)，Eureka 的各個(gè)節(jié)點(diǎn)平等，幾個(gè)節(jié)點(diǎn)掛掉不影響正常節(jié)點(diǎn)的工作，只要還有一個(gè) Eureka 節(jié)點(diǎn)，就能保證注冊(cè)服務(wù)可用，但查到的信息可能不是最新的版本，不保證數(shù)據(jù)一致性。

放棄 CAP 理論中的強(qiáng)一致性，提出 Base 理論：
無(wú)法做到強(qiáng)一致性（Strong Consistency），但每個(gè)應(yīng)用都可以根據(jù)自身的業(yè)務(wù)特點(diǎn)，采用適當(dāng)?shù)姆绞絹?lái)使系統(tǒng)達(dá)到最終一致性（Eventual Consistency）。

Base 這個(gè)單詞來(lái)自于，基本可用（Basically Available）、軟狀態(tài)（Soft State）和最終一致性（Eventually Consistent）。

Base 理論是從 CAP 發(fā)展而來(lái)、在分區(qū)和副本存在的前提下，通過(guò)系統(tǒng)設(shè)計(jì)方案，放棄強(qiáng)一致性，實(shí)現(xiàn)基本可用、最終一致。

先看保證一致性的兩種機(jī)制：

1、Write All Read one，所有節(jié)點(diǎn)寫(xiě)成功才算成功，從任意一個(gè)節(jié)點(diǎn)讀都是最新數(shù)據(jù)；

2、Quorum 機(jī)制，在 N 個(gè)副本中，一次更新成功的如果有 W 個(gè)，那么在讀取數(shù)據(jù)時(shí)從大于 N－W 個(gè)副本中讀取，這樣就至少讀到一個(gè)更新成功的數(shù)據(jù)。如，10 個(gè)副本，更新成功 5 個(gè)，只要讀大于 10-5=5，即訪問(wèn) 6 個(gè)節(jié)點(diǎn)至少能讀到一個(gè)最新的值。Paxos 算法就用到了此機(jī)制。

再看 Paxos 算法，它主要解決一致性問(wèn)題，在分布式領(lǐng)域具有非常重要的地位。

邏輯上包含三類節(jié)點(diǎn)角色：

• Proposer 提案者，提出議案，議案即操作，被抽象為 value，如更新某值

• Acceptor 批準(zhǔn)者，完全對(duì)等獨(dú)立，Proposer 提出的 value 必須獲得超過(guò)半數(shù)（N/2+1）的 Acceptor 批準(zhǔn)后才能通過(guò)

• Learner 學(xué)習(xí)者，不參與選舉，而是學(xué)習(xí)被批準(zhǔn)的 value，至少讀取 N/2+1 個(gè) Accpetor，才能學(xué)習(xí)到一個(gè)通過(guò)的 value

選舉過(guò)程是 Paxos 算法中最核心的內(nèi)容，包含兩個(gè)階段：

階段1、準(zhǔn)備階段
Proposer 生成全局唯一且遞增的 ProposalID，向 Paxos 集群的所有機(jī)器發(fā)送 Prepare 請(qǐng)求，不攜帶 value，只攜帶 ProposalID

Acceptor 收到 Prepare 請(qǐng)求后，收到的 ProposalID 比之前已響應(yīng)的所有提案的大

• 在本地持久化 ProposalID，可記為 Max_ProposalID；

• 回復(fù)請(qǐng)求，并帶上已經(jīng) Accept 的提案中 ProposalID 最大的 value，如果此時(shí)還沒(méi)有已經(jīng) Accept 的提案，則返回 value 為空；

• 做出承諾，不會(huì) Accept 任何小于 Max_ProposalID 的提案。

否則，不回復(fù)或回復(fù) Error

階段2、選舉階段

Proposer 發(fā)送 Accept

Proposer 收集到一些 Prepare 回復(fù)，有 3 種情況：

• 若回復(fù)數(shù)量 > 一半的 Acceptor 數(shù)量，且所有回復(fù)的 value 都為空時(shí)，則 Porposer 發(fā)出 accept 請(qǐng)求，并帶上自己指定的 value。

• 若回復(fù)數(shù)量 > 一半的 Acceptor 數(shù)量，且有的回復(fù) value 不為空時(shí)，則 Porposer 發(fā)出 accept 請(qǐng)求，并帶上回復(fù)中 ProposalID 最大的 value，作為自己的提案內(nèi)容。

• 若回復(fù)數(shù)量 <= 一半的 Acceptor 數(shù)量時(shí)，則嘗試更新生成更大的 ProposalID，再轉(zhuǎn)到準(zhǔn)備階段執(zhí)行。

Acceptor 應(yīng)答 Accept 

Accpetor 收到 Accpet 請(qǐng)求后，判斷：

• 若收到的 ProposalID >= Max_ProposalID，則回復(fù)提交成功，并持久化 ProposalID 和 value；

• 若收到的 ProposalID < Max_ProposalID，則不回復(fù)或者回復(fù)提交失敗。

Proposer 統(tǒng)計(jì)投票 

經(jīng)過(guò)一段時(shí)間后，Proposer 會(huì)收集到一些 Accept 回復(fù)提交成功的情況，比如：

• 當(dāng)回復(fù)數(shù)量 > 一半的 Acceptor 數(shù)量時(shí)，則表示提交 value 成功，此時(shí)可以發(fā)一個(gè)廣播給所有的 Proposer、Learner，通知它們已 commit 的 value；

• 當(dāng)回復(fù)數(shù)量 <= 一半的 Acceptor 數(shù)量時(shí)，則嘗試更新生成更大的 ProposalID，轉(zhuǎn)到準(zhǔn)備階段執(zhí)行。

• 當(dāng)收到一條提交失敗的回復(fù)時(shí)，則嘗試更新生成更大的 ProposalID，也會(huì)轉(zhuǎn)到準(zhǔn)備階段執(zhí)行。

Zab(ZooKeeper Atomic Broadcast，ZooKeeper 原子廣播協(xié)議) 是 ZooKeeper 保證事務(wù)一致性的協(xié)議，分為消息廣播、崩潰恢復(fù)、數(shù)據(jù)同步階段。Zab 協(xié)議是基于 Paxos 算法實(shí)現(xiàn)。

兩者聯(lián)系：

• 都存在一個(gè) Leader 進(jìn)程的角色，負(fù)責(zé)協(xié)調(diào)多個(gè) Follower 進(jìn)程的運(yùn)行

• 都應(yīng)用 Quorum 機(jī)制，Leader 進(jìn)程都會(huì)等待超過(guò)半數(shù)的 Follower 做出正確的反饋后，才會(huì)將一個(gè)提案提交

• 在 Zab 協(xié)議中，Zxid 中通過(guò) epoch 來(lái)代表當(dāng)前 Leader 周期；在 Paxos 算法中叫 Ballot Number

區(qū)別：

• Paxos 是論文性質(zhì)的理論，目的是設(shè)計(jì)一種通用的分布式一致性算法；而 Zab 協(xié)議是應(yīng)用在 ZooKeeper 中對(duì) Paxos 的實(shí)踐，是一個(gè)為解決一致性特別設(shè)計(jì)的崩潰可恢復(fù)的原子消息廣播算法。