How application operations are grouped into the transactions the journal records, how they wait in memory, and when they are appended to the journal pages and folded.

Status: settled apart from the open questions at the end; kladde-rs implements it as described here.

Transactions are normative — they are the unit of atomicity an application builds on. Batches are not: they are an implementation’s mechanism for turning a long run of operations into reasonably sized transactions, and an implementation is free to offer something else or nothing at all. Both exist only to affect how mutations are persisted; the accompanying in-memory mutations are always immediate.

From the buffer on, this page is the design of the reference implementations, not one way among several to meet the format. kladde-rs and kladde-cpp each keep exactly one buffer of operations and the cursors into it described below, and append and flush by exactly the rules in Flush triggers. A departure — a second buffer, copying between spans, another trigger — is a deviation: it is recorded with its reason, in the implementation notes for kladde-rs and in kladde-cpp for kladde-cpp, and proposed as a change to this page if it is better, rather than taken as a free choice.

Three mechanisms over one journal

mechanismeffect on the journalwhat it is forwhen to use
transactionwraps a sequence of operations in a single journal transaction, appended atomically when the caller commitscorrectness: either all or none of the operations are persisted, so a crash can’t expose an invalid intermediate statewhenever intermediate state would be invalid
batchcuts a long sequence of operations into the largest pieces that fit in what is left of the journal’s page budget, respecting nested transactions, and wraps each in a transactionoptimization: fewer and fuller journal writes, while keeping the journal within its budgetwhen many operations happen at once with valid intermediate states — a large import, a paste
bare operationrecorded as its own transactionsimplicity: changes persist immediatelysingle mutations, prototyping

Transactions enforce correctness. In complex data types, one semantic operation often produces several journal records — appending to a vector splices the element in and rewrites the count — and interrupting between them leaves a sequence that does not decode. The same happens in application code, where a transition between two valid states sometimes passes through invalid ones.

Batches are an optimization, and a necessary one. Kladde’s promise to persist every mutation immediately carries a small unavoidable per-transaction overhead. That is usually worth it, but it adds up when an action triggers a large or unbounded burst — and for such bursts, per-operation durability buys little anyway. It is tempting to wrap the burst in a transaction instead, but very large transactions perform poorly, because the whole transaction is held in memory until it ends, and the journal pages, and therefore the file, must then temporarily grow in proportion to the number and size of the operations. A batch is the middle ground: the backend decides how to divide the sequence, respecting any explicit transaction inside it, so that each piece fills what is left of the journal’s budget as far as the transaction boundaries allow.

Recommendations

  • For most application code, reach for a batch or a bare operation. Batches are cheaper for multiple operations, have no I/O overhead over a bare operation even for one, and cost a handful of instructions and no allocation. But remember that batches delay persistence: they are only guaranteed committed when ended, so holding one open for a long time defeats the point of immediate persistence.
  • Use transactions when application logic requires atomicity, and keep them short. Needing a very long transaction almost always means either that the application’s state transitions pass through too many invalid intermediate states, or that the wrong data type was chosen — a vector where a rope or an ordered tree belongs. When atomicity is genuinely required for a large mutation, it can usually be imposed at the application level instead: build the value in memory, outside any handle, then insert it in one operation, which encodes it into one buffer and splices it in.
  • For a long sequence where some parts need atomicity, use a batch with a few smaller transactions inside. This is the pattern the design is arranged around.

Nesting

Transactions and batches nest arbitrarily, so that a container’s push can open a transaction without caring whether its caller already did. The backend flattens the nesting, because the journal only deals with a flat sequence of transactions.

↓ outer; inner →transaction in a …batch in a …
… transactiononly outer transaction survivesonly the transaction survives (shouldn’t usually occur)
… batchboth surviveonly outer batch survives
  • Transaction in a transaction ⇒ outer. The inner one is meaningless; its atomicity is already enforced. Expected often in composable code.
  • Transaction in a batch ⇒ both. The inner transaction enforces atomicity, so no cutting point may lie inside it. Expected often.
  • Batch in a batch ⇒ outer. The inner one is meaningless; deferral is already in effect. Fine, but not useful.
  • Batch in a transaction ⇒ the transaction. The inner batch is meaningless, since the transaction already forces the operations to commit as one group. A potential code smell: batches are for large or unbounded sequences, transactions should be short, so this combination implies a long chain of state transitions with only invalid intermediate states.

