一致性hash.md

jedis中sharejedis一致性hash实现

• Redis服务器节点划分：将每台服务器节点采用hash算法划分为160个虚拟节点(可以配置划分权重)
• 将划分虚拟节点采用TreeMap存储
• 对每个Redis服务器的物理连接采用LinkedHashMap存储
• 对Key or KeyTag 采用同样的hash算法，然后从TreeMap获取大于等于键hash值得节点，取最邻近节点存储；当* * key的hash值大于虚拟节点hash值得最大值时，存入第一个虚拟节点
• sharded采用的hash算法：MD5 和 MurmurHash两种；默认采用64位的MurmurHash算法；有兴趣的可以 研究下，MurmurHash是一种高效，低碰撞的hash算法；参考地址：

http://blog.csdn.net/yfkiss/article/details/7337382
https://sites.google.com/site/murmurhash/

public static final int DEFAULT_WEIGHT = 1;

private TreeMap<Long, S> nodes; 
private final Hashing algo;// hash算法
//shardinfo对应的jedis连接
private final Map<ShardInfo<R>, R> resources = new LinkedHashMap<ShardInfo<R>, R>();


//shards 所有的服务器节点列表

private void initialize(List<S> shards) {

  // TreeMap的hash环
  nodes = new TreeMap<Long, S>();
  
  // 遍历节点
  for (int i = 0; i != shards.size(); ++i) {
    final S shardInfo = shards.get(i);
     //每个节点创建160个虚拟节点
    if (shardInfo.getName() == null) 
      for (int n = 0; n < 160 * shardInfo.getWeight(); n++){
      nodes.put(this.algo.hash("SHARD-" + i + "-NODE-" + n), shardInfo);
      }
    else for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
      nodes.put(this.algo.hash(shardInfo.getName() + "*" + shardInfo.getWeight() + n), shardInfo);
    }
    resources.put(shardInfo, shardInfo.createResource());
  }
}

// 获取一个节点
public S getShardInfo(byte[] key) {
  //返回大于key的部分子map
  SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
  if (tail.isEmpty()) {
    return nodes.get(nodes.firstKey());
  }
  
  //返回map中key值最小的一个
  return tail.get(tail.firstKey());
}

// 获得一个jedis
public R getShard(String key) {
  return resources.get(getShardInfo(key));
}

public S getShardInfo(String key) {
  return getShardInfo(SafeEncoder.encode(getKeyTag(key)));
}