數據一致性演算法

① 同時寫文件和資料庫，如何保證數據一致性

1.計算文件 md5 ；
2.記日誌（比如某張表中插入一條記錄包含 md5, filepath ；或者日誌文件 -> md5 為文件名，內容 filepath ）；

----優化

思考：
考慮到zookeeper的數據慶差一致性原理，有個機制是3PC， paxos演算法
leader 選譽睜皮舉，server 接受leader 的 事務請求，給予響應，leader 接收到大多數的成功響應，再次給server發送事物提交請求，同時告訴client,事物ok

這是對多節點的一個事物操作，而題目是對單節點的一個事物的操作，事物分早譽為多個步驟。

② 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

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

環割法（一致性 hash）環割法的原理如下：

1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字元串的所有 hash 值。

2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。

3. 輸入字元串的時候計算輸入字元串的 hash 值，查看 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為數據的分片。

數據比較

下面將通過測試對環割法和跳躍法的性能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。

• 數據源：現場數據 350595 條

• 測試經過：

  1. 通過各自的測試方法執行對於測試數據的分片任務。

  2. 測試方法：記錄分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。

  3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。

④ 共識演算法：Raft

上篇講到了「拜占庭將軍問題」：多個拜占庭將軍要如何在可能有叛徒、信使可能被策反或者暗殺的情況下達成是否要進攻的一致性決定？還不了解的先看看上一篇 《拜占庭將軍問題》 。這篇主要是介紹簡化版拜占庭將軍問題的解決方案：Raft 共識演算法。

所以將拜占庭將軍問題根據常見的工作上的問題進行簡化： 假設將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們如何達成一致性決定？

對於這個簡化後的問題，有許多解決方空跡案，第一個被證明的共識演算法是 Paxos，由拜占庭將軍問題的作者 Leslie Lamport 在1990年提出，最初以論文難懂而出名，後來這哥們在2001重新發了一篇簡單版的論文 Paxos Made Simple ，然而還是挺難懂的。

因為 Paxos 難懂，難實現，所以斯坦福大學的教授在2014年發表了新的分布式協議 Raft。與 Paxos 相比，Raft 有著基本相同運行則升效率，但是更容易理解，也更容易被用在系統開發上。

我們還是用拜占庭將軍的例子來幫助理解 Raft。

Raft 的解決方案大概可以理解成 先在所有將軍中選出一個大將軍，所有的決定由大孫虧老將軍來做。 選舉環節 ：比如說現在一共有3個將軍 A, B, C，每個將軍都有一個 隨機時間 的倒計時器，倒計時一結束，這個將軍就會把自己當成大將軍候選人，然後派信使去問其他幾個將軍，能不能選我為總將軍？假設現在將軍A倒計時結束了，他派信使傳遞選舉投票的信息給將軍B和C，如果將軍B和C還沒把自己當成候選人（倒計時還沒有結束），並且沒有把選舉票投給其他，他們把票投給將軍A，信使在回到將軍A時，將軍A知道自己收到了足夠的票數，成為了大將軍。在這之後，是否要進攻就由大將軍決定，然後派信使去通知另外兩個將軍，如果在一段時間後還沒有收到回復（可能信使被暗殺），那就再重派一個信使，直到收到回復。

故事先講到這里，希望不做技術方面的朋友可以大概能理解 Raft 的原理，下面從比較技術的角度講講 Raft 的原理。

從拜占庭將軍的故事映射到分布式系統上，每個將軍相當於一個分布式網路節點，每個節點有 三種狀態：Follower，Candidate，Leader ，狀態之間是互相轉換的，可以參考下圖，具體的後面說。

每個節點上都有一個倒計時器 (Election Timeout)，時間隨機在 150ms 到 300ms 之間。有幾種情況會重設 Timeout：

在 Raft 運行過程中，最主要進行兩個活動：

假設現在有如圖5個節點，5個節點一開始的狀態都是 Follower。

在一個節點倒計時結束 (Timeout) 後，這個節點的狀態變成 Candidate 開始選舉，它給其他幾個節點發送選舉請求 (RequestVote)

