引言
最后一道海量数据的处理问题
题目
工程师使用服务器集群来设计和实现海量数据缓存,以下是常见的策略:
- 无论是添加,删除还是修改数据,都先将数据的id通过哈希函数转化成一个哈希值,记为key.
- 假设当前有N台机器,则计算key%N的值,这个值就是数据所在的机器的编号,无论是添加还是删除还是查询,都只能在这台机器上处理.
分析
其中使用机器是这个种策略的核心,这里也使用了key%N.这种缓存策略的潜在问题就是如果增加或者删除机器时(N发生变化)代价会非常高,所有的数据都要更改自己的哈希值,然后将这个哈希值都新的机器编号进行取模,会有大规模的数据迁移.
这时候我们使用一致性哈希算法,这是一种很好的数据缓存方案.
我们在布隆过滤器中了解了哈希函数的特性,即哈希函数有一个固定的输出域S,我们在这里假设哈希值是2^32 次方,范围也就是0-----2^32-1这个空间中,我们可以将这些数字头尾相连,想象成一个闭合的环形,那么我们计算出的id肯定就在这个环的一个特定位置,我们截取以下书中的一个图:
图片.png
进一步的,我们将机器引入到这个环中,
图片.png
data1经过哈希函数计算的值为key1,然后顺时针最近的机器是machine2,那么我们将认为data1是归属于machine2的,同理,我们可以知道data2(key2)是归属于machine3的,data3,data4是归属于machine1的.
增加数据时的处理
我们假设在这个圈上,有m1,m2两台机器,然后有三个数据data1,data2,data3.具体如下图:
图片.png
图中的箭头也给我们指向了,data3归属于m1,data1,data2归属于m2的,现在我们增加一台机器在m1和m2之间,具体的位置如下图:
图片.png
这个时候,按图中的情况data1就归属于m3了,这个时候只需将m2中的数据取出给m3即可,这样操作调整的代价是很小的.我们看书中是怎么描述的
图片.png
机器负载不均的情况
图片.png
如上图所示,这种情况下,机器没有均匀的分布在这个范围中,所以m1的负担要比m2的负担要大很多.这个时候,一致性哈希算法就引入了虚拟节点机制,通过不同的哈希函数,对于对个位置放置一台机器,具体做法就是在机器的ip或者主机后面添加编号和端口号来实现.对于上面的m1和m2就可以转化成四台虚拟机器m1-1,m1-2,m2-1,m2-2
图片.png
图片.png
