通过PHP实现一致性哈希算法

tulayang 发布于2019-07-01 12:32 / 2112人阅读

摘要：通过虚拟节点优化一致性算法为了提高一致性算法的平衡性，我们首先能够想到的是，增加节点数，但是机器毕竟是需要经费啊，不是说增就能随意增，那就增加虚拟节点，这样就没毛病了。

一、案例分析
（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 DivisionByZeroError: 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"));

执行结果如下：

二、备注
1、取模与取余的区别？

取余，遵循尽可能让商向0靠近的原则

取模，遵循尽可能让商向负无穷靠近的原则

1、什么是CRC算法？

CRC（Cyclical Redundancy Check）即循环冗余码校验，主要用于数据校验，常用的有CRC16、CRC32，其中16、32代表多项式最高次幂。

GPU云服务器云服务器一致性哈希算法哈希一致性一致性哈希 golang 一致性哈希

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/30928.html

[PHP内核探索]PHP中的哈希表

摘要：的介绍哈希表是实现字典操作的一种有效数据结构。因此，实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。取而代之的是通过应用哈希表的，然后只取哈希表的低位。由上面可以看到，的哈希表实现相当复杂。在PHP内核中，其中一个很重要的数据结构就是HashTable。我们常用的数组，在内核中就是用HashTable来实现。那么，PHP的HashTable是怎么实现的呢？最近在看H...

Yuanf 2019-06-27 14:00 评论0 收藏0
memcached分布式原理与实现

摘要：哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。平衡性平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。 memcached分布式原理与实现标签（空格分隔）： nosql 0x01 概况 1.1 什么是memcached memcached是一个分布式，开源的数据存储引擎。memcach...

Ververica 2019-08-06 12:27 评论0 收藏0
memcached分布式原理与实现

摘要：哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。平衡性平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。 memcached分布式原理与实现标签（空格分隔）： nosql 0x01 概况 1.1 什么是memcached memcached是一个分布式，开源的数据存储引擎。memcach...

LiuRhoRamen 2019-06-24 18:07 评论0 收藏0
什么是一致性Hash算法？

摘要：五一致性算法的容错性和可扩展性现假设不幸宕机，可以看到此时对象不会受到影响，只有对象被重定位到。综上所述，一致性算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。最近有小伙伴跑过来问什么是Hash一致性算法，说面试的时候被问到了，因为不了解，所以就没有回答上，问我有没有相应的学习资料推荐，当时上班，没时间回复，晚上回去了就忘了这件事，今天突然看到这个，...

feng409 2019-07-01 12:32 评论0 收藏0
如何对用户密码进行加密

摘要：结论对用户密码进行加密时需要做到防止用户密码明文被窃听交给，明文传输。为什么盐可以明文存储攻击者很难有足够的计算资源和存储空间建立海量的哈希值密码数据库，针对单条用户记录，建立哈希值密码数据库进行攻击的成本过高。摘要密码验证是很常见的需求，如何在实现功能之余，防止用户密码泄露，已经有了很成熟的方案。这篇文章把自己的思考和结论做一下记录。结论对用户密码进行加密时需要做到：防止用...

张率功 2019-06-28 14:31 评论0 收藏0