lua version: A Fast, Minimal Memory, Consistent Hash Algorithm

jump_consistent_hash.lua

local function jump_consistent_hash(key, num_buckets)
    local b = -1
    local j = 0
    while j < num_buckets do
        b = j
        key = key * 2862933555777941757 + 1
        j = math.floor((b+1) * (1<<31) / ((key>>33) + 1))
    end
    return b
end

local function test()
    local cases = {
        {0, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
        {1, {0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 17, 17}},
        {0xdeadbeef, {0, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 16, 16, 16}},
        {0x0ddc0ffeebadf00d, {0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 15, 15, 15, 15}},
    }

    for _, case in ipairs(cases) do
        local key = case[1]
        local bucket = case[2]
        for i, v in ipairs(bucket) do
            local got = jump_consistent_hash(key, i)
            if got ~= v then
                print("== FAIL ==", key, i, got, v)
            end
        end
        
    end
end

-- run test
test()


local buckets = 100
local new_buckets = 101
print("buckets, new_buckets:", buckets, new_buckets)
for k = 1, 1000 do
    local h1 = jump_consistent_hash(k, buckets)
    local h2 = jump_consistent_hash(k, new_buckets)
    if h1 ~= h2 then
        print(string.format("key %d map to (%d, %d)", k, h1, h2))
    end
end