专栏首页灰子学技术Hash冲突和一致性

Hash冲突和一致性

对于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),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:位运算基本操作

    https://leetcode-cn.com/problems/number-of-1-bits/

    灰子学技术
  • 【C++】虚函数指针和虚函数列表

    本篇文章主要来讲述,C++多态的实现原理,也就是虚函数和虚函数列表是怎么回事?它们是如何实现多态的?

    灰子学技术
  • 分布式锁:一、基础知识

    互斥:是指散步在不同进程之间的若干程序片段,当某个进程运行其中一个程序片段时,其它进程就不能运行它 们之中的任一程序片段,只能等到该进程运行完这个程序片段后才可...

    灰子学技术
  • djb2 hash算法

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就...

    李小白是一只喵
  • hash散列 introduction

    hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

    CoffeeLand
  • 如果世界上只有一种数据结构,那么我选择哈希!

    来源:blog.csdn.net/liweisnake/article/details/104779497

    芋道源码
  • 面试题,如何在千万级的数据中判断一个值是否存在?

    当你看到这个标题的时候,你也许会想我可以使用hashmap之类的来存储值,然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

    ImportSource
  • 纸上谈兵: 哈希表 (hash table)

    HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

    Vamei
  • php hash算法类

    它可以将一个长度不固定的数据,通过算法,获取其特征值生成一个固定的,较短的数据,压缩其文件标识.

    仙士可
  • 【专业技术】STL hash_map使用(一)

    今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券