Module foundationdb::tuple::hca

The directory layer offers subspace indirection, where logical application subspaces are mapped to short, auto-generated key prefixes. This prefix assignment is done by the High Contention Allocator, which allows many clients to allocate short directory prefixes efficiently.

The allocation process works over candidate value windows. It uses two subspaces to operate, the "counters" subspace and "recents" subspace (derived from the subspace used to create the HCA).

"counters" contains a single key : "counters : window_start", whose value is the number of allocations in the current window. "window_start" is an integer that marks the lower bound of values that can be assigned from the current window. "recents" can contain many keys : "recents : ", where each "candidate" is an integer that has been assigned to some client

Assignment has two stages that are executed in a loop until they both succeed.

1. Find the current window. The client scans "counters : *" to get the current "window_start" and how many allocations have been made in the current window. If the window is more than half-full (using pre-defined window sizes), the window is advanced: "counters : *" and "recents : *" are both cleared, and a new "counters : window_start + window_size" key is created with a value of 0. (1) is retried If the window still has space, it moves to (2).

2. Find a candidate value inside that window. The client picks a candidate number between "[window_start, window_start + window_size)" and tries to set the key "recents : ". If the write succeeds, the candidate is returned as the allocated value. Success! If the write fails because the window has been advanced, it repeats (1). If the write fails because the value was already set, it repeats (2).

Structs

HighContentionAllocator

Represents a High Contention Allocator for a given subspace

Enums

HcaError