有趣的算法(四)——一致性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 条评论
登录 后参与评论

相关文章

来自专栏架构师之路

浅谈CAS在分布式ID生成方案上的应用 | 架构师之路

近几篇文章聊CAS被骂得较多,今天还是聊CAS,谈谈CAS在一种“分布式ID生成方案”上的应用。 所谓“分布式ID生成方案”,是指在分布式环境下,生成全局唯一I...

3754
来自专栏coder修行路

Python爬虫从入门到放弃(十)之 关于深度优先和广度优先

网站的树结构 深度优先算法和实现 广度优先算法和实现 网站的树结构 通过伯乐在线网站为例子: ? 并且我们通过访问伯乐在线也是可以发现,我们从任何一个子页面其实...

2248
来自专栏.net core新时代

数据字典生成工具之旅系列文章导航

数据字典生成工具之旅系列文章导航 宣传语 数据字典生成工具、数据字典文档生成工具、NPOI入门、NPOI下载、NPOI中文教程、NPOI实例、DocX组件操作W...

1929
来自专栏逍遥剑客的游戏开发

Nebula3中的委托(Delegate)

973
来自专栏斑斓

漂亮的with,鱼与熊掌可以兼得

假设要加载磁盘上的一个文件,并以二进制形式读取文件的数据。若要从健壮性的角度考虑,需得考虑两种异常情况: 加载文件失败,例如给定的文件路径并不存在该文件 读取文...

3498
来自专栏张善友的专栏

WCF和ASP.NET Web API 接口执行时间监控

软件产品常常会出现这样的情况:产品性能因某些无法预料的瓶颈而受到干扰,导致程序的处理效率降低,性能得不到充分的发挥。如何快速有效地找到软件产品的性能瓶颈,则是我...

2178
来自专栏进击的程序猿

ElasticSearch学习笔记1

先看第一个问题,如果我们用数据来实现搜索功能,可能的语句就是对 string 建立索引,或者直接 like 关键字。带来的问题是什么?

402
来自专栏PingCAP的专栏

TiDB 2.0 GA Release

2018 年 4 月 27 日,TiDB 发布 2.0 GA 版。相比 1.0 版本,对 MySQL 兼容性、系统稳定性、优化器和执行器做了很多改进。

4405
来自专栏Golang语言社区

【Go 语言社区】[Golang]优秀开源库剖析

原创文章,转载请注明出处:服务器非业余研究http://blog.csdn.net/erlib 作者Sunface 1.blelve 地址:h...

3548
来自专栏Jerry的SAP技术分享

微信小程序开发系列二:微信小程序的视图设计

大家如果跟着我第一篇文章 微信小程序开发系列一:微信小程序的申请和开发环境的搭建 一起动手,那么微信小程序的开发环境一定搭好了。效果就是能把该小程序的体验版以二...

652

扫描关注云+社区