引言

關(guān)于一致性的話題，在分布式領(lǐng)域算是一個(gè)殿堂級(jí)的課題。但從各種文章上看出大家對(duì)其理解比較模糊，大概都能說(shuō)出一些相關(guān)的概念，但都沒(méi)法完全解析清楚。本篇文章我將從一致性說(shuō)起，好好聊一聊對(duì)一致性概念的思考和理解，然后引出paxos算法。

關(guān)于paxos算法，先給出幾個(gè)形容該算法的表述：

Google Chubby的作者M(jìn)ike Burrows說(shuō)過(guò):這個(gè)世界上只有一種一致性算法，那就是Paxos

計(jì)算機(jī)分布式系統(tǒng)中號(hào)稱最難理解的協(xié)議-Paxos

Paxos的作者Leslie Lamport寫了篇paper，因此獲得了圖靈獎(jiǎng)

可能大家對(duì)paxos不是很了解，而說(shuō)起raft都知道。因?yàn)閜axos的理論太抽象，無(wú)法很容易落地工程中，而raft作為multi paxos的一個(gè)應(yīng)用，其貢獻(xiàn)在于其一致性理論很好理解，落地又比較簡(jiǎn)單，所以被大家所熟知。raft很好地解釋了HOW，但缺少WHY，而paxos從本質(zhì)上解釋了WHY。
本文從一致性的理論一步一步推導(dǎo)出paxos的核心理念，然后給出paxos的具體步驟（很多paxos的文章也只是談了這一步，并沒(méi)有給出理念）。

1. 一致性

一般我們?cè)谡務(wù)撘恢滦缘臅r(shí)候，有的人會(huì)說(shuō)事務(wù)中的ACID中的C，有的人會(huì)說(shuō)是分布式事務(wù)中的強(qiáng)一致性，有的人會(huì)說(shuō)是CAP理論上中C，也有的人會(huì)說(shuō)是實(shí)現(xiàn)了paxos/raft算法的就是一致性結(jié)構(gòu)。很多人都會(huì)對(duì)一致性的理解都是模凌兩可的，拿這個(gè)一個(gè)領(lǐng)域內(nèi)的原理去解釋另一個(gè)領(lǐng)域的東西。

那今天我們來(lái)先好好說(shuō)一說(shuō)一致性這個(gè)問(wèn)題。
在計(jì)算機(jī)軟件領(lǐng)域，我們談到一致性，其實(shí)會(huì)涉及到三個(gè)領(lǐng)域：數(shù)據(jù)庫(kù)，業(yè)務(wù)邏輯以及分布式。

在數(shù)據(jù)庫(kù)中，一致性是指事務(wù)特性中ACID的C，在事務(wù)的開始和結(jié)束以后，數(shù)據(jù)庫(kù)的一致性約束沒(méi)有被破壞。即以事務(wù)為單位，數(shù)據(jù)庫(kù)從一個(gè)一致性狀態(tài)變到另一個(gè)一致性狀態(tài)。

在業(yè)務(wù)邏輯中，通常一份邏輯數(shù)據(jù)，被拆分到不同的數(shù)據(jù)庫(kù)中甚至不同的系統(tǒng)中，我們沒(méi)有辦法使用本地事務(wù)來(lái)保證這份邏輯數(shù)據(jù)的原子性和一致性，這個(gè)時(shí)候通常可以借助分布式事務(wù)來(lái)解決，或者其他一些可補(bǔ)償?shù)臋C(jī)制。通常這些一致性都維持在弱一致性（最終一致性）層面上。

在分布式系統(tǒng)中，一致性（強(qiáng)一致性）是指一份邏輯數(shù)據(jù)冗余存在多個(gè)物理副本中，對(duì)其執(zhí)行讀寫操作的表現(xiàn)行為是否一致的。這也符合CAP原理的闡述。（所以當(dāng)有人讓你舉例CP場(chǎng)景的時(shí)候，千萬(wàn)別再拿銀行轉(zhuǎn)賬說(shuō)事了。）下面我們著重說(shuō)一下分布式系統(tǒng)的一致性理論。

2. 分布式一致性

上面我們說(shuō)到分布式系統(tǒng)一致性是指，一份邏輯數(shù)據(jù)冗余存在多個(gè)物理副本中，對(duì)其執(zhí)行讀寫操作的表現(xiàn)行為是否一致的。我們下面來(lái)好好解讀一下這句話。

