分布式系统中三种Hash取模算法原理——普通hash取模、Hash ring、Hash slot-程序员宅基地

技术标签： rust 分布系统后端 Hash Hash ring hash slot

前言

1.Hash取模算法常被用于分布式缓存集群系统，一般分三种，普通hash取模，一致性hash，Hash槽。
2.使用场景：假设现在有一个用户注册系统，用户数量会不断的增大，需要几个服务器共同存储。

一、普通Hash取模

1.先创建4个服务器(canister)，然后对注册的用户id hash之后取模，例如果用户的id是"matt",先对“matt”做hash计算，假设得到值是17，拿这个hash对canister 个数进行取模：17 % 4 = 1，那么这个“matt”的用户就被分配到canister 1进行储存。再来一个用户，重复上一步骤,hash后得到23，那么取模后，分配到canister 3上，访问时也一样，先hash后求余数，再去对应的canister里面读取数据。
在这里插入图片描述
2.使用这种hash取模数算法有一个问题是，当4个canister都满了，如果想增加多一台canister,那么之前的关系就会被全部打乱，就代表着，存储过的数据通过hash索引就找不着位置了。只能全部迁移数据，重新建立关系。
在这里插入图片描述

二.Hash ring

1.Hash 环可以解决动态扩容的问题，首先，在初始化的时候创建一个用户Canister,把Canister id 映射到Hash环上（Canister id Hash对2的32次方取余），然后把当前用户的ID的也映射到这个Hsah 环上（ID Hash 后对2的32次方取余）。当前只有一个Canister 1,那么所有Hash 环上映射的用户顺时针都找到该Canister里面。
如下图：
在这里插入图片描述
2.当Canister 1储存达到额定的容量的时候，动态创建一个Canister 2,也把Canister 2的ID hash后也映射到Hash环上，这时，Hash环上顺时针存储规则就要重新定义。

3. 这时要对所有存储的ID 进行计算，每个ID在计算Hash后会顺时针找到临接的存储节点存放。
这里会引起数据迁移，当只有一个Canister的时候，ID Hash 后顺时针所有临接点都是Canister 1,现在插入了Canister 2，那么原本存储在Canister 1里面的data index 1和data index 2就要迁移到Canister 2里面,这样在查询ID才能找到对应的Canister。
在查询数据时，也是按照PID hash后顺时针去找到临接的Caniste。
在这里插入图片描述
3.当Canister 2达到额定的容量时，再动态创建Canister 3,映射到Hash环上，重复上面的步骤对数据进行迁移。这样，每次在新增一个Canister之后，只会引起小量的数据迁移。如果下图，当增加了Canister后，把原本属于Canister 2的data index 1迁移到新新创建的Canister 3上，就能保证Hash环的插入和查找不会错乱。
在这里插入图片描述
4.hash ring会出现一个问题是，hash倾斜，就是某个canister获取的顺时针很大，某个却佷小，就会出现，有的canister 存了很多数据，有的却没有存到多少数据，为了避免这个问题，就要建立很多个虚拟节点，来均分hash环的空间，虚拟节点所对应的数据再映射到真实节点上，以达到均分的效果。
在这里插入图片描述

三、Hash slot

1.hash 槽的原理跟hash ring差不多，只是hash 槽在初始状态下就确定了映射，Hash 槽计算方式：crc16（ID）% 16383 ,然后对应hash槽上的映射关系存储数据，当取模的值小于3000的时候，ID存储在canister 1上，当值大于30001并小于60000的时候，存储在canister 2上，以类推。
在这里插入图片描述
2.新增canister 时，重新调整映射表，然后把数据迁移到对应的canister 上就可以了，hash slot 理论上出现hash倾斜的概率要小于hash ring.

本文链接：https://blog.csdn.net/matt45m/article/details/126091236

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Docker 快速上手学习入门教程_docker菜鸟教程-程序员宅基地

文章浏览阅读2.5w次，点赞6次，收藏50次。官方解释是，docker 容器是机器上的沙盒进程，它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程，所谓的容器化，其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程

电脑技巧：Windows系统原版纯净软件必备的两个网站_msdn我告诉你-程序员宅基地

文章浏览阅读5.7k次，点赞3次，收藏14次。该如何避免的，今天小编给大家推荐两个下载Windows系统官方软件的资源网站，可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源，比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具（Visual Studio 、SQLServer等等）、系统镜像、设计人员工具等。总的来说，这两个都是非常优秀的Windows系统镜像资源站，提供了丰富的Windows系统镜像资源，并且保证了资源的纯净和安全性，有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你

vue2封装对话框el-dialog组件_<el-dialog 封装成组件 vue2-程序员宅基地

文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_

MFC 文本框换行_c++ mfc同一框内输入二行怎么换行-程序员宅基地

文章浏览阅读4.7k次，点赞5次，收藏6次。MFC 文本框换行标签： it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行

redis-desktop-manager无法连接redis-server的解决方法_redis-server doesn't support auth command or ismis-程序员宅基地

文章浏览阅读832次。检查Linux是否是否开启所需端口，默认为6379，若未打开，将其开启：以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决，修改redis.conf，修改主机地址：bind 192.168.85.**；然后使用该配置文件，重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try

实验四数据选择器及其应用-程序员宅基地

文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用

随便推点

灰色预测模型matlab_MATLAB实战|基于灰色预测河南省社会消费品零售总额预测-程序员宅基地

文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位，是生产的最终目的和动力，是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额，是进行宏观经济调控和消费体制改变创新的基础，是河南省内人民对美好的全面和谐社会的追求的要求，保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型，利用MATLAB软件，预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件

log4qt-程序员宅基地

文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件，看这一篇就足够了一、为啥要使用第三方Log库，而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库，而不用平台自带的Log库首先要说明的是，在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt

100种思维模型之全局观思维模型-67_计算机中对于全局观的-程序员宅基地

文章浏览阅读786次。全局观思维模型，一个教我们由点到线，由线到面，再由面到体，不断的放大格局去思考问题的思维模型。_计算机中对于全局观的

线程间控制之CountDownLatch和CyclicBarrier使用介绍_countdownluach于cyclicbarrier的用法-程序员宅基地

文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算；是一个同步辅助工具类和CyclicBarrier类功能类似，允许一个或多个线程等待，直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景：场景一：所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知，既执行startSignal.countDown()方法后;所有线程才开始执行；每个线程执行完发出做完信号，既执行do..._countdownluach于cyclicbarrier的用法

自动化监控系统Prometheus&Grafana_-自动化监控系统prometheus&grafana实战-程序员宅基地

文章浏览阅读508次。Prometheus 算是一个全能型选手，原生支持容器监控，当然监控传统应用也不是吃干饭的，所以就是容器和非容器他都支持，所有的监控系统都具备这个流程，_-自动化监控系统prometheus&grafana实战

React 组件封装之 Search 搜索_react search-程序员宅基地

文章浏览阅读4.7k次。输入关键字，可以通过键盘的搜索按钮完成搜索功能。_react search