memcached客户端一致性哈希算法实现——libketama

对于memcached，K-V存储到哪个memcached服务器，由memcached客户端决定。下面我们分析一种memcached客户端一致性哈希算法（consistent hashing algo）实现库——libketama。

使用方法

libketama提供了一个memcached服务器配置文件，我们需先将服务器ip、memory填入该文件：

之后我们编码调用libketama接口，输入K-V中的key值，libketama为我们返回该K-V将要被存放到的memcached服务器ip。

以上代码简单展示了libketama的用法，用到libketama提供的ketama_roll、ketama_hashi、ketama_get_server、ketama_smoke几个接口。

一致性哈希模型构建

构建一致性哈希模型，需要模拟两个对象，一个是圆，另一个是圆上的虚拟节点。libketama分别通过continuum、mcs两个结构模拟圆和虚拟节点：

以上numpoints记录圆上虚拟节点的数目，modtime记录memcached服务器配置文件的修改时间，array为圆上虚拟节点mcs数组。

以上point记录虚拟节点在圆上的位置。

模型构建过程

ketama_roll接口用于一致性哈希模型构建，其调用ketama_create_continuum，ketama_create_continuum函数先调用read_server_definition函数读取memcached服务器配置文件，将信息保存在以下结构中：

之后构建虚拟节点，根据所配置的服务器个数，一共构建numservers*160个虚拟节点：

以上代码中，首先对每个物理服务器节点计算权重pct，再由权重得出为每个物理服务器设立的虚拟节点个数ks*4。

之后调用ketama_md5_digest计算“ip-i”（比如“10.0.1.1:11211-0”）对应的md5值，并由该md5值得出虚拟节点的具体位置，即mcs结构中的point值。

确定所有虚拟节点point值之后，最终对所有point值排序，并将虚拟节点总个数、mcs数组放入共享内存中。至此完成一致性哈希模型的构建。

由Key获取ip

一个K-V应该放入哪个memcached？首先我们可以调用ketama_hashi接口计算出key的md5散列值kh，其计算方法与计算虚拟节点point值的方法相同。

之后调用ketama_get_server，构建虚拟节点时虚拟节点已根据point值完成排序，ketama_get_server中采用二分查找法，若能找到第一个大于kh的point值，则返回相应的mcs结构；若未找到，则返回虚拟节点数组的第一个mcs结构。

Have fun!