本文實例講述了PHP實現(xiàn)的一致性Hash算法。分享給大家供大家參考,具體如下:
一致性哈希算法是分布式系統(tǒng)中常用的算法,為什么要用這個算法?
比如:一個分布式存儲系統(tǒng),要將數(shù)據(jù)存儲到具體的節(jié)點(服務(wù)器)上, 在服務(wù)器數(shù)量不發(fā)生改變的情況下,如果采用普通的hash再對服務(wù)器總數(shù)量取模的方法(如key%服務(wù)器總數(shù)量),如果期間有服務(wù)器宕機(jī)了或者需要增加服務(wù)器,問題就出來了。 同一個key經(jīng)過hash之后,再與服務(wù)器總數(shù)量取模的結(jié)果跟之前的結(jié)果會不一樣,這就導(dǎo)致了之前保存數(shù)據(jù)的丟失。因此,引入了一致性Hash(Consistent Hashing)分布算法
把數(shù)據(jù)用hash函數(shù)(如md5,sha1),映射到一個圓環(huán)上,如上圖所示,數(shù)據(jù)在存儲時,先根據(jù)hash算法算出key的hash值,對應(yīng)到這個環(huán)中的位置,如k1對應(yīng)圖中所示的位置同,然后沿著順時針方向找到服務(wù)器節(jié)點B,然后把k1在存到B這個節(jié)點中。
如果B節(jié)點宕機(jī)了,則B上的數(shù)據(jù)就會落到C節(jié)點上,如下圖所示
這樣,只會影響C節(jié)點,對于其他節(jié)點A、D的數(shù)據(jù)不會造成影響。但是問題來了,這樣會造成C節(jié)點負(fù)載過重的情況,因為C節(jié)點承擔(dān)了B節(jié)點的數(shù)據(jù),所以C節(jié)點容易宕機(jī),這樣造成了分布不均勻。
為了解決這個問題,引入了“虛擬節(jié)點“的概念:即想象空上環(huán)上有很多”虛擬節(jié)點“,一個真實的服務(wù)器節(jié)點對應(yīng)多個虛擬節(jié)點,數(shù)據(jù)存儲的時候沿著環(huán)的順時針方向找到虛擬節(jié)點,就找到了對應(yīng)的真實服務(wù)器節(jié)點。如下圖
圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點,機(jī)器A負(fù)載存儲A1、A2的數(shù)據(jù),機(jī)器B負(fù)載存儲B1、B2的數(shù)據(jù),機(jī)器C負(fù)載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點數(shù)量很多,均勻分布,因此不會造成“雪崩”現(xiàn)象。
一致性哈希算法的PHP實現(xiàn)
下面給出一個接口
/**
* 一致性哈希實現(xiàn)接口
* Interface ConsistentHash
*/
interface ConsistentHash
{
//將字符串轉(zhuǎn)為hash值
public function cHash($str);
//添加一臺服務(wù)器到服務(wù)器列表中
public function addServer($server);
//從服務(wù)器刪除一臺服務(wù)器
public function removeServer($server);
//在當(dāng)前的服務(wù)器列表中找到合適的服務(wù)器存放數(shù)據(jù)
public function lookup($key);
}
這個接口分別定義了4個方法,cHash(將字符串處理為hash值)、addServer(增加一臺服務(wù)器)、removeServer(移除一臺服務(wù)器)、lookup(找到一臺服務(wù)器來存儲數(shù)據(jù))
下面給出一個該接口的具體實現(xiàn)
/**
* 具體一致性哈希實現(xiàn)
* author chenqionghe
* Class MyConsistentHash
*/
class MyConsistentHash implements ConsistentHash
{
public $serverList = array(); //服務(wù)器列列表
public $virtualPos = array(); //虛擬節(jié)點的位置
public $virtualPosNum = 5; //每個節(jié)點對應(yīng)5個虛節(jié)點
/**
* 將字符串轉(zhuǎn)換成32位無符號整數(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);//落點的hash值
$finalServer = current($this->virtualPos);//先取圓環(huán)上最小的一個節(jié)點當(dāng)成結(jié)果
foreach($this->virtualPos as $pos=>$server)
{
if($point = $pos)
{
$finalServer = $server;
break;
}
}
reset($this->virtualPos);//重置圓環(huán)的指針為第一個
return $finalServer;
}
/**
* 添加一臺服務(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;
}
/**
* 移除一臺服務(wù)器(循環(huán)所有的虛節(jié)點,刪除值為該服務(wù)器地址的虛節(jié)點)
* @param $key
* @return bool
*/
public function removeServer($key)
{
if(isset($this->serverList[$key]))
{
//刪除對應(yīng)虛節(jié)點
foreach($this->serverList[$key] as $pos)
{
unset($this->virtualPos[$pos]);
}
//刪除對應(yīng)服務(wù)器
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 "增加十臺服務(wù)器192.168.1.1~192.168.1.10br />";
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 "移除一臺服務(wù)器192.168.1.2br />";
$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 "移除一臺服務(wù)器192.168.1.6br />";
$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 "移除一臺服務(wù)器192.168.1.8br />";
$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 "移除一臺服務(wù)器192.168.1.2br />";
$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 "增加一臺服務(wù)器192.168.1.11br />";
$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 />';
運行結(jié)果如下
增加十臺服務(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
移除一臺服務(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
移除一臺服務(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
移除一臺服務(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
移除一臺服務(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
增加一臺服務(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
可以,看到,使用一致性哈希后,無認(rèn)是增加服務(wù)器還是減少服務(wù)器都最大程度的保證了數(shù)據(jù)的完整性、均勻性.
PS:這里再為大家提供2款hash相關(guān)在線工具供大家參考使用:
在線散列/哈希算法加密工具:
http://tools.jb51.net/password/hash_encrypt
在線MD5/hash/SHA-1/SHA-2/SHA-256/SHA-512/SHA-3/RIPEMD-160加密工具:
http://tools.jb51.net/password/hash_md5_sha
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《php加密方法總結(jié)》、《PHP編碼與轉(zhuǎn)碼操作技巧匯總》、《PHP數(shù)學(xué)運算技巧總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《php字符串(string)用法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》及《php正則表達(dá)式用法總結(jié)》
希望本文所述對大家PHP程序設(shè)計有所幫助。
您可能感興趣的文章:- Nginx 安裝筆記(含PHP支持、虛擬主機(jī)、反向代理負(fù)載均衡)
- PHP開發(fā)負(fù)載均衡指南
- PHP實現(xiàn)負(fù)載均衡下的session共用功能
- PHP實現(xiàn)負(fù)載均衡session共享redis緩存操作示例
- Thinkphp結(jié)合AJAX長輪詢實現(xiàn)PC與APP推送詳解
- PHP經(jīng)典算法集錦【經(jīng)典收藏】
- php 分庫分表hash算法
- php的hash算法介紹
- PHP中對各種加密算法、Hash算法的速度測試對比代碼
- PHP實現(xiàn)負(fù)載均衡的加權(quán)輪詢方法分析