分布一致性演算法

Ⅰ 一致性演算法（Paxos、Raft、ZAB)

一致性演算法（Paxos、Raft、ZAB)

什麼是一致性

1、弱一致性
a、最終一致性
i、DNS（Domain Name System）
j、Gossip（Cassandra的通信協議）

以DNS為例：

2、強一致性
a、同步
b、Paxos
c、(multi-paxos)
d、ZAB(multi-paxos)

DNS 就是一種最終一致性，比如 上圖中 增加一條記錄： www.hyb.small.com , 我們從其他DNS伺服器一時會讀取不到，但是過一會就會讀取得到了。

數據不能存在單點上。
分布式系統對fault tolerence的一般解決方案是state machine replication 。

准確的來說應該是 state machine replication 的共識（consensus）演算法。

paxos其實是一個共識演算法，系統的最終一致性，不僅需要達成共識，還會取決於client的行為

主從同步復制

1、Master 接受寫請求
2、Master 復制日誌到slave
3、Master 等待，直到所有從庫返回

問題：

任何一個節點失敗，哪怕是從節點（Slave）同步失敗，都會導致整個集群不可用，雖然保證了一致性，但是可用性卻大大降低

基本想法：
a、多數派：
每次寫都保證寫入大於N/2個節點，每次讀保證從大於N/2個節點中讀。
比如5個節點，每次寫大於3個節點才算成功；讀也是大於3個節點才算成功。

b、多數派還不夠！
在並發環境下，無法保證系統正確性，順序非常重要。比如下圖的 Inc 5; Set 0; 執行順序亂了，結果就會引發錯亂。

Lesile Lamport,Latex的發明者。

為描述Paxos演算法早昌，Lamport虛擬了一個叫做Paxos的希臘城邦，這個島按照議會民主制的政治模式制定法律，但是沒有人願意將自己的全部時間和精力放在這種事上，所以無論是議員、議長或者傳遞消息的時間。

Paxos

1、Basic Paxos
2、Multi Paxos
3、Fast Paxos

強一致性演算法---Basic Paxos

角色叢睜晌介紹：

Client:系統外部角色，請求發起者。像民眾

Propser: 接滲鋒受Client 請求，向集群提出提議(propose)。並在沖突發生時，起到沖突調節的作用。像議員替民眾提出議案

Accpetor(Voter): 提議投票和接收者，只有在形成法定人數(Quorum,一般即為majority 多數派)時，提議才會最終接受，像國會。

Learner:提議接受者，backup，備份，對集群一致性沒什麼影響，像記錄員；

步驟、階段(phases):
1、Phase 1a:Prepare
proposer 提出一個提案，編號為N，此N 大於這個proposer之前提出提案編號，向acceptors請求同意，要求有quorum接受的才行。

2、Phase 1b:Promise
N 必須大於此acceptor之前接受的任何提案編號，才會接受，否則會拒絕。

3、Phase 2a: Accept
如果達到了多數派，proposer會發出accept請求，此請求包含提案編號N ,以及提案內容。

4、Phase 2b:Accepted
如果此acceptor在此期間沒有收到任何編號大於N的提案，則接受此提案內容，否則忽略。

流程圖如下：

操作步驟如下：
Request;
Prepare(1);
Promise(1,{Va,Vb,Vc});
Accept(1,Vn)
Accepted(1,Vn);
Response;

1、Acceptor部分節點失敗，但達到了Quoroms，此時仍然會成功。

如果有一個Acceptor因為各種原因掛掉了，3個Acceptors變成了2個Acceptors，還是滿足>n/2 的要求，所以還是會成功。

2、Proposer失敗，上一次記錄不會被寫入Proposer表，然後重新開啟一個新的Proposer，來替代上次的Proposer來處理未完成請求，此時編號已經增加為2，也就是Prepare(2)

Basic Paxos when an Proposer fails
如果Proposer 在發送了一條Accept消息之後，但是還沒收到Accepted消息之前就掛掉了，只有一個Acceptor接收到了Accept消息。那麼整個Paxos協議就沒法進行下去了，這時一個新的Leader（Proposer）會被選舉出來，重新開始一輪新的共識。

Basic Paxos潛在的問題是：活鎖（liveness）或eling

Basic Paxos很有可能出現這種情況：
1、議員A(proposer A)說我們來討論提案1，大部分議員說：「好，我們來討論提案1」；
2、但是此時議員A還沒有說內容是什麼，這時候又來了一個議員B，又來說：「我們來討論提案2」；這時候大部分還沒有接受提案1，提案2的編號是大於提案1的，這時候大部分還沒有接受議案2；
3、這時候議員A以為網路斷了，然後把編號改下，內容不變然後提出議案3；然後議案4、議案5....
這樣就形成了活鎖。
解決活鎖的方法是用Random的timeout，當兩個沖突的時候用一個隨機的等待時間；當自己提議未生效時，再發起提議等待幾秒。

Basic-Paxos是一個無限循環的2PC，1條日誌的確認至少需要2個RTT + 2次落盤（1次是prepare的廣播與回復，1次是accept的廣播與回復）。

Basic Paxos when multiple Proposers conflict
最後再描述一個最復雜的情況，即有多個Proposers認為他們是Leaders，並不斷的發送Prepare請求。為什麼會有多個Leaders呢？ 有可能一個Proposer當了一段時間Leader之後掛掉了，新的Proposer被選為Leader繼續新的一輪共識。後面掛掉的Proposer又恢復了，它認為自己還是Leader，所以繼續發送Prepare請求。

