[php]对服务器进行一致性hash分布算法

ponh

• <?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";