負載均衡--一致性hash演算法
有沒有好奇過redis、memcache等是怎麼實現集群負載均衡的呢？
其實他們都是通過一致性hash演算法實現節點調度的。
講一致性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。一般的，在一致性哈希演算法中，如果增加一台伺服器，則受影響的數據僅僅是新伺服器到其環空間中前一台伺服器（即順著逆時針方向行走遇到的第一台伺服器）之間數據，其它不會受到影響。
綜上所述，一致性哈希演算法對於節點的增減都只需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性。
我用golang做了個簡單版，官方也有package大家可以參考討論一下：
鏈接Consistent Hashing
推薦閱讀：