講一致性hash演算法前，先簡述一下求餘hash演算法：

hash(object)%N

一個快取伺服器宕機了，這樣所有對映到這臺伺服器的物件都會失效，我們需要把屬於該伺服器中的快取移除，這時候快取伺服器是 N-1 臺，對映公式變成了 hash(object)%(N-1) ；由於QPS升高，我們需要新增多一臺伺服器，這時候伺服器是 N+1 臺，對映公式變成了 hash(object)%(N+1) 。

1 和 2 的改變都會出現所有伺服器需要進行資料遷移。

一致性HASH演算法

一致性HASH演算法的出現有效的解決了上面普通求餘演算法在節點變動後面臨全部快取失效的問題：

type Consistent struct {    numOfVirtualNode int    hashSortedNodes  []uint32    circle           map[uint32]string    nodes            map[string]bool}

簡單地說，一致性雜湊將整個雜湊值空間組織成一個虛擬的圓環，如假設某空間雜湊函式H的值空間是0-2^32-1（即雜湊值是一個32位無符號整形），整個雜湊空間如下：

下一步將各個伺服器使用雜湊演算法計算出每臺機器的位置，具體可以使用伺服器的IP地址或者主機名作為關鍵字，並且是按照順時針排列：

//這裡我選擇crc32，具體情況具體安排func hashKey(host string) uint32 {    scratch := []byte(host)    return crc32.ChecksumIEEE(scratch)}

這裡我們假設三臺節點memcache經計算後位置如下：

//add the nodec.Add("Memcache_server01")c.Add("Memcache_server02")c.Add("Memcache_server03")func (c *Consistent) Add(node string) error {    if _, ok := c.nodes[node]; ok {        return errors.New("host already existed")    }    c.nodes[node] = true    // add virtual node    for i := 0; i < c.numOfVirtualNode; i++ {        virtualKey := getVirtualKey(i, node)        c.circle[virtualKey] = node        c.hashSortedNodes = append(c.hashSortedNodes, virtualKey)    }    sort.Slice(c.hashSortedNodes, func(i, j int) bool {        return c.hashSortedNodes[i] < c.hashSortedNodes[j]    })    return nil}

接下來使用相同演算法計算出資料的雜湊值,並由此確定資料在此雜湊環上的位置

假如我們有資料A、B、C和D，經過雜湊計算後位置如下：

根據一致性雜湊演算法，資料A就被繫結到了server01上，D被繫結到了server02上，B、C在server03上，是按照順時針找最近服務節點方法

這樣得到的雜湊環排程方法，有很高的容錯性和可擴充套件性：

假設server03宕機

可以看到此時A、C、B不會受到影響，只是將B、C節點被重定位到Server 1。一般的，在一致性雜湊演算法中，如果一臺伺服器不可用，則受影響的資料僅僅是此伺服器到其環空間中前一臺伺服器（即順著逆時針方向行走遇到的第一臺伺服器）之間資料，其它不會受到影響。

考慮另外一種情況，如果我們在系統中增加一臺伺服器Memcached Server 04：

此時A、D、C不受影響，只有B需要重定位到新的Server 4。一般的，在一致性雜湊演算法中，如果增加一臺伺服器，則受影響的資料僅僅是新伺服器到其環空間中前一臺伺服器（即順著逆時針方向行走遇到的第一臺伺服器）之間資料，其它不會受到影響。

綜上所述，一致性雜湊演算法對於節點的增減都只需重定位環空間中的一小部分資料，具有較好的容錯性和可擴充套件性。

連結 https://github.com/zhenorzz/consistent