【分布式的存储系统之一致性哈希算法】

算法有点难以理解，看不懂的可以放弃，毕竟是分布式算法，主要解决怎么把一个值缓存映射到服务器上面，下次查找可以直接从缓存中找回来，而不用再去查找数据库。应用程序首先去缓存取得数据，如果取不到，再去数据库查找，把查找到得数据库缓存到缓存服务器上面，下次就可以从缓存服务器查找相同数据了，从而减轻对数据库的压力,提高网页访问速率。

例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%（n-1）]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。

 问：  如何改进或者换一种方法，使得：

（1）一台服务器死掉后，不会造成大面积的访问错误，

（2）原有的访问基本还是停留在同一台服务器上；

（3）尽量考虑负载均衡。

比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；

hash(object)%N

一切都运行正常，再考虑如下的两种情况；

1 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ；

2 由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ；

1 和 2 意味着什么？这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；

再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。

 

 

一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。这就是取模算法的局限性，因此，引入了一致性哈希算法：

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。 

 

 一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

 

1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

 

2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 

 

3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。 

 

4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

代码如下：

/** 把一个字符串映射为一个hash之后的数字

*  MurMurHash算法，是非加密HASH算法，性能很高， 

*  比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免） 

 *  等HASH算法要快很多，而且据说这个算法的碰撞率很低. 

 *  http://murmurhash.googlepages.com/ 

 */  

 private static 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); 

            // for big-endian version, do this first: 

            // finish.position(8-buf.remaining()); 

            finish.put(buf).rewind(); 

            h ^= finish.getLong(); 

            h *= m; 

        }  

        h ^= h >>> r; 

        h *= m;  

        h ^= h >>> r; 

        buf.order(byteOrder);

        return h; 

    }

 

 

//映射key到真实节点  

public void keyToNode(String key){  

        // 沿环的顺时针找到一个虚拟节点  

        SortedMap<Long, Node> tail = nodes.tailMap(this.hash(key)); 

        if (tail.size() == 0) {  

            return;  

        }  

  treeKey.put(hash(key), tail.get(tail.firstKey()));  

System.out.println(key+"（hash："+hash(key)+"）连接到主机->"+tail.get(tail.firstKey()));  

    }  

 

// 初始化一致性hash环  

 private void init() { 

        nodes = new TreeMap<Long, Node>();  

        treeKey = new TreeMap<Long, Node>();  

        for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点  

            final Node shardInfo = shards.get(i);  

  

            for (int n = 0; n < NODE_NUM; n++)  

                // 一个真实机器节点关联NODE_NUM个虚拟节点  

                nodes.put(hash("SHARD-" + shardInfo.name + "-NODE-" + n), shardInfo);  

        }  

    }  

 

 

 

public class Shard<Node> { // S类封装了机器节点的信息 ，如name、password、ip、port等  

  

    static private TreeMap<Long, Node> nodes; // 虚拟节点到真实节点的映射  

    static private TreeMap<Long,Node> treeKey; //key到真实节点的映射  

    static private List<Node> shards = new ArrayList<Node>(); // 真实机器节点  

    private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数  

    boolean flag = false;  

      

    public Shard(List<Node> shards) {  

        super();  

        this.shards = shards;  

        init();  

    }  

}