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

Generated by: LCOV version 2.1-beta