1 | #include "FunctionsConsistentHashing.h" |
---|---|
2 | #include <Functions/FunctionFactory.h> |
3 | |
4 | |
5 | namespace DB |
6 | { |
7 | |
8 | /// Code from https://arxiv.org/pdf/1406.2294.pdf |
9 | static 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 | |
21 | struct 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 | |
36 | using FunctionJumpConsistentHash = FunctionConsistentHashImpl<JumpConsistentHashImpl>; |
37 | |
38 | void registerFunctionJumpConsistentHash(FunctionFactory & factory) |
39 | { |
40 | factory.registerFunction<FunctionJumpConsistentHash>(); |
41 | } |
42 | |
43 | } |
44 | |
45 |