一致 Hash 算法分析

简介: 当我们在做数据库分库分表或者是分布式缓存时,不可避免的都会遇到一个问题:如何将数据均匀的分散到各个节点中,并且尽量的在加减节点时能使受影响的数据最少。

Hash 取模


随机放置就不说了,会带来很多问题。通常最容易想到的方案就是 hash 取模了。


可以将传入的 Key 按照 index = hash(key) % N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法,N 就是节点的数量。


这样可以满足数据的均匀分配,但是这个算法的容错性和扩展性都较差。


比如增加或删除了一个节点时,所有的 Key 都需要重新计算,显然这样成本较高,为此需要一个算法满足分布均匀同时也要有良好的容错性和拓展性。


一致 Hash 算法


一致 Hash 算法是将所有的哈希值构成了一个环,其范围在 0 ~ 2^32-1。如下图:



之后将各个节点散列到这个环上,可以用节点的 IP、hostname 这样的唯一性字段作为 Key 进行 hash(key),散列之后如下:



之后需要将数据定位到对应的节点上,使用同样的 hash 函数 将 Key 也映射到这个环上。



这样按照顺时针方向就可以把 k1 定位到 N1节点,k2 定位到 N3节点,k3 定位到 N2节点


容错性


这时假设 N1 宕机了:



依然根据顺时针方向,k2 和 k3 保持不变,只有 k1 被重新映射到了 N3。这样就很好的保证了容错性,当一个节点宕机时只会影响到少少部分的数据。


拓展性


当新增一个节点时:



在 N2 和 N3 之间新增了一个节点 N4 ,这时会发现受印象的数据只有 k3,其余数据也是保持不变,所以这样也很好的保证了拓展性。


虚拟节点


到目前为止该算法依然也有点问题:


当节点较少时会出现数据分布不均匀的情况:



这样会导致大部分数据都在 N1 节点,只有少量的数据在 N2 节点。


为了解决这个问题,一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash,生成多个节点放置在环上称为虚拟节点:



计算时可以在 IP 后加上编号来生成哈希值。


这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。


相关文章
|
11月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
318 3
|
3月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
237 127
|
5月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
221 4
|
2月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
100 1
|
2月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
5月前
|
存储 监控 算法
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
146 14
|
6月前
|
自然语言处理 算法 安全
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
|
6月前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
6月前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。
|
7月前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
113 3

热门文章

最新文章