Malachi.
View Source
Shared keyspace arithmetic: hashing keys into a power-of-two space [0, 2^bits) and the
buddy-allocator block math NorthGuard's ranges use.
Both the data plane (Malachi.Broker, which routes record keys to keyspace slices) and
the control plane (Malachi.Cluster.HashRing/DS-RSM, which routes metadata keys to
vnodes) hash keys the same way and share the same 1..32 bound (because
:erlang.phash2/2 supports a range up to 2^32). Centralizing it here keeps that rule:
and the buddy split/merge math, in one place.
Summary
Functions
Whether two equal-size, power-of-two-aligned blocks are buddies: the two halves of a
common parent block (the buddy-allocator rule start XOR size).
Hashes key into [0, size).
Returns {:ok, 2^bits} for bits in 1..32, or {:error, :out_of_range} otherwise.
Use this when bits comes from untrusted input (e.g. a replicated command) and must not
raise; use size_for_bits!/2 for trusted callers where bad bits is a programmer error.
Validates bits is in 1..32 and returns the keyspace size 2^bits. Raises
ArgumentError (mentioning label) otherwise.
The midpoint that splits a power-of-two block [block_start, block_end) in half.
Whether the block [block_start, block_end) is large enough to split (size >= 2).
Whether position falls in the block [block_start, block_end).
Functions
@spec buddies?( non_neg_integer(), non_neg_integer(), non_neg_integer(), non_neg_integer() ) :: boolean()
Whether two equal-size, power-of-two-aligned blocks are buddies: the two halves of a
common parent block (the buddy-allocator rule start XOR size).
@spec position_of(term(), pos_integer()) :: non_neg_integer()
Hashes key into [0, size).
@spec size_for_bits(integer()) :: {:ok, pos_integer()} | {:error, :out_of_range}
Returns {:ok, 2^bits} for bits in 1..32, or {:error, :out_of_range} otherwise.
Use this when bits comes from untrusted input (e.g. a replicated command) and must not
raise; use size_for_bits!/2 for trusted callers where bad bits is a programmer error.
@spec size_for_bits!(integer(), String.t()) :: pos_integer()
Validates bits is in 1..32 and returns the keyspace size 2^bits. Raises
ArgumentError (mentioning label) otherwise.
@spec split_point(non_neg_integer(), non_neg_integer()) :: non_neg_integer()
The midpoint that splits a power-of-two block [block_start, block_end) in half.
@spec splittable?(non_neg_integer(), non_neg_integer()) :: boolean()
Whether the block [block_start, block_end) is large enough to split (size >= 2).
@spec within?(non_neg_integer(), non_neg_integer(), non_neg_integer()) :: boolean()
Whether position falls in the block [block_start, block_end).