首先，提問(wèn)一下，什么一份邏輯數(shù)據(jù)需要冗余存在多個(gè)物理副本中？
核心點(diǎn)在于可用率。我們知道一些牛逼的系統(tǒng)的可用率都很高，可以達(dá)到9個(gè)9（99.9999999%）。這些牛逼的系統(tǒng)其實(shí)都是搭建在一些不那么可靠的硬件設(shè)施上。那提升可用率一個(gè)很明顯的做法就是冗余恢復(fù)，我使用多臺(tái)機(jī)器存在同一份數(shù)據(jù)，當(dāng)一臺(tái)機(jī)器出問(wèn)題后，我可以讀另一臺(tái)機(jī)器。假設(shè)一臺(tái)機(jī)器出問(wèn)題的概率是1%，那兩臺(tái)都出問(wèn)題的概率就是1%*1%，隨著機(jī)器的增加，都出問(wèn)題的概率越小，而從可用率得到有效提高。

然后，再來(lái)看“對(duì)其執(zhí)行讀寫操作的表現(xiàn)行為是否一致”這句話。
多副本的意思是說(shuō)同一份邏輯數(shù)據(jù)冗余在多個(gè)副本中，那么是否是說(shuō)所有副本每時(shí)每刻都必須數(shù)據(jù)完全一樣呢？
這個(gè)問(wèn)題的答案是顯然不需要的。我們引入多副本的目的在于提高可用率，即當(dāng)出現(xiàn)某幾臺(tái)機(jī)器掛掉，或者網(wǎng)絡(luò)不可達(dá)，或者數(shù)據(jù)延遲的時(shí)候，副本集群仍然可以給出正確的讀寫結(jié)果。
其實(shí)這里引出兩個(gè)概念：狀態(tài)視角的一致性和操作視角的一致性。
狀態(tài)視角的一致性是說(shuō)：所有副本的數(shù)據(jù)狀態(tài)在任何時(shí)刻都是一致的。
操作視角的一致性是說(shuō)：任何對(duì)副本集群的操作的結(jié)果是一致的。

然后再來(lái)引申一下，當(dāng)多個(gè)副本中，因?yàn)橐恍┰颍ňW(wǎng)絡(luò)不可靠）出現(xiàn)數(shù)據(jù)狀態(tài)的不一致的時(shí)候，整個(gè)副本集群可以通過(guò)自己的方式來(lái)對(duì)某個(gè)提議（操作）能夠達(dá)成統(tǒng)一的意見(jiàn)。這個(gè)概念就叫做共識(shí)。這里我們只是簡(jiǎn)單聊一下共識(shí)，下面我們會(huì)詳細(xì)討論下這個(gè)問(wèn)題。
對(duì)，這里也解釋了，當(dāng)我們說(shuō)到paxos算法的時(shí)候，都說(shuō)他是一個(gè)共識(shí)算法的原因。

3. 復(fù)制算法

上面說(shuō)到一份邏輯數(shù)據(jù)冗余在多個(gè)副本中。如何冗余呢？
說(shuō)到底就是數(shù)據(jù)復(fù)制，當(dāng)一個(gè)副本收到一個(gè)新數(shù)據(jù)的時(shí)候，將這個(gè)數(shù)據(jù)復(fù)制給其他副本的動(dòng)作。
下面我們來(lái)看一下常見(jiàn)的幾種復(fù)制算法從引出我們的paxos。

主從同步復(fù)制

image.png

原理很簡(jiǎn)單，所有的讀寫交給主節(jié)點(diǎn)。當(dāng)主節(jié)點(diǎn)收到寫操作時(shí)，必須同步復(fù)制給所有從節(jié)點(diǎn)，只有所有從節(jié)點(diǎn)都返回成功后，主節(jié)點(diǎn)才向客戶點(diǎn)返回成功。
這里的主從同步復(fù)制保證了上面提到的狀態(tài)視角的一致性。
但是對(duì)于可用率來(lái)反而降低了。任何一個(gè)從節(jié)點(diǎn)失敗，本次客戶端的請(qǐng)求就會(huì)失敗。

主從異步復(fù)制

image.png

原理上將也很簡(jiǎn)單，就是寫請(qǐng)求只要寫主節(jié)點(diǎn)就返回給客戶端成功。
然后從節(jié)點(diǎn)異步復(fù)制。這也是MySQL binlog的復(fù)制策略。
異步復(fù)制解決了上面同步復(fù)制的可用率問(wèn)題，但是如果當(dāng)主節(jié)點(diǎn)寫入成功到復(fù)制給從階段這段時(shí)間，主節(jié)點(diǎn)故障，這樣數(shù)據(jù)就丟失了。

多數(shù)派讀寫

