PHP で一貫性のあるハッシュ アルゴリズムを実装する手順の詳細な説明

今回は、PHP で一貫性のあるハッシュ アルゴリズムを実装する手順について詳しく説明します。PHP で一貫性のあるハッシュ アルゴリズムを実装するための 注意事項 は何ですか?実際のケースを見てみましょう。

整合性ハッシュ アルゴリズムは、分散システムで一般的に使用されるアルゴリズムです。なぜこのアルゴリズムを使用する必要があるのでしょうか? 例: 分散ストレージ システムは、サーバーの数が変わらない場合、通常のハッシュ方式を使用してサーバーの総数を剰余化する場合 (key% など)、データを特定のノード (サーバー) に保存する必要があります。サーバーの総数）、期間中にサーバーがダウンした場合、またはサーバーを追加する必要がある場合、問題が発生します。 同じキーをハッシュした後、サーバーの合計数を法とした結果は以前の結果とは異なるため、以前に保存したデータが失われます。そこで、Consistent Hash (Consistent Hashing) 分散アルゴリズムが導入されます

データを格納する際には、上図のようにハッシュ関数(md5、sha1など)を使ってリングにマッピングされます。最初にハッシュに従って格納されます。アルゴリズムはキーのハッシュ値を計算し、リング内の位置に対応します。たとえば、k1 の位置は対応する図に示されているとおりです。次に、サーバー ノード B を見つけます。時計回りにk1をノードBに格納します。

ノード B がダウンした場合、以下の図に示すように、B 上のデータはノード C に落ちます

このように、影響を受けるのはノード C のみであり、ノード C のデータには損傷は生じません。他のノード A と D。影響。しかし、ここで問題が発生します。これにより、C ノードが過負荷になり、C ノードがダウンタイムを起こしやすくなり、分散が不均一になります。

この問題を解決するために、「仮想ノード」の概念が導入されます。つまり、空のリング上に多数の「仮想ノード」があり、複数の仮想ノードに対応するデータが存在します。リングに沿って時計回りに格納され、その方向に仮想ノードが見つかると、対応する実サーバー ノードが見つかります。以下の図に示すように

図では、A1、A2、B1、B2、C1、C2、D1、D2はすべて仮想ノードであり、マシンAはA1とA2のデータをロードし、マシンBはデータをロードします。マシン C は、B1 と B2 のデータをロードして保存します。これらの仮想ノードの数は多く、均等に分散されているため、「雪崩」現象は発生しません。

一貫性のあるハッシュアルゴリズムのPHP実装

インターフェースは以下に示されています

/**
 * 一致性哈希实现接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
 //将字符串转为hash值
 public function cHash($str);
 //添加一台服务器到服务器列表中
 public function addServer($server);
 //从服务器删除一台服务器
 public function removeServer($server);
 //在当前的服务器列表中找到合适的服务器存放数据
 public function lookup($key);
}

このインターフェースは、cHash (文字列をハッシュ値に処理する)、addServer (サーバーを追加する)、removeServer (サーバーを削除する)の4つのメソッドをそれぞれ定義します。サーバー)、ルックアップ (データを保存するサーバーを見つける)

以下はこのインターフェースの具体的な実装です

/**
 * 具体一致性哈希实现
 * author chenqionghe
 * Class MyConsistentHash
 */
class MyConsistentHash implements ConsistentHash
{
 public $serverList = array(); //服务器列列表
 public $virtualPos = array(); //虚拟节点的位置
 public $virtualPosNum = 5;  //每个节点对应5个虚节点
 /**
  * 将字符串转换成32位无符号整数hash值
  * @param $str
  * @return int
  */
 public function cHash($str)
 {
  $str = md5($str);
  return sprintf('%u', crc32($str));
 }
 /**
  * 在当前的服务器列表中找到合适的服务器存放数据
  * @param $key 键名
  * @return mixed 返回服务器IP地址
  */
 public function lookup($key)
 {
  $point = $this->cHash($key);//落点的hash值
  $finalServer = current($this->virtualPos);//先取圆环上最小的一个节点当成结果
  foreach($this->virtualPos as $pos=>$server)
  {
   if($point <= $pos)
   {
    $finalServer = $server;
    break;
   }
  }
  reset($this->virtualPos);//重置圆环的指针为第一个
  return $finalServer;
 }
 /**
  * 添加一台服务器到服务器列表中
  * @param $server 服务器IP地址
  * @return bool
  */
 public function addServer($server)
 {
  if(!isset($this->serverList[$server]))
  {
   for($i=0; $i<$this->virtualPosNum; $i++)
   {
    $pos = $this->cHash($server . '-' . $i);
    $this->virtualPos[$pos] = $server;
    $this->serverList[$server][] = $pos;
   }
   ksort($this->virtualPos,SORT_NUMERIC);
  }
  return TRUE;
 }
 /**
  * 移除一台服务器（循环所有的虚节点，删除值为该服务器地址的虚节点）
  * @param $key
  * @return bool
  */
 public function removeServer($key)
 {
  if(isset($this->serverList[$key]))
  {
   //删除对应虚节点
   foreach($this->serverList[$key] as $pos)
   {
    unset($this->virtualPos[$pos]);
   }
   //删除对应服务器
   unset($this->serverList[$key]);
  }
  return TRUE;
 }
}