其他四個節點都返回成功，這個節點的狀態由 Candidate 變成了 Leader，並在每個一小段時間後，就給所有的 Follower 發送一個 Heartbeat 以保持所有節點的狀態，Follower 收到 Leader 的 Heartbeat 後重設 Timeout。

這是最簡單的選主情況， 只要有超過一半的節點投支持票了，Candidate 才會被選舉為 Leader ，5個節點的情況下，3個節點 (包括 Candidate 本身) 投了支持就行。

一開始已經有一個 Leader，所有節點正常運行。

Leader 出故障掛掉了，其他四個 Follower 將進行重新選主。

4個節點的選主過程和5個節點的類似，在選出一個新的 Leader 後，原來的 Leader 恢復了又重新加入了，這個時候怎麼處理？在 Raft 里，第幾輪選舉是有記錄的，重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的，而現在的 Leader 則是 Term 2，所有原來的 Leader 會自覺降級為 Follower

假設一開始有4個節點，都還是 Follower。

有兩個 Follower 同時 Timeout，都變成了 Candidate 開始選舉，分別給一個 Follower 發送了投票請求。

兩個 Follower 分別返回了ok，這時兩個 Candidate 都只有2票，要3票才能被選成 Leader。

兩個 Candidate 會分別給另外一個還沒有給自己投票的 Follower 發送投票請求。

但是因為 Follower 在這一輪選舉中，都已經投完票了，所以都拒絕了他們的請求。所以在 Term 2 沒有 Leader 被選出來。

這時，兩個節點的狀態是 Candidate，兩個是 Follower，但是他們的倒計時器仍然在運行，最先 Timeout 的那個節點會進行發起新一輪 Term 3 的投票。

兩個 Follower 在 Term 3 還沒投過票，所以返回 OK，這時 Candidate 一共有三票，被選為了 Leader。

如果 Leader Heartbeat 的時間晚於另外一個 Candidate timeout 的時間，另外一個 Candidate 仍然會發送選舉請求。

兩個 Follower 已經投完票了，拒絕了這個 Candidate 的投票請求。

Leader 進行 Heartbeat， Candidate 收到後狀態自動轉為 Follower，完成選主。

以上是 Raft 最重要活動之一選主的介紹，以及在不同情況下如何進行選主。
總結：
1.每個節點一直有一個timeout，timeout結束就開始選自己為主節點；
2.主節點會輪詢從節點，從節點更新timeout；
3.選舉等級機制；

Raft 在實際應用場景中的一致性更多的是體現在不同節點之間的數據一致性，客戶端發送請求到任何一個節點都能收到一致的返回，當一個節點出故障後，其他節點仍然能以已有的數據正常進行。在選主之後的復制日誌就是為了達到這個目的。

一開始，Leader 和 兩個 Follower 都沒有任何數據。

客戶端發送請求給 Leader，儲存數據 「sally」，Leader 先將數據寫在本地日誌，這時候數據還是 Uncommitted (還沒最終確認，紅色表示)

Leader 給兩個 Follower 發送 AppendEntries 請求，數據在 Follower 上沒有沖突，則將數據暫時寫在本地日誌，Follower 的數據也還是 Uncommitted。

Follower 將數據寫到本地後，返回 OK。Leader 收到後成功返回， 只要收到的成功的返回數量超過半數 (包含Leader) ，Leader 將數據 「sally」 的狀態改成 Committed。( 這個時候 Leader 就可以返回給客戶端了)

Leader 再次給 Follower 發送 AppendEntries 請求，收到請求後，Follower 將本地日誌里 Uncommitted 數據改成 Committed。這樣就完成了一整個復制日誌的過程，三個節點的數據是一致的，

在 Network Partition 的情況下，部分節點之間沒辦法互相通信，Raft 也能保證在這種情況下數據的一致性。

一開始有 5 個節點處於同一網路狀態下。

Network Partition 將節點分成兩邊，一邊有兩個節點，一邊三個節點。

兩個節點這邊已經有 Leader 了，來自客戶端的數據 「bob」 通過 Leader 同步到 Follower。

