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

Generated by: LCOV version 2.1-beta