一、分佈式尋址算法簡介
分佈式尋址算法是很重要的內容，不瞭解這些算法，也就不能透徹的瞭解各種分佈式中間件的原理。簡單說一下這些高大上的尋址到底是個啥意思，比如在elasticsearch中，採用的是多分片，每個分片上存儲的是不一樣的數據，是一種並集關係。比如我們通過_id去搜索一條數據，elasticsearch怎麼知道這個_id的數據是存在哪個分片上？再比如redis cluster中通過key去查詢一條數據，redis集群中怎麼知道這個key在哪個節點上？所以這就是尋址算法要解決的問題。
簡單介紹三種分佈式尋址算法
<code>1 hash算法2 一致性hash算法3 hash slot/<code>
hash算法比較適合固定分區或者分佈式節點的集群架構，比如elasticsearch中primary shard是固定並且不能改變的。所以採用hash算法是一種不錯的選擇，當然ES確實也是這麼做的。感興趣的可以看我的另一篇關於ES的博客。https://www.cnblogs.com/hello-shf/p/11543480.html
shard = hash(routing) % number_of_primary_shards （routing默認_id）
一致性hash算法比較適合需要動態擴容的分佈式架構以及一些動態負載均衡的分佈式中間件和RPC中間件。
redis cluster應用的是hash slot實現的一致性hash尋址。
二、hash算法
比如在elasticsearch中，假如有3個primary shard。
<code>shard = hash(_id) % 3;/<code>
插入一條數據，通過以上公式我們很容易能確認該數據存在了哪個分片上。按照_id查詢的是有同樣通過以上公式很容易找到該數據位於哪個分片上。
以上算法看上去一切都是那麼美好，然鵝。。。
假如primary shard需要擴容意思也就是需要增加一個primary shard怎麼辦？（僅僅是假如，elasticsearch primary shard是不可變的）hash公式變成下面這樣
<code>shard = hash(_id) % 4;/<code>
是不是就會發生尋址錯誤？
這就意味著當增加分區需要將原來各個分區上的數據按照shard = hash(_id) % 4的hash取模結果將數據搬運到對應分區上去。假如當有海量數據怎麼辦？說實話很難辦。當發現一個shard宕機，需要快速容災處理時候，也是一樣的問題。
三、一致性hash
可以說一致性hash就是解決以上動態擴容和縮容問題而誕生的。在分佈式架構中如果不支持動態擴容和容災，分佈式=雞肋，沒毛病吧。
其實一致性hash聽起來那麼牛X，其實也沒啥高級的，只不過是一種更加高級的hash取模運算而已。
如上所示，一般的hash環是hash取模運算的node = hash(key) % n;n取2^32，即形成了一個從0~32的hash環。尋址按照順時針進行查找最近的一個節點。
<code>node = hash(key) % n/<code>
有4個節點按照IP取模即node = hash(IP) % n落在瞭如上圖所示的位置，這時一個請求，根據node = hash(key) % n求出該請求落在瞭如下圖所示位置，按照順時針查找，找到該請求命中節點2。這就是這麼一個簡單的尋址過程。
擴容：
在原來4個節點的基礎上，增加一個節點5，依然根據根據IP取模即node = hash(IP) % n確定節點在hash環上的位置。如下圖所示。
可見原來的請求就命中了節點5，所以我們依然需要進行數據的遷移，但是隻是部分的，只需要遷移1-2節點之間的數據即可。相對hash取模，一致性hash算法減少了擴容帶來的數據遷移量太大的問題。容災同理。
但是一致性hash算法存在的問題也是很明顯的，因為節點很難均勻的落在hash環上。但是有效的減少了動態增刪節點帶來的數據遷移問題。
四、hash slot
hash slot即hash槽。redis cluster採用的正式這種hash槽算法實現的尋址。以redis cluster為例。
在redis cluster中固定的存在 16384 個hash slot。
<code>hash slot = CRC16（key）%16384；/<code>
#CRC16算法可以簡單的理解為一種hash算法。詳見度娘。
這樣我們就能找到key對應的hash slot。其實按照我的理解，hash slot就是在尋址和節點間加了一層映射關係。當節點動態變化，只需要改變hash slot ==> 節點的映射，然後只需要遷移指定slot到新添加的節點即可。既減少了hash尋址帶來的數據全量遷移問題，相對一致性hash也使得負載均衡效果更加明顯。
如上圖，如果我們有三個節點。redis cluster初始化時會自動均分給每個節點16384個slot。
當增加一個節點4，只需要將原來node1~node3節點部分slot上的數據遷移到節點4即可。在redis cluster中數據遷移並不會阻塞主進程。對性能影響是十分有限的。
如有錯誤的地方還請留言指正。
閱讀更多 sandag 的文章