Basic Paxos的問題
難實現（角色太多）、效率低（2輪RPC）、活鎖問題

Multi Paxos:
新概念，Leader;唯一的propser，所有請求都需經過此Leader;

只有一個Proposer，沒有第二個Proposer； 這個Proposer就是Leader,沒人跟他搶;

再者分布式系統必須串列執行所有提議，否則就會出現前面說的順序問題。

--------First Request(第一次執行)----------
Request
Prepare(N) //選Leader
Promise(N,I,{Va,Vb,Vc})
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

--------Following Request(第二次或者以後)----------
Request
Accept!(N,I,Vm)
Accepted(N,I,Vm)
Response;

第二次或者以後，就不用再選Leader了 直接執行Request 請求，由Leader 發出議案。
如果Leader 掛了 就選下一個總統Leader(N+1)

減少角色，進一步簡化，在Basic-Paxos中我們區分了很多角色，有Clients、Proposers、Acceptors、 Learners，實際上Proposers、Acceptors 、Leanrners可以合並成一個，統稱為Server，下面是合並之後的序列圖。

Multi-Paxos when roles are collapsed and the leader is steady
同樣的，當Leader很穩定的時候，我們可以在接下來的執行中忽略Phase 1. 如下圖所示：

Raft
1、劃分三個子問題
a、Leader Election
b、Log Replication
c、Safely
2、重定義角色
a、Leader
b、Follower
c、Candidate

原理動畫解釋： http://thesecretlivesofdata.com/raft
場景測試： https://raft.github.io

Raft 是比 Multi Paxos 還要簡單的一個版本
一致性並不代表完全正確性！三個可能結果：成功，失敗，unknown

詳細內容參考：
https://www.jianshu.com/p/6cd41fe0b8f6

強一致性演算法--ZAB
基本與raft相同。在一些名詞的叫法上有些區別：如ZAB將某一個leader的周期稱為epoch，而raft則稱為term。實現上也有些許不同：如raft保證日誌連續性，心跳方向為leader至follower，ZAB則相反。

Ⅱ 分布式系統常用的一致性演算法有哪些

在做伺服器負載均衡時候可供選擇的負載均衡的演算法有很多，包括： 輪循演算法（Round Robin）、哈希演算法（HASH）、最少連接演算法（Least Connection）、響應速度演算法（Response Time）、加權法（Weighted ）等。其中哈希演算法是最為常用的演算法. 典型的應用場景是： 有N台伺服器提供緩存服務，需要對伺服器進行負載均衡，將請求平均分發到每台伺服器上，每台機器負責1/N的服務。 常用的演算法是對hash結果取余數 (hash() mod N)：對機器編號從0到N-1，按照自定義的hash()演算法，對每個請求的hash()值按N取模，得到余數i，然後將請求分發到編號為i的機器。但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；如果新增一台機器，會有N /(N+1)的伺服器的緩存數據需要進行重新計算。對於系統而言，這通常是不可接受的顛簸（因為這意味著大量緩存的失效或者數據需要轉移）。那麼，如何設計一個負載均衡策略，使得受到影響的請求盡可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都採用了Consistent Hashing演算法，可以說Consistent Hashing 是分布式系統負載均衡的首選演算法。 1、Consistent Hashing演算法描述 下面以Memcached中的Consisten Hashing演算法為例說明。 由於hash演算法結果一般為unsigned int型，因此對於hash函數的結果應該均勻分布在[0,232-1]間，如果我們把一個圓環用232 個點來進行均勻切割，首先按照hash(key)函數算出伺服器（節點）的哈希值， 並將其分布到0～232的圓上。 用同樣的hash(key)函數求出需要存儲數據的鍵的哈希值，並映射到圓上。然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器（節點）上。 Consistent Hashing原理示意圖 新增一個節點的時候，只有在圓環上新增節點逆時針方向的第一個節點的數據會受到影響。刪除一個節點的時候，只有在圓環上原來刪除節點順時針方向的第一個節點的數據會受到影響，因此通過Consistent Hashing很好地解決了負載均衡中由於新增節點、刪除節點引起的hash值顛簸問題。 Consistent Hashing添加伺服器示意圖 虛擬節點（virtual nodes）：之所以要引進虛擬節點是因為在伺服器（節點）數較少的情況下（例如只有3台伺服器），通過hash(key)算出節點的哈希值在圓環上並不是均勻分布的（稀疏的），仍然會出現各節點負載不均衡的問題。虛擬節點可以認為是實際節點的復製品（replicas），本質上與實際節點實際上是一樣的（key並不相同）。引入虛擬節點後，通過將每個實際的伺服器（節點）數按照一定的比例(例如200倍)擴大後並計算其hash(key)值以均勻分布到圓環上。在進行負載均衡時候，落到虛擬節點的哈希值實際就落到了實際的節點上。由於所有的實際節點是按照相同的比例復製成虛擬節點的，因此解決了節點數較少的情況下哈希值在圓環上均勻分布的問題。 虛擬節點對Consistent Hashing結果的影響 從上圖可以看出，在節點數為10個的情況下，每個實際節點的虛擬節點數為實際節點的100-200倍的時候，結果還是很均衡的。 第3段中有這些文字：「但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；」 為何是 (N-1)/N 呢？解釋如下： 比如有 3 台機器，hash值 1-6 在這3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果掛掉一台，只剩兩台，模數取 2 ，那麼分布情況就變成： host 1: 1 3 5 host 2: 2 4 6 可以看到，還在數據位置不變的只有2個： 1，2，位置發生改變的有4個，占共6個數據的比率是 4/6 = 2/3這樣的話，受影響的數據太多了，勢必太多的數據需要重新從 DB 載入到 cache 中，嚴重影響性能 【consistent hashing 的辦法】 上面提到的 hash 取模，模數取的比較小，一般是負載的數量，而 consistent hashing 的本質是將模數取的比較大，為 2的32次方減1，即一個最大的 32 位整數。然後，就可以從容的安排數據導向了，那個圖還是挺直觀的。 以下部分為一致性哈希演算法的一種PHP實現。點擊下載