One buffer and three cursors

Every operation recorded since the last flush lives in one in-memory buffer ops, in the order it was recorded, whether it is already in the journal pages or not. Between two flushes, the operations form a single stream: some prefix of it has been appended to the journal pages, the operations on top of that are a batch’s ready run, and those on top of that belong to the transaction that is still open. So everything that happens between two flushes either appends to the buffer or moves a boundary between these spans; nothing is ever copied from one span to another.

The flush folds the operations the journal pages hold from this buffer, not from the pages, which only recovery reads back. Recovery decodes the journal’s complete transactions into the buffer, and open folds them before it returns (see opening a file).

In kladde-rs, the buffer is a VecDeque of records, beside a byte arena, also a VecDeque, that holds their payloads. Positions in both are counted from the start of the session rather than from the buffer’s front, so that discarding the folded prefix after a flush moves the front and nothing else: no record moves, and every position held elsewhere — a record’s payload, a pending fragment of the flush pointing into the arena — stays valid. A journal’s cuts are positions in it too: a paste names its cut by distance among the cuts of its journal, which the records keep in order, so no cursor moves them.

Three cursors, front <= committed_cursor <= ready_cursor <= end, divide the buffer into three spans:

  • committed := ops[front..committed_cursor] — appended to the journal pages since the last flush: what the next flush folds;
  • ready := ops[committed_cursor..ready_cursor] — a batch’s operations, held back to be appended as one transaction;
  • transaction := ops[ready_cursor..end] — the operations of the open transaction.

Each cursor also carries the encoded size of the records before it, so that the encoded size of any span is a subtraction, and deciding whether a span fits costs constant time. The journal’s length prefix needs a transaction’s size before its first byte is written anyway.

Moving the cursors is all that recording, appending, and flushing do:

  • Recording an operation appends it at end.
  • Appending a span to the journal pages encodes it as one transaction, writes it, and moves committed_cursor to the span’s end.
  • A flush folds committed and moves front to committed_cursor.
  • Discarding operations — a transaction that failed halfway and is rolled back, or one the application abandons — moves end back to where they began.

The backend’s state holds the depths of the open scopes and the cursors that are not implied by them:

enum TransactionState {
    Immediate,
    InBatch              { batch_depth: NonZero, committed_cursor: Cursor },
    InTransaction        { transaction_depth: NonZero, batch_depth: u32,
                           committed_cursor: Cursor },
    InTransactionInBatch { transaction_depth: NonZero, batch_depth: NonZero,
                           committed_cursor: Cursor, ready_cursor: Cursor },
}

transaction_depth and batch_depth count begins minus ends, with an implied zero in any variant where they are absent. front and end belong to the buffer, and the table below gives the cursors each state implies.

stateDiagram-v2
    [*] --> Immediate
    Immediate --> InBatch: begin_batch
    Immediate --> InTransaction: begin_transaction
    InBatch --> Immediate: end_batch when<br> batch_depth == 1
    InBatch --> InTransactionInBatch: begin_transaction
    InTransaction --> Immediate: end_transaction when<br> transaction_depth == 1
    InTransactionInBatch --> InBatch: end_transaction when<br> transaction_depth == 1

Why four states and not three. InTransaction carries a batch_depth that may be positive, so it overlaps with InTransactionInBatch in depth alone. What distinguishes them is which scope was opened first. InTransactionInBatch is batch outside, transaction inside — the useful nesting, where ending the transaction returns to InBatch and persistence stays deferred. InTransaction { batch_depth > 0 } is transaction outside, batch inside — the code-smell nesting, where the batch is subsumed and its depth is tracked only so that its end can be matched.

Transitions in detail

The error cells are all the same mistake: ending one scope while a scope nested inside it is still open — interleaving rather than nesting. An implementation should make that unrepresentable at the API level rather than checking for it.

