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 write batches, using Rust's type system and typestate patterns to control the operations available at each stage of their lifecycle. It also explains how the write pipeline's ownership and ordering requirements shaped that representation.

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, the engine can coordinate them as a write group. There are several ways to organise this work, including leader/follower lists and a pipeline backed by a multiple-producer, single-consumer (MPSC) queue:

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.

Ordinum has explored both approaches. The earlier design used leader/follower coordination, with one writer processing shared work on behalf of waiting writers. The current direction is inspired by Pebble's commit pipeline: callers submit batches to an ordered queue, and the pipeline coordinates their progress. Establishing commit order does not require every stage to execute serially; memtable application can overlap while publication remains ordered.

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 using the commit pipeline 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 the owning handle into the engine and returning it later, the commit interface borrows the caller's sealed batch. Internally, the pipeline uses non-owning pointers to its stable heap allocation. This keeps allocation ownership with the caller and fits the pooling model, but requires precise limits on how long pipeline components may access that allocation. Moving the handle itself would not move the heap allocation or copy its encoded records.

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 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.
2. WAL writes must preserve that ordering.
3. Memtable application may run concurrently and may complete out of order.
4. Sequence visibility must advance in order.
5. Batch grouping must not allow later writers to bypass earlier sequence ordering.
6. WAL synchronisation may overlap with memtable application.
7. A synchronous commit must not complete before its requested WAL sync has been observed.
8. 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

Before looking at the layers, it helps to start with the caller API that guided the design. A caller should be able to acquire a batch, append operations, and then either clear it for reuse or return it to its pool. The following example uses the current internal API; it assumes batch_pool is available and the surrounding function returns a compatible Result.

let mut batch = batch_pool.acquire_batch();
batch.put(b"item:7:stock", b"25");

// Clear the records and retain the allocation for another batch.
let mut batch = batch.reset();
batch.put(b"item:8:stock", b"100");

// Return the allocation to the pool when finished.
batch.close()?;

The example deliberately does not commit either batch: reset() discards the existing records, and close() returns the allocation rather than submitting its contents. Both methods consume the handle. Reset returns a new Batch<UnCommitted, P>, whereas close returns a Result<()> and leaves no batch handle to reuse.

The central abstraction is BatchObject<State, Allocation>. Its two type parameters describe independent aspects of the batch: what operations are permitted at this stage, and which owning allocation representation backs it. This lets ordinary and indexed batches share a lifecycle abstraction while retaining their own storage and destruction behaviour.

// Simplified declaration; visibility and methods omitted.
struct BatchObject<State: BatchCommitState, Allocation: BatchAllocation> {
    _state: PhantomData<State>,
    inner: Allocation,
}

// The same state can describe different owning allocations.
type OrdinaryBuilding = BatchObject<UnCommitted, OwnedBatchPtr>;
type IndexedBuilding = BatchObject<UnCommitted, OwnedIndexedBatchPtr>;

type OrdinarySealed = BatchObject<Sealed, OwnedBatchPtr>;
type IndexedSealed = BatchObject<Sealed, OwnedIndexedBatchPtr>;

The outer Batch and IndexedBatch handles add acquisition and memory-reuse policy around these objects. Ordinum currently uses a pool, kept alive by an Arc in the handle. Pooling is how we acquire and recycle the memory; the state and allocation parameters are what describe the batch itself.

Separating The Layers

Each layer has a distinct responsibility:

The generic names are worth distinguishing: P in Batch<S, P> is the pool type, while the second parameter of BatchObject is an allocation type. I use A in the table to make that distinction clear. The ordinary batch fixes that allocation type to OwnedBatchPtr.

Moving these wrappers between the caller and pool does not move the BatchInner allocation. That stable address allows the pipeline to refer to it without taking ownership. The encoded Vec<u8> may still reallocate while records are being appended; a stable BatchInner address does not imply that its byte buffer always has a stable address.

Typestate Controls Capabilities

The current compile-time states are UnCommitted and Sealed. They describe which operations are available through the handle, rather than every stage of commit execution.

Batch<UnCommitted, P> exposes put(&mut self, ...) and seal(self). Sealing consumes the mutable-building handle and returns Batch<Sealed, P> around the same allocation. The sealed handle has no put() method, so the caller cannot continue appending operations through that API.

let mut batch = batch_pool.acquire_batch();
batch.put(b"item:7:stock", b"25");

let sealed = batch.seal();
// sealed.put(...) is unavailable for this type.

// Sealing alone does not submit or commit the batch.
let batch = sealed.reset();
batch.close()?;

The commit interface accepts &impl SealedBatch. The ordinary batch implements this trait for Batch<Sealed, P>, exposing the stable BatchInner pointer needed by the pipeline. The interface therefore requires a sealed handle while borrowing, rather than consuming, its owner.