因為只有兩個節點，少於3個節點，所以 「bob」 的狀態仍是 Uncommitted。所以在這里， 伺服器會返回錯誤給客戶端

另外一個 Partition 有三個節點，進行重新選主。客戶端數據 「tom」 發到新的 Leader，通過和上節網路狀態下相似的過程，同步到另外兩個 Follower。

因為這個 Partition 有3個節點，超過半數，所以數據 「tom」 都 Commit 了。

網路狀態恢復，5個節點再次處於同一個網路狀態下。但是這里出現了數據沖突 「bob" 和 「tom"

三個節點的 Leader 廣播 AppendEntries

兩個節點 Partition 的 Leader 自動降級為 Follower，因為這個 Partition 的數據 「bob」 沒有 Commit，返回給客戶端的是錯誤，客戶端知道請求沒有成功，所以 Follower 在收到 AppendEntries 請求時，可以把 「bob「 刪除，然後同步 」tom」，通過這么一個過程，就完成了在 Network Partition 情況下的復制日誌，保證了數據的一致性。

Raft 是能夠實現分布式系統強一致性的演算法，每個系統節點有三種狀態 Follower，Candidate，Leader。實現 Raft 演算法兩個最重要的事是：選主和復制日誌

參考鏈接：
Raft 官網： https://raft.github.io/

Raft 原理動畫 (推薦看看)： http://thesecretlivesofdata.com/raft/

⑤ 一致性hash演算法是什麼

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

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

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

構成哈希演算法的條件：

從哈希值不能反向推導出原始數據（所以哈希演算法也叫單向哈希演算法）。

對輸入數據非常敏感，哪怕原始數據只修改了一個 Bit，最後得到的哈希值也大不相同。

散列沖突的概率要很小，對於不同的原始數據，哈希值相同的概率非常小。

哈希演算法的執行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。

⑥ 一致性演算法（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實現。點擊下載

⑧ (3)一致性哈希vs哈希取模演算法

大數字取模 分散不同桶，兩個桶， 2、3、4、5 ，模 2 分桶：

擴容 新桶 ，模 3 來結果：

每次擴展 和 收縮 所有條目分布 重新計算 ，某些場景不可接受。文件 分布 在哪台 哈希演算法 決定 ，這個系統想要 加 一台機器時就需要 停 下來等所有文件 重新分布一次 才能對外提供服務，一台機器掉線盡管 只掉一部分數據 ，所有數據訪問路由 都會出問題 。 無法平滑的擴縮容 。

無狀態化 ，用多瞎輪個桶，  模 7個 ，開始只有兩個 3 和 6。同樣取模，分到不存在的桶，往下找第一個真實存桶。 2 和 3 分3 桶， 4 和 5分 6 桶。

添加新  編號4桶， 還是模 7 ：

3 號桶取模 小於等於 3 ，4 號桶只需從 6 號桶 拿走屬於它數字就可， 只調整一個桶重新分布 。即使有 1 億個桶，增加減少一個桶也只會影響一個桶的數據分布。

只需 和後面機器同步 數據 就可工作 ，同步到後一台機器再下線。 實現中 可以讓每台機器 同步一份自己前面機器的數據 ，即使 掉線也不影響 這部分數據服務。

問題：編號  6 的機桶下線 了， 沒有後一個桶了 ，哈希空間做成 環狀 ， 數據給 3  ：

一致性哈希還能 實現部分 的分布式系統 無鎖化 ， 演算法的確定性 ，分到哪個桶也是確定的就 不存在爭搶 ， 不需要分布式鎖 了。

查找效率：普通的哈希 查詢 一次 哈希計算就可以找到對應的桶了  O(1) ，一致性哈希需要將 排好序 的 桶組成 一個 鏈表 ，一路找下去k 個桶  O(k)

O(k) 對於哈希來說 不能忍 ，這個量級了用哈希沒意義，在排好序桶里查詢， 二分 把時間復雜度降到 O(logk) ，桶組合需不斷增減，鏈表實現二分肯定不行，用 跳轉錶快速跳轉 也能 實現 O(logk) 

