-
Notifications
You must be signed in to change notification settings - Fork 71
/
tokens.go
89 lines (74 loc) · 2.9 KB
/
tokens.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package utils
import (
"math/big"
"sort"
)
type Partitioner struct {
RingOffset *big.Int
RingRange *big.Int
}
var one = newBigInt(1)
var Murmur3Partitioner = Partitioner{
RingOffset: new(big.Int).Lsh(newBigInt(-1), 63), // -1<<63
RingRange: new(big.Int).Lsh(one, 64), // 1<<64
}
var RandomPartitioner = Partitioner{
RingOffset: new(big.Int), // 0
RingRange: new(big.Int).Lsh(one, 127), // 1<<127
}
// ComputeTokens takes a list of numbers indicating the number of nodes in each datacenter, and returns a recommended
// list of tokens for the given partitioner (one token per node, grouped by datacenter).
func ComputeTokens(dcCounts []int, partitioner Partitioner) [][]string {
dcOffset := computeDcOffset(dcCounts, partitioner)
tokensPerDc := make([][]string, len(dcCounts))
for dc, dcCount := range dcCounts {
start := new(big.Int).Mul(dcOffset, newBigInt(dc))
increment := new(big.Int).Div(partitioner.RingRange, newBigInt(dcCount))
tokens := make([]*big.Int, dcCount)
for i := 0; i < dcCount; i++ {
// token := i*increment + start + ringOffset
token := newBigInt(i)
token = token.Mul(token, increment)
token = token.Add(token, start)
token = token.Add(token, partitioner.RingOffset)
if token.Cmp(partitioner.RingOffset) < 0 {
token = token.Add(token, partitioner.RingRange)
}
tokens[i] = token
}
sort.Slice(tokens, func(i, j int) bool { return tokens[i].Cmp(tokens[j]) < 0 })
tokensPerDc[dc] = make([]string, len(tokens))
for i, token := range tokens {
tokensPerDc[dc][i] = token.String()
}
}
return tokensPerDc
}
// computeDcOffset calculates an offset to spread the starting point of each datacenter: our strategy is to start each
// DC from a "zero" point, and distribute its tokens evenly across the ring; however nodes cannot share tokens, so the
// "zeros" must be slightly apart.
func computeDcOffset(dcCounts []int, partitioner Partitioner) *big.Int {
maxDcCount := 0
for _, dcCount := range dcCounts {
if dcCount > maxDcCount {
maxDcCount = dcCount
}
}
// Ensure that we preserve the original order, i.e. the offset does not push us past the next token of the previous
// DC. For example, if there are 3 DCs with 4 nodes each, and we picture the ring as a 360° circle, the first two
// tokens of DC1 would be at 0° and 90°. So the next two starting points must be between 0 and 90.
// 360 / (3*4*2) gets us there.
divisor := len(dcCounts) * maxDcCount * 2
// Copied verbatim from the DSE code that this is adapted from. The intent is not clear (it looks like this will
// almost always kick in, so the previous computation is irrelevant). But we keep it as-is to be able to compare
// results.
const minDivisor = 235
if divisor < minDivisor {
divisor = minDivisor
}
result := new(big.Int).Neg(partitioner.RingRange)
return result.Div(result, newBigInt(divisor))
}
func newBigInt(i int) *big.Int {
return big.NewInt(int64(i))
}