WAL and durability

The write-ahead log (WAL) makes committed transactions survive crashes. Before a transaction counts as committed, its changes must be written to the WAL and flushed to disk.

The WAL principle

WAL record format

Each operation is stored as a framed record:

Linear buffer

The WAL area has a fixed size. Records are appended to it until it is full; then they move into a WAL segment, an extent of pages elsewhere in the file, and the WAL starts over:

Spilling into WAL segments

When the WAL fills, the database does not force a checkpoint. It spills the WAL into a WAL segment:

The header names up to 64 segments. Each entry holds the segment's seq, start page, page count, byte length, and whether it is sealed (no spill appends to it any more). The table also holds covered, the newest segment seq the snapshot covers, and the seq the next segment gets. A header that names WAL segments is written as format version 3, with minimum reader version 3, so a build that reads version 2 but not segments refuses the file with a version mismatch instead of missing the commits in its segments. Once a checkpoint covers every segment, as a clean close normally does, the header is written as version 2 again. Every header this version writes carries the magic KiteDB format 2\0: releases up to v0.2.18, which check a header only by its magic and checksum, read only its first slot and check no version, refuse these files (invalid magic number) instead of misreading them. This version opens the files of v0.2.3 to v0.2.18, and those earlier unreleased builds wrote in the old magic (a writable open rewrites both slots in the new one as its last step), except a header in the old magic that names WAL segments: its checksum, unlike the new one's, cannot tell a slot torn inside the segment table from a whole one.

Background checkpoints

A background checkpoint folds the log into a new snapshot while reads and writes continue. Automatic checkpoints run this way on the database's checkpoint thread. backgroundCheckpoint() runs one on the calling thread, after any running one ends, and returns after its install.

Durability guarantees

Durability is configurable with the syncMode option:

Fast writes (single-file)

Recommended profile for high write throughput:

• syncMode = Normal
• Commit from several threads: commits that arrive while others are written are written together, with one WAL write, one header write and (in Full mode) one fsync. This is always on; groupCommitEnabled has no effect, and no commit waits for others to join
• beginBulk() + batch APIs for ingest (with or without MVCC)
• The default 4 MB WAL is enough for heavy ingest: a full WAL spills into a WAL segment, and checkpoints run on the checkpoint thread without holding up commits. A larger walSize means fewer spills (each is a copy of the WAL and three syncs), and raises the floors of the checkpoint trigger (3/8 of the WAL), the segment limit (16 WALs) and the segment extent (2 WALs)

Crash recovery

On database open, the log (the WAL segments, then the WAL) is replayed to rebuild the delta:

When checkpoints happen

The in-memory delta takes about ten times the log's bytes, so the log budget bounds memory while checkpoints keep up: the default 128 MiB of log is about 1.3 GB of delta at most at the trigger, and writers that outrun checkpoints grow the log up to walSegmentLimit. A checkpoint briefly needs about twice that, for the delta it replays from the cut plus the live delta. To bound reopen replay time or memory, lower checkpointLogBudget. To checkpoint less often on a large database, raise checkpointLogRatio, at the cost of more memory; the budget caps the trigger either way. checkpointThreshold is deprecated and has no effect.

walSegmentLimit (default: twice the trigger, at least 16 WALs, at most four times checkpointLogBudget) bounds the bytes of WAL segments, and with them disk use and the delta's memory. The segment table bounds them too, at 63 extents (the 64th is kept for a checkpoint's cut): an extent is walSegmentSize, by default a sixteenth of the limit (from two WALs to 32 MiB, or two WALs if more), so the table holds about four times a limit of up to 512 MiB, and 2 GiB beyond. Writers wait only when the segments reach either: a writer that needs to spill then asks for a checkpoint (on the checkpoint thread, a run that starts after it asked; without the thread, one of its own) and waits for its install to free segments.

