哈希就是一种函数,也可以叫散列、杂凑。
百度有专门的定义:是把任意长度的输入(又叫做预映射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)。
单调性:新增了服务器,某一用户请求要么依旧是在原服务器上处理,要么就是在新增的服务器上处理,不会在其它服务器上处理。
分散性:哈希一致性的分散性很低。就是保证同一用户的请求尽量是在同一服务器上处理。
平衡性:不同于均衡性。平衡性,只是代表一致性哈希确保了每台服务器有请求处理,但请求数量是不是一致就没法保障。在一致性哈希环上添加虚拟结点,构成均衡一致性哈希结构,此时才有请求处理的均衡性。
说通俗点,一致性哈希只是确保了每台服务器有粥可吃,并没保障每个服务器粥量一样。
具体建议大家参看文末链接。
参考文章推荐: