@spec get_log_indices(non_neg_integer(), pos_integer(), non_neg_integer()) :: [
  non_neg_integer()
]

Returns m log indices for shard tag x given n total logs.

Uses golden ratio stepping for uniform distribution. The result is deterministic for the same inputs.

Parameters

• x - Shard tag (non-negative integer)
• n - Total number of logs
• m - Replication factor (how many logs to return)

Examples

iex> ShardRouter.get_log_indices(0, 5, 2)
[4, 0]  # Two distinct indices in range [0, 5)

iex> ShardRouter.get_log_indices(0, 5, 0)
[]

@spec get_logs_for_key(
  :ets.table(),
  binary(),
  %{required(non_neg_integer()) => binary()},
  non_neg_integer()
) :: [binary()]

Routes a key to its logs using shard lookup and golden ratio log selection.

Uses lazy caching: first call computes log_indices and caches in ETS, subsequent calls use the cached value. The ETS entry format changes from {end_key, tag} to {end_key, {tag, log_indices}} after first access.

Parameters

• shard_table - ETS table with {end_key, tag} or {end_key, {tag, log_indices}} entries
• key - The key to route
• log_map - Map from log index to log_id (%{0 => "log-a", 1 => "log-b", ...})
• replication_factor - How many logs to return

Returns

List of log_ids that should store data for this key.

@spec lookup_shard(:ets.table(), binary()) :: non_neg_integer()

Looks up the shard tag for a key using ETS ceiling search.

The ETS table must be an ordered_set with entries in one of two formats:

• {end_key, tag} - uncached format
• {end_key, {tag, log_indices}} - cached format (after get_logs_for_key/4 call)

Shard ranges are [min, max) - start inclusive, end exclusive.

Parameters

• table - ETS table reference
• key - The key to look up

Returns

The shard tag (non-negative integer) that owns the key.

Examples

# Table has: {"m", 0}, {"\xff", 1}
# Shard 0 covers ["", "m"), Shard 1 covers ["m", "\xff")
iex> lookup_shard(table, "apple")
0
iex> lookup_shard(table, "m")
1  # "m" is the START of shard 1, not end of shard 0
iex> lookup_shard(table, "zebra")
1

@spec lookup_shards_for_range(:ets.table(), binary(), binary()) :: [non_neg_integer()]

Looks up all shard tags that overlap with a key range.

Used for range mutations (clear_range) that may span multiple shards. Returns a list of tags for all shards that intersect the range [start_key, end_key).

Parameters

• table - ETS table reference with {end_key, tag} entries
• start_key - Start of the range (inclusive)
• end_key - End of the range (exclusive)

Returns

List of shard tags that the range intersects with.

Examples

# Table has: {"d", 0}, {"h", 1}, {"m", 2}, {"\xff", 3}
iex> lookup_shards_for_range(table, "a", "c")
[0]
iex> lookup_shards_for_range(table, "c", "f")
[0, 1]

@spec lookup_shards_with_ranges(:ets.table(), binary(), binary()) :: [
  {non_neg_integer(), binary(), binary()}
]

Returns shards overlapping a key range, with their boundaries.

Unlike lookup_shards_for_range/3 which returns only tags, this function returns {tag, shard_start, shard_end} tuples to enable clamping range mutations to shard boundaries.

Parameters

• table - ETS table reference with {end_key, tag} entries
• start_key - Start of the range (inclusive)
• end_key - End of the range (exclusive)

Returns

List of {tag, shard_start, shard_end} tuples for all shards that overlap [start_key, end_key). Returns [] when the range lies entirely beyond shard coverage (start_key >= every shard's exclusive end_key).

Examples

# Table has: {"d", 0}, {"h", 1}, {"m", 2}, {"\xff", 3}
# Shards: 0 = ["", "d"), 1 = ["d", "h"), 2 = ["h", "m"), 3 = ["m", "\xff")
iex> lookup_shards_with_ranges(table, "a", "c")
[{0, "", "d"}]
iex> lookup_shards_with_ranges(table, "c", "j")
[{0, "", "d"}, {1, "d", "h"}, {2, "h", "m"}]