有沒有好奇過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 inthashSortedNodes []uint32circle map[uint32]stringnodes 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 nodefor i := 0; i < c.numOfVirtualNode; i++ {virtualKey := getVirtualKey(i, node)c.circle[virtualKey] = nodec.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://www.cnblogs.com/starluke/p/11997694.html
·END·
PHP開源社群進階·提升·漲薪
crc32算法_一緻性hash算法負載均衡