ImmediateInBatchInTransactionInTransactionInBatch
transaction_depth0 (implicit)0 (implicit)> 0> 0
batch_depth0 (implicit)> 0any> 0
committed_cursorend (implicit)explicitexplicitexplicit
ready_cursorend (implicit)end (implicit)committed_cursor (implicit)explicit
begin_transaction()InTransaction { t: 1, b: 0 }InTransactionInBatch { t: 1, .. }transaction_depth += 1transaction_depth += 1
end_transaction()errorerror−1; at 0: Immediate if batch_depth == 0, else error−1; at 0: InBatch
begin_batch()InBatch { b: 1 }batch_depth += 1batch_depth += 1batch_depth += 1
end_batch()error−1; at 0: Immediatebatch_depth -= 1−1; at 0: error

The implied cursors are invariants at every operation boundary, not just labels: in Immediate, everything recorded is in the journal pages, and in InBatch, everything not yet appended is the batch’s.

Flush triggers

Keep the journal within its page budget. A transaction that would not fit in what is left of the budget is preceded by a flush, and only a transaction too large for the budget on its own exceeds it, followed by a flush at once.

The budget is a number of journal pages, B, and a transaction fits if the journal’s stream, with the transaction appended, ends within B pages, counting each of the journal’s payload pages as one. Each journal page holds page_size − 8 bytes of the stream, the rest being its trailer, and a transaction of n record bytes takes n plus its length prefix plus its 4-byte crc. The writer takes the next journal page only once the stream continues past the current one, so fitting within B · (page_size − 8) stream bytes is fitting within B pages. A transaction’s size is estimated with its bytes inline, which for large bytes is about the payload pages they will take. A transaction that does not fit even into an empty journal is overlong.

Whenever operations close — a bare operation recorded in Immediate or InBatch, or the outermost transaction ending, InTransaction → Immediate or InTransactionInBatch → InBatch — let X be the operations that just closed, ops[ready_cursor..end], and apply:

  1. The candidate is ops[committed_cursor..end]: X alone outside a batch, where ready is empty, and ready followed by X inside one, to be appended as one transaction.
  2. If the candidate does not fit, the batch is cut before X: append ready as one transaction if it is not empty, which it always fits, and flush, unless the journal is empty. The candidate is now X alone, in an empty journal. A paste in X that names a cut of the journal just folded becomes a Splice of its value’s bytes, since that cut has ended (moving values), and X’s size is computed again.
  3. Inside a batch, a candidate that fits stays in memory as the new ready, which the batch holds back until its next cut or its end.
  4. Otherwise, the candidate is appended as one transaction, and if that took the journal past its budget, flush again. Only an overlong X can do that, since step 2 left it an empty journal.

The other triggers:

  • The outermost batch ends, InBatch → Immediate: append ready if it is not empty. It fits, so no flush follows.
  • An explicit flush(): append ready if it is not empty, then flush — on an empty journal too, since a flush also consolidates. An open transaction stays in the buffer, past committed_cursor.
  • A flush when the application is idle: flush_if_journal_exceeds(fraction) appends ready and flushes if the journal pages then hold at least that fraction of the budget, and does nothing otherwise; the check is a subtraction of two cursors. An interactive application calls it from its event loop’s idle callback, so that the automatic flush, whose fsync blocks the mutating call that triggers it, rarely fires in the middle of a gesture. The fraction should stay well above zero: an idle flush ends the journal, and with it the cuts its records made.
  • Opening a file: kladde-rs folds a non-empty recovered journal before open returns, since reads see the flushed state only. That also keeps the journal’s rule that nothing is appended to a non-empty recovered journal, and no state outlives open.

So an overlong transaction is flushed twice, once before it and once after it, the first unless the journal was empty; and a batch is always cut at the last boundary at which its run still fits, which lies between two closed transactions or operations, never inside a transaction.

The journal’s budget

B is 2% of the sequence’s length in whole pages, at least 2 and at most 10, unless the application fixes it, and the writer computes it from the length as it stands whenever it checks a transaction against it. It is a whole number of pages, since a journal page once taken costs a page of the file however little of it is used.

