首页 > 编程 > Consistent Hashing算法

Consistent Hashing算法

2010年3月12日

网络应用中经常会用到缓存机制,例如memcached。当需要缓存的数据量较大,一个memcached实例存不下的时候,就需要一定的策略将不同的对象分配到不同的memcached实例上。比较常见的方法是对对象的key值做hash,再求余,根据余数分配到不同的cache中。这种简单的方法的扩展性相当差一些,主要体现在cache结点的增加和删除上。假设本来有a个cache结点,因数据量扩大而扩大至b个结点,可以计算得到有 min(a, b) / [a, b]比例的对象的余数没有发生变化,也就是说这些对象仍可以存在于原来的cache结点上。如果每次cache结点数量的扩展都是翻番的,即b=2a,则有50%的对象的缓存失效。但是如果是原有5个结点,增加了2个结点,则会有86%的对象缓存失效,这将对系统的性能造成较大冲击。

所以出现了consistent hashing算法,它可以减少节点变动带来的缓存失效。consistent hashing的实现方法是把缓存对像的key和cache结点本身,分别用一定的算法映射到一个相同的hash空间上,例如一个32位的整数。然后将这个空间想像成一个圆,然后将各key及各cache结点都画在这个圆上。对于每个key,它顺时针碰到的最近的一个cache结点就是它应该存在的地方。如下图所示:

为了防止由于对cache结点的hash算法结果的不均匀,导致cache结点在圆环上的分布过于不均,使得每个cache的负载不同,consistent hashing算法还引用了virtual node的概念。也就是在对cache结点计算hash的时候,通过对hash过程的微调,使每个结点都算出很多(例如200个)hash值,这些值以virtual node的形式添加到环上,所有属于这些virtual node的缓存对象都映射到该实际结点上,这样就基本能保持每个cache结点在hash空间中cover住基本同样多的对象了。

这样,在保证结点基本均匀分布的情况下,将cache结点数从a提高到b,只有(b-a)/b比例的对象缓存失效。对于上文提到的从5个结点添加2个结点的情况,缓存失效率为28%,相比传统算法的86%,性能提高了不少。

不少新的memcached client都已经支持这种算法,如libketama等。但是不同语言的客户端的实现依赖于该语言对对象的serialization实现,可能分配的结果也不一致。我最近做的项目需要同时从Java和C客户端访问同一组cache server,所以我还是自己实现了一个简单的consistent hashing机制。其中,算法中的环结构对应一个SortedMap,每个cache结点均为该树中的一个点,某key顺时针碰到的第一个结点的问题转化成排序树上大于该key的最小结点。(无关代码已略去)

public class ConsistentHashingPartitionStrategy <TTarget, TKey> {

    public static final int                    DEFAULT_REPLICA = 64;

    private final SortedMap <Integer, TTarget> circle          = new TreeMap <Integer, TTarget> ();

    /**
     * Number of virtual nodes we create for a target
     */
    private final int                          replica;

    public void addTarget (TTarget target) {

        for (int i = 0; i < replica; i++) {
            circle.put (this.getTargetHashingFunction ().hash (target.toString() + i), target);
        }
    }

    public void removeTarget (TTarget target) {

        for (int i = 0; i < replica; i++) {
            circle.remove (this.getTargetHashingFunction ().hash (target.toString() + i));
        }
    }

    /**
     * Find the nearest target next to the key hash on the circle.
     */
    public TTarget getTargetForKey (TKey key) {

        if (circle.isEmpty ()) {
            return null;
        }

        int hash = getKeyHashingFunction ().hash (key);

        if (!circle.containsKey (hash)) {
            SortedMap <Integer, TTarget> tailMap = circle.tailMap (hash);
            hash = tailMap.isEmpty () ? circle.firstKey () : tailMap.firstKey ();
        }

        return circle.get (hash);
    }
}

编程 ,

  1. 目前还没有任何评论.
  1. 目前还没有任何 trackbacks 和 pingbacks.