一致性哈希概念與Python的簡單實現
- 2020 年 1 月 9 日
- 筆記
好像從開始接觸Zookeeper的時候就知道了有一致性哈希這東西。。。。不過倒是一直都沒有去了解這到底是個啥東西。。。只是知道它在分散式系統設計中有十分重要的作用。。。。
好了，接下來用舉例子的方式來說一下一致性哈希到底有啥用吧。。。場景如下：
當前有4台伺服器組成的分散式快取系統，這裡對於一個Key，通過哈希的方式，將其保存到某一台伺服器上。。。
對於一般的哈希演算法，我們首先會想到用一些哈希演算法來獲取Key的哈希值，例如MD5啥的。。。接著進行一次取模的操作，通過餘數來確定將這個Key保存到哪一台伺服器上。。。
嗯，這種方法確實很簡單。。。不夠缺存在很大的問題：
當系統中某一台伺服器退出了之後，那麼對於所有Key的哈希分布都得重新來過，以前的快取也就基本失效了。。。
同時：
如果在系統中加入新的伺服器，所有的Key的哈希分布也都失效了。。。
接下來就可以引入一致性哈希了。。。它就是用於解決這種問題的了。。。
這裡無恥的盜一張圖：
這裡的關鍵就是，不光是要對快取的key進行哈希，同時也需要伺服器也提供一個key進行哈希，然後將其分布在一個閉圓上，在決定一個key的分布的時候，這裡通過找到第一個大於這個key的哈希值的伺服器就行了。。。
這樣在當一台伺服器退出之後，或者有新的伺服器加入進來之後，只會影響一部分的key的哈希分布，不至於導致所有的key的哈希分布都失效。。。。
另外，如果伺服器比較少的情況下，一般都會引入虛擬節點的概念。。也就是一個伺服器在圓上對應多個節點。。。
當然這個只是對一致性哈希比較皮毛的理解。。。對於其在分散式系統中其他的高端用法也不太清楚。。不過好在以後不用怕再遇到這概念了。。
這裡還簡單的實現了一個簡單的一致性哈希演算法。。。用Python寫的：
# -*- coding: utf-8 -*- import hashlib class YHash(object): def __init__(self, nodes=None, n_number=3): """ :param nodes: 所有的節點 :param n_number: 一個節點對應多少個虛擬節點 :return: """ self._n_number = n_number #每一個節點對應多少個虛擬節點，這裡默認是3個 self._node_dict = dict() #用於將虛擬節點的hash值與node的對應關係 self._sort_list = [] #用於存放所有的虛擬節點的hash值，這裡需要保持排序 if nodes: for node in nodes: self.add_node(node) def add_node(self, node): """ 添加node，首先要根據虛擬節點的數目，創建所有的虛擬節點，並將其與對應的node對應起來 當然還需要將虛擬節點的hash值放到排序的裡面 這裡在添加了節點之後，需要保持虛擬節點hash值的順序 :param node: :return: """ for i in xrange(self._n_number): node_str = "%s%s" % (node, i) key = self._gen_key(node_str) self._node_dict[key] = node self._sort_list.append(key) self._sort_list.sort() def remove_node(self, node): """ 這裡一個節點的退出，需要將這個節點的所有的虛擬節點都刪除 :param node: :return: """ for i in xrange(self._n_number): node_str = "%s%s" % (node, i) key = self._gen_key(node_str) del self._node_dict[key] self._sort_list.remove(key) def get_node(self, key_str): """ 返回這個字元串應該對應的node，這裡先求出字元串的hash值，然後找到第一個小於等於的虛擬節點，然後返回node 如果hash值大於所有的節點，那麼用第一個虛擬節點 :param : :return: """ if self._sort_list: key = self._gen_key(key_str) for node_key in self._sort_list: if key <= node_key: return self._node_dict[node_key] return self._node_dict[self._sort_list[0]] else: return None @staticmethod def _gen_key(key_str): """ 通過key，返回當前key的hash值，這裡採用md5 :param key: :return: """ md5_str = hashlib.md5(key_str).hexdigest() return long(md5_str, 16) fjs = YHash(["127.0.0.1", "192.168.1.1"]) print fjs.get_node("fjs32121")
