[php]对服务器进行一致性hash分布算法
[*]<?php
[*]/**
[*] * 对服务器进行一致性hash分布算法
[*] */
[*]class HashRing
[*]{
[*] private $servers = array();
[*] private $nodeList = array();
[*] private $nodeHashList = array();
[*] private $nodeTotalNum = 0;
[*] private $virtualNodeNum = 32;
[*] private $keyHash = '';
[*]
[*] public function __construct($servers)
[*] {
[*] $this->servers = $servers;
[*] foreach ($servers as $server) {
[*] for ($i = 0; $i < $this->virtualNodeNum; $i++) {
[*] $this->nodeList[sprintf("%u", crc32($server.'-'.$i))] = array($server, $i);
[*] }
[*] }
[*] ksort($this->nodeList);
[*] $this->nodeHashList = array_keys($this->nodeList);
[*] }
[*]
[*] private function getNodeIndex($key)
[*] {
[*] $this->keyHash = sprintf("%u", crc32($key));
[*] if ($this->keyHash > end($this->nodeHashList)) {
[*] $this->keyHash = $this->keyHash % end($this->nodeHashList);
[*] }
[*] if ($this->keyHash <= reset($this->nodeHashList)) {
[*] return 0;
[*] }
[*] $this->nodeTotalNum = count($this->nodeHashList);
[*] return $this->binaryChopIndex(0, $this->nodeTotalNum);
[*] }
[*]
[*] private function binaryChopIndex($l=0, $r=0)
[*] {
[*] if ($l < $r) {
[*] $avg = intval(($l+$r) / 2);
[*] if ($this->nodeHashList[$avg] == $this->keyHash) {
[*] return $avg;
[*] } elseif ($this->keyHash < $this->nodeHashList[$avg] && ($avg > 0)) {
[*] return $this->binaryChopIndex($l, $avg-1);
[*] } else {
[*] return $this->binaryChopIndex($avg+1, $r);
[*] }
[*] } else {
[*] return $l;
[*] }
[*] }
[*]
[*] public function getServersByKey($key, $num=1)
[*] {
[*] $index = $this->getNodeIndex($key);
[*] $server = $this->nodeList[$this->nodeHashList[$index]];
[*] if ($num == 1) {
[*] return $server[0];
[*] }
[*] if ($num >= count($this->servers)) {
[*] $num = count($this->servers);
[*] }
[*] $result = array($server[0]);
[*] for ($i=$index+1; true; $i++) {
[*] if ($i >= $this->nodeTotalNum) {
[*] $i = 0;
[*] }
[*] $nextServer = $this->nodeList[$this->nodeHashList[$i]];
[*] if (!in_array($nextServer[0], $result)) {
[*] $result[] = $nextServer[0];
[*] }
[*] if (count($result) == $num) {
[*] break;
[*] }
[*] }
[*] return $result;
[*] }
[*]}
[*]
[*]
[*]
[*]//示例
[*]$servers = array(
[*] '127.0.0.1:11211',
[*] '127.0.0.1:11212',
[*] '127.0.0.1:11213',
[*] '127.0.0.1:11214',
[*] '127.0.0.1:11215'
[*]);
[*]$obj = new HashRing($servers);
[*]$servers = $obj->getServersByKey('testkey', 2);
[*]print_r($servers);
[*]echo "\n";
页:
[1]