有趣的算法(四)——一致性Hash算法模拟redis集群

有趣的算法(四)——一致性Hash算法模拟redis集群

(原创内容,转载请注明来源,谢谢)

一、概述

redis的集群,对key存储在哪个服务器的问题上,采用的是一致性hash的原理。本文试着实现一致性hash算法, 以模拟redis的集群。

一致性hash是一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,在memcache和redis中也使用广泛。

当redis采用集群(cluster)时,对于服务器的节点分配和数据存储位置就是采用一致性hash的方式来实现。

redis的一致性hash如下图所示:

1、转换

假设一个圆圈,上面均匀分布了0-232-1。当redis的集群服务器数量是n,就通过某种hash算法,将这n台服务器转换成数字,放置到圆环中,当作节点。

此时,客户端需要设置key=>value时,把key也通过同一个hash算法,转换成数字,也分布到这个圆环上,再通过顺时针的 方式,将key存储到与其最接近的一个节点中。

如上图所示,三个绿色的节点就是三台服务器经过hash,被转换到圆环上后的值;黄色的点是key经过hash转换到圆环上的值。则上图的key1顺时针最近的节点是node1,其就存储在node1上;同理,key3存储在node2;key2和key4存储在node3。

2、变动

如果此时任意一台服务器宕机,也只是部分数据减少,再来的数据仍可以存储在其顺时针最近的服务器上。如果新增服务器,则也是部分数据无法找到,但后续新增的数据仍按规则进行存储。

3、注意

需要注意的是,如果hash算法设计的不好,服务器都集中在圆圈的一小部分,则会有大量的数据存储在个别服务器,而很多服务器又空闲。当某个承载巨大的服务器宕机,会发生雪崩现象。

为避免此情况,在上述的基础上,如果服务器转成hash后的节点太集中,还需要采用虚拟节点的方式。

如上图所示,假设服务器上述key1、key2、key4,则圆的另外大半边都没有节点,按照概率大部分的数据将存储在key2。这是需要避免的现象。因此,就可以制造虚拟节点,可以让node1、key3、node2作为key1、key2、key4的虚拟节点。

二、设计

1)hash函数转换数字

hash函数用于将服务器转换成数字,也用于将key转换成数字。采用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)获取key对应的server

         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)二分法,快速判断key对于的server是哪个

         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)
}

——written by linhxx 2017.08.22

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

文本分类中语料库的获取——搜狗语料库

这次主要总结搜过语料库的获取,因为老师要求20万数据,而我自己只爬了2万多,所以用到了搜狗的语料库. ? 在这个页面中,我选择的是一个月的数据,别小看一个月...

5708
来自专栏NetCore

Visual C#.Net网络程序开发-Tcp篇(2) 祥细内容:

前面我们说,TcpClient类创建在Socket之上,在Tcp服务方面提供了更高层次的抽象,体现在网络数据的发送和接受方面,是TcpClient使用标准的St...

4545
来自专栏用户画像

Python 使用正则表达式进行MongoDB条件查询

db.VideoProfile.find( {_id: { $regex: /^1_[0-9]{5,}$/} } ).count()

722
来自专栏SAP最佳业务实践

想学FM系列(18)-SAP FM模块:派生规则推导策略(1)-派生规则推导步骤-初始化

4 派生规则推导策略 派生规则推导,是SAP提供由数据源推导到目标数据的一种工具,它提供了一系列面向用户开放使用的方法来使数据源经过逻辑推理后生成了有效目标数据...

4087
来自专栏Petrichor的专栏

tensorflow: variable的值 与 variable.read_value()的值 区别

查看 tensorflow api manual 时,看到关于 variable.read_value() 的注解如图:

1013
来自专栏一个会写诗的程序员的博客

《一切皆是映射》 一致性哈希算法(consistent hashing)

按照常用的hash算法来将对应的key哈希到一个具有232次方个桶的空间中,即0~(232)-1的数字空间中。现在我们可以将这些数字头尾相连,想象成一个闭合的环...

884
来自专栏linux驱动个人学习

Linux CFS调度器之负荷权重load_weight--Linux进程的管理与调度(二十五)

负荷权重用struct load_weight数据结构来表示, 保存着进程权重值weight。其定义在/include/linux/sched.h, v=4.6...

711
来自专栏java一日一条

Github 的清点对象算法

这就叫”清点对象”(counting objects),Github需要实时计算出来,需要克隆的对象总数。

602
来自专栏GAN&CV

tensorflow ‘/biases/Adam_1’not in ckpt file

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_25737169/article/d...

1275
来自专栏前端杂货铺

[译] Cookbook of QUnit

本篇文章是QUnit的简介,可以作为很好的入门教程。文章原址 介绍 自动化测试时软件开发过程中必不可少的一部分,而单元测试则是自动化测试的最为基本的一块,软件的...

29111

扫码关注云+社区