目錄
- 傳統(tǒng)算法缺陷
- 算法思想
- 算法實(shí)現(xiàn)
- 總結(jié)
傳統(tǒng)算法缺陷
對(duì)于服務(wù)器分布,我們要考慮的東西有如下三點(diǎn):數(shù)據(jù)平均分布,查找定位準(zhǔn)確,降低宕機(jī)影響。
傳統(tǒng)算法一般是將數(shù)據(jù)的鍵用算法映射出數(shù)字,對(duì)其用服務(wù)器數(shù)量取模,并根據(jù)結(jié)果選擇要存儲(chǔ)的服務(wù)器。其能達(dá)到數(shù)據(jù)平均分布和查找定位準(zhǔn)確的要求,并且優(yōu)點(diǎn)是算法簡(jiǎn)單,存取時(shí)的計(jì)算量都比較小(在數(shù)據(jù)非常大時(shí)才會(huì)明顯)。
但其有一個(gè)致命缺點(diǎn),即一個(gè)服務(wù)器宕機(jī)后的影響很大,我們可以推算一下一臺(tái)服務(wù)器宕機(jī)后的影響:
- 原有數(shù)據(jù)大部分丟失:服務(wù)器數(shù)量減少一臺(tái),取模數(shù)減1導(dǎo)致取模值錯(cuò)亂,如果以前有N臺(tái)服務(wù)器,那么宕機(jī)后數(shù)據(jù)只有1/(n*(n-1))的數(shù)據(jù)能夠被準(zhǔn)確查找到。
- 負(fù)載無(wú)法均衡導(dǎo)致集體宕機(jī):如果沒(méi)有及時(shí)處理宕機(jī)的服務(wù)器,那么他的存儲(chǔ)任務(wù)將會(huì)被順序積累給它的下一個(gè)服務(wù)器,那么下一個(gè)服務(wù)器也會(huì)很快被壓致宕機(jī),如此一來(lái),服務(wù)器組很快會(huì)集體宕機(jī)。
算法思想
一致性哈希算法是使用一定的哈希算法,將大量的數(shù)據(jù)平均映射到不同的存儲(chǔ)目標(biāo)上,在保證其查找準(zhǔn)確性的同時(shí),還要考慮其中一個(gè)存儲(chǔ)目標(biāo)失效時(shí),其他存儲(chǔ)目標(biāo)對(duì)其責(zé)任存儲(chǔ)內(nèi)容的負(fù)載均衡。
一致性哈希算法的實(shí)現(xiàn)思想不難理解,如圖:
1.用一定的哈希算法(哈希函數(shù)等)將一組服務(wù)器的多個(gè)(數(shù)目自己設(shè)定)節(jié)點(diǎn)隨機(jī)映射分散到0-232之間,由于其隨機(jī)分布,保證了其數(shù)據(jù)平均分布的特點(diǎn);
2.用同一算法計(jì)算要存儲(chǔ)數(shù)據(jù)的鍵,根據(jù)服務(wù)器節(jié)點(diǎn)確定其存儲(chǔ)的服務(wù)器結(jié)點(diǎn),由于每次用同一算法計(jì)算,所以得出的結(jié)果是相同的,使其查找定位準(zhǔn)確;
3.查找數(shù)據(jù)時(shí),再次用同一算法計(jì)算鍵,并查找服務(wù)器的數(shù)據(jù)結(jié)點(diǎn);
4.如果有一個(gè)服務(wù)器宕機(jī),消除其服務(wù)器結(jié)點(diǎn),并將數(shù)據(jù)放在下一個(gè)結(jié)點(diǎn)上,由于隨機(jī)節(jié)點(diǎn)位置的隨機(jī)性,所以數(shù)據(jù)被其他服務(wù)器平均負(fù)載,也就降低了宕機(jī)影響。
需要注意的是,這個(gè)環(huán)形空間只是一個(gè)虛擬空間,只是表示了服務(wù)器存儲(chǔ)的范圍和數(shù)據(jù)的落點(diǎn),在進(jìn)行存儲(chǔ)時(shí),我們還要通過(guò)查找到的落點(diǎn),將數(shù)據(jù)放入對(duì)應(yīng)的服務(wù)器進(jìn)行查改。
算法實(shí)現(xiàn)
編程語(yǔ)言我們使用PHP來(lái)實(shí)現(xiàn)一致性哈希算法:
我們主要用到以下函數(shù):
int crc32 ( string $str )
生成 str 的 32 位循環(huán)冗余校驗(yàn)碼多項(xiàng)式。這通常用于檢查傳輸?shù)臄?shù)據(jù)是否完整。
string sprintf ( string $format [, mixed $args [, mixed $... ]] )
通過(guò)傳入的格式產(chǎn)生字符串的特定格式形態(tài)。
實(shí)現(xiàn)如下:
class Consistance
{
protected $num=24; //設(shè)定每一個(gè)服務(wù)器的節(jié)點(diǎn)數(shù),數(shù)量越多,宕機(jī)時(shí)服務(wù)器負(fù)載就會(huì)分布得越平均,但也增大數(shù)據(jù)查找消耗。
protected $nodes=array(); //當(dāng)前服務(wù)器組的結(jié)點(diǎn)列表。
//計(jì)算一個(gè)數(shù)據(jù)的哈希值,用以確定位置
public function make_hash($data)
{
return sprintf('%u',crc32($data));
}
//遍歷當(dāng)前服務(wù)器組的節(jié)點(diǎn)列表,確定需要存儲(chǔ)/查找的服務(wù)器
public function set_loc($data)
{
$loc=self::make_hash($data);
foreach ($this->nodes as $key => $val)
{
if($loc=$key)
{
return $val;
}
}
}
//添加一個(gè)服務(wù)器,將其結(jié)點(diǎn)添加到服務(wù)器組的節(jié)點(diǎn)列表內(nèi)。
public function add_host($host)
{
for($i=0;$i$this->num;$i++)
{
$key=sprintf('%u',crc32($host.'_'.$i));
$this->nodes[$key]=$host;
}
ksort($this->nodes); //對(duì)結(jié)點(diǎn)排序,這樣便于查找。
}
//刪除一個(gè)服務(wù)器,并將其對(duì)應(yīng)節(jié)點(diǎn)從服務(wù)器組的節(jié)點(diǎn)列表內(nèi)移除。
public function remove_host($host)
{
for($i=0;$i$this->num;$i++)
{
$key=sprintf('%u',crc32($host.'_'.$i));
unset($this->nodes[$key]);
}
}
}
我們用以下代碼進(jìn)行測(cè)試:
結(jié)果如下:
總結(jié)
算法的實(shí)現(xiàn)到此,我們還可以對(duì)算法進(jìn)行優(yōu)化,如在服務(wù)器數(shù)量和每個(gè)服務(wù)器節(jié)點(diǎn)數(shù)都很多的情況下,對(duì)查找結(jié)點(diǎn)的過(guò)程進(jìn)行優(yōu)化,因?yàn)榕判蚝玫模梢杂枚址ㄟM(jìn)行查找,加快查詢效率,這些,仁智各見(jiàn)吧。
另外,雖然nginx服務(wù)器有一致性算法的插件,memcache和redis也都有相應(yīng)的插件,MySQL的中間件有相應(yīng)的集成,但是了解一致性哈希算法也很有意義。而且,我們也可以對(duì)其靈活使用,如對(duì)文件等進(jìn)行分布式管理等等。
以上就是如何用PHP實(shí)現(xiàn)分布算法之一致性哈希算法的詳細(xì)內(nèi)容,更多關(guān)于用PHP實(shí)現(xiàn)分布算法之一致性哈希算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
您可能感興趣的文章:- PHP實(shí)現(xiàn)的服務(wù)器一致性hash分布算法示例
- PHP哈希表實(shí)現(xiàn)算法原理解析
- PHP實(shí)現(xiàn)的一致性哈希算法完整實(shí)例
- PHP內(nèi)核探索:哈希表碰撞攻擊原理
- PHP中創(chuàng)建和驗(yàn)證哈希的簡(jiǎn)單方法實(shí)探
- php內(nèi)核解析:PHP中的哈希表
- php-perl哈希算法實(shí)現(xiàn)(times33哈希算法)
- PHP 5.5 創(chuàng)建和驗(yàn)證哈希最簡(jiǎn)單的方法詳解
- 一致性哈希算法以及其PHP實(shí)現(xiàn)詳細(xì)解析