posted on 2012-10-10 11:32
云云 阅读(48716)
评论(5)
一致性哈希算法是分布式系统中常用的算法。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%n，key是数据的key，n是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
因此，引入了一致性哈希算法：
把数据用hash函数（如md5），映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点b，将k1存储到b这个节点中。
如果b节点宕机了，则b上的数据就会落到c节点上，如下图所示：
这样，只会影响c节点，对其他的节点a，d的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即c节点由于承担了b节点的数据，所以c节点的负载会变高，c节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。
为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：
图中的a1、a2、b1、b2、c1、c2、d1、d2都是虚拟节点，机器a负载存储a1、a2的数据，机器b负载存储b1、b2的数据，机器c负载存储c1、c2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。
实现：
- public class shard
{ private treemap nodes; private list shards; private final int node_num = 100; public shard(list shards) { super(); this.shards = shards; init(); } private void init() { nodes = new treemap(); for (int i = 0; i != shards.size(); i) { final s shardinfo = shards.get(i); for (int n = 0; n < node_num; n ) nodes.put(hash("shard-" i "-node-" n), shardinfo); } } public s getshardinfo(string key) { sortedmap tail = nodes.tailmap(hash(key)); if (tail.size() == 0) { return nodes.get(nodes.firstkey()); } return tail.get(tail.firstkey()); } private long hash(string key) { bytebuffer buf = bytebuffer.wrap(key.getbytes()); int seed = 0x1234abcd; byteorder byteorder = buf.order(); buf.order(byteorder.little_endian); long m = 0xc6a4a7935bd1e995l; int r = 47; long h = seed ^ (buf.remaining() * m); long k; while (buf.remaining() >= 8) { k = buf.getlong(); k *= m; k ^= k >>> r; k *= m; h ^= k; h *= m; } if (buf.remaining() > 0) { bytebuffer finish = bytebuffer.allocate(8).order( byteorder.little_endian); finish.put(buf).rewind(); h ^= finish.getlong(); h *= m; } h ^= h >>> r; h *= m; h ^= h >>> r; buf.order(byteorder); return h; } }