哈希算法与一致性哈希算法

语言: CN / TW / HK
时间 2023-01-27 03:15:13

theme: orange

哈希算法

哈希函数，又称为散列函数、散列算法。哈希函数把任意长度的消息或数据通过算法压缩成固定长度的摘要信息，也称为哈希值。使得数据量变小，把数据的格式固定下来，哈希值的格式通常是16进制或者是10进制。常见的哈希算法有MD5、SHA-1 `````` func main() { TestString := "this is a test"

Md5Inst := md5.New() Md5Inst.Write([]byte(TestString)) Result := Md5Inst.Sum([]byte("")) fmt.Printf("%x\n\n", Result)

Sha1Inst := sha1.New() Sha1Inst.Write([]byte(TestString)) Result = Sha1Inst.Sum([]byte("")) fmt.Printf("%x\n\n", Result) } /* Output: 54b0c58c7ce9f2a8b551351102ee0938

fa26be19de6bff93f70bc2308434e4a440bbad02 */

``````

主要特点
  • 不可逆， 从哈希值推导出原始数据是不可行的，也就是只有加密过程，没有解密过程。所以Hash算法广泛应用在现代密码体系中
  • 抗碰撞， 理想的哈希函数，不同的信息进行哈希后得到的值应该是不同的，但是从实际上来说，哈希算法其实是有可能发生碰撞的， 输入的信息是无穷的，而输出的哈希值长度是固定的，所以是有限的。好比要把10个苹果放到9个抽屉里面，肯定会有一个抽屉装了多个苹果，只不过哈希算法的碰撞的概率是非常小的，比如128位的哈希值，就有2的128次方的空间。
  • 效率高， 在处理比较大的原生值时，也能快速的计算出哈希值
  • 无规律， 数据的任何改变都会导致哈希值发生改变。即如果输入有微小不同，哈希运算后的输出一定不同
主要应用场景
  • 文件校验，哈希算法可以校验信息是否是相同的，这样的优势可以在文件接收通过对比哈希值判断文件是否正确
  • 数字签名，由于哈希值加密是不可逆的，可以很大程度上实现安全
  • 鉴权协议

为什么要引入一致性哈希算法？

在互联网中，通常面对的都是海量的数据，海量的用户，那为了要满足大量数据的写入和查询，以及高可用， 一台单机的存储服务器肯定是不能满足需求的，通常需要使用多台服务器构建集群，形成分布式存储。

这个过程也就是实现负载均衡的过程，最简单的方式是引入一个中间的负载均衡层，让他将外界的请求轮流的转发给内部的服务器集群，比如集群有3个节点，外界请求也有3 个，那么每个节点处理1个请求，达到了平均分配的目的

image.png

既然如此，我们为什么不能使用哈希算法呢？

这里列出了一个简单的例子，有三位用户，分别是 James、 Bob、 Lee, 我们需要把用户的图片写入到存储服务器节点， 这里有ABC三个节点， 而且当查询用户的图片时， 还需要快速定位到这个用户的图片是在哪个节点存储的，然后直接从这个节点进行查询， 需要满足高效率的查询。

image.png

实现过程：
首先，我们可以对用户标识进行哈希计算，我们可以根据用户名、用户ID或者是用户IP进行计算，这里采用用户名作为对象进行计算，计算会生成一个int类型的数字，然后再根据存储节点的数量进行取模，这里的公式就是 hash(name) % 3， 计算得出的结果只有三种情况，分别是 0，1，2

然后我们再把这三种结果和三个存储节点做一个映射， 0 ==> A， 1 ==> B， 2 == C。因为Hash算法对一个值多次计算后都会得到同样的hash值， 所以上面的公式， 一个用户的图片每次都会固定的写入的其中一个节点，这样做查询的话， 也可以通过hash算法快速找到这个用户的图片所在的节点。

image.png

