1#include "FunctionsConsistentHashing.h"
2#include <Functions/FunctionFactory.h>
3
4
5namespace DB
6{
7
8/// Code from https://arxiv.org/pdf/1406.2294.pdf
9static inline int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets)
10{
11 int64_t b = -1, j = 0;
12 while (j < num_buckets)
13 {
14 b = j;
15 key = key * 2862933555777941757ULL + 1;
16 j = static_cast<int64_t>((b + 1) * (double(1LL << 31) / double((key >> 33) + 1)));
17 }
18 return static_cast<int32_t>(b);
19}
20
21struct JumpConsistentHashImpl
22{
23 static constexpr auto name = "jumpConsistentHash";
24
25 using HashType = UInt64;
26 using ResultType = Int32;
27 using BucketsType = ResultType;
28 static constexpr auto max_buckets = static_cast<UInt64>(std::numeric_limits<BucketsType>::max());
29
30 static inline ResultType apply(UInt64 hash, BucketsType n)
31 {
32 return JumpConsistentHash(hash, n);
33 }
34};
35
36using FunctionJumpConsistentHash = FunctionConsistentHashImpl<JumpConsistentHashImpl>;
37
38void registerFunctionJumpConsistentHash(FunctionFactory & factory)
39{
40 factory.registerFunction<FunctionJumpConsistentHash>();
41}
42
43}
44
45