一致性哈希java

❶ java中值相同，hashcode一定相同嗎

兩者之間唯一的必然關系被你說反了，equls返回為true,則兩者的hashcode一定相等，意即相等的對象必須具有相等的哈希碼。每當equals方法被覆寫，通常需要重寫hashCode方法從而
保持對象行為的一致性。而具有相等的hashcode的兩個對象equals不一定成立。你可以這樣認為也行，hashcode是作為一個對象存儲的參考，hash表本身是一種散列表，在數據存儲這塊，功效比較大，而equals是相當於兩對象之間的屬性（成員變數）「相等」，意即具有相同的行為（方法）。或許這樣講起來理解比較的費勁。舉個例子，比如你定義class A有兩個屬性，int aA,aB,在定義一個class B也有兩個屬性，int bA,bB,然後覆寫hashcode方法，A類為return aA*aB;B類為return bA*bB.現在情況已經很顯然了，各自實例化一個對象:a,b,假如:a.aA=b.bA,a.aB=b.bB,相等，或者a.aA=b.bB,a.aB=b.bA兩個對象a,b的hashcode一定相等，當時你能說兩個對象相等嗎？顯然不能吧，a與b都是不同類的實例。連equals最基本的obj instance of A或是obj instance of B都不成立。如果是同一個類的不同對象，當兩者擁有相同hashcode的時候，則一定相等，或者equals成立的時候則hashcode一定為真，這也就是所謂的相等的對象具有行為一致性。

❷ 一致性hash演算法是什麼

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

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

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

構成哈希演算法的條件：

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

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

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

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

❸ 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演算法中的幾個核心問題進行一些探究。

❹ Java分布式系統處理分布式事務有哪些經典解決方

當我們在生產線上用一台伺服器來提供數據服務的時候，我會遇到如下的兩個問題：

1）一台伺服器的性能不足以提供足夠的能力服務於所有的網路請求。

2）我們總是害怕我們的這台伺服器停機，造成服務不可用或是數據丟失。

於是我們不得不對我們的伺服器進行擴展，加入更多的機器來分擔性能上的問題，以及來解決單點故障問題。 通常，我們會通過兩種手段來擴展我們的數據服務：

1）數據分區：就是把數據分塊放在不同的伺服器上（如：uid % 16，一致性哈希等）。

2）數據鏡像：讓所有的伺服器都有相同的數據，提供相當的服務。

對於第一種情況，我們無法解決數據丟失的問題，單台伺服器出問題時，會有部分數據丟失。所以，數據服務的高可用性只能通過第二種方法來完成——數據的冗餘存儲（一般工業界認為比較安全的備份數應該是3份，如：Hadoop和Dynamo）。 但是，加入更多的機器，會讓我們的數據服務變得很復雜，尤其是跨伺服器的事務處理，也就是跨伺服器的數據一致性。這個是一個很難的問題。 讓我們用最經典的Use Case：「A帳號向B帳號匯錢」來說明一下，熟悉RDBMS事務的都知道從帳號A到帳號B需要6個操作：

• 從A帳號中把余額讀出來。

• 對A帳號做減法操作。

• 把結果寫回A帳號中。

• 從B帳號中把余額讀出來。

• 對B帳號做加法操作。

• 把結果寫回B帳號中。

為了數據的一致性，這6件事，要麼都成功做完，要麼都不成功，而且這個操作的過程中，對A、B帳號的其它訪問必需鎖死，所謂鎖死就是要排除其它的讀寫操作，不然會有臟數據的問題，這就是事務。那麼，我們在加入了更多的機器後，這個事情會變得復雜起來：

1）在數據分區的方案中：如果A帳號和B帳號的數據不在同一台伺服器上怎麼辦？我們需要一個跨機器的事務處理。也就是說，如果A的扣錢成功了，但B的加錢不成功，我們還要把A的操作給回滾回去。這在跨機器的情況下，就變得比較復雜了。

2）在數據鏡像的方案中：A帳號和B帳號間的匯款是可以在一台機器上完成的，但是別忘了我們有多台機器存在A帳號和B帳號的副本。如果對A帳號的匯錢有兩個並發操作（要匯給B和C），這兩個操作發生在不同的兩台伺服器上怎麼辦？也就是說，在數據鏡像中，在不同的伺服器上對同一個數據的寫操作怎麼保證其一致性，保證數據不沖突？

同時，我們還要考慮性能的因素，如果不考慮性能的話，事務得到保證並不困難，系統慢一點就行了。除了考慮性能外，我們還要考慮可用性，也就是說，一台機器沒了，數據不丟失，服務可由別的機器繼續提供。 於是，我們需要重點考慮下面的這么幾個情況：

