分布式缓存技术memcached学习(四)—— 一致性hash算法原理

时间:2022-06-30 11:46:35

分布式一致性hash算法简介

当你看到“分布式一致性hash算法”这个词时,第一时间可能会问,什么是分布式,什么是一致性,hash又是什么。在分析分布式一致性hash算法原理之前,我们先来了解一下这几个概念。

分布式

分布式(distributed)是指在多台不同的服务器中部署不同的服务模块,通过远程调用协同工作,对外提供服务。

以一个航班订票系统为例,这个航班订票系统有航班预定、网上值机、旅客信息管理、订单管理、运价计算等服务模块。现在要以集中式(集群,cluster分布式的方式进行部署,下面我们来看看它们部署的示意图。

集中式示部署意图

图 分布式部署示意图

从上面的集中式示部署意图和分布式部署示意图中我们可以看出,集中式将一个系统的所有服务模块部署到了不同的服务器上,构成一个集群,通过负载均衡设备对外提供服务。分布式则将不同的服务模块分布在不同的服务器上

从上图我们也可以看出,分布式部署方案中,不仅仅是分布式服务,还有分布式数据存储分布式静态资源分布式计算等。此时,可能你已经回忆起上提到的,memcached不就是一套分布式的缓存系统吗。对,没错,memcached的分布式就体现在分布式数据存储,“分布式一致性hash算法”中的“分布式”就是指缓存数据的分布性。

一致性

了解了分布式之后,一致性就好理解了。有分布式数据存储数据,那就离不开分布式提取数据。一致性即存储数据到memcached和从memcached中提取数据的时候采用的算法要一致以保持数据一致性。即当以hash算法将数据存储到memcached时,提取该数据时,也要以hash算法进行提取。

Hash

hash,俗称“哈希”,也叫散列,是一种将任意长度的消息(数据)压缩到某一固定长度的消息摘要(数据)的算法。常见的hash算法有MD5,SHA等。hash算法具有两个重要的特性:不可逆性(即从hash值反推出原消息是不可能的)、抗冲突性(即给定消息M1,不存在另一个消息M2,使得Hash(M1)=Hash(M2))和分布均匀性(即hash的结果是均匀分布的)。memcached中,存取数据时都要进行哈希映射。正是这两个特性,保证了memcached缓存中key值得唯一性。

图 消息哈希过程示意图

三个词已经介绍完了,那memcached为什么要使用分布式一致性hash算法呢,继续看下文。

分布式一致性hash算法使用背景

我们已经知道,memcached的分布式主要在于客户端的分布式算法。memcached客户端就像一个网络中的路由,经过特定的算法将数据分散的存在到memcached服务端的机器上,又从分散的memcached服务端的机器上提取数据。实际中,常见的存储和提取数据的算法有取模算法和本文分析的一致性hash算法。

取模算法算法的原理是:

hash(key)%N

其中key 代表数据的键,N代表memcached服务器的数量。取模的结果就是memcached客户端要定位的memcached服务器。取模算法很明显,结果很容易受N的影响,当服务器数量N增加或者减少的时候,原先的缓存数据定位几乎失效,缓存数据定位失效意味着要到数据库重新查询,这对于高并发的系统来说是致命的。于是,人们提出了一致性hash算法最终目的是实现在移除、添加一个memcached服务器时对已经存在的缓存数据的定位影响尽可能的降到最小

分布式一致性hash算法的简介和使用背景已经介绍完了,想必你对“分布式一致性hash算法”这个词已经不陌生了,下面将开启我们的”分布式一致性hash算法”原理的讲解。

环形hash空间

通常,一个缓存数据的key经过hash后会得到一个32位的值,也就是0~2^32 - 1数值范围。我们可以把这个数值范围抽象成一个首尾相连环形的空间,我们称这个空间为环形hash空间。如下图所示:

图 环形hash空间

映射key到环形hash空间

有了环形hash空间之后,缓存数据的key经过hash后得到的值就映射到了环形hash空间。假设有key1、key2、key3、key4,经过hash后,映射到环形hash空间如下图所示:

图 key映射到环形hash空间

映射server节点到hash空间

同理,我们可以把memcached服务器抽象成网络上的节点经过hash后映射到环形hash空间。假设有server1、server2、server3,经过hash后,映射到环形hash空间如下图所示:

图 server节点映射到环形hash空间

映射key到server节点

现在缓存key和server节点都经过一致性hash算法映射到了环形hash空间,现在就可以将缓存key和server节点的关系进行映射了。顺时针沿着环形hash空间,从某个缓存key开始,直到遇到一个server节点,那么该缓存key就存储到这个server节点上。如图:

图 key映射到server节点

了解了key、server节点、hash空间之间的映射关系之后,现在我们已经清楚了缓存数据是怎样分布的存储到memcached服务器了。查找缓存数据的时候,也采用同样的映射方法来定位。

添加server节点

现在我们已经知道memcached存储和访问数据的策略了。那么当在server集群中增加一个server节点时,对数据访问的命中率又有什么影响呢。如下图,我在serverC和serverD节点之间增加一个节点serverF。

图 增加serverF节点

从上图可以看出,增加serverF节点后,原有的缓存数据分布中,仅有serverC~serverF节点的数据进行了重新分布,这部分数据需要重新到数据库查找再次映射到新添加的serverF节点上。尽管不能命中的缓存数据仍然存在,但相对于取模算法,已经是最大限度地抑制了hash键的重新分布。

删除server节点

同理,当在server集群中删除serverC节点时,受影响的也仅是serverB~serverC之间的缓存数据,这部分数据需要重新到数据库查找再次映射到serverD节点上。如下图所示:

图 删除serverC节点

虚拟节点的引入

我们已经知道,添加和删除节点都会影响缓存数据的分布。尽管hash算法具有分布均匀的特性,但是当集群中server数量很少时,他们可能在环中的分布并不是特别均匀,进而导致缓存数据不能均匀分布到所有的server上。为解决这个问题,需要使用虚拟节点的思想:为每个物理节点(server)在环上分配100~200个点,这样环上的节点较多,就能抑制分布不均匀。当为cache定位目标server时,如果定位到虚拟节点上,就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。如下图所示:

图 引入虚拟server节点

另外,如果每个实际server节点的负载能力不同,可以赋予不同的权重,根据权重分配不同数量的虚拟节点。

虚拟节点的hash计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 serverA 的 IP 地址为 127.0.0.1 。引入虚拟节点前,计算serverA 的 hash 值:

hash(“127.0.0.1”);

和 serverA12 的 hash 值:hash(“127.0.0.1#1”);

hash(“127.0.0.1#2”);

节点变化数据分流的问题

上面讨论的节点变化都会导致部分缓存数据的重新分布,hash算法还有一个重要的衡量指标:hash算法的结果能够保证需要重新分布的缓存数据能映射到新的server节点中。

一致性hash算法与取模算法的比较

取模算法的方法简单,数据的分散性也可以,但其主要缺点是当添加或移除server节点时,缓存重新映射的代价相当巨大。添加或移除server节点时,余数就会产生巨变,这样就无法定位与存储时相同的server节点,从而影响缓存的命中率。而一致性hash算法则最大限度的减少了server节点变化带来的影响,当节点变化时,只影响一个server节点的部分数据,且hash算法能够保证需要重新分布的缓存数据能映射到新的server节点中。

参考文档

http://blog.csdn.net/sparkliang/article/details/5279393

http://www.blogjava.net/hao446tian/archive/2013/01/29/394858.html

http://www.dexcoder.com/selfly/article/2388

http://www.cnblogs.com/lintong/p/4383427.html

http://blog.csdn.net/fdipzone/article/details/7170045

http://blog.jobbole.com/95588/