一致性Hash热点
一致性Hash算法是来解决热点问题，如果虚拟节点设置过小热点问题仍旧存在。
关于一致性Hash算法的原理我就不说了，网上有很多人提供自己编写的一致性Hash算法的代码示例，我在跑网上的代码示例发现还是有热点问题。为此我翻阅了Jedis的ShardedJedis类的源码把它的一致性Hash算法提取出来，作为自己的一个工具类，以后自己工程开发中用起来也放心些，毕竟jedis的代码经受了大家的验证。
提取jedis的一致性hash代码作为通用工具类
看看人家码神写的代码，这泛型，这继承，这多态用的，写的真是好，代码通用性真是没话说。
在Sharded方法中：
1 ,定义了一个TreeMap ，TreeMap 用于存储虚拟节点（在初始化方法中，将每台服务器节点采用hash算法划分为160个（默认的，DEFAULT_WEIGHT）虚拟节点（当然也可以配置划分权重）
2 ，定义一个LinkedHashMap，用于存储每一个Redis服务器的物理连接，其中shardInfo的createResource就是物理连接信息 。
3，对于key采用与初始化时同样的hash（MurmurHash或者MD5）算法，然后从TreeMap获取大于等于键hash值得节点，取最邻近节点；
4，当key的hash值大于虚拟节点hash值得最大值时（也就是tail为空），取第一个虚拟节点。
相关完整的源码可以查看我的github的intsmaze-hash这个model，传送点https://github.com/intsmaze/intsmaze。
package cn.intsmaze.hash.shard;
public class Sharded<R, S extends ShardInfo<R>> {
public static final int DEFAULT_WEIGHT = 1;
private TreeMap<Long, S> nodes;
private final Hashing algo;
private final Map<ShardInfo<R>, R> resources = new LinkedHashMap<ShardInfo<R>, R>();
public Sharded(List<S> shards) {
this(shards, Hashing.MURMUR_HASH); // MD5 is really not good as we works
// with 64-bits not 128
}
public Sharded(List<S> shards, Hashing algo) {
this.algo = algo;
this.shards=shards;
initialize(shards);
}
private void initialize(List<S> shards) {
nodes = new TreeMap<Long, S>();
for (int i = 0; i != shards.size(); ++i) {
final S shardInfo = shards.get(i);
if (shardInfo.getTableName() == 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.getTableName() + "*" + shardInfo.getWeight() + n), shardInfo);
}
resources.put(shardInfo, shardInfo.createResource());//调用IntsmazeShardInfo的createResource()方法 如果我们的实现不需要控制远程的连接，那么这个方法就不没什么用
}
}
/**
* 这个是找到key对应的节点后，不是仅仅返回属于的节点名称而是返回对应的实例连接
* @param key
* @return
*/
public R getShardByResources(String key) {
return resources.get(getShardInfo(key));
}
/**
* 这个是找到key对应的节点后，返回属于的节点名称
* @param key
* @return
*/
public S getShard(String key) {
return getShardInfo(key);
}
public S getShardInfo(byte[] key) {
SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
if (tail.isEmpty()) {
return nodes.get(nodes.firstKey());
}
return tail.get(tail.firstKey());
}
public S getShardInfo(String key) {
return getShardInfo(SafeEncoder.encode(key));
}
}
package cn.intsmaze.hash.shard;
public class IntsmazeShardedConnection extends Sharded<Intsmaze, IntsmazeShardInfo>{
public IntsmazeShardedConnection(List<IntsmazeShardInfo> shards) {
super(shards);
}
public String getTable(String key) {
IntsmazeShardInfo intsmazeShardInfo = getShard(key);
return intsmazeShardInfo.getTableName();
}
}
package cn.intsmaze.hash.shard;
public class IntsmazeShardInfo extends ShardInfo<Intsmaze> {
private String host;
private int port;
public IntsmazeShardInfo(String host, String tableName) {
super(Sharded.DEFAULT_WEIGHT, tableName);
URI uri = URI.create(host);
this.host = uri.getHost();
this.port = uri.getPort();
}
@Override
public Intsmaze createResource() {
return new Intsmaze(this);
}
}
package cn.intsmaze.hash.shard;
public abstract class ShardInfo<T> {
private int weight;
private String tableName;
public ShardInfo() {
}
public ShardInfo(int weight,String tableName) {
this.weight = weight;
this.tableName=tableName;
}
protected abstract T createResource();
}
package cn.intsmaze.hash.shard;
public class Test {
private static IntsmazeShardedConnection sharding;
public static void setUpBeforeClass() throws Exception {
List<IntsmazeShardInfo> shards = Arrays.asList(
new IntsmazeShardInfo("localhost:6379", "intsmaze-A"),
new IntsmazeShardInfo("localhost::6379", "intsmaze-B"),
new IntsmazeShardInfo("localhost::6379", "intsmaze-C"),
new IntsmazeShardInfo("localhost::6379", "intsmaze-D"),
new IntsmazeShardInfo("localhost::6379", "intsmaze-E"));
sharding = new IntsmazeShardedConnection(shards);
}
public void shardNormal() {
Map<String,Long> map=new HashMap<String,Long>();
for (int i = 0; i < 10000000; i++) {
String result = sharding.getTable("sn" + i);
Long num=map.get(result);
if(num==null)
{
map.put(result,1L);
}
else
{
num=num+1;
map.put(result,num);
}
}
Set<Map.Entry<String, Long>> entries = map.entrySet();
Iterator<Map.Entry<String, Long>> iterator = entries.iterator();
while(iterator.hasNext())
{
Map.Entry<String, Long> next = iterator.next();
System.out.println(next.getKey()+"--->>>"+next.getValue());
}
}
public static void main(String[] args) throws Exception {
Test t=new Test();
t.setUpBeforeClass();
t.shardNormal();
}
}没有热点问题
把jedis的源码提取出来后，跑了一下，发现没有热点问题，原理不是采用算法的问题，而是一个物理节点对应的虚拟节点的数量的问题导致使用hash算法后，还是有热点问题。jedis源码物理节点对应虚拟节点时160，而网上大部分代码都是10以下，所以导致了热点问题，这也告诉我们，实现一致性Hash算法时，不要太吝啬，虚拟节点设置的大点，热点问题就不会再有。
相关完整的源码可以查看我的github的intsmaze-hash这个model，传送点https://github.com/intsmaze/intsmaze。