Line data Source code
1 : //! See docs/rfcs/031-sharding-static.md for an overview of sharding.
2 : //!
3 : //! This module contains a variety of types used to represent the concept of sharding
4 : //! a Neon tenant across multiple physical shards. Since there are quite a few of these,
5 : //! we provide an summary here.
6 : //!
7 : //! Types used to describe shards:
8 : //! - [`ShardCount`] describes how many shards make up a tenant, plus the magic `unsharded` value
9 : //! which identifies a tenant which is not shard-aware. This means its storage paths do not include
10 : //! a shard suffix.
11 : //! - [`ShardNumber`] is simply the zero-based index of a shard within a tenant.
12 : //! - [`ShardIndex`] is the 2-tuple of `ShardCount` and `ShardNumber`, it's just like a `TenantShardId`
13 : //! without the tenant ID. This is useful for things that are implicitly scoped to a particular
14 : //! tenant, such as layer files.
15 : //! - [`ShardIdentity`]` is the full description of a particular shard's parameters, in sufficient
16 : //! detail to convert a [`Key`] to a [`ShardNumber`] when deciding where to write/read.
17 : //! - The [`ShardSlug`] is a terse formatter for ShardCount and ShardNumber, written as
18 : //! four hex digits. An unsharded tenant is `0000`.
19 : //! - [`TenantShardId`] is the unique ID of a particular shard within a particular tenant
20 : //!
21 : //! Types used to describe the parameters for data distribution in a sharded tenant:
22 : //! - [`ShardStripeSize`] controls how long contiguous runs of [`Key`]s (stripes) are when distributed across
23 : //! multiple shards. Its value is given in 8kiB pages.
24 : //! - [`ShardLayout`] describes the data distribution scheme, and at time of writing is
25 : //! always zero: this is provided for future upgrades that might introduce different
26 : //! data distribution schemes.
27 : //!
28 : //! Examples:
29 : //! - A legacy unsharded tenant has one shard with ShardCount(0), ShardNumber(0), and its slug is 0000
30 : //! - A single sharded tenant has one shard with ShardCount(1), ShardNumber(0), and its slug is 0001
31 : //! - In a tenant with 4 shards, each shard has ShardCount(N), ShardNumber(i) where i in 0..N-1 (inclusive),
32 : //! and their slugs are 0004, 0104, 0204, and 0304.
33 :
34 : use std::hash::{Hash, Hasher};
35 :
36 : #[doc(inline)]
37 : pub use ::utils::shard::*;
38 : use postgres_ffi_types::forknum::INIT_FORKNUM;
39 : use serde::{Deserialize, Serialize};
40 : use utils::critical;
41 :
42 : use crate::key::Key;
43 : use crate::models::ShardParameters;
44 :
45 : /// The ShardIdentity contains enough information to map a [`Key`] to a [`ShardNumber`],
46 : /// and to check whether that [`ShardNumber`] is the same as the current shard.
47 0 : #[derive(Clone, Copy, Serialize, Deserialize, Eq, PartialEq, Debug)]
48 : pub struct ShardIdentity {
49 : pub number: ShardNumber,
50 : pub count: ShardCount,
51 : pub stripe_size: ShardStripeSize,
52 : layout: ShardLayout,
53 : }
54 :
55 : /// Hash implementation
56 : ///
57 : /// The stripe size cannot change dynamically, so it can be ignored for efficiency reasons.
58 : impl Hash for ShardIdentity {
59 148146 : fn hash<H: Hasher>(&self, state: &mut H) {
60 : let ShardIdentity {
61 148146 : number,
62 148146 : count,
63 : stripe_size: _,
64 : layout: _,
65 148146 : } = self;
66 :
67 148146 : number.0.hash(state);
68 148146 : count.0.hash(state);
69 0 : }
70 : }
71 :
72 : /// Stripe size in number of pages
73 0 : #[derive(Clone, Copy, Serialize, Deserialize, Eq, PartialEq, Debug)]
74 : pub struct ShardStripeSize(pub u32);
75 :
76 : impl Default for ShardStripeSize {
77 10 : fn default() -> Self {
78 10 : DEFAULT_STRIPE_SIZE
79 10 : }
80 : }
81 :
82 : impl std::fmt::Display for ShardStripeSize {
83 0 : fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
84 0 : self.0.fmt(f)
85 0 : }
86 : }
87 :
88 : /// Layout version: for future upgrades where we might change how the key->shard mapping works
89 0 : #[derive(Clone, Copy, Serialize, Deserialize, Eq, PartialEq, Hash, Debug)]
90 : pub struct ShardLayout(u8);
91 :
92 : const LAYOUT_V1: ShardLayout = ShardLayout(1);
93 : /// ShardIdentity uses a magic layout value to indicate if it is unusable
94 : const LAYOUT_BROKEN: ShardLayout = ShardLayout(255);
95 :
96 : /// The default stripe size in pages. 16 MiB divided by 8 kiB page size.
97 : ///
98 : /// A lower stripe size distributes ingest load better across shards, but reduces IO amortization.
99 : /// 16 MiB appears to be a reasonable balance: <https://github.com/neondatabase/neon/pull/10510>.
100 : pub const DEFAULT_STRIPE_SIZE: ShardStripeSize = ShardStripeSize(16 * 1024 / 8);
101 :
102 : #[derive(thiserror::Error, Debug, PartialEq, Eq)]
103 : pub enum ShardConfigError {
104 : #[error("Invalid shard count")]
105 : InvalidCount,
106 : #[error("Invalid shard number")]
107 : InvalidNumber,
108 : #[error("Invalid stripe size")]
109 : InvalidStripeSize,
110 : }
111 :
112 : impl ShardIdentity {
113 : /// An identity with number=0 count=0 is a "none" identity, which represents legacy
114 : /// tenants. Modern single-shard tenants should not use this: they should
115 : /// have number=0 count=1.
116 646 : pub const fn unsharded() -> Self {
117 646 : Self {
118 646 : number: ShardNumber(0),
119 646 : count: ShardCount(0),
120 646 : layout: LAYOUT_V1,
121 646 : stripe_size: DEFAULT_STRIPE_SIZE,
122 646 : }
123 646 : }
124 :
125 : /// An unsharded identity with the given stripe size (if non-zero). This is typically used to
126 : /// carry over a stripe size for an unsharded tenant from persistent storage.
127 0 : pub fn unsharded_with_stripe_size(stripe_size: ShardStripeSize) -> Self {
128 0 : let mut shard_identity = Self::unsharded();
129 0 : if stripe_size.0 > 0 {
130 0 : shard_identity.stripe_size = stripe_size;
131 0 : }
132 0 : shard_identity
133 0 : }
134 :
135 : /// A broken instance of this type is only used for `TenantState::Broken` tenants,
136 : /// which are constructed in code paths that don't have access to proper configuration.
137 : ///
138 : /// A ShardIdentity in this state may not be used for anything, and should not be persisted.
139 : /// Enforcement is via assertions, to avoid making our interface fallible for this
140 : /// edge case: it is the Tenant's responsibility to avoid trying to do any I/O when in a broken
141 : /// state, and by extension to avoid trying to do any page->shard resolution.
142 0 : pub fn broken(number: ShardNumber, count: ShardCount) -> Self {
143 0 : Self {
144 0 : number,
145 0 : count,
146 0 : layout: LAYOUT_BROKEN,
147 0 : stripe_size: DEFAULT_STRIPE_SIZE,
148 0 : }
149 0 : }
150 :
151 : /// The "unsharded" value is distinct from simply having a single shard: it represents
152 : /// a tenant which is not shard-aware at all, and whose storage paths will not include
153 : /// a shard suffix.
154 191 : pub fn is_unsharded(&self) -> bool {
155 191 : self.number == ShardNumber(0) && self.count == ShardCount(0)
156 191 : }
157 :
158 : /// Count must be nonzero, and number must be < count. To construct
159 : /// the legacy case (count==0), use Self::unsharded instead.
160 13358 : pub fn new(
161 13358 : number: ShardNumber,
162 13358 : count: ShardCount,
163 13358 : stripe_size: ShardStripeSize,
164 13358 : ) -> Result<Self, ShardConfigError> {
165 13358 : if count.0 == 0 {
166 1 : Err(ShardConfigError::InvalidCount)
167 13357 : } else if number.0 > count.0 - 1 {
168 3 : Err(ShardConfigError::InvalidNumber)
169 13354 : } else if stripe_size.0 == 0 {
170 1 : Err(ShardConfigError::InvalidStripeSize)
171 : } else {
172 13353 : Ok(Self {
173 13353 : number,
174 13353 : count,
175 13353 : layout: LAYOUT_V1,
176 13353 : stripe_size,
177 13353 : })
178 : }
179 13358 : }
180 :
181 : /// For use when creating ShardIdentity instances for new shards, where a creation request
182 : /// specifies the ShardParameters that apply to all shards.
183 122 : pub fn from_params(number: ShardNumber, params: ShardParameters) -> Self {
184 122 : Self {
185 122 : number,
186 122 : count: params.count,
187 122 : layout: LAYOUT_V1,
188 122 : stripe_size: params.stripe_size,
189 122 : }
190 122 : }
191 :
192 : /// Asserts that the given shard identities are equal. Changes to shard parameters will likely
193 : /// result in data corruption.
194 0 : pub fn assert_equal(&self, other: ShardIdentity) {
195 0 : if self != &other {
196 : // TODO: for now, we're conservative and just log errors in production. Turn this into a
197 : // real assertion when we're confident it doesn't misfire, and also reject requests that
198 : // attempt to change it with an error response.
199 0 : critical!("shard identity mismatch: {self:?} != {other:?}");
200 0 : }
201 0 : }
202 :
203 2731458 : fn is_broken(&self) -> bool {
204 2731458 : self.layout == LAYOUT_BROKEN
205 2731458 : }
206 :
207 1542 : pub fn get_shard_number(&self, key: &Key) -> ShardNumber {
208 1542 : assert!(!self.is_broken());
209 1542 : key_to_shard_number(self.count, self.stripe_size, key)
210 1542 : }
211 :
212 : /// Return true if the key is stored only on this shard. This does not include
213 : /// global keys, see is_key_global().
214 : ///
215 : /// Shards must ingest _at least_ keys which return true from this check.
216 2729916 : pub fn is_key_local(&self, key: &Key) -> bool {
217 2729916 : assert!(!self.is_broken());
218 2729916 : if self.count < ShardCount(2) || (key_is_shard0(key) && self.number == ShardNumber(0)) {
219 2693817 : true
220 : } else {
221 36099 : key_to_shard_number(self.count, self.stripe_size, key) == self.number
222 : }
223 2729916 : }
224 :
225 : /// Return true if the key should be stored on all shards, not just one.
226 36192 : pub fn is_key_global(&self, key: &Key) -> bool {
227 36192 : if key.is_slru_block_key()
228 36192 : || key.is_slru_segment_size_key()
229 36192 : || key.is_aux_file_key()
230 36192 : || key.is_slru_dir_key()
231 : {
232 : // Special keys that are only stored on shard 0
233 24 : false
234 36168 : } else if key.is_rel_block_key() {
235 : // Ordinary relation blocks are distributed across shards
236 36086 : false
237 82 : } else if key.is_rel_size_key() {
238 : // All shards maintain rel size keys (although only shard 0 is responsible for
239 : // keeping it strictly accurate, other shards just reflect the highest block they've ingested)
240 5 : true
241 : } else {
242 : // For everything else, we assume it must be kept everywhere, because ingest code
243 : // might assume this -- this covers functionality where the ingest code has
244 : // not (yet) been made fully shard aware.
245 77 : true
246 : }
247 36192 : }
248 :
249 : /// Return true if the key should be discarded if found in this shard's
250 : /// data store, e.g. during compaction after a split.
251 : ///
252 : /// Shards _may_ drop keys which return false here, but are not obliged to.
253 1414884 : pub fn is_key_disposable(&self, key: &Key) -> bool {
254 1414884 : if self.count < ShardCount(2) {
255 : // Fast path: unsharded tenant doesn't dispose of anything
256 1378704 : return false;
257 36180 : }
258 :
259 36180 : if self.is_key_global(key) {
260 70 : false
261 : } else {
262 36110 : !self.is_key_local(key)
263 : }
264 1414884 : }
265 :
266 : /// Obtains the shard number and count combined into a `ShardIndex`.
267 189 : pub fn shard_index(&self) -> ShardIndex {
268 189 : ShardIndex {
269 189 : shard_count: self.count,
270 189 : shard_number: self.number,
271 189 : }
272 189 : }
273 :
274 4 : pub fn shard_slug(&self) -> String {
275 4 : if self.count > ShardCount(0) {
276 4 : format!("-{:02x}{:02x}", self.number.0, self.count.0)
277 : } else {
278 0 : String::new()
279 : }
280 4 : }
281 :
282 : /// Convenience for checking if this identity is the 0th shard in a tenant,
283 : /// for special cases on shard 0 such as ingesting relation sizes.
284 1526 : pub fn is_shard_zero(&self) -> bool {
285 1526 : self.number == ShardNumber(0)
286 1526 : }
287 : }
288 :
289 : /// Whether this key is always held on shard 0 (e.g. shard 0 holds all SLRU keys
290 : /// in order to be able to serve basebackup requests without peer communication).
291 72248 : fn key_is_shard0(key: &Key) -> bool {
292 : // To decide what to shard out to shards >0, we apply a simple rule that only
293 : // relation pages are distributed to shards other than shard zero. Everything else gets
294 : // stored on shard 0. This guarantees that shard 0 can independently serve basebackup
295 : // requests, and any request other than those for particular blocks in relations.
296 : //
297 : // The only exception to this rule is "initfork" data -- this relates to postgres's UNLOGGED table
298 : // type. These are special relations, usually with only 0 or 1 blocks, and we store them on shard 0
299 : // because they must be included in basebackups.
300 72248 : let is_initfork = key.field5 == INIT_FORKNUM;
301 :
302 72248 : !key.is_rel_block_key() || is_initfork
303 72248 : }
304 :
305 : /// Provide the same result as the function in postgres `hashfn.h` with the same name
306 72195 : fn murmurhash32(mut h: u32) -> u32 {
307 72195 : h ^= h >> 16;
308 72195 : h = h.wrapping_mul(0x85ebca6b);
309 72195 : h ^= h >> 13;
310 72195 : h = h.wrapping_mul(0xc2b2ae35);
311 72195 : h ^= h >> 16;
312 72195 : h
313 72195 : }
314 :
315 : /// Provide the same result as the function in postgres `hashfn.h` with the same name
316 36098 : fn hash_combine(mut a: u32, mut b: u32) -> u32 {
317 36098 : b = b.wrapping_add(0x9e3779b9);
318 36098 : b = b.wrapping_add(a << 6);
319 36098 : b = b.wrapping_add(a >> 2);
320 :
321 36098 : a ^= b;
322 36098 : a
323 36098 : }
324 :
325 : /// Where a Key is to be distributed across shards, select the shard. This function
326 : /// does not account for keys that should be broadcast across shards.
327 : ///
328 : /// The hashing in this function must exactly match what we do in postgres smgr
329 : /// code. The resulting distribution of pages is intended to preserve locality within
330 : /// `stripe_size` ranges of contiguous block numbers in the same relation, while otherwise
331 : /// distributing data pseudo-randomly.
332 : ///
333 : /// The mapping of key to shard is not stable across changes to ShardCount: this is intentional
334 : /// and will be handled at higher levels when shards are split.
335 37642 : pub fn key_to_shard_number(
336 37642 : count: ShardCount,
337 37642 : stripe_size: ShardStripeSize,
338 37642 : key: &Key,
339 37642 : ) -> ShardNumber {
340 : // Fast path for un-sharded tenants or broadcast keys
341 37642 : if count < ShardCount(2) || key_is_shard0(key) {
342 1545 : return ShardNumber(0);
343 36097 : }
344 :
345 : // relNode
346 36097 : let mut hash = murmurhash32(key.field4);
347 : // blockNum/stripe size
348 36097 : hash = hash_combine(hash, murmurhash32(key.field6 / stripe_size.0));
349 :
350 36097 : ShardNumber((hash % count.0 as u32) as u8)
351 37642 : }
352 :
353 : /// For debugging, while not exposing the internals.
354 : #[derive(Debug)]
355 : #[allow(unused)] // used by debug formatting by pagectl
356 : struct KeyShardingInfo {
357 : shard0: bool,
358 : shard_number: ShardNumber,
359 : }
360 :
361 0 : pub fn describe(
362 0 : key: &Key,
363 0 : shard_count: ShardCount,
364 0 : stripe_size: ShardStripeSize,
365 0 : ) -> impl std::fmt::Debug {
366 0 : KeyShardingInfo {
367 0 : shard0: key_is_shard0(key),
368 0 : shard_number: key_to_shard_number(shard_count, stripe_size, key),
369 0 : }
370 0 : }
371 :
372 : #[cfg(test)]
373 : mod tests {
374 : use std::str::FromStr;
375 :
376 : use utils::Hex;
377 : use utils::id::TenantId;
378 :
379 : use super::*;
380 :
381 : const EXAMPLE_TENANT_ID: &str = "1f359dd625e519a1a4e8d7509690f6fc";
382 :
383 : #[test]
384 1 : fn tenant_shard_id_string() -> Result<(), hex::FromHexError> {
385 1 : let example = TenantShardId {
386 1 : tenant_id: TenantId::from_str(EXAMPLE_TENANT_ID).unwrap(),
387 1 : shard_count: ShardCount(10),
388 1 : shard_number: ShardNumber(7),
389 1 : };
390 :
391 1 : let encoded = format!("{example}");
392 :
393 1 : let expected = format!("{EXAMPLE_TENANT_ID}-070a");
394 1 : assert_eq!(&encoded, &expected);
395 :
396 1 : let decoded = TenantShardId::from_str(&encoded)?;
397 :
398 1 : assert_eq!(example, decoded);
399 :
400 1 : Ok(())
401 1 : }
402 :
403 : #[test]
404 1 : fn tenant_shard_id_binary() -> Result<(), hex::FromHexError> {
405 1 : let example = TenantShardId {
406 1 : tenant_id: TenantId::from_str(EXAMPLE_TENANT_ID).unwrap(),
407 1 : shard_count: ShardCount(10),
408 1 : shard_number: ShardNumber(7),
409 1 : };
410 :
411 1 : let encoded = bincode::serialize(&example).unwrap();
412 1 : let expected: [u8; 18] = [
413 1 : 0x1f, 0x35, 0x9d, 0xd6, 0x25, 0xe5, 0x19, 0xa1, 0xa4, 0xe8, 0xd7, 0x50, 0x96, 0x90,
414 1 : 0xf6, 0xfc, 0x07, 0x0a,
415 1 : ];
416 1 : assert_eq!(Hex(&encoded), Hex(&expected));
417 :
418 1 : let decoded = bincode::deserialize(&encoded).unwrap();
419 :
420 1 : assert_eq!(example, decoded);
421 :
422 1 : Ok(())
423 1 : }
424 :
425 : #[test]
426 1 : fn tenant_shard_id_backward_compat() -> Result<(), hex::FromHexError> {
427 : // Test that TenantShardId can decode a TenantId in human
428 : // readable form
429 1 : let example = TenantId::from_str(EXAMPLE_TENANT_ID).unwrap();
430 1 : let encoded = format!("{example}");
431 :
432 1 : assert_eq!(&encoded, EXAMPLE_TENANT_ID);
433 :
434 1 : let decoded = TenantShardId::from_str(&encoded)?;
435 :
436 1 : assert_eq!(example, decoded.tenant_id);
437 1 : assert_eq!(decoded.shard_count, ShardCount(0));
438 1 : assert_eq!(decoded.shard_number, ShardNumber(0));
439 :
440 1 : Ok(())
441 1 : }
442 :
443 : #[test]
444 1 : fn tenant_shard_id_forward_compat() -> Result<(), hex::FromHexError> {
445 : // Test that a legacy TenantShardId encodes into a form that
446 : // can be decoded as TenantId
447 1 : let example_tenant_id = TenantId::from_str(EXAMPLE_TENANT_ID).unwrap();
448 1 : let example = TenantShardId::unsharded(example_tenant_id);
449 1 : let encoded = format!("{example}");
450 :
451 1 : assert_eq!(&encoded, EXAMPLE_TENANT_ID);
452 :
453 1 : let decoded = TenantId::from_str(&encoded)?;
454 :
455 1 : assert_eq!(example_tenant_id, decoded);
456 :
457 1 : Ok(())
458 1 : }
459 :
460 : #[test]
461 1 : fn tenant_shard_id_legacy_binary() -> Result<(), hex::FromHexError> {
462 : // Unlike in human readable encoding, binary encoding does not
463 : // do any special handling of legacy unsharded TenantIds: this test
464 : // is equivalent to the main test for binary encoding, just verifying
465 : // that the same behavior applies when we have used `unsharded()` to
466 : // construct a TenantShardId.
467 1 : let example = TenantShardId::unsharded(TenantId::from_str(EXAMPLE_TENANT_ID).unwrap());
468 1 : let encoded = bincode::serialize(&example).unwrap();
469 :
470 1 : let expected: [u8; 18] = [
471 1 : 0x1f, 0x35, 0x9d, 0xd6, 0x25, 0xe5, 0x19, 0xa1, 0xa4, 0xe8, 0xd7, 0x50, 0x96, 0x90,
472 1 : 0xf6, 0xfc, 0x00, 0x00,
473 1 : ];
474 1 : assert_eq!(Hex(&encoded), Hex(&expected));
475 :
476 1 : let decoded = bincode::deserialize::<TenantShardId>(&encoded).unwrap();
477 1 : assert_eq!(example, decoded);
478 :
479 1 : Ok(())
480 1 : }
481 :
482 : #[test]
483 1 : fn shard_identity_validation() -> Result<(), ShardConfigError> {
484 : // Happy cases
485 1 : ShardIdentity::new(ShardNumber(0), ShardCount(1), DEFAULT_STRIPE_SIZE)?;
486 1 : ShardIdentity::new(ShardNumber(0), ShardCount(1), ShardStripeSize(1))?;
487 1 : ShardIdentity::new(ShardNumber(254), ShardCount(255), ShardStripeSize(1))?;
488 :
489 1 : assert_eq!(
490 1 : ShardIdentity::new(ShardNumber(0), ShardCount(0), DEFAULT_STRIPE_SIZE),
491 : Err(ShardConfigError::InvalidCount)
492 : );
493 1 : assert_eq!(
494 1 : ShardIdentity::new(ShardNumber(10), ShardCount(10), DEFAULT_STRIPE_SIZE),
495 : Err(ShardConfigError::InvalidNumber)
496 : );
497 1 : assert_eq!(
498 1 : ShardIdentity::new(ShardNumber(11), ShardCount(10), DEFAULT_STRIPE_SIZE),
499 : Err(ShardConfigError::InvalidNumber)
500 : );
501 1 : assert_eq!(
502 1 : ShardIdentity::new(ShardNumber(255), ShardCount(255), DEFAULT_STRIPE_SIZE),
503 : Err(ShardConfigError::InvalidNumber)
504 : );
505 1 : assert_eq!(
506 1 : ShardIdentity::new(ShardNumber(0), ShardCount(1), ShardStripeSize(0)),
507 : Err(ShardConfigError::InvalidStripeSize)
508 : );
509 :
510 1 : Ok(())
511 1 : }
512 :
513 : #[test]
514 1 : fn shard_index_human_encoding() -> Result<(), hex::FromHexError> {
515 1 : let example = ShardIndex {
516 1 : shard_number: ShardNumber(13),
517 1 : shard_count: ShardCount(17),
518 1 : };
519 1 : let expected: String = "0d11".to_string();
520 1 : let encoded = format!("{example}");
521 1 : assert_eq!(&encoded, &expected);
522 :
523 1 : let decoded = ShardIndex::from_str(&encoded)?;
524 1 : assert_eq!(example, decoded);
525 1 : Ok(())
526 1 : }
527 :
528 : #[test]
529 1 : fn shard_index_binary_encoding() -> Result<(), hex::FromHexError> {
530 1 : let example = ShardIndex {
531 1 : shard_number: ShardNumber(13),
532 1 : shard_count: ShardCount(17),
533 1 : };
534 1 : let expected: [u8; 2] = [0x0d, 0x11];
535 :
536 1 : let encoded = bincode::serialize(&example).unwrap();
537 1 : assert_eq!(Hex(&encoded), Hex(&expected));
538 1 : let decoded = bincode::deserialize(&encoded).unwrap();
539 1 : assert_eq!(example, decoded);
540 :
541 1 : Ok(())
542 1 : }
543 :
544 : // These are only smoke tests to spot check that our implementation doesn't
545 : // deviate from a few examples values: not aiming to validate the overall
546 : // hashing algorithm.
547 : #[test]
548 1 : fn murmur_hash() {
549 1 : assert_eq!(murmurhash32(0), 0);
550 :
551 1 : assert_eq!(hash_combine(0xb1ff3b40, 0), 0xfb7923c9);
552 1 : }
553 :
554 : #[test]
555 1 : fn shard_mapping() {
556 1 : let key = Key {
557 1 : field1: 0x00,
558 1 : field2: 0x67f,
559 1 : field3: 0x5,
560 1 : field4: 0x400c,
561 1 : field5: 0x00,
562 1 : field6: 0x7d06,
563 1 : };
564 :
565 1 : let shard = key_to_shard_number(ShardCount(10), ShardStripeSize(32768), &key);
566 1 : assert_eq!(shard, ShardNumber(8));
567 1 : }
568 :
569 : #[test]
570 1 : fn shard_id_split() {
571 1 : let tenant_id = TenantId::generate();
572 1 : let parent = TenantShardId::unsharded(tenant_id);
573 :
574 : // Unsharded into 2
575 1 : assert_eq!(
576 1 : parent.split(ShardCount(2)),
577 1 : vec![
578 1 : TenantShardId {
579 1 : tenant_id,
580 1 : shard_count: ShardCount(2),
581 1 : shard_number: ShardNumber(0)
582 1 : },
583 1 : TenantShardId {
584 1 : tenant_id,
585 1 : shard_count: ShardCount(2),
586 1 : shard_number: ShardNumber(1)
587 1 : }
588 : ]
589 : );
590 :
591 : // Unsharded into 4
592 1 : assert_eq!(
593 1 : parent.split(ShardCount(4)),
594 1 : vec![
595 1 : TenantShardId {
596 1 : tenant_id,
597 1 : shard_count: ShardCount(4),
598 1 : shard_number: ShardNumber(0)
599 1 : },
600 1 : TenantShardId {
601 1 : tenant_id,
602 1 : shard_count: ShardCount(4),
603 1 : shard_number: ShardNumber(1)
604 1 : },
605 1 : TenantShardId {
606 1 : tenant_id,
607 1 : shard_count: ShardCount(4),
608 1 : shard_number: ShardNumber(2)
609 1 : },
610 1 : TenantShardId {
611 1 : tenant_id,
612 1 : shard_count: ShardCount(4),
613 1 : shard_number: ShardNumber(3)
614 1 : }
615 : ]
616 : );
617 :
618 : // count=1 into 2 (check this works the same as unsharded.)
619 1 : let parent = TenantShardId {
620 1 : tenant_id,
621 1 : shard_count: ShardCount(1),
622 1 : shard_number: ShardNumber(0),
623 1 : };
624 1 : assert_eq!(
625 1 : parent.split(ShardCount(2)),
626 1 : vec![
627 1 : TenantShardId {
628 1 : tenant_id,
629 1 : shard_count: ShardCount(2),
630 1 : shard_number: ShardNumber(0)
631 1 : },
632 1 : TenantShardId {
633 1 : tenant_id,
634 1 : shard_count: ShardCount(2),
635 1 : shard_number: ShardNumber(1)
636 1 : }
637 : ]
638 : );
639 :
640 : // count=2 into count=8
641 1 : let parent = TenantShardId {
642 1 : tenant_id,
643 1 : shard_count: ShardCount(2),
644 1 : shard_number: ShardNumber(1),
645 1 : };
646 1 : assert_eq!(
647 1 : parent.split(ShardCount(8)),
648 1 : vec![
649 1 : TenantShardId {
650 1 : tenant_id,
651 1 : shard_count: ShardCount(8),
652 1 : shard_number: ShardNumber(1)
653 1 : },
654 1 : TenantShardId {
655 1 : tenant_id,
656 1 : shard_count: ShardCount(8),
657 1 : shard_number: ShardNumber(3)
658 1 : },
659 1 : TenantShardId {
660 1 : tenant_id,
661 1 : shard_count: ShardCount(8),
662 1 : shard_number: ShardNumber(5)
663 1 : },
664 1 : TenantShardId {
665 1 : tenant_id,
666 1 : shard_count: ShardCount(8),
667 1 : shard_number: ShardNumber(7)
668 1 : },
669 : ]
670 : );
671 1 : }
672 : }
|
