memcached分布式-一致性哈希

2019-11-11 04:11:52

字體：大中小

來源：轉載

供稿：網友

一致性哈希分布式算法

概述

一致性哈希提出了在動態變化的Cache環境中，哈希算法應該滿足的4個適應條件：均衡性：盡可能分布到所有的緩沖中，使得所有的空間得到利用；單調性：新增緩沖時候，能分配到新的緩沖區。分散性：盡量避免不一致情況發生，降低分散性。負載：能最好均勻分布到各個緩沖區。同時清晰路由到某個節點。

分析

當n個memcached服務器中1臺down掉了，也就是變成了n-1臺。1/（n-1）:將down掉了那一臺服務器負載平均分配到其余的服務器上。

場景分析

引入虛擬節點，如3臺服務器a，b，ca1,a2.....a64個節點。b1,b2....b64個節點。c1,c2...c64個節點，混合均勻排序；（條件：假設前一個節點掛掉會找相鄰的節點進行存儲。）keyx在服務器b1，keyy在服務器b2,keyz在服務器節點b64；假設b服務器down掉，則keyx在a服務器，keyy在b服務器，keyz在a服務器（相鄰節點）虛擬出虛擬越多的虛擬節點這樣就能使得所有的緩存key均勻分布并且當一臺掛掉會找相鄰的節點；這樣概率角度能達到均勻的負載到其他服務器上去。

php實現

需要一個函數把字符串轉成整數的函數crc32

簡單示例

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

未完待續….

上一篇：bean的生命周期

下一篇：CodeForces - 764B Timofey and cubes