Introduction détaillée à l'implémentation d'un algorithme de hachage cohérent en PHP (exemple de code)

Le contenu de cet article est une introduction détaillée (exemple de code) sur la mise en œuvre d'un algorithme de hachage cohérent en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Analyse de cas
(1) Présentation du problème

Supposons que nos données d'image soient réparties uniformément entre trois services (étiquetés respectivement Serveur A et Serveur A) B, serveur C) ci-dessus, nous voulons maintenant en obtenir l'image. Après avoir reçu cette requête, comment le serveur peut-il spécifier si cette image existe sur le serveur A, le serveur B ou le serveur C ? Si on veut traverser, deux ou trois serveurs, c'est bien, mais c'est trop impossible. Quand le nombre de serveurs atteint des centaines ou des milliers, ose-t-on encore parler de traversée ?

(2) Solution

a. Grâce à la relation de mappage de stockage

Tout d'abord, nous pouvons penser que nous pouvons créer une couche intermédiaire pour enregistrer stockage d'images Sur quel serveur, comme suit :

logo1.png =====》 Service A

ogo2.png =====》 Service B

logo3 .png =====》Service C

De cette façon, chaque fois qu'une requête arrive, nous demandons d'abord la relation de mappage entre l'image et le serveur, trouvons le serveur sur lequel l'image est stockée, puis faisons une requête au serveur spécifié. Du point de vue de la mise en œuvre, cela est faisable, mais lors du stockage des images, nous devons également stocker la relation de mappage entre les images et le serveur, ce qui augmente évidemment la charge de travail, et sa maintenance est également un problème une fois les images stockées et le serveur. serveur S'il y a un problème avec la relation de mappage, l'ensemble du système raccrochera.

b. Algorithme de hachage

Puisque nous voulons exclure la relation de mappage de stockage, à l'heure actuelle, les gens pensent à l'algorithme de hachage. Par exemple, lorsque l'image

est stockée, la valeur de hachage val est calculée via l'algorithme de hachage basé sur le nom de l'image (logo1.png). val, nous obtenons de la valeur, vous pouvez déterminer sur quel serveur l'image doit être stockée. Comme suit :

key = hash(imgName) % n

où :

imgName est le nom de l'image,

n est le nombre de serveurs, et

key représente que l'image doit être stockée sur plusieurs serveurs.

Lorsqu'une requête arrive, par exemple, demandant l'image logo1.png, le serveur peut déterminer sur quel serveur le logo1.png est stocké en fonction de la clé calculée par la formule ci-dessus. L'implémentation PHP est la suivante :

$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"));

Sortie :

À ce stade, nous passons du stockage de la relation de mappage au calcul du numéro de série de le serveur, ce qui constitue en effet une grande simplification et une charge de travail accrue.

Mais une fois qu'une nouvelle machine est ajoutée, c'est très gênant, car n change, et presque toutes les clés du numéro de série changent également, donc beaucoup de travail de migration de données est nécessaire.

C. Algorithme de hachage cohérent

L'algorithme de hachage cohérent est un algorithme de hachage spécial conçu pour résoudre le problème lorsque le nombre de nœuds (tel que le nombre de serveurs qui stockent images) ) change, essayez de migrer le moins de données possible.

L'idée de base :

1. Tout d'abord, répartissez uniformément les points de 0 à 2 à la puissance 32 sur un anneau, comme suit :

2. Calculez ensuite tous les nœuds (serveurs qui stockent des images) via le calcul de hachage, prenez le reste de 232, puis mappez-le à l'anneau de hachage, comme suit :

3. Lorsqu'une requête arrive, par exemple, demandant l'image logo1.png, après le calcul du hachage, prenez le reste de 232, puis mappez-le à l'anneau de hachage, comme suit :

4. Tournez ensuite dans le sens des aiguilles d'une montre. Le premier nœud atteint est considéré comme le serveur qui stocke l'image logo1.png.

Comme vous pouvez le voir ci-dessus, le point culminant d'un hachage cohérent est d'une part le calcul de hachage et le mappage des nœuds (serveurs qui stockent les images) et des objets (images), et d'autre part la conception en boucle fermée.

Avantages : Lorsqu'une nouvelle machine est ajoutée, seule la zone marquée est affectée, comme indiqué ci-dessous :

Inconvénients : Lorsqu'il y a relativement peu de nœuds. , manque souvent d'équilibre, car après le calcul du hachage, les nœuds mappés sur l'anneau de hachage ne sont pas répartis uniformément, ce qui entraîne une charge élevée sur certaines machines et une inactivité sur certaines machines.

L'implémentation PHP est la suivante :

$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>Le résultat de sortie est le suivant : </p><p><img src="https://img.php.cn/upload/image/534/248/963/1551677736513489.png" title="1551677736513489.png" alt="Introduction détaillée à limplémentation dun algorithme de hachage cohérent en PHP (exemple de code)"></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="Introduction détaillée à limplémentation dun algorithme de hachage cohérent en PHP (exemple de code)"></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="Introduction détaillée à limplémentation dun algorithme de hachage cohérent en PHP (exemple de code)"></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>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!