Detaillierte Einführung in die Implementierung eines konsistenten Hashing-Algorithmus in PHP (Codebeispiel)

Der Inhalt dieses Artikels ist eine detaillierte Einführung (Codebeispiel) über die Implementierung eines konsistenten Hashing-Algorithmus in PHP. Ich hoffe, dass er für Sie hilfreich ist.

1. Fallanalyse
(1) Problemübersicht

Angenommen, unsere Bilddaten sind gleichmäßig auf drei Dienste verteilt (mit der Bezeichnung Server A bzw. Server A). B, Server C) oben, jetzt möchten wir das Bild davon abrufen. Nachdem wir diese Anfrage erhalten haben, wie kann der Server angeben, ob dieses Bild auf Server A, Server B oder Server C vorhanden ist? Wenn wir durchqueren möchten, sind zwei oder drei Server in Ordnung, aber wenn die Anzahl der Server Hunderte oder Tausende erreicht, wagen wir es dann noch, über Durchqueren zu sprechen?

(2) Lösung

a. Durch Speicherzuordnungsbeziehung

Zunächst denken wir vielleicht, dass wir eine Zwischenschicht zum Aufzeichnen erstellen können Bildspeicherung Auf welchem ​​Server, wie folgt:

logo1.png =====》 Service A

ogo2.png =====》 Service B

logo3 .png =====》Service C

Auf diese Weise fordern wir bei jeder Anfrage zunächst die Zuordnungsbeziehung zwischen dem Bild und dem Server an, suchen den Server, auf dem das Bild gespeichert ist, und erstellen es dann eine Anfrage an den angegebenen Server. Aus Implementierungssicht ist dies machbar, aber beim Speichern von Bildern müssen wir auch die Zuordnungsbeziehung zwischen den Bildern und dem Server speichern, was offensichtlich den Arbeitsaufwand erhöht, und seine Wartung ist auch ein Problem server Wenn es ein Problem mit der Zuordnungsbeziehung gibt, bleibt das gesamte System hängen.

b. Hash-Algorithmus

Da wir die Speicherzuordnungsbeziehung ausschließen möchten, denken die Leute zu diesem Zeitpunkt an den Hash-Algorithmus. Wenn beispielsweise das Bild

gespeichert wird, wird der Hash-Wert durch den Hash-Algorithmus basierend auf dem Bildnamen (logo1.png) berechnet val, wir erhalten den Wert, Sie können bestimmen, auf welchem ​​Server das Bild gespeichert werden soll. Wie folgt:

key = hash(imgName) % n

wobei:

imgName der Name des Bildes ist,

n die Anzahl der Server ist,

key die Anzahl in darstellt welches Bild auf dem Server gespeichert werden soll.

Wenn eine Anfrage eingeht, beispielsweise die Anforderung des Bildes logo1.png, kann der Server anhand des durch die obige Formel berechneten Schlüssels ermitteln, auf welchem ​​Server das logo1.png gespeichert ist. Die PHP-Implementierung lautet wie folgt:

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

Ausgabe:

An diesem Punkt wechseln wir von der Speicherung der Zuordnungsbeziehung zur Berechnung der Seriennummer des Servers , was die Arbeitsmenge tatsächlich erheblich vereinfacht.

Sobald jedoch eine neue Maschine hinzugefügt wird, ist dies sehr problematisch, da sich n ändert und sich auch fast alle Seriennummernschlüssel ändern, sodass viel Datenmigrationsarbeit erforderlich ist.

C. Konsistenter Hash-Algorithmus

Der konsistente Hash-Algorithmus ist ein spezieller Hash-Algorithmus, der das Problem lösen soll, wenn die Anzahl der Knoten (z. B. die Anzahl der Server, die speichern). Bilder) ) Änderungen, versuchen Sie, so wenig Daten wie möglich zu migrieren.

Die Grundidee:

1. Verteilen Sie zunächst die Punkte von 0 bis 2 hoch 32 gleichmäßig auf einem Ring, wie folgt:

2. Berechnen Sie dann alle Knoten (Server, die Bilder speichern) durch Hash-Berechnung, nehmen Sie den Rest von 232 und ordnen Sie ihn dann wie folgt dem Hash-Ring zu:

3. Wenn eine Anfrage eintrifft, zum Beispiel das Bild logo1.png, wird nach der Hash-Berechnung der Rest von 232 genommen und dann auch dem Hash-Ring zugeordnet, wie folgt:

4. Der erste erreichte Knoten gilt als der Server, der das Bild logo1.png speichert.

Wie Sie oben sehen können, ist das Highlight des konsistenten Hashing erstens die Hash-Berechnung und Zuordnung beider Knoten (Server, die Bilder speichern) und Objekte (Bilder) und zweitens das Closed-Loop-Design.

Vorteile: Wenn eine neue Maschine hinzugefügt wird, ist nur der markierte Bereich betroffen, wie unten gezeigt:

Nachteile: Wenn relativ wenige Knoten vorhanden sind. , oft fehlt es an Ausgewogenheit, da nach der Hash-Berechnung die dem Hash-Ring zugeordneten Knoten nicht gleichmäßig verteilt sind, was dazu führt, dass einige Maschinen eine hohe Last haben und einige Maschinen im Leerlauf sind.

PHP-Implementierung ist wie folgt:

$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>Das Ausgabeergebnis ist wie folgt: </p><p><img src="https://img.php.cn/upload/image/534/248/963/1551677736513489.png" title="1551677736513489.png" alt="Detaillierte Einführung in die Implementierung eines konsistenten Hashing-Algorithmus in PHP (Codebeispiel)"></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="Detaillierte Einführung in die Implementierung eines konsistenten Hashing-Algorithmus in PHP (Codebeispiel)"></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="Detaillierte Einführung in die Implementierung eines konsistenten Hashing-Algorithmus in PHP (Codebeispiel)"></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>

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Implementierung eines konsistenten Hashing-Algorithmus in PHP (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!