docker高级篇2-分布式存储之三种算法

时间:2022-12-18 14:57:12

面试题:

1~2亿条数据需要缓存,请问如何设计这个缓存案例?

答:单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地?

一般有三种方案:

哈希取余分区;一致性哈希算法分区;哈希槽分区。如下图:

docker高级篇2-分布式存储之三种算法


大家好,我是凯哥Java(kaigejava),乐于分享,每日更新技术文章,欢迎大家关注“凯哥Java”,及时了解更多。让我们一起学Java。也欢迎大家有事没事就来和凯哥聊聊~~~

哈希取余分区:

对redis的key进行hash后和机器总数取余。公式:has(key)%N

这种分区算法的优点:

简单粗暴,直接有效。只需要预估好数据规划好节点。就能保证一段时间的数据支撑。使用HASH算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求,起到负载均衡+分而治之的作用。

缺点:

原来规划后的节点,进行扩容或者缩容就比较麻烦了。不管是扩容还是缩容,每次数据变更导致几点有变动,映射关系需要重新进行计算。在服务器个数固定不变的时候没问题。如果需要弹性扩容或者故障停机的情况下,原来的取模公式就会发生变化。此时地址经过某个redis机器宕机了。由于机器总数量发生了变化,会导致hash取余全部数据重新洗牌啊!!

一致性哈希算法分区:

一致性hash算法是什么?

一致性hash算法在1997年麻省理工学院提出的,设计目标是为了解决:

分布式缓存数据变动和映射问题。某个机器宕机了,分母数量改变了,自然取余就出问题了。

一致性hash算法能干嘛?

提出一致性hash解决方案。目的是当服务器个数发生变动的时候,尽量减少影响客户端到服务器的映射关系。

都有哪些步骤?

3大步骤。

1:算法构建一致性哈希环;

一致性哈希算法必然有个hash函数并安装算法产生hash值,这个算法的所有可能哈希值会构成一个全量集,这个集合可以成为hash空间,范围是[0,2^32-1],这是一个线性空间,但是在算法中,通过适当的逻辑控制将其首尾相连(0=2^32),这样在逻辑上,就形成了一个环形的空间。

一致性哈希环也是使用的取模的方方,是对2^32取模。一致性hash算法将这个哈希值空间组织成一个虚拟的圆环,整个哈希环是按照顺时针方法组织的。如下图:

docker高级篇2-分布式存储之三种算法

2:服务器IP节点映射

将集群中的各个IP节点映射到环上的某一个位置。将各个服务器使用hash进行一个hash.(具体可以选择服务器的IP或者主机名称作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置)。例如4个节点NodeA、B、C、D,经过IP地址的哈希环上计算(hash(ip)),使用IP地址哈希后环空间位置如下图:

docker高级篇2-分布式存储之三种算法

3:key落到服务器的落键规则

hash环构建了、服务器IP节点也映射了,那么当我们需要存储一个KV键值对的时候,先要计算的是key对应的hash值(hash(key)),将这个key使用相同的函数hash计算出哈希值并确定此数据在环上的位置,从此位置沿着环顺时针"行走",第一遇到的服务器就是其应该定位到的服务器。并将该键值对存储在这个节点上。

例如:我们有ObjA、ObjB、ObjC、ObjD四个数据对象,在经过hash计算之后,在环上分布的空间位置如下图。

根据一致性hash算法,ObjA的数据将会被定位到NodeA上。其他的类推,B将会在NodeB上,C将会在NodeC上,D将会在NodeD上.

docker高级篇2-分布式存储之三种算法

一致性hash算法的优点是什么?

1:一致性哈希算法的容错性

假设上图中的NodeC所在的服务器宕机了,可以看到次数对象ABD不会受到影响,只有C队形会被重定位到NodeD的机器上。一般地,在一致性Hash算法中,如果一台服务器不可用了,则受到影响的数据仅仅是对应服务器到其环空间中前一台服务器(也就是沿着逆时针方向行走遇到的第一台服务器)之间的数据而已,其他的数据不会受到影响,简单的来说,就是C服务器挂了,受影响的只是B、C之间的数据,并且这些数据会迁移到D上进行存储。

docker高级篇2-分布式存储之三种算法

2:一致性哈希算法的扩展性

所谓的扩展性,就是数据量增加了,则需要增加一台节点NodeX,X的位置在A和B之间,那受到影响的也就是A到X之间的数据,重新把A到X的数据录入到X上即可,不会导致hash重新取余,全部数据重新洗牌.如下图:

