🥮 mooncakes.io

    moonshardkit

    Deterministic shard placement, replica isolation and migration planning for MoonBit.

    consistent-hashing
    rendezvous-hashing
    sharding
    replica-placement
    migration-planning
    Download zip
    Author
    Version
    0.4.0
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    50

    No dependencies

    #MoonShardKit

    Deterministic shard placement and migration planning for MoonBit.

    MoonShardKit is a backend-neutral foundation library for caches, object stores, task queues, distributed indexes, and stateless routing systems. The same topology and key set produce the same placement on Native, JavaScript, WebAssembly, and WebAssembly-GC.

    #Features

    • Weighted consistent hashing with virtual nodes
    • Integer-score weighted Rendezvous hashing
    • Zone- and rack-aware replica placement
    • Deterministic primary and replica migration plans
    • Five-phase safe migration workflows: add, backfill, verify, cut over, clean up
    • Global wave concurrency and per-node pressure budgets
    • Migration-plan validation and blocked-key reporting
    • Capacity-admitted batch placement with per-node primary/replica budgets
    • Capacity adjustments, failure-domain exclusion, regional isolation, and resumable migration waves
    • Distribution, skew, and topology-violation reports
    • Stable JSON output and a runnable CLI
    • No network, database, service-discovery, or platform dependency

    #Install

    moon add Dz-6666/moonshardkit

    #Example

    let nodes = [
      @moonshardkit.ShardNode::new("node-a", zone="east", rack="rack-1"),
      @moonshardkit.ShardNode::new("node-b", zone="west", rack="rack-1"),
      @moonshardkit.ShardNode::new("node-c", zone="south", rack="rack-2"),
    ]

    let placement = @moonshardkit.place_key(nodes, "customer-42", 3)
    println(placement.to_json())

    placement.owners[0] is the primary owner. Remaining entries are replicas, ordered deterministically while preferring zone and rack diversity.

    #Safe Migration Workflow

    let workflow = @moonshardkit.plan_safe_migration(
      keys,
      old_nodes,
      new_nodes,
      replicas=3,
      max_actions_per_wave=64,
      max_actions_per_node=8,
    )

    assert_eq(@moonshardkit.validate_safe_migration(workflow).length(), 0)

    The planner never emits source cleanup before target creation, backfill, verification, and primary cutover. Keys without a readable source are reported in blocked_keys instead of receiving an unsafe plan. The output is a pure, deterministic control-plane plan; storage adapters execute and checkpoint it.

    #Capacity-constrained admission

    plan_capacity_placement turns placement into an admission decision for a batch. It retains deterministic weighted Rendezvous ordering and topology-aware replica preference, while never exceeding a node's primary or replica budget. Keys that cannot obtain every requested owner remain visible in rejected_keys; there is no hidden overload fallback.

    moon run cmd/scenario --target js

    The scenario models a four-region control plane with 24 tenants, three replicas, and explicit per-node limits. It prints a stable JSON audit report with accepted/rejected keys and every budgeted node load.

    For control-plane recovery, resume_safe_migration takes a durable completed- wave checkpoint and returns a re-indexed, validation-ready remaining workflow. exclude_failure_domains and isolate_regions produce offline-marked topology snapshots without mutating the source topology.

    #Verify

    moon fmt --check
