Redis整合性hash

Redis整合性hash
1.整合性hashに関する理論知識。

* http://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html
* http://blog.csdn.net/cywosp/article/details/23397179/

2.整合性hashアルゴリズムの良し悪しについて4つの定義を書きます。

*    (Balance).                         ，                  。
*    (Monotonicity).                           ，            ，                                   ，                    。
*    (Spread).       ，             ，            。                     ，                  ，            ，                           。            ，                   ，          。                   。                  ，          。
*    (Load).                     。                         ，              ，                 。      ，           ，                    。
*    (Smoothness).                               。

3.整合性hashのjavaを実現する

`
public class ConsistentHash {
    private SortedMap<Long,String> ketamaNodes=new TreeMap<Long,String>();
    private int numberOfReplicas=1024;
    private HashFunction hashFunction= Hashing.md5(); //guava
    private List<String> nodes;
    private volatile boolean init=false; //         

    public ConsistentHash(int numberOfReplicas,List<String> nodes){
        this.numberOfReplicas=numberOfReplicas;
        this.nodes=nodes;

        init();
    }

    public String getNodeByKey(String key){
        if(!init)throw new RuntimeException("init uncomplete...");

        byte[] digest=hashFunction.hashString(key, Charset.forName("UTF-8")).asBytes();
        long hash=hash(digest,0);
        //        ，     ，  
        if(!ketamaNodes.containsKey(hash)){
            //      key    Map，         key，            key
            SortedMap<Long,String> tailMap=ketamaNodes.tailMap(hash);
            if(tailMap.isEmpty()){
                hash=ketamaNodes.firstKey();
            }else{
                hash=tailMap.firstKey();
            }

        }
        return ketamaNodes.get(hash);
    }

    public synchronized void addNode(String node){
        init=false;
        nodes.add(node);
        init();
    }

    private void init(){
        //     ，  numberOfReplicas     
        for(String node:nodes){
            //        1 
            for(int i=0;i<numberOfReplicas/4;i++){
                //             
                byte[] digest=hashFunction.hashString(node+i, Charset.forName("UTF-8")).asBytes();
                //Md5   16       ， 16            ，          ，                      
                for(int h=0;h<4;h++){
                    Long k = hash(digest,h);
                    ketamaNodes.put(k,node);
                }
            }
        }
        init=true;
    }

    public void printNodes(){
        for(Long key:ketamaNodes.keySet()){
            System.out.println(ketamaNodes.get(key));
        }
    }

    public static long hash(byte[] digest, int nTime)
    {
        long rv = ((long)(digest[3 + nTime * 4] & 0xFF) << 24)
                | ((long)(digest[2 + nTime * 4] & 0xFF) << 16)
                | ((long)(digest[1 + nTime * 4] & 0xFF) << 8)
                | ((long)digest[0 + nTime * 4] & 0xFF);
        return rv;
    }
}
`

4.以下はjedisの一致性hashを見て実現します。
1.まず一例を見て、ShardedJedPoolを使ってredisクラスタに接続する三つのredisがあります。

`
public class ShardedRedis {
    public static void main(String[] args){
        GenericObjectPoolConfig config=new GenericObjectPoolConfig();
        config.setMaxTotal(1000);
        config.setMaxIdle(500);

        List<JedisShardInfo> jedisShardInfoList=new ArrayList<JedisShardInfo>();
        JedisShardInfo shardInfo1=new JedisShardInfo("192.168.217.157",6380);
        JedisShardInfo shardInfo2=new JedisShardInfo("192.168.217.157",6381);
        JedisShardInfo shardInfo3=new JedisShardInfo("192.168.217.157",6382);
        jedisShardInfoList.add(shardInfo1);
        jedisShardInfoList.add(shardInfo2);
        jedisShardInfoList.add(shardInfo3);

        ShardedJedisPool pool=new ShardedJedisPool(config,jedisShardInfoList);

        set("user1","a",pool);
        set("user12","a",pool);
        set("user13","a",pool);
        set("usera","a",pool);
        set("userb","a",pool);
    }

    public static void set(String key,String value,ShardedJedisPool pool){
        ShardedJedis shardedJedis=pool.getResource();
        shardedJedis.set(key,value);
        pool.returnResource(shardedJedis);
    }
}

`

2.jedis実現

* Jedis   ShardedJedis redis       ,ShardedJedis      ：<br/>
`
public Sharded(List<S> shards, Hashing algo, Pattern tagPattern) {
    this.algo = algo;
    this.tagPattern = tagPattern;
    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.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());
    }
}

// key，value      shard
 public String set(String key, String value) {
    Jedis j = getShard(key);
    return j.set(key, value);
 }

public R getShard(String key) {
    return resources.get(getShardInfo(key));
}

//  key  shard
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());
}
`
*     jedis    hash     ， redis           ，         hash  redis  。