Ⅲ 一致性hash演算法

先說一下hash演算法，hash演算法是將任意長度的二進制值映射為固定長度的二進制值。

在分布式系統中， 可以通過該演算法計算哈希值

Hash是一個字元串到正整數的hash映射函數， key是鍵值（例如伺服器ip地址/唯一主機名）， n是鍵的個數。每當改變伺服器數量時， 都會使hash值改變，容錯性和擴展性會極差。

一致性hash演算法將2的32次方的hash空間組成一個首尾相連的圓環，然後把伺服器空敗ip地址/唯一主機名作為鍵進行hash得到一個唯一的hash值，該值就是該伺服器在圓環上的位置。數據也通過hash得到一個唯一的hash值，然後把數據放進最近的伺服器中（順時針），如下圖。

假如伺服器C宕機了， 數據B就會被放在伺服器A，其他伺服器和數據都不會受到影響。

假如新增伺服器D， 數據C會放在伺服器D中，其他的都不變。

在伺服器節點太少時， 會有數據告虧碼傾斜問題，即大部分數據在一個節點上。

為了解決這個問題，引入了虛擬節點。可以在ip地址/唯襪哪一主機名後面加上編號，使一台伺服器算出多個hash值，在hash環上增加同一伺服器節點，該節點就是虛擬節點；在伺服器節點較少時也能實現數據均勻分布。

Ⅳ 分布式存儲中，怎樣使用paxos演算法保證數據的一致性

在分布式系統中，我們經常遇到多數據副本保持一致的問題，在我們所能找到的資料中該問題講的很籠統，模模糊糊的，把多個問題或分類糅合在一起，難以理解。在思考和翻閱資料後，通俗地把一致性的問題可分解為2個問題：
1、任何一次修改保證數據一致性。
2、多次數據修改的一致性。
在弱一致性的演算法，不要求每次修改的內容在修改後多副本的內容是一致的，對問題1的解決比較寬松，更多解決問題2，該類演算法追求每次修改的高度並發性，減少多副本之間修改的關聯性，以獲得更好的並發性能。例如最終一致性，無所謂每次用戶修改後的多副本的一致性及格過，只要求在單調的時間方向上，數據最終保持一致，如此獲得了修改極大的並發性能。
在強一致性的演算法中，強調單次修改後結果的一致，需要保證了對問題1和問題2要求的實現，犧牲了並發性能。本文是討論對解決問題1實現演算法，這些演算法往往在強一致性要求的應用中使用。
解決問題1的方法，通常有兩階段提交演算法、採用分布式鎖服務和採用樂觀鎖原理實現的同步方式,下面分別介紹這幾種演算法的實現原理。

兩階段提交演算法

在兩階段提交協議中，系統一般包含兩類機器（或節點）：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants，cohorts或workers），一般包含多個，在數據存儲系統中可以理解為數據副本的個數。兩階段提交協議由兩個階段組成，在正常的執行下，這兩個階段的執行過程如下所述：
階段1：請求階段（commit-request phase，或稱表決階段，voting phase）。
在請求階段，協調者將通知事務參與者准備提交或取消事務，然後進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。
階段2：提交階段（commit phase）。
在該階段，協調者將基於第一個階段的投票結果進行決策：提交或取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者將通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行響應的操作。
舉個例子：A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動將舉行；如果有一人不同意去爬長城，那麼活動將取消。用2PC演算法解決該問題的過程如下：
首先A將成為該活動的協調者，B、C和D將成為該活動的參與者。
階段1：A發郵件給B、C和D，提出下周三去爬山，問是否同意。那麼此時A需要等待B、C和D的郵件。B、C和D分別查看自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A它們同意下周三去爬長城。由於某種原因，D白天沒有查看郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後查看日程安排，發現周三當天已經有別的安排，那麼D回復A說活動取消吧。
階段2：此時A收到了所有活動參與者的郵件，並且A發現D下周三不能去爬山。那麼A將發郵件通知B、C和D，下周三爬長城活動取消。此時B、C回復A「太可惜了」，D回復A「不好意思」。至此該事務終止。
兩階段提交演算法在分布式系統結合，可實現單用戶對文件（對象）多個副本的修改，多副本數據的同步。其結合的原理如下：
1、客戶端（協調者）向所有的數據副本的存儲主機（參與者）發送：修改具體的文件名、偏移量、數據和長度信息，請求修改數據，該消息是1階段的請求消息。
2、存儲主機接收到請求後，備份修改前的數據以備回滾，修改文件數據後，向客戶端回應修改成功的消息。 如果存儲主機由於某些原因（磁碟損壞、空間不足等）不能修改數據，回應修改失敗的消息。
3、客戶端接收發送出去的每一個消息回應，如果存儲主機全部回應都修改成功，向每存儲主機發送確認修改的提交消息；如果存在存儲主機回應修改失敗，或者超時未回應，客戶端向所有存儲主機發送取消修改的提交消息。該消息是2階段的提交消息。
4、存儲主機接收到客戶端的提交消息，如果是確認修改，則直接回應該提交OK消息；如果是取消修改，則將修改數據還原為修改前，然後回應取消修改OK的消息。
5、 客戶端接收全部存儲主機的回應，整個操作成功。
在該過程中可能存在通信失敗，例如網路中斷、主機宕機等諸多的原因，對於未在演算法中定義的其它異常，都認為是提交失敗，都需要回滾，這是該演算法基於確定的通信回復實現的，在參與者的確定回復（無論是回復失敗還是回復成功）之上執行邏輯處理，符合確定性的條件當然能夠獲得確定性的結果哲學原理。

