聲明：本文僅限于簡書發(fā)布，其他第三方網(wǎng)站均為盜版，原文地址： 一致性哈希及其 Python 實(shí)現(xiàn)
記得之前看一些集群數(shù)據(jù)庫或者和集群相關(guān)的文章和書籍的時(shí)候，總是會有人提到一致性哈希這個(gè)東西，一開始感覺挺稀奇，挺神奇的，漸漸得看得多了，也就習(xí)以為常了。但是，雖然看了那么多的介紹，大多數(shù)都是理論層面講講，所說這是什么東西，什么原理，然后就完了，頂多再補(bǔ)充一下再具體的應(yīng)用場景里面有什么好處。
作為一個(gè)開發(fā)者，我更關(guān)注于說這個(gè)東西怎么實(shí)現(xiàn)好用，有什么比較好的數(shù)據(jù)結(jié)構(gòu)，好的實(shí)踐可以更好得滿足我們的目的。很可惜的是，我看的大部分書都沒有說這個(gè)，我一開始還傻傻得以為真的用一個(gè)數(shù)組來設(shè)置哈希環(huán)，然后所有實(shí)例都哈希到對應(yīng)的位置上，然后要哈希 key 的時(shí)候在環(huán)里一個(gè)個(gè)找。這是一個(gè)比較傻的方法，不過這是建立在我對一致性哈希的小規(guī)模應(yīng)用場景的思維方式下，所以產(chǎn)生了這個(gè)想法，雖然一開始我就覺得不大可能，但是沒細(xì)想它，最近突然看到 Map 這個(gè)數(shù)據(jù)結(jié)構(gòu)（這個(gè)純屬 Java 學(xué)藝不精，當(dāng)年寫 Java 的時(shí)候沒有區(qū)分 HashMap 和 TreeMap 的區(qū)別，罪過罪過）居然有人用紅黑樹實(shí)現(xiàn)的時(shí)候，我心里有一些想法冒出來了。
一致性哈希
廢話說得有點(diǎn)多，還是先進(jìn)入到主題吧，什么是一致性哈希。要說一致性哈希，我想來講個(gè)普通的哈希表的例子，大家先看看有什么問題，下面先來一段描述：
假設(shè)我們有 5 臺 MySQL 服務(wù)器，然后對數(shù)據(jù)庫進(jìn)行水平拆分，也就是對于插入表中的數(shù)據(jù)，我們對記錄的 id 進(jìn)行哈希映射到 0～4 的區(qū)間，然后根據(jù)哈希結(jié)果保存到對應(yīng)的 MySQL 服務(wù)器中。
這個(gè)方案乍一看問題不大，但是，在不考慮冗余備份的情況下，我們考慮一下如果其中一臺數(shù)據(jù)庫宕機(jī)了，我們的數(shù)據(jù)就會因?yàn)檫@種哈希算法而亂掉，我們就需要定義新的哈希算法，將哈希映射到 0～3 的區(qū)間上，然后再對 所有的數(shù)據(jù) 進(jìn)行重新分配，這對于分布式存儲來說是很嚴(yán)重的問題。
那針對這個(gè)問題，我們當(dāng)然是不希望重新分配 所有的數(shù)據(jù) 啦，我們期望的是重新分配的數(shù)據(jù)只是宕機(jī)的那臺機(jī)器上的數(shù)據(jù)就好，而且我們的存儲和獲取邏輯還不需要更換，這就是一致性哈希的常見應(yīng)用場景。
為了簡單理解，我就簡化描述，我們可以認(rèn)為 一致性哈希比普通哈希表多做了一次哈希，也就是不僅僅數(shù)據(jù)做哈希，機(jī)器也做哈希；怎么理解，假設(shè)對于剛才的例子，我們構(gòu)建一個(gè) 32 個(gè)位的環(huán)，我們將機(jī)器作哈希（這里可以使用任意的哈希函數(shù)，不過最好均勻一些）到 0～31 的區(qū)間里，假設(shè)哈希后的位置是這樣的：
然后我們再對數(shù)據(jù)根據(jù) id 進(jìn)行映射，也是映射到 0～31 的區(qū)間內(nèi)，假設(shè) id 為 10086 的數(shù)據(jù)的哈希值是 18，那么我們就從環(huán)中 18 的位置開始尋找，只到找到第一個(gè)主機(jī)為止，在這個(gè)環(huán)中它就是 host3，也就是哈希值為 23 的機(jī)器，然后我們就可以將數(shù)據(jù)存儲到這臺機(jī)器了。
這就是一致性哈希的簡單描述啦！那我們就來看看這樣子有什么好處，先來看看機(jī)器宕機(jī)了吧，假設(shè) host4 宕機(jī)了，那么一致性哈希會怎么處理？根據(jù)這個(gè)情況，我們從圖中也可以發(fā)現(xiàn)，host4 中的數(shù)據(jù)都會遷移到 host3 中，除此之外就不需要做什么了。
增加一臺主機(jī)也一樣，假設(shè)我們增加了一臺主機(jī) liuliqiang.info，那么我們會發(fā)現(xiàn)這個(gè)環(huán)就應(yīng)該變成這樣：
然后可以發(fā)現(xiàn)，原來放到 host4 的數(shù)據(jù)就可以遷移一部分到新的機(jī)器上，只是局部影響，而不是導(dǎo)致全體主機(jī)的數(shù)據(jù)收到波動影響。
但是，目前這都是最原始的，還是問題比較大，因?yàn)閺纳厦婵梢钥吹剑僭O(shè)一臺機(jī)器宕機(jī)之后，那么就會導(dǎo)致 host4 的數(shù)據(jù)全都遷移到 host3 中，從概率上來講，host3 承載了 40% 的數(shù)據(jù)，比其他機(jī)器多了一倍負(fù)載，很可能會發(fā)生 雪崩效應(yīng) ，當(dāng)然，一致性哈希還是可以解決這個(gè)問題。我知道的一個(gè)比較常用的方法就是使用 虛擬節(jié)點(diǎn)，也就是說一臺主機(jī)，不僅僅只在環(huán)上有一個(gè)位置，而是多個(gè)位置，例如這樣：
這樣我們就可以看到，假設(shè)還是 host4 崩了，那么他一部分的數(shù)據(jù)會轉(zhuǎn)給 host0，還有一部分?jǐn)?shù)據(jù)會轉(zhuǎn)給 host3，如果我們將虛擬節(jié)點(diǎn)再多一些，可能會更平均一點(diǎn)。至于怎么映射虛擬節(jié)點(diǎn)到多個(gè)節(jié)點(diǎn)，這個(gè)也很簡單呀，我們可以這樣做嘛：
這樣我就定義了 host1 的 4 個(gè)虛擬節(jié)點(diǎn)啦。
Python 實(shí)現(xiàn)
講完原理之后，是時(shí)候上真刀真槍了，前面說了，我想用紅黑樹去實(shí)現(xiàn)它，為什么呢？考慮一下前面的說的，前面給的例子是一個(gè) 32 長度的環(huán)，這個(gè)確實(shí)比較好辦，但是，假設(shè)我機(jī)器就幾百臺，那環(huán)就會更大，隨著機(jī)器的增加或者我們做一些虛擬節(jié)點(diǎn)，這個(gè)環(huán)就會很大了，影響了查找效率，這是一方面；另一方面，我們從上面的例子中也可以看到，環(huán)中除了一些有意義的位置存了主機(jī)的信息之外，還有很多位置是閑置的，這又浪費(fèi)了內(nèi)存空間。
其實(shí)，細(xì)想一下，這里根本就不需要有真的環(huán)實(shí)體存在，理論上經(jīng)常說環(huán)是為了方便理解，但是事實(shí)上在實(shí)現(xiàn)的時(shí)候我們可以忽略環(huán)這個(gè)概念，將它轉(zhuǎn)化為一個(gè)排序的數(shù)組，例如上面的例如，我們可以將哈希值排序，排序?yàn)椋篬0, 3, 8, 15, 23, 24]
當(dāng)我們有一條數(shù)據(jù)例如哈希值是 10 的記錄要保存時(shí)，我們不用找環(huán)了，直接在排序的哈希數(shù)組里面二分查找大于 10 的最小記錄，也就是 15，這樣就保證了空間的合理利用，查找效率上也不差，最壞也是 log(n)。
但是，在轉(zhuǎn)化成代碼的時(shí)候，我們又要考慮了，這里要用什么數(shù)據(jù)結(jié)構(gòu)？數(shù)組好不好？首先數(shù)組可以保證我們查找的效率，但是，刪除和新增的復(fù)雜度時(shí)很高的，將會達(dá)到 O(n)，而且我們數(shù)組的大小也是問題，要怎么分配這個(gè)數(shù)組的大小，如果太小以后不夠是不是要擴(kuò)容？所以不是很合適。鏈表呢？刪除和新增效率很高，但是我們比較常用的查找性能又不行，用跳表來彌補(bǔ)？空間浪費(fèi)又來了。。。
好吧，權(quán)衡之下，我選擇了用 紅黑樹，紅黑樹有什么特點(diǎn)？它最大的特點(diǎn)就是平均，它可以保證在最壞的情況下，基本的操作都是 log(n)，下面是一張別人總結(jié)的對比圖：
所以用紅黑樹來保存還是非常合適的。
下面用 Python 代碼來模擬一下這個(gè)一致性哈希的過程，其實(shí)可以分為三個(gè)部分：
- 新增主機(jī)
- 刪除主機(jī)
- 查找主機(jī)
然后紅黑樹的實(shí)現(xiàn)我是使用的 bintrees，首先，想看下我們的主機(jī)的 model 是怎么寫的，需要保存些什么內(nèi)容：
這里我就保存了主機(jī)的名稱，還有它們的哈希值，這個(gè)后面會用到，然后再來看看增加主機(jī)怎么寫：
插入的代碼可以很簡單得寫出來，因?yàn)槲覀円呀?jīng)封裝好了節(jié)點(diǎn)以及紅黑樹，所以也就沒什么難度了，還有刪除的也會很簡單：
沒啥大毛病，下面的關(guān)鍵來了，就是如何查找存放數(shù)據(jù)的主機(jī)，這個(gè)很關(guān)鍵，也是二叉查找樹里面的一個(gè)比較有意思的問題，就是如何查找不小于指定元素的最小元素節(jié)點(diǎn)，我是這么寫的：
這里對對查找邏輯做了一些簡單封裝，有一點(diǎn)需要注意的是，如果要查找的 id 比所有的主機(jī)的 id 都要大，那么就應(yīng)該選取環(huán)中 id 最小的那個(gè)元素（回顧一下前面）。這樣整個(gè)簡單的代碼就完成了。
本文的所有代碼都可以在我的 Github 代碼片段中找到：Github代碼片段
