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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
use rand::Rng;
use std::collections::HashMap;
use std::convert::TryFrom;
use std::net::SocketAddr;
use std::num::NonZeroU16;
use thiserror::Error;
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
pub struct Node {
pub addr: SocketAddr,
}
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
pub struct Token {
pub value: i64,
}
pub type Shard = u32;
pub type ShardCount = NonZeroU16;
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ShardInfo {
pub shard: u16,
pub nr_shards: ShardCount,
pub msb_ignore: u8,
}
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct Sharder {
pub nr_shards: ShardCount,
pub msb_ignore: u8,
}
impl std::str::FromStr for Token {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Token, std::num::ParseIntError> {
Ok(Token { value: s.parse()? })
}
}
impl ShardInfo {
pub fn new(shard: u16, nr_shards: ShardCount, msb_ignore: u8) -> Self {
ShardInfo {
shard,
nr_shards,
msb_ignore,
}
}
pub fn get_sharder(&self) -> Sharder {
Sharder::new(self.nr_shards, self.msb_ignore)
}
}
impl Sharder {
pub fn new(nr_shards: ShardCount, msb_ignore: u8) -> Self {
Sharder {
nr_shards,
msb_ignore,
}
}
pub fn shard_of(&self, token: Token) -> Shard {
let mut biased_token = (token.value as u64).wrapping_add(1u64 << 63);
biased_token <<= self.msb_ignore;
(((biased_token as u128) * (self.nr_shards.get() as u128)) >> 64) as Shard
}
pub fn shard_of_source_port(&self, source_port: u16) -> Shard {
(source_port % self.nr_shards.get()) as Shard
}
pub fn draw_source_port_for_shard(&self, shard: Shard) -> u16 {
assert!(shard < self.nr_shards.get() as u32);
rand::thread_rng()
.gen_range((49152 + self.nr_shards.get() - 1)..(65535 - self.nr_shards.get() + 1))
/ self.nr_shards.get()
* self.nr_shards.get()
+ shard as u16
}
pub fn iter_source_ports_for_shard(&self, shard: Shard) -> impl Iterator<Item = u16> {
assert!(shard < self.nr_shards.get() as u32);
let starting_port = self.draw_source_port_for_shard(shard);
let first_valid_port = (49152 + self.nr_shards.get() - 1) / self.nr_shards.get()
* self.nr_shards.get()
+ shard as u16;
let before_wrap = (starting_port..=65535).step_by(self.nr_shards.get().into());
let after_wrap = (first_valid_port..starting_port).step_by(self.nr_shards.get().into());
before_wrap.chain(after_wrap)
}
}
#[derive(Error, Debug)]
pub enum ShardingError {
#[error("ShardInfo parameters missing")]
MissingShardInfoParameter,
#[error("ShardInfo parameters missing after unwraping")]
MissingUnwrapedShardInfoParameter,
#[error("ShardInfo contains an invalid number of shards (0)")]
ZeroShards,
#[error("ParseIntError encountered while getting ShardInfo")]
ParseIntError(#[from] std::num::ParseIntError),
}
impl<'a> TryFrom<&'a HashMap<String, Vec<String>>> for ShardInfo {
type Error = ShardingError;
fn try_from(options: &'a HashMap<String, Vec<String>>) -> Result<Self, Self::Error> {
let shard_entry = options.get("SCYLLA_SHARD");
let nr_shards_entry = options.get("SCYLLA_NR_SHARDS");
let msb_ignore_entry = options.get("SCYLLA_SHARDING_IGNORE_MSB");
if shard_entry.is_none() || nr_shards_entry.is_none() || msb_ignore_entry.is_none() {
return Err(ShardingError::MissingShardInfoParameter);
}
if shard_entry.unwrap().is_empty()
|| nr_shards_entry.unwrap().is_empty()
|| msb_ignore_entry.unwrap().is_empty()
{
return Err(ShardingError::MissingUnwrapedShardInfoParameter);
}
let shard = shard_entry.unwrap().first().unwrap().parse::<u16>()?;
let nr_shards = nr_shards_entry.unwrap().first().unwrap().parse::<u16>()?;
let nr_shards = ShardCount::new(nr_shards).ok_or(ShardingError::ZeroShards)?;
let msb_ignore = msb_ignore_entry.unwrap().first().unwrap().parse::<u8>()?;
Ok(ShardInfo::new(shard, nr_shards, msb_ignore))
}
}
#[cfg(test)]
mod tests {
use super::Token;
use super::{ShardCount, Sharder};
use std::collections::HashSet;
#[test]
fn test_shard_of() {
let sharder = Sharder::new(ShardCount::new(4).unwrap(), 12);
assert_eq!(
sharder.shard_of(Token {
value: -9219783007514621794
}),
3
);
assert_eq!(
sharder.shard_of(Token {
value: 9222582454147032830
}),
3
);
}
#[test]
fn test_iter_source_ports_for_shard() {
let nr_shards = 4;
let max_port_num = 65535;
let min_port_num = (49152 + nr_shards - 1) / nr_shards * nr_shards;
let sharder = Sharder::new(ShardCount::new(nr_shards).unwrap(), 12);
for shard in 0..nr_shards {
let mut lowest_port = min_port_num;
while lowest_port % nr_shards != shard {
lowest_port += 1;
}
let possible_ports_number: usize =
((max_port_num - lowest_port) / nr_shards + 1).into();
let port_iter = sharder.iter_source_ports_for_shard(shard.into());
let mut returned_ports: HashSet<u16> = HashSet::new();
for port in port_iter {
assert!(!returned_ports.contains(&port));
assert!(port % nr_shards == shard);
returned_ports.insert(port);
}
assert_eq!(returned_ports.len(), possible_ports_number);
}
}
}