缺点： 虽然上面我们使用Hash算法实现了负载均衡， 可以根据用户名路由到图片所在的节点服务器， 但是上面的方法也有一个很大的缺点， 那就是当服务器的数量增加或者减少时， 我们通过Hash算法生成的路由规则就再不准确了

如果新增或者减少一个服务器节点，上面的公式就会变成 hash(name) % 4 或者 hash(name) % 2， 这里的关键点是，我们之前用3取模，现在变成用4或者2取模，结果当然大概率是不一样了，这个问题带来的影响是，路由规则不再准确，大部分的查询请求都扑了空，也就是说当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据；同理，假设突然有一台缓存服务器出现了故障，那么我们则需要将故障机器移除，那么缓存服务器数量从3台变为2台，同样会导致大量缓存在同一时间失效，造成了缓存的雪崩，后端服务器将会承受巨大的压力，整个系统很有可能被压垮

那么如何解决这个问题呢？相信有的同学这时应该有了一些想法，是的没错，关键点就在于，不管节点的数量怎么变化，都应该使用一个固定的值来进行取模！只有这样才能保证每次进行Hash计算后，得出的结果是不变的。一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题

一致性哈希算法

一致哈希算法也采用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对一个很大的数（这个数可以用2^32，越大的数，平均分配的概率就越大）进行取模运算，是一个固定的值

实现步骤：
  1. 一致性哈希算法将整个哈希值空间（对2^32取模的结果集）按照顺时针方向组织成一个虚拟的圆环，圆环的正上方的点代表0。0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1，我们把这个由 2^32 个点组成的圆环称为hash环。

image.png

  1. 确定服务器节点在哈希环上的位置，具体可以选择服务器的IP或主机名作为关键字进行哈希：hash(服务器ID) % 2^32，我们使用得到的哈希值代表服务器节点，假设我们有3台服务器，经过哈希计算，映射到了如图的位置：

image.png

  1. 将数据映射到哈希环上，映射的结果值往顺时针方向找到的第一个节点就是存储该数据的节点。我们对要查询的 key-01 进行哈希计算，确定此  key-01 映射在哈希环的位置，然后从这个位置往顺时针的方向找到第一个节点，就是存储该  key-01 数据的节点。下图中的   key-01 映射的位置，往顺时针的方向找到第一个节点就是节点 A。

image.png

上述就是一致性哈希寻址方式，我们来看看，如果增加一个节点或者减少一个节点会发生大量的数据迁移吗？

假设节点数量从 3 增加到了 4，新的节点 D 经过哈希计算后映射到了下图中的位置：

image.png

可以看到，key-01、key-03 都不受影响，只有 key-02  需要被迁移节点 D。

假设节点数量从 3 减少到了 2，比如将节点 A 移除：

image.png

可以看到，key-02 和 key-03 不会受到影响，只有 key-01 需要被迁移节点 B。

因此，在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

不足之处：

上面这些图中 3 个节点映射在哈希环还是比较分散的，所以看起来请求都会「均衡」到每个节点。但是一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上

image.png

从图上我们可以看到，有一半以上的数据都会寻址到节点A，也就是访问主要集中在节点A上，违背了负载均衡平均分配的目的。另外，在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。因此可以通过设置虚拟节点的方式提高均衡度

通过虚拟节点提高均衡度

要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。

但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。

具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。 比如对每个节点分别设置 3 个虚拟节点：

  • 对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
  • 对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
  • 对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03

引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。

image.png

可以看到，节点数量多了之后，节点在哈希环上的分布就相对均匀了，这时候，如果有访问请求寻址到「A-01」这个虚拟节点，接着再通过「A-01」虚拟节点找到真实节点 A，这样请求就能访问到真实节点 A 了。另外，虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可。

因此，带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。

文章参考：

http://www.cnblogs.com/aganippe/p/16009141.html http://blog.csdn.net/a745233700/article/details/120814088

「」
「」