分布式鎖服務

分布式鎖是對數據被外界修改持保守態度，在整個數據處理過程中將數據處於鎖定狀態，在用戶修改數據的同時，其它用戶不允許修改。
採用分布式鎖服務實現數據一致性，是在操作目標之前先獲取操作許可，然後再執行操作，如果其他用戶同時嘗試操作該目標將被阻止，直到前一個用戶釋放許可後，其他用戶才能夠操作目標。分析這個過程，如果只有一個用戶操作目標，沒有多個用戶並發沖突，也申請了操作許可，造成了由於申請操作許可所帶來的資源使用消耗，浪費網路通信和增加了延時。
採用分布式鎖實現多副本內容修改的一致性問題， 選擇控制內容顆粒度實現申請鎖服務。例如我們要保證一個文件的多個副本修改一致， 可以對整個文件修改設置一把鎖，修改時申請鎖，修改這個文件的多個副本，確保多個副本修改的一致，修改完成後釋放鎖；也可以對文件分段，或者是文件中的單個位元組設置鎖， 實現更細顆粒度的鎖操作，減少沖突。
常用的鎖實現演算法有Lamport bakery algorithm （俗稱麵包店演算法）， 還有Paxos演算法。下面對其原理做簡單概述。

Lamport麵包店演算法

是解決多個線程並發訪問一個共享的單用戶資源的互斥問題的演算法。 由Leslie Lamport（英語：Leslie Lamport）發明。
Lamport把這個並發控制演算法可以非常直觀地類比為顧客去麵包店采購。麵包店只能接待一位顧客的采購。已知有n位顧客要進入麵包店采購，安排他們按照次序在前台登記一個簽到號碼。該簽到號碼逐次加1。根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0. 如果完成購買的顧客要再次進店購買，就必須重新排隊。
這個類比中的顧客就相當於線程，而入店購貨就是進入臨界區獨占訪問該共享資源。由於計算機實現的特點，存在兩個線程獲得相同的簽到號碼的情況，這是因為兩個線程幾乎同時申請排隊的簽到號碼，讀取已經發出去的簽到號碼情況，這兩個線程讀到的數據是完全一樣的，然後各自在讀到的數據上找到最大值，再加1作為自己的排隊簽到號碼。為此，該演算法規定如果兩個線程的排隊簽到號碼相等，則線程id號較小的具有優先權。
把該演算法原理與分布式系統相結合，即可實現分步鎖。

Paxos演算法

該演算法比較熱門，參見WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。BigTable使用一個分布式數據鎖服務Chubby，而Chubby使用Paxos演算法來保證備份的一致性。

採用樂觀鎖原理實現的同步

