image

前言

記得一年前分享過一篇《一致性 Hash 算法分析》，當(dāng)時(shí)只是分析了這個(gè)算法的實(shí)現(xiàn)原理、解決了什么問題等。

但沒有實(shí)際實(shí)現(xiàn)一個(gè)這樣的算法，畢竟要加深印象還得自己擼一遍，于是本次就當(dāng)前的一個(gè)路由需求來著手實(shí)現(xiàn)一次。

背景

看過《為自己搭建一個(gè)分布式 IM(即時(shí)通訊) 系統(tǒng)》的朋友應(yīng)該對(duì)其中的登錄邏輯有所印象。

先給新來的朋友簡(jiǎn)單介紹下 cim 是干啥的：

image

其中有一個(gè)場(chǎng)景是在客戶端登錄成功后需要從可用的服務(wù)端列表中選擇一臺(tái)服務(wù)節(jié)點(diǎn)返回給客戶端使用。

而這個(gè)選擇的過程就是一個(gè)負(fù)載策略的過程；第一版本做的比較簡(jiǎn)單，默認(rèn)只支持輪詢的方式。

雖然夠用，但不夠優(yōu)雅??。

因此我的規(guī)劃是內(nèi)置多種路由策略供使用者根據(jù)自己的場(chǎng)景選擇，同時(shí)提供簡(jiǎn)單的 API 供用戶自定義自己的路由策略。

先來看看一致性 Hash 算法的一些特點(diǎn)：

• 構(gòu)造一個(gè) 0 ~ 2^32-1 大小的環(huán)。
• 服務(wù)節(jié)點(diǎn)經(jīng)過 hash 之后將自身存放到環(huán)中的下標(biāo)中。
• 客戶端根據(jù)自身的某些數(shù)據(jù) hash 之后也定位到這個(gè)環(huán)中。
• 通過順時(shí)針找到離他最近的一個(gè)節(jié)點(diǎn)，也就是這次路由的服務(wù)節(jié)點(diǎn)。
• 考慮到服務(wù)節(jié)點(diǎn)的個(gè)數(shù)以及 hash 算法的問題導(dǎo)致環(huán)中的數(shù)據(jù)分布不均勻時(shí)引入了虛擬節(jié)點(diǎn)。

image

自定義有序 Map

根據(jù)這些客觀條件我們很容易想到通過自定義一個(gè)有序數(shù)組來模擬這個(gè)環(huán)。

這樣我們的流程如下：

1. 初始化一個(gè)長(zhǎng)度為 N 的數(shù)組。
2. 將服務(wù)節(jié)點(diǎn)通過 hash 算法得到的正整數(shù)，同時(shí)將節(jié)點(diǎn)自身的數(shù)據(jù)（hashcode、ip、端口等）存放在這里。
3. 完成節(jié)點(diǎn)存放后將整個(gè)數(shù)組進(jìn)行排序（排序算法有多種）。
4. 客戶端獲取路由節(jié)點(diǎn)時(shí)，將自身進(jìn)行 hash 也得到一個(gè)正整數(shù)；
5. 遍歷這個(gè)數(shù)組直到找到一個(gè)數(shù)據(jù)大于等于當(dāng)前客戶端的 hash 值，就將當(dāng)前節(jié)點(diǎn)作為該客戶端所路由的節(jié)點(diǎn)。
6. 如果沒有發(fā)現(xiàn)比客戶端大的數(shù)據(jù)就返回第一個(gè)節(jié)點(diǎn)（滿足環(huán)的特性）。

先不考慮排序所消耗的時(shí)間，單看這個(gè)路由的時(shí)間復(fù)雜度：

• 最好是第一次就找到，時(shí)間復(fù)雜度為O(1)。
• 最差為遍歷完數(shù)組后才找到，時(shí)間復(fù)雜度為O(N)。

理論講完了來看看具體實(shí)踐。

我自定義了一個(gè)類：SortArrayMap

他的使用方法及結(jié)果如下：

