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:
Before exploring the implementation, it helps to understand where batching fits into an LSM storage engine's write path.
There are two levels of batching to distinguish here. A write batch collects multiple operations submitted by a caller. Group commit allows the engine to process batches from multiple callers together, sharing commit overhead without making those callers part of one application-level transaction. A queue can hold waiting writers, while a leader coordinates work on behalf of a group of followers.
It is a good mental exercise to follow operations through the write path. Each component carries out its responsibility and passes work to the next stage while preserving the required ordering and visibility guarantees. Moving each write forward immediately is not always best for throughput: allowing writes to accumulate briefly can produce larger batches, but it also adds latency for the callers waiting on them.
With write-ahead logging enabled, the write path records incoming operations in the Write-Ahead Log (WAL) and inserts them into the memtable. The WAL provides a record that can be replayed during recovery, while the memtable holds the in-memory updates used to serve reads before they are flushed to sorted files.
Recording an operation in the WAL does not, by itself, mean it has reached durable storage. The durability guarantee depends on when the WAL is synchronised with storage and when success is reported to the caller. For writes that require this synchronisation before returning, group commit can share its cost across multiple callers.
Grouping Write Batches
For context, Batch A in the diagram below might contain the following operation records, shown in batch order. Each record identifies the operation and target column family, followed by the key and value lengths and their contents. Lengths are in bytes; the example keys and values use ASCII text.
| Operation type | Column family ID | Key length | Key | Value length | Value |
|---|---|---|---|---|---|
Put | 1 | 12 | item:7:stock | 2 | 25 |
Delete | 1 | 12 | item:7:offer | 0 | No value |
Put | 1 | 12 | item:8:stock | 3 | 100 |
Put | 1 | 12 | item:8:price | 5 | 19.99 |
Put | 2 | 14 | order:9:status | 7 | pending |
Delete | 2 | 13 | order:9:draft | 0 | No value |
Each Put sets the value associated with its key in the specified column family, while each Delete marks its key for deletion. The zero value length illustrates that the delete carries no value payload; whether its encoding includes a value-length field depends on the record format. These operations belong to the same batch and retain their order when the batch is processed.
Multiple incoming batches are grouped to share write overhead. The diagram highlights the two main responsibilities: 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 synced to 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.
How Ordinum groups batches and coordinates their progress through the write pipeline will be covered in a separate journal, Write Pipeline. For now, the important connection is that batching happens at two levels: a write batch groups individual operations, and the write pipeline can group multiple batches to share commit overhead. Understanding that relationship helps explain where a write batch fits into the wider write path.