一、场景描述
假设有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为 01号、02号、03号，现在有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。也就是说，我们希望每台服务器能够缓存1万张左右的图片，那么我们应该怎样做呢？
常见的做法是对缓存项的键进行哈希，将hash后的结果对缓存服务器的数量进行取模操作，通过取模后的结果，决定缓存项将会缓存在哪一台服务器上
hash（图片名称）% N
存在的问题：
当服务器数量发生改变时，比如新增加一台缓存服务器，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据；
同理，假设突然有一台缓存服务器出现了故障，那么我们则需要将故障机器移除，那么缓存服务器数量从3台变为2台，同样会导致大量缓存在同一时间失效，造成了缓存的雪崩，后端服务器将会承受巨大的压力，整个系统很有可能被压垮。为了解决这种情况，就有了一致性哈希算法。
二、一致性hash 算法是什么？
一致性哈希算法也是使用取模的方法，但是取模算法是对服务器的数量进行取模，而理论上一致性哈希算法是对 2^32 取模，具体步骤如下：
-
步骤一：一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为 Hash 环；
将 2^32 想象成一个圆，像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆 -
步骤二：接着将各个服务器使用 Hash 函数进行哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，从而确定每台机器在哈希环上的位置
哈希算法：hash（服务器的IP） % 2^32；计算结果一定是 0 到 2^32-1 之间的整数，那么 hash 环上必定有一个点与这个整数对应，所以我们可以使用这个整数代表服务器，也就是服务器就可以映射到这个环上 -
步骤三：最后使用算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针寻找，第一台遇到的服务器就是其应该定位到的服务器
图片的名称作为 key，所以我们使用下面算法将图片映射在哈希环上：hash（图片名称） % 2^32; 只要从图片的位置开始，沿顺时针方向遇到的第一个服务器就是图片存放的服务器了
graph LR
A(())三、一致性hash的优缺点
优点：
一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，只有部分缓存会失效，不至于将所有压力都在同一时间集中到后端服务器上，具有较好的容错性和可扩展性。缺点：
一致性哈希算法在服务节点太少的情况下，容易因为节点分部不均匀而造成数据倾斜问题，也就是被缓存的对象大部分集中缓存在某一台服务器上，从而出现数据分布不均匀的情况，这种情况就称为 hash 环的倾斜。通常优化方案：
为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点，一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。 具体做法可以在服务器ip或主机名的后面增加编号来实现四、python实现一致性hash
# -*- coding: utf-8 -*-
import hashlib
class ConsistHash(object):
def __init__(self, nodes=None, n_number=12) -> None:
"""
nodes: 所有的节点
n_number: 一个节点对应多少个虚拟节点
"""
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) ->None:
"""
添加node，首先要根据虚拟节点的数目，创建所有的虚拟节点，并将其与对应的node对应起来
当然还需要将虚拟节点的hash值放到排序的里面
这里在添加了节点之后，需要保持虚拟节点hash值的顺序
"""
for i in range(self._n_number):
node_str = "%s#%s" % (node,i) #虚拟节点=n#真实节点#n
key = self._gen_key(node_str) #计算虚拟节点的key
self._node_dict[key] = node #key和真实节点的对应关系
self._sort_list.append(key)
self._sort_list.sort()
@staticmethod
def _gen_key(key_str) ->str:
"""
通过key，返回当前key的hash值，这里采用md5
"""
return hashlib.md5(key_str.encode(encoding='UTF-8')).hexdigest() #16进制
def get_node(self, key_str):
"""
返回这个字符串应该对应的node，这里先求出字符串的hash值，然后找到第一个小于等于的虚拟节点，然后返回node
如果hash值大于所有的节点，那么用第一个虚拟节点
"""
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
def remove_node(self, node):
"""
这里一个节点的退出，需要将这个节点的所有的虚拟节点都删除
"""
for i in range(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)
if __name__ == "__main__":
cons = ConsistHash(["192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4"])
print(cons.get_node("DV001"))
print(cons.get_node("DV002"))
print(cons.get_node("DV003"))
print(cons.get_node("DV004"))
print(cons.get_node("DV005"))
print(cons.get_node("DV006"))
print(cons.get_node("DV007"))
参考链接： https://blog.csdn.net/a745233700/article/details/120814088