docker高级篇2-分布式存储之三种算法

一致性hash算法的缺点是什么?

一致性哈希算法的数据倾斜问题

在服务器节点太少的情况下,容易因为节点数据分布不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)的问题。假设系统中只有两台服务器。那么出现数据倾斜就如下图:

docker高级篇2-分布式存储之三种算法

总结一致性hash算法:

目的:为了在节点数目发生改变时尽可能少迁移数据。将所有的存储节点排列在相接的hash环上,每个key在计算hash之后,会按照顺时针找到的存储节点存放。而当有节点加入或者退出时候,仅影响该节点在hash环上的顺时针相邻的后续节点。

优点:加入和删除节点只会影响哈希环中顺时针方向相邻的节点,对其他节点无影响。

缺点:数据的分布和节点的位置有关,因为这些节点不是均匀地分布在哈希环上的,所以数据进行存储时候达不到均匀分布效果。可能就出现了数据倾斜问题。

针对上面问题,于是,又有了新的方案。就是接下来要讲的,哈希槽分区。

哈希槽分区

哈希槽是什么?

为什么会出现哈希槽算法?

因为一致性哈希算法的数据倾斜问题,为了解决这个问题。

哈希槽实质上就是一个数组,数组[0,2^14-1]形成hash slot空间。

能干什么?

解决均匀分配的问题,在数据和节点之间又加入了一层,把这一层称为哈希槽(slot),用于管理数据和节点之间的关系。现在就相当于节点上放的是槽,槽里面上的是数据。

docker高级篇2-分布式存储之三种算法

槽解决的是粒度问题,相当于是把粒度变大了。这样便于数据移动。

哈希解决的是映射问题,使用key的哈希值来计算所对应槽,便于数据分配。

多少个hash槽:

一个集群中只能有16384个槽。编号为0--16383(0-2^14-1),这些槽会分配给集群中所有的主节点,分配策略没有要求。可以指定哪个编号的槽分配给哪个主节点。集群会记录节点和槽对应的关系。解决了节点和槽的关系后,接下来就需要对key进行hash值计算,然后对16384取余。余数是几,那么key就落入到对应的槽中。slot=CRC16(key)%16384.以槽为单位移动数据,因为槽的数目是固定的,处理起来比较容器,这样数据迁移问题就解决了.

哈希槽计算

Redis集群中内置了16384个哈希槽,Redis会根据节点数量大致均等地将hash槽映射到不同的节点。当需要在集群中放置一个k-v时,Redis先对key使用crc16算法算出一个结果,然后把结果对16834求余数。这样每个key都会对应一个编号,也就会映射到某个节点上。如下图:

docker高级篇2-分布式存储之三种算法

结束语

如操作有问题欢迎去 我的 ​​个人博客(www.kaigejava.com)​​留言或者  ​​ 微信公众号(凯哥Java)​​留言交流哦。


本系列教程直通车

直通车,本系列教程已发布文章,快速到达,《Docker学习系列》教程已经发布的内容如下:

​【图文教程】Windows11下安装Docker Desktop​

​【填坑】在windows系统下安装Docker Desktop后迁移镜像位置​

​【Docker学习系列】Docker学习1-docker安装​

​【Docker学习系列】Docker学习2-docker设置镜像加速器​

​【Docker学习系列】Docker学习3-docker的run命令干了什么?docker为什么比虚拟机快?​

​【Docker学习系列】Docker学习2-常用命令之启动命令和镜像命令​

​【Docker学习系列】Docker学习系列3:常用命令之容器命令​

​【Docker学习系列】Docker学习4-常用命令之重要的容器命令​

​【Docker教程系列】Docker学习5-Docker镜像理解​

​【Docker教程系列】Docker学习6-Docker镜像commit操作案例​

​【Docker学习教程系列】7-如何将本地的Docker镜像发布到阿里云​

​【Docker学习教程系列】8-如何将本地的Docker镜像发布到私服?​

​「Docker学习系列教程」9-Docker容器数据卷介绍​

​「Docker学习系列教程」10-Docker容器数据卷案例​

​Docker学习11-Docker常规方式安装软件​

​「Docker学习系列教程」基础篇小总结及高级篇预告​

​docker高级篇1-dockeran安装mysql主从复制​


​【Docker学习教程系列汇总】笔记及遇到问题解决文章​