布隆过滤器、哈希一致性

布隆过滤器、哈希一致性

一、布隆过滤器

<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)
blank

相关推荐

  • vmware安装虚拟机失败_虚拟机无法安装系统

    vmware安装虚拟机失败_虚拟机无法安装系统虚拟机给我的编程工作确实带了很多方便,但是虚拟机的一个最大挑战是硬件赶不上,速度太慢了。最近一直在致力于虚拟机上Win7专业版平台上SQLServer2005+VisualStudio2012系统开发,最初还可以,但是越到后面速度越慢。最后决定重新启用记忆版的XP系统。记得最初接触的Windows系统是Win98,是在高中时候与其解下不解之缘的。于是,今天在茶余饭后,开启XP模式。

  • DOS命令copy con的用

    DOS命令copy con的用copy是复制命令con 是dos 设备文件的简称。 在dos中把很多外部设备作为文件,称为设备文件。dos中这样规定的:con 控制台(键盘/显示器) aux (或com1)第一个串口 lpt1 第一个并行打印机接口,nul 不存在的设备 所以,举例说明: copy con abc

  • java中的 Set转List

    java中的 Set转List//构造Map数据 Map&lt;String,String&gt;map=newHashMap&lt;String,String&gt;(); map.put("ele1","小樱"); map.put("ele2","若曦"); map.put("ele3","晴川"); Set&lt;String&gt;s

    2022年10月18日
  • 关于CPU编程—无锁编程

    关于CPU编程—无锁编程Lock-free算法通常比基于锁的算法要好:从其定义来看,它们是wait-free的,可以确保线程永远不会阻塞。状态转变是原子性的,以至于在任何点失败都不会恶化数据结构。因为线程永远不会阻塞,所以当同步的细粒度是单一原子写或比较交换时,它们通常可以带来更高的吞吐量。在某些情况下,lock-free算法会有更少的同步写操作(比如Interlocked操作),因此纯粹从性能

  • 【蓝牙sbc协议】sbc源码阅读笔记(四)——sbc_encode函数详解

    【蓝牙sbc协议】sbc源码阅读笔记(四)——sbc_encode函数详解sbc_encode函数详解函数定义://sbc.cSBC_EXPORTssize_tsbc_encode(sbc_t*sbc,constvoid*input,size_tinput_len, void*output,size_toutput_len,ssize_t*written){ structsbc_priv*priv; intsamples; ssize_tframelen; int(*sbc_enc_process_input)(int

  • mac idea2022.01永久激活【2021免费激活】

    (mac idea2022.01永久激活)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

发表回复

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

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