一致性哈希算法的php实现与分析-算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

一致性哈希算法的php实现与分析-算法

简介: <?php/** 一致性哈希算法* 过程:* 1,抽象一个圆,然后把服务器节点按一定算法得到整数有序顺时针放到圆上,圆环用2^32 个点来进行均匀切割。* hash函数的结果应该均匀分布在[0,2^32-1]区间* 2,由于服务器少,在圆上分布不均匀会造成数据倾斜,所以我们使用虚拟节点代替服务器的节点,一个服务器生成32个虚拟节点,或者更多。

<?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');

echo $s->getServer('我存在哪里呢');
/结果192.168.1.3:12344/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章