Bedrock.HighContentionAllocator (bedrock v0.5.2)

View Source

High-Concurrency Allocator (HCA) implementation for Bedrock.

This module implements the HighContentionAllocator algorithm used by FoundationDB's Directory Layer for efficient allocation of unique identifiers in high-contention environments.

Based on the FoundationDB Python bindings and the erlang/erlfdb implementation. Uses a sophisticated windowing strategy with:

  1. Randomized candidate selection to reduce contention
  2. Dynamic window sizing based on allocation pressure
  3. Window reuse and cleanup mechanisms
  4. Conflict-resistant allocation patterns

References:

Summary

Types

t()

Functions

allocate(hca)

Allocate a single unique ID from the HighContentionAllocator.

allocate(hca, txn)

Allocate a prefix within an existing transaction.

allocate_many(hca, count)

Allocate multiple unique IDs from the HighContentionAllocator.

new(repo, keyspace, opts \\ [])

Create a new HighContentionAllocator instance.

stats(hca)

Get statistics about the HighContentionAllocator state.

Types

t()

@type t() :: %Bedrock.HighContentionAllocator{
  counters_keyspace: binary(),
  random_fn: (pos_integer() -> pos_integer()),
  recent_keyspace: binary(),
  repo: module()
}

Functions

allocate(hca)

@spec allocate(t()) :: {:ok, binary()} | {:error, term()}

Allocate a single unique ID from the HighContentionAllocator.

Returns a unique compact binary encoding of the allocated ID. This operation is highly concurrent and designed to minimize write conflicts even under heavy load.

Examples

iex> MyApp.Repo.transact(fn ->
...>   {:ok, Bedrock.HighContentionAllocator.allocate(hca)}
...> end)
{:ok, <<21, 42>>}  # Key-encoded binary

allocate(hca, txn)

@spec allocate(t(), Bedrock.Internal.Repo.transaction()) :: binary()

Allocate a prefix within an existing transaction.

allocate_many(hca, count)

@spec allocate_many(t(), pos_integer()) :: {:ok, [binary()]} | {:error, term()}

Allocate multiple unique IDs from the HighContentionAllocator.

Returns a list of unique compact binary encoded IDs. This is implemented by calling allocate/2 multiple times.

Examples

iex> MyApp.Repo.transact(fn ->
...>   {:ok, Bedrock.HighContentionAllocator.allocate_many(hca, 5)}
...> end)
{:ok, [<<21, 0>>, <<21, 1>>, <<21, 2>>, <<21, 3>>, <<21, 4>>]}

new(repo, keyspace, opts \\ [])

@spec new(module(), binary(), keyword()) :: t()

Create a new HighContentionAllocator instance.

Parameters

  • repo - The Bedrock.Repo module to use for transactions
  • keyspace - Binary prefix for this allocator's keys
  • opts - Optional configuration

Options

  • :random_fn - Custom random function for testing (default: &:rand.uniform/1)

Examples

iex> hca = Bedrock.HighContentionAllocator.new(MyApp.Repo, "my_allocator")
iex> hca.counters_keyspace
"my_allocator\x00"

iex> hca.recent_keyspace
"my_allocator\x01"

# For testing with controlled randomization
iex> deterministic_random = fn _size -> 1 end
iex> hca = Bedrock.HighContentionAllocator.new(MyApp.Repo, "test", random_fn: deterministic_random)

stats(hca)

@spec stats(t()) :: %{
  latest_window_start: non_neg_integer(),
  total_counters: non_neg_integer(),
  estimated_allocated: non_neg_integer()
}

Get statistics about the HighContentionAllocator state.

Returns information about allocated windows, usage patterns, etc. Useful for monitoring and debugging.