資訊專欄INFORMATION COLUMN
摘要：好的哈希算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。一致性哈希算法的基本實現原理是將機器節點和值都按照一樣的算法映射到一個的圓環上。
一致性 hash
分布式過程中我們將服務分散到若干的節點上，以此通過集體的力量提升服務的目的。然而，對于一個客戶端來說，該由哪個節點服務呢？或者說對某個節點來說他分配到哪些任務呢？
強哈希考慮到單服務器不能承載，因此使用了分布式架構，最初的算法為 hash() mod n, hash()通常取用戶ID，n為節點數。此方法容易實現且能夠滿足運營要求。缺點是當單點發生故障時，系統無法自動恢復。同樣不也不能進行動態增加節點。
弱哈希為了解決單點故障，使用 hash() mod (n/m),
這樣任意一個用戶都有 m 個服務器備選，可由 client 隨機選取。
由于不同服務器之間的用戶需要彼此交互，所以所有的服務器需要確切的知道用戶所在的位置。
因此用戶位置被保存到 memcached 中。當一臺發生故障，client 可以自動切換到對應 backup，由于切換前另外 1 臺沒有用戶的 session，因此需要 client 自行重新登錄。
好處
他比強哈希的好處是：解決了單點問題。
缺點
但存在以下問題：負載不均衡，尤其是單臺發生故障后剩下一臺會壓力過大；不能動態增刪節點；節點發生故障時需要 client 重新登錄
一致性 hash 算法一致性 hash 算法提出了在動態變化的 Cache 環境中，判定哈希算法好壞的四個定義：
平衡性(Balance)平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。
單調性(Monotonicity)單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
分散性(Spread)在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。
當終端希望通過哈希過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。
這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。
負載(Load)負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么對于一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。
與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。
普通的哈希算法（也稱硬哈希）采用簡單取模的方式，將機器進行散列，這在cache環境不變的情況下能取得讓人滿意的結果，但是當cache環境動態變化時，
這種靜態取模的方式顯然就不滿足單調性的要求（當增加或減少一臺機子時，幾乎所有的存儲內容都要被重新散列到別的緩沖區中）。
一致性哈希算法有多種具體的實現，包括 Chord 算法)，KAD 算法等實現，以上的算法的實現都比較復雜。
這里介紹一種網上廣為流傳的一致性哈希算法的基本實現原理，感興趣的同學可以根據上面的鏈接或者去網上查詢更詳細的資料。
一致性哈希算法的基本實現原理是將機器節點和key值都按照一樣的hash算法映射到一個0~2^32的圓環上。
當有一個寫入緩存的請求到來時，計算 Key 值 k 對應的哈希值 Hash(k)，如果該值正好對應之前某個機器節點的 Hash 值，則直接寫入該機器節點，
如果沒有對應的機器節點，則順時針查找下一個節點，進行寫入，如果超過 2^32 還沒找到對應節點，則從0開始查找(因為是環狀結構)。
如圖 1 所示:
圖 1 中 Key K 的哈希值在 A 與 B 之間，于是 K 就由節點B來處理。
另外具體機器映射時，還可以根據處理能力不同，將一個實體節點映射到多個虛擬節點。
經過一致性哈希算法散列之后，當有新的機器加入時，將只影響一臺機器的存儲情況，
例如新加入的節點H的散列在 B 與 C 之間，則原先由 C 處理的一些數據可能將移至 H 處理，
而其他所有節點的處理情況都將保持不變，因此表現出很好的單調性。
而如果刪除一臺機器，例如刪除 C 節點，此時原來由 C 處理的數據將移至 D 節點，而其它節點的處理情況仍然不變。
而由于在機器節點散列和緩沖內容散列時都采用了同一種散列算法，因此也很好得降低了分散性和負載。
而通過引入虛擬節點的方式，也大大提高了平衡性。
實現代碼consitent-hashing原文地址
consitent-hashing
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76734.html
摘要：一致性哈希算法能盡可能減少了服務器數量變化所導致的緩存遷移。哈希算法首先，一致性哈希算法依賴于普通的哈希算法。我們以下面四個量化的指標對基于不同哈希函數的一致性哈希算法進行評測。 一致性哈希算法在分布式緩存領域的 MemCached，負載均衡領域的 Nginx 以及各類 RPC 框架中都有廣泛的應用，它主要是為了解決傳統哈希函數添加哈希表槽位數后要將關鍵字重新映射的問題。 本文會介紹一...
摘要：是我們一直擁有的，即我們有，。中的迭代器中的迭代器主要包括方法。在遍歷過程中，如果已經遍歷的數組上的內容變化了，迭代器不會拋出異常。這就是迭代器弱一致的表現。總結的弱一致性主要是為了提升效率，是一致性與效率之間的一種權衡。 本文將用到Java內存模型的happens-before偏序關系（下文將簡稱為hb）以及ConcurrentHashMap的底層模型相關的知識。happens-be...
摘要：不允許隱式轉換的是強類型，允許隱式轉換的是弱類型。拿一段代碼舉例在使用調用函數的時候會先生成一個類模板運行時生成，執行的時候會生成類模板，執行的時候會生成類模板。 0 x 01 引言 今天和一個朋友討論 C++ 是強類型還是弱類型的時候，他告訴我 C++ 是強類型的，他和我說因為 C++ 在寫的時候需要 int，float 等等關鍵字去定義變量，因此 C++ 是強類型的，我告訴他 C+...
摘要：數據結構和算法樹快速排序，堆排序，插入排序其實八大排序算法都應該了解一致性算法，一致性算法的應用的內存結構。如何存儲一個的。八大排序算法一定要手敲一遍快排，堆排尤其重要。面試是一個雙向選擇的過程，不要抱著畏懼的心態去面試，不利于自己的發揮。 前言 16年畢業到現在也近兩年了，最近面試了阿里集團（菜鳥網絡，螞蟻金服），網易，滴滴，點我達，最終收到點我達，網易offer，螞蟻金服二面掛掉，...
閱讀 1071·2023-04-25 14:35
閱讀 2832·2021-11-16 11:45
閱讀 3421·2021-09-04 16:48
閱讀 2187·2021-08-10 09:43
閱讀 534·2019-08-30 13:17
閱讀 1627·2019-08-29 13:27
閱讀 892·2019-08-26 13:58
閱讀 2158·2019-08-26 13:48
