Write Batches

Write Batches

Ordinum uses batching on the write path to group multiple operations together and commit them together as a group rather than individually. The concept of batching should not be unfamiliar to most even outside of system design.

Each write has a per-operation cost as well as overhead associated with committing it. In a simplified model, processing x writes individually costs approximately x * (h + y), where h is the fixed commit overhead and y is the work required per write. Committing those writes in one batch costs approximately h + x * y. Batching therefore amortises the commit overhead across multiple writes, although the individual operations still need to be processed.

Simply put, if I was going to wash my clothes on a Saturday (like I do), I would not wash one item at a time and wait for each cycle to finish before selecting another. No, I'll load them all in, within the machine's capacity, and wait for one cycle to finish with lovely clean-smelling clothes.

This journal explores how Ordinum represents and processes write batches, using Rust's type system and type-state patterns to express batch states and enforce valid transitions at compile time. It will also explore how queues and leader/follower coordination can work together to organise concurrent writers, and the design decisions behind Ordinum's approach.

One of the biggest design decisions when creating batches was to use Rust's type system to represent their lifecycle. Ordinum relies heavily on the Typestate Pattern for this.

Two really great blogs on this subject are:

1. The Typestate Pattern in Rust
2. How To Use The Typestate Pattern In Rust

Before exploring the implementation, it is important to separate two related but distinct concepts: write batches and write groups.

A write batch is a unit of work submitted by a single caller. It contains one or more write operations in a defined order:

Batch A
├── Put(item:7:stock, 25)
├── Delete(item:7:offer)
└── Put(item:8:stock, 100)

The caller constructs the batch and submits it to Ordinum as one commit operation. The batch remains the caller's logical unit of work as it moves through the write path.

When several callers submit batches concurrently, Ordinum may temporarily collect those batches into a write group:

Writer 1 ── Batch A ──┐
Writer 2 ── Batch B ──┼── Write Group ── Commit
Writer 3 ── Batch C ──┘

The write group is an internal coordination mechanism rather than another caller-visible batch. Batch A, Batch B, and Batch C remain distinct batches belonging to distinct callers; Ordinum simply processes them together where doing so allows fixed commit costs to be shared.

This distinction gives us two different forms of aggregation:

Within a batch, multiple operations from one caller share the cost of committing that batch.

Across batches, group commit allows multiple concurrent callers to share engine-level commit work, such as writing and synchronising the WAL.

A batch therefore answers:

What operations did this caller ask Ordinum to commit together?

A write group answers:

Which waiting batches can Ordinum process together efficiently?

One batch can form a write group by itself when there are no other writers waiting. Under concurrent load, several batches may instead participate in the same write group.

A queue provides the meeting point for these concurrent writers. One writer can act as the leader for a group, selecting compatible waiting batches and coordinating the shared portion of the write path on behalf of the followers. Grouping may improve throughput by amortising fixed costs, although waiting briefly for additional writers can also increase latency.

With write-ahead logging enabled, the resulting write group passes through the WAL and memtable portions of the write path. The operations from each constituent batch retain their required ordering; grouping the batches does not turn them into one application-level transaction.

From Write Batches to Write Groups

For context, consider three callers submitting the following batches:

Each batch is independently created and submitted by its caller:

Batch A = 2 operations
Batch B = 2 operations
Batch C = 2 operations
             ↓
Write Group = [Batch A, Batch B, Batch C]

Ordinum does not conceptually turn these batches into a new application-level batch. Instead, it forms a write group so that shared portions of the write path can be coordinated once for all participating writers.

Multiple incoming batches can therefore share write overhead while remaining distinct units of caller work. The diagram below highlights the two main responsibilities involved after a write group has been formed: recording operations in the WAL and inserting them into the memtable. It shows a synchronous write, where completion also requires confirmation that the WAL has been synchronised with storage.

The branches show completion requirements, not execution order or a requirement to run both steps in parallel. The WAL-synced signal confirms storage synchronisation; inserting into the memtable alone does not make a write durable.

The Write Path

There are three main components involved in committing writes through Ordinum:

1. Write Batch
2. Batch Group
3. Write Pipeline

The WriteBatch is the underlying vehicle throughout the entire write path. It remains caller-owned from construction through to commit completion.

This ownership model has influenced a large amount of the surrounding design.

Rather than transferring a batch into the engine and returning ownership later, Ordinum operates on references to the caller's batch. This avoids unnecessary ownership movement and fits naturally with the batch pooling model, but it also means the pipeline must be very precise about how long it retains access to batch state.

The WriteBatch itself is split across several layers and typestates. Different states expose different operations and trait bounds, allowing invalid transitions to be rejected at compile time rather than relying entirely on runtime checks.

The batch remains the unit of caller-owned work. The group is temporary coordination state around several compatible batches.

The pipeline is responsible for moving those batches through the commit path while maintaining ordering, visibility and durability guarantees.

Moving Away From Leader / Follower

The first implementation of batch grouping followed a design similar to RocksDB's leader/follower write path.

RocksDB WriteThread

Writers linked themselves into an intrusive list. The oldest writer became the group leader and walked the waiting writers, collecting compatible writes into a local group.

Followers then waited on state transitions indicating whether they had:

• been committed by the current leader;
• become the next leader;
• or needed to apply their batch to the memtable themselves.

There were parts of this design that worked well for Ordinum. In particular, it made it possible to separate WAL work from memtable application and allow followers to participate in memtable writes while WAL synchronisation was still taking place.