1）容災：數據不丟、節點的Failover

2）數據的一致性：事務處理

3）性能：吞吐量 、 響應時間

前面說過，要解決數據不丟，只能通過數據冗餘的方法，就算是數據分區，每個區也需要進行數據冗餘處理。這就是數據副本：當出現某個節點的數據丟失時可以從副本讀到，數據副本是分布式系統解決數據丟失異常的唯一手段。所以，在這篇文章中，簡單起見，我們只討論在數據冗餘情況下考慮數據的一致性和性能的問題。簡單說來：

1）要想讓數據有高可用性，就得寫多份數據。

2）寫多份的問題會導致數據一致性的問題。

3）數據一致性的問題又會引發性能問題

這就是軟體開發，按下了葫蘆起了瓢。

一致性模型

說起數據一致性來說，簡單說有三種類型（當然，如果細分的話，還有很多一致性模型，如：順序一致性，FIFO一致性，會話一致性，單讀一致性，單寫一致性，但為了本文的簡單易讀，我只說下面三種）：

1）Weak 弱一致性：當你寫入一個新值後，讀操作在數據副本上可能讀出來，也可能讀不出來。比如：某些cache系統，網路游戲其它玩家的數據和你沒什麼關系，VOIP這樣的系統，或是網路搜索引擎（呵呵）。

2）Eventually 最終一致性：當你寫入一個新值後，有可能讀不出來，但在某個時間窗口之後保證最終能讀出來。比如：DNS，電子郵件、Amazon S3，Google搜索引擎這樣的系統。

3）Strong 強一致性：新的數據一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統，RDBMS，Azure Table都是強一致性的。

從這三種一致型的模型上來說，我們可以看到，Weak和Eventually一般來說是非同步冗餘的，而Strong一般來說是同步冗餘的，非同步的通常意味著更好的性能，但也意味著更復雜的狀態控制。同步意味著簡單，但也意味著性能下降。 好，讓我們由淺入深，一步一步地來看有哪些技術：

Master-Slave

首先是Master-Slave結構，對於這種加構，Slave一般是Master的備份。在這樣的系統中，一般是如下設計的：

1）讀寫請求都由Master負責。

2）寫請求寫到Master上後，由Master同步到Slave上。

從Master同步到Slave上，你可以使用非同步，也可以使用同步，可以使用Master來push，也可以使用Slave來pull。 通常來說是Slave來周期性的pull，所以，是最終一致性。這個設計的問題是，如果Master在pull周期內垮掉了，那麼會導致這個時間片內的數據丟失。如果你不想讓數據丟掉，Slave只能成為Read-Only的方式等Master恢復。

當然，如果你可以容忍數據丟掉的話，你可以馬上讓Slave代替Master工作（對於只負責計算的節點來說，沒有數據一致性和數據丟失的問題，Master-Slave的方式就可以解決單點問題了） 當然，Master Slave也可以是強一致性的， 比如：當我們寫Master的時候，Master負責先寫自己，等成功後，再寫Slave，兩者都成功後返回成功，整個過程是同步的，如果寫Slave失敗了，那麼兩種方法，一種是標記Slave不可用報錯並繼續服務（等Slave恢復後同步Master的數據，可以有多個Slave，這樣少一個，還有備份，就像前面說的寫三份那樣），另一種是回滾自己並返回寫失敗。（註：一般不先寫Slave，因為如果寫Master自己失敗後，還要回滾Slave，此時如果回滾Slave失敗，就得手工訂正數據了）你可以看到，如果Master-Slave需要做成強一致性有多復雜。

Master-Master

Master-Master，又叫Multi-master，是指一個系統存在兩個或多個Master，每個Master都提供read-write服務。這個模型是Master-Slave的加強版，數據間同步一般是通過Master間的非同步完成，所以是最終一致性。 Master-Master的好處是，一台Master掛了，別的Master可以正常做讀寫服務，他和Master-Slave一樣，當數據沒有被復制到別的Master上時，數據會丟失。很多資料庫都支持Master-Master的Replication的機制。

另外，如果多個Master對同一個數據進行修改的時候，這個模型的惡夢就出現了——對數據間的沖突合並，這並不是一件容易的事情。看看Dynamo的Vector Clock的設計（記錄數據的版本號和修改者）就知道這個事並不那麼簡單，而且Dynamo對數據沖突這個事是交給用戶自己搞的。就像我們的SVN源碼沖突一樣，對於同一行代碼的沖突，只能交給開發者自己來處理。（在本文後後面會討論一下Dynamo的Vector Clock）

