PHP でのコンシステント ハッシュ アルゴリズムの実装に関する詳細な紹介 (コード例)

この記事では、PHP でのコンシステント ハッシュ アルゴリズムの実装について詳しく紹介 (コード例) しています。一定の参考価値があります。必要な友人は参照してください。お役に立てば幸いです。

1. ケース分析
(1) 問題の概要

画像データが 3 つのサービス (それぞれサーバー A とサーバー A というラベルが付いている) に均等に分散されていると仮定します。 ) B、サーバー C) 上で、そこから画像を取得したいと考えています。このリクエストを取得した後、サーバーは、この画像がサーバー A、サーバー B、またはサーバー C に存在するかどうかをどのように指定できますか?横断する場合、サーバーが 2 つまたは 3 つあれば問題ありませんが、それは多すぎます。サーバーの数が数百、数千に達した場合でも、横断についてあえて話す必要があるでしょうか。

(2) 解決策

a. ストレージ マッピング関係を通じて

まず、記録するための中間層を作成できると考えます。画像ストレージ どのサーバー上にあるかは次のとおりです:

logo1.png =====》 サービス A

ogo2.png =====》 サービス B

logo3.png == ===》サービス C

このように、リクエストが来るたびに、まず画像とサーバー間のマッピング関係をリクエストし、画像が保存されているサーバーを見つけて、次のリクエストを行います。指定されたサーバー。実装の観点からは、これは実現可能ですが、画像を保存する場合、画像とサーバー間のマッピング関係も保存する必要があるため、明らかに作業負荷が増加し、そのメンテナンスも問題になります。サーバー マッピング関係に問題がある場合、システム全体がハングアップします。

b. ハッシュ アルゴリズム

ストレージ マッピング関係を除外したいため、この時点ではハッシュ アルゴリズムが考えられます。たとえば、

# 画像が保存されている場合、画像名 (logo1.png) に基づいてハッシュ アルゴリズムによってハッシュ値 val が取得され、ハッシュ値 val が取得されます。 val. value の剰余を取得することで取得されるので、画像をどのサーバーに保存するかを決定できます。次のように:

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 の余りが取得され、次のようにハッシュ リングにもマッピングされます。

##4. 次に、時計回りに回して、到達した最初のノードが、logo1.png 画像を保存するサーバーであると見なされます。 上記のことからわかるように、実際、コンシステント ハッシュのハイライトは、最初のノード ノード (画像を保存するサーバー) とオブジェクト (画像) の両方のハッシュ計算とマッピングであることです。 )、2 つ目は閉ループ設計です。

利点: 新しいマシンが追加されると、以下に示すように、マークされた領域のみが影響を受けます:

欠点: ノードが比較的少ない場合、ハッシュ計算後、ハッシュ リングにマッピングされたノードが均等に分散されず、一部のマシンの負荷が高くなり、一部のマシンがアイドル状態になるため、バランスが崩れることがよくあります。

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></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 中国語 Web サイトの他の関連記事を参照してください。