记得我人生第一次参加面试的时候，面试官问我的就是这样一个问题: 你有很多台服务器，每台服务器上都存放着很多数据，现在要加一台服务器，如何才能让数据搬迁尽可能的少，同时能让每台服务器经可能的负载均衡。现在才发现，这就是可一致性hash 问题，当时我答了个hashMap中的rehash操作，给糊弄过去了…

具体的内容可见 reference，这里大致记录一下

问题定义

简化问题如下:

有 $m$m 个item，有 $n$n 台机器，将 $m$m 个item 尽量均匀的hash到每一台服务器，同时，当机器出现删减的时候应该能够保证数据移动足够小。

简单实现

用两个hash函数，

$hash_i(x)$hashi​(x), 对 item 做hash

$hash_m(x)$hashm​(x), 对 machine 做hash

hash的范围是一个单位圆(e.g. [0,1] float /[0,2^32-1] int)

每个 item 的hash值所对应的顺时针找到的第一个server，存储这个item 对象，这就是 karger 论文中的核心思想。

假设机器将圆平均分成 $m$m 段
这样做很显然，每台机器的期望对象数目是 $O(\frac{n}{m})$O(mn​) 同时，同时新加入一台机器的时候期望的移动数目是 $O(\frac{n}{m+1})$O(m+1n​)

这样做已经是很好的解决我们的那个问题了。

下面是用一个好的数据结构来维护查找一个item的时间，可以用一棵 BST 来维护这些机器
(e.g. rb-tree )<key: hash_m(server),value: (server)> 他们的key是 server 的hash 值，value 是每一个server对象。

看一下如下几个操作:

1. 插入/delete item

这样插入一个 item 仅仅需要找到 hash(item) 在bst上的后继节点就好了。删除类似

2. insert/delete machine

找到这台机器 $Y$Y 的 后继节点，将节点上 hash(item) 小于 $hash(Y)$hash(Y) 移动到 Y上。

分析

reference

1. MIT adv algorithm lecture note
2. stanford cs 168 lec note 1
3. Karger, David, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web.” In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 654-663. ACM, 1997.

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

转载请保留此版权声明，并注明出处