PHP完成一致性哈希算法的细致引见（代码示例）【php教程】,php

本篇文章给人人带来的内容是关于PHP完成一致性哈希算法的细致引见（代码示例），有肯定的参考价值，有须要的朋侪可以参考一下，愿望对你有所协助。

一、案例剖析
（1）题目概述

假定我们的图片数据匀称的分派在三台效劳（离别标注为效劳器A，效劳器B、效劳器C）上面，如今我们要从内里取图片，效劳端在拿到这个要求后，怎么会指定，这张图片是存在效劳器A、效劳器B，照样效劳器C上面呢？如果去遍历，两三台还好说，但那也太out了，当效劳器的数目抵达成百上千台的时刻，还敢说去遍历吗？

（2）处理方案

a、经由过程存储映照关联

起首我们可能会想到，可以搞一个中间层来纪录图片存储在哪一个效劳器上面，以下：

logo1.png =====》效劳A

ogo2.png =====》效劳B

logo3.png =====》效劳C

如许，每当要求过来的时刻，我们先去要求图片与效劳器的映照关联，找到图片存储的效劳器，在向指定的效劳器发出要求。从完成的角度来讲，这是可行的，然则在存储图片的时刻，我们也必需存储图片与效劳器的映照关联，这显著加大了事情量，其保护也是一个题目，一旦存储的图片和效劳器映照关联涌现了题目，全部体系就挂了。

b、hash算法

既然我们要消除存储映照关联，这个时刻，人们想到了hash算法。如

图片在存储的时刻，根据图片称号（logo1.png），经由过程hash算法求出散列值val，经由过程对val举行取模，得出的值，就可以推断图片应当存储在哪一个效劳器上面。以下：

key = hash(imgName) % n

个中：

imgName为图片称号，

n为效劳器的个数，

key代表图片应当存储在第几个效劳器上面。

当要求过来的时刻，比方要求logo1.png这个图片，效劳端根据上述公式盘算出的key，就可以推断该logo1.png存储在哪一个效劳器上面。PHP完成以下：

$hostsMap = ['img1.findme.wang', 'img2.findme.wang', 'img3.findme.wang'];
 
function getImgSrc($imgName) {
    global $hostsMap;
    $key = crc32($imgName) % count($hostsMap);
    return 'http://' . $hostsMap[abs($key)] . '/' . $imgName;
}
//测试
var_dump(getImgSrc("logo1.png"));
var_dump(getImgSrc("logo2.png"));
var_dump(getImgSrc("logo3.png"));

输出：

此时，我们由存储映照关联变成盘算效劳器的序号，确切极大的简化了事情量。

然则一旦新增机械，就异常麻烦了，由于n变了，险些一切的序列号key也变了，因而须要大批的数据迁徙事情。

C、一致性hash算法

一致性hash算法，是一种特别的hash算法，旨在处理当node数（如存储图片的效劳器数目）变化时刻，只管少数据的迁徙。

其基本思想：

1、起首把0~2的32次方个点，匀称的散布到一个圆环上面，以下：

2、然后将一切的节点node（存储图片的效劳器）经由过程hash盘算后，对232取余，然后也映照到hash环上面，以下：

3、当要求过来的时刻，比方要求logo1.png这个图片，经由过程hash盘算后，对232取余，然后也映照到hash环上面，以下：

4、然后顺时针迁移转变，第一个抵达的节点node，就认为是存储logo1.png图片的效劳器。

从上面可以得知，实在一致性hash的亮点，起首在于对节点node（存储图片的效劳器）和对象（图片）都举行了hash盘算和映照，其次是闭环的设想。

长处：当新增机械的时刻，仅仅标志出来的地区受到影响，以下图：

瑕玷：当节点node比较少的时刻，每每缺乏平衡性，由于经由hash盘算后，映照到hash环上面的节点node，并非匀称散布的，致使了有的机械负载很高，有的机械很余暇。

PHP完成以下：

$hostsMap = ['img1.findme.wang', 'img2.findme.wang', 'img3.findme.wang'];
$hashRing = [];
 
function getImgSrc($imgName){
    global $hostsMap;
    global $hashRing;
    //将节点映照到hash环上面
    if (empty($hashRing)) {
        foreach($hostsMap as $h) {
            $hostKey = fmod(crc32($h) , pow(2,32));
            $hostKey = abs($hostKey);
            $hashRing[$hostKey] = $h;
        }
        //从小到大排序，便于查找
        ksort($hashRing);
    }
 
    //盘算图片hash
    $imgKey = fmod(crc32($imgName) , pow(2,32));
    $imgKey = abs($imgKey);
    foreach($hashRing as $hostKey => $h) {
        if ($imgKey < $hostKey) {
            return 'http://' . $h . '/' . $imgName;
        }
    }
    return 'http://' . current($hashRing) . '/' . $imgName;
}
 
var_dump(getImgSrc("logo1.png"));
var_dump(getImgSrc("logo2.png"));
var_dump(getImgSrc("logo3.png"));

输出效果以下：

至于为何运用fmod函数不实用求余运算符%，重要是由于pow(2,32)在32位操作体系上面，超高了PHP_INT_MAX，详细可以参考上一篇文章“PHP中对大数求余报错Uncaught pisionByZeroError: Modulo by zero”。

d、经由过程假造节点优化一致性hash算法

为了进步一致性hash算法的平衡性，我们起首可以想到的是，增添节点数，然则机械毕竟是须要经费啊，不是说增就可以随便增，那就增添假造节点，如许就没毛病了。思绪以下：

1、假定host1、host2、host3，都离别有3个假造节点，如host1的假造节点为host1_1、host1_2、host1_3

2、然后将一切的假造节点node（存储图片的效劳器）经由过程hash盘算后，对232取余，然后也映照到hash环上面，以下：

然后，接下来步骤同一致性hash算法一致，只是末了须要将假造节点，转为实在的节点。

PHP完成以下：

$hostsMap = ['img1.findme.wang', 'img2.findme.wang', 'img3.findme.wang'];
$hashRing = [];
 
function getImgSrc($imgName){
    global $hostsMap;
    global $hashRing;
    $virtualNodeLen = 3; //每一个节点的假造节点个数
 
    //将节点映照到hash环上面
    if (empty($hashRing)) {
        foreach($hostsMap as $h) {
            $i = 0;
            while($i < $virtualNodeLen){
                $hostKey = fmod(crc32($h.'_'.$i) , pow(2,32));
                $hostKey = abs($hostKey);
                $hashRing[$hostKey] = $h;
                $i++;
            }
        }
        //从小到大排序，便于查找
        ksort($hashRing);
    }
 
    //盘算图片hash
    $imgKey = fmod(crc32($imgName) , pow(2,32));
    $imgKey = abs($imgKey);
    foreach($hashRing as $hostKey => $h) {
        if ($imgKey < $hostKey) {
            return 'http://' . $h . '/' . $imgName;
        }
    }
    return 'http://' . current($hashRing) . '/' . $imgName;
}
 
var_dump(getImgSrc("login1.png"));
var_dump(getImgSrc("login2.png"));
var_dump(getImgSrc("login3.png"));

实行效果以下：