快捷導(dǎo)航

PHP實(shí)現(xiàn)的一致性Hash算法詳解【分布式算法】

更新時(shí)間：2018年03月31日 15:07:50 作者：雪山飛豬

這篇文章主要介紹了PHP實(shí)現(xiàn)的一致性Hash算法,結(jié)合實(shí)例形式詳細(xì)分析了php一致性Hash算法的概念、原理及相關(guān)實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下

本文實(shí)例講述了PHP實(shí)現(xiàn)的一致性Hash算法。分享給大家供大家參考，具體如下：

一致性哈希算法是分布式系統(tǒng)中常用的算法，為什么要用這個(gè)算法？

比如：一個(gè)分布式存儲(chǔ)系統(tǒng)，要將數(shù)據(jù)存儲(chǔ)到具體的節(jié)點(diǎn)（服務(wù)器）上，在服務(wù)器數(shù)量不發(fā)生改變的情況下，如果采用普通的hash再對(duì)服務(wù)器總數(shù)量取模的方法（如key%服務(wù)器總數(shù)量），如果期間有服務(wù)器宕機(jī)了或者需要增加服務(wù)器，問(wèn)題就出來(lái)了。同一個(gè)key經(jīng)過(guò)hash之后，再與服務(wù)器總數(shù)量取模的結(jié)果跟之前的結(jié)果會(huì)不一樣，這就導(dǎo)致了之前保存數(shù)據(jù)的丟失。因此，引入了一致性Hash（Consistent Hashing）分布算法

把數(shù)據(jù)用hash函數(shù)（如md5，sha1)，映射到一個(gè)圓環(huán)上，如上圖所示，數(shù)據(jù)在存儲(chǔ)時(shí)，先根據(jù)hash算法算出key的hash值，對(duì)應(yīng)到這個(gè)環(huán)中的位置，如k1對(duì)應(yīng)圖中所示的位置同，然后沿著順時(shí)針?lè)较蛘业椒?wù)器節(jié)點(diǎn)B，然后把k1在存到B這個(gè)節(jié)點(diǎn)中。

如果B節(jié)點(diǎn)宕機(jī)了，則B上的數(shù)據(jù)就會(huì)落到C節(jié)點(diǎn)上，如下圖所示

這樣，只會(huì)影響C節(jié)點(diǎn)，對(duì)于其他節(jié)點(diǎn)A、D的數(shù)據(jù)不會(huì)造成影響。但是問(wèn)題來(lái)了，這樣會(huì)造成C節(jié)點(diǎn)負(fù)載過(guò)重的情況，因?yàn)镃節(jié)點(diǎn)承擔(dān)了B節(jié)點(diǎn)的數(shù)據(jù)，所以C節(jié)點(diǎn)容易宕機(jī)，這樣造成了分布不均勻。

為了解決這個(gè)問(wèn)題，引入了“虛擬節(jié)點(diǎn)“的概念：即想象空上環(huán)上有很多”虛擬節(jié)點(diǎn)“，一個(gè)真實(shí)的服務(wù)器節(jié)點(diǎn)對(duì)應(yīng)多個(gè)虛擬節(jié)點(diǎn)，數(shù)據(jù)存儲(chǔ)的時(shí)候沿著環(huán)的順時(shí)針?lè)较蛘业教摂M節(jié)點(diǎn)，就找到了對(duì)應(yīng)的真實(shí)服務(wù)器節(jié)點(diǎn)。如下圖

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點(diǎn)，機(jī)器A負(fù)載存儲(chǔ)A1、A2的數(shù)據(jù)，機(jī)器B負(fù)載存儲(chǔ)B1、B2的數(shù)據(jù)，機(jī)器C負(fù)載存儲(chǔ)C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點(diǎn)數(shù)量很多，均勻分布，因此不會(huì)造成“雪崩”現(xiàn)象。

一致性哈希算法的PHP實(shí)現(xiàn)

下面給出一個(gè)接口

