登录  /  注册

PHP实现一致性哈希算法的详细介绍(代码示例)

不言
发布: 2019-03-04 13:38:24
转载
2478人浏览过

本篇文章给大家带来的内容是关于php实现一致性哈希算法的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

一、案例分析
(1)问题概述

假设我们的图片数据均匀的分配在三台服务(分别标注为服务器A,服务器B、服务器C)上面,现在我们要从里面取图片,服务端在拿到这个请求后,怎么会指定,这张图片是存在服务器A、服务器B,还是服务器C上面呢?若是去遍历,两三台还好说,但那也太out了,当服务器的数量达到成百上千台的时候,还敢说去遍历吗?

(2)解决方案

a、通过存储映射关系

首先我们可能会想到,可以搞一个中间层来记录图片存储在哪个服务器上面,如下:

logo1.png     =====》 服务A

ogo2.png     =====》 服务B

logo3.png     =====》 服务C

这样,每当请求过来的时候,我们先去请求图片与服务器的映射关系,找到图片存储的服务器,在向指定的服务器发出请求。从实现的角度来说,这是可行的,但是在存储图片的时候,我们也必须存储图片与服务器的映射关系,这明显加大了工作量,其维护也是一个问题,一旦存储的图片和服务器映射关系出现了问题,整个系统就挂了。

b、hash算法

既然我们要排除存储映射关系,这个时候,人们想到了hash算法。如

2095458979-5c7ca121e7705_articlex.png

图片在存储的时候,依据图片名称(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"));
登录后复制

输出:

1956153453-5c7ca1635c91c_articlex.png

此时,我们由存储映射关系变为计算服务器的序号,确实极大的简化了工作量。

但是一旦新增机器,就非常麻烦了,因为n变了,几乎所有的序列号key也变了,于是需要大量的数据迁移工作。

C、一致性hash算法

一致性hash算法,是一种特殊的hash算法,旨在解决当node数(如存储图片的服务器数量)变化时候,尽量少数据的迁移。

其基本思想:

1、首先把0~2的32次方个点,均匀的分布到一个圆环上面,如下:

990454915-5c7ca1779d3f5_articlex.png

2、然后将所有的节点node(存储图片的服务器)通过hash计算后,对232取余,然后也映射到hash环上面,如下:

956894435-5c7ca184b9bac_articlex.png

3、当请求过来的时候,比如请求logo1.png这个图片,通过hash计算后,对232取余,然后也映射到hash环上面,如下:

807439409-5c7ca1918fcb9_articlex.png

4、然后顺时针转动,第一个到达的节点node,就认为是存储logo1.png图片的服务器。

从上面可以得知,其实一致性hash的亮点,首先在于对节点node(存储图片的服务器)和对象(图片)都进行了hash计算和映射,其次是闭环的设计。

优点:当新增机器的时候,仅仅标志出来的区域受到影响,如下图:

4038178100-5c7ca1a7bf490_articlex.png

缺点:当节点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 <p>输出结果如下:</p><p><img src="https://img.php.cn/upload/image/534/248/963/1551677736513489.png" title="1551677736513489.png" alt="628828581-5c7ca1c65ded0_articlex.png"></p><p>至于为什么使用fmod函数不适用求余运算符%,主要是因为pow(2,32)在32位操作系统上面,超高了PHP_INT_MAX,具体可以参考上一篇文章“PHP中对大数求余报错Uncaught pisionByZeroError: Modulo by zero”。</p><p>d、通过虚拟节点优化一致性hash算法</p><p>为了提高一致性hash算法的平衡性,我们首先能够想到的是,增加节点数,但是机器毕竟是需要经费啊,不是说增就能随意增,那就增加虚拟节点,这样就没毛病了。思路如下:</p><p>1、假设host1、host2、host3,都分别有3个虚拟节点,如host1的虚拟节点为host1_1、host1_2、host1_3</p><p>2、然后将所有的虚拟节点node(存储图片的服务器)通过hash计算后,对232取余,然后也映射到hash环上面,如下:</p><p><img src="https://img.php.cn/upload/image/891/291/577/1551677752319649.png" title="1551677752319649.png" alt="3488012023-5c7ca1d7214cf_articlex.png"></p><p>然后,接下来步骤同一致性hash算法一致,只是最后需要将虚拟节点,转为真实的节点。</p><p>PHP实现如下:</p><pre class="brush:php;toolbar:false">$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  $h) {
        if ($imgKey <p>执行结果如下:</p><p><img src="https://img.php.cn/upload/image/947/947/423/1551677769758146.png" title="1551677769758146.png" alt="1283067839-5c7ca1f729486_articlex.png"></p><p><strong>二、备注</strong><br>1、取模与取余的区别?</p><p>取余,遵循尽可能让商向0靠近的原则</p><p>取模,遵循尽可能让商向负无穷靠近的原则</p><p>1、什么是CRC算法?</p><p>CRC(Cyclical Redundancy Check)即循环冗余码校验,主要用于数据校验,常用的有CRC16、CRC32,其中16、32代表多项式最高次幂。</p><p></p>
登录后复制

以上就是PHP实现一致性哈希算法的详细介绍(代码示例)的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
相关标签:
来源:segmentfault网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号