有趣的算法（四）-一致性哈希算法模拟Redis集群

I. 概述

redis集群采用一致性哈希的原理，将密钥存储在该服务器上. 本文尝试实现一致性哈希算法来模拟redis集群.

一致性哈希是一种分布式哈希（DHT）实现算法. 设计目标是解决Internet中的热点问题. 它也广泛用于内存缓存和Redis.

当redis使用集群时，服务器的节点分配和数据存储位置由一致的哈希实现.

redis的一致性哈希如下所示:

1，转化

假设一个圆形，其上均匀分布有0-232-1. 当redis集群服务器的数量为n时，通过某种哈希算法将n台服务器转换为数字，并作为节点放置在环中.

这时，当客户端需要设置key => value时，该密钥也将通过相同的哈希算法转换为数字，并且还将其分配在此环上，然后将该密钥按顺时针方向存储靠近节点的方式.

如上图所示，三个绿色节点是三个服务器经过散列并转换为环后的值;黄点是通过哈希转换为圆环的键的值. 那么上图中的key1顺时针最近的节点是node1，存储在node1上；同样，key3存储在node2上； key2和key4存储在node3上.

2. 变化

如果此时有任何服务器关闭，则仅会减少部分数据，并且下一个数据仍可以存储在其最近的顺时针服务器上. 如果添加了新服务器，则无法找到部分数据，但以后添加的数据仍会按照规则存储.

3. 注意

应注意，如果哈希算法设计不当且服务器集中在圆圈的一小部分，则单个服务器上将存储大量数据，并且许多服务器处于空闲状态. 当负载很大的服务器宕机时，会发生雪崩.

为了避免这种情况，在上述基础上，如果将服务器转换为哈希后的节点过于集中，则还需要虚拟节点方法.

如上图所示，假设服务器具有key1redis一致性哈希算法，key2和key4，则圆的其他一半都没有节点redis一致性哈希算法，并且大多数数据将根据概率存储在key2中. 这是需要避免的现象. 因此，可以制造虚拟节点，并且可以将node1，key3和node2用作key1，key2和key4的虚拟节点.

第二，设计

1）哈希函数转换数字

哈希函数用于将服务器转换为数字，并将密钥转换为数字. 使用PHP的crc32函数，可以将任何字符串转换为10位数字，并且232和1010是闭合的，因此使用此方法.

         //将字符串转成10位数字，取正数
         privatefunction changeStrToNum($str){
                   returnabs(crc32($str));
         }

2）服务器转换

对于服务器，使用md5（服务器ip: 端口号: 虚拟序列号），虚拟序列号从0开始到预定的虚拟号码.

         publicfunction setVitualServers(array $servers){
                   //所有主机一起从0生成到vitualnum
                   for($i=0;$i<$this->vitualNum;$i++){
                            foreach($serversas $server){
                                     $tmpStr= $server['ip'] . ':' . $server['port'] . ':' . $i;
                                     $tmpNum= $this->changeStrToNum($tmpStr);
                                     $index= $server['ip'] . ':' . $server['port'];
                                     //避免hash后重复
                                     if(!in_array($tmpNum,$this->allCrcServers)){
                                               $this->servers[$tmpNum][]= $index;
                                               array_push($this->allCrcServers,$tmpNum);
                                     }
                            }
                   }
                   //对allcrcservers排序，从低到高排序
                   sort($this->allCrcServers);
                   return$this;
         }

3）密钥转换

对于密钥，使用crc32直接将其转换为数字.

         publicfunction setHashedKey($str){
                   if(!is_array($str)){
                            $this->keys[$str]= $this->changeStrToNum($str);
                   }else{
                            foreach($stras $s){
                                     $this->keys[$s]= $this->changeStrToNum($s);
                            }
                   }
                   sort($this->keys);
                   return$this;
         }

4）注意事项

无论是服务器还是密钥，转换后都会调用php sort从小到大进行排序，以方便后续搜索.

5）获取与密钥相对应的服务器

         publicfunction ensureKeyServer(){
                   if(empty($this->servers)|| empty($this->keys)){
                            returnnull;
                   }
                   $start= 0;
                   $length= count($this->allCrcServers);
                   foreach($this->keysas $key){
                            $keyToServer= $this->getKeyServer($key, $start, $length-1);
                            //如果比最大值还大，说明其应设定为第一个服务器
                            if(null== $keyToServer){
                                     $keyToServer= 0;
                            }
                            $this->keyToServer[$key]= $keyToServer;
                   }
                   return$this->keyToServer;
         }

6）二分法，快速确定密钥用于哪个服务器

         privatefunction getKeyServer($key, $start, $length){
                   if(1== $length){
                            return$this->allCrcServers[$start];
                   }
                   if(2== $length){
                            $start= $key <= $this->allCrcServers[$start] ? $start : ($start +1);
                            return$this->allCrcServers[$start];
                   }
                   $mid= floor($length/2);
                   if($key<= $this->allCrcServers[$start+$mid-1]){
                            return$this->getKeyServer($key, $start, $mid);
                   }
                   return$this->getKeyServer($key, $start+$mid, $length-$mid);
         }

7）致电

$servers = array(
         array('ip'=>'127.0.0.1','port'=>'5678'),
         array('ip'=>'127.0.0.1','port'=>'6789'),
         array('ip'=>'127.0.0.1','port'=>'7890'),
);
$keys = array(
         'key1',
         'key2',
         'key3',
         'key4',
         'key5'
);
$hash = new ConsistencyHash();
$hash->setVitualServers($servers)->setHashedKey($keys);
var_dump($hash->ensureKeyServer());

8）结果（浏览器输出）

array(5) {
[724672585]=> int(725715703)
[744252496]=>int(745411194)
[1034812036]=>int(1035024362)
[1252706838]=> int(1253443456)
[1547079903]=> int(1548139105)
}

-由linhxx撰写2017.08.22

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-251003-1.html