一致性演算法

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

在做伺服器負載均衡時候可供選擇的負載均衡的演算法有很多，包括： 輪循演算法（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實現。點擊下載

『貳』 java中哪些地方實現了一致性hash演算法

關於一致性Hash演算法，在我之前的博文中已經有多次提到了，MemCache超詳細解讀一文中"一致性Hash演算法"部分，對於為什麼要使用一致性Hash演算法、一致性Hash演算法的演算法原理做了詳細的解讀。

演算法的具體原理這里再次貼上：

先構造一個長度為232的整數環（這個環被稱為一致性Hash環），根據節點名稱的Hash值（其分布為[0, 232-1]）將伺服器節點放置在這個Hash環上，然後根據數據的Key值計算得到其Hash值（其分布也為[0, 232-1]），接著在Hash環上順時針查找距離這個Key值的Hash值最近的伺服器節點，完成Key到伺服器的映射查找。

這種演算法解決了普通余數Hash演算法伸縮性差的問題，可以保證在上線、下線伺服器的情況下盡量有多的請求命中原來路由到的伺服器。

當然，萬事不可能十全十美，一致性Hash演算法比普通的余數Hash演算法更具有伸縮性，但是同時其演算法實現也更為復雜，本文就來研究一下，如何利用Java代碼實現一致性Hash演算法。在開始之前，先對一致性Hash演算法中的幾個核心問題進行一些探究。

『叄』 一致性哈希演算法怎麼保證數據的一致性

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

『肆』 一致性哈希的哈希演算法

一致性哈希提出了在動態變化的Cache環境中，哈希演算法應該滿足的4個適應條件： 單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖區加入到系統中，那麼哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖區中去，而不會被映射到舊的緩沖集合中的其他緩沖區。（這段翻譯信息有負面價值的，當緩沖區大小變化時一致性哈希(Consistent hashing)盡量保護已分配的內容不會被重新映射到新緩沖區。）
簡單的哈希演算法往往不能滿足單調性的要求，如最簡單的線性哈希：
x → ax + b mod (P)在上式中，P表示全部緩沖的大小。不難看出，當緩沖大小發生變化時(從P1到P2)，原來所有的哈希結果均會發生變化，從而不滿足單調性的要求。
哈希結果的變化意味著當緩沖空間發生變化時，所有的映射關系需要在系統內全部更新。而在P2P系統內，緩沖的變化等價於Peer加入或退出系統，這一情況在P2P系統中會頻繁發生，因此會帶來極大計算和傳輸負荷。單調性就是要求哈希演算法能夠應對這種情況。 負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希演算法應能夠盡量降低緩沖的負荷。
從表面上看，一致性哈希針對的是分布式緩沖的問題，但是如果將緩沖看作P2P系統中的Peer，將映射的內容看作各種共享的資源(數據，文件，媒體流等)，就會發現兩者實際上是在描述同一問題。
路由演算法
在一致性哈希演算法中，每個節點(對應P2P系統中的Peer)都有隨機分配的ID。在將內容映射到節點時，使用內容的關鍵字和節點的ID進行一致性哈希運算並獲得鍵值。一致性哈希要求鍵值和節點ID處於同一值域。最簡單的鍵值和ID可以是一維的，比如從0000到9999的整數集合。
根據鍵值存儲內容時，內容將被存儲到具有與其鍵值最接近的ID的節點上。例如鍵值為1001的內容，系統中有ID為1000，1010，1100的節點，該內容將被映射到1000節點。
為了構建查詢所需的路由，一致性哈希要求每個節點存儲其上行節點(ID值大於自身的節點中最小的)和下行節點(ID值小於自身的節點中最大的)的位置信息(IP地址)。當節點需要查找內容時，就可以根據內容的鍵值決定向上行或下行節點發起查詢請求。收到查詢請求的節點如果發現自己擁有被請求的目標，可以直接向發起查詢請求的節點返回確認；如果發現不屬於自身的范圍，可以轉發請求到自己的上行/下行節點。
為了維護上述路由信息，在節點加入/退出系統時，相鄰的節點必須及時更新路由信息。這就要求節點不僅存儲直接相連的下行節點位置信息，還要知道一定深度(n跳)的間接下行節點信息，並且動態地維護節點列表。當節點退出系統時，它的上行節點將嘗試直接連接到最近的下行節點，連接成功後，從新的下行節點獲得下行節點列表並更新自身的節點列表。同樣的，當新的節點加入到系統中時，首先根據自身的ID找到下行節點並獲得下行節點列表，然後要求上行節點修改其下行節點列表，這樣就恢復了路由關系。

『伍』 一致性hash演算法虛擬節點多少比較合適

MD5不是 只有知道密鑰才能生成相同的信息摘要，是需要知道原數據才能生成相同的摘要(不過可以碰撞破解)。在信息安全上，MD5/SHA經常和RSA一起使用做數字簽名。 樓主說的一致性hash演算法，估計是指Memcache等分布式KV資料庫的一致性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、節點失效、通信失敗等問題。

『柒』 ahp法中平均隨機一致性指標的演算法是用什麼軟體完成的

層次分析法（Ahalytic Hie。by PrOCess簡稱 AHP）是美國運籌學家 T.L.Saay於 20世紀 70年代初提出的一種簡便、靈活而又實用的多准則決策方法,用於處理諸如社會、經濟和科學管理領域所經常遇到一些由相互關聯、相互制約的眾多因素構成的復雜而又缺少定量數據系統的建模問題。運用層次分析法需要通過決策者反復地回答問題,對同一層次的各元素關於上一層次中某一準則的重要性進行比較,從而構造出一些兩兩比較的判斷矩陣 A=h入。（稱為成對比較矩陣人這些成對比較矩陣應滿足如下條件: （ l）＊ti 0 （2） siaji 二 l（ ）＊n= l 按照事物邏輯要求,該矩陣還應具備一致性,即滿足:

『捌』 一致性hash和hash的區別

一致性哈希基本解決了在P2P環境中最為關鍵的問題——如何在動態的網路拓撲中分布存儲和路由。每個節點僅需維護少量相鄰節點的信息，並且在節點加入/退出系統時，僅有相關的少量節點參與到拓撲的維護中。所有這一切使得一致性哈希成為第一個實用的DHT演算法。
但是一致性哈希的路由演算法尚有不足之處。在查詢過程中，查詢消息要經過O(N)步(O(N)表示與N成正比關系，N代表系統內的節點總數)才能到達被查詢的節點。不難想像，當系統規模非常大時，節點數量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。換個角度來看，即使用戶能夠忍受漫長的時延，查詢過程中產生的大量消息也會給網路帶來不必要的負荷。
英文解釋
Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots.