布隆过滤器、哈希一致性

布隆过滤器、哈希一致性

一、布隆过滤器

<span>布隆过滤器、哈希一致性</span>

使用大的bitMap,存储哈希函数计算后的结果。

请求: 文件中有大量的key,此时请求一个key,判断是否在文件中。(如果允许失误率,使用布隆过滤器)

步骤:1. 使用k个hash函数计算key的hash值,再%m(bitMap的位数),将k个计算出的位置都填1。

​ 2.下次查询是否存在key时,经过k个hash函数计算出的k个值,查看bitMap中对应位置,如果都为1,则存在过,反之不存在。

但是有失误率P,

问题:不存在文件中的key,也会被误认为存在于文件。

​ (如果K值不合适,或者m值过小,则失误率就会上涨。)

下图为各个参数计算公式。

<span>布隆过滤器、哈希一致性</span>

二、哈希一致性

该算法的原理用一句话将就是:

将服务器节点分布到一个环上,必要时需要增加虚拟节点(映射到真实节点),查找的时候根据Hash算法定位到环上的某个点,然后再顺时针找到最近的一个可用的服务器节点。

解决问题

在使用分布式对数据进行存储时,经常会碰到需要新增节点来满足业务快速增长的需求。然而在新增节点时,如果处理不善会导致所有的数据重新分片,这对于某些系统来说可能是灾难性的。

作用:在新增或者减少服务器的时候,减小影响的范围。

原理

一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

<span>布隆过滤器、哈希一致性</span>

  1. 首先求出memcached服务器(节点)的哈希值,并将其配置圆(continuum)上。
  2. 然后采用同样的方法求出存储数据的键的哈希值,并映射到相同的圆上。
  3. 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。

但此时有问题

  1. 机器节点不一定分配均匀
  2. 增加或减少机器,负载就不均衡了

因此产生了虚拟节点技术来解决问题

虚拟节点

为机器分配字符串,此时不再用机器来抢环上的数据归属,而是使用字符串(机器的代表点)来抢占

如机器A:a1,a2,a3,…….a1000

​ B: b1,b2,b3,……b1000

​ C: c1,c2,c3,……..c1000

此时使用字符串(机器的代表点)来计算hash值来抢环

因为虚拟节点很多,所以在环上的任意区域,相当于均分了数据。如下图,任意区域都均分了虚拟节点,

此时如果增加机器,就给新增的节点D也分配很多字符串用来抢数据,最后一个区域均分4个机器的虚拟节点了。

此时就解决了机器节点不均匀分配和增加减少机器负载不均衡的问题了。

而且还额外的增添了一个功能,就是可以管理负载,如果A机器性能良好,就可以分配2000个虚拟节点,而D机器不好,就可以少分配一些节点,从而达到管理负载的效果。

<span>布隆过滤器、哈希一致性</span>

性质

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

如果原本有一些服务器被分配了数据,此时有新的服务器加入,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的服务器中去,,而不会被映射到旧的服务器中。

平滑性(Smoothness)

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

分散性(Spread)

在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。

导致了相同内容被存储到不同缓冲中去,降低了系统存储的效率。

分散性的定义就是上述情况发生的严重程度。

好的哈希算法应能够尽量避免不一致

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115160.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 男生说fb是什么梗_男生聊污是什么意思 男生会对谁聊污

    男生说fb是什么梗_男生聊污是什么意思 男生会对谁聊污男生聊污是在暗示么,肯定啊,经常聊肯定是想要发生些什么,如果能够得到回应肯定就进一步发展了。还有一种情况是为了口嗨,不管是真正的性、还是聊天是聊污,都是为了嗨,最终的目的还是为了上床。一般来讲,女生是不喜欢这样的话题,甚至讲得过份的话会觉得受到侮辱。男生一般不会随便的在女生面前讲起这些话题,讲起来肯定是有目的。费玉清其实也是一种试探,如果两个人能够聊下去,哪怕不发展到床上这种地步,但是也会聊的非常…

  • OpenCV人脸识别的原理 完整版代码

    OpenCV人脸识别的原理 完整版代码http://blog.csdn.net/yanming901012/article/details/8606183本程序首先利用从摄像头检测到的人脸图片,先进行直方图均衡化 并缩放到92*112的图片大小,然后根据train.txt的采集到的人脸模版 进行匹配识别(最好是在统一光照下,采集不同角度的人脸图片各一张) 注意:影响的极大因素在于光照,模版若与采集的图像光照不一样,识别率很低。…

  • 【安德鲁斯】基于脚本的数据库&quot;增量更新&quot;,如果不改变,每次更新java代码、!

    【安德鲁斯】基于脚本的数据库&quot;增量更新&quot;,如果不改变,每次更新java代码、!

    2021年12月31日
  • 有刷/无刷动力电调与马达知识

    有刷/无刷动力电调与马达知识模型车需要行驶,就跟真车一样,需要一套动力单元,也有分电动和油动,至于混合动力这个估计就不需要奢望了,对于车模这么小的空间来说是不现实的,而且模型车也不需要考虑燃油经济性的问题。本文则重点介绍电动模型的动力单元。电动模型的动力,主要是指2个元件:第一就是带动车架行驶的电机(Motor),也称马达/摩打等。第二就是控制电机转速的调速器(SpeedController),很久之前早期的调速器…

  • verilog vhdl混合_vhdl转换为verilog

    verilog vhdl混合_vhdl转换为verilog采用三步法完成混合语言RTL设计的加载。step1.用vhdlcom将所有的VHDLRTL代码编译成库1.1将所有的vhdl文件放到vhdl.f文件中,如:vhdl.f———my_design.vhdmy_lib.vhdtb_my_design.vhd1.2编译成库…

  • mysql 同步远程数据库_两个sql数据库数据实时同步

    mysql 同步远程数据库_两个sql数据库数据实时同步1.服务配置说明:服务器名称服务器地址数据库名称用户名密码端口数据库服务器A121.xx.xx.xxyoujihui_zsrootyoujihui3306数据库服务器B120.yy.yy.yyy

    2022年10月15日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号