A small budget keeps the file close to its content. At a flush, the journal it folds and the previous one, still the fallback, both occupy pages, and the pages a flush frees become reusable only after the next flush; a budget of B pages thus keeps up to about 2B pages of journal beside the content. A budget of 256 pages, a megabyte, made the files of drawings of 40 KB to 1 MB up to 16 times their content, and a budget sized to them kept them within 1.2 to 2.2 times.

Every flush is a chance to consolidate, so flushing often costs little beyond the flush’s fsync: a flush folds a journal of a few pages in one to two milliseconds, within a frame of an interactive application, where a journal of a megabyte stalled the edit that triggered it for 46 to 77 ms.

The floor of 2 pages keeps a small file from flushing at every few edits: a budget of 1 page flushed the same drawings two to four times as often as 2 to 4 pages and made their files no smaller. The ceiling of 10 pages keeps a large file’s journal, and with it the pages it holds and the time a flush takes, bounded; a file of tens of megabytes gains from a longer journal only fewer flushes, which an application that wants them can have by fixing the budget.

Payload pages

When a transaction is appended, the bytes of each of its Writes and Splices that carries at least payload_threshold bytes, 2 KB, are written into payload pages first, and the transaction names them rather than holding them. The decision falls at the append, not when the operation is recorded, because the records of an open transaction or a batch’s ready run may still be discarded, and the cuts that an application holds name records by their number in the buffer, which splitting a record there would change. So the buffer keeps each record as it was recorded, its bytes in the arena, and records beside the arena which runs of it also lie in a payload page, at which page, offset and checksum; the encoder writes such a record as one record per run, and the flush maps the runs onto the pages. Nothing above the store sees a difference: a container hands the store its bytes as before.

  • The bytes go into the journal’s open payload page as far as it has room, and the rest into new pages, a page’s worth at a time; a last part shorter than the threshold that would open a page stays inline in the journal, in a record of its own. The pages a transaction touched are written whole, framed with the journal’s epoch, before the transaction is appended, and the open page is written again whenever a later transaction of the journal appends to it.
  • A record whose bytes are cut into runs becomes one record per run, the first removing what the record removed and the rest removing nothing at the cursor, delta 0; a Write becomes such splices too, the first removing what it overwrote, so that it still makes one cut, and a paste of the overwritten value still names one.
  • Payload pages come from the reusable pool, lowest first, as journal pages do, but leave its last page alone, growing the file instead: a large transaction is followed by a flush, which seals only if a reusable page is left for the next journal to begin in, and without its seal that flush could not commit on a worker, and a lost header would lose what was appended after it.
  • Payload pages count toward the budget, so a transaction with more payload pages than the budget is overlong: preceded by a flush if the journal is not empty, and followed by one at once, which adopts its pages and writes a header and a leaf or two. The budget so bounds how much content waits for a flush to be durable under a power cut, as well as the journal’s share of the file.
  • A transaction that is abandoned after its pages were written leaves them in no world: they return to the pool, and the bytes it added to the open page are dead from the start. A payload page that cannot be written fails the transaction and poisons the store, as a journal append that cannot get a page does.

The threshold is about half a page, and unmeasured: a payload page holding r bytes costs a page write now and leaves 4081 − r bytes of slack until an append or consolidation fills it, where inline bytes cost r in the journal and r again in a data page the flush shares with other content. Creating a file of 4.26 MB, one splice of the whole drawing, then takes four journal pages besides its payload pages, and the file comes out at 1076 pages, within three pages of a consolidated copy, where with every byte in the journal it took 2139.

Why ready always fits

ready only becomes longer in step 3, which checked that it fits after what the journal pages already hold. Nothing else is appended while a batch holds a ready run, since every closing operation inside the batch either joins ready or cuts the batch, and the cut appends ready first. So what the journal pages hold does not change until ready itself is appended, and ready still fits then.

Why flush first

A flush before the append leaves no journal page behind that only the start of an overflowing transaction occupies. Appending first and flushing once the journal is over budget would end every journal with such a page, nearly empty; and at the moment of a flush, the journal it folds and the previous one, still the fallback, are both off limits, so that it would cost two pages at a time.

It costs nothing. The operations of X are already in the buffer, and their encoded size is known from the cursors, so deciding before the append is as cheap as deciding after it. A flush folds only committed, so X waits in the buffer past committed_cursor and is appended to the next journal; only the order of the two steps changes.

