對一致哈希環的簡單解釋

知識 06-08

Python部落(python.freelycode.com)組織翻譯，禁止轉載，歡迎轉發。

一致哈希環的提出是一個非常棒的發明，然而卻讓人不太好理解。一般來說，實際與理論有很大的不同，一個理論能否在實際中得到廣泛應用與大家對它的理解程度有關，然而具體的實現方法卻可能不太理解，因為這些太抽象了。
本文嘗試用Python對哈希環進行簡單的說明，希望大多數人都能夠理解。

為什麼要用Hash？

通常情況下，你需要根據一件物品的名稱來找到與之對應的東西，例如，你可以通過URL地址來訪問特定的網站。這些事情都可以通過映射來完成，就像是你拿著電話本根據聯繫人姓名來查找電話號碼。還有一本書下面的索引也是一個映射，你可以根據關鍵字找到指定的頁數來獲取需要的內容。來個書面點的說法，所有的映射都是根據一個條目經過一種特定的方式找到另一個條目。
在計算機中也有這樣的例子，例如，在內存中存儲一個數，計算機會標記一個值，然後根據這個值通過某種方式找到內存中的那個數。在整個過程中，找到內存地址的方法稱為哈希演算法，映射是根據哈希表來完成的，內存的位置叫做哈希桶(hash buckets)。

問題1：有限內存

一般情況下，哈希演算法會根據一個鍵生成一個儘可能無限大的數來表示內存的位置，但是實際中，計算機提供的內存是非常有限的。也就是說，哈希數和計算機內存之間是不可能直接形成一對一查找的。
解決方案就是避免這種情況：

1、提前知道所有可能的內存位置
2、順序使用，如果可能的話將其按序列標記
3、取一個鍵計算哈希數並將它除以內存位置數，也就是取余

最終你計算出的數就放在內存位置數和它一樣的內存處。舉例來說，就是假設你有10個可存儲位置，你的哈希數鍵值為103，將這個數取余得到3(1013%10=3)，然後就把這個數放在標記為3 的位置處。
當我查詢這個數時，就執行這些步驟，存儲一個新數時，也同樣如此，那麼這些數就始終儲存在這個位置 hash % buckets。
對於許多現實世界的應用來說，這實際上是足夠的。這有兩個簡單實現哈希表的代碼：

一個更加完善的哈希演算法應該能夠解決更多的數值，或者有兩個不同的數值卻產生了相同的哈希數這樣的問題。好在這些都得到解決了。

問題2：消失的桶

一般的哈希表依賴於固定不變的存儲位置，實際情況卻並非如此。讓我們通過以下步驟來了解存儲位置數n發生變化時會出現什麼樣的事情：

1、開始有10個存儲位置，要存儲的數的哈希值為1013
2、將這個數放在1013%10=3的位置
3、將存儲位置數改為9
4、現在根據同樣的方法要查找原來的數，結果卻返回103%9=5處的數，很顯然這是錯誤的

返回錯誤的數時無法想像的，就像你輸入谷歌的網址來訪問Facebook一樣。不過這樣的事情卻經常發生，例如在網路上傳送數據的時候，通常會通過多個伺服器，而要知道特定的URL地址返回伺服器上的數據。有些伺服器會死機，有時會增加伺服器的數量，總而言之，存儲位置的數量在變。
使用常規哈希表，確保數據一致性的唯一方法如下：

1、獲取每個鍵，包括哪些丟失位置的值
2、根據原來的位置數計算最初存儲的值
3、將所有的數都移動到新的位置
4、按照新的要求重新計算所有的數

這是一個重新映射的過程，當你的存儲位置發生變化時會採取這樣的措施。例如，有2000個鍵分布在100個位置，現在其中一個位置丟失了，你需要將剩下的1800個鍵重新分布在剩下的99個位置上。那麼，有沒有更簡單的做法？

Yes，更簡單的做法

一致哈希的發明就是為了解決存儲位置不斷發生變化的問題。簡而言之，一致哈希的實施過程如下：

1、取消一個位置只保存一個值的做法，讓一個位置存儲來自多個鍵的值
2、不連續編碼存儲位置，給它們分配0到無窮的隨機數
3、不計算「哈希數%存儲位置數」，找到比哈希數大的最小位置數，將數放在那
4、如果你的哈希數大於所有的存儲位置，將其放在最低編號的位置

例如，隨機給出1,20,41,1024,2016五個存儲位置，假定哈希數為1013，那麼將其代表的數放在1024這個存儲位置；如果哈希數為2017，則將其放在編號為1的存儲位置。

為什麼這樣的做法更好呢？下面來看下具體的過程：

1、將開始隨機生成的五個存儲位置中的1024去掉，這樣只剩下1,20,41,2016這四個了
2、所有大於2016的哈希數都存儲在位置為1的位置，不用改變
3、所有比20,41,2016略小的哈希數仍在這些位置，也不需要改變
4、只有比41大比1024小的哈希數需要改變，這個新的最小位置是2016，所以它們會存儲在2016這個新位置。

與上一個例子不同的是，現在你只需要改變20個數的位置即可。
這就是一致哈希的優點，當一個存儲位置消失後，不必對所有的數據都進行操作。對於那些經常改變存儲位置的數據，現在你可以不用再擔心了。

重要說明

現在你應該理解一致哈希的過程了，有一些說明還是必要的：

1、一致哈希不能解決尋值的問題，它只知道這些值最有可能存儲在哪裡。因為一個位置能存儲多個值，一旦一個鍵確認了存儲位置，需要額外的操作來返回具體的位置。在這個例子中，存儲位置可能是伺服器，當鍵值通過一致哈希來查找時，伺服器會搜尋比它小的哈希數來返回數值。
2、實際中，每個存儲位置的值並不是隨機生成的，相反，它們都有個名稱，而且這個名稱是根據哈希演算法得到的有效隨機數，因此才被稱為一致哈希。這樣做簡化了很多細節，當然，也可以生成純隨機數，不過這都屬於高級優化的過程了。

怎樣實現一致哈希環

這是這篇文章的技術部分，首先考慮我們的需求：
1、需要一個能搜尋數值的結構
2、需要一個能維持排序順序的結構
當使用二分法搜索時，兩個基本數據結構應該符合上面準則：
1、排序列表
2、二叉搜索樹
對於給定的排序列表，工作流程如下：
1、創建一個空結構
2、給定伺服器主機名，對其進行哈希並返回數值
3、在列表中插入數值，並將伺服器的名稱保存在其他地方
4、如果主機名被刪除，只需將其從當前位置彈出
5、如果添加了主機名，則按其排序順序將舊的主機名經過哈希變換後放置在新位置
6、給定一個鍵值，計算它的哈希數並使用二分法搜尋找到最近的哈希數，返回主機名
以上就是所有的過程。
在這篇文章中，我選擇用二叉搜索樹來達到目的，這裡有很多原因，最重要的是想避免任何比python更複雜的東西，想高效的使用排序列表可以用python的bisecct。所以，毫無疑問下面是一個簡單的遞歸演算法;