數據結構與演算法：大數據之一致性哈希演算法

工程師常使用伺服器集群來設計和實現數據緩存。

以下是常見的策略。

1.無論是添加、查詢還是刪除數據，都先將數據的ID通過哈希函數轉換成一個哈希值，記為key.

2.如果目前機器有N台，則計算key%N的值，這個值就是該數據所屬的機器編號，無論是添加、刪除或者查詢

操作，都只在這台機器上運行。

試分析這種緩存策略可能帶來的問題，並提出改進的方案。

潛在問題：如果增加或者刪除機器，數據遷移的代價很大。

根據哈希函數得到哈希值結果%N

當機器數N發生變化是，所有數據必須重新計算哈希值，以及對新的機器數M取余，來決定各自數據的歸屬。

解決辦法：

一致性哈希演算法：

數據id通過哈希值計算後結果為0-2^32。

把這些數字首尾相連想向成一個閉合的環形。

通過哈希函數計算後的哈希值一次映射到環上的位置。然後順時針尋找離自己最近的一台機器。

那麼這個數據就歸屬於該機器。

比如下圖：

順時針尋找離自己最近的機器

data1歸屬在machine2上

data2歸屬在machine3上

data3和data4歸屬在machine1上

進行添加刪除操作時

沒有添加m3之前，data1和data2都是屬於m2的（m1到m2 的這一段歸m2管理）

添加m3之後，計算m3的id，映射到相應的位置。

然後m1-m3這一段就歸屬於m3了，那麼我們只需要把data1數據放到m3機器上即可。

其他數據都不需要改變。

刪除數據也是一樣的，只需要把該機器上的數據順時針複製到下一台機器上即可，不會影響到其他的機器。