我們既希望能保證可用率，又希望能夠保證在部分機(jī)器掛的時(shí)候，不會(huì)數(shù)據(jù)丟失造成不一致。
那么思路就是寫的時(shí)候，同步寫一部分副本，其他副本異步去寫。
這也就引出來(lái)多數(shù)派讀寫。
那么我們面臨的問(wèn)題是同步多多少個(gè)副本呢？讀的時(shí)候？

image.png

如上圖所示，我們?cè)趺幢ＷC讀到就是剛才寫入的副本呢？
這里就引入多數(shù)派讀寫的理論。
假設(shè)，我們有3個(gè)副本（一般副本數(shù)都是奇數(shù)，至于為什么，聰明的你肯定能想出來(lái)），我們同步寫2個(gè)，讀的時(shí)候，如果一定到2個(gè)上都去讀，那么無(wú)論我們讀到的是哪2個(gè)，肯定至少能得到剛才同步寫的一臺(tái)機(jī)器上。
即多數(shù)派寫的機(jī)器和多數(shù)派讀機(jī)器的情況下，一定有重復(fù)機(jī)器。
（n/2+1）+(n/2+1) > n。
所以說(shuō)多數(shù)派讀寫既有主從同步復(fù)制的數(shù)據(jù)一致性，又有主從異步復(fù)制的可用率（因?yàn)橥綄?，只需要超過(guò)半數(shù)的機(jī)器的成功就同步返回成功了）。

4. 從多數(shù)派讀寫引出paxos

版本號(hào)的引入

剛才說(shuō)了多數(shù)派讀寫的基本原理，首先會(huì)面臨一個(gè)問(wèn)題：

image.png

假設(shè)3副本集群中a的初始狀態(tài)是0，然后客戶端將a改為1。副本1和副本2此時(shí)a=1，副本3的a=0，然后客戶端進(jìn)行多數(shù)派讀，讀到的是副本1和副本3，這樣到底a是0還是1呢？
解決這個(gè)問(wèn)題的辦法就是引入版本號(hào)。
當(dāng)寫數(shù)據(jù)的時(shí)候，將版本號(hào)+1，這樣，讀取的時(shí)候，取版本號(hào)最大的那個(gè)。

共識(shí)問(wèn)題

當(dāng)我們引入版本號(hào)之后，其實(shí)還是會(huì)有問(wèn)題。

image.png

首先客戶端希望寫入a1的值是1，然后當(dāng)進(jìn)行了多數(shù)派寫后，還未返回客戶端結(jié)果時(shí)，副本1宕機(jī)了。這樣因?yàn)榭蛻舳耸詹坏饺魏蝦esponse，就會(huì)進(jìn)行重試，那這次，突然又想把a(bǔ)的值設(shè)置為2了。
然后這是就出現(xiàn)的問(wèn)題。版本號(hào)最大的是1，但1這個(gè)版本號(hào)居然對(duì)應(yīng)了兩個(gè)值。無(wú)法決定應(yīng)該返回哪個(gè)值了。
我們把這個(gè)問(wèn)題擴(kuò)展引申一下，我們希望的是對(duì)同一件事（a1的更新）的多個(gè)提議，只能有一個(gè)提議被確認(rèn)。

這里引申出一個(gè)很重要的概念：共識(shí)。
我們先來(lái)看一下共識(shí)的問(wèn)題域的定義：

Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If
no value is proposed, then no value should be chosen. If a value has been
chosen, then processes should be able to learn the chosen value. The safety
requirements for consensus are:
? Only a value that has been proposed may be chosen,
? Only a single value is chosen, and
? A process never learns that a value has been chosen unless it actually
has been.
We won’t try to specify precise liveness requirements. However, the goal is
to ensure that some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.

這里解讀一下，假設(shè)一個(gè)多節(jié)點(diǎn)的數(shù)據(jù)集群，每個(gè)節(jié)點(diǎn)都可以對(duì)同一件事進(jìn)行提議，共識(shí)算法的目標(biāo)是保證只會(huì)有一個(gè)提議被選擇。
即：

僅會(huì)有一個(gè)被提議的value被選擇。
被選擇的提議將不會(huì)發(fā)生改變。
一旦某個(gè)提供被選擇，則任何一個(gè)節(jié)點(diǎn)最終都會(huì)學(xué)到這個(gè)被選擇的提議值。

5. 引入paxos算法

5.1 思想

那么為了達(dá)到這個(gè)目的，我們應(yīng)該如何解決呢？
如果只有一個(gè)acceptor的話，其實(shí)這個(gè)問(wèn)題很好解決。第一個(gè)proposer提議后，拒絕后面所有的提議。有多個(gè)acceptor的話，如果每次讀寫都是對(duì)所有acceptor同步的話，這個(gè)問(wèn)題就變成了單個(gè)acceptor的問(wèn)題。但為了可用率，我們只允許每次讀寫，多數(shù)派成功后就可以。那應(yīng)該怎么辦呢？