それではアルゴリズムをテストしてみましょう

$hashServer = new MyConsistentHash();
$hashServer->addServer('192.168.1.1');
$hashServer->addServer('192.168.1.2');
$hashServer->addServer('192.168.1.3');
$hashServer->addServer('192.168.1.4');
$hashServer->addServer('192.168.1.5');
$hashServer->addServer('192.168.1.6');
$hashServer->addServer('192.168.1.7');
$hashServer->addServer('192.168.1.8');
$hashServer->addServer('192.168.1.9');
$hashServer->addServer('192.168.1.10');
echo "增加十台服务器192.168.1.1~192.168.1.10<br />";
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.6<br />";
$hashServer->removeServer('192.168.1.6');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.8<br />";
$hashServer->removeServer('192.168.1.8');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一台服务器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "增加一台服务器192.168.1.11<br />";
$hashServer->addServer('192.168.1.11');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';

実行結果は以下の通りです

10 台のサーバー 192.168.1.1~192.168.1.10 を追加します
key1 をサーバー:192.168.1.2 に保存します
key2 をサーバー:192.168.1.1 に保存します
key3 をサーバー:192.168.1.6 に保存します
key4 をサーバー:192.168.1 に保存します.8
key5 をサーバー:192.168.1.9 に保存
key6 をサーバー:192.168.1.10 に保存
key7 をサーバー:192.168.1.7 に保存
key8 をサーバー:192.168.1.4 に保存
key9 をサーバー:192.168.1.7 に保存
key10 をサーバーに保存: 192.168.1.4 1 サーバー 192.168.1.2 を削除します
key1 をサーバー: 192.168.1.7 に保存します
key2 をサーバー: 192.168.1.1 に保存します
Key3 をサーバー: 192.168.1.6 に保存します
KEY4 をサーバー: 192.168.1.8 に保存します

保存key5をサーバー:192.168.1.9に保存
key6をサーバー:192.168.1.10に保存
key7をサーバー:192.168.1.7に保存
key8をサーバー:192.168.1.4に保存
key9をサーバー:192.168.1.7に保存
key10をサーバー:192.1に保存68 .1.4
サーバー192.168.1.6を削除
key1をサーバー:192.168.1.7に保存
key2をサーバー:192.168.1.1に保存
key3をサーバー:192.168.1.3に保存
key4をサーバー:192.168.1.8に保存key5へサーバー:192.168.1.9
key6 をサーバー:192.168.1.10 に保存
key7 をサーバー:192.168.1.7 に保存
key8 をサーバー:192.168.1.4 に保存
key9 をサーバー:192.168.1.7 に保存
key10 をサーバー:192.168 に保存します。 1.4
サーバー 192.168.1.8 を削除します
key1 をサーバー:192.168.1.7 に保存します
key2 をサーバー:192.168.1.1 に保存します
key3 をサーバー:192.168.1.3 に保存します
key4 をサーバー:192.168.1.10 に保存します
key5 をサーバー:1 に保存します92.168 .1.9
SaveKey6へのサーバーへ：192.168.1.10
SaveKey7からサーバーへ：192.168.1.7
サーバーへのSave Key8へ：192.168.1.4
サーバーへ：192.168.1.7
Saveキー10からサーバー：192.168.1 .4.4サーバー 192.168.1.2 を削除します
key1 をサーバー:192.168.1.7 に保存します
key2 をサーバー:192.168.1.1 に保存します
key3 をサーバー:192.168.1.3 に保存します
key4 をサーバー:192.168.1.10 に保存します
key5 をサーバー:192.168 に保存します。 1.9
key6をサーバー:192.168.1.10に保存
key7をサーバー:192.168.1.7に保存
key8をサーバー:192.168.1.4に保存
key9をサーバー:192.168.1.7に保存
key10をサーバー:192.168.1に保存します。サーバー 192.168.1.11
key1 をサーバー:192.168.1.7 に保存
key2 をサーバー:192.168.1.1 に保存
key3 をサーバー:192.168.1.11 に保存
key5 をサーバー:192.16 に保存８． 1.9
key6をサーバー:192.168.1.10に保存
key7をサーバー:192.168.1.7に保存
key8をサーバー:192.168.1.4に保存
key9をサーバー:192.168.1.7に保存
key10をサーバー:192.168.1.4に保存


はい一貫したハッシュを使用すると、サーバーを追加するか削減するかに関係なく、データの整合性と均一性が最大限に保証されることがわかります。

この記事の事例を読んだ後は、この方法を習得したと思います。 、そしてさらにエキサイティングなものがあるでしょう、php中国語ウェブサイトの他の関連記事にも注目してください。

推奨読書:

thinkPHP フレームワーク自動入力の原理と使用法の詳細な説明

PHP デコレーター モードの使用の詳細な説明

以上がPHP で一貫性のあるハッシュ アルゴリズムを実装する手順の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。