The flush after an overlong transaction keeps a long journal from lingering: the journal is back within its budget as soon as the operation that exceeded it returns.

The budget bounds the file, not memory. An open transaction is held in memory in full, whatever the budget, because nothing can fold an unfinished transaction; a huge transaction costs memory in proportion to its size, and journal or payload pages in proportion too once it is appended.

Consequence for write-phase state

A flush may run while operations are still in the buffer past committed_cursor: the X that step 2 holds back, or, at an explicit flush(), an open transaction. The write-phase state — the sequence’s length and the journal’s cuts — describes them as well, so a flush leaves it as it was, and the flush folds only the records before committed_cursor, whose positions refer to the sequence as it stood before the held-back ones.

Discarding operations moves the length and the cuts back to what they were where the discarded operations began.

Checkpoint versus commit

Decided: a checkpoint never splits a commit — see the journal.

A checkpoint is a flush triggered by resource pressure, and a commit is a transaction boundary the recovered state may snap to. The open question was whether a checkpoint could fold part of an unfinished transaction, to bound the memory the transaction holds. It cannot: the header it committed would describe a state inside the transaction, and undoing that part on recovery would need a mechanism the format does not have. So every flush folds complete transactions only, and the memory an open transaction holds is bounded only by keeping transactions short.

What remains is that application authors need never call flush(): the operation whose transaction would not fit in the journal’s budget flushes automatically. Two consequences follow:

Flush needs only shared access to the backend. The auto-checkpoint fires from inside a mutating call, which holds no exclusive reference to the whole structure. This is safe: handles hold positions in the sequence, which a flush does not change, since it rewrites only where the sequence’s bytes lie on file. Note that it is a reentrant call, so no write path may hold an interior borrow across a callback.

The trigger belongs at operation boundaries, not at append time. A check on append can fire between two records of one logical mutation. An operation is the natural atomic unit, being the smallest thing an application author perceives as one change.

A flush off the caller’s thread

An automatic flush that sealed its journal may hand its fsync and its header write to a thread of their own, and the mutating call that triggered it then returns without waiting for the disk. Folding a journal and writing a flush’s pages take well under a millisecond for files of the sizes kladde is meant for, while the fsync takes milliseconds on an SSD and more on a slow disk, which an interactive application feels as a stall in the middle of a gesture. So the calling thread seals, folds, places and writes the pages as before, and a worker does what remains: the fsync, then the header write. The application goes on appending to the next journal meanwhile, which the seal makes reachable from either header, so an application crash before the header is written loses nothing that returned. Doing it is optional; the format requires only the seal, and a flush that runs entirely on the calling thread writes the same file.

The worker shares nothing with the calling thread but the file, through a second handle to it, and one hand-over:

  • The next flush waits for the worker before it seals, and so do an explicit flush, before it returns, and closing the store. One commit is in flight at a time.
  • The pages the commit before freed become reusable only when the worker reports, since its fsync is what retires the world that held them (the reuse rule); until then neither the next journal nor anything else may take them.
  • A flush that cannot seal syncs on the calling thread: without a seal, transactions appended during the fsync would belong to a journal only the unwritten header names. A flush seals only where a reusable page can start the next journal, since a page added at the end of the file before the flush’s own pages would keep the file from being truncated to them.
  • A failure on the worker poisons the store when it is reported, at the next flush that waits for it, as a failure on the calling thread would at once. Reads do not wait: the pages they read are in the file already, synced or not. A failure reported only as the store is dropped has nobody left to tell, and is lost, which is no worse than a power cut at that moment.
  • A session’s first sealing flush syncs the page it seals to before appending the seal, as the specification requires; that one extra fsync per session runs on the calling thread.

An explicit flush() keeps its meaning — everything before it is durable when it returns — by waiting; only the flushes that mutations trigger run their commit off the calling thread. kladde-rs offers this behind an option, off by default, until the Inkscape demo has shown whether the idle flush of flush triggers already keeps the stall out of gestures.

Open questions

  • The journal’s page budget: whether it should adapt to an application whose transactions routinely exceed it.