PHP實作一致性Hash演算法步驟詳解-php教程-PHP中文網

首頁

後端開發

php教程

PHP實作一致性Hash演算法步驟詳解

php中世界最好的语言

May 17, 2018 am 11:55 AM

hash php 一致性

這次帶給大家PHP實作一致性Hash演算法步驟詳解，PHP實作一致性Hash演算法的注意事項有哪些，以下就是實戰案例，一起來看一下。

一致性雜湊演算法是分散式系統中常用的算法，為什麼要用這個演算法？

例如：一個分散式儲存系統，要將資料儲存到具體的節點（伺服器）上，在伺服器數量不改變的情況下，如果採用普通的hash再對伺服器總數量取模的方法（如key%伺服器總數量），如果期間有伺服器宕機了或需要增加伺服器，問題就出來了。同一個key經過hash之後，再與伺服器總數量取模的結果跟之前的結果會不一樣，這就導致了先前保存資料的遺失。因此，引入了一致性Hash（Consistent Hashing）分佈演算法

把資料用hash函數（如md5，sha1)，映射到一個圓環上，如上圖所示，資料在儲存時，先根據hash演算法算出key的hash值，對應到這個環中的位置，如k1對應圖中所示的位置同，然後沿著順時針方向找到伺服器節點B，然後把k1在存到B這個節點中。

如果B節點宕機了，則B上的資料就會落到C節點上，如下圖所示

##這樣，只會影響C節點，對於其他節點A、D的資料不會造成影響。但是問題來了，這樣會造成C節點負載過重的情況，因為C節點承擔了B節點的數據，所以C節點容易宕機，這樣造成了分佈不均勻。

為了解決這個問題，引入了「虛擬節點「的概念：即想像空上環上有很多」虛擬節點“，一個真實的伺服器節點對應多個虛擬節點，資料儲存的時候沿著環的順時針方向找到虛擬節點，就找到了對應的真實伺服器節點。如下圖

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載儲存A1、A2的數據，機器B負載儲存B1、B2的數據，機器C負載儲存C1、C2的數據。由於這些虛擬節點數量很多，均勻分佈，因此不會造成「雪崩」現象。

一致性雜湊演算法的PHP實作

下面給一個介面

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

登入後複製

這個介面分別定義了4個方法，cHash（將字串處理為hash值）、addServer（增加一台伺服器）、removeServer（移除一台伺服器）、lookup（找到一台伺服器來儲存資料）

下面給出一個該介面的具體實作

/**
 * 具体一致性哈希实现
 * 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 />';

登入後複製

運行結果如下

增加十台伺服器192.168.1.1~192.168.1.10
儲存key1 到server :192.168.1.2
儲存key2 到server :192.168.1.1
儲存key3 到server :191668.192662.
儲存key4 到server :192.168.1.8
儲存key5 到server :192.168.1.9
儲存key6 到server :192.168.1.10
已經儲存到#key7 到server :192.168.1.7 儲存到被儲存到#key server :192.168.1.4
儲存key9 到server :192.168.1.7
儲存key10 到server :192.168.1.4
移除一台伺服器192.168.1.2
儲存key1 到server :1922168.192#key1 到server17. ##儲存key3 到server :192.168.1.1
儲存key3 到server :192.168.1.6
儲存key4 到server :192.168.1.8
儲存key5 到server :192.168.169.1.8
儲存key5 到server :192.168.11.server# :192.168.1.10
儲存key7 到server :192.168.1.7
儲存key8 到server :192.168.1.4
儲存key9 到server :192.168.1.7
##key10 到server :192.168.1.7
##192.server 儲存:1186:

186:186:##21. #移除一台伺服器192.168.1.6
儲存key1 到server :192.168.1.7
儲存key2 到server :192.168.1.1
儲存key3 到server :192.168.1.3
##key4 到 server: 192.168.1.8
保存key5 到server :192.168.1.9
保存key6 到server :192.168.1.10
保存key7 到server :192.168.1.7
保存key8 到server :1server :192.168.1.7
存檔儲存key9 到server :192.168.1.7
儲存key10 到server :192.168.1.4
移除一台伺服器192.168.1.8
儲存key1 到server :192.168.1.7
key2 到儲存key1 到server :192.168.1.7
key12 到server:68 .1.1
保存key3 到server :192.168.1.3
保存key4 到server :192.168.1.10
保存key5 到server :192.168.1.9
保存key6 到server :192.168.1. key7 到server :192.168.1.7
儲存key8 到server :192.168.1.4
儲存key9 到server :192.168.1.7
儲存key10 到server :192.168.168.1.7
儲存key10 到server :192.168.1.4#1686868.1.4#16868.1.4#168. 1.2
儲存key1 到server :192.168.1.7
儲存key2 到server :192.168.1.1
儲存key3 到server :192.168.1.3
儲存key4 儲存到server :192.168.168.1.3
儲存key4 到server :192.168.1.101151511592.168.1.到server :192.168.1.9
保存key6 到server :192.168.1.10
保存key7 到server :192.168.1.7
保存key8 到server :192.168.1.4
key9 到儲存key8 到server :192.168.1.4
19 到儲存key8 到server :192.168.1.4
19 到儲存key8
儲存key10 到server :192.168.1.4
增加一台伺服器192.168.1.11
儲存key1 到server :192.168.1.7
儲存key2 到server :192.168.1.1
key3 儲存到:192.168.1.11
儲存key4 到server :192.168.1.10
儲存key5 到server :192.168.1.9
儲存key6 到server :192.168.1.10
key17 到 168.192.168.1.10
key17 到#1812112168.110