一致性哈希算法

在讲本文的主题之前，我们先来看一个现实中的应用场景，那就是分布式缓存。

场景描述：

假设我们现在有三台服务器用于缓存我们的一些文件，比如图片。我么将这三台服务器进行编号便于后面的描述，分别为0号、1号和2号。比如说我们现在大量的图片需要缓存在这些服务器上面，在实际应用中，我们当然希望这些图片能够均匀的分布在各个服务器上面，从而将每台服务器的访问压力尽可能降低。假设我们有三万张图片，那么在我们的三台服务器上，我们希望每台服务器能缓存一万张图片左右。

针对上面的应用场景，你可能会说那对于每个图片随机找个服务器缓存就行了，只要算法随机，那么自然在三台服务器上缓存的图片是差不了多少的。可是如此这样，当我们需要访问图片的时候，就需要遍历几个服务器了，显然这样的处理是不合适的，失去了缓存的意义。

那么我们该怎么做呢？

最简单的办法应该就是采用哈希算法了。我们根据图片的特征，如图片名进行哈希运算，然后得到一个数值，将这个数值和服务器的数量（这里是3）进行取模操作，根据取模操作之后的值来决定将图片缓存在哪个服务器上面，后面在访问图片的时候也根据的运算来确定从哪台服务器上读取，这样只要哈希运算保证足够均匀，那么就基本可以保证图片在服务器上的分布均匀。如下所示：

至此，图片分布式缓存的问题真的能够很好的得到解决吗？

NO。

我们来分析下上面这种简单取模哈希之后可能引起的问题。试想一下，如果现在图片很多，3台服务器压力比较大，我们想增加一台服务器来缓解各个服务器的压力。假设之前有一个图片test.jpg，在之前有3台服务器时通过取模运算得到2，即将图片保存到了服务器2上面。这时候新增一台服务器之后，服务器的数量变成了4，那么取模运算得到的余数肯定不同（分子不变，分母变化），这时候原本缓存的图片在经过取模哈希运算后根本无法再命中之前保存的那些服务器，也就命中不了缓存了，从而导致缓存失效的问题。并且，如果这些服务器上缓存的图片越多，那么缓存失效的就越多。

这并不是我们想要的结果对不对，我们希望不管后面服务器部署结构如何变动，仅仅只对一小部分数据产生影响，最理想的当然是一点都不影响，但显然这不太现实。上述之所以存在这个问题，是因为哈希算法采用的是取模的方式，取模的数值是服务器的数量，而这个数量是随着部署结构的变化而变动的，所以存在上面所说的问题。为了解决这个问题，我们需要用到一致性哈希。

接下来我们进入本文的主题：一致性哈希算法。

一致性哈希的基本概念

本质上来说，一致性哈希也是采用取模运算，只不过他取模时的数值不是服务器的数量了，而是一个很大的整数，准确点说就是2^32次方。由于这里取模的数值是固定的，所以只要哈希的key值不变，那么key经过哈希算法之后进行取模得到的值也肯定不会变，这样命中的服务器自然也就不会变了。

上面我们只有三台服务器时，我们对hash(key)对3取模，而这里我们对2^32取模，我们可以理解为存在2^32次方个服务器。我们将这些服务器散步均匀围成一个圆形，圆上有2^32个点，就像时钟一样，时钟的表面是由60个点组成。

这个圆最顶部认为是起始点0，之后沿顺时针方向，出现的第一个点为1，出现的第二个点未2，…，一直到最后一个点为2^32（也就是起始点0左边的第一个点）。我们将这由2^32次方个点组成的圆环称为hash环。

回到前面我们说到的3台服务器的分布式缓存的应用场景，假设我们这三台服务器分别为服务器A、服务器B和服务器C，这三台服务器在实际部署时都有自己的ip地址，我们根据服务器的ip地址进行某种hash运算，并将计算结果对2^32取模，如下所示：

hash(服务器的ip地址)/(2^32)

从而得到一个位于[0,2^32-1]之间的数值，我们在Hash环上找到这个数值，将其与服务器进行对应，得到如下所示。

至此，我们将服务器和Hash环之间对应了起来，那么对于缓存的图片呢？怎么去命中这些缓存服务器？

假设我们这里使用图片的名称来作为图片的key，那么我们同样可以使用下面的方式计算出来跟这个图片相对应的值，

hash(图片名称)/(2^32)

映射之后的结果如下，橙色代表某个图片经过上述运算之后所得的值对应的在hash环上的点。

至此，服务器和图片都映射到了Hash环上，那么我们怎么将图片和服务器之间映射上了？如下所示，我们按照顺时针方式行进，当代表图片的橙色点遇到的第一个服务器点就是这个图片要缓存的服务器。如下所示，这个图片就被缓存到了服务器A上。