paxos里引入一個(gè)很有意思的理念：反向理念。即讓數(shù)據(jù)記住寫入者。
paxos算法是通過(guò)引入兩階段的多數(shù)派讀寫+數(shù)據(jù)記憶來(lái)實(shí)現(xiàn)。
增加一個(gè)階段的最主要目的為了讓副本上記住最后一個(gè)提議者。使得二階段的時(shí)候，副本只接受記錄到的最后一個(gè)提議者。

5.2 roles

這里引入paxos算法的幾個(gè)角色。一個(gè)副本節(jié)點(diǎn)可以同時(shí)擔(dān)當(dāng)幾個(gè)角色，不會(huì)影響算法協(xié)議的正確性。

Client
表示發(fā)起請(qǐng)求給副本集群的客戶端。
Acceptor (Voters)
就是副本集群中的普通節(jié)點(diǎn)。超過(guò)半數(shù)的Acceptors are called Quorums
Proposer
是副本集群中的某個(gè)節(jié)點(diǎn)，承接客戶端的請(qǐng)求以及發(fā)起提議。
Learner
與協(xié)議算法本身無(wú)關(guān)。當(dāng)一個(gè)值被確認(rèn)后，發(fā)送給所有l(wèi)earner。learner用來(lái)對(duì)客戶端作出響應(yīng)。多數(shù)情況下，proposer也是一個(gè)learner。
目的為了提高可用率，可以增加learner的數(shù)量。

5.3 具體過(guò)程

paxos的兩階段分為兩個(gè)步驟：prepare和accept
為了下面好理解，我們事先先定義幾個(gè)概念：

round：代表一個(gè)提議。

proposer端：
round_num：代表proposer發(fā)起一次提議標(biāo)識(shí)。這個(gè)值遞增。即每次發(fā)起提議時(shí)，這個(gè)值一定大于歷史上發(fā)起過(guò)的round_num。

acceptor端
last_round_num：代表acceptor可以接受哪個(gè)proposer來(lái)寫。
v：代表acceptor已經(jīng)寫入的值
v_round_num：代表v寫入的時(shí)候，對(duì)應(yīng)的proposer的round_num

image.png

5.3.1 Phase 1

第一階段包括

Prepare過(guò)程

proposer向acceptor進(jìn)行提議，發(fā)送一個(gè)round_num，這個(gè)值遞增。即每次發(fā)起提議時(shí)，這個(gè)值一定大于歷史上發(fā)起過(guò)的round_num。

Promise過(guò)程

當(dāng)acceptor收到proposer的prepare請(qǐng)求后，需要向proposer保證，我以后只會(huì)接受你的請(qǐng)求。

if (last_round_num > round_num) { // 代表本次提議round_num是一個(gè)老的了，直接拒絕
    refuse;
}
set last_round_num = round_num; // 代表從現(xiàn)在開始我只接受last_round_num的提議

return (last_round_num, v, v_round_num);

5.2.2 Phase 2

Accept過(guò)程

當(dāng)proposer收到多數(shù)派的acceptor的Promise返回值后，做出以下判斷：

if (v全部都是null){ // v從來(lái)沒(méi)有被設(shè)置過(guò)，那么我就設(shè)置自己想設(shè)置的值
    set accept_value = want_set_v;
} else {
    if (發(fā)現(xiàn)有一個(gè)的last_round_num要大于自己的round_num){// 本次提議為老提議
        中斷本次提議;
    }else {// 這一步又叫做修復(fù)。修復(fù)在Phase1的時(shí)候，少數(shù)派的節(jié)點(diǎn)
        從多個(gè)acceptor的返回值中挑一個(gè)最大的v_round_num對(duì)應(yīng)v
        set accept_value = v; round_num =  v_round_num;
    }
}
send round_num, accept_value

總結(jié)一句話，當(dāng)發(fā)現(xiàn)有人已經(jīng)設(shè)置v了，則我也設(shè)置v，保持不變。
如果都沒(méi)人設(shè)置v，那我就設(shè)置自己想設(shè)置的值。
這一步也是保證了

只會(huì)有一個(gè)提議被確認(rèn)的理論。

Accepted過(guò)程

當(dāng)acceptor收到proposer的Accept請(qǐng)求后，拒絕不等于last_round_num的請(qǐng)求，然后更新v和v_round_num。

