Write Path

Write Path

At a high level, a database has two fundamental responsibilities: reading and writing data. The complexity lies in making those operations fast, efficient and reliable while preserving the guarantees the database provides.

In the previous journal, Write Batches, we outlined how Ordinum represents and collects write operations into batches to amortize the cost of committing them. We also briefly introduced how those batches move through the write pipeline.

Before exploring the implementation, it is useful to establish why batches need coordination in the first place. Batching lets us process several operations together, but it does not resolve how concurrent batches should be ordered, written and made visible.

Ordinum's commit process must preserve the following invariants:

1. Each batch is assigned a contiguous sequence number range covering its operations. These ranges establish the order of batches within the write pipeline.
2. Before application, sufficient space must be reserved in the relevant memtables. Where necessary, memtables and the WAL must be rotated to accommodate incoming writes.
3. Each batch must be appended to the WAL in sequence order, with WAL rotation coordinated with the memtables receiving those writes.
4. Batches may be applied to memtables in parallel, but visibility must advance through a contiguous prefix of completed batches. A batch cannot become visible until every preceding batch has finished applying.

This gives us room to perform work concurrently while preserving a single, ordered view of committed writes.

Designs Explored

Before settling on Ordinum's write pipeline, we explored whether we could organise this work differently. The aim was to reduce coordination between writers while retaining parallel memtable application.

One approach was to give each incoming batch a ticket establishing its position in the commit order. Each writer could then perform its work independently, with completed tickets allowing visibility to advance. However, assigning a position does not resolve the dependencies behind it. We still need to coordinate sequence ranges, WAL order, memtable reservations and rotation. We also need to track which batches have finished applying so that publication stops at the first incomplete batch. Once those requirements were accounted for, the ticket mechanism had become another representation of an ordered commit queue.

Before settling on Ordinum's write pipeline, we explored whether we could organise this work differently. The aim was to reduce coordination between writers while retaining parallel memtable application. Each approach, however, still had to satisfy the same invariants.

Ticket-based ordering

One approach was to give each incoming batch a ticket establishing its position in the commit order. Writers could then perform their work independently, with completed tickets allowing visibility to advance.

However, a ticket only establishes order. It does not coordinate sequence number assignment, memtable reservations or WAL rotation and append order, as required by invariants 1–3. We would also need to track completed batches and stop publication at the first incomplete ticket to satisfy invariant 4.

Once those requirements were accounted for, the ticket mechanism had become another representation of an ordered commit queue.

Cooperative writers

We also considered allowing writers to leave work for other callers to complete. An active writer could process several waiting batches, sharing some of the coordination cost.

This could satisfy the invariants, but it required explicit responsibility for carrying out the ordered work in invariants 1–3, and for signalling completion after publication under invariant 4. We would need to define who performs each stage, how that responsibility is transferred and when waiting callers can return.

In Ordinum, the caller also retains ownership of its batch. Delegating work therefore requires keeping that batch alive until all outstanding access has finished. As we added these ownership and completion rules, the approach began to resemble a leader coordinating a group of waiting writers.

Commit epochs

Another possibility was to collect batches into epochs, reserving their resources together and publishing each epoch once all its members had finished applying.

An epoch could provide a unit for coordinating invariants 1–3, while its publication barrier would preserve invariant 4. However, one slow batch would delay publication of the entire epoch, including completed batches preceding it.

That barrier is stricter than invariant 4 requires. Allowing an earlier completed portion of the epoch to become visible would require tracking and publishing a contiguous completed prefix—the same ordering problem we were already trying to solve.

Concurrent WAL copying

We also explored separating WAL space reservation from copying batch contents into that space. Reserving regions in sequence order could allow writers to fill them concurrently.

However, invariant 3 requires more than assigning ordered offsets. A later region might be filled while an earlier region remains incomplete. We would need to track those gaps and establish how they affect writing, synchronisation and recovery. Invariant 2 also requires those reservations to remain valid across WAL and memtable rotation.

This approach could be made to work, but it would move additional coordination into the WAL rather than remove it.

Where the approaches converged

These explorations helped identify the dependencies that remained regardless of how we represented the work:

Once a batch's resources have been prepared, memtable application can proceed in parallel. Publication must still wait for every preceding batch. Representing that dependency through tickets, cooperating writers or epochs does not remove it.

For Ordinum, the alternatives we explored did not establish a clear enough advantage to justify their additional machinery. That brought us back to two existing approaches to coordinating concurrent writers: the writer-group approach in RocksDB and the commit pipeline in Pebble.

Ordinum's commit pipeline

We arrived at a commit pipeline closely resembling Pebble's and so realising that, we were able to draw heavily on the code implementaion that Pebble's commit pipeline used. The design separates the work that establishes batch order from the work that can proceed concurrently, then coordinates publication so readers observe writes in sequence order.

A batch moves through five stages:

1. Reserve — Acquire admission to the pipeline, bounding the number of batches in flight.
2. Prepare — Under the preparation mutex, assign the batch's sequence number range, enqueue it, resolve and reserve its destination memtables, and append it to the WAL. Rotate memtables and the WAL where required.
3. Apply — Insert the batch's operations into the prepared memtables without holding the preparation mutex. Multiple writers can perform this stage concurrently.
4. Publish — Advance the visible sequence number through the completed prefix of the commit queue, stopping at the first batch that has not finished applying.
5. Complete — Return once the batch has been published and, where synchronous durability was requested, its WAL contents have been synchronised.

WAL synchronisation can overlap with application and publication; a synchronous write waits for both visibility and durability before completing.

This structure is representative of Pebble's commit pipeline: ordered preparation, parallel application and ordered publication. Ordinum follows that coordination model, with additional considerations around batch ownership, lifecycle and column families.

In particular, a batch may touch several column families, each with its own memtable and capacity requirements. Preparation must reserve every destination and retain the mappings needed during application, while publication makes the entire batch visible at a single boundary.

We will work through these stages in order, examining the implementation and the decisions needed to preserve those guarantees.