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