PHP에서 일관된 해싱 알고리즘 구현에 대한 자세한 소개(코드 예)

이 기사는 PHP에서 일관된 해싱 알고리즘을 구현하는 방법에 대한 자세한 소개(코드 예제)를 제공합니다. 이는 특정 참조 가치가 있으므로 도움이 될 수 있습니다.

1. 사례 분석
(1) 문제 개요

이미지 데이터가 세 가지 서비스(각각 서버 A, 서버 B, 서버 C로 표시됨)에 균등하게 분산되어 있다고 가정합니다. 이제 해당 서비스에서 사진을 가져오고 싶습니다. , 이 요청을 받은 후 서버는 이 사진이 서버 A, 서버 B 또는 서버 C에 있는지 어떻게 지정할 수 있습니까? 순회하려면 서버 2~3개면 괜찮지만, 서버 수가 수백, 수천 개에 이르면 감히 순회를 이야기할 수 있을까요?

(2) 솔루션

a, 스토리지 매핑 관계를 통해

우선, 이미지가 어느 서버에 저장되어 있는지 기록하는 중간 레이어를 다음과 같이 생성할 수 있다고 생각할 수 있습니다.

logo1.png ==== =》 Service A

ogo2.png =====》 Service B

logo3.png =====》 Service C

이렇게 요청이 올 때마다 먼저 매핑을 요청합니다. 이미지와 서버 간의 관계를 확인하고, 이미지가 저장된 서버를 찾아 지정된 서버에 요청합니다. 구현 관점에서 볼 때 이는 가능하지만 사진을 저장할 때 사진과 서버 간의 매핑 관계도 저장해야 하므로 작업량이 확실히 증가하고 일단 저장된 사진과 사진을 유지 관리하는 것도 문제입니다. 서버 매핑 관계에 문제가 있으면 시스템 전체가 중단됩니다.

b, 해시 알고리즘

저장 매핑 관계를 배제하고 싶기 때문에 이때 사람들은 해시 알고리즘을 떠올립니다. 예를 들어

사진이 저장되면 사진 이름(logo1.png)에 따라 해시 알고리즘을 통해 해시 값 val을 구하고, val의 모듈로를 취하면 얻은 값을 다음과 같이 판단할 수 있습니다. 사진은 어느 서버에 저장되어야 할까요? 다음과 같습니다:

key = hash(imgName) % n

여기서:

imgName은 이미지의 이름이고,

n은 서버 수이며,

key는 이미지가 저장되어야 하는 서버를 나타냅니다.

예를 들어 logo1.png 이미지를 요청하는 요청이 오면 서버는 위 수식으로 계산된 키를 기반으로 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이 변경되고, 거의 모든 일련번호 키도 변경되므로 많은 데이터 마이그레이션 작업이 필요하기 때문에 매우 번거롭습니다.

C. 일관된 해시 알고리즘

일관적인 해시 알고리즘은 노드 수(예: 이미지를 저장하는 서버 수)가 변경될 때 데이터 이동을 최소화하도록 설계된 특수 해시 알고리즘입니다.

기본 아이디어:

1. 먼저 다음과 같이 링에 0부터 2까지의 포인트를 32의 거듭제곱으로 균등하게 분배합니다.

2 그런 다음 모든 노드 노드(사진 저장). 해시 계산 후 나머지 232를 계산하여 다음과 같이 해시 링에 매핑합니다.

3. 예를 들어 logo1.png 이미지를 요청하는 경우 해시 계산 후 232 Take를 수행합니다. 나머지는 다음과 같이 해시 링에 매핑합니다.

4 그런 다음 시계 방향으로 돌리면 가장 먼저 도착한 노드가 logo1.png 이미지를 저장하는 서버로 간주됩니다.

위에서 볼 수 있듯이 실제로 일관된 해싱의 하이라이트는 첫째로 노드(사진을 저장하는 서버)와 개체(그림) 모두의 해시 계산 및 매핑이고, 둘째로 폐쇄 루프 설계입니다.

장점: 새로운 머신이 추가되면 아래와 같이 표시된 영역만 영향을 받습니다.

단점: 상대적으로 노드 수가 적은 경우 해시 계산 후 균형이 부족한 경우가 많습니다. 해시 링의 노드가 균등하게 분산되지 않아 일부 시스템의 로드가 매우 심하고 일부 시스템은 유휴 상태가 됩니다.

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="PHP에서 일관된 해싱 알고리즘 구현에 대한 자세한 소개(코드 예)"></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="PHP에서 일관된 해싱 알고리즘 구현에 대한 자세한 소개(코드 예)"></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="PHP에서 일관된 해싱 알고리즘 구현에 대한 자세한 소개(코드 예)"></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 중국어 웹사이트의 기타 관련 기사를 참조하세요!