moon check --deny-warn --target all
moon info && git diff --exit-code -- '*.mbti'
moon test --deny-warn --target all
moon run cmd/main --target js
moon run bench/main --target js
moon run cmd/scenario --target js

    The benchmark emits reproducible 1k/10k/100k rows containing movement ratio, load spread, migration waves, validation issues, and a stable evidence hash. Run the same command with --target native, js, wasm, or wasm-gc to compare backend output; CI executes the supported matrix.

    CI uses the executable quality gates supported by the current MoonBit CLI: moon fmt --check, moon check --deny-warn --target all, moon info plus a clean .mbti diff, and moon test --deny-warn --target all. moon fmt and moon info do not accept --deny-warn in this CLI version, so CI documents their equivalent checks rather than adding commands that always fail.

    #Documentation

    #License

    Apache-2.0.

    CapacityAdjustment

    source
    pub(all) struct CapacityAdjustment {
      node_id : String
      primary_delta : Int
      replica_delta : Int
    } derive(Eq, 
    Debug    )

    A signed update to one node's ownership budgets.

    CapacityAdjustment::new

    source
    fn CapacityAdjustment::new(node_id : String, primary_delta : Int, replica_delta : Int) -> CapacityAdjustment

    CapacityLoad

    source
    pub(all) struct CapacityLoad {
      node_id : String
      primary_keys : Int
      replica_keys : Int
      max_primary : Int
      max_replicas : Int
    } derive(Eq, 
    Debug    )

    Observed ownership and the configured budgets for one node.

    CapacityPlan

    source
    pub(all) struct CapacityPlan {
      placements : Array[KeyPlacement]
      rejected_keys : Array[String]
      loads : Array[CapacityLoad]
      replicas : Int
    } derive(Eq, 
    Debug    )

    Deterministic batch placement result with explicit admission failures.

    CapacityPlan::accepted_keys

    source
    fn CapacityPlan::accepted_keys(self : CapacityPlan) -> Int

    CapacityPlan::is_within_capacity

    source
    fn CapacityPlan::is_within_capacity(self : CapacityPlan) -> Bool

    CapacityPlan::to_json

    source
    fn CapacityPlan::to_json(self : CapacityPlan) -> String

    Encodes capacity-admitted placement evidence for control-plane logs.

    ConsistentHashRing

    source
    pub struct ConsistentHashRing {
      points : Array[RingPoint]
      eligible_nodes : Int
      seed : UInt
    }

    Immutable consistent hash ring.

    ConsistentHashRing::build

    source
    fn ConsistentHashRing::build(nodes : Array[ShardNode], seed? : UInt) -> ConsistentHashRing

    Builds a ring from active nodes.

    ConsistentHashRing::node_count

    source
    fn ConsistentHashRing::node_count(self : ConsistentHashRing) -> Int

    Returns the number of active real nodes.

    ConsistentHashRing::owner

    source
    fn ConsistentHashRing::owner(self : ConsistentHashRing, key : String) -> String?

    Returns the primary owner for a key.

    ConsistentHashRing::owners

    source
    fn ConsistentHashRing::owners(self : ConsistentHashRing, key : String, replicas : Int) -> Array[String]

    Returns distinct clockwise owners, primary first.

    ConsistentHashRing::point_count

    source
    fn ConsistentHashRing::point_count(self : ConsistentHashRing) -> Int

    Returns the number of virtual points.

    DistributionReport

    source
    pub(all) struct DistributionReport {
      keys : Int
      replicas : Int
      nodes : Array[NodeLoad]
      min_primary : Int
      max_primary : Int
      spread : Int
      incomplete_placements : Int
      zone_violations : Int
      rack_violations : Int
    } derive(Eq, 
    Debug    )

    Distribution quality summary.

    DistributionReport::to_json

    source
    fn DistributionReport::to_json(self : DistributionReport) -> String

    Encodes distribution evidence.

    KeyPlacement

    source
    pub(all) struct KeyPlacement {
      key : String
      owners : Array[String]
      complete : Bool
      message : String
    } derive(Eq, 
    Debug    )

    One key and its ordered owner list.

    KeyPlacement::to_json

    source
    fn KeyPlacement::to_json(self : KeyPlacement) -> String

    Encodes one placement.

    MigrationAction

    source
    pub(all) struct MigrationAction {
      key : String
      phase : MigrationPhase
      from_node : String?
      to_node : String?
    } derive(Eq, 
    Debug    )

    One idempotent operation in a safe migration workflow.

    MigrationCheckpoint

    source
    pub(all) struct MigrationCheckpoint {
      completed_waves : Int
    } derive(Eq, 
    Debug    )

    Durable progress marker for resuming a safe migration by wave.

    MigrationCheckpoint::new

    source
    fn MigrationCheckpoint::new(completed_waves : Int) -> MigrationCheckpoint

    MigrationPhase

    source
    pub(all) enum MigrationPhase {
      AddTarget
      Backfill
      Verify
      SwitchPrimary
      RemoveSource
    } derive(Eq, 
    Debug    )

    Ordered safety phase for an executable shard migration.

    MigrationPlan

    source
    pub(all) struct MigrationPlan {
      keys : Int
      moved_keys : Int
      unchanged_keys : Int
      moves : Array[ShardMove]
    } derive(Eq, 
    Debug    )

    Aggregate migration evidence.

    MigrationPlan::to_json

    source
    fn MigrationPlan::to_json(self : MigrationPlan) -> String

    Encodes one migration plan.

    MigrationWave

    source
    pub(all) struct MigrationWave {
      index : Int
      phase : MigrationPhase
      actions : Array[MigrationAction]
    } derive(Eq, 
    Debug    )

    A deterministic group of actions that may execute concurrently.

    MoveKind

    source
    pub(all) enum MoveKind {
      PrimaryChanged
      ReplicaAdded
      ReplicaRemoved
    } derive(Eq, 
    Debug    )

    Why an ownership assignment changed.

    NodeCapacity

    source
    pub(all) struct NodeCapacity {
      node_id : String
      max_primary : Int
      max_replicas : Int
    } derive(Eq, 
    Debug    )

    Hard ownership budgets for one node during a batch placement run. A missing node from the capacity list is treated as unbounded.

    NodeCapacity::new

    source
    fn NodeCapacity::new(node_id : String, max_primary : Int, max_replicas : Int) -> NodeCapacity

    NodeLoad

    source
    pub(all) struct NodeLoad {
      node_id : String
      primary_keys : Int
      replica_keys : Int
    } derive(Eq, 
    Debug    )

    Per-node ownership count.

    NodeStatus

    source
    pub(all) enum NodeStatus {
      Active
      Draining
      Offline
    } derive(Eq, 
    Debug    )

    Administrative state used by placement algorithms.

    PlacementAlgorithm

    source
    pub(all) enum PlacementAlgorithm {
      ConsistentRing
      Rendezvous
      TopologyAware
    } derive(Eq, 
    Debug    )

    Built-in owner-selection strategy.

    RingPoint

    source
    type RingPoint

    One virtual point on a consistent hash ring.

    SafeMigrationPlan

    source
    pub(all) struct SafeMigrationPlan {
      keys : Int
      migrating_keys : Int
      blocked_keys : Array[String]
      actions : Array[MigrationAction]
      waves : Array[MigrationWave]
      max_actions_per_wave : Int
      max_actions_per_node : Int
    } derive(Eq, 
    Debug    )

    Executable migration workflow with explicit safety and pressure budgets.

    SafeMigrationPlan::to_json

    source
    fn SafeMigrationPlan::to_json(self : SafeMigrationPlan) -> String

    Encodes a safe migration workflow for audit logs and control planes.

    ShardMove

    source
    pub(all) struct ShardMove {
      key : String
      from_node : String?
      to_node : String?
      kind : MoveKind
    } derive(Eq, 
    Debug    )

    One planned ownership change between topology snapshots.

    ShardNode

    source
    pub(all) struct ShardNode {
      id : String
      weight : Int
      virtual_nodes : Int
      zone : String
      rack : String
      status : NodeStatus
    } derive(Eq, 
    Debug    )

    A storage or compute node participating in shard placement.

    ShardNode::is_eligible

    source
    fn ShardNode::is_eligible(self : ShardNode) -> Bool

    Returns whether the node can receive new ownership.

    ShardNode::new

    source
    fn ShardNode::new(id : String, zone? : String, rack? : String, weight? : Int, virtual_nodes? : Int) -> ShardNode

    Creates a normalized active node.

    ShardNode::with_status

    source
    fn ShardNode::with_status(self : ShardNode, status : NodeStatus) -> ShardNode

    Returns a copy with a new administrative state.

    TopologyIssue

    source
    pub(all) enum TopologyIssue {
      EmptyNodeId(Int)
      DuplicateNodeId(String)
      EmptyZone(String)
      EmptyRack(String)
    } derive(Eq, 
    Debug    )

    Structural problem in a topology snapshot.

    adjust_capacities

    source
    fn adjust_capacities(capacities : Array[NodeCapacity], adjustments : Array[CapacityAdjustment]) -> Array[NodeCapacity]

    Applies capacity changes without mutating the caller's policy array. Unknown adjustment targets are ignored so stale control-plane updates are safe to replay.

    analyze_distribution

    source
    fn analyze_distribution(keys : Array[String], nodes : Array[ShardNode], replicas? : Int, salt? : String) -> DistributionReport

    Measures placement balance and topology constraint outcomes.

    exclude_failure_domains

    source
    fn exclude_failure_domains(nodes : Array[ShardNode], unavailable_zones : Array[String], unavailable_racks : Array[String]) -> Array[ShardNode]

    Marks every node in an unavailable zone or rack as offline.

    isolate_regions

    source
    fn isolate_regions(nodes : Array[ShardNode], allowed_zones : Array[String]) -> Array[ShardNode]

    Restricts new placement to an explicit regional allow-list.

    json_escape

    source
    fn json_escape(value : String) -> String

    Escapes a string for JSON output.

    migration_phase_name

    source
    fn migration_phase_name(phase : MigrationPhase) -> String

    Returns the stable machine-readable name of a workflow phase.

    move_kind_name

    source
    fn move_kind_name(kind : MoveKind) -> String

    Returns a stable name for one migration action.

    movement_ratio

    source
    fn movement_ratio(plan : MigrationPlan) -> Double

    Returns the fraction of keys whose ordered owner set changed.

    place_key

    source
    fn place_key(nodes : Array[ShardNode], key : String, replicas : Int, algorithm? : PlacementAlgorithm, seed? : UInt, salt? : String) -> KeyPlacement

    Places one key through a selected built-in algorithm.

    place_keys

    source
    fn place_keys(nodes : Array[ShardNode], keys : Array[String], replicas : Int, algorithm? : PlacementAlgorithm, seed? : UInt, salt? : String) -> Array[KeyPlacement]

    Places a deterministic key batch with one algorithm.

    place_replicas

    source
    fn place_replicas(nodes : Array[ShardNode], key : String, replicas : Int, salt? : String) -> KeyPlacement

    Places ordered replicas while preferring zone and rack diversity.

    placement_score

    source
    fn placement_score(key : String, node_id : String, salt : String) -> UInt

    Deterministically mixes a key, node identity, and namespace salt.

    plan_capacity_placement

    source
    fn plan_capacity_placement(keys : Array[String], nodes : Array[ShardNode], capacities : Array[NodeCapacity], replicas : Int, salt? : String) -> CapacityPlan

    Plans a capacity-admitted, topology-aware placement for a key batch.

    Candidate order is deterministic weighted Rendezvous order. The planner never exceeds a configured budget: keys that cannot receive every requested owner remain in rejected_keys with an incomplete placement record.

    plan_migration

    source
    fn plan_migration(keys : Array[String], before : Array[ShardNode], after : Array[ShardNode], replicas? : Int, salt? : String) -> MigrationPlan

    Compares two topology snapshots and emits deterministic ownership changes.

    plan_safe_migration

    source
    fn plan_safe_migration(keys : Array[String], before : Array[ShardNode], after : Array[ShardNode], replicas? : Int, max_actions_per_wave? : Int, max_actions_per_node? : Int, salt? : String) -> SafeMigrationPlan

    Builds a five-phase, budgeted migration workflow.

    All target replicas are added, backfilled, and verified before any primary switch or source cleanup is emitted. Keys without a readable source are reported as blocked instead of receiving unsafe actions.

    rendezvous_node_score

    source
    fn rendezvous_node_score(key : String, node : ShardNode, salt? : String) -> UInt

    Computes a deterministic weighted score for one node.

    Integer tickets avoid backend-dependent floating-point logarithms. A node with weight N receives N independent score opportunities and keeps its best.

    rendezvous_owner

    source
    fn rendezvous_owner(nodes : Array[ShardNode], key : String, salt? : String) -> String?

    Returns the highest-ranked active node.

    rendezvous_owners

    source
    fn rendezvous_owners(nodes : Array[ShardNode], key : String, replicas : Int, salt? : String) -> Array[String]

    Ranks all active nodes using weighted highest-random-weight placement.

    resume_safe_migration

    source
    fn resume_safe_migration(plan : SafeMigrationPlan, checkpoint : MigrationCheckpoint) -> SafeMigrationPlan

    Returns a self-contained remaining workflow after a durable checkpoint. Wave indexes are renumbered from zero so validation remains meaningful for the resumed executor.

    stable_hash

    source
    fn stable_hash(text : String, seed? : UInt) -> UInt

    Stable FNV-1a style 32-bit hash over MoonBit UTF-16 code units.

    topology_is_valid

    source
    fn topology_is_valid(nodes : Array[ShardNode]) -> Bool

    Returns true when the topology has no structural issues.

    validate_safe_migration

    source
    fn validate_safe_migration(plan : SafeMigrationPlan) -> Array[String]

    Checks phase ordering, wave indexes, and both concurrency budgets.

    validate_topology

    source
    fn validate_topology(nodes : Array[ShardNode]) -> Array[TopologyIssue]

    Validates identifiers and failure-domain metadata in one snapshot.

    virtual_position

    source
    fn virtual_position(node_id : String, replica : Int, seed : UInt) -> UInt

    Creates a virtual-node position without ambiguous string concatenation.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io