#hashwheel (MoonBit)

let hr : @hashwheel.ConsistentHash[String] = @hashwheel.ConsistentHash::new()
ignore(hr.add("server1"))
ignore(hr.add("server2"))

let node = hr.get("resourceName")   // Some("server1") or Some("server2")

#Features

• Bit-for-bit compatible with the JavaScript version: string hashes, the uniform control points and the resulting resource mappings are identical to the JavaScript hashwheel implementation (verified input by input).
• Hash: MurmurHash3 (x86 32-bit) over UTF-16 code units, matching JavaScript string semantics, returning an unsigned 32-bit value.
• O(n log n) insertion: adding any number of nodes never degrades to O(n²).
• Fast lookup: control points are kept sorted and searched with an "approximate binary" search (binary search down to 25 entries, then a linear scan); the hot path only touches one sorted array and one parallel node array.
• Two control point layouts:
  • Random: scatter points and detect collisions (default);
  • Uniform: interleave evenly spaced points, fully deterministic — the same nodes in the same order always produce the same ring.
• Weights: weight decides how many control points a node owns, and therefore how much of the resource space it serves (nodes weighted 1:2:3 serve 1/6, 1/3 and 1/2 of the resources).
• Explicit control points: pass a points array for low-level control over the resource distribution.
• Optional LRU lookup cache: cache=n caches get() results (the cache is dropped whenever a node is added or removed).
• Multi node lookup: get_many(name, count) returns the count nearest distinct nodes starting at the resource, for replica selection.
• Generic nodes: the node type is a generic T (requires Eq, usually just String); String, Int or your own type all work.
• Reproducible: Uniform distribution is deterministic by construction, and Random distribution accepts a 32-byte seed to reproduce the same ring.
• Pure library: no third-party packages, builds for native, wasm, wasm-gc and js targets.

#How it works

• The ring: range positions (default 100003; an odd range, preferably a prime relatively prime to the number of nodes, distributes better). The ring capacity is the range of hash(name) % range.
• Control points (tokens): each node owns weight control points around the ring. Giving a node more weight means giving it more control points.
• Lookup: point = murmur3(name) % range; the node owning the first control point at or after point handles the resource. If point is larger than every control point, the search wraps around to the first control point.
• Random placement: Random mode creates control points during add(), probing for free positions with an occupancy set. Each point is retried at most 100 times; random probing fills roughly 90% of a ring.
• Uniform placement: Uniform mode assigns points on first use (first lookup or get_points) using step = range / (nodes * weight), interleaving the control points of consecutive nodes around the ring.
• Capacity: the theoretical node count is range / weight (2500 with the defaults), which is a completely full ring; in practice about 90% can be filled. For more nodes use a wider range (such as 1000003) or a smaller weight (such as 4).

#Build and test

moon check     # type check
moon test      # run all tests
moon info      # refresh pkg.generated.mbti
moon fmt       # format the sources

#API

#ConsistentHash::new(...)

// uniform distribution, 40 control points per node, 100-entry lookup cache
///|
let hr : @hashwheel.ConsistentHash[String] = @hashwheel.ConsistentHash::new(
  distribution=Uniform,
  cache=100,
)

// a small ring, easy to inspect: range=24, 4 control points per node

///|
let small : @hashwheel.ConsistentHash[String] = @hashwheel.ConsistentHash::new(
  range=24,
  weight=4,
  nodes=["a", "b", "c"],
)

#hr.add(node, weight?, points?) -> Self

• weight: number of control points for this node, defaults to the ring weight;
• points: an explicit control point array; when given, no random or uniform points are generated for this node.

ignore(hr.add("server1"))              // default weight
ignore(hr.add("server2", weight=120))  // heavier, serves more resources
ignore(hr.add("server3", points=[10, 20, 30]))

#hr.remove(node) -> Self

ignore(hr.remove("server1"))

#hr.get(name) -> T?

match hr.get("user:42") {
  Some(node) => println("handled by \{node}")
  None => println("no nodes on the ring")
}

#hr.get_many(name, count) -> Array[T]?

///|
let replicas = hr.get_many("user:42", 3) // primary plus two fallbacks

#Inspection

#Package level

#API mapping from JavaScript

#Behaviour and caveats

• The node type must implement Eq (remove, get_points and get_many use it to find and de-duplicate nodes by value).
• get / get_many return None on an empty ring (the JavaScript version returns null).
• With Uniform distribution every node uses the ring's weight, so a per-call weight argument is ignored (same as JavaScript); uniform control points are only materialised on first use.
• Adding the same node several times increases its weight.
• If the ring is too full (100 retries per point all collide) the program aborts (JavaScript throws an exception); use a larger range or a smaller weight.
• A Random ring differs from run to run. For reproducibility use Uniform, or pass the same seed.

#Tests

moon test

• hashwheel_test.mbt (blackbox): constructors, adding and removing nodes, weights, uniform and random distribution, multi node lookup, cache invalidation, lookup distribution fairness, filling 80% of a ring with 2000 nodes, and more;
• hashwheel_wbtest.mbt (whitebox): the approximate binary search, hashes matching the JavaScript values, sorted index construction, uniform point coordinates, LRU eviction;
• the mbt check examples in the source comments also run as tests.

moon coverage analyze > uncovered.log

#Layout

moon.mod                 module definition
moon.pkg                 package dependencies (moonbitlang/core/random)
consistent_hash.mbt      the ring: ConsistentHash, add/remove/get/get_many/...
hash.mbt                 MurmurHash3
lru_cache.mbt            optional LRU lookup cache
hashwheel_test.mbt       blackbox tests
hashwheel_wbtest.mbt     whitebox tests
pkg.generated.mbti       generated public interface (moon info)
README.mbt.md            this file
LICENSE                  Apache-2.0

#License