什么是一致性 Hash 算法?面试又被问到怎么办?
haoteby 2024-11-11 12:46 18 浏览
01 数据分片
?? 先让我们看一个例子吧
我们经常会用 Redis 做缓存，把一些数据放在上面，以减少数据的压力。
当数据量少，访问压力不大的时候，通常一台Redis就能搞定，为了高可用，弄个主从也就足够了；
当数据量变大，并发量也增加的时候，把全部的缓存数据放在一台机器上就有些吃力了，毕竟一台机器的资源是有限的，通常我们会搭建集群环境，让数据尽量平均的放到每一台 Redis 中，比如我们的集群中有 4 台Redis。
那么如何把数据尽量平均地放到这 4 台Redis中呢？最简单的就是取模算法：
hash( key ) % N，N 为 Redis 的数量，在这里 N = 4 ;
看起来非常得美好，因为依靠这样的方法，我们可以让数据平均存储到 4 台 Redis 中，当有新的请求过来的时候，我们也可以定位数据会在哪台 Redis 中，这样可以精确地查询到缓存数据。
02 数据分片会遇到的问题
但是 4 台 Redis 不够了，需要再增加 4 台 Redis ；
那么这个求余算法就会变成：hash( key ) % 8 ；
那么可以想象一下，当前大部分缓存的位置都会是错误的，极端情况下，就会造成 缓存雪崩。
03 一致性 Hash 算法
一致性 Hash 算法可以很好地解决这个问题，它的大概过程是这样的：
把 0 作为起点，2^32-1 作为终点，画一条直线，再把起点和终点重合，直线变成一个圆，方向是顺时针从小到大。0 的右侧第一个点是 1 ，然后是 2 ，以此类推。
对三台服务器的 IP 或其他关键字进行 hash 后对 2^32 取模，这样势必能落在这个圈上的某个位置，记为 Node1、Node2、Node3。
然后对数据 key 进行相同的操作，势必也会落在圈上的某个位置；然后顺时针行走，可以找到某一个 Node，这就是这个 key 要储存的服务器。
如果增加一台服务器或者删除一台服务器，只会影响 部分数据。
但如果节点太少或分布不均匀的时候，容易造成 数据倾斜，也就是大部分数据会集中在某一台服务器上。
为了解决数据倾斜问题，一致性 Hash 算法提出了【虚拟节点】，会对每一个服务节点计算多个哈希，然后放到圈上的不同位置。
当然我们也可以发现，一致性 Hash 算法，也只是解决大部分数据的问题。
如果看到这里，说明你喜欢这篇文章，请转发
相关推荐
- JAVA零基础入门:JDK的概述及安装（jdk完整安装教程）
-
一.什么是jdkJDK(JavaDevelopmentToolKit)是Java开发工具包，JDK是整个JAVA的核心，包括了Java运行环境（JavaRuntimeEnvirnment），一...
- 开源、强大的工作流引擎:camunda入门介绍
-
原创不易，请多多支持！对Java技术感兴趣的童鞋请关注我，后续技术分享更精彩。简介CamundaisaJava-basedframeworksupportingBPMNforwork...
- Centos8搭建Java环境(JDK1.8+Nginx+Tomcat9+Redis+Mysql)
-
一、开篇1.1目的每次换新的服务器，都要找资料配下环境，所以我写这篇文章，重新梳理了一下，方便了自己,希望也能给大家带来一些帮助。安装的软件有：JDK1.8+Nginx+Tomcat9+...
- 记录一次tomcat的升级过程（tomcat6升级tomcat8）
-
原因：ApacheTomcat资源管理错误漏洞(CVE-2021-42340)版本：ApacheTomcat/9.0.46,tomcat解决方法：升级tomcat9到最新版本9.0.581．官...
- Tomcat10安装与配置图文教程（tomcat安装及配置）
-
Tomcat10安装与配置图文教程1、百度搜索“tomcat下载”，进入官网下载https://tomcat.apache.org/index.html...
- VS2022配置x86/x64调用32位和64位汇编语言动态库环境
-
配置X86MASM汇编环境1.创建项目打开VS2022创建新项目，新建asm文件（注意要手动修改cpp文件后缀名为asm文件后缀名）。2.设置入口点选择菜单栏中的“调试”-“demo调试属性”-...
- ARM版Win10用户狂喜 微软全新补丁让应用不再不兼容
-
Windows10onARM仅支持模拟32位的X86应用程序，这意味着大多数的桌面应用是无法在这一平台上运行的，这在很大程度上限制该平台的发展。为了解决这一问题，微软在内部开发频道推出可用于AR...
- 分享收藏的 oracle 11.2.0.4各平台的下载地址
-
概述oracle11.2.0.4是目前生产环境用的比较多的版本，同时也是很稳定的一个版本。目前官网上已经找不到下载链接了，有粉丝在头条里要求分享一下下载地址。一、各平台下载地址...
- Android-x86现已基于5.1.1 Lollipop:支持UEFI和64位内核
-
采用Linux内核的Android-x86，旨在为PC带来最新的Android移动操作系统体验。而近日，该操作系统已经发布了Android-x865.1的首个候选发布（RC）版本。发行说明中提到：A...
- Linux Kernel源码阅读: x86-64 系统调用实现细节(二)
-
特别说明：该文章前两天发布过，但一直在审核中。看头条网友说字数太多可能一直处于审核中状态，我把该文章拆分成几个章节发布，如影响阅读体验还请见谅。五、系统调用编号...
- 树莓派4B安装win10后实测，CPU秒杀AMD Athlon64 3200+
-
在上一篇文章介绍了如何给树莓派4B安装win10系统，这篇就简单对系统进行测试，上一篇文章链接https://www.toutiao.com/i7015518822056886821/因为树莓派是a...
- 一键离线部署x86、arm64 RabbitMQ，花了2天去验证整理，直接拿去
-
最近有一个项目，客户是内网网络，只能离线部署，采用的麒麟ARM64服务器系统，不能远程部署，需要提前准备离线部署包让客户IT拷备上去再现场部署，部署时间就只有1天。自家系统采用的vue+springb...
- Linux软件包管理（linux系统软件包的安装方法,并简要说明其特点）
-
Linux系统如果需要安装软件怎么办？如何安装，大概有以下几种方式1.二级制软件包管理（RPM、YUM）...
- Tachyum要做全球最强64位处理器:性能比X86强，面积比ARM小
-
全球半导体芯片研发、生产最强的国家非美国莫属，如果有某家美国公司宣布要开发性能超强的芯片，大家不会意外，但要是一家斯洛伐克初创公司宣布要研发超级芯片呢？Tachyum公司就是这样一家公司，成立于201...
- Android L 64位模拟器终于来了:x86独享
-
GoogleI/O2014大会已经过去了很久，64位的AndroidL依然停留在纸面上，但现在至少可以让开发者们先行品尝品尝了：64位的AndroidL模拟器已经发布。这次公布的模拟器镜像是专...