11月10, 2016

一致性哈希在集群中的引用

一致性哈希介绍

应用场景

一种适用于分布式数据存储的算法。可用于为各类存储引擎提供集群服务器落点判断(如memcached,redis,mysql)等。

比普通哈希的优点

普通哈希

假设你的图片服务器是一个三台服务器的集群,那么当一个图片要存储到这个集群时,如何判断落点应该在哪台服务器上呢,最简单的就是哈希取模。

hash(图片名称) % 3 = [0-2]

这样计算最大的缺点就是当我们增加节点的时候,大部分的缓存都会失效。例如现在集群增加到四台。

hash(图片名称) % 4 = [0-3]

我们计算下当机器从3台增加到4台时,有多少图片的存储落点没有变化(就是%3和%4相等):

公式: 3 / 12(最小公倍数) = 25% (每12个数一个循环,每个循环内有3个数余数相等,大家可以穷举后用数学归纳法总结)。

综上可以得到,75%的图片都会发生变化。(缓存雪崩就是这么来的)

一致性哈希

第一步,我们假设机器和图片名的落点都在一个2^32-1的圆环上(之所以是2^32-1是因为哈希算法通常是32位,e.g crc32 || md5)。

alt

理想状态下,ABC三个点的哈希值应该把整个圆等分成了三份,(设服务器节点是空心圆,图片名称的哈希值是实心圆)

第二步,现在我们在对一些图片的名称进行哈希

alt

我们把图片的哈希值进行顺时针查找,1和2图片顺时针找到了B服务器,那么1和2就储存在B服务器上。以此类推,3和4存储在C上,5和6储存在A上。

第三步,我们增加一个服务器,服务器可能落在任何一个点上,假设最糟糕的情况(通常算法的时间复杂度都是这么做假设的)

alt

此时D和A几乎重合,那么按照上面介绍的顺时针查找的方法,5和6以前是落在A点的,现在落在D点。那么共有2张图片的存储位置发生了变化。

那么我们可以说小于33%(2/6)的图片储存位置发生了变化,怎么样,是不是比普通哈希的结果好多了。

在第一步我们假设了ABC三台服务器ip的哈希值恰巧把2的32次方等分成了三份,现实中,当服务器数量这么小时,很可能分布的没有这么平均。

alt

很可能是以上的情况。

那么当服务器数量很小的时候,我们要用一致性哈希怎么办呢,这时我们可以增加很多虚拟节点。假设三台服务器IP如下

A:192.168.0.1 对应哈希值:hash(192.168.0.1)

B:192.168.0.2 对应哈希值:hash(192.168.0.2)

C:192.168.0.3 对应哈希值:hash(192.168.0.3)

那么我们把三个节点分别虚拟出一个节点出来

A:192.168.0.1 对应哈希值:hash(192.168.0.1)

A1:192.168.0.1#1 对应哈希值:hash(192.168.0.1#1)

B:192.168.0.2 对应哈希值:hash(192.168.0.2)

B1:192.168.0.2#1 对应哈希值:hash(192.168.0.2#1)

C:192.168.0.3 对应哈希值:hash(192.168.0.3)

C1:192.168.0.3#1 对应哈希值:hash(192.168.0.3#1)

alt

这样当图片找到A1时,我们就把图片存到A服务器,B1存到B服务器,C1存到C服务器,现在虽然分布还不均衡,但是不是已经好多了?由此可见,我们设置越多的虚拟节点,图片的分布就会越平均,但相应的我们会增加程序的计算时间。

概念就讲到这,下面放上一致性哈希的PHP实现吧。

代码实现

<?php


/**
 *  一致性哈希实现类
 *  @author naiqianz
 */

class ConsistentHash 
{
    //节点数组
    private  $NodeList = array();

    //储存各节点的标识名称和该名称下所有的节点
    private $NodesName = array();

    //哈希所用函数
    private $Hasher;

    //每个结点虚拟的结点数量
    private $NodeNum;

    function __construct(Hasher $Hasher = null, $NodeNum = "")
    {

        $this->Hasher = empty($Hasher) ? new Crc32_Hasher() : $Hasher;

        $this->NodeNum = empty($NodeNum) ? 6 : $NodeNum;
    }


    /**
    *   增加节点
    *   @param string 机器标识,一般为ip
    */
    public function addNode($target)
    {
        //检查该节点是否存在
        if (array_key_exists($target, $this->NodesName)) {
            throw new Exception("Target already exists");
        }

        $this->NodesName[$target] = array();
        //将该节点加入到列表中
        for ($i=0; $i < $this->NodeNum; $i++) { 
            $position = $this->Hasher->hash($target."#".$i);
            $this->NodeList[$position] = $target;
            $this->NodesName[$target] = $position;
        }

        //排序使新加入的点在合适的位置
        ksort($this->NodeList);

        return $this;

    }

    /**
    *   增加一组节点
    *   @param array 机器标识,一般为ip
    */

    public function addNodes($targets)
    {
        foreach ($targets as $target) {
            $this->addNode($target);
        }

        return $this;
    }

    /**
    *   删除一个节点
    *   @param string 机器标识,一般为ip
    */

    public function deleteNode($target)
    {
        //检查该节点是否存在
        if (!array_key_exists($target, $this->NodesName)) {
            throw new Exception("Target not exists");
        }

        foreach ($this->NodesName[$target] as $node) {
            unset($this->NodeList[$node]);
        }

        unset($this->NodesName[$target]);

    }

    /**
    *  查找到存储节点
    *  @param string 要存储的键
    */
    public function findNode($ResourceKey)
    {
        if (count($this->NodeList) == 0)
            throw new Exception("No Target Now");
        $keyPosition = $this->Hasher->hash($ResourceKey);
        foreach ($this->NodeList  as $key => $value) {
            if ($keyPosition > $key) 
                return $value;
        }
        //如果都没找到,返回第一个值,形成一个圆
        return $this->NodeList[0];
    }


    /**
     * 查找出所有的节点
     */

    public function getAllNodes()
    {
        return $this->NodeList;
    }

}


/**
 *  定义哈希规则
 */

interface Hasher 
{
    public function hash($string);
}

/**
 *  实现哈希
 */
class Crc32_Hasher implements Hasher
{
    public function hash ($string)
    {
        return abs(crc32($string));
    }
}

本文链接:http://www.qiana.info/post/consistentHashing.html

-- EOF --

Comments