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

這次帶給大家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

17.1-16811212168.110

17.server1681211212119.1212121.10

17.1-1681121212119.10

17.1-1681121212121.10

17。 #儲存key8 到server :192.168.1.4

儲存key9 到server :192.168.1.7

儲存key10 到server :192.168.1.4

可以，看到，使用一致性哈希後，無認是增加伺服器還是減少伺服器都最大程度的保證了資料的完整性、均勻性.

相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！ 推薦閱讀：

######thinkPHP框架自動填入原理與用法使用詳解############PHP裝飾器模式使用詳解###### #

以上是PHP實作一致性Hash演算法步驟詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！