一致性哈希算法的应用及其优化【转载】

• 简单哈希算法

哈希(Hash)就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,使得散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。哈希算法是一种消息摘要算法,虽然哈希算法不是一种加密算法,但由于其单向运算,具有一定的不可逆性使其成为加密算法中的一个重要构成部分。

• 分布式缓存问题

哈希算法除了在数据加密中的运用外,也可以用在常见的数据分布式技术中。哈希计算是通过求模运算来计算哈希值的,然后根据哈希值将数据映射到存储空间中。设有由 N 个存储节点组成的存储空间,采用简单哈希计算将一个数据对象 object 映射到存储空间上的

公式为:Hash(object)% N。现在假设有一个网站,最近发现随着流量增加,服务器压力越来越大,之前直接读写数据库的方式已经不能满足用户的访问,于是想引入 Memcached 作为缓存机制。现在一共有三台机器可以作为 Memcached 服务器,如下图 1 所示。

可以用简单哈希计算:h = Hash(key) % 3 ,其中 Hash 是一个从字符串到正整数的哈希映射函数,这样能够保证对相同 key 的访问会被发送到相同的服务器。现在如果我们将Memcached Server 分别编号为 0、1、2,那么就可以根据上式和 key 计算出服务器编号 h,然后去访问。但是,由于这样做只是采用了简单的求模运算,使得简单哈希计算存在很多不足:

1)增删节点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为 Hash(object)%(N±1),这将使得所有 object 的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。

2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用,也是亟待解决的一个问题。

3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

由上述分析可知,简单地采用模运算来计算 object 的 Hash 值的算法显得过于简单,存在节点冲突,且难以满足单调性要求。

• 一致性哈希算法

一致性哈希的原理:

首先,对存储节点的哈希值进行计算,其将存储空间抽象为一个环,将存储节点配置到环上。环上所有的节点都有一个值。其次,对数据进行哈希计算,按顺时针方向将其映射到离其最近的节点上去。现在根据一致性哈希算法原理,重新解决上面分布式缓存问题。

1.一致性哈希将整个哈希值空间组织成一个虚拟的圆环,

现在假设某哈希函数 H 的值空

间为 0 – 2^32-1(即哈希值是一个 32 位无符号整形)

,那么整个哈希空间环如下图 2:

2.将各个服务器使用哈希函数进行一个哈希,具体可以选择服务器的 ip 或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中三台服务器使用 ip 地址哈希后在环空间的位置如下图 3 所示。

3.把数据对象映射到哈希空间,对应访问到相应的服务器:

对数据对象进行哈希值计算,将数据对应带到环上。这里考虑四个数据对象 object1、 object2、 object3、 object4 ,通过 Hash 函数计算出 Hash 值的 Key:Hash(object1) = Key1;

Hash(object2) = Key2;

Hash(object3) = Key3;

Hash(object4) =Key4;

将其对应在哈希空间环上,其分布如图 4 所示。

根据一致性哈希算法,object1 会被定为到 Server2 上,object2 被定为到 Server 3 上,而object3 和 object4 分别被定为到 Server 1 上。一致性哈希算法与简单哈希算法相比有了明显的改善:

1.容错性得到了提升。

例如,假设 server2 宕机了,那么此时 object2 ,object3, object4,不会受到影响,只有 object1 被重定位到 Server 3。即在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。如图 5 所示。

2.可扩展性好。同理再增加一台 server 的时候受影响的也只是局部范围。如下图 6 是2^32-1增加一个 server 的情况。

• 一致性哈希算法的优化

一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。如果只有两个 server,如下图 7 所示。时必然造成大量数据集中到 Server 2上,而只有极少量会定位到 Server 1 上。

为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器 ip 或主机名的后面增加编号来实现。例如图 7 的情况,可以为每台服务器计算三个虚拟节点,分别计算“Memcached Server 1-1”、“Memcached Server 1-2”、“Memcached Server1-3”、“Memcached Server 2-1”、“Memcached Server 2-2”、“Memcached Server 2-3”的哈希值,于是形成六个虚拟节点,其环分布如下图 8 所示:

此时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Memcached Server 1-1”、“Memcached Server 1-2”、“Memcached Server 1-3”三个虚拟节点的数据均定位到 Server 1 上。这样就解决了服务节点少时数据倾斜的问题。