文档章节

redis系列之——一致性hash算法

诸葛小猿
 诸葛小猿
发布于 07/13 23:23
字数 1832
阅读 55
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

一致性hash算法你了解吗?什么时候使用?解决什么问题?redis集群模式使用了一致性hash算法了吗?

数据分片(sharding)

分布式数据存储时,经常要考虑数据分片,避免将大量的数据放在单表或单库中,造成查询等操作的耗时过长。比如,存储订单数据时使用三个mysql库(编号0,1,2),当一条订单数据过来时,对订单id求hash后与机器数量取模,hash(orderId) % 3,假如得到的结果是2,则这条数据会存储到编号为2的mysql中。分表分库存储时,根据数据库的主键或唯一键做hash,然后跟数据库机器的数量取模,从而决定该条数据放在哪个库中。

根据机器数量取模就会存在一个问题,当机器不够用需要扩容或机器宕机,机器的数量就会发生变化,造成数据的命中率下降,所以之前的数据就需要重新hash做一次sharding。这种操作会导致服务在一定的时间不可用,而且每次扩缩容都会存在这个问题。

一致性hash

一致性hash算法主要应用于分布式存储系统中,可以有效地解决分布式存储结构下普通余数Hash算法带来的伸缩性差的问题,可以保证在动态增加和删除节点的情况下尽量有多的请求命中原来的机器节点。

Hash环

一致性Hash算法也是使用取模的方法,只是,刚才描述的取模法是对服务器的数量进行取模,而一致性Hash算法是对2^ 32-1取模,什么意思呢简单来说,一致性Hash算法将整个Hash值控件组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1取模(即哈希值是一个32位无符号整型),整个哈希环如下:

image-20200712172733665

整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^ 32-1,也就是说0点左侧的第一个点代表2^ 32-1, 0和2^ 32-1在零点中方向重合,我们把这个由2^32个点组成的圆环称为Hash环。

下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的主机名(考虑到ip变动,不要使用ip)作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中三个master节点的IP地址哈希后在环空间的位置如下:

image-20200712172803805

下面将三条key-value数据也放到环上:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置。将数据从所在位置顺时针找第一台遇到的服务器节点,这个节点就是该key存储的服务器!

例如我们有a、b、c三个key,经过哈希计算后,在环空间上的位置如下:key-a存储在node1,key-b存储在node2,key-c存储在node3。

image-20200712172817716

容错性和可扩展性

现假设Node 2不幸宕机,可以看到此时对象key-a和key-c不会受到影响,只有key-b被重定位到Node 3。一般的,在一致性Hash算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器,如下图中Node 2与Node 1之间的数据,图中受影响的是key-2)之间数据,其它不会受到影响。

同样的,如果集群中新增一个node 4,受影响的数据是node 1和node 4之间的数据,其他的数据是不受影响的。

综上所述,一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

数据倾斜

一致性Hash算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题,例如系统中只有两台服务器,此时必然造成大量数据集中到Node 2上,而只有极少量会定位到Node 1上。其环分布如下:

为了解决数据倾斜问题,一致性Hash算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node 1#1”、“Node 1#2”、“Node 1#3”、“Node 2#1”、“Node 2#2”、“Node 2#3”的哈希值,于是形成六个虚拟节点:

上图中虚拟节点node 1#1,node 1#2,node 1#3都属于真实节点node 1;虚拟节点node 2#1,node 2#2,node 2#3都属于真实节点node 2。

实际项目中使用

上来先说一个误区,Redis 集群没有使用一致性hash, 而是引入了哈希槽slots的概念。可以参考我的另一篇文章《redis系列之——高可用(主从、哨兵、集群)》。

我们说的一致性hash都不是缓存机器自身的功能,而是集群前置的代理或客户端实现的。而redis官方的集群是集群本身通过slots实现了数据分片。

redis集群时3.0版本才出现的,出现的比较晚,在集群模式出现之前,很多公司都做了自己的redis集群了。这些自研的redis集群的实现方式有多种,比如在redis的jedis客户端jar包就是实现了一致性hash算法(客户端模式),或者在redis集群前面加上一层前置代理如Twemproxy也实现了hash一致性算法(代理模式)。Twemproxy,是 Twitter 开源出来的 Redis 和 Memcached 代理,使用这种代理模式搭建的集群,我们的客户端连接只需要连接代理服务器即可,不用连接代理后面具体的redis机器。Twemproxy具体使用哪一种hash算法也是可以通过配置文件指定的。

完成,收工!

传播知识,共享价值】,感谢小伙伴们的关注和支持,我是【诸葛小猿】,一个彷徨中奋斗的互联网民工!!!

诸葛小猿
粉丝 0
博文 20
码字总数 48020
作品 0
崇明
私信 提问
加载中
请先登录后再评论。
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
Javascript图元绘制库--ternlight

基于HTML CANVAS API的Javascript库,提供在HTML页面上绘制图元——如流程图的能力。 目前已支持简单的矩形图元和图元间的连线(直线、直角连线两种),拖拽图元等能力。 该javascript librar...

fancimage1
2013/02/07
6.1K
1
实时分析系统--istatd

istatd是IMVU公司工程师开发的一款优秀的实时分析系统,能够有效地收集,存储和搜索各种分析指标,类似cacti,Graphite,Zabbix等系统。实际上,istatd修改了Graphite的存储后端,重新实现了...

匿名
2013/02/07
2.7K
1
PHP框架--XiunoPHP

XiunoPHP 是一款面向高负载应用的 PHP 开发框架,PHPer 通过它可以快速的简单的开发出高负载项目。 XiunoPHP 前身名为 Xiuno Framework,更名后版本号从 v1.0 开始计算。已经经过了多年的实际...

匿名
2013/03/20
2.5K
0
图形化的 IDE--LiveCode

LiveCode是一个图形化的IDE,允许用户通过拖放控件并编写代码,来创建桌面或移动应用程序(支持Windows、Mac OS、Linux、iOS和Android平台)。LiveCode受苹果HyperCard的启发,采用一种基于英...

匿名
2013/04/12
7.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

IntelliJ IDEA简介及jetbrains-agent安装教程

IDEA 全称 IntelliJ IDEA,是java编程语言开发的集成环境。IntelliJ在业界被公认为最好的java开发工具,尤其在智能代码助手、代码自动提示、重构、JavaEE支持、各类版本工具(git、svn等)、J...

osc_mxz6aybo
19分钟前
13
0
Arraylist翻译分析

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //序列号UID,代表版本,私有的静态常量 private static final......

osc_bgpugm2v
20分钟前
0
0
深入分析序列化和反序列化原理,终于知道serialVersionUID到底有什么用了

深入序列化和反序列化原理 一个问题引发的思考 什么是序列化和反序列化 为什么需要序列化 序列化的方式 Java序列化 serialVersionUID的作用 serialVersionUID的两种表现形式 Transient关键字...

osc_sw1y4qdg
21分钟前
0
0
039. Nginx 负载均衡

1. 基于反向代理的功能,Nginx 作为负载均衡主要有以下几点理由: 高并发连接。 采用 epoll nio 的形式。 内存消耗少。 使用了大量自带的数据结构(自己设计的)。 数据拷贝采用类零拷贝的形式...

华夏紫穹
22分钟前
12
0
线程的基本概念和线程的使用方法

线程的基本概念 很多人会对程序、进程和线程之间理解比较含糊,在此先给出三者的概念: 程序:是一个指令的集合,意思就是我们为了完成特定的功能而编写的代码。 进程:是指程序的一次静态态执...

osc_t46alvdj
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部