Hash冲突和一致性

Stella981
• 阅读 704

对于hash算法,有几个问题避无可避的。

问题1: hash冲突的问题?

1. 背景介绍:

在数据量很大的时候,就会出现hash之后的数值,指向相同的位置,也就是所谓的hash冲突。这个取决于hash算法的好坏,以及数据量的大小,hash算法越差,数据量越大,hash冲突的概率就会越大。

2. 然而一旦出现了hash冲突,我们该怎么办呢?

首先,我们应该考虑能不能找一个更高级的hash算法来解决,让hash值尽量均匀,冲突尽量的少。

其次,我们要想办法来解决hash冲突的问题,目前最常用的解决办法是"链表法",也就是说,在不同的数据hash到同一个值的时候,我们要将这些key依次放到hash对应的value中的一个链表中。在hash冲突很小的时候,链表的访问速度是没有问题的。然而,一旦冲突变得很大的时候,我们就需要对链表进行改造了,让链表变成一个红黑树,进一步减少访问冲突的key值的数据。

问题2: hash的一致性问题?

1.背景介绍:

对于hash来说,另外一个必须要要解决的问题,就是hash的一致性问题了,它所处于的场景常常发生在我们对hash所对应的服务器进行扩容或者缩减的时候,举个例子:服务器不够用,我们添加新的服务器的时候,或者服务器平白无辜挂掉了的时候。在这种情况下,我们又希望hash之后的key尽量少的影响数据的hash指向的服务器,于是便有了hash一致性算法。

2.解决方案:

hash一致性算法大体的意思就是:针对一个很大的数值uint32做hash,从0~2^32-1构成一个环,首先,通过hash算法将服务器的IP或者域名计算一个数值,分布在这一个环上面;然后,对于数据key采用同样的hash算法,将value也分布到这个这个环上面,按照顺时针的顺序找到下一个服务器,将数据的放到这个服务器上面。

服务器数量太少导致的负载不均衡的情况:

上面的算法在服务器数量很大的时候,是没有问题的,数据会均匀分布到这些服务器上面。可是,如果服务器数量很少的时候,就会出现数据落到不同服务器上面的数据不均衡的现象。

为了解决这个问题,hash一致性又引入了虚拟服务器的含义,思路如下:首先将同一个服务器计算多次hash值,这样以来这些大量的虚拟服务器会落在环上面,这个情况下的服务器分布就会均匀很多,如此以来数据的hash值就会被分配到虚拟的服务器上面,而虚拟服务器最终会指向真实的服务器。

笔者觉得,这种操作是利用了添加映射层的方式,类似于将hash值对应一个适配的数据层,在将数据层对应真实的数据。

https://zhuanlan.zhihu.com/p/34985026

问题3: hash中的长尾效应,如何处理?(还不成熟,欢迎讨论)

1.背景介绍:

在开始之前,笔者来讲下长尾效应:对于一个消息,在被一个消费者拿走了之后,如果需要处理很长时间,才能结束,那么笔者称这个消息的任务是一个长尾任务。长尾任务在通过hash之后,往往会导致有一部分服务器上面的任务都是短任务,一部分服务器上的任务长尾任务很多,结果就是有些服务器会很忙。笔者将这种情况描述为长尾效应。

对于长尾效应,笔者觉得根本原因在于消费者处理不同任务的时间有快有慢导致,也就是说我们只要在hash的时候能够识别出来那些服务器处理时间久就好了,让那些处理比较慢的服务器分配少一点的任务数量。

2.解决办法:

基于上面的思路,笔者想到了消息响应机制,也就是说hash的时候,对服务器对应的数据增加一个flag,让它来记录分配出去的key值数据有没有被服务器处理完毕。服务器端在收到消息的任务之后,不立马回复ack消息,等到处理完了之后,再回复ack消息,如此一来,收到ack的hash记录会把服务器的flag设置成true。如此以来,hash之后的数据,不会直接发给没处理完的服务器。

原理类似rabbitmq里面对消费者处理的ack响应处理的思路,不过如此一来,再进行hash的时候,需要根据ack的响应这个可能会导致提供hash服务的进程存在消息堆积的问题。

不过这个问题也是合理的,因为就算快速的消息丢给了消费者,在消费者很慢的时候,消息只是堆积在了消费者而已。当然,我们也可以模拟rabbitmq的方式,增加qos的数量设置,让消费者一次性消费多个消息,如此就会缓解消息堆积在hash的那个服务上面了。

备注:上面这个问题,是作者自己的想法,如果有不足之后,欢迎大家讨论,也希望大家能够提供更好的解决方案。

本文分享自微信公众号 - 灰子学技术(huizixueguoxue)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
1星期前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
2年前
Java中HashMap的实现原理
总结:HashMap的实现原理:1.利用key的hashCode重新hash计算出当前对象的元素在数组中的下标2.存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的keyvalue放入链表中3.获取时,直接找到hash值对应
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
oracle获取hash值
_ORACLE_中提供了几种_HASH_的函数,主要包括下面三种_MD4_,_MD5_,_SH1_。我知道常用的函数调用方法如下:_1,_这个函数不知道具体的哪种算法,不过这个应该是最常用的一个_HASH_函数了_selectdbms\_utility.get\_hash\_value('1',1,100)fromdual;__2,_
Stella981 Stella981
2年前
Hash算法解决冲突的四种方法
Hash算法解决冲突的方法一般有以下几种常用的解决方法 1,开放定址法: 所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入 公式为:fi(key)(f(key)di)MODm(di1,2,3,……,m1) ※用开放定址法解决冲突的做法是:当冲突发
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
2年前
Mysql 表分区分类
针对Mysql数据库,表分区类型简析。【1】表分区类型(1)Range分区:按范围分区。按列值的范围区间进行分区存储;比如:id小于10存储在一个分区;id大于10小于20存储在另外一个分区;(2)List分区:按离散值集合分区。与range分区类似,不过它是按离散值进行分区。(3)Hash分区:按hash算法结果分区。对用户定义的表达式所返
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
6个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这