本文内容大致来源于 CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing
0X00#
假设你对 cache 进行水平扩展，那么你便希望将数据较均匀地存储到每一台 cache 中。Hash 算法可以帮助你，比如 MD5(id) % cache_num。理想情况下可以运作，但是现实情况中有很多干扰因素。如果想对这个集群进行扩容，比如增加一个 cache 节点，那么可能引发所有的数据进行重新定位。同样的，如果有一个节点宕机也会产生这种状况
md5('user_id#1001') % 3 # 1
md5('user_id#1002') % 3 # 0
# add a new cache node
md5('user_id#1001') % 4 # 2
md5('user_id#1002') % 4 # 0
一致性哈希可以解决上述的场景，某个节点的添加和移除不会重新分配全部的数据，而只会影响小部分的数据，如果均衡性做的好的话，当添加一个节点时，会均匀地从其它节点移一部分到新的节点上；当删除一个节点的时候，这个节点上的数据会均匀地分配到其它活着的节点上
Karger 一致性哈希算法首先对 cache 进行哈希(可以根据 server name 之类的唯一性标识)，然后散列到一个环上(假设长度为 2^32-1)【下图左】。对于数据我们也同样哈希至环上的某个位置，再顺时针找到第一个 cache 节点，这便是它的存储位置。如果新增了节点 s3，那么原来放到 s0 的一部分数据就可以存放到 s3 上，不会导致所有节点的数据分配受到影响【下图右】
但是这种做法也有些问题。首先 cache 节点应在环上分配均匀。其次如果有一个节点宕机，那么顺时针方向的下一个节点将会承受原来两倍的数据量(分配均匀的情况下)，搞不好会崩溃，然后引发雪崩效应。我们可以通过 “virtual copies” 的方法来解决。具体来说是使用 k 种不同的 Hash 算法来对 cache 节点进行散列。n 个节点，在环上会出现 n × k 次
“virtual copies” 也可用于解决异构 cache 的场景。根据容量或者其他参数来合理地制定 virtual copies 的数量。例如，如果一个 cache 容量是另一个 cache 的两倍，那么应该有两倍的 virtual copies
0X01#
下面是论文中的关于使用何种数据结构的讨论
A hash table isn’t good enough (it doesn’t maintain any order information at all); a heap isn’t good enough (it only maintains a partial order so that identifying the minimum is fast); but recall that binary search trees, which maintain a total ordering of the stored elements, do export a Successor function. Since the running time of this operation is linear in the depth of the tree, it’s a good idea to use a balanced binary search tree, such as a Red-Black tree. Finding the cache responsible for storing a given object x then takes O(log n) time, where n is the number of caches.
Python 实现如下 借助红黑树，个人感觉没必要，直接用 bisect 就行了
import hashlib
from bintrees.rbtree import RBTree
from types import GeneratorType
def md5(data: str) -> int:
"""md5 util function"""
return int(hashlib.md5(data.encode('utf-8')).hexdigest(), 16)
class Node:
"""Node Implemention
>>> n1 = Node('192.168.1.203')
>>> n1.name
'192.168.1.203'
>>> n2 = Node('192.168.1.203', prefix='slave')
>>> n2.name
'slave#192.168.1.203'
>>> n1.nid != n2.nid
True
"""
algorithms = {
'md5': md5
}
def __init__(self, node_name: str, prefix: str='',
nid: int=None, kind: str='md5'):
self._node_name = node_name
if prefix:
self._node_name = '{}#{}'.format(prefix, self._node_name)
self._nid = nid or self.algorithms[kind](self._node_name)
@property
def name(self) -> str:
return self._node_name
@property
def nid(self) -> int:
return self._nid
class ConsistentHashing:
"""Consistent Hashing Implemention
>>> ch = ConsistentHashing()
>>> ch.size
255
>>> ch.join(Node('192.168.1.2'))
>>> ch.node_count
1
>>> ch.join(Node('192.168.1.2', prefix='slave'))
>>> ch.node_count
2
>>> ch.join(Node('192.168.1.65'))
>>> ch.join(Node('192.168.1.232'))
>>> [nid for nid, _ in ch.nodes]
[83, 135, 141, 243]
>>> ch.get_location(0)
83
>>> ch.get_location(39)
83
>>> ch.get_location(100)
135
>>> ch.get_location(141)
141
>>> ch.get_location(244)
83
"""
def __init__(self, size: int=255):
self._rbtree = RBTree()
self._size = size
@property
def size(self)-> int:
return self._size
@property
def nodes(self)-> GeneratorType:
"""a generator"""
return self._rbtree.items()
@property
def node_count(self)-> int:
return self._rbtree.count
def join(self, node):
self._rbtree.insert(node.nid % self._size, node)
def depart(self, node):
self._rbtree.remove(node.nid % self._size, node)
def get_location(self, elem)-> int:
try:
# raise KeyError When no key greater than the elem
# so return the min key, since this is a loop
location = self._rbtree.ceiling_key(elem)
except KeyError:
location = self._rbtree.min_key()
return location
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=False)