一緻性雜湊演算法的php實作與分析-算法

<?php

/*

* 一緻性雜湊演算法

* 過程：

* 1，抽象一個圓，然後把伺服器節點按一定算法得到整數有序順時針放到圓上,圓環用2^32 個點來進行均勻切割。

* hash函數的結果應該均勻分布在[0,2^32-1]區間

* 2，由于伺服器少，在圓上分布不均勻會造成資料傾斜，是以我們使用虛拟節點代替伺服器的節點，一個伺服器生成32個虛拟節點，或者更多。

* 3，資料要存到伺服器上，通過同樣的算法得到整數，在圓上順時針跟節點對比，如果剛好大于或者等于，那麼就儲存在這台伺服器上，

* 如果走完一圈也沒找到，就落入第一個節點。

* 參數是：伺服器IP，資料。

* 需要的操作是：添加伺服器，删除伺服器，添加資料（

伺服器在這

）

class A{

public $server;

public $node;

/我們需要得到的散列值是一個正整數，是以我們可以使用times33或者crc32來獲得/

public function hashing($str){

    return sprintf('%u',crc32($str));

}

/添加伺服器/

public function addServer($server){

    if(!isset($this->server[$server])){

        $this->addNode($server);

    }

/添加虛拟節點/

public function addNode($server){

    /每個添加32個虛拟節點，伺服器少你可以添加更多，分布相對均勻以防資料傾斜/

    for($i=0;$i<32;$i++){

        $key_node=$this->hashing($server.$i);

        $this->server[$server][]=$key_node;

        $this->node[$key_node]=$server;

    /變成有序的整數數組/

    ksort($this->node,SORT_NUMERIC);

/删除伺服器/

public function dropServer($server){

    foreach($this->server[$server] as $v){

        unset($this->node[$v]);

    unset($this->server[$server]);

/排程伺服器/

public function getServer($str){

    $key_str=$this->hashing($str);

    /第一個節點/

    $server=current($this->node);

    foreach($this->node as $k=>$v){

        if($k>=$key_str){

            $server=$v;

            break;

        }

    reset($this->node);

    return $server;

$s=new A();

$s->addServer('192.168.1.2:12341');

$s->addServer('192.168.1.3:12342');

$s->addServer('192.168.1.4:12343');

$s->addServer('192.168.1.5:12344');

$s->addServer('192.168.1.6:12345');

echo $s->getServer('我存在哪裡呢');

/結果192.168.1.3:12342/

/删除這台伺服器/

$s->dropServer('192.168.1.3:12342');

/結果192.168.1.3:12344/