jonnify·bcs /bcs/cache/single-writer-ring/two-sequences-one-table

B4.3 · dive 1 — two sequences, one table

Two sequences, one table.

The ring's runtime is an atomics pair — tail for the producer, head for the applier — and a public ETS table whose rows are reused by rem(seq, capacity): preallocation, BEAM-style. The correctness of the whole structure leans on one documented sentence: "All atomic operations are mutually ordered" — the slot insert happens before the tail advance, so an applier that reads the new tail finds the slot already written, with no lock anywhere. The committed gate puts order on the record: 1000 items crossed the ring in publish order exactly, through 2 batches (largest 801) on 1 wakes.

Source: content/bcs4.3.md, quoting bcs_rung_4_3_check.out; the module is committed at runtimes/elixir/lib/echo_store/ring.ex.

The ring walk. A head/tail machine over the G1 ring's committed capacity 512 — publish advances the tail, a drain moves the head to the tail in one pass; the slot of every item is rem(seq, capacity), and a fresh ring stands at occupancy 0, as G1 declares.
tail — the producer's sequence (oxide red) head — the applier's sequence (drafting blue) occupancy = tail − head · slot = rem(seq, 512) 512 preallocated slots, rows reused by index; the slot insert happens before the tail advance, so a reader of the new tail finds the slot written. fresh ring: tail = head — occupancy 0; wakes are edge-triggered on empty → nonempty.
readout · A fresh ring stands at occupancy 0 — tail 0, head 0. Publish to advance the tail; drain to move the head to the tail in one pass. Every readout line is computed by the structure's own arithmetic: slot = rem(seq, 512), occupancy = tail − head.
§1

The transcript

bcs_rung_4_3_check.out · verbatim · this dive reads the surface and order lines
content/echo_data/runtimes/elixir/bcs_rung_4_3_check.out · the slice this dive readsfrozen
G1 surface ok -- the ring's surface is whole -- publish, occupancy, stats, stop, a generic one-batch apply function -- and the declaration tells the truth: the broadcast table carries its ring name and capacity 512 in the directory, the :none table carries nil, and a fresh ring stands at occupancy 0
derive (order): the applier drains everything between head and tail in one pass, so concatenating the batches must reproduce publish order exactly; wakes are edge-triggered on the empty-to-nonempty transition, so 1000 items published into a draining ring should cost a handful of wakes -- well under fifty -- and more than one batch proves the batching is real
G2 order ok -- 1000 items crossed the ring in publish order exactly -- the concatenated batches reproduce the sequence -- through 2 batches (largest 801) on 1 wakes: one message per busy period, not one per item
…
PASS 6/6

The elided lines hold the header, the throughput and full drills, and the storm and convergence drills — dive 2 and dive 3 read them, and the module hub freezes the record whole. The derive lines are part of the record: each measurement is bounded before it is taken, and the committed line then lands inside its own band.

§2

Two sequences and a slot table

content/bcs4.3.md · What · Decisions · Boundaries

The ring's runtime is an atomics pair — tail for the producer, head for the applier — and a public ETS table whose rows are reused by rem(seq, capacity): preallocation, BEAM-style. The load-bearing sentence is documented, not assumed: "All atomic operations are mutually ordered." The slot insert happens before the tail advance, so an applier that reads the new tail finds the slot already written — no lock anywhere.

G1 gates the surface and the declaration's truthfulness: publish, occupancy, stats, stop, a generic one-batch apply function — and "the broadcast table carries its ring name and capacity 512 in the directory, the :none table carries nil, and a fresh ring stands at occupancy 0". A table that declares no coherence carries no ring; the directory of 4.1 reports both, truthfully.

Two decisions hold the structure up. Single producer, structurally: the publish path is lock-free because exactly one process calls it — the owner, where pushes already serialize. The simplicity is bought with a rule, the rule is stated in the module doc, and the wake-race analysis in the drain's comment is sound only under it; two producers race the tail and the structure's guarantees evaporate — a second producer needs a second ring, not a clever interleave. Runtime in persistent_term: the producer must reach sequences and slots without a process hop; one persistent_term read per publish is the BEAM's cheapest shared-read path, written once at ring start and erased at stop. A brutal kill skips terminate and leaks one entry until the name is reused — "a stated cost of kill-9 truthfulness."

§3

Order through batches

content/bcs4.3.md · What · quoting G2

The applier drains everything between head and tail in one pass, applies the batch in arrival order, advances head, and re-checks the tail before parking. The committed gate: 1000 items crossed the ring in publish order exactly -- the concatenated batches reproduce the sequence -- through 2 batches (largest 801) on 1 wakes: one message per busy period, not one per item.

That last clause is the wake economy: the producer sends :wake only on the empty-to-nonempty transition, and the applier's re-check-before-park closes the race where a publish lands after the drain's tail read. The derive line bounds it before the measurement — 1000 items published into a draining ring "should cost a handful of wakes -- well under fifty -- and more than one batch proves the batching is real". The committed line lands at 1.

The concatenation, checked. The G2 drill's stream of 1000 items in two batches — the record fixes the count and the largest size (801), not which batch came first; the bar widths are computed live from the committed pair, and the check runs the concatenation element by element.
largest batch · 801 drained in one pass, applied in arrival order the other batch 1000 − 801, computed live · 2 batches on 1 wakes
readout · Select a view. The derive line bounds the drill, G2 commits it, the check reruns the concatenation over the same shape, and the wake ledger reads the economy: 2 batches, 1 wake.
§4

The prior art

content/bcs4.3.md · Why · How

LMAX built a retail exchange whose business logic ran on a single thread — "6 million orders per second on a single thread" — fed by the Disruptor, a bounded ring of preallocated slots with sequence counters, where one consumer drains batches in order and the batching happens by itself whenever the consumer falls behind. The chapter translates that shape onto the BEAM, and the correspondence is exact: sequences are atomics; the preallocated slots are ETS rows reused by index; the single business-logic thread is the applier process; the batching effect — a lagging consumer drains everything available in one pass — is the drain loop; and the wait strategy is the BEAM's own: park in the mailbox, wake on the edge. What does not translate is busy-spinning, and nothing is lost in the omission — on this runtime the mailbox is the wait strategy.

That is why the chapter reads the Disruptor beside the bus's park-don't-poll rather than instead of it — the discipline the manuscript's Part III gave the bus's parked consumers, planned for the course as B3.4 · Fair Lanes. Both replace discovery with arrival, and both wake exactly once per busy period: the same edge-triggered discipline, in one process instead of across a wire.

§5

References

sources · related

Sources

Related