分布式尋址算法-魔扣目錄

一、分布式尋址算法簡介

分布式尋址算法是很重要的內(nèi)容，不了解這些算法，也就不能透徹的了解各種分布式中間件的原理。簡單說一下這些高大上的尋址到底是個啥意思，比如在elasticsearch中，采用的是多分片，每個分片上存儲的是不一樣的數(shù)據(jù)，是一種并集關(guān)系。比如我們通過_id去搜索一條數(shù)據(jù)，elasticsearch怎么知道這個_id的數(shù)據(jù)是存在哪個分片上？再比如redis cluster中通過key去查詢一條數(shù)據(jù)，redis集群中怎么知道這個key在哪個節(jié)點上？所以這就是尋址算法要解決的問題。

簡單介紹三種分布式尋址算法

1 hash算法2 一致性hash算法3 hash slot

hash算法比較適合固定分區(qū)或者分布式節(jié)點的集群架構(gòu)，比如elasticsearch中primary shard是固定并且不能改變的。所以采用hash算法是一種不錯的選擇，當(dāng)然ES確實也是這么做的。感興趣的可以看我的另一篇關(guān)于ES的博客。https://www.cnblogs.com/hello-shf/p/11543480.html

shard = hash(routing) % number_of_primary_shards （routing默認_id）

一致性hash算法比較適合需要動態(tài)擴容的分布式架構(gòu)以及一些動態(tài)負載均衡的分布式中間件和RPC中間件。

redis cluster應(yīng)用的是hash slot實現(xiàn)的一致性hash尋址。

二、hash算法

比如在elasticsearch中，假如有3個primary shard。

shard = hash(_id) % 3;

插入一條數(shù)據(jù)，通過以上公式我們很容易能確認該數(shù)據(jù)存在了哪個分片上。按照_id查詢的是有同樣通過以上公式很容易找到該數(shù)據(jù)位于哪個分片上。

以上算法看上去一切都是那么美好，然鵝。。。

假如primary shard需要擴容意思也就是需要增加一個primary shard怎么辦？（僅僅是假如，elasticsearch primary shard是不可變的）hash公式變成下面這樣

shard = hash(_id) % 4;

是不是就會發(fā)生尋址錯誤？

這就意味著當(dāng)增加分區(qū)需要將原來各個分區(qū)上的數(shù)據(jù)按照shard = hash(_id) % 4的hash取模結(jié)果將數(shù)據(jù)搬運到對應(yīng)分區(qū)上去。假如當(dāng)有海量數(shù)據(jù)怎么辦？說實話很難辦。當(dāng)發(fā)現(xiàn)一個shard宕機，需要快速容災(zāi)處理時候，也是一樣的問題。

三、一致性hash

可以說一致性hash就是解決以上動態(tài)擴容和縮容問題而誕生的。在分布式架構(gòu)中如果不支持動態(tài)擴容和容災(zāi)，分布式=雞肋，沒毛病吧。

其實一致性hash聽起來那么牛X，其實也沒啥高級的，只不過是一種更加高級的hash取模運算而已。

如上所示，一般的hash環(huán)是hash取模運算的node = hash(key) % n;n取2^32，即形成了一個從0~32的hash環(huán)。尋址按照順時針進行查找最近的一個節(jié)點。

node = hash(key) % n

有4個節(jié)點按照IP取模即node = hash(IP) % n落在了如上圖所示的位置，這時一個請求，根據(jù)node = hash(key) % n求出該請求落在了如下圖所示位置，按照順時針查找，找到該請求命中節(jié)點2。這就是這么一個簡單的尋址過程。

擴容：

在原來4個節(jié)點的基礎(chǔ)上，增加一個節(jié)點5，依然根據(jù)根據(jù)IP取模即node = hash(IP) % n確定節(jié)點在hash環(huán)上的位置。如下圖所示。

可見原來的請求就命中了節(jié)點5，所以我們依然需要進行數(shù)據(jù)的遷移，但是只是部分的，只需要遷移1-2節(jié)點之間的數(shù)據(jù)即可。相對hash取模，一致性hash算法減少了擴容帶來的數(shù)據(jù)遷移量太大的問題。容災(zāi)同理。

但是一致性hash算法存在的問題也是很明顯的，因為節(jié)點很難均勻的落在hash環(huán)上。但是有效的減少了動態(tài)增刪節(jié)點帶來的數(shù)據(jù)遷移問題。

四、hash slot

hash slot即hash槽。redis cluster采用的正式這種hash槽算法實現(xiàn)的尋址。以redis cluster為例。

在redis cluster中固定的存在 16384 個hash slot。

hash slot = CRC16（key）%16384；

#CRC16算法可以簡單的理解為一種hash算法。詳見度娘。

這樣我們就能找到key對應(yīng)的hash slot。其實按照我的理解，hash slot就是在尋址和節(jié)點間加了一層映射關(guān)系。當(dāng)節(jié)點動態(tài)變化，只需要改變hash slot ==> 節(jié)點的映射，然后只需要遷移指定slot到新添加的節(jié)點即可。既減少了hash尋址帶來的數(shù)據(jù)全量遷移問題，相對一致性hash也使得負載均衡效果更加明顯。