标签归档:一致性哈希

PHP 的哈希算法

PHP 内核实现的哈希算法

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
    register ulong hash = 5381;
    /* variant with the hash unrolled eight times */
    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
    }
    return hash;
}

参照内核实现的哈希算法

function hash0($str)
{
    $length = strlen($str);
    // 不过测试中填 0 显得分散性更好
    $hash = 5381;
    $i = 0;
    for (; $length >= 8; $length -= 8) {
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        $hash = (($hash << 5) + $hash) + ord($str[$i++]);
    }


    switch ($length) {
        case 7:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 6:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 5:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 4:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 3:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 2:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        case 1:
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            break;
        case 0:
            break;
    }
    // 表示 hash 最大值为 0x7FFFFFFF
    return $hash & 0x7FFFFFFF;
}


// 测试
$str  = 'helloworldddfdfdfdfdsfdsdffdsfddfdsfdsfssaafd';
$hash = hash0($str);
echo $hash % 7; // 输出 

一致性哈希

一致性哈希算法出现的原因

在分布式缓存中,如果直接通过对缓存的键哈希然后与服务器的个数取模的方式,当加入新服务器时,会造成整个分布式缓存系统中的缓存失效,因为需要重新对服务器数取模。

一致性哈希算法的原理

假设有 k 个服务器,数据的哈希值范围为 [0,MAX],我们可以把哈希值分成 m 个区,每个机器负责 m / k 个区的缓存,当新来一台服务器时,我们只需把某一个区的缓存从原来服务器移动到新服务器就可以了。

上面说的是一致性哈希的基本思想。除此之外,还会借助一个虚拟的环和虚拟节点。

      虚拟的环就是把缓存键和服务器的哈希值,放到一个 [0,2^32] 的圆上,每台服务器负责存储与上一台服务器顺时针方向的之间的值,当新加入一台服务器时,只需要将这台服务器与上一台服务器之间的缓存移动到该服务器上,就可以了。

      虚拟节点,就是一台服务器往往哈希多个值,以减轻数据倾斜问题,一般是一台服务器有 32 个虚拟节点。

一致性哈希算法

class ConsistentHash
{
    protected $servers = [];
    protected $virtualServers;
    protected $virtualServerNum;


    /**
     * @param array $servers 服务器
     * @param int $virtualServerNum 虚拟节点个数
     */
    public function __construct(array $servers, $virtualServerNum = 32)
    {
        $this->virtualServerNum = $virtualServerNum;
        $this->addServers($servers);
    }


    public function getServers()
    {
        return $this->servers;
    }


    /**
     * 添加服务器
     *
     * @param $servers
     */
    public function addServers($servers)
    {
        if (! is_array($servers)) {
            $servers = [$servers];
        }
        $this->servers = array_merge($this->servers, $servers);
        foreach ($servers as $server) {
            $i = 1;
            while ($i <= 32) {
                $virtualNode = $server.'#'.$i;
                $this->virtualServers[$virtualNode] = $this->hash($virtualNode);
                $i++;
            }
        }
        asort($this->virtualServers);
    }


    /**
     * 删除服务器
     *
     * @param $server
     * @return bool
     */
    public function deleteServer($server)
    {
        $i = 1;
        $delKey = array_search($server, $this->servers);
        if ($delKey !== false) {
            unset($this->servers[$delKey]);
        }
        while ($i <= 32) {
            $virtualNode = $server.'#'.$i;
            unset($this->virtualServers[$virtualNode]);
            $i++;
        }
        return true;
    }


    /**
     * 添加数据
     *
     * @param $key
     * @param $data
     * @return string|string[]|null
     */
    public function add($key, $data)
    {
        $hash = $this->hash($key);
        foreach ($this->virtualServers as $server => $val) {
            if ($hash <= $val) {
                return $this->subServer($server);
            }
        }
        reset($this->virtualServers);
        return $this->subServer(key($this->virtualServers));
    }


    /**
     * 获取数据
     *
     * @param $key
     * @return string|string[]|null
     */
    public function get($key)
    {
        $hash = $this->hash($key);
        foreach ($this->virtualServers as $server => $val) {
            if ($hash <= $val) {
                return $this->subServer($server);
            }
        }
        reset($this->virtualServers);
        return $this->subServer(key($this->virtualServers));
    }


    protected function subServer($server)
    {
        $pattern = '/#[0-9]+/';
        return preg_replace($pattern, '', $server);
    }


    protected function hash($str)
    {
        $length = strlen($str);
        $hash = 5381;
        $i = 0;
        for (; $length >= 8; $length -= 8) {
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            $hash = (($hash << 5) + $hash) + ord($str[$i++]);
        }


        switch ($length) {
            case 7:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 6:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 5:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 4:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 3:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 2:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
            case 1:
                $hash = (($hash << 5) + $hash) + ord($str[$i++]);
                break;
            case 0:
                break;
        }
        return $hash & 0x7FFFFFFF;

参考:

  1. https://www.laruence.com/2009/07/23/994.html
  2. https://www.cnblogs.com/lpfuture/p/5796398.html