The problem was the amount of machinery required to make the ownership model work cleanly in Rust.

The writer list required intrusive links between objects owned elsewhere. Those links had to remain valid while writers changed state across threads, groups were constructed and dismantled, and callers continued to own the underlying batches.

The resulting implementation accumulated considerably more unsafe code and coordination complexity than we wanted in such a central part of the engine. The design worked, but it did not fit Ordinum particularly well.

Moving Towards a Commit Pipeline

Pebble's commitPipeline provided a much better reference point for the direction we wanted to take.

Pebble commitPipeline

The important idea for Ordinum was not to reproduce Pebble's implementation directly, but to move away from explicit writer leadership and instead make the pipeline itself responsible for coordinating progress.

That led us towards:

• a bounded commit queue;
• explicit batch states;
• ordered sequence assignment;
• concurrent memtable application;
• ordered publication;
• and asynchronous WAL synchronisation.

This mapped much more naturally onto the rest of Ordinum's design. Instead of encoding coordination primarily through linked writers, we could encode more of it through queue position and state transitions.

The resulting design is closer to:

The stages are logically ordered, but they do not all have to execute serially. That distinction is important. The pipeline serialises the parts of the write path that establish order, while allowing work that does not require serial execution to proceed concurrently.

Pipeline Ordering

The first major invariant is sequence ordering.

Batches entering the pipeline receive monotonically increasing sequence ranges.

Batch A      Batch B      Batch C
100..102     103..106     107..109

Once those ranges have been assigned, later stages are allowed varying degrees of concurrency. WAL writes must preserve sequence order. Memtable application does not necessarily need to. If three batches are applying concurrently, their physical insertion may complete in a different order:

Batch A ─────────────── applied
Batch B ───────────────────── applied
Batch C ─────── applied

Batch C finishing before Batch B is acceptable.

Publishing Batch C before Batch B is not.

The pipeline therefore separates application from visibility.

Each batch records when its memtable work has completed. Publication then walks the ordered commit queue and advances through the contiguous sequence of batches that have completed application.

This gives us concurrent memtable application without weakening read visibility ordering.

Batch Grouping Through the Commit Queue

Batch grouping is formed by the commit queue rather than existing as a separate mechanism.

Each caller-owned WriteBatch enters the bounded commit queue in commit order. The queue therefore provides both the ordering mechanism for the pipeline and the set of pending batches from which groups can be formed. A BatchGroup therefore can be thought of as a set of queued batches in the pipeline.

The batches are not copied into a new combined WriteBatch, and their ownership does not change. The group is simply the pipeline's view of which queued batches can participate in shared commit work.

This was an important simplification over the original leader/follower implementation.

The earlier design encoded grouping through relationships between writers: writers linked themselves together, one became leader, and that leader constructed a group from its followers. The current design already has the ordering information we need in the commit queue.

Rather than maintaining a second intrusive writer structure, the pipeline can use queue position itself as the basis for coordination. This keeps grouping tied directly to commit ordering.

A later batch cannot be pulled ahead of an earlier queued batch simply because it would make a more convenient group. Group construction has to respect the ordering already established by the queue.

WAL and Memtable Concurrency

Another part of the earlier Rocks-style design that we wanted to retain was the ability to overlap WAL synchronisation with memtable application.

Once the WAL contents have been prepared and submitted, the pipeline does not need to sit idle waiting for storage synchronisation before beginning memtable insertion.

Conceptually:

These branches represent different completion conditions rather than two completely independent operations.

For a synchronous write, both sides eventually matter.

The memtable work must complete before the sequence range can become visible.

The WAL sync must complete before the caller can be told that the requested durability guarantee has been satisfied.

This distinction became particularly important because Ordinum keeps the batch caller-owned.

The caller cannot be allowed to reset or reuse the batch while an asynchronous WAL sync still holds state associated with that commit.

Current Design Invariants

The current pipeline is built around a small number of invariants:

1. Batches must receive sequence ranges in commit order.

1. WAL writes must preserve that ordering.

1. Memtable application may run concurrently and may complete out of order.

1. Sequence visibility must advance in order.

1. Batch grouping must not allow later writers to bypass earlier sequence ordering.

1. WAL synchronisation may overlap with memtable application.

1. A synchronous commit must not complete before its requested WAL sync has been observed.

1. A caller-owned batch must not be reset, reused or returned to its pool while any part of the pipeline may still reference its commit state.

These invariants are more important than the exact queue or state-machine implementation.

The queue, grouping strategy and internal states can change as Ordinum evolves, but the write path must continue to preserve these guarantees.

Across these designs, the mechanics of grouping and committing batches share many of the same underlying constraints. Sequence ordering must be preserved, WAL ordering must remain consistent with that sequence, memtable application may proceed concurrently without allowing visibility to advance out of order, and synchronous writes must not complete before their required durability conditions have been satisfied.

Those invariants place fairly strict boundaries around what the write pipeline is allowed to do. The interesting design space for Ordinum therefore lies less in inventing a completely different commit protocol and more in how the batch itself is represented and moved safely through that protocol.

This is where much of Ordinum's implementation differs.

The WriteBatch is not simply a buffer of encoded operations. It carries the state required by the commit path while remaining caller-owned throughout its lifetime. Its representation is split across a number of layers, typestates and trait bounds which progressively expose the capabilities required at each stage of the write path.

The next section looks more closely at how Ordinum constructs the WriteBatch, why those layers exist, and how Rust's type system is used to enforce valid batch transitions at compile time.

Write Batch

...