🥮 mooncakes.io

moonshardkit

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

consistent-hashing
rendezvous-hashing
sharding
replica-placement
migration-planning
moon add Dz-6666/moonshardkit@0.4.0
Download zip
Author
Version
0.4.0
License
Apache-2.0
Repository
Last updated
last month
Downloads
15
README

#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 issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io