工程师常使用服务器集群来设计和实现数据缓存,以下是常见的策略:
1.无论是添加、查询还是删除数据,都先将数据的id通过哈希函数转换成一个哈希值,记为key。
2.如果目前机器有N台,则计算key%N的值,这个值就是该数据所属的机器编号,无论是添加、删除还是查询操作,都只在这台机器上进行。
请分析这种缓存策略可能带来的问题,并提出改进的方案。
算法思想:
哈希函数:输入域无穷,输出域在一个固定区间
哈希函数使得输入域尽可能均匀的分布在输出域上,输入域数据越大,分布越均匀。
哈希函数又称散列函数,哈希码为哈希函数的返回值。
服务器集群设计和实现数据缓存的一般策略中,因为哈希码是均匀的,所以每个服务器上的数据缓存是均匀的。但当增加或减少机器时,N值会变化,导致整个数据在机器上的分布变化,造成数据的大量迁移,因此一般改为一致性哈希。
把哈希码抽象成一个环,将A,B,C三个服务器打在哈希码的如图位置,是均匀分布的,但当又加入一个D服务器后,D只分担了BC之间的数据量,其他的数据量没有变化,并不能达到我们的要求。因此引入虚拟节点的概念。
假设有A,B两个物理节点,每个节点有1000个虚拟节点,每次不是把真实物理节点打在哈希码上,而是对应的1000个虚拟节点打在哈希码环上,因为数量相对够大,所以分布是均匀的。当有个物理节点C要加入时,他也有对应的1000个虚拟点打在哈希码上,因为数量大,也能看成是均匀的。
根据虚拟点来找到相应的物理节点就可以解决上述问题了。