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

相关文章

来自专栏数据库新发现

Oracle诊断案例-SGA与Swap之二

案例描述: 这是一个大型生产系统 问题出现时系统累计大量用户进程 用户请求得不到及时响应,新的进程不断尝试建立连接 连接数很快被用完 数据库版本:9.2.0...

702
来自专栏杨建荣的学习笔记

关于Oracle的技术问答 (r4笔记第85天)

今天和Oracle的一个资深前辈聊了下,聊了不少技术的问题,他也来了兴致,随机提了几个问题来问我,发现看似简单的问题还是有不少的干货,很多东西似懂非懂其实还是没...

4015

控制MongoDB中的集群分片

分片标记是MongoDB 2.2.0版中的一项新功能。它应该强制写入到本地数据中心,但也可以用来将集合固定到一个分片或一组分片。

1867
来自专栏java一日一条

Hadoop HBase存储原理结构学习

hbase是bigtable的开源山寨版本。是建立的hdfs之上,提供高可靠性、高性能、列存储、可伸缩、实时读写的数据库系统。 它介于nosql和RDBMS之...

663
来自专栏大魏分享(微信公众号:david-share)

内存虚拟化技术介绍之---内存去重

前言 虚拟化的目的是为了提升硬件的资源利用率,包括CPU,内存、IO等。在各种虚拟化中,都有内存压缩、内存去重等技术。本文通过介绍PowerVM的内存去重技术,...

3878
来自专栏大魏分享(微信公众号:david-share)

IBM Power7 服务器 Hypervisor 内存使用情况研究

Hypervisor 的概念 Hypervisor 是一种运行在基础物理服务器和操作系统之间的 中间软件 层 , 可允许多个操作系统和应用共享硬件。Hyperv...

2475
来自专栏企鹅号快讯

无惧双十二Or 黑五,这些 MySQL 性能调优技巧看过来

摘要:针对购物旺季网站流量会对数据库造成的压力,作者给出了 MySQL 性能调优的一些技巧,这些技巧极具参考价值,通过这些调优,可以有效避免因为流量过大造成服务...

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

SAP最佳业务实践:SD–可退回包装物销售(120)-5托盘退货

一、 VA01创建托盘退货订单 在此活动中,您可以为托盘输入退货销售订单。 如果您不使用精益仓库管理 (WM),请通过如下路径选择存储地点不使用精益仓库管理进行...

2613
来自专栏数据和云

循序渐进Oracle - 全面认识Oracle ASH

从Oracle 10g开始,Oracle引入了ASH新特性,也就是活动Session历史信息记录(Active Session History,ASH)。如果说...

2535
来自专栏数据和云

盘点 Oracle 11g 中新特性带来的10大性能影响

Oracle的任何一个新版本,总是会带来大量引人瞩目的新特性,但是往往在这些新特性引入之初,首先引起的是一些麻烦,因为对于新技术的不了解、因为对于旧环境的不适应...

3734

扫码关注云+社区