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