文章大纲

哈希及哈希一致性的温习

2020年04月02日 00:26

哈希是什么?

哈希就是一种函数,也可以叫散列、杂凑。


哈希函数是做什么的?

百度有专门的定义:是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。


说得有点高深,简单举个例子,就很好懂了。


假如某银行办公有3个窗口,有人来办事就得先从机器取号,然后机器就会打印一张号码,上面有指定该人去哪个窗口办理业务。


去银行办理业务的人员数量是不确定的,就是上面定义里提到的“任意长度”。


银行只有3个窗口受理业务,这就是定义里的“固定长度的输出”。


取号器打印的排队号码上指定了办理窗口,这是机器内部通过某种计算而安排的,这就是上面定义里说的“散列算法”。


常见的哈希函数有哪些?

1. 直接寻址法。

算法就是一个线性方程式:y= ax+b, x为输入值,y为输出值。


2.数字分析法。

对输入值进行分析,然后再构造出冲突率较低的输出值,即散列值。


3.平方取中法(不懂,忽略)


4.折叠法(同上)


5.随机数法。

随机种子,生成随机数,作为散列值


6.取余法。

例如输入值10,除以3,余数1,1就是输入值10对应的散列值。3这个数字,实际场景应该选择多少,就具体情况具体分析了。


什么是哈希碰撞?

也叫哈希冲撞,哈希冲突。

拿上面银行办理业务的例子来说,就是两个不同号码的人,抽到的是在同一窗口办理业务。

拿上面取余法来举例子,1、4、10的散列值都是1,就是碰撞了。

归纳定义一下:哈希碰撞就是不同的输入值,经过散列算法,得到的却是相同的散列值。


哈希碰撞有什么坏处?

谈好坏的前提,是首先得确定使用场景。


在针对使用场景谈好坏之前,先提提分布式和集群的区别。


分布式和集群的区别?

举例子说明,最容易区分了。

假如一个系统有用户系统、订单系统、仓库系统、财务系统等多个部分,服务器当前有A、B、C、D3台。

分布式:A服务器部署用户系统,B服务器部署订单系统,C服务器部署仓库系统,D服务器部署财务系统。

集群:A、B、C、D四台服务器都包含上面提到的四个子系统。


归纳定义一下:分布式就是将一块数据分割成多块存储了,而集群则是将一块数据拷贝成好几份完全一样的。


当我们用某哈希算法给用户生成id时,如果发生A用户和B用户id一样,即哈希碰撞,就代表B用户可以盗取A用户的信息了。某些骇客就专干这些好事儿,这就是哈希碰撞的坏处。


如果拿nginx负载均衡来说,对用户id除模取余,然后根据散列值派发到对应的服务器上去,这个场景下,肯定是要允许有多个用户的请求都能被某一台服务器处理,就像上面银行窗口处理业务的例子一样,这时“哈希碰撞”只是对这种状况的一种描述而已了,就不存在所谓的坏处一说。


一致性哈希是什么?

一致性哈希是算法,英文叫Distributed Hash Table,直面翻译为分布式哈希表,缩写DHT。一致性这个名字的来源,得从理解这个算法开始。


这个算法处理的是什么问题呢?

还是举例子来说明。

例如某系统缓存采用了分布式架构,用户数据,被分布到多个redis服务器上去了。现假定有3台redis服务器R1、R2、R3,以前根据取余的哈希算法将用户数据分布的存储在R1、R2、R3这台服务器里。例如1、4、7...用户的数据存储在R1,2、5、8...用户的数据存储在R2里,3、6、9...用户的数据存储在R3里。


现在为了扩容,新增一台redis服务器R4,取余算法里的模值改为4了,然后就变成1、5、9...用户数据存储在R1了。以前用户5的缓存数据是在R2里,现在变成R1了,会造成用户读取缓存数据失败、缓存数据存储混乱的结果。


上面问题导致的原因,其实就是映射关系的变更导致的。以前是A对应R1,后面变成A对应R2了。


一致性哈希算法的出现,就是为了解决这个映射全部变更的问题,确保大部分映射关系,在新增或下线服务器时,能够得已保持不变。


一致性哈希有什么好处?

好处就是确保大部分映射关系,在新增或下线服务器时,能够得已保持不变。

这里注意是大部分,并不是全部,一致性哈希是无法完完全全保持原有的映射关系的。


关于哈希一致性的深刻理解,请看文末推荐文章。


哈希一致性的倾斜是什么?又该如何解决?

当哈希环上服务器分布不均,就会导致各服务器处理用户请求不均衡。采用添加虚拟节点来解决这个问题。


具体建议大家参看文末链接。


哈希一致性的3个特性:单调性(monotonicity)、分散性(spread)、平衡性(balance)。


单调性:新增了服务器,某一用户请求要么依旧是在原服务器上处理,要么就是在新增的服务器上处理,不会在其它服务器上处理。


分散性:哈希一致性的分散性很低。就是保证同一用户的请求尽量是在同一服务器上处理。


平衡性:不同于均衡性。平衡性,只是代表一致性哈希确保了每台服务器有请求处理,但请求数量是不是一致就没法保障。在一致性哈希环上添加虚拟结点,构成均衡一致性哈希结构,此时才有请求处理的均衡性。


说通俗点,一致性哈希只是确保了每台服务器有粥可吃,并没保障每个服务器粥量一样。


具体建议大家参看文末链接。


参考文章推荐:

1、深入浅出一致性Hash原理

2、哈希碰撞与生日攻击



  • 2020年04月01日 18:11文章创建
  • 2020年04月02日 00:26文章发布
我要评论
«-必填,限2-20个字符,中文/字母/字母数字组合
«-评论后,邮箱会收到激活链接,未激活邮箱的留言,将无法显示
评论列表
暂无评论,期待你的评论哦!
回到顶部