if (round_num != last_round_num) { //拒絕不等于last_round_num的請(qǐng)求。
    refuse;
}else{
    set v = accept_value;
    set v_round_num = round_num;
}

5.4 看paxos如何解決有沖突的現(xiàn)象

以下這張圖解釋了發(fā)生了沖突的時(shí)候，paxos是如何解決的。

image.png

圖中已經(jīng)畫的很清楚了，就不做詳細(xì)解釋了。

5.5 活鎖問(wèn)題

其實(shí)paxos是有一個(gè)可能存在活鎖的問(wèn)題的。從上面我們知道當(dāng)某個(gè)proposer失敗后，它會(huì)遞增round_num進(jìn)行重試。
當(dāng)兩個(gè)proposer交替失敗后重試后，可能出現(xiàn)循環(huán)鎖的問(wèn)題，導(dǎo)致一直都沒(méi)法確認(rèn)值。
如圖所示

image.png

6. 擴(kuò)展

我們上面說(shuō)的額paxos實(shí)際上是最樸實(shí)的classic paxos。
classic paxos一直以來(lái)被詬病的地方是說(shuō)，一次寫入，需要兩次rpc，影響效率。
所以Leslie Lamport老爺子對(duì)paxos進(jìn)行了優(yōu)化, multi paxso和fast paxos。

multi paxso

我們引入另一個(gè)角色：leader。
所有的提議都由leader來(lái)做，如果leader相對(duì)穩(wěn)定的話。其實(shí)我們可以不要classic paxos中的第一階段。
前面我們說(shuō)過(guò)，第一階段的一個(gè)最主要的目的是數(shù)據(jù)記憶，即我只允許你來(lái)修改我的值。那如果都是由leader來(lái)提議的話，第一階段可以省略的。
如果省略，那round_num怎么搞的？
在實(shí)際應(yīng)用中，我們一般都是對(duì)一組連續(xù)的value進(jìn)行提議。
所以假設(shè)我們第一次提議的時(shí)候，兩階段，使用的round_num是N。那么后續(xù)直接使用N+1就可以了。這樣后續(xù)的提議就只需要第二階段就可以了。

而且，因?yàn)槲覀兌际鞘褂胠eader來(lái)提議，也解決了上面提到的活鎖的問(wèn)題。

我們熟知的raft，其核心就是multi paxos的一個(gè)應(yīng)用。之所以raft比paxos流行的原因是因?yàn)閞aft的描述額更佳直白，更加工程化。

chubby，zookeeper，spanner等著名應(yīng)用都是使用multi paxso協(xié)議的一些擴(kuò)展。

fast paxso

沒(méi)沖突：1輪rpc
有沖突：2輪rpc
意思就是說(shuō)先直接進(jìn)行第2次rpc寫入看看，如果發(fā)現(xiàn)失敗（多數(shù)派寫入的時(shí)候副本的可接受的客戶端不是本次請(qǐng)求的客戶端），就會(huì)退化為class paxos。如果成功就成功了。
有點(diǎn)類似于JAVA中的偏向鎖的概念。

參考文檔：

https://blog.openacid.com/algo/paxos/
http://www.lamport.org/
http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一致性之Paxos算法

一致性之Paxos算法

引言

1. 一致性

2. 分布式一致性

3. 復(fù)制算法

主從同步復(fù)制

主從異步復(fù)制

多數(shù)派讀寫

4. 從多數(shù)派讀寫引出paxos

版本號(hào)的引入

共識(shí)問(wèn)題

5. 引入paxos算法

5.1 思想

5.2 roles

5.3 具體過(guò)程

5.3.1 Phase 1

Prepare過(guò)程

Promise過(guò)程

5.2.2 Phase 2

Accept過(guò)程

Accepted過(guò)程

5.4 看paxos如何解決有沖突的現(xiàn)象

5.5 活鎖問(wèn)題

6. 擴(kuò)展

multi paxso

fast paxso

參考文檔：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

一致性之Paxos算法

引言

1. 一致性

2. 分布式一致性

3. 復(fù)制算法

主從同步復(fù)制

主從異步復(fù)制

多數(shù)派讀寫

4. 從多數(shù)派讀寫引出paxos

版本號(hào)的引入

共識(shí)問(wèn)題

5. 引入paxos算法

5.1 思想

5.2 roles

5.3 具體過(guò)程

5.3.1 Phase 1

Prepare過(guò)程

Promise過(guò)程

5.2.2 Phase 2

Accept過(guò)程

Accepted過(guò)程

5.4 看paxos如何解決有沖突的現(xiàn)象

5.5 活鎖問(wèn)題

6. 擴(kuò)展

multi paxso

fast paxso

參考文檔：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av