介绍一种轻巧的一致性哈希算法

发表于 更新于 分类于

主题

介绍一种轻巧的一致性哈希算法

来源

一篇论文：A Fast, Minimal Memory, Consistent Hash Algorithm

此算法的作者是 Google 的 John Lamping 和 Eric Veach

简介

原始代码—— C 代码实现

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets)
{
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31)/double((key >> 33) + 1));
    }
    return b;
}

Java 代码实现

Jump Consistent Hash

GAV

<dependency>
    <groupId>com.github.ssedano</groupId>
    <artifactId>jump-consistent-hash</artifactId>
    <version>1.0.0</version>
</dependency>

使用

int jumpConsistentHash = JumpConsistentHash.jumpConsistenHash(key, buckets);

基本流程

  1. 基于上面的调用方式，算出所有虚拟节点的 hash 环位置
  2. 将这些值都放入跳表中
  3. 要访问数据时，根据数据的 key 算出 hash 环位置
  4. 根据 key 的 hash 环位置，查找跳表得到虚拟节点
  5. 根据虚拟节点，获取真实节点
  6. 访问真实节点，得到数据

这里提到了跳表，我们明天讲

Python 代码实现

Jump Consistent Hash

Jump Consistent Hash

安装

pip install jump-consistent-hash

使用

>>> import jump
>>> jump.hash(256, 1024)
520