假设这里有多张图片，如下所示，那么每个图片所对应的缓存的服务器如下所示，1号和2号图片缓存在了服务器A上，3号图片缓存在了服务器B上，4号图片缓存在了服务器C上：

一致性哈希怎么解决上面的增减服务器导致的缓存失效问题？

如前所述，当服务器的数量变化之后，将会导致大量的缓存数据失效。那么使用了一致性哈希之后会不会还存在这个问题呢？我们结合上面的图来看下。

假设上面的服务器B突然出故障了，需要从整个部署结构中移除，如下所示：

在移除之前，图片3根据一致性哈希是缓存在服务器B上的，而在移除服务器B之后，图片3根据一致性哈希是需要缓存在服务器C上的，因为从图片3的位置顺时针移动碰到的第一个服务器节点是服务器C。虽然图片B缓存的位置发生了变化，但是我们发现，对于图片1、2和4，他们对应的缓存服务器都是没有变化的。这就是一致性哈希所带来的好处，那就是当服务器数量变化时，只有部分缓存受到影响，服务器越多，受影响的面越小。

一致性哈希可能存在什么问题？

上面的一致性哈希很好的解决了上面分布式缓存的问题，但是一致性哈希真的不存在其他问题了吗？

相信你也发现了，上面我们所说的过程中三个服务器在hash环上的位置是均匀分散的。但是现实中如果真有三台服务器，这三台服务器经过一致性hash运算后可不一定是这样。

那么当有大量的图片根据一致性hash运算后，可能有大量的图片都映射到了一个服务器A上，而只有较少的图片映射到了服务器B和服务器C上。如下所示：

这种情况缓存分布非常不均匀，不能使各台缓存服务器都充分发挥作用，使得资源造成浪费。如果此时服务器A也挂掉了，那么同样也会造成大量缓存的失效问题。我们将这种现象称为Hash偏斜，那么怎么才能有效的避免Hash偏斜呢？

我们可以给Hash环认为增加除实体节点以外的虚拟节点。

什么是虚拟节点？

为什么说是虚拟节点呢？话接上文，在这里其实我们的服务器只有3台，但是我们希望做到这个3台服务器能均匀分布在Hash环上，这时候我们就在想如果我们有很多服务器，那么自然就更容易实现平均分布。然而，真实的服务器只有3台，怎么才能让服务器节点多起来呢？没错，那就是根据已有的真实服务器节点复制出虚拟的服务器节点并将这些虚拟服务器节点映射到Hash环上，当图片映射到这些虚拟服务器节点时，我们就认为这个图片和这个虚拟服务器节点相应的真实服务器才在映射关系。

从上面可以看出，在Hash环上，我们给服务器A、B、C分别复制出来一个虚拟节点。如果需要，我们可以复制出更多的虚拟节点，从而使得缓存的分布更加均匀。

至此关于一致性hash的概念便全部讲完了。接下来我们从实际实现角度来看下一致性hash代码层面到底如何实现，这里我们以Ketama一致性哈希源码实现来看下。

Ketama一致性哈希算法

我们先贴出算法实现：

package com.majing.java.hash;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public final class KetamaNodeLocator {
    private TreeMap<Long, Node> ketamaNodes;
    private HashAlgorithm hashAlg;
    private int numReps = 160;
    public KetamaNodeLocator(List<Node> nodes, HashAlgorithm alg, int nodeCopies) {
        hashAlg = alg;
        ketamaNodes=new TreeMap<Long, Node>();
        numReps= nodeCopies;
        for (Node node : nodes) {
            for (int i = 0; i < numReps / 4; i++) {
                byte[] digest = hashAlg.computeMd5(node.getName() + i);
                for(int h = 0; h < 4; h++) {
                    long m = hashAlg.hash(digest, h);
                    ketamaNodes.put(m, node);
                }
            }
        }
    }
    public Node getPrimary(final String k) {
        byte[] digest = hashAlg.computeMd5(k);
        Node rv=getNodeForKey(hashAlg.hash(digest, 0));
        return rv;
    }
    Node getNodeForKey(long hash) {
        final Node rv;
        Long key = hash;
        if(!ketamaNodes.containsKey(key)) {
            SortedMap<Long, Node> tailMap=ketamaNodes.tailMap(key);
            if(tailMap.isEmpty()) {
                key=ketamaNodes.firstKey();
            } else {
                key=tailMap.firstKey();
            }
            //For JDK1.6 version
//            key = ketamaNodes.ceilingKey(key);
//            if (key == null) {
//                key = ketamaNodes.firstKey();
//            }
        }
        rv=ketamaNodes.get(key);
        return rv;
    }
}