/**
 * 一致性哈希實(shí)現(xiàn)接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
 //將字符串轉(zhuǎn)為hash值
 public function cHash($str);
 //添加一臺(tái)服務(wù)器到服務(wù)器列表中
 public function addServer($server);
 //從服務(wù)器刪除一臺(tái)服務(wù)器
 public function removeServer($server);
 //在當(dāng)前的服務(wù)器列表中找到合適的服務(wù)器存放數(shù)據(jù)
 public function lookup($key);
}

這個(gè)接口分別定義了4個(gè)方法，cHash（將字符串處理為hash值）、addServer（增加一臺(tái)服務(wù)器）、removeServer（移除一臺(tái)服務(wù)器）、lookup（找到一臺(tái)服務(wù)器來(lái)存儲(chǔ)數(shù)據(jù)）

下面給出一個(gè)該接口的具體實(shí)現(xiàn)

/**
 * 具體一致性哈希實(shí)現(xiàn)
 * author chenqionghe
 * Class MyConsistentHash
 */
class MyConsistentHash implements ConsistentHash
{
 public $serverList = array(); //服務(wù)器列列表
 public $virtualPos = array(); //虛擬節(jié)點(diǎn)的位置
 public $virtualPosNum = 5;  //每個(gè)節(jié)點(diǎn)對(duì)應(yīng)5個(gè)虛節(jié)點(diǎn)
 /**
  * 將字符串轉(zhuǎn)換成32位無(wú)符號(hào)整數(shù)hash值
  * @param $str
  * @return int
  */
 public function cHash($str)
 {
  $str = md5($str);
  return sprintf('%u', crc32($str));
 }
 /**
  * 在當(dāng)前的服務(wù)器列表中找到合適的服務(wù)器存放數(shù)據(jù)
  * @param $key 鍵名
  * @return mixed 返回服務(wù)器IP地址
  */
 public function lookup($key)
 {
  $point = $this->cHash($key);//落點(diǎn)的hash值
  $finalServer = current($this->virtualPos);//先取圓環(huán)上最小的一個(gè)節(jié)點(diǎn)當(dāng)成結(jié)果
  foreach($this->virtualPos as $pos=>$server)
  {
   if($point <= $pos)
   {
    $finalServer = $server;
    break;
   }
  }
  reset($this->virtualPos);//重置圓環(huán)的指針為第一個(gè)
  return $finalServer;
 }
 /**
  * 添加一臺(tái)服務(wù)器到服務(wù)器列表中
  * @param $server 服務(wù)器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;
 }
 /**
  * 移除一臺(tái)服務(wù)器（循環(huán)所有的虛節(jié)點(diǎn)，刪除值為該服務(wù)器地址的虛節(jié)點(diǎn)）
  * @param $key
  * @return bool
  */
 public function removeServer($key)
 {
  if(isset($this->serverList[$key]))
  {
   //刪除對(duì)應(yīng)虛節(jié)點(diǎn)
   foreach($this->serverList[$key] as $pos)
   {
    unset($this->virtualPos[$pos]);
   }
   //刪除對(duì)應(yīng)服務(wù)器
   unset($this->serverList[$key]);
  }
  return TRUE;
 }
}

然后，我們來(lái)測(cè)試一下該算法

$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 "增加十臺(tái)服務(wù)器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 "移除一臺(tái)服務(wù)器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 "移除一臺(tái)服務(wù)器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 "移除一臺(tái)服務(wù)器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 "移除一臺(tái)服務(wù)器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 "增加一臺(tái)服務(wù)器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 />';

運(yùn)行結(jié)果如下

增加十臺(tái)服務(wù)器192.168.1.1~192.168.1.10
保存 key1 到 server :192.168.1.2
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 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 :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺(tái)服務(wù)器192.168.1.2
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 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 :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺(tái)服務(wù)器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 :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺(tái)服務(wù)器192.168.1.8
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.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.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺(tái)服務(wù)器192.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.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 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.4
增加一臺(tái)服務(wù)器192.168.1.11
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.11
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 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.4