image

image

可見最終會(huì)按照 key 的大小進(jìn)行排序，同時(shí)傳入 hashcode = 101 時(shí)會(huì)按照順時(shí)針找到 hashcode = 1000 這個(gè)節(jié)點(diǎn)進(jìn)行返回。

下面來看看具體的實(shí)現(xiàn)。

成員變量和構(gòu)造函數(shù)如下：

image

其中最核心的就是一個(gè) Node 數(shù)組，用它來存放服務(wù)節(jié)點(diǎn)的 hashcode 以及 value 值。

其中的內(nèi)部類 Node 結(jié)構(gòu)如下：

image

寫入數(shù)據(jù)的方法如下：

image

相信看過 ArrayList 的源碼應(yīng)該有印象，這里的寫入邏輯和它很像。

• 寫入之前判斷是否需要擴(kuò)容，如果需要?jiǎng)t復(fù)制原來大小的 1.5 倍數(shù)組來存放數(shù)據(jù)。
• 之后就寫入數(shù)組，同時(shí)數(shù)組大小 +1。

但是存放時(shí)是按照寫入順序存放的，遍歷時(shí)自然不會(huì)有序；因此提供了一個(gè) Sort 方法，可以把其中的數(shù)據(jù)按照 key 其實(shí)也就是 hashcode 進(jìn)行排序。

image

排序也比較簡(jiǎn)單，使用了 Arrays 這個(gè)數(shù)組工具進(jìn)行排序，它其實(shí)是使用了一個(gè) TimSort 的排序算法，效率還是比較高的。

最后則需要按照一致性 Hash 的標(biāo)準(zhǔn)順時(shí)針查找對(duì)應(yīng)的節(jié)點(diǎn)：

image

代碼還是比較簡(jiǎn)單清晰的；遍歷數(shù)組如果找到比當(dāng)前 key 大的就返回，沒有查到就取第一個(gè)。

這樣就基本實(shí)現(xiàn)了一致性 Hash 的要求。

ps:這里并不包含具體的 hash 方法以及虛擬節(jié)點(diǎn)等功能（具體實(shí)現(xiàn)請(qǐng)看下文），這個(gè)可以由使用者來定，SortArrayMap 可作為一個(gè)底層的數(shù)據(jù)結(jié)構(gòu)，提供有序 Map 的能力，使用場(chǎng)景也不局限于一致性 Hash 算法中。

TreeMap 實(shí)現(xiàn)

SortArrayMap 雖說是實(shí)現(xiàn)了一致性 hash 的功能，但效率還不夠高，主要體現(xiàn)在 sort 排序處。

下圖是目前主流排序算法的時(shí)間復(fù)雜度：

image

最好的也就是 O(N) 了。

這里完全可以換一個(gè)思路，不用對(duì)數(shù)據(jù)進(jìn)行排序；而是在寫入的時(shí)候就排好順序，只是這樣會(huì)降低寫入的效率。

比如二叉查找樹，這樣的數(shù)據(jù)結(jié)構(gòu) jdk 里有現(xiàn)成的實(shí)現(xiàn)；比如 TreeMap 就是使用紅黑樹來實(shí)現(xiàn)的，默認(rèn)情況下它會(huì)對(duì) key 進(jìn)行自然排序。

來看看使用 TreeMap 如何來達(dá)到同樣的效果。

image

127.0.0.1000

效果和上文使用 SortArrayMap 是一致的。

只使用了 TreeMap 的一些 API：

• 寫入數(shù)據(jù)候，TreeMap 可以保證 key 的自然排序。
• tailMap 可以獲取比當(dāng)前 key 大的部分?jǐn)?shù)據(jù)。
• 當(dāng)這個(gè)方法有數(shù)據(jù)返回時(shí)取第一個(gè)就是順時(shí)針中的第一個(gè)節(jié)點(diǎn)了。
• 如果沒有返回那就直接取整個(gè) Map 的第一個(gè)節(jié)點(diǎn)，同樣也實(shí)現(xiàn)了環(huán)形結(jié)構(gòu)。

