Bedrock.Internal.TransactionBuilder.LayoutIndex (bedrock v0.5.2)

View Source

Pre-computed index for efficient Transaction System Layout lookups.

This module builds a gb_tree index from the static TSL configuration by segmenting the keyspace into non-overlapping ranges. Each segment shows exactly which PIDs are responsible for that portion of the keyspace, enabling O(log n) lookups instead of O(n) linear scans through all storage teams.

Segmented Keyspace Example

Given overlapping storage teams:

  • a-f → [pid1]
  • d-m → [pid2]
  • h-p → [pid3]

The index creates non-overlapping segments:

  • {a, d} → [pid1]
  • {d, f} → [pid1, pid2]
  • {f, h} → [pid2]
  • {h, m} → [pid2, pid3]
  • {m, p} → [pid3]

Summary

Types

t()

Functions

build_index(transaction_system_layout)

Builds a segmented index from a Transaction System Layout.

get_next_segment(layout_index, key)

Finds the next segment after the one containing the given key.

get_previous_segment(layout_index, key)

Finds the previous segment before the one containing the given key.

lookup_key!(layout_index, key)

Looks up storage servers for a single key using recursive tree traversal.

lookup_range(layout_index, start_key, end_key)

Looks up storage servers for a key range.

Types

t()

@type t() :: %Bedrock.Internal.TransactionBuilder.LayoutIndex{
  tree:
    :gb_trees.tree(
      binary(),
      {binary(), [pid()]}
    )
}

Functions

build_index(transaction_system_layout)

@spec build_index(Bedrock.ControlPlane.Config.TransactionSystemLayout.t()) :: t()

Builds a segmented index from a Transaction System Layout.

get_next_segment(layout_index, key)

@spec get_next_segment(t(), binary()) ::
  {:ok, {{binary(), binary()}, [pid()]}} | :end_of_keyspace

Finds the next segment after the one containing the given key.

This is useful for cross-shard KeySelector resolution when we need to continue processing in the next shard.

get_previous_segment(layout_index, key)

@spec get_previous_segment(t(), binary()) ::
  {:ok, {{binary(), binary()}, [pid()]}} | :start_of_keyspace

Finds the previous segment before the one containing the given key.

This is useful for cross-shard KeySelector resolution when we need to continue processing in the previous shard.

lookup_key!(layout_index, key)

@spec lookup_key!(t(), binary()) :: {{binary(), binary()}, [pid()]}

Looks up storage servers for a single key using recursive tree traversal.

Returns a {key_range, [pid]} tuple for the segment containing the key. The end key will be the binary sentinel <<0xFF, 0xFF>> for unbounded ranges. Raises if no segment is found. This is an O(log n) operation.

lookup_range(layout_index, start_key, end_key)

@spec lookup_range(t(), binary(), binary()) :: [{{binary(), binary()}, [pid()]}]

Looks up storage servers for a key range.

Returns a list of {key_range, [pid]} tuples for all segments that overlap with the specified range. Each segment shows exactly which PIDs cover that portion of the keyspace. End keys will be the binary sentinel <<0xFF, 0xFF>> for unbounded ranges.