LCOV - code coverage report
Current view: top level - libs/pageserver_api/src - shard.rs (source / functions) Coverage Total Hit
Test: 07bee600374ccd486c69370d0972d9035964fe68.info Lines: 93.3 % 403 376
Test Date: 2025-02-20 13:11:02 Functions: 48.3 % 58 28

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

Generated by: LCOV version 2.1-beta