ps:這里同樣也沒有 hash 方法以及虛擬節(jié)點(diǎn)（具體實(shí)現(xiàn)請(qǐng)看下文），因?yàn)?TreeMap 和 SortArrayMap 一樣都是作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)來使用的。

性能對(duì)比

為了方便大家選擇哪一個(gè)數(shù)據(jù)結(jié)構(gòu)，我用 TreeMap 和 SortArrayMap 分別寫入了一百萬條數(shù)據(jù)來對(duì)比。

先是 SortArrayMap：

image

耗時(shí) 2237 毫秒。

TreeMap：

image

耗時(shí) 1316毫秒。

結(jié)果是快了將近一倍，所以還是推薦使用 TreeMap 來進(jìn)行實(shí)現(xiàn)，畢竟它不需要額外的排序損耗。

cim 中的實(shí)際應(yīng)用

下面來看看在 cim 這個(gè)應(yīng)用中是如何具體使用的，其中也包括上文提到的虛擬節(jié)點(diǎn)以及 hash 算法。

模板方法

在應(yīng)用的時(shí)候考慮到就算是一致性 hash 算法都有多種實(shí)現(xiàn)，為了方便其使用者擴(kuò)展自己的一致性 hash 算法因此我定義了一個(gè)抽象類；其中定義了一些模板方法，這樣大家只需要在子類中進(jìn)行不同的實(shí)現(xiàn)即可完成自己的算法。

AbstractConsistentHash，這個(gè)抽象類的主要方法如下：

image

• add 方法自然是寫入數(shù)據(jù)的。
• sort 方法用于排序，但子類也不一定需要重寫，比如 TreeMap 這樣自帶排序的容器就不用。
• getFirstNodeValue 獲取節(jié)點(diǎn)。
• process 則是面向客戶端的，最終只需要調(diào)用這個(gè)方法即可返回一個(gè)節(jié)點(diǎn)。

下面我們來看看利用 SortArrayMap 以及 AbstractConsistentHash 是如何實(shí)現(xiàn)的。

image

就是實(shí)現(xiàn)了幾個(gè)抽象方法，邏輯和上文是一樣的，只是抽取到了不同的方法中。

只是在 add 方法中新增了幾個(gè)虛擬節(jié)點(diǎn)，相信大家也看得明白。

把虛擬節(jié)點(diǎn)的控制放到子類而沒有放到抽象類中也是為了靈活性考慮，可能不同的實(shí)現(xiàn)對(duì)虛擬節(jié)點(diǎn)的數(shù)量要求也不一樣，所以不如自定義的好。

但是 hash 方法確是放到了抽象類中，子類不用重寫；因?yàn)檫@是一個(gè)基本功能，只需要有一個(gè)公共算法可以保證他散列地足夠均勻即可。

因此在 AbstractConsistentHash 中定義了 hash 方法。

image

這里的算法摘抄自 xxl_job，網(wǎng)上也有其他不同的實(shí)現(xiàn)，比如 FNV1_32_HASH 等；實(shí)現(xiàn)不同但是目的都一樣。

這樣對(duì)于使用者來說就非常簡(jiǎn)單了：

image

他只需要構(gòu)建一個(gè)服務(wù)列表，然后把當(dāng)前的客戶端信息傳入 process 方法中即可獲得一個(gè)一致性 hash 算法的返回。

同樣的對(duì)于想通過 TreeMap 來實(shí)現(xiàn)也是一樣的套路：

image

他這里不需要重寫 sort 方法，因?yàn)樽陨韺懭霑r(shí)已經(jīng)排好序了。

而在使用時(shí)對(duì)于客戶端來說只需求修改一個(gè)實(shí)現(xiàn)類，其他的啥都不用改就可以了。

image

運(yùn)行的效果也是一樣的。

