memcached分布式-一致性哈希

2019-11-11 04:10:55

字體：大中小

供稿：網(wǎng)友

一致性哈希分布式算法

概述

一致性哈希提出了在動(dòng)態(tài)變化的Cache環(huán)境中，哈希算法應(yīng)該滿足的4個(gè)適應(yīng)條件：均衡性：盡可能分布到所有的緩沖中，使得所有的空間得到利用；單調(diào)性：新增緩沖時(shí)候，能分配到新的緩沖區(qū)。分散性：盡量避免不一致情況發(fā)生，降低分散性。負(fù)載：能最好均勻分布到各個(gè)緩沖區(qū)。同時(shí)清晰路由到某個(gè)節(jié)點(diǎn)。

分析

當(dāng)n個(gè)memcached服務(wù)器中1臺(tái)down掉了，也就是變成了n-1臺(tái)。1/（n-1）:將down掉了那一臺(tái)服務(wù)器負(fù)載平均分配到其余的服務(wù)器上。

場景分析

引入虛擬節(jié)點(diǎn)，如3臺(tái)服務(wù)器a，b，ca1,a2.....a64個(gè)節(jié)點(diǎn)。b1,b2....b64個(gè)節(jié)點(diǎn)。c1,c2...c64個(gè)節(jié)點(diǎn)，混合均勻排序；（條件：假設(shè)前一個(gè)節(jié)點(diǎn)掛掉會(huì)找相鄰的節(jié)點(diǎn)進(jìn)行存儲(chǔ)。）keyx在服務(wù)器b1，keyy在服務(wù)器b2,keyz在服務(wù)器節(jié)點(diǎn)b64；假設(shè)b服務(wù)器down掉，則keyx在a服務(wù)器，keyy在b服務(wù)器，keyz在a服務(wù)器（相鄰節(jié)點(diǎn)）虛擬出虛擬越多的虛擬節(jié)點(diǎn)這樣就能使得所有的緩存key均勻分布并且當(dāng)一臺(tái)掛掉會(huì)找相鄰的節(jié)點(diǎn)；這樣概率角度能達(dá)到均勻的負(fù)載到其他服務(wù)器上去。

php實(shí)現(xiàn)

需要一個(gè)函數(shù)把字符串轉(zhuǎn)成整數(shù)的函數(shù)crc32

簡單示例

<?phpclass Consistent { PRotected $nodes = array(); protected $virtual = 64;//表示每臺(tái)服務(wù)器有64個(gè)虛擬節(jié)點(diǎn) protected $position = array();//虛擬節(jié)點(diǎn) /** *@function 實(shí)現(xiàn)hash，將字符串轉(zhuǎn)成響應(yīng)整數(shù) */ public function _hash($str) { //把字符串轉(zhuǎn)成32位無符號(hào)整數(shù) return sprintf('%u', crc32($str)); } /** *@function 根據(jù)key 值來查找到相關(guān)的存儲(chǔ)節(jié)點(diǎn) * */ public function lookup($key) { //算出key值 $point = $this->_hash($key); //沿著節(jié)點(diǎn)進(jìn)行判斷該key值應(yīng)該存儲(chǔ)哪個(gè)節(jié)點(diǎn) $node = current($this->nodes); foreach($this->position as $key => $val) { if($point <= $key) { $node = $val; break; } } return $node;//返回node節(jié)點(diǎn)所處的服務(wù)器； } /** *@function 添加一個(gè)服務(wù)器需要新增64個(gè)虛擬節(jié)點(diǎn) */ public function addNode($node) { //虛擬出64個(gè)節(jié)點(diǎn)。 for($i = 0; $i < $this->virtual; $i++) { $num = $node .'-'.$i; $this->position[$this->_hash($num)] = $node;//新增64個(gè)位置 } $this->nodes[] = $node; //對(duì)新增節(jié)點(diǎn)進(jìn)行排序，整個(gè)節(jié)點(diǎn)進(jìn)行排序 $this->nodeSort(); } /** *@function 刪除一個(gè)服務(wù)器節(jié)點(diǎn) * */ public function delNode($node) { //循環(huán)所有的虛擬節(jié)點(diǎn)位置 foreach($this->position as $key => $val) { if($val == $node) { unset($this->position[$key]); } } } /** *@function 排序大小 * */ public function nodeSort() { ksort($this->position, SORT_REGULAR); } /** *@function 獲取所有的節(jié)點(diǎn) * */ public function getNodes() { return $this->nodes; } /** *@function 返回所有的虛擬節(jié)點(diǎn) * */ public function getVirtual() { return $this->position; }}$con = new Consistent();$con->addNode('a');//a服務(wù)器$con->addNode('b');//b服務(wù)器$con->addNode('c');//c服務(wù)器print_r($con->getVirtual());$name = 'linjunbin';$tital = 'title4';echo $name.'數(shù)字為'.$con->_hash($name).'落在'.$con->lookup($name);echo '<br>';echo $tital.'數(shù)字為'.$con->_hash($tital).'落在'.$con->lookup($tital);

未完待續(xù)….

上一篇：C# MVC后臺(tái)將PartialView文件輸出為字符串

下一篇：xgboost介紹