跳轉表中， 每個桶記錄距離自己 1，2，4 距離的數字所存的桶，不管查詢落在哪個節點上，對整個哈希環上任意的查詢一次都 可以至少跳過一半的查詢空間？ ，這樣遞歸下去很快就可以定位到數據是存在哪個桶上。

上面只是 一種 ，很多一致性哈希 變體 。如選桶：上面順著數字選 對面 出現 第一個桶 ，其實也可選距離 數字最近桶 ，這樣跳轉表規則也變。同樣跳轉表不同演算法實現：  CAN，Chord，Tapestry，Pastry 這四種 DHT  

1、如果 6號 (裡面有數據)桶突然 宕機 了，是不是裡面的數據也丟失了？來不及將桶里的數據往前一個桶移？

答：實際情況會做冗餘，畫的是一個桶， 實際可能是三個

2、 「一致性」 是擴縮容前後數據在桶里的 分布是一致 的

3、 分布式 系統中怎麼 實現服務間的事務 ，目前有哪些通用做法，比如bbo?

用zk或者etcd這種分布式 鎖 服務，讓介面是 冪等， 可以反復重試

4、增加此類操作會 拖慢集群的性能 。如果某節點上一刻 宕機 ，往後新尺唯數據會進入 下一個節點 ，宕機節點 恢復 ，下一個節點還要同步原屬宕機的數據，復雜度為O(nlogn)，會不會代價略高？開源的ketama沒有同步數據這一做法，所以本質上只是近似一致性哈希，是不是一個trade-off的選擇？

答：這個場景不適合使用一致性哈希吧。以 負載均衡 為例，理論上是認為後台伺服器是 無狀態 的吧。所以宕機重啟 不應該有數據同步 的問題。

處理數據同步，raft強一致方案

對磨困信hash結果取余數 (hash() mod N)：機器編號從 0到N-1 ，hash()值 按N取模 ， 余數i，分發到編號i機器 。致命問題，宕機，落在該機器請求無法處理，有 (N-1)/N 伺服器的緩存數據重新計算；為何是 (N-1)/N 呢：3 台機器，hash值 1-6 分布：

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。

N個真實 節點,每個映射成 M個虛擬節 點, M*N個虛擬節點散列在圓環上. 真虛相互交錯分布，真down後,平均分到所有節點

訪問方法：

寫入緩存請求，Key值為K，計算器hash值Hash(K)， Hash(K) 對應於環中的某一個點，沒有映射到機器節點，順時針查找，直到找到有映射機器的節點，確定目標節點，超過2^32找不到，命中第一個。

缺陷：server數量很少時，環中分布不均勻，導致cache到server不均勻

例：用電話號碼group by，如移動用戶多，就會傾斜，reverse或加隨機數解決

hash取模對模數有要求，用奇數不用偶數，數據量大的時模數不好選，用上面辦法。

https://zhuanlan.hu.com/p/24440059

https://blog.csdn.net/hunandexingkong/article/details/70241933

⑨ paxos演算法是什麼

Paxos演算法是萊斯利·蘭伯特（Leslie Lamport，就是LaTeX中的＂La"，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞的一致性演算法。這個演算法被認為是類似演算法中最有效的。

蘭伯特提出的Paxos演算法包含2個部分：

一個是Basic Paxos演算法，描述的是多節點之間如何就某個值（提案Value）達成共識；

另一個是Multi-Paxos思想，描述的是執行多個Basic Paxos實例，就一系列值達成共識

可因為蘭伯特提到的Multi-Paxos思想，缺少代碼實現的必要細節（比如怎麼選舉領導者），所以在理解上比較難。Basic Paxos是Multi-Paxos思想的核心。

(9)數據一致性演算法擴展閱讀

背景

Paxos演算法解決的問題是一個分布式系統如何就某個值（決議）達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點執行相同的操作序列，那麼他們最後能得到一個一致的狀態。

為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。

一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。因此從20世紀80年代起對於一致性演算法的研究就沒有停止過。節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。