Two/Three Phase Commit

這個協議的縮寫又叫2PC，中文叫兩階段提交。在分布式系統中，每個節點雖然可以知曉自己的操作時成功或者失敗，卻無法知道其他節點的操作的成功或失敗。當一個事務跨越多個節點時，為了保持事務的ACID特性，需要引入一個作為協調者的組件來統一掌控所有節點(稱作參與者)的操作結果並最終指示這些節點是否要把操作結果進行真正的提交(比如將更新後的數據寫入磁碟等等)。

❺ java中的equals，hashcode的區別和聯系

equals
publicbooleanequals(Objectobj)
指示其他某個對象是否與此對象「相等」。
equals方法在非空對象引用上實現相等關系：
自反性：對於任何非空引用值x，x.equals(x)都應返回
true。
對稱性：對於任何非空引用值x和y，當且僅當
y.equals(x)返回true時，x.equals(y)才應返回
true。
傳遞性：對於任何非空引用值x、y和z，如果
x.equals(y)返回true，並且y.equals(z)返回
true，那麼x.equals(z)應返回true。
一致性：對於任何非空引用值x和y，多次調用
x.equals(y)始終返回true或始終返回false，前提是對象上
equals比較中所用的信息沒有被修改。
對於任何非空引用值x，x.equals(null)都應返回
false。
Object類的equals方法實現對象上差別可能性最大的相等關系；即，對於任何非空引用值
x和y，當且僅當x和y引用同一個對象時，此方法才返回true（x==y具有值true）。
注意：當此方法被重寫時，通常有必要重寫hashCode方法，以維護hashCode方法的常規協定，該協定聲明相等對象必須具有相等的哈希碼。

參數：
obj-要與之比較的引用對象。
返回：
如果此對象與obj參數相同，則返回true；否則返回false。
另請參見：
hashCode(),Hashtable

hashCode
publicinthashCode()
返回該對象的哈希碼值。支持此方法是為了提高哈希表（例如java.util.Hashtable提供的哈希表）的性能。
hashCode的常規協定是：
在Java應用程序執行期間，在對同一對象多次調用hashCode方法時，必須一致地返回相同的整數，前提是將對象進行
equals比較時所用的信息沒有被修改。從某一應用程序的一次執行到同一應用程序的另一次執行，該整數無需保持一致。
如果根據equals(Object)方法，兩個對象是相等的，那麼對這兩個對象中的每個對象調用
hashCode方法都必須生成相同的整數結果。
如果根據equals(java.lang.Object)方法，兩個對象不相等，那麼對這兩個對象中的任一對象上調用hashCode方法不要求一定生成不同的整數結果。但是，程序員應該意識到，為不相等的對象生成不同整數結果可以提高哈希表的性能。
實際上，由Object類定義的hashCode
方法確實會針對不同的對象返回不同的整數。（這一般是通過將該對象的內部地址轉換成一個整數來實現的，但是JavaTM編程語言不需要這種實現技巧。）

返回：
此對象的一個哈希碼值。
另請參見：
equals(java.lang.Object),
Hashtable

也就是說equals和hashCode的關系只是在於一個協定，equals默認判斷依據是對象是否相等，hashCode()得到對象的內存地址的一個特殊計算得到的值，協定內容是：equals相等的對象的hashCode值相等，所以要求重寫了equals之後重寫hashCode。

equals是判斷對象是否相等的方法。hashCode是得到對象hash值的方法，對象hash值默認是根據內存地址計算得到。equals默認表的是對象內存地址。

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

環割法（一致性 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 地址進行截斷，取全量長度進行測試。

❼ 一致性hash演算法是什麼

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

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

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

優點

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

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

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

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

❽ 一致性哈希 java實現 怎麼映射到圓環上

一致性哈希提出了在動態變化的Cache環境中，哈希演算法應該滿足的4個適應條件：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖區加入到系統中，那麼哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖區中去，而不會被映射到舊的緩沖集合中的其他緩沖區。（這段翻譯信息有負面價值的，當緩沖區大小變化時一致性哈希(Consistenthashing)盡量保護已分配的內容不會被重新映射到新緩沖區。）簡單的哈希演算法往往不能滿足單調性的要求，如最簡單的線性哈希：x→ax+bmod(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找到下行節點並獲得下行節點列表，然後要求上行節點修改其下行節點列表，這樣就恢復了路由關系。