常用哈希算法:加密/路由

哈希算法


常用Hash加密算法

(1)MD5

最常用的Hash加密算法,一般用于加盐存储密码。

所谓“加盐”,就是将Hash后的密码与另一个字符串(一般就是原密码)拼接后,再进行一次Hash。这样能大大降低被暴力破解的可能。

(2)SHA-1

Git求快照就是用的SHA-1

(3)CRC(循环冗余校验)


常用Hash路由算法

(1)普通的余数式哈希

h = Hash(key) % i将数据Hash后分布到i个槽中。

Hash是一个将其他类型映射成正整数的函数。

缺点:

  1. 不具备伸缩性,如果i变化(增加/删除槽),算法和代码就要跟着变化。
  2. 如果i变化,那么就会有大量的数据要根据新的i重新计算h,大量的数据被重定位到不同的服务器造成缓存大量不命中

(2)一致性哈希算法

一致性哈希算法将整个Hash空间组织成一个虚拟的圆环,比如0 ~ 2^31-1

环空间

然后将槽位分配到环上的不同位置,这样,我们就不再根据具体数值确认槽位,而是根据一个数值范围确认槽位,选择顺时针第一个
比如现在有o1 ~ o4 四个槽位,对其进行Hash,将其映射到环空间,对于需要Hash的值,落到了环空间上,顺时针第一个就是它对应的槽位:

1
2
3
4
m1 = hash(o1)
m2 = hash(o2)
m3 = hash(o3)
m4 = hash(o4)

hash

值得注意的是一致性哈希节点宕机后的数据迁移也很麻烦,不适合用作DB的分库分表路由规则,比较适合于那种所有数据冗余存储,每个节点保存相同副本的高可用架构。

同时极限情况可能存在一个节点宕机,压力分摊到剩余节点,导致所有节点都瘫痪、系统不可用的情况。

即使是使用了一致性hash,数据迁移仍然是一个难点

MyCat在rule.xmlPartitionByMurmurHash分片规则中实现了一致性hash,可以通过virtualBucketTimes属性实现均匀一致性hash,并且可以通过weightMapFile配置节点权重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<function name="murmur" class="io.mycat.route.function.PartitionByMurmurHash">
<property name="seed">0</property>
<!-- 分片数量 -->
<property name="count">2</property>
<!-- 一个实际节点默认被映射为160个虚拟节点,这是为了保证数据的均匀性 -->
<property name="virtualBucketTimes">160</property>
<!-- 节点权重,没有指定权重的节点默认是1。
以.property文件的格式填写,
以0~(count-1)的整数值(即节点索引)为key,
以节点权重为value(所有权重必须是正整数,否则以1代替) -->
<property name="weightMapFile">weightMapFile</property>
<!-- 用于测试时观察各物理节点与虚拟节点的分布情况,如果指定了该属性,
会把虚拟节点的一致性hash值和物理节点的映射按行输出到该文件,
如果不指定,就不会输出 -->
<property name="bucketMapPath">/etc/mycat/bucketMapPath</property>
</function>

优点

一致性哈希算法具有较高的容错性和可扩展性,
每次只需要重定位环空间中的一部分数据

比如此时我删除槽位m4,只有m4槽的数据(即原来m3 ~ m4这部分的数据)需要重定位。新增同理。

缺点

槽位的分布并不总是均匀的(极端的情况Hash算法获得的两个槽位甚至相邻),如果槽位较少,数据分布可能不一致
比如下图的情况,m2槽位的数据会远远少于m1槽位。

不一致

(3)均匀一致性哈希算法

虚拟节点:如果槽位过少,可以考虑引入虚拟节点,保证数据分布均匀。

虚拟节点

引入虚拟节点m1-virtual-1和m2-virtual-2,分别分配给m1和m2槽位,保证数据的均匀分布。

-------------本文结束感谢您的阅读-------------

本文标题:常用哈希算法:加密/路由

文章作者:DragonBaby308

发布时间:2019年07月24日 - 21:48

最后更新:2019年09月22日 - 10:05

原始链接:http://www.dragonbaby308.com/hash/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%