筆者帶你剖析三種常見的分散式路由演算法
Redis、Memcache也好，MySQL也罷。當達到單點可處理的容量上線時，Sharding是一種解決痛點最直接的解決方案。假設對存儲系統實施了Sharding，那麼我們究竟應該如何選取合適的路由演算法呢？本文列舉三種最常見的分散式理由演算法：硬Hash演算法、一致性Hash演算法，以及預分桶演算法。
1、硬Hash演算法：
即hash(routeKey) % dbSize，首先對路由Key進行Hash，然後對機器數量求余，這種分散式路由演算法非常簡單，同時也極其容易理解。
我們可以看一下MySQL分庫分表中間件Shark的路由演算法：
這種分散式路由演算法儘管簡單，但隨著後續數據持續膨脹，一旦達到單表存儲容量上線，我們仍然需要再次進行水平擴容，但這時的數據遷移成本就顯得非常昂貴了。假設從32個庫水平擴展到64個庫(伸縮都如此)，假設原routeKey是路由到第14個庫上，現在卻路由到了第45庫上，採用硬Hash演算法，嚴重依賴節點數量，基本上所有的數據都需要進行一次徹底的遷移，否則歷史數據將無法成功命中。
2、一致性Hash演算法：
相較於硬Hash演算法而言，一致性Hash儘管在實現和理解上更為複雜，但是帶來的好處仍然是顯而易見的。首先我們先簡單對一致性Hash演算法有個大致的了解。所謂一致性Hash，簡單來說，就是首先抽象出一個0～232的圓，然後hash(機器)映射到圓的各個位置上，接著hash(routeKey)採用順時針方式查找圓上最近的機器即可(如果超過232仍然找不到機器，則映射到第一台機器上)，如如A所示。
圖A：一致性hash演算法
假設中途我們對機器進行相應的擴容，比如從4台擴容到5台，那麼只有在圓上增加伺服器的地點逆時針方向的第一台伺服器上的routeKey相關資料庫會受到影響，這和硬Hash不同，至少大部分歷史數據還是可以正常命中的，影響面較小，如圖B所示。
圖B：一致性hash演算法擴容影響
相對於硬Hash演算法，儘管一致性Hash能夠適當的降低遷移成本，提升歷史數據的命中率，但是一致性Hash演算法有個不容忽視的問題，那便是一致性哈希演算法在機器節點太少時，容易因為節點分部不均勻從而造成數據傾斜，如圖C所示：
圖C：數據傾斜
上圖中，由於節點分配不均勻，將會導致大量的數據都在node1節點上命中，如果在並發較高的場景下，node1將會因為負載壓力被擴大至N倍導致宕機。為了解決這個問題，我們引入了虛擬節點機制，即對每一個機器節點計算多次(個)Hash，均勻分布到圓的各個位置上。具體做法可以在伺服器ip或主機名的後面增加編號來實現(比如192.168.1.1-01，192.168.1.1-02，192.168.1.1-03，192.168.1.1-0n)，實際上這麼做的目的就是把一個實際節點映射圓上的到多個位置上，多個位置其實都是指向的同一個目標物理節點。
那麼在Java中實現一致性Hash也是非常簡單的，這裡我們會使用到SortedMap。如下所示：
3、預分桶演算法：
預分桶演算法介於硬Hash演算法與一致性Hash演算法之間，算是取得一個平衡(對於歷史數據的遷移而言，硬Hash演算法是全遷移，而一致性Hash演算法則是部分遷移)，儘管犧牲了一定的靈活性，但是相較而言，數據的管理成本將會變得更低。因為硬Hash演算法與強一致性Hash演算法都是站在具體的數據維度上，而預分桶演算法則是在數據被包裹的基礎之上以slot為維度(儘管也是需要數據全部遷移，但只需要遷移上層的一段slot)。
Redis3.x以上版本提供了cluster功能，實際上這卻是一個服務端的sharding操作。一共劃分了16384個slot，假設redis有3台集群，那麼理論上這16384個slot將會均勻分布給這3個節點，每個redis節點負責存儲一段區間內的數據，通過閱讀Jedis客戶端源碼，我們不難發現，在做數據路由的時候，採用的做法是：
只需要算出routeKey對應的slot是哪一個，即可知道對應的Redis節點是哪一個，並且16384個slot是一開始就固定的，不會因為節點的伸縮而變化，也就是說，某個key一開始路由到第2048slot上，那麼它永遠也只會路由到這個固定的slot上，當運維同學擴容節點時，把slot移走就行了，不需要關心那麼多具體的數據應該怎麼遷移。
TAG:Hello架構 |