PhantomData carries the state in the type system without storing a runtime state value. A typestate transition moves the owning wrapper into a new type; it does not copy the encoded records or allocate another BatchInner. Sealing also does not mean that the batch has been applied, published or made durable.

Runtime State Still Matters

Compile-time capabilities cannot tell us when another thread has finished its work. BatchInner therefore also holds an atomic BatchRuntimeState, with states including Acquired, InQueue, WaitingSync and Applied, plus a separate WAL sync waiter.

These mechanisms answer different questions. Typestate controls whether the caller can append records or submit the handle to the commit interface. Runtime state tracks progress through the protocol, and the waiter records WAL completion. Resetting checks that the runtime state permits reuse; the outer handle also waits for outstanding WAL work before resetting or closing.

The intended commit contract requires non-owning pipeline pointers to stop accessing the allocation before commit returns. Outstanding WAL synchronisation can retain a clone of the shared waiter, rather than a pointer to the mutable records. These lifetime and synchronisation requirements still have to be upheld by the implementation: typestate alone is not a proof that the concurrent pipeline is safe.

Allocation Pointers Preserve Ownership

OwnedBatchPtr and OwnedIndexedBatchPtr are owning wrappers, not interchangeable raw pointers. Each originates from a boxed allocation and is responsible for reconstructing and dropping the correct box exactly once. NonNull alone provides neither ownership nor automatic destruction; those responsibilities come from the wrapper's implementation.

The ordinary wrapper owns a BatchInner directly. The indexed wrapper owns a larger IndexedBatchInner, which contains a BatchInner alongside an arena and indexes. Its batch_ptr() projects the address of the embedded batch field. This gives the pipeline access to the common batch representation while the indexed owner retains responsibility for the entire allocation. The projected pointer must never be treated as an independently owned Box<BatchInner>.

Both wrappers implement BatchAllocation, whose common operations expose the batch pointer and reset storage for reuse. A BatchObject can therefore preserve its allocation parameter while changing its state parameter. Sealing an indexed object produces BatchObject<Sealed, OwnedIndexedBatchPtr>; it does not convert the allocation into an ordinary batch or discard its indexes.

This is the reason for representing state and allocation separately at compile time. State-specific implementations determine which operations are available, while allocation-specific implementations determine how storage is accessed, reset and destroyed. The shared object does not need a runtime ordinary-versus-indexed tag to select those implementations.

Borrowing Across The Commit Lifetime

At the commit boundary, both sealed outer handles implement SealedBatch, exposing the common BatchInner pointer. The pipeline does not need to take ownership of either allocation type to process its records. The concrete owner stays with the caller and continues to determine how the complete allocation will eventually be reused or destroyed.

There are two lifetimes to respect here. The pipeline's access to the records must end before the owning allocation can be mutated or destroyed. WAL synchronisation may then remain outstanding through a separately shared completion waiter. The intended non-sync commit contract ends all pipeline access to batch memory before returning, while reset() and close() also wait for outstanding WAL completion before reusing the batch's state.

The Rust borrow at the commit interface keeps the caller's handle borrowed for the call, but the raw pointers used internally do not carry that borrow's lifetime. Keeping them within the permitted interval is an implementation obligation. A stable address makes those pointers usable; ownership keeps their allocation alive; typestate restricts the caller's operations; and runtime coordination establishes when access has finished. These mechanisms work together to support the batch lifecycle.

Bringing It Together

What began as a way to group write operations became a question of how to represent work throughout its lifetime. A batch needs to be mutable while it is being built, stable while the pipeline accesses it, and reusable only when that access has finished. Its representation has to carry those constraints alongside the records themselves.

For Ordinum, BatchObject<State, Allocation> brings those concerns together. The state parameter controls the capabilities available through the object, while the allocation parameter preserves the concrete ownership and storage behaviour. That separation lets ordinary and indexed batches use the same lifecycle abstraction without losing the information needed to manage their different allocations. The pipeline can operate on their common batch representation while ownership remains with the caller.

The useful boundary is between what the compiler can establish and what execution must establish. Rust can restrict which methods exist for a given state and preserve the allocation type across transitions. The commit protocol must still establish when pointers are no longer in use, when writes become visible, and when the requested durability has been reached. Making that boundary explicit gives us a clearer basis for implementing and reviewing the remaining pipeline work.

That is the main design lesson from Ordinum's write batches: memory ownership, API capabilities and commit progress each need their own representation, with precise rules connecting them. The write pipeline builds on those rules to coordinate many callers; the batch provides the unit of work whose storage and lifetime remain accounted for throughout.