Skip to content

Internals

Snapshot and delta

The core storage model

KiteDB separates storage into two parts: a snapshot (immutable, on disk) and a delta (mutable, in memory). Reads merge the two, writes only touch the delta and the write-ahead log, and a periodic checkpoint folds the delta into a new snapshot.

The model

Database state

Snapshot

on disk
  • Immutable
  • CSR format
  • Memory-mapped

Delta

in memory
  • Changes since the last checkpoint
  • Fast writes
  • Merged on read

WAL

on disk

Write-ahead log behind the delta. Every commit is appended here first (a full WAL spills into WAL segments), and the log is replayed into the delta after a crash.

Snapshot

The snapshot is a point-in-time image of the entire database. It's stored in CSR format and memory-mapped directly from disk.

Key properties:

  • Immutable – once written, never modified. Safe for concurrent reads.
  • Memory-mapped via mmap(), so the OS page cache handles caching. Uncompressed sections are read in place; compressed ones are decompressed once and cached.
  • Compressed – zstd compression reduces disk usage by ~60%.
  • Complete – contains all nodes, edges, properties, and indexes.

Delta

The delta holds all changes since the last snapshot. It's a collection of in-memory data structures optimized for both reads and writes.

Delta state

struct DeltaState

Main fields. Edge changes are kept in both directions.

created_nodes
New and recreated nodesHashMap<NodeId, NodeDelta>
deleted_nodes
Tombstones; they keep hiding a recreated node's old snapshot copyHashSet<NodeId>
modified_nodes
Label and property changesHashMap<NodeId, NodeDelta>
out_add / out_del
Outgoing edge changesHashMap<NodeId, BTreeSet<EdgePatch>>
in_add / in_del
Incoming edge changesHashMap<NodeId, BTreeSet<EdgePatch>>
key_index
Key lookupsHashMap<String, NodeId>

How reads work

Every read operation merges snapshot and delta:

Reading a node

  1. 1

    Is node_id in delta.created_nodes?

    Yes: return the node from the delta (new or recreated node)

  2. 2

    Is node_id in delta.deleted_nodes?

    Yes: not found (deleted)

  3. 3

    Does the snapshot have this node?

    No: not found (never existed)

  4. 4

    Merge the snapshot with delta.modified_nodes

    Then: return the combined result

Edge traversals work the same way: scan the snapshot's edges, skip the ones deleted in the delta or touching a deleted (or recreated) node, and add new ones from the delta.

How writes work

Writes go to two places:

Transaction commit

  1. 1WALAppend records (durability)
  2. 2DeltaUpdate in-memory state (visible to reads)

Normal writes never modify the snapshot.

Checkpoint: merging the delta into the snapshot

Periodically, KiteDB creates a new snapshot that incorporates all delta changes. This is called a checkpoint.

Checkpoint process

1Read the current snapshot
2Apply the changes committed up to the checkpoint
3Write a new snapshot (CSR, compressed)
4Update the header to point to the new snapshot
5Drop the log it covers; later commits stay in the delta

Automatic: when the log reaches half the snapshot's size (at least 3/8 of the WAL, at most 128 MiB)

Manual: db.checkpoint()

During a checkpoint, reads continue against the old snapshot and delta. An automatic checkpoint runs on the database's checkpoint thread, so writes continue too: it builds the new snapshot from the changes committed up to its cut, and replays the commits made since over it before the switch. The switch to the new snapshot and delta is atomic. The delta takes about ten times the bytes of log it holds, so checkpointLogBudget (default 128 MiB of log) bounds its memory. See background checkpoints.

Why this works well

PropertyHow it's achieved
Fast readsSnapshot is mmap'd. OS caches hot pages. Delta is small.
Fast writesWAL append + memory update. No disk seeks.
Crash safetyWAL survives crashes. Replay rebuilds delta.
Concurrent readsSnapshot is immutable. MVCC handles delta visibility.

Next steps