The ring buffer, explained

How Prayog turns thousands of orders arriving at once from many places into one official, fair, replayable order of events, without a single lock. First a business example, then how it works, then exactly how Prayog uses it.

1. The problem it solves

Orders reach the exchange from many directions at the same instant: hundreds of bots, a few humans in the web terminal, the clock ticking every 100 ms, an ops person pressing "halt". Each of these runs on its own thread.

But the order book must be changed by one thread only:

• Fairness: "first come, first served" only means something if there is one official order of arrival.
• Speed: one thread needs no locks. Locks are slow even when uncontended, and much slower when threads fight over them.
• Replay: if we record that one order, we can rebuild the market exactly after a crash (S8).

So we need something at the entrance that takes many writers and hands one reader a single, numbered line of work. That's the ring buffer. Prayog uses the LMAX Disruptor, a widely used Java implementation built by the LMAX exchange for exactly this.

2. A business example: the restaurant ticket wheel

Picture a busy restaurant kitchen with a round ticket wheel: a ring of 8 numbered clips that rotates in front of the head chef.

Notice what the kitchen doesn't have: no manager taking a lock on the whole wheel each time a waiter clips a ticket, and no new clips being made for every order. That's exactly why the design is fast.

3. Why not a normal queue, or locks?

LMAX publicly reported the Disruptor handling millions of messages per second on one thread with much lower and steadier latency than queues. Prayog doesn't need that speed. We use it because it gives us one official order, pipeline stages and back-pressure in one well-tested piece.

4. How the ring works

Sequence numbers, not positions

Everything is counted with ever-increasing sequence numbers (1, 2, 3, …, millions). They never wrap. The slot for sequence s is s mod size. Because the size is a power of two (8, 1,024, 65,536), "mod" is a single bit operation: s & (size − 1). That's why the ring size must be a power of two.

Writing (producers)

1. Claim. A producer atomically increases the shared "claimed" counter (a compare-and-swap). Two threads can never get the same sequence. Before claiming, it checks that the slot is free: claim − slowest reader ≤ size. If not, trySubmit gives up and returns false, while submit waits.
2. Write. It copies the command into that slot. The slot object already exists, created once at startup, so nothing is allocated.
3. Publish. It marks the sequence as available. Readers can now see it. Publishing uses a memory barrier so other threads see the fully written slot, never a half-written one.

Reading (consumers)

1. Each reader keeps its own counter, "the last sequence I finished". The matching handler waits for producers; the journal waits for matching; publishers wait for the journal. These dependencies form the pipeline.
2. A reader that has nothing to do waits using its wait strategy: sleep until woken (BLOCKING, low CPU), spin then yield (YIELDING), or spin forever on its own core (BUSY_SPIN, lowest latency).
3. When a reader falls behind, it finds many ready slots and processes them as a batch, without waiting in between. The last one is flagged endOfBatch. The journal uses that flag to flush the disk once for the whole batch (group commit), so a slow disk gets more efficient under load, not less.

Why it's fast (the short version)

• No locks: just atomic counters, each written by one thread.
• No garbage: slots are reused forever.
• CPU-cache friendly: slots sit next to each other in memory, and the Disruptor pads its counters so two threads' counters never share a cache line ("false sharing").

5. Try it: a ring of 8 slots

Submit commands, then advance each stage. Watch the colours move round the ring, and try filling it to see back-pressure. Sequence numbers keep growing while slots are reused.

Things to try: press "Burst of 5" twice: the second burst is refused partway, which is back-pressure. Then advance only Matching: it can run ahead, but Publishers can't pass the Journal. Turn on "Slow disk" in auto-run and watch the ring fill up, then drain in batches.

6. The ring in Prayog

Key choices (ADR 0006)

• The input sequence is assigned by the matching thread, not by producers. If producers numbered commands, thread A could take 5 and thread B 6 while B publishes first. Then the numbers would disagree with what actually happened.
• The journal sits before the publishers. Nobody is told about a trade until it's on disk.
• Fail safe: if a handler throws, its thread stops, the ring fills and trading halts. Never skip a command.
• 65,536 slots: enough to absorb bursts (seconds of peak traffic), small in memory, and a power of two.

7. One order, end to end

A bot sends BUY 10 ABC @ ₹100.05 while the clock thread is publishing a tick at the same moment.

1. The gateway thread calls trySubmit(newOrder). It claims sequence 41,203, which maps to slot 41,203 & 65,535 = 41,203, writes the command reference and publishes. Meanwhile the clock thread claims 41,204 for its tick. Neither waited for the other.
2. The matching thread, which has been waiting, sees 41,203 is available. It sets inputSeq to the next number (say 41,203), applies the order: accepted, one trade at ₹100.00. It writes two events into the slot's list.
3. It moves straight on to 41,204 (the tick) in the same batch, with no waiting between them.
4. The journal stage (S8) sees both, writes the two commands and their events, and calls fsync once because 41,204 is the end of the batch.
5. The publisher stages send the HTTP response to the bot and push the trade print and book update to WebSocket subscribers.
6. Once every stage has passed 41,203, its slot is free and will be reused by sequence 106,739 (41,203 + 65,536).

What the S7 test proves: 8 threads × 2,000 commands at once. Whatever order the ring produced, the input sequence has no gaps, each thread's own order is preserved, and replaying the recorded order through a fresh engine gives identical events. S8 makes that recorded order permanent, on disk.

8. Questions

What happens if matching is slower than producers?

The ring fills. trySubmit starts returning false, and the gateway answers 503 "busy". Clients back off, and nothing is lost, because nothing was accepted.

What if the journal (disk) is slow?

Matching can run ahead, but only until the ring is full, because slots aren't freed until the journal and the publishers pass them. Under load the journal sees bigger batches, so each fsync covers more commands.

Isn't one matching thread a bottleneck?

One thread can match millions of simple orders per second because it never waits for locks or I/O. When that's not enough, exchanges shard: symbols A–M on one ring and thread, N–Z on another. Prayog runs one shard for the MVP.

Why are the producers allowed to block in submit?

Only internal producers use it: a lost clock tick or a lost "halt" would be worse than a few milliseconds' wait. The gateway uses trySubmit so web threads never hang.

Do commands still allocate memory?

Yes. Our commands are Java records created by producers; only the slots are pre-allocated. Fully garbage-free designs write raw bytes into the slots. We'll consider that only if the S9 benchmarks show garbage collection hurting latency.

9. Glossary