`
wbj0110
  • 浏览: 1644346 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

一致性hash算法(consistent hashing)

阅读更多

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛;

1 基本场景

比如你有 N  cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N  cache 上呢,你很可能会采用类似下面的通用方法计算 object  hash 值,然后均匀的映射到到 N  cache 

hash(object)%N

一切都运行正常,再考虑如下的两种情况;

一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m  cache 中移除,这时候 cache  N-1 台,映射公式变成了 hash(object)%(N-1) 

由于访问加重,需要添加 cache ,这时候 cache  N+1 台,映射公式变成了 hash(object)%(N+1) 

1  2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;

再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。

  有什么方法可以改变这个状况呢,这就是 consistent hashing...

2 hash 算法和单调性

   Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

  单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

3 consistent hashing 算法的原理

consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

3.1 环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

circle space

 1 环形 hash 空间

3.2 把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash  key 在环上的分布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

object

 2 4 个对象的 key 值分布

3.3 cache 映射到hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的hash 算法。

假设当前有 A,B  C  3  cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

cache

 3 cache 和对象的 key 值分布

 

说到这里,顺便提一下 cache  hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为hash 输入。

3.4 把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache  hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 object3 对应到 cache C  object4 对应到 cache B 

3.5 考察cache 的变动

前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时,cache 会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

3.5.1 移除 cache

考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache  cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 

remove

 4 Cache B 被移除后的 cache 映射

3.5.2 添加 cache

再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache  cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

 

因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 

add

 添加 cache D 后的映射关系

虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

平衡性

  平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A  cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2  object3  object4 ;分布是很不均衡的。

为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅部署 cache A  cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了cache A  cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 

virtual nodes

 引入“虚拟节点”后的映射关系

 

此时,对象到“虚拟节点”的映射关系为:

objec1->cache A2  objec2->cache A1  objec3->cache C1  objec4->cache C2 

因此对象 object1  object2 都被映射到了 cache A 上,而 object3  object4 映射到了 cache C 上;平衡性有了很大提高。

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

map

 查询对象所在 cache

 

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A  IP 地址为202.168.14.241 

引入“虚拟节点”前,计算 cache A  hash 值:

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A1  cache A2  hash 值:

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2

分享到:
评论

相关推荐

    呼伦贝尔市-鄂温克族自治旗-街道行政区划_150724_Shp数据-wgs84坐标系.rar

    呼伦贝尔市-鄂温克族自治旗-街道行政区划_150724_Shp数据-wgs84坐标系.rar

    Cruise纯电动汽车仿真输入模板详解:涵盖8大核心模块参数设置与代码实现

    内容概要:本文详细介绍了用于Cruise纯电动汽车仿真的输入模板,该模板由8个表单组成,覆盖了从整车参数到计算输出的各个方面。每个表单都包含了关键参数的设置方法及其背后的逻辑,如校核清单、整车参数、电池参数、电机参数、传动系参数、制动轮胎参数、能量回收参数以及最终的计算输出。文中不仅提供了具体的参数定义和计算公式,还附有Python代码示例,帮助用户更好地理解和应用这些参数。此外,作者还分享了一些实用技巧,如防止参数遗漏的校验函数、处理电池温度效应的实际容量计算函数等。 适合人群:从事纯电动汽车仿真工作的工程师和技术人员,尤其是那些需要频繁处理复杂输入参数的人群。 使用场景及目标:① 提高纯电动汽车仿真工作的效率和准确性;② 规范参数收集流程,减少因参数错误导致的仿真失败;③ 提供详细的参数设置指导和代码实现,帮助用户更好地理解和应用Cruise仿真平台。 其他说明:本文不仅提供了一个全面的输入模板,还分享了许多实践经验,旨在帮助用户在实际工作中少走弯路,提高工作效率。

    张家口市-桥西区--街道行政区划_130703_Shp-wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接下载使用。

    通辽市-通辽市-街道行政区划_150500_Shp数据-wgs84坐标系.rar

    街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用

    【预编码】基于matlab大规模多用户MIMO系统低复杂度混合预编码(Rayleigh信道)【含Matlab源码 13197期】.zip

    Matlab领域上传的视频是由对应的完整代码运行得来的,完整代码皆可运行,亲测可用,适合小白; 1、从视频里可见完整代码的内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

    CTF竞赛基于杂项题目的隐写术与编码挑战:涵盖LSB隐写、摩斯密码、进制转换及文件格式转换技巧了文档的核心内容

    内容概要:本文档是作者在bugku平台进行CTF(夺旗赛)杂项题目练习的解题思路总结,涵盖第25至33题。题目类型多样,包括但不限于隐写术、进制转换、音频分析、图像处理等。每道题都详细介绍了背景信息、解题步骤和所使用的工具,如Stegsolve用于图片隐写分析、Python脚本处理进制转换、Audacity解析音频中的摩尔斯电码等。通过这些实例,展示了如何运用各种技术手段解决实际问题,强调了理论与实践相结合的重要性。 适合人群:对信息安全、逆向工程感兴趣的读者,特别是有一定编程基础和技术积累的安全爱好者或初学者。 使用场景及目标:①学习隐写术的基本原理及其在CTF比赛中的应用;②掌握不同进制间的转换方法及其实现;③熟悉音频文件中提取摩尔斯电码的技术;④了解图像处理技巧,如调整尺寸、解析隐藏信息等;⑤掌握压缩文件的明文攻击技巧,以及如何利用已知信息破解加密文件。 阅读建议:由于每道题涉及的知识点较为独立且专业性强,建议读者根据自己的兴趣选择相关题目深入研究。同时,在学习过程中应注重动手实践,尝试复现文中提到的操作流程,并结合网络资源进一步拓展知识面。对于遇到的工具和概念,可以通过查阅官方文档或参考教程加深理解。

    Qt时间标尺控件:实现丝滑缩放与自适应刻度的高效可视化组件

    内容概要:本文详细介绍了如何在Qt中实现一个高效的时间标尺控件,重点讲解了时间标尺的缩放功能、刻度自动生成以及曲线绘制的技术细节。首先,通过重载wheelEvent方法,利用QGraphicsView框架实现了基于鼠标的缩放功能,确保缩放过程中鼠标位置对应的时间点不变。其次,针对不同的时间范围,采用对数分级算法自动调整刻度间隔,使刻度线既美观又实用。最后,在曲线绘制方面,使用QPainterPath进行路径构建,并通过预处理和分段绘制优化性能,确保即使面对大量数据点也能保持流畅的用户体验。 适合人群:具有一定Qt开发经验的程序员,尤其是从事数据可视化项目的开发者。 使用场景及目标:适用于需要展示时间序列数据的应用程序,如金融图表、监控系统、日志分析工具等。主要目标是提供一个响应迅速、视觉效果优秀的交互式时间标尺控件,帮助用户更好地理解和分析数据。 其他说明:文中还提到了一些性能优化的小技巧,如数据预处理、路径分段绘制等,有助于提高大型数据集的渲染速度。同时,作者强调了在时间转换函数中避免使用低效的方法,推荐自行实现高效的缓存机制。

    天津市-静海区-街道行政区_120118_Shapefile_wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接下载使用。

    石家庄市-石家庄市-石家庄市-赵县-街道行政区划_130133_Shp数据wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接下载使用。

    赤峰市-喀喇沁旗-街道行政区划_150428_Shp数据-wgs84坐标系.rar

    赤峰市-喀喇沁旗-街道行政区划_150428_Shp数据-wgs84坐标系.rar

    【时间序列预测】基于Python和LSTM的时间序列预测系统设计与实现:从环境搭建到案例实战

    内容概要:本文详细介绍了使用Python和LSTM(长短期记忆网络)进行时间序列预测的方法及其应用场景。首先阐述了时间序列预测的重要性,指出传统ARIMA模型在处理复杂模式和长期依赖关系时的局限性,进而引出LSTM的优势。LSTM通过引入门控机制(输入门、遗忘门、输出门)和记忆单元,有效解决了长期依赖问题,能更好地捕捉时间序列中的复杂模式。接着,文章详细讲解了LSTM的工作原理,包括各个门控机制的作用和计算流程。随后,通过股票价格预测和气温预测两个案例,逐步演示了从环境搭建、数据准备(包括数据读取、归一化处理)、模型构建(使用Keras搭建LSTM模型)、模型编译、训练与评估到预测结果可视化的全过程。最后,文章总结了LSTM的关键技术和实现要点,并展望了其在自然语言处理、计算机视觉、生物学等领域的应用前景及未来研究方向。 适合人群:具备一定编程基础,尤其是对深度学习和时间序列预测感兴趣的开发者、数据科学家和研究人员。 使用场景及目标:①帮助读者掌握LSTM的基本原理和工作流程;②提供详细的Python实现步骤,包括环境配置、数据处理、模型搭建与训练;③通过具体案例展示LSTM在时间序列预测中的应用,如股票价格预测和气温预测;④探讨LSTM在其他领域的潜在应用,如自然语言处理、计算机视觉和生物学等。 阅读建议:本文内容详尽,涵盖理论与实践两方面,建议读者在阅读过程中结合代码实践,逐步理解LSTM的工作原理和实现细节,特别是注意数据处理和模型参数的选择对预测效果的影响。

    三菱FX5U机床双轴定位控制系统解析与优化 - 结构化编程及应用实例

    内容概要:本文详细介绍了基于三菱FX5U PLC的机床X轴和Y轴工作台定位控制系统的开发与优化过程。主要内容涵盖:使用J4-A系列伺服驱动器进行绝对位置控制,通过ST语言和结构化梯形图实现复杂的20组直线插补工序;手动模式下的点动与长按操作逻辑;MODBUS通讯协议的应用;以及详细的报警诊断和统计功能。文中展示了如何利用结构体封装参数,提高代码可读性和维护性,并通过具体案例解释了关键技术和调试经验。 适合人群:从事工业自动化控制领域的工程师和技术人员,尤其是熟悉三菱PLC编程的从业者。 使用场景及目标:适用于需要深入了解三菱FX5U PLC编程技巧及其在实际工程项目中应用的人群。目标是掌握高级编程方法如结构化编程、ST语言特性、MODBUS通讯优化等,从而提升工作效率并减少调试时间。 其他说明:文章不仅提供了理论知识,还包括大量实用的编程技巧和实践经验分享,有助于读者更好地理解和应用于实际工作中。

    大同市-大同市-街道行政区划_140200_Shp数据-wgs84坐标系.rar

    大同市-大同市-街道行政区划_140200_Shp数据-wgs84坐标系.rar

    火电厂协调仿真机:提升PID参数调试效率与安全性

    内容概要:本文详细介绍了火电厂协调仿真机的应用及其优势,特别是在PID参数调试方面的高效性和安全性。文中通过具体的Python代码示例展示了如何构建锅炉和汽轮机的仿真模型,并解释了PID控制器的工作原理。重点讨论了PID参数调试的关键点,如响应延迟、采样时间设定以及前馈控制的叠加效果。此外,还提到了实时曲线对比、参数扫描、自整定算法等功能的实际应用,强调了仿真机在提高调试效率和降低现场调试风险方面的重要作用。 适合人群:从事火电厂自动化控制领域的工程师和技术人员,尤其是需要进行PID参数调试的专业人士。 使用场景及目标:① 提高PID参数调试效率,减少现场调试时间和成本;② 降低现场调试的安全风险;③ 实现更加精确和平稳的控制系统性能。 其他说明:文章不仅提供了理论指导,还结合了大量的实战经验和具体代码示例,帮助读者更好地理解和掌握协调仿真机的使用方法。

    邢台市-襄都区--街道行政区划_130502_Shp-wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接下载使用。

    保定市-博野县--街道行政区划_130637_Shp-wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接使用。

    学号-姓名-作业二编写程序.ipynb

    学号-姓名-作业二编写程序.ipynb

    正弦内插算法的FPGA实现.docx

    正弦内插算法的FPGA实现.docx

    呼和浩特市_回民区_街道级--街道行政区划_150103_Shp_wgs84坐标系.rar

    街道级行政区划shp数据,wgs84坐标系,直接使用。

    【O05】基于51单片机的16路抢答器设计(一).zip

Global site tag (gtag.js) - Google Analytics