Location: PHPKode > scripts > Magic Consistent Hash Script > magic-consistent-hash-class/ConsistentHash.class.php
<?php
/**
 * consistent hash is way to solve messing up 
 * items problem whan 1 server deleted from cluster
 * 
 * if 1 server deleted than all other objects will stay on same servers
 * 
 * example of usage:
 * 
 * to remove server from pool just make item empty, 
 * by this way all cached items will not be reorganized, 
 * only keys from removed server will be reorganized
 * 
 * 
 * $servers = array(
                                        'server1',
                                        'server2',
                                        'server3',
                                     );
    $objCHash = new ConsistentHash($servers);    
    $host = $objCHash->Lookup($id_of_object,3);
    
                                         
 * 
 * @author Magic
 *
 */

class ConsistentHash{
    public $Circle = array();
    public $CircleKeys = array();
    public $Points = 64;
    public function __construct($servers,$points=64){
        $this->Points = $points;
        $this->addToCircle($servers);
        
    }
    
    /**
     * add all existing servers to integer circle
     * @param $servers
     * @return bool
     */
    public function addToCircle($servers){
        $max_val = 4294967296;
                   
        $total_weight = 0;
        $weight = $this->Points;
        $server_count = count($servers);
        $total_weight = $server_count*$weight;
        
        // numbers of points in circle
        $grow = round($max_val/$total_weight);
        
        $j = 0;
        
        for ($i=0; $i <=$max_val; $i+=$grow){
            if ($servers[$j]){
                $circle[sprintf('%u',$i)] = $servers[$j];
            }
            $j<$server_count-1?$j++:$j=0;        
        }
        
        ksort($circle);
        reset($circle);
        $this->Circle = $circle;
        //print_r($this->Circle); die;
        
        $this->CircleKeys = array_keys($circle);
        
        return true;
    }
    
    /**
     * search needed point in circle
     * return index of element in circle
     * uses binary search method. 
     * 
     * if $pointsCount = 1 than will be returned string, 
     * if $pointsCount >1 than will be returned array of strings
     * 
     * usually you not need cahnge here anything
     * 
     * @param $search_val
     * @param $pointsCount
     * @return int
     */
    private function searchInCircle($search_val,$pointsCount=1){
        //$search_val = $search_val;
        $circle_keys = $this->CircleKeys;

        $circle_count = count($circle_keys);
        $res = false;
        $i = $circle_count-1;
        
        // { here we looking key not in circle. rule: max>key<0 - key is out of circle
        // this key will be associated with fist or last item in circle
        if ($circle_keys[$i]<=$search_val && $search_val<=$circle_keys[0]){
            //found
            if ($search_val-$circle_keys[$i]<$circle_keys[0]-$search_val){
                $res = $circle_keys[$i];
            }else{
                $res = $circle_keys[0];
            }
            return $res;
        }elseif($circle_keys[$i]<=$search_val){
            $res = $circle_keys[$i];
        }elseif($search_val<=$circle_keys[0]){
            $res = $circle_keys[0];
        }
        // }
        
        // { if key in circle than search it in circle
        // uses binary searching algorithm
        if (!$res){
            $i=floor(($circle_count-1)/2); 
            $distance = $circle_count-1-$i;
            while(true){
                if ($circle_keys[$i]<=$search_val && $search_val<=$circle_keys[$i+1]){
                    //found
                    if (abs($search_val-$circle_keys[$i])<abs($circle_keys[$i+1]-$search_val)){
                        $res = $circle_keys[$i];
                    }else{
                        $res = $circle_keys[$i+1];
                        $i+=1;
                    }
                    break;
                }else{
                    $distance = floor($distance/2);
                    $distance = $distance>0?$distance:1;
                    if ($search_val>$circle_keys[$i+1]){
                        $i = $i + $distance;
                    }else{
                        $i = $i - $distance;
                    }
                }
            }
        }        
        // }    
        $result = $res;
        // { search another nearly items, 
        // this can be need in case if found items not avaiable at some reason 
        // and program should try another item
        if ($pointsCount>1){ 
            $result = array($res);
            $_l = 1; // go left index
            $_r = 1; // go right index
            for ($j=1; $j<$pointsCount; $j++){
                if (abs($search_val-$circle_keys[$i-$_l])<abs($circle_keys[$i+$_r]-$search_val)){
                    $result[] = $circle_keys[$i-$_l];
                    $_l++;
                }else{
                    $result[] = $circle_keys[$i+$_r];
                    $_r++;
                }
            }
        }
        // }
        
        return $result;
    }
    /**
     * will return constant server name for constant data
     * each data will be saved on own server, so there 
     * will not be mixed data in claster
     * 
     * if $pointsCount = 1 than will be returned string, 
     * if $pointsCount >1 than will be returned array of strings
     * 
     * @param $data
     * @param $pointsCount
     * @return mixed
     */
    public function Lookup($data,$pointsCount=1){
        return $this->getHost($this->Hash($data),$pointsCount);
    }
    
    /**
     * just hash data by crc32
     * 
     * @param $data
     * @return unknown_type
     */
    public function Hash($data){
        return sprintf('%u',crc32($data));
    }
    
    
    /**
     * returns server|servers by hashed key
     * @param $key
     * @param $pointsCount
     * @return mixed
     */
    public function getHost($key, $pointsCount = 1){
        $res = $this->searchInCircle($key,$pointsCount);
        if (is_array($res)){
            $result= array();
            foreach ($res as $v){
                if (!in_array($this->Circle[$v],$result)){
                    $result[] = $this->Circle[$v]; 
                    //$result[] = $v; 
                }
            }
        }else{
            return $this->Circle[$res];    
        }
        
        return $result;
    }
} 
Return current item: Magic Consistent Hash Script