我們舉個例子說明該演算法的實現原理。如一個金融系統，當某個操作員讀取用戶的數據，並在讀出的用戶數據的基礎上進行修改時（如更改用戶帳戶余額），如果採用前面的分布式鎖服務機制，也就意味著整個操作過程中（從操作員讀出數據、開始修改直至提交修改結果的全過程，甚至還包括操作員中途去煮咖啡的時間），資料庫記錄始終處於加鎖狀態，可以想見，如果面對幾百上千個並發，這樣的情況將導致怎樣的後果。
樂觀鎖機制在一定程度上解決了這個問題。樂觀鎖，大多是基於數據版本（ Version）記錄機制實現。何謂數據版本？即為數據增加一個版本標識，在基於資料庫表的版本解決方案中，一般是通過為資料庫表增加一個 「version」 欄位來實現。讀取出數據時，將此版本號一同讀出，之後更新時，對此版本號加一。此時，將提交數據的版本數據與資料庫表對應記錄的當前版本信息進行比對，如果提交的數據版本號大於資料庫表當前版本號，則予以更新，否則認為是過期數據。
對於上面修改用戶帳戶信息的例子而言，假設資料庫中帳戶信息表中有一個 version 欄位，當前值為 1 ；而當前帳戶余額欄位（ balance ）為 $100 。
操作員 A 此時將其讀出（version=1 ），並從其帳戶余額中扣除 $50（$100-$50 ）。
在操作員 A 操作的過程中，操作員B也讀入此用戶信息（ version=1 ），並從其帳戶余額中扣除 $20 （ $100-$20 ）。
操作員 A 完成了修改工作，將數據版本號加一（ version=2 ），連同帳戶扣除後余額（ balance=$50 ），提交至資料庫更新，此時由於提交數據版本大於資料庫記錄當前版本，數據被更新，資料庫記錄 version 更新為 2 。
操作員 B 完成了操作，也將版本號加一（ version=2 ）試圖向資料庫提交數據（ balance=$80 ），但此時比對資料庫記錄版本時發現，操作員 B 提交的數據版本號為 2 ，資料庫記錄當前版本也為 2 ，不滿足 「 提交版本必須大於記錄當前版本才能執行更新 「 的樂觀鎖策略，因此，操作員 B 的提交被駁回。這樣，就避免了操作員 B 用基於 version=1 的舊數據修改的結果覆蓋操作員A 的操作結果的可能。
樂觀鎖機制與分布式系統相結合上， 我整理了偽代碼如下：
obj 操作的目標
vlaue 修改的值
atom_update_ver 每個目標上的版本，每次修改該值遞增
set( obj, value)
{
//從每個節點上取出修改前的對象版本
get original_ver = obj.atom_update_ver from each node;
//將值賦到每個節點的obj目標
set obj = value from each node;
//條件修改每個節點的obj版本，目標版本加一
//比較和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功遞歸修改

該演算法未考慮節點下線、失效等問題，在後續我將分析採用樂觀鎖原理實現一致性演算法，解決問題2、節點失效、通信失敗等問題。

Ⅳ 一致性hash演算法是什麼

一致性哈希演算法是在1997年由麻省理工學院提出的一種分布式哈希（DHT）演算法。其設計目標是為了解決網際網路中的熱點（Hot spot)問題，初衷和CARP十分類似。

一致性Hash是一種特殊的Hash演算法，由於其均衡性、持久性的映射特點，被廣泛的應用於負載均衡領域，如nginx和memcached都採用了一致性Hash來作為集群負載均衡的方案。

一致性哈希演算法的目標是，當K個請求key發起請求時。後台增減節點，只會引起K/N的key發生重新映射。即一致性哈希演算法，在後台節點穩定時，同一key的每次請求映射到的節點是一樣的。而當後台節點增減時，該演算法盡量將K個key映射到與之前相同的節點上。

優點

可擴展性。一致性哈希演算法保證了增加或減少伺服器時，數據存儲的改變最少，相比傳統哈希演算法大大節省了數據移動的開銷。

更好地適應數據的快速增長。採用一致性哈希演算法分布數據，當數據不斷增長時，部分虛擬節點中可能包含很多數據、造成數據在虛擬節點上分布不均衡，此時可以將包含數據多的虛擬節點分裂，這種分裂僅僅是將原有的虛擬節點一分為二、不需要對全部的數據進行重新哈希和劃分。

虛擬節點分裂後，如果物理伺服器的負載仍然不均衡，只需在伺服器之間調整部分虛擬節點的存儲分布。這樣可以隨數據的增長而動態的擴展物理伺服器的數量，且代價遠比傳統哈希演算法重新分布所有數據要小很多。

以上內容參考：網路-一致性哈希

Ⅵ 詳解分布式共識（一致性）演算法Raft

所謂分布式共識（consensus），與 CAP理論 中的一致性（consistency）其實是異曲同工，就是在分布式系統中，所有節點對同一份數據的認知能夠達成一致。保證集群共識的演算法就叫共識演算法，它與一致性協議這個詞也經常互相通用。

當今最著名的共識演算法就是Paxos演算法。它由Leslie Lamport在1990年提出，很長時間以來都是一致性的事實標准。但是它有兩個不小的缺點：難以理解和證明，難以在實際工程中實現。Google Chubby的工程師就曾有以下的評論：

於是2014年，來自斯坦福的兩位大佬Diego Ongaro與John Ousterhout通過論文 《In Search of an Understandable Consensus Algorithm》 提出了一個新的共識演算法Raft。從題目就可以看出，Raft的特點就是容易理解，在此基礎上也容易實現，因此在real world中，它的應用也比Paxos要廣泛，比較有名的如etcd、Ku等。

Raft為了達到易懂易用的目標，主要做了兩件事：一是分解問題（decomposition），即將復雜的分布式共識問題拆分為 領導選舉 （leader election）、 日誌復制 （log replication）和 安全性 （safety）三個子問題，並分別解決；二是壓縮狀態空間（state space rection），相對於Paxos演算法而言施加了更合理的限制，減少因為系統狀態過多而產生的不確定性。

下面先簡要介紹共識演算法的基礎——復制狀態機，然後就來按順序研究Raft是如何解決三個子問題的。

在共識演算法中，所有伺服器節點都會包含一個有限狀態自動機，名為復制狀態機（replicated state machine）。每個節點都維護著一個復制日誌（replicated logs）的隊列，復制狀態機會按序輸入並執行該隊列中的請求，執行狀態轉換並輸出結果。可見，如果能保證各個節點中日誌的一致性，那麼所有節點狀態機的狀態轉換和輸出也就都一致。共識演算法就是為了保障這種一致性的，下圖示出簡單的復制狀態機及其相關架構。

