一緻性hash算法_了解一緻性hash算法以及TreeMap簡易實作示例

作者：niewj

來源：SegmentFault 思否

1. 算法說明

目的: 一緻性hash算法的目的, 就是為了解決2個問題:

1. hash算法中損毀節點對應的請求失敗;
2. 有節點損毀後, 請求落點不均勻問題;

2. 示例說明

一個hash環, 模拟節點數為1024個, 實際可用的節點有8個(比如線上實際的ip服務節點), 1024個模拟節點跟8個ip節點有均勻的映射關系;

我們模拟的環上有 1024 個虛拟節點, 真實可用的節點(可以想象為線上實際叢集有8個可用ip供存儲)

使用一緻性hash使用方法:

1. 環上的虛拟節點跟所有真實節點之間有個映射關系

   (1024個節點跟8個節點的映射, 用的是除8取模的對應關系,
              

   例如: 0, 8, 16, 24 都對應到node_0;
       1, 7, 15, 23都映射到node_1);
              

2. 發一個請求字元串, 我們計算出hash值, 除 1024 取模;
3. 将取模結果, 先映射到虛拟節點環上的點, 比如 "hello"的hashcode/1024 = 210
4. 查詢虛拟環和真實節點映射關系, 210對應的真實節點為 node_2; 于是, "hello" 就落到節點 node_2 上;
5. 我們可以調用 com.niewj.dsalg.ConsistentHashMock#dropBadNode("node_2") 來删除 node_2節點;

6. 删除 node_2 後, "hello"應該落在 211 上, 對應到環的真實映射, 是 node_3 , 于是, "hello"的請求就落到 node_3;

   這, 就是 一緻性hash算法!

3. 算法代碼示例:

- END -