分布式系统中三种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

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

智能推荐

nyoj5 Binary String Matching 查子串个数 strstr函数模板题_nyoj5串匹配-程序员宅基地

文章浏览阅读1.5k次。Binary String Matching时间限制：3000 ms | 内存限制：65535 KB难度：3描述Given two strings A and B, whose alphabet consist only ‘0’ and ‘1’. Your task is only to tell how many times does A appear as a substring of B..._nyoj5串匹配

《数据分析与挖掘第十四章基于基站定位数据的商圈分析》_基于基站定位数据的商圈分析 scala-程序员宅基地

文章浏览阅读1.4k次。基于基站定位数据的商圈分析数据抽取以2014-1-1开始到2014-6-30结束时间作为分析窗口数据分析以55555这个人为例，判断其活动位置，基站号改变，说明其进入下一个区域，分析出2014-1-1下午零时53分进入36902基站，直到二时13分才进入36907基站，说明他在36902基站呆了80分钟数据预处理首先，去掉无用的属性，例如什么信令类型，LOC编号这些的，只留下日期，时间..._基于基站定位数据的商圈分析 scala

【技术分享】针对SOAP的渗透测试与防护_available soap services 漏洞-程序员宅基地

文章浏览阅读2.2k次，点赞3次，收藏2次。本文翻译自：https://blog.securelayer7.net/owasp-top-10-penetration-testing-soap-application-mitigation/SOAP概述简单对象访问协议（SOAP）是连接或Web服务或客户端和Web服务之间的接口。SOAP通过应用层协议（如HTTP，SMTP或甚至TCP）进行操作，用于消息传输。图1 SOAP操..._available soap services 漏洞

GB∕T 33171-2016 城市交通运行状况评价规范_城市交通运行状况评价规范下载-程序员宅基地

文章浏览阅读407次，点赞5次，收藏8次。标准号：GB/T 33171-2016中文标准名称：城市交通运行状况评价规范英文标准名称：Specification for urban traffic performance evaluation_城市交通运行状况评价规范下载

ROS1与ROS2的bag包互换（包含自定义消息）_ros2的rosbag可以用ros1播放么-程序员宅基地

文章浏览阅读7.3k次，点赞8次，收藏48次。https://blog.csdn.net/shanpenghui/article/details/117282535https://blog.csdn.net/weixin_37532614/article/details/109602947https://blog.csdn.net/weixin_41010198/article/details/117042386_ros2的rosbag可以用ros1播放么

Python报错：RuntimeError: one of the variables needed for gradient computation has been modified by_python runtimeerror: one of the variables needed f-程序员宅基地

文章浏览阅读978次。Python报错：RuntimeError: one of the variables needed for gradient computation has been modified by_python runtimeerror: one of the variables needed for gradient computation ha

随便推点

【调剂】太原科技大学材料科学与工程学院特种金属制造与固废高值化利用课题组招收冶金、材料、机械、化工、计算机类调剂生...-程序员宅基地

文章浏览阅读297次。公众号【计算机与软件考研】每天都会发布最新的计算机考研调剂信息！点击公众号界面左下角的调剂信息或者公众号回复“调剂”是计算机/软件等专业的所有调剂信息集合，会一直更新的。太原科技大学材料科学与工程学院特种金属制造与固废高值化利用课题组招收冶金、材料、机械、化工、计算机类调剂生：一志愿为工学专业、数一数二均可。课题组简介：本课题组与山西建邦集团共同成立“优特钢新材料产业技术研究院”，并建设有“太原..._太原科技大学任志峰

docker-compose.yaml设置中国时区_把docker-compose.yml里的这一行 - tz=cn 改成 - tz=asia/shan-程序员宅基地

文章浏览阅读3w次，点赞11次，收藏14次。背景docker中如果对时区不加限制，默认会采用格林尼治时间（GMT），这给日常程序部署、日志查看、错误调试等带来了诸多麻烦与困扰。每次都需要将event发生的显示时间+8个时区，手工换算成北京时间，想想都令人抓狂。Dockerfile中配置时区在Dockerfile中，可以通过如下方式添加中国时区：FROM docker.io/centosMAINTAINER DAVID# 使用..._把docker-compose.yml里的这一行 - tz=cn 改成 - tz=asia/shanghai

【工具使用系列】关于 MATLAB 径向基神经网络，你需要知道的事-程序员宅基地

文章浏览阅读263次。2019独角兽企业重金招聘Python工程师标准>>> ..._径向基神经网络工具

经典搜索算法总结-程序员宅基地

文章浏览阅读1.1w次，点赞20次，收藏167次。前言0x01 搜索问题的形式化0x02 树搜索和图搜索0x03 搜索算法的评估0x04 盲目搜索算法0x04.01 宽度优先搜索算法BFS0x04.02 一致代价搜索算法UCS0x04.03 深度优先搜索算法DFS前言搜索问题是在解决各类问题时不可避免的重点难点，很多问题的求解过程都可以转变为搜索问题。比如，对于以下罗马尼亚问题，希望找到一条路径使得从城市 Arad 到城市 Bucuresti 的路径最短，这就是一个经典的搜索问题，在数据结构课程中，我们都知道使用 Dijkstra 算法来求得最优解，._搜索算法

华为云鲲鹏服务器安装gogs_kunpeng golang镜像-程序员宅基地

文章浏览阅读922次。部署环境名称类型服务器华为云鲲鹏服务器系统版本CentOS 7.6 64bit with ARM安装gogs安装gityum install git -y下载gogs的armv8版本 gogs_0.12.3_linux_armv8.tar.gz 上传到服务器上解压gogs_0.12.3_linux_armv8.tar.gztar -zxvf gogs_0.12.3_linux_armv8.tar.gz进入到对应目录cd gogs后台_kunpeng golang镜像

打表法-程序员宅基地

文章浏览阅读4.8k次，点赞9次，收藏24次。今天见到了传说中的打表法，有人说这是流氓算法，但是我觉得这个也是非常牛逼的。下面就来说说这个打表法把，打表法对于某些用时较长的题目非常的有用。就是将我们要的结果打印到一个文本文档中，然后直接调用这个结果就可以了。在编译的时候就不用再程序里面计算，这样就省了很多时间，。是不是非常的牛逼呢，哈哈程序如下；#include<iostream>#include<..._打表法