Before that, writers are paced. While a background checkpoint runs and the log is past the trigger, each commit, once it is done and holds no lock, waits its share of the time the room left below walSegmentLimit must last: the run's expected remaining time (its last run's duration, or twice its elapsed time before any run finished), spread over the log's growth. All writers share one schedule, so writers that outrun the checkpoint slow down instead of stopping at the limit for the rest of the run. A commit waits at most 100 ms, and no longer than the run: its end, installed or not, and closing the database end every wait. A commit can also wait, once per run, for the install, which holds the commit lock while it replays the last commits and frees the replaced delta: a time that grows with the delta. On the 1M-node, 10M-edge benchmark database with the default 4 MB WAL, one writer of 100-node transactions waited up to 3.6-4.6 s at the limit without pacing; with it, at most 100 ms per commit for pacing, and about 0.5-1 s once per run for the install. Blocking checkpoints (backgroundCheckpoint: false) pace no one, nor do reads, rollbacks or read-only handles. Any background checkpoint run counts, an application's backgroundCheckpoint() too, as long as automatic background checkpoints are on; with blocking or no automatic checkpoints nothing is paced. The limit stays the backstop: a run that takes much longer than the last still makes writers wait there.

Pacing holds no lock of the database's, but it waits inside the commit call. In Node the call is synchronous (there is no async commit), so a paced commit blocks the event loop for up to 100 ms, and a Kite's other calls wait for its commit. In Python the GIL is released, but the handle stays in use, so close() waits for a paced commit. A replica's catch-up applies each frame as a commit, so it may wait likewise, inside whatever its caller holds. Either way it is at most 100 ms per paced commit, in place of the stops of seconds at the limit. Up to 10 ms of the time since the last paced commit counts toward the next one's wait, so commits that are spread out (one per request, say) wait little or nothing; a writer committing in a tight loop waits its share.

Avoiding WAL overflow

A full WAL does not fail a write: it spills into a WAL segment, and a commit too large for an empty WAL goes straight to one. A write fails with WAL buffer full (WalBufferFull; WalFullError in Python) only when the WAL segments reach walSegmentLimit (or fill the segment table) and waiting for a checkpoint cannot help:

• Automatic checkpoints are off: spills continue up to the limit, then writes fail. Run checkpoint() before the limit, or raise walSegmentLimit (and walSegmentSize with it past what the table holds).
• Background checkpoints are off: automatic checkpoints are blocking, so the writer fails, and one runs once its transaction ends, by commit or rollback (after the back-off, if the last one failed).
• Open write transactions hold records in enough segments to fill the limit. No checkpoint can free those until the transactions finish: keep write transactions shorter, or raise walSegmentLimit.
• A blocking checkpoint, optimize, vacuum or resizeWal is waiting for the writer's own transaction to finish.
• The database is closing, or the checkpoint thread cannot start.
• The checkpoint run that answered the writer (one that started after it asked) freed no segment space.

While the last automatic checkpoint failed, a writer at the limit fails instead of waiting, with Checkpoint failed, and the WAL segments are full: ... (CheckpointFailed; Python raises CheckpointError, a KiteError subclass). With the checkpoint thread it asks for another, which the thread runs after its back-off (1 s, doubling to 60 s after each failure in a row; any checkpoint that succeeds meanwhile, such as the caller's own, ends it); without it, with background checkpoints inline, writers fail during the back-off and run one themselves after it; with background checkpoints off, writers fail until a checkpoint succeeds, and the blocking one that runs once a refused writer's transaction ends (after the back-off) is one. checkpointError() (checkpoint_error() in Python) returns the checkpoint's error. A panic in a checkpoint run is reported the same way, and the thread ends. Since such a panic may strike between writes that keep memory and disk in step, the handle then refuses writes (The database refuses writes until it is reopened: ..., WritesRefused), as it does after a panic in a commit, a spill, a checkpoint, optimize, vacuum or resizeWal that its caller catches (as the Python bindings do). Reads go on, closing persists nothing, and reopening the database recovers every acknowledged commit from disk. A rollback never waits or fails for log space: its record is not needed, since recovery drops a transaction without a commit record.

Next steps

• Single-file format: how the WAL and its segments fit in the file layout
• Snapshot and delta: what a checkpoint produces
• MVCC and transactions: how transactions work