ClickHouse

1
#include "FunctionsConsistentHashing.h"
2
#include <Functions/FunctionFactory.h>
3

4

5
namespace DB
6
{
7
namespace
8
{
9

10
/// Code from https://arxiv.org/pdf/1406.2294.pdf
11
inline int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets)
12
{
13
    int64_t b = -1, j = 0;
14
    while (j < num_buckets)
15
    {
16
        b = j;
17
        key = key * 2862933555777941757ULL + 1;
18
        j = static_cast<int64_t>((b + 1) * (static_cast<double>(1LL << 31) / static_cast<double>((key >> 33) + 1)));
19
    }
20
    return static_cast<int32_t>(b);
21
}
22

23
struct JumpConsistentHashImpl
24
{
25
    static constexpr auto name = "jumpConsistentHash";
26

27
    using HashType = UInt64;
28
    using ResultType = Int32;
29
    using BucketsType = ResultType;
30
    static constexpr auto max_buckets = static_cast<UInt64>(std::numeric_limits<BucketsType>::max());
31

32
    static inline ResultType apply(UInt64 hash, BucketsType n)
33
    {
34
        return JumpConsistentHash(hash, n);
35
    }
36
};
37

38
using FunctionJumpConsistentHash = FunctionConsistentHashImpl<JumpConsistentHashImpl>;
39

40
}
41

42
REGISTER_FUNCTION(JumpConsistentHash)
43
{
44
    factory.registerFunction<FunctionJumpConsistentHash>();
45
}
46

47
}
48