The core insight: What if your database never forgot anything, and you could query any point in its history as fast as querying the present—without the storage exploding?
SirixDB is a bitemporal node store that makes version control a first-class citizen of the storage engine itself. Every commit creates an immutable snapshot. Every revision is queryable. And unlike naive approaches that either copy everything (git-style) or maintain expensive logs (event sourcing), SirixDB achieves this through structural sharing and a novel sliding snapshot versioning algorithm.
Traditional approaches to temporal databases must choose between conflicting goals:
┌─────────────────────┐
│ FAST READS │
│ (single lookup) │
└──────────┬──────────┘
│
Trade-offs: │
│
┌──────────────────────────┼──────────────────────────┐
│ │ │
▼ ▼ ▼
┌─────────────┐ ┌─────────────────┐ ┌─────────────┐
│ FAST WRITES │ │ LOW STORAGE │ │ BOUNDED │
│ (append Δ) │ │ (share pages) │ │ READ COST │
└─────────────┘ └─────────────────┘ └─────────────┘
• Full snapshots: Fast reads, but O(n) storage per revision
• Delta chains: Compact, but reads degrade to O(revisions)
• Periodic snapshots: Bounded reads, but write spikes during compaction
SirixDB’s answer: The SLIDING_SNAPSHOT algorithm—formally verified—achieves all three without periodic compaction spikes. See MVCC & Versioning.
| Feature | What it means | Why it matters |
|---|---|---|
| Temporal | Every revision preserved | Git-like history for your data |
| Append-Only | No in-place updates | No WAL needed, crash-safe by design |
| Copy-on-Write | Modified pages copied, unchanged shared | O(Δ) storage per revision |
| Structural Sharing | Unchanged subtrees reference existing pages | Billion-node docs with small revisions |
| Log-Structured | Sequential writes only | SSD-friendly, no random write I/O |
SirixDB stores trees of nodes, not blobs of documents. This isn’t an implementation detail—it’s a fundamental design choice with profound implications.
Most document databases (MongoDB, CouchDB, etc.) treat a document as an opaque blob: store it, retrieve it, replace it. SirixDB takes a radically different approach—it understands the structure of your data.
┌────────────────────────────────────────────────────────────────────────────┐
│ Document Store vs. Node Store │
├────────────────────────────────────────────────────────────────────────────┤
│ │
│ Document Store (MongoDB, etc.) Node Store (SirixDB) │
│ ────────────────────────────── ───────────────────── │
│ │
│ ┌─────────────────────────┐ Each node stores pointers: │
│ │ { "user": "alice", │ ┌─────────────────────────────┐ │
│ │ "orders": [ │ │ parentKey │ │
│ │ { "id": 1, ... }, │ │ firstChildKey, lastChildKey │ │
│ │ { "id": 2, ... }, │ │ leftSiblingKey, rightSibling│ │
│ │ ...10000 orders... │ │ childCount, descendantCount │ │
│ │ ] │ └─────────────────────────────┘ │
│ │ } │ │
│ └─────────────────────────┘ ┌────────┐ │
│ ↓ │ root │ │
│ Stored as ONE blob └───┬────┘ │
│ Updated as ONE blob ┌──────────┴─────────┐ │
│ Limited by max doc size ▼ ▼ │
│ ┌───────────────┐ ┌───────────┐ │
│ SirixDB Node Encoding: │ "user":"alice"│ ◄──► │ "orders": │ │
│ (object fields are FUSED │ OBJECT_NAMED_ │ │ OBJECT_ │ │
│ name+value nodes) │ STRING │ │NAMED_ARRAY│ │
│ parent └───────────────┘ └─────┬─────┘ │
│ ▲ value inline; ┌─────────┼────────┐ │
│ │ no child node ▼ ▼ ▼ │
│ left ◄──┼──► right ┌───┐ ┌───┐ ┌───┐ │
│ │ │[0]│◄──►│[1]│◄──►│...│ │
│ ┌─────┴─────┐ └─┬─┘ └─┬─┘ └───┘ │
│ ▼ ▼ ▼ ▼ │
│ first last {...} {...} │
│ child child O(1) navigation in any │
│ direction. No size limit │
└────────────────────────────────────────────────────────────────────────────┘
Why this matters:
| Aspect | Document Store | SirixDB Node Store |
|---|---|---|
| Size limits | 16MB (MongoDB), 1MB (DynamoDB) | Unlimited—nodes stored independently |
| Update granularity | Replace entire document | Write only changed nodes |
| Query efficiency | Load doc, filter in app | Navigate directly to target nodes |
| Memory footprint | Entire doc in memory | Stream nodes, never load full tree |
| Versioning granularity | “Document changed” | “These specific nodes changed” |
| Diff precision | “Something’s different” | Exact path to every modified node |
Real-world implications:
No artificial document splits: A 100GB JSON dataset with millions of records? Store it as one logical resource. No need to shard by arbitrary boundaries.
Surgical updates: Change one field in a deeply nested object? Depending on the versioning type, SirixDB writes just that node plus the modified path through the page index structure. If node hashing is enabled, the path to the document root is also updated to reflect the new rolling hash. The document store rewrites everything.
Efficient streaming: Process a billion-node tree without ever holding the full structure in memory. Navigate node-by-node.
Fine-grained history: “Show me exactly which fields changed in the last 100 commits” is a fast index lookup, not a document-diff operation.
Partial materialization: Need just one branch of a huge tree? Fetch and reconstruct only that subtree. The rest stays on disk.
Note on child lookup complexity: While navigation to parent, first/last child, and siblings is O(1), finding a specific child (e.g., the 5000th element in an array) requires O(n) sibling traversal. This is where secondary indexes shine:
(: SLOW: O(n) sibling traversal to find order with id=5000 :)
jn:doc('shop','orders').orders[][5000]
(: FAST: O(log n) with a CAS index on order IDs :)
(: First, create the index on the 'id' field: :)
let $doc := jn:doc('shop','orders')
let $idx := jn:create-cas-index($doc, 'xs:integer', '/orders/[]/id')
return sdb:commit($doc)
(: Then query the index directly - O(log n) lookup :)
let $doc := jn:doc('shop','orders')
let $idxNo := jn:find-cas-index($doc, 'xs:integer', '/orders/[]/id')
for $node in jn:scan-cas-index($doc, $idxNo, 5000, '==', '/orders/[]/id')
return $node
(: Navigate to a specific node in a 100GB resource -
loads only the pages along the path, not the whole tree :)
let $doc := jn:doc('huge', 'dataset')
return $doc.customers[10000].orders[500].items[3].price
This query touches ~5 nodes across a few pages (each page holds up to 1024 nodes), not 100GB. Note: the page-level granularity means neighboring nodes are loaded together—a potential future optimization would be “mini-pages” (as proposed by Viktor Leis et al.) for finer-grained caching.
Before diving into the architecture, let’s understand the real-world problems that shaped the design. These aren’t academic exercises—they’re scenarios where traditional databases force you into painful workarounds.
The Scenario: Your e-commerce system processed 50,000 orders yesterday. A customer claims they were charged the wrong price. Your current database shows today’s price. What was the price at the moment of their order?
Traditional Approach: Hope you logged it. Build audit tables. Maintain change data capture pipelines. Query across multiple systems. Pray nothing was missed.
With SirixDB:
(: Query the exact state at the order timestamp :)
let $catalog := jn:open('shop', 'products', xs:dateTime('2024-01-15T15:23:47Z'))
return $catalog.products[.sku eq "SKU-12345"].price
One query. Exact answer. No audit infrastructure required—the database remembers everything.
The Scenario: Your configuration management system shows a production outage started at 2:00 AM. What configuration changes were made between the last known good state (midnight) and the incident?
Traditional Approach: Diff log files. Compare backup snapshots. Write custom scripts to parse change logs. Miss the one change that mattered.
With SirixDB:
(: Get structured diffs between any two points in time :)
let $midnight := jn:open('configs', 'production', xs:dateTime('2024-01-15T00:00:00Z'))
let $incident := jn:open('configs', 'production', xs:dateTime('2024-01-15T02:00:00Z'))
return jn:diff('configs', 'production', sdb:revision($midnight), sdb:revision($incident))
Returns a structured JSON diff showing exactly what was inserted, deleted, updated, and moved—with node-level precision.
The Scenario: A patient’s medical record shows an allergy. When was it added? Was it ever modified? By which revision?
Traditional Approach: Build a separate history table. Maintain triggers. Hope the triggers don’t miss edge cases. Query across temporal joins.
With SirixDB:
(: Every version of a specific node, across all time :)
let $allergy := jn:doc('hospital', 'patient-123').allergies[.name eq "Penicillin"]
for $version in jn:all-times($allergy)
return {
"revision": sdb:revision($version),
"timestamp": sdb:timestamp($version),
"data": $version,
"changedFromPrevious": sdb:hash($version) ne sdb:hash(jn:previous($version))
}
The node key is stable across all revisions. The built-in Merkle hash tree instantly detects if the subtree changed.
The Scenario: Regulatory audit requires identifying all customer accounts created after the new compliance rules took effect that are still active.
With SirixDB:
(: Find the revision number for the compliance cutoff date :)
let $cutoffDoc := jn:open('bank', 'accounts', xs:dateTime('2024-06-01T00:00:00Z'))
let $cutoffRev := sdb:revision($cutoffDoc)
(: Query current state, filter by creation revision :)
let $current := jn:doc('bank', 'accounts')
for $account in $current.accounts[]
where not(exists(jn:previous($account))) (: First revision this account exists :)
and sdb:revision($account) > $cutoffRev
return $account
jn:previous() navigates to the same node in the prior revision (if it existed). No separate “created_at” column needed—the revision history is the audit trail.
The Scenario: A bulk import corrupted part of your document. You need to restore just that subtree, not the entire database.
Traditional Approach: Restore from backup (lose all other changes). Write complex update scripts. Hope you got the scope right.
With SirixDB:
(: Find the node 5 revisions ago and see its state :)
let $currentDoc := jn:doc('mydb', 'myresource')
let $currentRev := sdb:revision($currentDoc)
let $nodeKey := 12345 (: Stable across all revisions :)
(: Open the older revision and select the same node :)
let $oldDoc := jn:doc('mydb', 'myresource', $currentRev - 5)
let $oldVersion := sdb:select-item($oldDoc, $nodeKey)
return $oldVersion (: This is the exact state we want to restore :)
Node keys are stable. You can surgically access any subtree at any point in history.
The Scenario: You implement temporal data the “standard” way—history tables with valid_from and valid_to timestamps on every row.
The Hidden Costs:
user_id becomes (user_id, valid_from, valid_to). 3x larger, less cache-friendly.WHERE valid_from <= :timestamp AND valid_to > :timestamp. The optimizer must scan timestamp ranges, not just key lookups.valid_to. Two writes per logical change.With SirixDB:
“But don’t you have to find the revision first?”
Yes! When querying by timestamp (e.g., jn:open(..., xs:dateTime('2024-01-15T15:00:00Z'))), SirixDB must find the corresponding revision:
sirix.revisions file stores: [(rev, timestamp, offset), ...]The key difference:
History table scanning 1000 products:
1000 × (index lookup + timestamp range filter)
= 1000 timestamp comparisons
SirixDB scanning 1000 products:
1 × O(log R) revision lookup + 1000 × (index lookup)
= 1 timestamp lookup total
And typically, you open a session on a revision and run many queries—so that one O(log R) cost is amortized across the entire session.
The Problem: Naive copy-on-write creates a full copy of every modified structure, leading to O(n) storage per revision where n = data size.
Structural Sharing: When a page is modified, only the path from that page to the root is copied. Unchanged sibling pages are referenced (not copied) in the new revision. This is the same principle used in persistent data structures (Okasaki) and version control systems.
Revision N: Revision N+1:
Root ──► A ──► C Root' ──► A ──► C (A, C shared)
└─► B ──► D └─► B'──► D' (B', D' new)
Storage Complexity: For a modification affecting k pages in a tree of depth d:
The Problem: Pure delta-based versioning (like INCREMENTAL) is compact, but reading revision 1000 means reconstructing from 1000 deltas. Reads degrade linearly with history depth. INCREMENTAL versioning mitigates this with intermittent full snapshots, but these cause unpredictable write spikes.
SirixDB’s Solution: The SLIDING_SNAPSHOT algorithm bounds reconstruction to a constant window (default: 3 fragments), regardless of total revision count. Revision 1 and revision 10,000 have the same read performance—without the write spikes of periodic full snapshots.
The Problem: To bound read cost, systems periodically write full snapshots. Every N revisions: write storm.
SirixDB’s Solution: SLIDING_SNAPSHOT never writes full snapshots after initialization. It selectively preserves only records falling out of the window—amortized O(1) extra writes per record. No spikes. Ever.
These aren’t just nice-to-haves—they’re load-bearing constraints that enable the solutions above:
┌─────────────────────────────────────────────────────────────────────────┐
│ SirixDB Design Philosophy │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ TEMPORAL │ │ IMMUTABLE │ │ SHARED │ │
│ │ FIRST │ │ PAGES │ │ STRUCTURE │ │
│ │ │ │ │ │ │ │
│ │ Not bolted │ │ Once │ │ Unchanged │ │
│ │ on—baked │ │ written, │ │ subtrees │ │
│ │ into core │ │ never │ │ reference │ │
│ │ │ │ modified │ │ existing │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ SSD/FLASH │ │ CRASH │ │ ZERO │ │
│ │ NATIVE │ │ PROOF │ │ WRITE AMP │ │
│ │ │ │ │ │ │ │
│ │ Sequential │ │ Commit = │ │ No periodic │ │
│ │ append-only │ │ fsync once │ │ full page │ │
│ │ writes only │ │ No WAL/redo │ │ rewrites │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
graph TB
subgraph "Client Layer"
REST[REST API<br/>Vert.x/Kotlin]
CLI[CLI<br/>Kotlin]
LIB[Java/Kotlin Library]
end
subgraph "Query Layer"
QUERY[Query Engine<br/>Brackit XQuery]
AXIS[Axis Navigation]
FILTER[Filters]
end
subgraph "Transaction Layer"
TRX_MGR[Transaction Manager]
READ_TRX[Read-Only Transactions<br/>N concurrent]
WRITE_TRX[Read-Write Transaction<br/>1 at a time per resource]
end
subgraph "Index Layer"
PATH_IDX[Path Index]
NAME_IDX[Name Index]
CAS_IDX[CAS Index]
PATH_SUM[Path Summary]
end
subgraph "Storage Engine"
PAGE_TRX[Page Transaction]
BUFFER[Buffer Manager]
TIL[Transaction Intent Log]
end
subgraph "Persistence"
DATA[Data File<br/>resource.data]
REV[Revision File<br/>resource.revisions]
end
REST --> QUERY
CLI --> QUERY
LIB --> QUERY
QUERY --> TRX_MGR
AXIS --> READ_TRX
FILTER --> READ_TRX
TRX_MGR --> READ_TRX
TRX_MGR --> WRITE_TRX
READ_TRX --> PAGE_TRX
WRITE_TRX --> PAGE_TRX
WRITE_TRX --> PATH_IDX
WRITE_TRX --> NAME_IDX
WRITE_TRX --> CAS_IDX
WRITE_TRX --> PATH_SUM
PAGE_TRX --> BUFFER
PAGE_TRX --> TIL
BUFFER --> DATA
TIL --> DATA
PAGE_TRX --> REV
sirix/bundles/
├── sirix-core/ # Core storage engine, transactions, pages
├── sirix-query/ # Brackit XQuery engine integration
├── sirix-rest-api/ # Vert.x REST server (Kotlin)
├── sirix-kotlin-cli/ # Command-line interface
├── sirix-kotlin-api/ # Kotlin extensions
├── sirix-mcp/ # Model Context Protocol server for AI agents
├── sirix-distributed/ # Distributed features (experimental)
└── sirix-examples/ # Usage examples
Time-travel as a first-class operation: Most databases let you query the present. Some let you restore backups. SirixDB lets you query any point in history with the same syntax and performance as querying now.
SirixDB uses Brackit, a high-performance query processor, extended with temporal primitives:
(: The killer feature: compare a node across time :)
let $now := jn:doc('shop', 'products') (: Most recent revision :)
let $lastWeek := jn:open('shop', 'products', xs:dateTime('2024-12-30T00:00:00Z'))
for $product in $now.products[]
let $oldPrice := $lastWeek.products[.id eq $product.id].price
where $product.price > $oldPrice * 1.1 (: Price increased >10% :)
return {
"name": $product.name,
"priceChange": $product.price - $oldPrice,
"changedInRevision": sdb:revision($product)
}
This query joins data across time—something that would require ETL pipelines, data warehouses, or manual snapshotting in traditional systems. Here, it’s just a query.
┌───────────────────────────────────────────────────────────────────────────┐
│ Query Execution Pipeline │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ JSONiq/XQuery ──► Parser ──► AST ──► Optimizer ──► Axis Iterators │
│ │
│ Example: $doc.users[].name │
│ │
│ 1. Parse: ObjectDeref("users") → ArrayDeref → ObjectDeref("name") │
│ 2. Optimize: Push predicates, select index │
│ 3. Execute: ChildAxis → ArrayAxis → ChildAxis + NameFilter │
│ │
│ Each axis is a lazy iterator producing nodes on-demand. │
│ Temporal functions (jn:previous, sdb:revision) open new transactions. │
│ │
└───────────────────────────────────────────────────────────────────────────┘
| Function | Description |
|---|---|
jn:open(db, resource, revision) |
Open specific revision by number |
jn:open(db, resource, timestamp) |
Open revision at point-in-time |
jn:previous($node) |
Get node from previous revision |
jn:next($node) |
Get node from next revision |
jn:all-times($node) |
Iterate all versions of node |
sdb:revision($node) |
Get revision number |
sdb:timestamp($node) |
Get commit timestamp |
The Abstraction: To queries, documents look like trees you navigate with XPath-style axes. Under the hood, those “pointers” are actually node keys that resolve through the trie to contiguous memory regions. The abstraction is clean; the performance is physical.
Stable identity across time: Every node has a 64-bit nodeKey that never changes, even as the document evolves. Node 42 in revision 1 is the same logical entity as node 42 in revision 100 (if it still exists). This is what makes temporal queries like “show me how node 42 changed” possible.
Every document is stored as a tree of nodes, where each node has:
nodeKey (64-bit integer, stable across all revisions)parentKey, firstChildKey, lastChildKey, leftSiblingKey, rightSiblingKeyFused object-field nodes (JSON): A JSON object field is a name → value pair. Rather than storing the field name and its value as two separate nodes (a name-holding “object key” node pointing to a single child value node), SirixDB fuses the field name and its value into a single node record. One field in the source JSON maps to exactly one node:
| Source field | Single fused node |
|---|---|
"name": "Alice" |
OBJECT_NAMED_STRING — field nameKey + inline string value |
"age": 30 |
OBJECT_NAMED_NUMBER — field nameKey + inline number value |
"active": true |
OBJECT_NAMED_BOOLEAN — field nameKey + inline boolean value |
"address": null |
OBJECT_NAMED_NULL — field nameKey (null is implicit) |
"profile": { ... } |
OBJECT_NAMED_OBJECT — field nameKey + nested object container |
"tags": [ ... ] |
OBJECT_NAMED_ARRAY — field nameKey + nested array container |
This is the symmetry the design now enforces: the object key and its value are stored the same way whether the value is a scalar or a nested object/array. The scalar variants carry the value inline; the OBJECT_NAMED_OBJECT/OBJECT_NAMED_ARRAY variants additionally carry the container’s structural pointers (firstChildKey, lastChildKey, childCount, descendantCount) so the nested children hang directly off the fused node. The previous indirection node — a standalone “object key” node whose only job was to hold the field name and point at a single value child — has been removed entirely. Eliminating it removes one node, one slot, and one pointer hop per object field.
Array elements are unnamed (positional, not keyed), so they remain standalone value nodes (STRING_VALUE, NUMBER_VALUE, BOOLEAN_VALUE, NULL_VALUE) or plain OBJECT/ARRAY containers. Only object fields — which always carry a name — use the fused OBJECT_NAMED_* records.
┌───────────────────────────────────────────────────────────────────────────┐
│ Node Structure Overview │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Every node has a unique nodeKey (64-bit) stable across all revisions │
│ │
│ Base Node Fields (all nodes): │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ nodeKey (64-bit) Unique identifier, stable across time │ │
│ │ parentKey (64-bit) Parent node's key │ │
│ │ previousRevision (32-bit) When node was created │ │
│ │ lastModRevision (32-bit) When node was last modified │ │
│ │ hash (64-bit) Optional: rolling/postorder hash │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Structural Node Fields (tree nodes & fused object/array fields): │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ firstChildKey (64-bit) First child's key │ │
│ │ lastChildKey (64-bit) Last child's key │ │
│ │ leftSiblingKey (64-bit) Left sibling's key │ │
│ │ rightSiblingKey (64-bit) Right sibling's key │ │
│ │ childCount (64-bit) Optional: number of children │ │
│ │ descendantCount (64-bit) Optional: number of descendants │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Named Node Fields (XML elements/attributes, fused JSON object fields): │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ pathNodeKey (64-bit) Reference to PathSummary node (PCR) │ │
│ │ localNameKey/ (32-bit) Index into NamePage string table │ │
│ │ nameKey (the object field name, for JSON) │ │
│ │ prefixKey (32-bit) XML namespace prefix (NamePage index) │ │
│ │ uriKey (32-bit) XML namespace URI (NamePage index) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Fused Object-Field Value (JSON, OBJECT_NAMED_* records): │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Scalar fields carry the value INLINE in the same record: │ │
│ │ OBJECT_NAMED_STRING → byte[] value │ │
│ │ OBJECT_NAMED_NUMBER → Number value │ │
│ │ OBJECT_NAMED_BOOLEAN → boolean value │ │
│ │ OBJECT_NAMED_NULL → (no value; null is implicit) │ │
│ │ Structural fields carry the container's child pointers: │ │
│ │ OBJECT_NAMED_OBJECT → firstChildKey/lastChildKey/childCount/... │ │
│ │ OBJECT_NAMED_ARRAY → firstChildKey/lastChildKey/childCount/... │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└───────────────────────────────────────────────────────────────────────────┘
JSON Node Types:
| NodeKind | ID | Description |
|---|---|---|
| JSON_DOCUMENT | 31 | JSON document root |
| OBJECT | 24 | JSON object { } (array element or document root child) |
| ARRAY | 25 | JSON array [ ] (array element or document root child) |
| OBJECT_NAMED_BOOLEAN | 48 | Fused object field: name + inline boolean value |
| OBJECT_NAMED_NUMBER | 49 | Fused object field: name + inline number value |
| OBJECT_NAMED_STRING | 50 | Fused object field: name + inline string value |
| OBJECT_NAMED_NULL | 51 | Fused object field: name + null value |
| OBJECT_NAMED_OBJECT | 52 | Fused object field: name + nested object container |
| OBJECT_NAMED_ARRAY | 53 | Fused object field: name + nested array container |
| BOOLEAN_VALUE | 27 | Boolean value true/false (array element) |
| NUMBER_VALUE | 28 | Number value 123.45 (array element) |
| NULL_VALUE | 29 | Null value null (array element) |
| STRING_VALUE | 30 | String value "text" (array element) |
Note: The legacy
OBJECT_KEYnode kind (formerly ID 26) has been removed. A JSON object field no longer materializes as a separate key node plus a child value node — it is a single fusedOBJECT_NAMED_*record (IDs 48–53). The standalone*_VALUEkinds (27–30) now appear only as array elements, never under an object field.
XML Node Types:
| NodeKind | ID | Description |
|---|---|---|
| ELEMENT | 1 | XML element with optional attributes/namespaces |
| ATTRIBUTE | 2 | Attribute node |
| NAMESPACE | 4 | Namespace declaration |
| TEXT | 6 | Text content node |
| PROCESSING_INSTRUCTION | 7 | Processing instruction |
| COMMENT | 8 | Comment node |
| XML_DOCUMENT | 9 | Document root |
┌───────────────────────────────────────────────────────────────────────────┐
│ JSON Document with All Node Types │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Document: {"name":"Alice","age":30,"active":true,"address":null, │
│ "tags":["dev","lead"]} │
│ │
│ Tree Structure (object fields are FUSED name+value nodes): │
│ │
│ JSON_DOCUMENT (key=0) │
│ │ │
│ └── OBJECT (key=1) │
│ ├── OBJECT_NAMED_STRING "name"="Alice" (key=2) │
│ ├── OBJECT_NAMED_NUMBER "age"=30 (key=3) │
│ ├── OBJECT_NAMED_BOOLEAN "active"=true (key=4) │
│ ├── OBJECT_NAMED_NULL "address"=null (key=5) │
│ └── OBJECT_NAMED_ARRAY "tags" (key=6) │
│ │ (this node IS the array container) │
│ ├── STRING_VALUE "dev" (key=7) │
│ └── STRING_VALUE "lead" (key=8) │
│ │
│ Each object field = ONE node (no separate key + value pair). │
│ Array elements stay unnamed → standalone STRING_VALUE nodes. │
│ Navigation: nodeKey 2 has parentKey=1, rightSiblingKey=3 │
│ │
└───────────────────────────────────────────────────────────────────────────┘
Contrast with the old layout: Previously this document needed 14 nodes (keys 0–13) — every object field was an
OBJECT_KEYnode plus a separate child value node. With fusion the same document needs 9 nodes (keys 0–8): the four scalar fields and thetagsfield each collapse from two nodes into one. Fewer nodes means fewer slots, less pointer chasing, smaller pages, and less to copy on write.
Axes are iterators that traverse from a context node to related nodes. SirixDB provides both spatial axes (within a revision) and temporal axes (across revisions).
| Axis | Direction | Description |
|---|---|---|
ChildAxis |
Down | Direct children only |
DescendantAxis |
Down | All descendants (depth-first, pre-order) |
PostOrderAxis |
Down | All descendants (depth-first, post-order) |
LevelOrderAxis |
Down | All descendants (breadth-first) |
ParentAxis |
Up | Direct parent |
AncestorAxis |
Up | All ancestors to root |
FollowingSiblingAxis |
Right | Siblings after this node |
PrecedingSiblingAxis |
Left | Siblings before this node |
SelfAxis |
None | The node itself |
// Example: iterate all children of the document root
try (var rtx = resource.beginNodeReadOnlyTrx()) {
rtx.moveToDocumentRoot();
rtx.moveToFirstChild(); // Move to content root
for (var axis = new ChildAxis(rtx); axis.hasNext(); ) {
axis.nextLong();
System.out.println(rtx.getName() + ": " + rtx.getValue());
}
}
Navigate the same node across different revisions:
| Axis | Description |
|---|---|
AllTimeAxis |
All revisions where node exists |
PastAxis |
Previous revisions (oldest first or newest first) |
FutureAxis |
Later revisions |
FirstAxis |
First revision where node existed |
LastAxis |
Most recent revision |
PreviousAxis |
Immediately preceding revision |
NextAxis |
Immediately following revision |
┌───────────────────────────────────────────────────────────────────────────┐
│ Temporal Navigation │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Timeline: Rev 1 ──► Rev 2 ──► Rev 3 ──► Rev 4 ──► Rev 5 │
│ ▲ │
│ Current Node │
│ │
│ PastAxis: Rev 1, Rev 2 (iterations before Rev 3) │
│ FutureAxis: Rev 4, Rev 5 (iterations after Rev 3) │
│ AllTimeAxis: Rev 1, Rev 2, Rev 3, Rev 4, Rev 5 │
│ PreviousAxis: Rev 2 (one step back) │
│ NextAxis: Rev 4 (one step forward) │
│ │
└───────────────────────────────────────────────────────────────────────────┘
// Get all versions of all children of the document root
try (var rtx = resource.beginNodeReadOnlyTrx()) {
rtx.moveToDocumentRoot();
rtx.moveToFirstChild(); // Move to actual content root
var childAxis = new ChildAxis(rtx);
while (childAxis.hasNext()) {
childAxis.nextLong();
var allTimeAxis = new AllTimeAxis(resource, rtx);
while (allTimeAxis.hasNext()) {
var historicalRtx = allTimeAxis.next();
// historicalRtx points to this child in a different revision
}
}
}
Node keys are logical identifiers, not memory pointers. Nodes are stored contiguously in KeyValueLeafPages for cache locality:
┌───────────────────────────────────────────────────────────────────────────┐
│ Logical Keys → Physical Storage │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ nodeKey = 5000 │
│ │ │
│ ├──► pageKey = 5000 >> 10 = 4 (which KeyValueLeafPage) │
│ └──► slotIndex = 5000 & 1023 = 904 (which slot in page) │
│ │
│ KeyValueLeafPage #4: │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ MemorySegment (off-heap, up to 1024 nodes) │ │
│ │ ┌──────┬──────┬──────┬─────────────────────────┬──────┬──────────┐ │ │
│ │ │ [0] │ [1] │ [2] │ ... contiguous nodes ...│ [904]│ ... │ │ │
│ │ │ Node │ Node │ Node │ │ Node │ │ │ │
│ │ └──────┴──────┴──────┴─────────────────────────┴──────┴──────────┘ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Benefits: │
│ • Cache-friendly: nodes in same page are nearby in memory │
│ • O(1) lookup: trie navigation + slot index │
│ • No pointer chasing: direct offset calculation │
│ │
└───────────────────────────────────────────────────────────────────────────┘
The Challenge: Most databases bolt on versioning to indexes as an afterthought. Result: your index at revision 42 might not match your data at revision 42. SirixDB indexes version with the data—same CoW infrastructure, same revision semantics.
Secondary indexes answer the question: “Which nodes have property X?” Instead of scanning the entire document, look up X in an index and get back a bitmap of matching node keys.
graph TB
subgraph "Primary Indexes"
DOC[Document Index<br/>Node tree structure]
PATH_SUM[Path Summary<br/>Unique path classes]
DEWEY[DeweyID Index<br/>NodeKey → DeweyID]
end
subgraph "Secondary Indexes"
PATH[Path Index<br/>PCR → NodeKeys]
NAME[Name Index<br/>NameHash → NodeKeys]
CAS[CAS Index<br/>Value+Path → NodeKeys]
end
subgraph "Index Backends"
RBTREE[RBTree<br/>Nodes in KeyValueLeafPages]
HOT[HOT Trie<br/>HOTIndirectPage → HOTLeafPage]
end
PATH --> RBTREE
PATH --> HOT
NAME --> RBTREE
NAME --> HOT
CAS --> RBTREE
DeweyIDs: When enabled via ResourceConfiguration.Builder.useDeweyIDs(true), each node is assigned a hierarchical identifier (e.g., 1.3.5.7) that encodes its position in the document tree. DeweyIDs enable:
DeweyIDs are stored inline within KeyValueLeafPages alongside node records (in a dedicated MemorySegment). The sibling distance (deweyIdSiblingDistance) is configurable to optimize for insert-heavy vs. read-heavy workloads.
SirixDB supports three types of user-defined secondary indexes that can be created on any resource:
Purpose: Accelerates queries that filter by document structure (path expressions).
Key Mapping: PCR (Path Class Reference) → Set<NodeKey>
Use Case: “Find all nodes at path /users/[]/email”
Document: Path Index (for /users/[]/name):
───────── ─────────────────────────────────
{ PCR=3 → {5, 12} (nodeKeys of "Alice", "Bob")
"users": [
{"name": "Alice", "age": 30}, ← nodeKey=5
{"name": "Bob", "age": 25} ← nodeKey=12
]
}
When to Use:
//users/[]/address/city)Purpose: Accelerates queries that search for elements/fields by name regardless of path.
Key Mapping: QNm (Qualified Name hash) → Set<NodeKey>
Use Case: “Find all nodes named ‘email’ anywhere in the document”
Document: Name Index (for "email"):
───────── ──────────────────────────
{ hash("email") → {8, 15, 22}
"user": {
"email": "[email protected]" ← nodeKey=8
},
"admin": {
"contact": {
"email": "[email protected]" ← nodeKey=15
}
},
"support": {
"email": "[email protected]" ← nodeKey=22
}
}
When to Use:
//*:email, ..$email)Purpose: Accelerates queries that filter by both value AND path (content + structure).
Key Mapping: CASValue (Path + TypedValue) → Set<NodeKey>
Use Case: “Find all users where age > 30” or “Find products with price = 99.99”
Document: CAS Index (for /users/[]/age, Type=INT):
───────── ─────────────────────────────────────────
{ (PCR=4, 25) → {13}
"users": [ (PCR=4, 30) → {7}
{"name": "Alice", "age": 30}, (PCR=4, 35) → {19}
{"name": "Bob", "age": 25},
{"name": "Carol", "age": 35} Supports range queries: age > 28
] → Returns {7, 19}
}
When to Use:
where price < 100)where date between ...)unique for constraint enforcementImportant: The two index backends use different storage structures:
| Backend | Page Structure | Leaf Page Type |
|---|---|---|
| RBTree | IndexPage → IndirectPages → KeyValueLeafPage |
RBTree nodes stored as records |
| HOT | IndexPage → HOTIndirectPage → HOTLeafPage |
Sorted key-value entries |
The Path Summary is a compressed representation of all unique paths in the document:
Document: Path Summary:
───────── ─────────────
{ / (PCR=0)
"users": [ ├─ users (PCR=1)
{ │ └─ [] (PCR=2)
"name": "Alice", │ ├─ name (PCR=3)
"age": 30 │ └─ age (PCR=4)
},
{ PCR = Path Class Reference
"name": "Bob", Each unique path gets one PCR
"age": 25 Nodes reference their PCR
}
]
}
The HOT index is a cache-friendly alternative to B-trees:
┌───────────────────────────────────────────────────────────────────────────┐
│ HOT Index Structure │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Traditional B-Tree: HOT Trie: │
│ ───────────────── ───────── │
│ │
│ [Root] [Compound Node] │
│ / \ / | | \ │
│ [A] [B] [C1] [C2] [C3] [C4] │
│ / | \ / | \ │
│ ... ... Multiple levels collapsed │
│ into single cache-friendly node │
│ │
│ Node Types: │
│ ┌──────────┬──────────────────────────────────────────────────────────┐ │
│ │ BiNode │ 2 children, 1 discriminative bit │ │
│ ├──────────┼──────────────────────────────────────────────────────────┤ │
│ │ SpanNode │ 2-16 children, SIMD-optimized partial key search │ │
│ ├──────────┼──────────────────────────────────────────────────────────┤ │
│ │ MultiNode│ 17-256 children, direct byte indexing │ │
│ └──────────┴──────────────────────────────────────────────────────────┘ │
│ │
│ HOTLeafPage: │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ [key₁|value₁][key₂|value₂][key₃|value₃]... │ │
│ │ Sorted entries, binary search, off-heap MemorySegment │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└───────────────────────────────────────────────────────────────────────────┘
HOT index reads are revision-isolated: a read-only transaction pinned to
revision N (session.beginNodeReadOnlyTrx(N)) observes the index state as of
revision N — never a later commit’s state. A writer committing revision N+1
cannot bleed into a concurrently pinned reader of revision N.
This holds because every committed HOT leaf fragment lands at a unique
physical storage key under Sirix’s copy-on-write model. The reconstructed
leaf for revision N and for revision N+1 are therefore cached under
distinct keys in the storage-key-keyed HOTLeafPageCache and cannot collide —
the storage key already encodes the version. The fragment chain
(PageReference.getPageFragments()) walked during reconstruction is the chain
recorded at write time for that revision’s root reference, so combining it
yields exactly the cumulative-up-to-N view.
The property is enforced by test (NAME and CAS indexes, point and range reads, in-memory, across session close/reopen, and under a concurrent pinned-reader-vs-writer):
HOTMultiVersionInvariantsTest — per-revision independent readability and
monotone-cumulative value distributions.HOTVersionedLeafStressTest.MultiRevisionIsolation — a reader pinned to rev 1
sees a stable key count while a writer commits rev 2; oracle-verified range
queries across 5 revisions.HOTVersioningIntegrationTest, HOTIndirectPageVersioningTest,
HOTIndexManyRevisionsTest, HOTMultiRevisionFragmentChainTest — historical
revisions reconstruct correctly under FULL / INCREMENTAL / DIFFERENTIAL /
SLIDING_SNAPSHOT versioning, including chain rotation.// Create a path index for specific paths
IndexDef pathIdx = IndexDefs.createPathIdxDef(
Set.of(parse("/users/[]/name")),
0,
IndexDef.DbType.JSON
);
// Create a name index for all field names
IndexDef nameIdx = IndexDefs.createNameIdxDef(0, IndexDef.DbType.JSON);
// Create a CAS index for value queries
IndexDef casIdx = IndexDefs.createCASIdxDef(
false, // not unique
Type.STR, // string values
Set.of(parse("/users/[]/name")),
0,
IndexDef.DbType.JSON
);
Design Goal: A single append-only file per resource. No WAL. No compaction. Just write pages sequentially and fsync once per commit.
The storage engine is deceptively simple: pages go in, pages come out. The complexity lives in which pages to write and how to reconstruct them. That’s where versioning strategies earn their keep.
┌─────────────────────────────────────────────────────────────────────────────┐
│ SirixDB File Layout │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ mydatabase/ ◄── Database directory │
│ ├── dbsetting.obj ◄── Database configuration (binary) │
│ ├── keyselector/ ◄── Encryption key storage │
│ ├── .lock ◄── Database lock file │
│ └── resources/ ◄── All resources in this database │
│ │ │
│ ├── resource1/ ◄── Resource directory │
│ │ ├── ressetting.obj ◄── Resource config (binary) │
│ │ ├── data/ ◄── Main storage │
│ │ │ ├── sirix.data ◄── Page data (append-only) │
│ │ │ └── sirix.revisions ◄── Revision offset index │
│ │ ├── indexes/ ◄── Index definitions │
│ │ │ └── indexes.xml ◄── XML index config │
│ │ ├── log/ ◄── Transaction intent log │
│ │ │ └── .commit ◄── Commit marker file │
│ │ ├── encryption/ ◄── Resource encryption keys │
│ │ └── update-operations/ ◄── Update operation logs │
│ │ │
│ └── resource2/ ◄── Another resource │
│ └── ... │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Key files:
sirix.data - Append-only file containing all pages (compressed, versioned)sirix.revisions - Index mapping revision numbers to file offsetsressetting.obj - Serialized ResourceConfiguration (versioning type, compression, etc.)┌─────────────────────────────────────────────────────────────────────────┐
│ SirixDB Page Hierarchy │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ UberPage │
│ ════════ │
│ │ Entry point for resource (one per resource) │
│ │ Points to RevisionRootPage for each revision │
│ │ │
│ ▼ │
│ RevisionRootPage (Rev N) │
│ ════════════════════════ │
│ │ Root for one revision │
│ │ Commit timestamp, max node key │
│ │ │
│ ├──► DocumentPage ───────────────────────────────────────────────────┐ │
│ │ (Node storage root) │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ IndirectPage L0 [0..1023] │ │
│ │ │ │ │
│ │ ├─[0]──► IndirectPage L1 [0..1023] │ │
│ │ │ │ │ │
│ │ │ ├─[0]──► IndirectPage L2 ──► ... ──► Leaf │ │
│ │ │ ├─[1]──► IndirectPage L2 ──► ... ──► Leaf │ │
│ │ │ └─[...] │ │
│ │ │ │ │
│ │ ├─[1]──► IndirectPage L1 ──► ... │ │
│ │ ├─[2]──► IndirectPage L1 ──► ... │ │
│ │ └─[...]──► (up to 1024 children per level) │ │
│ │ │ │
│ │ ▼ │ │
│ │ KeyValueLeafPage │ │
│ │ ════════════════ │ │
│ │ │ Up to 1024 node records │ │
│ │ │ Off-heap MemorySegment │ │
│ │ └────────────────────────────────────────────────┘ │
│ │ │
│ ├──► PathSummaryPage ──► IndirectPages ──► KeyValueLeafPage (Paths) │
│ │ │
│ ├──► NamePage ─────────► IndirectPages ──► KeyValueLeafPage (names) │
│ │ │
│ │ Secondary Indexes (configurable backend): │
│ │ ───────────────────────────────────────── │
│ │ │
│ │ HOT backend: │
│ ├──► PathPage ─────────► HOTIndirectPage ──► HOTLeafPage │
│ ├──► NameIndexPage ────► HOTIndirectPage ──► HOTLeafPage │
│ ├──► CASPage ──────────► HOTIndirectPage ──► HOTLeafPage │
│ │ │
│ │ RBTree backend: │
│ ├──► PathPage ─────────► IndirectPages ──► KeyValueLeafPage (RBNodes) │
│ ├──► NameIndexPage ────► IndirectPages ──► KeyValueLeafPage (RBNodes) │
│ └──► CASPage ──────────► IndirectPages ──► KeyValueLeafPage (RBNodes) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────┐
│ HOT (Height-Optimized Trie) Index │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ PathPage / NameIndexPage / CASPage │
│ │ │
│ ▼ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ HOT Root (HOTIndirectPage) │ │
│ │ ════════════════════════════ │ │
│ │ │ │
│ │ BiNode: discriminative bit at position 12 │ │
│ │ ┌───────────────────┬───────────────────┐ │ │
│ │ │ bit=0 → left │ bit=1 → right │ │ │
│ │ └────────┬──────────┴─────────┬─────────┘ │ │
│ │ │ │ │ │
│ │ ▼ ▼ │ │
│ │ SpanNode HOTLeafPage │ │
│ │ (4 bits, 16 slots) ┌──────────────────────────────────┐ │ │
│ │ ┌──┬──┬──┬──┐ │ [key₁|NodeRefs₁] │ │ │
│ │ │0 │1 │..│15│ │ [key₂|NodeRefs₂] │ │ │
│ │ └┬─┴┬─┴──┴┬─┘ │ [key₃|NodeRefs₃] │ │ │
│ │ │ │ │ │ ... │ │ │
│ │ ▼ ▼ ▼ │ Sorted by key, binary search │ │ │
│ │ Leaf Leaf Leaf │ Values: Roaring64Bitmap │ │ │
│ │ └──────────────────────────────────┘ │ │
│ │ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ Index Types: │
│ ──────────── │
│ • PATH Index: key = pathNodeKey (long) → NodeReferences (bitmap) │
│ • NAME Index: key = nameHash (bytes) → NodeReferences (bitmap) │
│ • CAS Index: key = value+path (bytes) → NodeReferences (bitmap) │
│ │
│ HOT Node Types: │
│ ─────────────── │
│ • BiNode: 2 children, single discriminative bit │
│ • SpanNode: up to 16 children, 4 contiguous bits │
│ • MultiNode: up to 256 children, 8 bits (full byte) │
│ │
│ Leaf Page: │
│ ────────── │
│ • HOTLeafPage: up to 512 key-value entries │
│ • Keys sorted for binary search O(log n) │
│ • Values are Roaring64Bitmap (compressed node key sets) │
│ • Off-heap storage via MemorySegment │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Key Insight: Everything is a page. Documents, indexes, metadata—all stored in the same versioned page infrastructure. This uniformity is what makes temporal queries on indexes “just work.”
| Page Type | Purpose | Key Properties |
|---|---|---|
| UberPage | Resource entry point | Points to RevisionRootPages (all revisions) |
| RevisionRootPage | Root of a revision’s page tree | Commit timestamp, max node key |
| IndirectPage | Trie node for 64-bit keys | Up to 1024 child references |
| KeyValueLeafPage | Stores actual node records | Off-heap MemorySegment storage |
| NamePage | String table for names | Element/attribute/key names |
| PathPage | Path index roots | References to path index trees |
| CASPage | Content-and-Structure index | Combined value+path indexing |
Why a trie, not a B+ tree? B+ trees are optimized for range scans and disk seeks. But SirixDB’s append-only model means we never update nodes in place—we just need O(1) lookup from node key → page. A trie gives us that with minimal overhead and perfect structural sharing for versioning.
SirixDB uses a trie structure to navigate from node keys to their storage locations. The 64-bit node key is decomposed into 10-bit chunks, with each chunk indexing into an IndirectPage.
Reference: The trie design with flexible height is described in: Sebastian Graf, “Flexible Secure Cloud Storage”, PhD Dissertation, University of Konstanz, 2014. Available at KOPS
Dynamic Tree Height: The trie grows dynamically based on the maximum node key. Initially, a small document needs only 1 level. As the document grows and node keys exceed the current capacity, a new level is added at the top. This design minimizes storage overhead for small documents while scaling to billions of nodes.
Copy-on-Write: IndirectPages are fully copied when modified, ensuring immutability of previous revisions.
Navigation Algorithm (from NodeStorageEngineReader):
levelKey = pageKey
for level in (array.length - maxHeight) to (array.length - 1):
offset = levelKey >> exponent[level] // extract index (0-1023)
levelKey -= offset << exponent[level] // subtract for next level
page = page.getReference(offset) // follow reference
Exponent Array: {70, 60, 50, 40, 30, 20, 10, 0}
L0 L1 L2 L3 L4 L5 L6 L7
Tree height grows dynamically (maxHeight = 1 to 8):
Height 1: Only L7 (shift 0) → bits 0-9 → up to 1K pages
Height 2: L6→L7 → bits 0-19 → up to 1M pages
Height 3: L5→L6→L7 → bits 0-29 → up to 1B pages
Height 4: L4→L5→L6→L7 → bits 0-39 → up to 1T pages
...
Height 8: L0→L1→...→L7 → bits 0-69 → theoretical max
(only bits 0-63 exist in 64-bit keys)
Example: pageKey = 1_048_576 (0x100000), Height = 3
L5: offset = 1048576 >> 20 = 1 → IndirectPage[1]
L6: offset = 0 >> 10 = 0 → IndirectPage[0]
L7: offset = 0 >> 0 = 0 → KeyValueLeafPage[0]
┌─────────────────────────────────────────────────────────────────────────────┐
│ Trie Navigation Example │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ DocumentPage │
│ │ │
│ ▼ │
│ IndirectPage L0 [0..1023] │
│ │ │
│ ├── [0] ──► IndirectPage L1 ──► ... ──► LeafPage (nodes 0-1023) │
│ ├── [1] ──► IndirectPage L1 ──► ... ──► LeafPage (nodes 1024-2047) │
│ ├── [2] ──► IndirectPage L1 ──► ... ──► LeafPage (nodes 2048-3071) │
│ │ ... │
│ └── [1023] ──► IndirectPage L1 ──► ... │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Each IndirectPage level provides O(1) lookup for its portion of the key, making node lookup O(depth) where depth is typically 7 levels maximum.
┌───────────────────────────────────────────────────────────────────────────┐
│ KeyValueLeafPage (Off-Heap) │
├───────────────────────────────────────────────────────────────────────────┤
│ Header: pageKey (8B) | revision (4B) | entryCount (4B) | ... │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Slot Offsets Array (int[]) Records Array (DataRecord[]) │
│ │
│ ┌─────┬─────┬─────┬─────┐ ┌────────────────────────────┐ │
│ │ 0 │ 128 │ 256 │ ... │ │ │ │
│ └──┬──┴──┬──┴──┬──┴─────┘ │ Record 0 (offset 0) │ │
│ │ │ │ ┌──────────►│ │ │
│ │ │ │ │ ├────────────────────────────┤ │
│ │ │ │ │ │ │ │
│ │ │ └────────┼──────────►│ Record 1 (offset 128) │ │
│ │ │ │ │ │ │
│ │ │ │ ├────────────────────────────┤ │
│ │ │ │ │ │ │
│ │ └──────────────┼──────────►│ Record 2 (offset 256) │ │
│ │ │ │ │ │
│ └────────────────────┘ └────────────────────────────┘ │
│ │
│ MemorySegment (slots) MemorySegment (deweyIds) │
│ ┌─────────────────────┐ ┌─────────────────────┐ │
│ │ Serialized bytes │ │ DeweyID bytes │ │
│ │ for each record │ │ (if enabled) │ │
│ └─────────────────────┘ └─────────────────────┘ │
│ │
└───────────────────────────────────────────────────────────────────────────┘
Each PageReference contains:
class PageReference {
long key; // Storage offset (persistent)
int logKey; // Transaction log index (transient)
long checksum; // Data integrity checksum
Page page; // In-memory swizzled page (transient)
}
The fundamental invariant: Once a page is written, it is never modified. Ever. This single constraint enables time-travel, crash safety, and lock-free reads—but it creates the storage/performance trade-off that SLIDING_SNAPSHOT elegantly solves.
SirixDB implements a Copy-on-Write (COW) architecture where modifications never overwrite existing data:
| Benefit | How CoW Enables It |
|---|---|
| Time-travel | Old pages still exist—just follow old revision’s root |
| Lock-free reads | Readers see a consistent snapshot, never torn writes |
| Crash safety | Commit = atomic pointer swap; partial writes are orphaned |
| No WAL needed | Append-only + atomic commit = always consistent |
When a page is modified, SirixDB creates a new version rather than modifying in place:
┌─────────────────────────────────────────────────────────────────────────────┐
│ Copy-on-Write Page Modification │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Revision N Revision N+1 │
│ ────────── ──────────── │
│ │
│ ┌─────┐ ┌─────┐ │
│ │Root │ │Root'│ ◄── NEW (copied) │
│ └──┬──┘ └──┬──┘ │
│ │ │ │
│ ┌─────┴─────┐ ┌─────┴─────┐ │
│ │ │ │ │ │
│ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ │
│ │ A │ │ B │ │ A │────►│ B' │ ◄── NEW (copied) │
│ └──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘ │
│ │ │ SHARED │ │
│ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ │
│ │ C │ │ D │ │ C │────►│ D' │ ◄── NEW (modified)│
│ └─────┘ └─────┘ └─────┘ └─────┘ │
│ SHARED │
│ │
│ Key insight: Pages A and C are SHARED between revisions │
│ Only the modified path (Root' → B' → D') is copied │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
During a write transaction, modified pages are held in memory in the Transaction Intent Log:
┌─────────────────────────────────────────────────────────────────────────┐
│ Transaction Intent Log │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Write Transaction │
│ ───────────────── │
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ TransactionIntentLog │ │
│ │ ┌─────────────────────────────────────────────────────────────┐ │ │
│ │ │ PageContainer[0]: complete=Page₁, modified=Page₁' │ │ │
│ │ │ PageContainer[1]: complete=Page₂, modified=Page₂' │ │ │
│ │ │ PageContainer[2]: complete=Page₃, modified=Page₃' │ │ │
│ │ │ ... │ │ │
│ │ └─────────────────────────────────────────────────────────────┘ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ On COMMIT: On ROLLBACK: │
│ ─────────── ──────────── │
│ 1. Write all modified pages 1. TIL.clear() │
│ 2. Write new RevisionRootPage 2. Close all pages │
│ 3. Update UberPage pointer 3. Release memory │
│ 4. fsync() for durability │
│ 5. TIL.clear() │
│ │
└─────────────────────────────────────────────────────────────────────────┘
The key innovation in SirixDB is configurable page versioning which controls the trade-off between storage overhead, read performance, and write performance.
graph LR
subgraph "FULL Versioning"
F1[Rev 1<br/>Complete] --> F2[Rev 2<br/>Complete]
F2 --> F3[Rev 3<br/>Complete]
end
subgraph "INCREMENTAL Versioning"
I1[Rev 1<br/>Full] --> I2[Rev 2<br/>Delta]
I2 --> I3[Rev 3<br/>Delta]
I3 --> I4[Rev 4<br/>Full]
end
subgraph "DIFFERENTIAL Versioning"
D1[Rev 1<br/>Full] --> D2[Rev 2<br/>Diff from 1]
D1 --> D3[Rev 3<br/>Diff from 1]
D1 --> D4[Rev 4<br/>Full]
end
subgraph "SLIDING_SNAPSHOT (window=3)"
direction TB
S1[Rev 1<br/>🟢 Full]
S2[Rev 2<br/>Δ]
S3[Rev 3<br/>Δ]
S4[Rev 4<br/>Δ + preserve]
S1 --> S2 --> S3
S3 --> S4
S1 -.->|"slot 3 preserved"| S4
end
| Strategy | Fragments | Read Cost | Write Cost | Storage | Use Case |
|---|---|---|---|---|---|
| FULL | 1 | O(1) | High | Highest | Read-heavy, infrequent updates |
| INCREMENTAL | 1-w | O(w) small Δs | Low + periodic full | Lowest | Simple, periodic full writes OK |
| DIFFERENTIAL | 2 | O(2) large Δ | Medium-High (growing) | Medium | Read-heavy after initial load |
| SLIDING_SNAPSHOT | 1-w | O(w) small Δs | Low (no full writes) | Medium | Best overall trade-off |
Cost Clarification:
w= window size /revisionsToRestore(typically 8)- INCREMENTAL: Bounded via periodic full page snapshots (write spike every w revisions)
- SLIDING_SNAPSHOT: Bounded via preservation (never writes full pages, only small deltas)
- DIFFERENTIAL: 2 fragments but delta contains ALL changes since base (can be large)
- Reconstruction time depends on both fragment count AND fragment size
Every revision stores complete pages. No reconstruction needed.
┌─────────────────────────────────────────────────────────────────────────────┐
│ FULL Versioning │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Storage Layout: │
│ ─────────────── │
│ │
│ Rev 1: [Page A₁ FULL] [Page B₁ FULL] [Page C₁ FULL] │
│ Rev 2: [Page A₂ FULL] [Page B₂ FULL] [Page C₂ FULL] ◄── All complete │
│ Rev 3: [Page A₃ FULL] [Page B₃ FULL] [Page C₃ FULL] │
│ │
│ Read Rev 2, Page B: │
│ ─────────────────── │
│ → Load Page B₂ directly (O(1) I/O) │
│ │
│ Pros: Fastest reads, simplest implementation │
│ Cons: Highest storage, every write copies entire page │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Stores only changed records. Full snapshots created every N revisions.
┌─────────────────────────────────────────────────────────────────────────────┐
│ INCREMENTAL Versioning │
│ (revisionsToRestore = 4) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Storage Layout (Page A across revisions): │
│ ────────────────────────────────────────── │
│ │
│ Rev 1: [FULL: slots 0,1,2,3,4,5...1023] ◄── Full snapshot │
│ Rev 2: [DELTA: slot 5 changed] ◄── Only changed slot │
│ Rev 3: [DELTA: slots 10,11 changed] ◄── Only changed slots │
│ Rev 4: [DELTA: slot 5 changed again] │
│ Rev 5: [FULL: slots 0,1,2,3,4,5...1023] ◄── New full snapshot │
│ Rev 6: [DELTA: slot 100 changed] │
│ ... │
│ │
│ Read Rev 4, Page A (reconstruction): │
│ ──────────────────────────────────── │
│ 1. Load Rev 4 delta → slot 5 │
│ 2. Load Rev 3 delta → slots 10,11 │
│ 3. Load Rev 2 delta → slot 5 (skip, already have newer) │
│ 4. Load Rev 1 full → remaining slots │
│ 5. Combine: newer fragments override older │
│ │
│ Fragment Chain: │
│ ─────────────── │
│ PageReference.pageFragments = [ │
│ FragmentKey(rev=4, offset=..., dbId, resId), │
│ FragmentKey(rev=3, offset=...), │
│ FragmentKey(rev=2, offset=...), │
│ FragmentKey(rev=1, offset=...) ◄── Full dump (chain anchor) │
│ ] │
│ │
│ Slot Bitmap Optimization: │
│ ───────────────────────── │
│ Each KeyValueLeafPage tracks populated slots with a bitmap (long[16]) │
│ Reconstruction iterates only populated slots: O(k) not O(1024) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Each delta references the last full snapshot (not the previous revision).
┌─────────────────────────────────────────────────────────────────────────────┐
│ DIFFERENTIAL Versioning │
│ (revisionsToRestore = 4) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Storage Layout (Page A): │
│ ──────────────────────── │
│ │
│ Rev 1: [FULL: all slots] ◄── Full snapshot │
│ Rev 2: [DIFF from 1: slot 5] ◄── Changes since Rev 1 │
│ Rev 3: [DIFF from 1: slots 5,10,11] ◄── ALL changes since Rev 1 │
│ Rev 4: [FULL: all slots] ◄── New full snapshot (rev % 4 == 0) │
│ Rev 5: [DIFF from 4: slot 100] ◄── Changes since Rev 4 │
│ │
│ Read Rev 3, Page A: │
│ ─────────────────── │
│ 1. Load Rev 3 diff → slots 5,10,11 │
│ 2. Load Rev 1 full → remaining slots │
│ 3. Combine (only 2 pages, never more!) │
│ │
│ Key Difference from INCREMENTAL: │
│ ───────────────────────────────── │
│ • INCREMENTAL: delta = changes since previous revision │
│ • DIFFERENTIAL: delta = changes since last full snapshot │
│ │
│ Result: Always reconstruct from at most 2 fragments (O(1) complexity) │
│ Trade-off: Deltas grow larger over time until next full snapshot │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
“What if we could have bounded read cost without periodic write storms?”
This is the question that led to SLIDING_SNAPSHOT—the default versioning strategy and the algorithmic heart of SirixDB’s efficiency.
The Insight
Traditional bounded versioning (INCREMENTAL with periodic snapshots) has a fatal flaw: every w revisions, you must rewrite the entire page to reset the delta chain. For a 1024-record page with small changes, you’re rewriting 1024 records to save one record. That’s 1000x write amplification.
SLIDING_SNAPSHOT asks: what if we only preserved records that would actually be lost?
Instead of rewriting everything, track which records exist in the in-window fragments (a 128-byte bitmap). When a fragment falls out of the window, only preserve records not covered by the bitmap. The amortized cost? Each record is preserved at most once per window—exactly when it would otherwise become unreachable.
Formal Verification: This algorithm has been formally verified for correctness in: Sebastian Graf, “Flexible Secure Cloud Storage”, PhD Dissertation, University of Konstanz, 2014. Available at KOPS
The Trade-off Comparison
| Aspect | INCREMENTAL | DIFFERENTIAL | SLIDING_SNAPSHOT |
|---|---|---|---|
| Read fragments | Bounded O(w) | Fixed O(2) | Bounded O(w) |
| Fragment size | Small Δ | Grows over time | Small Δ |
| Full page writes | Every w revisions | Every w revisions | Never |
| Write pattern | Spiky (6,1,1,1,6,…) | Growing (1,2,3,4,…) | Smooth (1,1,1,4,1,1,…) |
| Write amplification | ❌ Periodic 100% rewrite | ❌ Unbounded delta growth | ✅ Amortized ~12.5%/rev |
┌───────────────────────────────────────────────────────────────────────────┐
│ SLIDING_SNAPSHOT: The Algorithm │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Configuration: revisionsToRestore = 4 (window size) │
│ │
│ PHASE 1: Prepare for Modification │
│ ══════════════════════════════════ │
│ │
│ combineRecordPagesForModification(pages, revToRestore, ...): │
│ │
│ 1. Build fragment reference chain (max revToRestore - 1 entries): │
│ previousPageFragmentKeys = [currentFragment] │
│ for each oldFragment in reference.pageFragments: │
│ if chain.size < revToRestore - 1: │
│ chain.add(oldFragment) // Keep in window │
│ else: │
│ break // Beyond window │
│ │
│ 2. Create two page views: │
│ completePage = reconstructed page (for reading) │
│ modifyingPage = new delta page (for writing changes) │
│ │
│ PHASE 2: Process In-Window Fragments │
│ ════════════════════════════════════ │
│ │
│ Use bitmap (128 bytes) to track which slots exist in window: │
│ │
│ inWindowBitmap = new long[16] // 1024 bits for 1024 slots │
│ │
│ for each fragment in window (newest → oldest): │
│ for each populated slot in fragment: │
│ inWindowBitmap[slot/64] |= (1L << (slot % 64)) │
│ if slot not in completePage: │
│ completePage.setSlot(slot, record) │
│ │
│ PHASE 3: Handle Out-of-Window Fragment (The Key Innovation!) │
│ ═════════════════════════════════════════════════════════════ │
│ │
│ if pages.size == revToRestore: // There IS an out-of-window fragment │
│ outOfWindowPage = pages.getLast() │
│ │
│ for each populated slot in outOfWindowPage: │
│ // Add to complete page if not already filled │
│ if slot not in completePage: │
│ completePage.setSlot(slot, record) │
│ │
│ // CRITICAL: Preserve if not in any in-window fragment! │
│ if slot NOT in inWindowBitmap: │
│ modifyingPage.markSlotForPreservation(slot) │
│ │
│ Result: modifyingPage contains: │
│ • New modifications made in this transaction │
│ • Preserved records from out-of-window fragment │
│ │
└───────────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────────┐
│ SLIDING_SNAPSHOT: Visual Timeline │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Window Size = 4, Page has slots [0,1,2,3,4,5] │
│ │
│ Rev 1: FULL PAGE │
│ ┌───┬───┬───┬───┬───┬───┐ │
│ │ A │ B │ C │ D │ E │ F │ ← All slots filled │
│ └───┴───┴───┴───┴───┴───┘ │
│ slots: 0 1 2 3 4 5 │
│ │
│ Rev 2: DELTA (slot 1 modified) │
│ ┌───┬───┬───┬───┬───┬───┐ │
│ │ │ B'│ │ │ │ │ ← Only changed slot │
│ └───┴───┴───┴───┴───┴───┘ │
│ Chain: [Rev2] → [Rev1] │
│ │
│ Rev 3: DELTA (slot 2 modified) │
│ ┌───┬───┬───┬───┬───┬───┐ │
│ │ │ │ C'│ │ │ │ │
│ └───┴───┴───┴───┴───┴───┘ │
│ Chain: [Rev3] → [Rev2] → [Rev1] │
│ │
│ Rev 4: DELTA (slot 0 modified) │
│ ┌───┬───┬───┬───┬───┬───┐ │
│ │ A'│ │ │ │ │ │ │
│ └───┴───┴───┴───┴───┴───┘ │
│ Chain: [Rev4] → [Rev3] → [Rev2] → [Rev1] (window full!) │
│ │
│ Rev 5: DELTA + PRESERVATION │
│ ════════════════════════ │
│ Rev 1 is now OUT OF WINDOW! │
│ │
│ In-window bitmap check: │
│ • Slot 0: in Rev4 ✓ │
│ • Slot 1: in Rev2 ✓ │
│ • Slot 2: in Rev3 ✓ │
│ • Slot 3: NOT in any window fragment! ← PRESERVE │
│ • Slot 4: NOT in any window fragment! ← PRESERVE │
│ • Slot 5: NOT in any window fragment! ← PRESERVE │
│ │
│ Rev 5 written: │
│ ┌───┬───┬───┬───┬───┬───┐ │
│ │ │ │ │ D │ E │ F │ ← Preserved from Rev 1 │
│ └───┴───┴───┴───┴───┴───┘ │
│ Chain: [Rev5] → [Rev4] → [Rev3] → [Rev2] (Rev1 dropped!) │
│ │
│ Reading Rev 5: │
│ Combine: Rev5 + Rev4 + Rev3 + Rev2 = [A',B',C',D,E,F] │
│ Only 4 fragments needed! (not 5) │
│ │
└───────────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────────┐
│ SLIDING_SNAPSHOT vs INCREMENTAL: Write Amplification │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Both achieve bounded read chains, but HOW they do it differs: │
│ │
│ INCREMENTAL (with revisionsToRestore = 4): │
│ ────────────────────────────────────────── │
│ │
│ Rev 1: FULL PAGE [A,B,C,D,E,F] ← Write 6 records │
│ Rev 2: Δ [_,B',_,_,_,_] ← Write 1 record │
│ Rev 3: Δ [_,_,C',_,_,_] ← Write 1 record │
│ Rev 4: Δ [A',_,_,_,_,_] ← Write 1 record │
│ Rev 5: FULL PAGE [A',B',C',D,E,F] ← Write 6 records (SPIKE!) │
│ Rev 6: Δ [_,_,_,D',_,_] ← Write 1 record │
│ ... │
│ Rev 9: FULL PAGE [...] ← Write 6 records (SPIKE!) │
│ │
│ Write pattern: 6, 1, 1, 1, 6, 1, 1, 1, 6, ... │
│ Average: 2.25 records/revision, periodic spikes of 6x │
│ │
│ SLIDING_SNAPSHOT (with revisionsToRestore = 4): │
│ ─────────────────────────────────────────────── │
│ │
│ Rev 1: FULL PAGE [A,B,C,D,E,F] ← Write 6 records (initial only) │
│ Rev 2: Δ [_,B',_,_,_,_] ← Write 1 record │
│ Rev 3: Δ [_,_,C',_,_,_] ← Write 1 record │
│ Rev 4: Δ [A',_,_,_,_,_] ← Write 1 record │
│ Rev 5: Δ+preserve [_,_,_,D,E,F] ← Write 1 change + 3 preserved = 4 │
│ Rev 6: Δ+preserve [_,_,_,D',_,_] ← Write 1 change + 0 preserved = 1 │
│ Rev 7: Δ+preserve [_,_,_,_,E',_] ← Write 1 change + 0 preserved = 1 │
│ ... │
│ │
│ Write pattern: 6, 1, 1, 1, 4, 1, 1, 1, ... │
│ Preservation is amortized: each record preserved at most once per window │
│ No periodic full page rewrites, ever! │
│ │
│ Key Insight: │
│ ──────────── │
│ • INCREMENTAL: Rewrites ENTIRE page every w revisions │
│ • SLIDING_SNAPSHOT: Preserves only records NOT in window (selective) │
│ │
│ For a page with 1024 records, mostly unchanged: │
│ • INCREMENTAL: Writes 1024 records every w revisions (100% of page) │
│ • SLIDING_SNAPSHOT: Writes only ~1024/w records per revision (~12.5%) │
│ │
└───────────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────────┐
│ SLIDING_SNAPSHOT: Implementation Details │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ Key Code Paths (VersioningType.java): │
│ ───────────────────────────────────── │
│ │
│ combineRecordPages(): │
│ • Called during READ to reconstruct page from fragments │
│ • Iterates fragments newest→oldest │
│ • Uses slot bitmap for O(populated) instead of O(1024) │
│ • Early exit when all 1024 slots filled │
│ │
│ combineRecordPagesForModification(): │
│ • Called during WRITE to prepare page for modification │
│ • Creates completePage (for reads) + modifyingPage (for writes) │
│ • Tracks inWindowBitmap to identify preservation candidates │
│ • Uses lazy copy: markSlotForPreservation() instead of copying │
│ │
│ Lazy Copy Optimization: │
│ ─────────────────────── │
│ Instead of copying preserved records immediately: │
│ 1. Mark slot indices in preservationBitmap │
│ 2. Store reference to completePage │
│ 3. At commit time, copy only marked slots │
│ 4. Avoids unnecessary copies if slot is later modified │
│ │
│ Memory Optimization: │
│ ──────────────────── │
│ • inWindowBitmap: 128 bytes (vs 64KB for full page copy) │
│ • Slot iteration uses populatedSlots() not full scan │
│ • Only 2 pages allocated (complete + modifying) │
│ │
│ Configuration: │
│ ────────────── │
│ ResourceConfiguration.newBuilder("resource") │
│ .versioningApproach(VersioningType.SLIDING_SNAPSHOT) │
│ .revisionsToRestore(3) // Window size (default) │
│ .build(); │
│ │
│ Trade-off Tuning: │
│ ───────────────── │
│ • Smaller window (3): Less read cost, more preservation writes │
│ • Larger window (16): Less preservation, more fragments to combine │
│ • Default (3): Current default, optimal value is workload-dependent │
│ │
│ Future: Adaptive window sizing based on workload characteristics │
│ │
└───────────────────────────────────────────────────────────────────────────┘
Page fragments are linked via PageFragmentKey for reconstruction:
record PageFragmentKey(
int revision, // Which revision this fragment is from
long storageKey, // Offset in data file
int databaseId, // For multi-database deployments
int resourceId // Which resource within database
) {}
During commit, the storage engine:
PageFragmentKey pointing to new fragmentPageReference.pageFragmentsWhen reading a page, fragments must be fetched from storage and recombined into a complete page:
┌───────────────────────────────────────────────────────────────────────────┐
│ Fragment Fetching Pipeline │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ PageReference │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ key: 12345 (current fragment offset) │ │
│ │ pageFragments: [ (chain of older fragments) │ │
│ │ {rev=5, key=10200}, │ │
│ │ {rev=3, key=8100}, │ │
│ │ {rev=1, key=5000} │ │
│ │ ] │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Fetching (NodeStorageEngineReader.getRecordPage): │
│ ───────────────────────────────────────────────── │
│ 1. Read current fragment from offset 12345 │
│ 2. Decompress (LZ4/Zstd) │
│ 3. Deserialize into KeyValueLeafPage │
│ 4. If delta page, fetch previous fragments from pageFragments chain │
│ 5. Repeat until full page found or chain exhausted │
│ │
│ Fragment Chain (newest → oldest): │
│ │
│ [Rev 7 Δ] → [Rev 5 Δ] → [Rev 3 Δ] → [Rev 1 FULL] │
│ ↑ ↑ ↑ ↑ │
│ current fragment[0] fragment[1] fragment[2] │
│ │
└───────────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────────┐
│ Fragment Recombination Algorithm │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ combineRecordPages(List<Page> fragments): │
│ ───────────────────────────────────────── │
│ │
│ Input: [Rev7, Rev5, Rev3, Rev1] (newest first) │
│ │
│ Algorithm: │
│ 1. Create empty result page │
│ 2. Use bitmap to track which slots are filled (1024 bits) │
│ 3. For each fragment (newest → oldest): │
│ a. Get populated slots from fragment │
│ b. For each slot NOT already in result: │
│ - Copy record to result │
│ - Mark slot as filled in bitmap │
│ c. If all 1024 slots filled → stop early │
│ 4. Return reconstructed page │
│ │
│ Visual Example (slots 0-5 only): │
│ ──────────────────────────────── │
│ │
│ Rev 7 (Δ): [_][_][C][_][_][_] → Result: [_][_][C][_][_][_] │
│ Rev 5 (Δ): [_][B][_][_][E][_] → Result: [_][B][C][_][E][_] │
│ Rev 3 (Δ): [_][_][_][D][_][_] → Result: [_][B][C][D][E][_] │
│ Rev 1 (F): [A][X][X][X][X][F] → Result: [A][B][C][D][E][F] │
│ │
│ Key: Newer values "win" - slot 1 has B (Rev5), not X (Rev1) │
│ │
│ Complexity: O(k × m) where k=fragments, m=avg populated slots │
│ Optimization: Bitmap iteration instead of O(1024) scan │
│ │
└───────────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────────┐
│ Strategy-Specific Recombination Behavior │
├───────────────────────────────────────────────────────────────────────────┤
│ │
│ FULL: │
│ ───── │
│ • Only 1 fragment (the current full page) │
│ • No recombination needed │
│ • Read cost: O(1) │
│ │
│ INCREMENTAL: │
│ ──────────── │
│ • Chain of deltas until a full page │
│ • Must combine all fragments │
│ • Chain length limited by `revisionsToRestore` │
│ • Read cost: O(k) where k = chain length │
│ │
│ DIFFERENTIAL: │
│ ───────────── │
│ • Each delta references a base full page directly │
│ • Only 2 fragments needed: current delta + base full │
│ • Read cost: O(1) (always 2 fragments max) │
│ │
│ SLIDING_SNAPSHOT: │
│ ───────────────── │
│ • Like INCREMENTAL but chain bounded by window size │
│ • Out-of-window records preserved in newer fragments │
│ • Read cost: O(window_size) worst case │
│ • No unbounded chain growth │
│ │
│ Cache Behavior: │
│ ─────────────── │
│ • Reconstructed pages cached in BufferManager │
│ • Subsequent reads hit cache (no reconstruction) │
│ • Cache key: (pageKey, revision) │
│ • Invalidation: only on new revision commit │
│ │
└───────────────────────────────────────────────────────────────────────────┘
The PageContainer holds two views of a page during modification:
┌─────────────────────────────────────────────────────────────────────────────┐
│ PageContainer │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ PageContainer { │
│ Page complete; // Reconstructed page (all slots from all fragments) │
│ Page modified; // Page being modified (for delta strategies) │
│ } │
│ │
│ For FULL versioning: │
│ ──────────────────── │
│ complete == modified (same page, full copy on any modification) │
│ │
│ For DIFFERENTIAL/INCREMENTAL: │
│ ────────────────────────────── │
│ complete = fully reconstructed page (for reading current values) │
│ modified = delta page (only stores NEW changes for efficient commit) │
│ │
│ Lazy Copy Optimization: │
│ ─────────────────────── │
│ Instead of copying all slots from complete→modified upfront: │
│ 1. Mark slots for preservation with preservationBitmap │
│ 2. At commit time (addReferences), copy only preserved slots │
│ 3. Slots that were actually modified are already in modified page │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
No read locks. Ever. Readers see a frozen snapshot at a specific revision. Writers append new pages to a transaction-local log. The two never interfere. This is MVCC in its purest form.
┌─────────────────────────────────────────────────────────────────────────────┐
│ SirixDB Transaction Types │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Read-Only Transaction (NodeReadOnlyTrx) │
│ ═══════════════════════════════════════ │
│ • ALWAYS bound to a SPECIFIC revision (immutable snapshot) │
│ • Multiple read transactions can run concurrently │
│ • Never sees uncommitted changes from write transactions │
│ • Can be opened for any historical revision │
│ │
│ Example: │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ // Read latest revision │ │
│ │ var rtx = session.beginNodeReadOnlyTrx(); │ │
│ │ │ │
│ │ // Read specific historical revision │ │
│ │ var rtx5 = session.beginNodeReadOnlyTrx(5); │ │
│ │ │ │
│ │ // Read revision at specific timestamp │ │
│ │ var rtxTime = session.beginNodeReadOnlyTrx(instant); │ │
│ │ │ │
│ │ // Read revisions between two timestamps │ │
│ │ int startRev = session.getRevisionNumber(startInstant); │ │
│ │ int endRev = session.getRevisionNumber(endInstant); │ │
│ │ for (int rev = startRev; rev <= endRev; rev++) { │ │
│ │ try (var trx = session.beginNodeReadOnlyTrx(rev)) { │ │
│ │ // Process each revision in the time range │ │
│ │ } │ │
│ │ } │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Read-Write Transaction (NodeTrx) │
│ ═════════════════════════════════ │
│ • Only ONE write transaction per resource at a time │
│ • Creates a NEW revision on commit │
│ • Changes held in Transaction Intent Log until commit │
│ • Readers never blocked by writer (MVCC) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
sequenceDiagram
participant W as Write Trx
participant R1 as Read Trx 1
participant R2 as Read Trx 2
participant S as Storage
Note over W,S: Single Writer, Multiple Readers (SWMR)
R1->>S: Begin (Rev 5)
R2->>S: Begin (Rev 5)
W->>S: Begin (Rev 5 → 6)
Note over R1,R2: Read transactions see<br/>consistent snapshot
R1->>S: Read node X
W->>S: Modify node X (in TIL)
R2->>S: Read node X
Note over R1,R2: Both read OLD value<br/>(snapshot isolation)
W->>S: Commit (creates Rev 6)
R1->>S: Close
R2->>S: Close
Note over R1,R2: New read trx can see Rev 6
The TIL holds uncommitted modifications during a write transaction:
┌─────────────────────────────────────────────────────────────────────────┐
│ Transaction Intent Log (TIL) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ PageContainer[0] │ │
│ │ ┌─────────────────────┐ ┌─────────────────────┐ │ │
│ │ │ Complete (original) │ │ Modified (changed) │ │ │
│ │ └─────────────────────┘ └─────────────────────┘ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ PageContainer[1] │ │
│ │ ┌─────────────────────┐ ┌─────────────────────┐ │ │
│ │ │ Complete (original) │ │ Modified (changed) │ │ │
│ │ └─────────────────────┘ └─────────────────────┘ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ PageReference.logKey → index into this list │
│ │
│ On COMMIT: Modified pages written to storage │
│ On ROLLBACK: TIL cleared, pages discarded │
│ │
└─────────────────────────────────────────────────────────────────────────┘
KEEP_OPEN_ASYNC_FLUSH)Long-running write transactions (bulk loads, streaming ingest) can bound their memory and commit latency with two distinct mechanisms — one of which is a real commit, and one of which deliberately is not:
| Mechanism | Creates a revision? | Writes a commit record? | What it does |
|---|---|---|---|
Explicit commit() |
yes | yes | full commit protocol |
Sync auto-commit (maxNodeCount/timer, KEEP_OPEN) |
yes | yes | full commit protocol, transaction stays open |
Async pre-flush (KEEP_OPEN_ASYNC_FLUSH) |
no | no | shadow-writes leaf pages ahead of the next real commit |
Async durable commit (KEEP_OPEN_ASYNC_COMMIT) |
yes | yes | page writes on the writer thread, durability barriers in the background (docs/ASYNC_COMMIT_DESIGN.md) |
The async pre-flush is a durability optimization, not a transactional
event. When triggered, the TIL takes an O(1) snapshot (an array swap that
freezes the current entries — the “frozen zone”) and the insert thread
immediately continues on a fresh TIL generation. A background thread then
writes every KeyValueLeafPage in the frozen snapshot to the data file
through a shadow PageReference — never touching the live references — and
records each page’s disk offset and content hash in the snapshot. No indirect
pages, no RevisionRootPage, no UberPage, and no revisions-file record are
written: nothing becomes visible, and if the process crashes before the next
real commit, the pre-flushed bytes are unreachable dead space (equivalent to
rolled-back bytes in the append-only file).
At the next real commit, each pre-flushed page falls into one of two cases:
(generation, logKey)
identity so that any stale reference copies — e.g. inside CoW’d
IndirectPages that are never re-walked — resolve to the new entry rather
than to the stale disk offset. Without this forwarding chain the final
commit would durably serialize the outdated page and silently lose every
record added after the snapshot boundary (issue #1077, hit in practice by
leaf pages straddling a snapshot epoch during monotonic bulk inserts). The
stale flushed bytes remain as unreachable dead space — write amplification
on write-hot pages is the price of moving leaf I/O off the commit path.Two invariants follow that other subsystems rely on:
TAMPER_EVIDENCE_PLAN.md).graph TB
subgraph "Buffer Manager"
RPC[RecordPageCache<br/>ShardedPageCache]
RPFC[RecordPageFragmentCache<br/>ShardedPageCache]
PC[PageCache<br/>Caffeine Cache]
RRPC[RevisionRootPageCache]
PSC[PathSummaryCache]
end
subgraph "Memory Allocation"
ALLOC[MemorySegmentAllocator<br/>Off-Heap]
GUARD[Guard-Based Lifetime<br/>LeanStore/Umbra pattern]
end
subgraph "Eviction"
CLOCK[ClockSweeper<br/>Background thread]
end
READ[Read Path] --> RPC
READ --> RPFC
READ --> PC
WRITE[Write Path] --> TIL[Transaction Intent Log]
TIL --> RPC
ALLOC --> RPC
ALLOC --> RPFC
CLOCK --> RPC
CLOCK --> RPFC
GUARD --> RPC
┌─────────────────────────────────────────────────────────────────────────────┐
│ Guard-Based Page Lifetime │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. Reader acquires guard: │
│ page.acquireGuard(); // guardCount++ │
│ │
│ 2. Reader uses page: │
│ byte[] data = page.getValue(index); │
│ │
│ 3. Reader releases guard: │
│ page.releaseGuard(); // guardCount-- │
│ │
│ 4. ClockSweeper checks: │
│ if (guardCount == 0 && !hotBit) { │
│ evict(page); │
│ } │
│ │
│ Key invariant: Page cannot be evicted while guardCount > 0 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
| Cache | Purpose | Eviction Policy | Typical Size |
|---|---|---|---|
| RecordPageCache | Hot data pages | Clock sweep | 50MB+ |
| RecordPageFragmentCache | Version fragments | Clock sweep | 25MB+ |
| PageCache | Metadata pages | Caffeine LRU | 500K entries |
| RevisionRootPageCache | Revision roots | Caffeine LRU | 5K entries |
| PathSummaryCache | Path summary data | Caffeine LRU | 20 entries |
SirixDB stores checksums in parent pages to detect corruption:
┌─────────────────┐
│ Parent Page │
│ │
│ Child Refs: │
│ ┌─────────────┐ │
│ │ key: 1234 │ │
│ │ checksum: ▓▓│◄──── Checksum of child page
│ └─────────────┘ │
└────────┬────────┘
│
▼
┌─────────────────┐
│ Child Page │
│ │
│ [data...] │────► Hash of this data
│ │ must match parent's checksum
└─────────────────┘
Since SirixDB is append-only with CoW:
| Operation | Complexity | Notes |
|---|---|---|
| Point lookup by key | O(log n) | Via B-tree/HOT index |
| Range scan | O(log n + k) | k = result size |
| Insert/Update | O(log n) | Plus CoW overhead |
| Revision lookup | O(log r) | r = number of revisions |
| Time-travel query | O(log r + query) | Binary search + query |
Long.compress() → PEXT instructionResourceConfiguration.newBuilder("myresource")
.versioningApproach(VersioningType.SLIDING_SNAPSHOT)
.revisionsToRestore(8)
.hashKind(HashType.ROLLING)
.useTextCompression(true)
.buildPathSummary(true)
.indexBackendType(IndexBackendType.HOT)
.build();
| Option | Values | Default | Description |
|---|---|---|---|
versioningApproach |
FULL, INCREMENTAL, DIFFERENTIAL, SLIDING_SNAPSHOT | SLIDING_SNAPSHOT | Page versioning strategy |
revisionsToRestore |
1-N | 3 | Max page fragments to combine for reconstruction |
hashKind |
NONE, ROLLING, POSTORDER | ROLLING | Hash computation method |
indexBackendType |
RB_TREE, HOT | RB_TREE | Secondary index implementation |
buildPathSummary |
true/false | true | Enable path summary |
Document Version: 1.0
Last Updated: June 2026
Author: SirixDB Team