根據分布式系統的 Quorum機制 與NRW演算法，集群中半數以上節點可用時，就能正確處理分布式事務，因此Raft集群幾乎都使用奇數節點，可以防止腦裂並避免浪費資源。採用ZAB協議的ZooKeeper集群也是如此。

在Raft集群中，任意節點同一時刻只能處於領導者（leader）、跟隨者（follower）、候選者（candidate）三種狀態之一。下圖示出節點狀態的轉移規則。

可見，集群建立時所有節點都是跟隨節點。如果在一定時間過後發現沒有領導節點，就會切換到候選狀態，發起選舉。得到多數票的候選者就會成為領導節點。如果候選節點或當前領導節點發現了更新的領導者，就會主動退回跟隨狀態。

領導節點全權負責管理復制日誌，也就是從客戶端接收請求，復制到跟隨節點，並告訴跟隨節點何時可以處理這些請求。如果領導節點故障或斷開連接，就會重新進行選舉。可見，領導節點的存在大大簡化了共識演算法的設計。

在上面的圖中出現了任期（term）這個詞。領導者並不是一直「在位」的，工作一段時間之後，就會選舉出新的領導者來接替它。

由上圖可見，藍色表示選舉時間段，綠色表示選舉出的領導者在位的時間段，這兩者合起來即稱作一個任期，其計數值是自增的。任期的值就可以在邏輯上充當時間戳，每個節點都會保存一份自己所見的最新任期值，稱為currentTerm。另外，如果因為票數相同，沒能選出領導，就會立即再發起新的選舉。

如果一個或多個跟隨節點在選舉超時（election timeout）內沒有收到領導節點的心跳（一個名為AppendEntries的RPC消息，本意是做日誌復制用途，但此時不攜帶日誌數據），就會發起選舉流程：

根據其他節點回復的消息，會出現如下三種結果：

獲得多數票的節點只要當選，就會立即給其他所有節點發送AppendEntries，避免再次選舉。另外，在同一任期內，每個節點只能投一票，並且先到先得（first-come-first-served），也就是會把票投給RequestVote消息第一個到達的那個節點。

至於上面的第三種情況，也就是所謂「split vote」現象，容易在很多跟隨者變成候選者時出現，因為沒有節點能得到多數票，選舉有可能無限繼續下去。所以，Raft設置的選舉超時並不是完全一樣的，而是有些許隨機性，來盡量使得投票能夠集中到那些較「快」的節點上。

領導節點選舉出來後，集群就可以開始處理客戶端請求了。前面已經說過，每個節點都維護著一個復制日誌的隊列，它們的格式如下圖所示。

可見，日誌由一個個按序排列的entry組成。每個entry內包含有請求的數據，還有該entry產生時的領導任期值。在論文中，每個節點上的日誌隊列用一個數組log[]表示。

當客戶端發來請求時，領導節點首先將其加入自己的日誌隊列，再並行地發送AppendEntries RPC消息給所有跟隨節點。領導節點收到來自多數跟隨者的回復之後，就認為該請求可以提交了（見圖中的commited entries）。然後，領導節點將請求應用（apply）到復制狀態機，並通知跟隨節點也這樣做。這兩步做完後，就不會再回滾。
這種從提交到應用的方式與最基礎的一致性協議——兩階段提交（2PC）有些相似，但Raft只需要多數節點的確認，並不需要全部節點都可用。

注意在上圖中，領導節點和4個跟隨節點的日誌並不完全相同，這可能是由於跟隨節點反應慢、網路狀況差等原因。領導節點會不斷地重試發送AppendEntries，直到所有節點上的日誌達到最終一致，而不實現強一致性。這就是CAP理論中在保證P的情況下，C與A無法兼得的體現。

日誌復制的過程仍然遺留了一個問題：如果領導或者跟隨節點發生異常情況而崩潰，如何保證日誌的最終一致性？它屬於下面的安全性問題中的一部分，稍後會解答它。

安全性是施加在領導選舉、日誌復制兩個解決方案上的約束，用於保證在異常情況下Raft演算法仍然有效，不能破壞一致性，也不能返回錯誤的結果。所有分布式演算法都應保障安全性，在其基礎上再保證活性（liveness）。

Raft協議的安全性保障有5種，分別是：選舉安全性（election safety）、領導者只追加（leader append-only）、日誌匹配（log matching）、領導者完全性（leader completeness）、狀態機安全性（state machine safety） 。下面分別來看。

選舉安全性是指每個任期內只允許選出最多一個領導。如果集群中有多於一個領導，就發生了腦裂（split brain）。根據「領導選舉」一節中的描述，Raft能夠保證選舉安全，因為：

在講解日誌復制時，我們可以明顯地看出，客戶端發出的請求都是插入領導者日誌隊列的尾部，沒有修改或刪除的操作。這樣可以使領導者的行為盡量簡單化，使之沒有任何不確定的行為，同時也作為下一節要說的日誌匹配的基礎。

日誌匹配的具體描述如下。
如果兩個節點的日誌隊列中，兩個entry具有相同的下標和任期值，那麼：

第一點自然由上一節的「領導者只追加」特性來保證，而第二點則由AppendEntries RPC消息的一個簡單機制來保證：每條AppendEntries都會包含最新entry之前那個entry的下標與任期值，如果跟隨節點在對應下標找不到對應任期的日誌，就會拒絕接受並告知領導節點。

