前言
記得一年前分享過一篇《一致性 Hash 算法分析》，當(dāng)時只是分析了這個算法的實現(xiàn)原理限佩、解決了什么問題等。
但沒有實際實現(xiàn)一個這樣的算法裸弦，畢竟要加深印象還得自己擼一遍祟同，于是本次就當(dāng)前的一個路由需求來著手實現(xiàn)一次。
背景
看過《為自己搭建一個分布式 IM(即時通訊) 系統(tǒng)》的朋友應(yīng)該對其中的登錄邏輯有所印象理疙。
先給新來的朋友簡單介紹下 cim 是干啥的：
其中有一個場景是在客戶端登錄成功后需要從可用的服務(wù)端列表中選擇一臺服務(wù)節(jié)點返回給客戶端使用晕城。
而這個選擇的過程就是一個負(fù)載策略的過程；第一版本做的比較簡單窖贤，默認(rèn)只支持輪詢的方式砖顷。
雖然夠用，但不夠優(yōu)雅??主之。
因此我的規(guī)劃是內(nèi)置多種路由策略供使用者根據(jù)自己的場景選擇择吊，同時提供簡單的 API 供用戶自定義自己的路由策略。
先來看看一致性 Hash 算法的一些特點：
- 構(gòu)造一個
0 ~ 2^32-1大小的環(huán)槽奕。 - 服務(wù)節(jié)點經(jīng)過 hash 之后將自身存放到環(huán)中的下標(biāo)中。
- 客戶端根據(jù)自身的某些數(shù)據(jù) hash 之后也定位到這個環(huán)中房轿。
- 通過順時針找到離他最近的一個節(jié)點粤攒，也就是這次路由的服務(wù)節(jié)點。
- 考慮到服務(wù)節(jié)點的個數(shù)以及 hash 算法的問題導(dǎo)致環(huán)中的數(shù)據(jù)分布不均勻時引入了虛擬節(jié)點囱持。
自定義有序 Map
根據(jù)這些客觀條件我們很容易想到通過自定義一個有序數(shù)組來模擬這個環(huán)夯接。
這樣我們的流程如下：
- 初始化一個長度為 N 的數(shù)組。
- 將服務(wù)節(jié)點通過 hash 算法得到的正整數(shù)纷妆，同時將節(jié)點自身的數(shù)據(jù)（hashcode盔几、ip、端口等）存放在這里掩幢。
- 完成節(jié)點存放后將整個數(shù)組進(jìn)行排序（排序算法有多種）逊拍。
- 客戶端獲取路由節(jié)點時上鞠，將自身進(jìn)行 hash 也得到一個正整數(shù)；
- 遍歷這個數(shù)組直到找到一個數(shù)據(jù)大于等于當(dāng)前客戶端的 hash 值芯丧，就將當(dāng)前節(jié)點作為該客戶端所路由的節(jié)點芍阎。
- 如果沒有發(fā)現(xiàn)比客戶端大的數(shù)據(jù)就返回第一個節(jié)點（滿足環(huán)的特性）。
先不考慮排序所消耗的時間缨恒，單看這個路由的時間復(fù)雜度：
- 最好是第一次就找到谴咸，時間復(fù)雜度為
O(1)。 - 最差為遍歷完數(shù)組后才找到骗露，時間復(fù)雜度為
O(N)岭佳。
理論講完了來看看具體實踐。
我自定義了一個類：SortArrayMap
他的使用方法及結(jié)果如下：
可見最終會按照 key 的大小進(jìn)行排序萧锉，同時傳入 hashcode = 101 時會按照順時針找到 hashcode = 1000 這個節(jié)點進(jìn)行返回驼唱。
下面來看看具體的實現(xiàn)。
成員變量和構(gòu)造函數(shù)如下：
其中最核心的就是一個 Node 數(shù)組驹暑，用它來存放服務(wù)節(jié)點的 hashcode 以及 value 值玫恳。
其中的內(nèi)部類 Node 結(jié)構(gòu)如下：
寫入數(shù)據(jù)的方法如下：
相信看過 ArrayList 的源碼應(yīng)該有印象，這里的寫入邏輯和它很像优俘。
- 寫入之前判斷是否需要擴(kuò)容京办，如果需要則復(fù)制原來大小的 1.5 倍數(shù)組來存放數(shù)據(jù)。
- 之后就寫入數(shù)組帆焕，同時數(shù)組大小 +1惭婿。
但是存放時是按照寫入順序存放的，遍歷時自然不會有序叶雹；因此提供了一個 Sort 方法财饥，可以把其中的數(shù)據(jù)按照 key 其實也就是 hashcode 進(jìn)行排序。
排序也比較簡單折晦，使用了 Arrays 這個數(shù)組工具進(jìn)行排序钥星，它其實是使用了一個 TimSort 的排序算法，效率還是比較高的满着。
最后則需要按照一致性 Hash 的標(biāo)準(zhǔn)順時針查找對應(yīng)的節(jié)點：
代碼還是比較簡單清晰的谦炒；遍歷數(shù)組如果找到比當(dāng)前 key 大的就返回，沒有查到就取第一個风喇。
這樣就基本實現(xiàn)了一致性 Hash 的要求宁改。
ps:這里并不包含具體的 hash 方法以及虛擬節(jié)點等功能（具體實現(xiàn)請看下文），這個可以由使用者來定魂莫，SortArrayMap 可作為一個底層的數(shù)據(jù)結(jié)構(gòu)还蹲，提供有序 Map 的能力，使用場景也不局限于一致性 Hash 算法中。
TreeMap 實現(xiàn)
SortArrayMap 雖說是實現(xiàn)了一致性 hash 的功能谜喊，但效率還不夠高潭兽，主要體現(xiàn)在 sort 排序處。
下圖是目前主流排序算法的時間復(fù)雜度：
最好的也就是 O(N) 了锅论。
這里完全可以換一個思路讼溺，不用對數(shù)據(jù)進(jìn)行排序；而是在寫入的時候就排好順序最易，只是這樣會降低寫入的效率怒坯。
比如二叉查找樹，這樣的數(shù)據(jù)結(jié)構(gòu) jdk 里有現(xiàn)成的實現(xiàn)藻懒；比如 TreeMap 就是使用紅黑樹來實現(xiàn)的剔猿，默認(rèn)情況下它會對 key 進(jìn)行自然排序。
來看看使用 TreeMap 如何來達(dá)到同樣的效果嬉荆。
運行結(jié)果：
127.0.0.1000
效果和上文使用 SortArrayMap 是一致的归敬。
只使用了 TreeMap 的一些 API：
- 寫入數(shù)據(jù)候，
TreeMap可以保證 key 的自然排序鄙早。 -
tailMap可以獲取比當(dāng)前 key 大的部分?jǐn)?shù)據(jù)汪茧。 - 當(dāng)這個方法有數(shù)據(jù)返回時取第一個就是順時針中的第一個節(jié)點了。
- 如果沒有返回那就直接取整個
Map的第一個節(jié)點限番，同樣也實現(xiàn)了環(huán)形結(jié)構(gòu)舱污。
ps:這里同樣也沒有 hash 方法以及虛擬節(jié)點（具體實現(xiàn)請看下文），因為 TreeMap 和 SortArrayMap 一樣都是作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)來使用的弥虐。
性能對比
為了方便大家選擇哪一個數(shù)據(jù)結(jié)構(gòu)扩灯，我用 TreeMap 和 SortArrayMap 分別寫入了一百萬條數(shù)據(jù)來對比。
先是 SortArrayMap：
耗時 2237 毫秒霜瘪。
TreeMap：
耗時 1316毫秒珠插。
結(jié)果是快了將近一倍，所以還是推薦使用 TreeMap 來進(jìn)行實現(xiàn)颖对，畢竟它不需要額外的排序損耗捻撑。
cim 中的實際應(yīng)用
下面來看看在 cim 這個應(yīng)用中是如何具體使用的，其中也包括上文提到的虛擬節(jié)點以及 hash 算法惜互。
模板方法
在應(yīng)用的時候考慮到就算是一致性 hash 算法都有多種實現(xiàn)布讹，為了方便其使用者擴(kuò)展自己的一致性 hash 算法因此我定義了一個抽象類；其中定義了一些模板方法训堆，這樣大家只需要在子類中進(jìn)行不同的實現(xiàn)即可完成自己的算法。
AbstractConsistentHash白嘁，這個抽象類的主要方法如下：
-
add方法自然是寫入數(shù)據(jù)的坑鱼。 -
sort方法用于排序，但子類也不一定需要重寫，比如TreeMap這樣自帶排序的容器就不用鲁沥。 -
getFirstNodeValue獲取節(jié)點呼股。 -
process則是面向客戶端的，最終只需要調(diào)用這個方法即可返回一個節(jié)點画恰。
下面我們來看看利用 SortArrayMap 以及 AbstractConsistentHash 是如何實現(xiàn)的彭谁。
就是實現(xiàn)了幾個抽象方法，邏輯和上文是一樣的允扇，只是抽取到了不同的方法中缠局。
只是在 add 方法中新增了幾個虛擬節(jié)點，相信大家也看得明白考润。
把虛擬節(jié)點的控制放到子類而沒有放到抽象類中也是為了靈活性考慮狭园，可能不同的實現(xiàn)對虛擬節(jié)點的數(shù)量要求也不一樣，所以不如自定義的好糊治。
但是 hash 方法確是放到了抽象類中唱矛，子類不用重寫；因為這是一個基本功能井辜，只需要有一個公共算法可以保證他散列地足夠均勻即可绎谦。
因此在 AbstractConsistentHash 中定義了 hash 方法。
這里的算法摘抄自 xxl_job粥脚，網(wǎng)上也有其他不同的實現(xiàn)窃肠，比如
FNV1_32_HASH等；實現(xiàn)不同但是目的都一樣阿逃。
這樣對于使用者來說就非常簡單了：
他只需要構(gòu)建一個服務(wù)列表铭拧，然后把當(dāng)前的客戶端信息傳入 process 方法中即可獲得一個一致性 hash 算法的返回。
同樣的對于想通過 TreeMap 來實現(xiàn)也是一樣的套路：
他這里不需要重寫 sort 方法恃锉，因為自身寫入時已經(jīng)排好序了搀菩。
而在使用時對于客戶端來說只需求修改一個實現(xiàn)類，其他的啥都不用改就可以了破托。
運行的效果也是一樣的肪跋。
這樣大家想自定義自己的算法時只需要繼承 AbstractConsistentHash 重寫相關(guān)方法即可，客戶端代碼無須改動土砂。
路由算法擴(kuò)展性
但其實對于 cim 來說真正的擴(kuò)展性是對路由算法來說的州既，比如它需要支持輪詢、hash萝映、一致性hash吴叶、隨機(jī)、LRU等序臂。
只是一致性 hash 也有多種實現(xiàn)蚌卤，他們的關(guān)系就如下圖：
應(yīng)用還需要滿足對這一類路由策略的靈活支持实束，比如我也想自定義一個隨機(jī)的策略。
因此定義了一個接口：RouteHandle
public interface RouteHandle {
/**
* 再一批服務(wù)器里進(jìn)行路由
* @param values
* @param key
* @return
*/
String routeServer(List<String> values,String key) ;
}
其中只有一個方法逊彭，也就是路由方法咸灿；入?yún)⒎謩e是服務(wù)列表以及客戶端信息即可。
而對于一致性 hash 算法來說也是只需要實現(xiàn)這個接口侮叮，同時在這個接口中選擇使用 SortArrayMapConsistentHash 還是 TreeMapConsistentHash 即可避矢。
這里還有一個 setHash 的方法，入?yún)⑹?AbstractConsistentHash囊榜；這就是用于客戶端指定需要使用具體的那種數(shù)據(jù)結(jié)構(gòu)审胸。
而對于之前就存在的輪詢策略來說也是同樣的實現(xiàn) RouteHandle 接口。
這里我只是把之前的代碼搬過來了而已锦聊。
接下來看看客戶端到底是如何使用以及如何選擇使用哪種算法歹嘹。
為了使客戶端代碼幾乎不動，我將這個選擇的過程放入了配置文件孔庭。
- 如果想使用原有的輪詢策略尺上，就配置實現(xiàn)了
RouteHandle接口的輪詢策略的全限定名。 - 如果想使用一致性 hash 的策略圆到，也只需要配置實現(xiàn)了
RouteHandle接口的一致性 hash 算法的全限定名怎抛。 - 當(dāng)然目前的一致性 hash 也有多種實現(xiàn)，所以一旦配置為一致性 hash 后就需要再加一個配置用于決定使用
SortArrayMapConsistentHash還是TreeMapConsistentHash或是自定義的其他方案芽淡。 - 同樣的也是需要配置繼承了
AbstractConsistentHash的全限定名马绝。
不管這里的策略如何改變，在使用處依然保持不變挣菲。
只需要注入 RouteHandle富稻，調(diào)用它的 routeServer 方法。
@Autowired
private RouteHandle routeHandle ;
String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));
既然使用了注入白胀，那其實這個策略切換的過程就在創(chuàng)建 RouteHandle bean 的時候完成的椭赋。
也比較簡單，需要讀取之前的配置文件來動態(tài)生成具體的實現(xiàn)類或杠，主要是利用反射完成的哪怔。
這樣處理之后就比較靈活了，比如想新建一個隨機(jī)的路由策略也是同樣的套路向抢；到時候只需要修改配置即可认境。
感興趣的朋友也可提交 PR 來新增更多的路由策略。
總結(jié)
希望看到這里的朋友能對這個算法有所理解挟鸠，同時對一些設(shè)計模式在實際的使用也能有所幫助叉信。
相信在金三銀四的面試過程中還是能讓面試官眼前一亮的，畢竟根據(jù)我這段時間的面試過程來看聽過這個名詞的都在少數(shù)??（可能也是和候選人都在 1~3 年這個層級有關(guān)）艘希。
以上所有源碼：
https://github.com/crossoverJie/cim
如果本文對你有所幫助還請不吝轉(zhuǎn)發(fā)茉盏。