這樣大家想自定義自己的算法時(shí)只需要繼承 AbstractConsistentHash 重寫相關(guān)方法即可，客戶端代碼無須改動(dòng)。

路由算法擴(kuò)展性

但其實(shí)對(duì)于 cim 來說真正的擴(kuò)展性是對(duì)路由算法來說的，比如它需要支持輪詢、hash、一致性hash、隨機(jī)、LRU等。

只是一致性 hash 也有多種實(shí)現(xiàn)，他們的關(guān)系就如下圖：

image

應(yīng)用還需要滿足對(duì)這一類路由策略的靈活支持，比如我也想自定義一個(gè)隨機(jī)的策略。

因此定義了一個(gè)接口：RouteHandle

public interface RouteHandle {

    /**
     * 再一批服務(wù)器里進(jìn)行路由
     * @param values
     * @param key
     * @return
     */
    String routeServer(List<String> values,String key) ;
}

其中只有一個(gè)方法，也就是路由方法；入?yún)⒎謩e是服務(wù)列表以及客戶端信息即可。

而對(duì)于一致性 hash 算法來說也是只需要實(shí)現(xiàn)這個(gè)接口，同時(shí)在這個(gè)接口中選擇使用 SortArrayMapConsistentHash 還是 TreeMapConsistentHash 即可。

image

這里還有一個(gè) setHash 的方法，入?yún)⑹?AbstractConsistentHash；這就是用于客戶端指定需要使用具體的那種數(shù)據(jù)結(jié)構(gòu)。

而對(duì)于之前就存在的輪詢策略來說也是同樣的實(shí)現(xiàn) RouteHandle 接口。

image

這里我只是把之前的代碼搬過來了而已。

接下來看看客戶端到底是如何使用以及如何選擇使用哪種算法。

為了使客戶端代碼幾乎不動(dòng)，我將這個(gè)選擇的過程放入了配置文件。

image

1. 如果想使用原有的輪詢策略，就配置實(shí)現(xiàn)了 RouteHandle 接口的輪詢策略的全限定名。
2. 如果想使用一致性 hash 的策略，也只需要配置實(shí)現(xiàn)了 RouteHandle 接口的一致性 hash 算法的全限定名。
3. 當(dāng)然目前的一致性 hash 也有多種實(shí)現(xiàn)，所以一旦配置為一致性 hash 后就需要再加一個(gè)配置用于決定使用 SortArrayMapConsistentHash 還是 TreeMapConsistentHash 或是自定義的其他方案。
4. 同樣的也是需要配置繼承了 AbstractConsistentHash 的全限定名。

不管這里的策略如何改變，在使用處依然保持不變。

只需要注入 RouteHandle，調(diào)用它的 routeServer 方法。

@Autowired
private RouteHandle routeHandle ;
String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));

既然使用了注入，那其實(shí)這個(gè)策略切換的過程就在創(chuàng)建 RouteHandle bean 的時(shí)候完成的。

image

也比較簡(jiǎn)單，需要讀取之前的配置文件來動(dòng)態(tài)生成具體的實(shí)現(xiàn)類，主要是利用反射完成的。

這樣處理之后就比較靈活了，比如想新建一個(gè)隨機(jī)的路由策略也是同樣的套路；到時(shí)候只需要修改配置即可。

感興趣的朋友也可提交 PR 來新增更多的路由策略。

總結(jié)

希望看到這里的朋友能對(duì)這個(gè)算法有所理解，同時(shí)對(duì)一些設(shè)計(jì)模式在實(shí)際的使用也能有所幫助。

相信在金三銀四的面試過程中還是能讓面試官眼前一亮的，畢竟根據(jù)我這段時(shí)間的面試過程來看聽過這個(gè)名詞的都在少數(shù)??（可能也是和候選人都在 1~3 年這個(gè)層級(jí)有關(guān)）。

以上所有源碼：

https://github.com/crossoverJie/cim

如果本文對(duì)你有所幫助還請(qǐng)不吝轉(zhuǎn)發(fā)。

image