有了日誌匹配特性，就可以解決日誌復制中那個遺留問題了。假設由於節點崩潰，跟隨節點的日誌出現了多種異常情況，如下圖。

注意圖中不是6個跟隨節點，而是6種可能的情況。比如a和b是丟失了entry，c和d是有多餘的未提交entry，e和f則是既有丟失又有冗餘。這時領導節點就會找到兩個日誌隊列中最近一條匹配的日誌點，將該點之後跟隨節點的所有日誌都刪除，然後將自己的這部分日誌復制給它。例如對於上圖中的情況e來說，最近一條匹配的日誌下標為5，那麼5之後的所有entry都會被刪除，被替換成領導者的日誌。

領導者完全性是指，如果有一條日誌在某個任期被提交了，那麼它一定會出現在所有任期更大的領導者日誌里。這也是由兩點來決定的：

根據這兩個描述，每次選舉出的領導節點一定包含有最新的日誌，因此只存在跟隨節點從領導節點更新日誌的情況，而不會反過來，這也使得一致性邏輯更加簡化，並且為下面的狀態機安全性提供保證。

狀態機安全性是說，如果一個節點已經向其復制狀態機應用了一條日誌中的請求，那麼對於其他節點的同一下標的日誌，不能應用不同的請求。這句話就很拗口了，因此我們來看一種意外的情況。

這里就有問題了，在時刻c的日誌與新領導者的日誌發生了沖突，此時狀態機是不安全的。
為了解決該問題，Raft不允許領導者在當選後提交「前任」的日誌，而是通過日誌匹配原則，在處理「現任」日誌時將之前的日誌一同提交。具體方法是：在領導者任期開始時，立刻提交一條空的日誌，所以上圖中時刻c的情況不會發生，而是像時刻e一樣先提交任期4的日誌，連帶提交任期2的日誌。就算此時S1再崩潰，S5也不會重新被選舉了。

如果想要更直觀地理解Raft，建議參考 這里 ，是一個用動畫來描述該演算法的網頁，形象生動。

Ⅶ 共識演算法（分布式下的一致性演算法)

共識演算法（分布式下的一致性演算法)

業務場景：

達到的效果：可以保證在過半節點正常的情況下，所有的寫入操作不會丟失。

Zab協議並不保證強一致性，也不是弱一致性，而是在一定限度內的強一致性慎轎山。

缺點：

缺點：

區塊鏈1.0時代：比特幣，作用就是去中心化的貨幣，無國界的貨幣，並且可以匿名性的洗錢
區塊鏈2.0時代：代表以太坊，引入了智能合約的概念，發揮其 去中心化和不可篡改的特性，可以實現類似於 追溯、拍賣、投票等業務場景。

區塊鏈技術的實用價值：
無國界虛擬貨幣：比如比特幣

模擬一個拍賣（盲拍）的業務場景（發布一個智能合約）：
https://solidity.readthedocs.io/en/latest/solidity-by-example.html#simple-open-auction

普通拍賣可能存在的問題：

商家A對一件商品公開自己要拍賣，智能合約在規定的時間會開始接收競拍（參與競拍的人需要支付保證金（以太幣）），在競拍結束之後，價格最高的人會完成支付，帆空其它的買家的保證金會全額退回。
然後成功競拍者可以線下去找賣家，證明自己的身份，然後獲得競拍品

優點：

工作量證明（ PoW ）通過計算一個數值（ nonce ），使得拼揍上交易數據後內容的 Hash 值滿足規定的上限。在節點成功找到滿足的Hash值之後，會馬上對全網進行廣播打包區塊，網路的節點收到廣播打包區塊，會立刻對其進行驗證

舉個例子，給定的一個基本的字元串」Hello, world!」，我們給出的工作量要求是，可以在這個字元串後面添加一個叫做nonce的整數值，對變更後（添加nonce)的字元串進行SHA256哈希運算，
如果得到的哈希結果（以16進制的形式表示）是以」0000」開頭的，則驗證通過。為了達到這個工作量證明的目標。我們需要不停的遞增nonce值，對得到的新字元串進行SHA256哈希運算。
按照這個規則，我們需要經過4251次計算才能找到恰好前4位為0的哈希散列。計算完之後，然後廣播到臨近的節點，臨近的節點會先驗算交易是否合法（金額是否異常），再驗證hash值是否滿足要求，都滿足的話，就會把這個數據塊添加到自己的賬本中。

優點：

缺點：

計算難度值會因為 股東持有的 幣齡而降低，為挖礦無形之中提升了壁壘，股東更容易算出結果值（難度更低），從而避免過度的算力競爭，節省電力，提升系統的穩定性。
因為從人性的角度，股東更不願意讓不安全的現象發生（比如攻擊主鏈)，因為會造成信用降低，從而自己的礦幣貶值。讓股東擁有更多的記賬權，讓主鏈更安全寬中。

擴展可以參考我之前寫過的zab專欄博客
https://www.jianshu.com/nb/32551354

Ⅷ raft:分布式一致性演算法筆記

在開始下一部分內容之前，可以先玩下 raft演基談示 ，不過後面第三章的圖文解析將用更詳細的演示圖。

在開始之前，先介紹一個 模擬raft的工具 ,如下圖：

