一致性哈希算法的优化关于如何保正在环中增

背景

09

年初，我们做了一个


memcached


的智能客户端库，业务只要将这个库链上，就能跟


memcached


服务器通信。并且实现了一致性哈希的分布式算法，后端


memcached


服务器可以无限制扩展，而且客户端能对


memcached


做自动故障转移以及恢复。

我们知道，在没有对数据做冗余存储的情况下，无论是一致性哈希还是求余数分布式算法，在新增或删除

memcached


节点时，命中率都会不同程度的降低。本文旨在解决当新增


memcached


节点时，如何保证命中率不变。

基本原理

当


新增一个

memcached


节点时，将该新节点的下一个节点的且属于该新节点的数据迁移过来。

上面的这个基本原理读起来可能会比较拗口，容我下面详细说明。

原理描述

如图

1


所示，假设当前哈希环上有


n


个


memcached


节点，记为


M



1


~M


n


，存储到这些节点上的数据的有效期都是一致的，记为

T



e


。因此从图

1


可以看出，从



M


1


到


M


k


区间的数据均从

M



k


上存取。比如数据

K



1


，

K



2


，

K



n


。

                                                                            图1

当新增节点


M


x


时，如图

2


所示。

                                                                              图2

此时数据


K


1


，

K



2


从新节点


M


x


读取不到的，但节点


M


k


存储了这些数据，我们需要做的就是将这些数据迁移到新节点


M


x


。

具体做法是：将新加入的节点


M


x


标记为

N


（


New


）状态，表示该节点是新增的。在


N


状态下读取数据


K



1


的步骤为：

1）


从


M


x


读取数据，如果读取得到，则返回，否则进行

2


）；

2）


从


M


k


读取数据，如果读取不到，则返回，否则进行

3


）；

3）


将读取到的数据

K



1


写入


M


x


；

4）


将

K



1


从


M


k


删除；

在

N


状态下，不断进行上面的


4


个步骤

因为数据的有效期是

T



e


，所以在经过

T



e


时间后，


M


k


上的数据随之自动失效了，此时将


M


x


标记为

O


（


Old


）状态，在


O


状态下，如果读取不到数据也立即返回，无需再次到它下一个节点尝试读取。