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

哈希算法

哈希函数，又称为散列函数、散列算法。哈希函数把恣意长度的音讯或数据经过算法压缩成固定长度的摘要信息，也称为哈希值。使得数据量变小，把数据的格局固定下来，哈希值的格局一般是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个恳求，达到了平均分配的意图

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

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

完成进程：
首先，咱们能够对用户标识进行哈希核算，咱们能够依据用户名、用户ID或许是用户IP进行核算，这儿选用用户名作为对象进行核算，核算会生成一个int类型的数字，然后再依据存储节点的数量进行取模，这儿的公式便是 hash(name) % 3， 核算得出的成果只要三种情况，分别是 0，1，2

然后咱们再把这三种成果和三个存储节点做一个映射， 0 ==> A， 1 ==> B， 2 == C。由于Hash算法对一个值屡次核算后都会得到相同的hash值， 所以上面的公式， 一个用户的图片每次都会固定的写入的其中一个节点，这样做查询的话， 也能够经过hash算法快速找到这个用户的图片所在的节点。

缺陷： 尽管上面咱们运用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环。

2. 确认服务器节点在哈希环上的方位，具体能够选择服务器的IP或主机名作为要害字进行哈希：hash(服务器ID) % 2^32，咱们运用得到的哈希值代表服务器节点，假定咱们有3台服务器，经过哈希核算，映射到了如图的方位：

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

上述便是共同性哈希寻址办法，咱们来看看，假如添加一个节点或许减少一个节点会产生很多的数据搬迁吗？

假定节点数量从 3 添加到了 4，新的节点 D 经过哈希核算后映射到了下图中的方位：

能够看到，key-01、key-03 都不受影响，只要 key-02 需求被搬迁节点 D。

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

能够看到，key-02 和 key-03 不会受到影响，只要 key-01 需求被搬迁节点 B。

因而，在共同哈希算法中，假如添加或许移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

不足之处：

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

从图上咱们能够看到，有一半以上的数据都会寻址到节点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 倍。

能够看到，节点数量多了之后，节点在哈希环上的散布就相对均匀了，这时候，假如有访问恳求寻址到「A-01」这个虚拟节点，接着再经过「A-01」虚拟节点找到实在节点 A，这样恳求就能访问到实在节点 A 了。别的，虚拟节点除了会进步节点的均衡度，还会进步体系的稳定性。当节点改变时，会有不同的节点共同分管体系的改变，因而稳定性更高。有了虚拟节点后，还能够为硬件装备更好的节点添加权重，比方对权重更高的节点添加更多的虚拟机节点即可。

因而，带虚拟节点的共同性哈希办法不只适合硬件装备不同的节点的场景，而且适合节点规划会产生改变的场景。

文章参阅：

www.cnblogs.com/aganippe/p/… blog.csdn.net/a745233700/…