這部分內容，會根據不同場景解釋第二章中的規則；

場景1：所有節點都正常

場景2：leader節點宕機，剩下4個節點參與選舉
四節點選舉時，存在兩種情況（1、一個候選者獲取多數選票，2、兩個候選者各獲得一半選票），不過這里合並一起講。

場景3：宕機節點重啟，並很快到達選舉超時計時
這種情況實際包含了s4正常重新加入集群的情況，只不過前面多了一點插曲

場景4：某個follower節點在某段時間因為網路問題無法收到leader的心跳請求，在這段時間內成為candidate，在發送vote請求時，網路又恢復正常

以上均是不含日誌情況下的選舉（日誌條數一樣的情況類似），下面將分析日誌條數不一樣的場景

首先先模擬場景（這個模擬也是模擬腦裂的場景，只不過這個模擬工具無法實現網路阻隔，但是這難不倒我們，我們可以分步來）

當candidate和follower日誌不同的時候，選舉情況看似復雜，其實是歸結起來就兩句話：日誌里最後一個log entry的term更大的日誌更加新，如果這個term相等，那麼最後個log entry 的index更大的日誌更新。

場景1、leader固定一個，新增日誌順序復制

場景2、在leader復制完日誌收到大多數確認之後，發生網路問題，leader切到其他節點。

那麼 往期的多數復制的日誌什麼時候提交 呢？請看下圖：

這里就演示了，即便大多數復制的內容也可能被覆蓋。如果在步驟（9）中s1在完成多數節點復制後提交了往期的日誌並執行到狀態機，但是還沒將提交狀態同步到其他節點，或者已經同步了狀態。此時S5發起的vote請求依然能悉戚成為leader，順利搏陸碰完成（9）之後的流程，這樣就覆蓋了已提交的log,與狀態機的狀態不一致了。
那為什麼當期提交就沒問題呢？
當期的leader能保證提交當期的日誌時最新的，往期的日誌leader不能保證是最新的 （比如s5的第四個log entry才是整個集群最新的日誌記錄）。

那麼只有在多數復制後，又有新的當期日誌（肯定是所有節點中最新的）提交，才能順帶往往期的一起提交：

3、leader的完整性（Leader Completeness Properties）驗證
論文中對leader的完整性（Leader Completeness Properties）用了一個很啰嗦的反證。其實就是只要是leader能確認提交的日誌肯定是多數復制了，且當前任期號的日誌肯定是最新的日誌，那麼下一任期選舉，一定會有包含該條最新日誌的節點參與選舉才能有節點得到多數選票，且一定是包含最新日誌的節點得到多數選票。

後面的成員配置邊和日誌壓縮等就先不玩了。。。

參考：
http://thesecretlivesofdata.com/raft/
https://raft.github.io/raftscope/index.html
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#51-raft-%E5%9F%BA%E7%A1%80
https://zhuanlan.hu.com/p/32052223
https://www.cnblogs.com/xybaby/p/10124083.html
https://blog.csdn.net/ppvqq/article/details/78572898

Ⅸ 一致性哈希演算法怎麼保證數據的一致性

一致性哈希（Consistent Hashing）和數據一致性沒有任何關系，這是個關鍵的理解錯誤。
一致性哈希只是保證在分布式結構下，哈希結果不會因為某個 node 掛掉而使得所有的鍵都不能用。在你的圖裡面，如果 node2 掛掉了，且沒有什麼自動錯誤恢復機制存在的話，讀寫 node2 的鍵會失敗而不是自動落到 node4 上面，所以不存在數據是否一致的問題

Ⅹ Paxos、Raft、ZAB、Gossip 分布式一致性演算法理解

以下各種工程實現都緩猜是一個在CAP之間tradeoff的過程

採用zab演算法，滿足寫強一致性（過半圓哪伏節點），讀最終一致性（所有節點）

採用租約機制確保並發寫入的順序性和採用hflush機制實現文件的最小副本可見性，滿足寫強一致性（滿足hfds最小副本數，其它副本hdfs自動非同步同步），讀最終一致性（所有副本），實現弱分區容錯性

kafka 讀寫都在leader上，配合acks=all，實現了讀寫強一致性，ISR機制確保了高可用性，副本機制實現了分區容錯性

hbase讀寫rowkey都在特定region上，實現讀寫強一致性，弱高可用性（region存在單點故障），分區容錯性hdfs來實現

redis3.0實現Redis-Cluster，採用Gossip協議進行redis元數據廣播，實現了元數據讀寫最終橘攜一致性，並且採用shard-master和shard-slave機制實現高可用性，分區容錯性
在分布式系統中，需要提供維護節點元數據信息的機制，所謂元數據是指節點負責哪些數據、主從屬性、是否出現故障等狀態信息。常見的元數據維護方式分為集中式和無中心式。Redis Cluster 採用 Gossip 協議實現了無中心式。

實現原理同redis-cluster，實現了讀寫最終一致性，高可用和分區容錯性

NameNode與JournalNode Cluster進行數據讀寫時核心點是需要大多數JN成功返回才可認為本次請求有效
在JournalNode Cluster中所有JN之間完全對等，不存在Primary/Secondary區別，實現原理類似paxos
QJM機制實現的是最終一致性

參考
https://blog.51cto.com/u_15220153/3175592