在Ketama一致性哈希算法中，Hash环采用了TreeMap数据结构来保存，并且我们可以看到，在访问到这个TreeMap最后发现没有元素的时候，是使用tailMap.firstKey()来找到数据结构中的第一个元素，从而模拟一个环形的数据结构。

至于刚才上面所说的虚拟节点，在Ketama一致性哈希算法中也有涉及，如下所示：

for (Node node : nodes) {
            for (int i = 0; i < numReps / 4; i++) {
                byte[] digest = hashAlg.computeMd5(node.getName() + i);
                for(int h = 0; h < 4; h++) {
                    long m = hashAlg.hash(digest, h);
                    ketamaNodes.put(m, node);
                }
            }
        }

上面就是遍历每个实体节点，然后复制出很多虚拟节点并影响到Hash环上.需要说明的是这里的hash算法采用的是MD5加密算法，字符串经过MD5运算之后得到一个16个字节的字节数组，在该算法实现过程中，将这16个字节拆分为4组，每组4个字节构成一个Long型数值（算法如下），作为虚拟节点在环中的唯一key。

如下所示：

package com.majing.java.hash;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public enum HashAlgorithm {
    /**
     * MD5-based hash algorithm used by ketama.
     */
    KETAMA_HASH;
    public 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)
                | (digest[0+nTime*4] & 0xFF);
        return rv & 0xffffffffL; /* Truncate to 32-bits */
    }
    /**
     * Get the md5 of the given key.
     */
    public byte[] computeMd5(String k) {
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5.reset();
        byte[] keyBytes = null;
        try {
            keyBytes = k.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("Unknown string :" + k, e);
        }
        md5.update(keyBytes);
        return md5.digest();
    }
}

编写测试代码对上述一致性Hash测试，代码如下：

package com.majing.java.hash;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class HashAlgorithmTest {
    static Random ran = new Random();
    /** key's count */
    private static final Integer EXE_TIMES = 100000;
    private static final Integer NODE_COUNT = 5;
    private static final Integer VIRTUAL_NODE_COUNT = 160;
    public static void main(String[] args) {
        HashAlgorithmTest test = new HashAlgorithmTest();
        /** Records the times of locating node*/
        Map<Node, Integer> nodeRecord = new HashMap<Node, Integer>();
        List<Node> allNodes = test.getNodes(NODE_COUNT);
        KetamaNodeLocator locator = new KetamaNodeLocator(allNodes, HashAlgorithm.KETAMA_HASH, VIRTUAL_NODE_COUNT);
        List<String> allKeys = test.getAllStrings();
        for (String key : allKeys) {
            Node node = locator.getPrimary(key);
            Integer times = nodeRecord.get(node);
            if (times == null) {
                nodeRecord.put(node, 1);
            } else {
                nodeRecord.put(node, times + 1);
            }
        }
        System.out.println("Nodes count : " + NODE_COUNT + ", Keys count : " + EXE_TIMES + ", Normal percent : " + (float) 100 / NODE_COUNT + "%");
        System.out.println("-------------------- boundary  ----------------------");
        for (Map.Entry<Node, Integer> entry : nodeRecord.entrySet()) {
            System.out.println("Node name :" + entry.getKey() + " - Times : " + entry.getValue() + " - Percent : " + (float)entry.getValue() / EXE_TIMES * 100 + "%");
        }
    }
    /**
     * Gets the mock node by the material parameter
     * 
     * @param nodeCount 
     *         the count of node wanted
     * @return
     *         the node list
     */
    private List<Node> getNodes(int nodeCount) {
        List<Node> nodes = new ArrayList<Node>();
        for (int k = 1; k <= nodeCount; k++) {
            Node node = new Node("node" + k);
            nodes.add(node);
        }
        return nodes;
    }
    /**
     *    All the keys    
     */
    private List<String> getAllStrings() {
        List<String> allStrings = new ArrayList<String>(EXE_TIMES);
        for (int i = 0; i < EXE_TIMES; i++) {
            allStrings.add(generateRandomString(ran.nextInt(50)));
        }
        return allStrings;
    }
    /**
     * To generate the random string by the random algorithm
     * <br>
     * The char between 32 and 127 is normal char
     * 
     * @param length
     * @return
     */
    private String generateRandomString(int length) {
        StringBuffer sb = new StringBuffer(length);
        for (int i = 0; i < length; i++) {
            sb.append((char) (ran.nextInt(95) + 32));
        }
        return sb.toString();
    }
}

测试结果如下所示：

从测试结果来看，对于10万个key，基本平均分布在5个节点上，可见效果还是可以的。
关于一致性哈希的算法实现还有很多，比较出名的有MurmurHash、CityHash等等，感兴趣的读者可以自己查阅相关资料，谢谢。