`data_objects` — LLAMA's Primary Data Units

This module defines the delta and base page types that form the core storage primitives of LLAMA

Overview

LLAMA is type-blind with respect to delta payloads: it does not interpret the bytes an access method writes into a delta's payload. However, LLAMA does understand the structure and state of of core delta types.

What LLAMA can see

Observable Attribute	accessible by
Delta kind (Flush / Update / PartialSwap / …)	[`Delta::delta_type`]
Total wire size	[`Delta::len`]
Page identifier	[`Delta::pid`]
Durability / flush state	[`Delta::is_durable`]
Packed status bits	[`Delta::packed_bits`]
Pointer to prior state	[`Delta::prior_state_ptr`]
Raw payload bytes	[`Delta::payload`]

Key Types at a Glance

Type	Role
[`DeltaData`]	Owned wire buffer; type-blind field accessors
[`Delta`]	Object-safe trait every concrete delta implements
[`DeltaRef`]	`Arc<dyn Delta>` — cheap, cloneable erased handle
[`FlushDelta`]	Marks a page as durably flushed (`F` bit) up to this point in the delta chain
[`UpdateDelta`]	Carries an insert / update / delete (`U` bit)
[`PartialSwapDelta`]	Records partial page eviction (`P` bit)
[`RelocationDelta`]	Describes relocated page regions (`Re` bit)
[`BasePage`]	Fixed-size base pages (4 KB – 64 KB)
[`PageState`]	In-memory version chain (delta DAG + base)
[`PageStateIter`]	DAG-safe iterator over a [`PageState`] chain

Delta Version Chain

Deltas are prepended to form a singly-linked (occasionally DAG-shaped) version chain:

Delta(N) → Delta(N-1) → … → Delta(0) → BasePage

A [PartialSwapDelta] introduces a second pointer (last_flushed), turning the chain into a DAG. [PageStateIter] handles this safely by tracking visited nodes.

Wire Format

Every delta is serialised into a contiguous byte buffer with the following layout:

┌──────┬──────────┬──────┬──────────────┬─────────────────┬──────────────────┬──────┬─────────┐
│ Len  │ LSS Off  │ PID  │ Packed Bits  │ Prior State Ptr │ Last Flushed Ptr │ PLen │ Payload │
│ u32  │ u32      │ u32  │ u8           │ u64             │ u64              │ u32  │  [u8]   │
└──────┴──────────┴──────┴──────────────┴─────────────────┴──────────────────┴──────┴─────────┘
   0       4         8        12               13                 21              29      33

All multi-byte integers are little-endian.

Quick-Start Examples

Building and inspecting an [`UpdateDelta`]

use pagedelta::{UpdateDelta, Delta, DeltaRef};
use std::sync::Arc;

// Construct an update delta carrying "hello world" for page 7,
// whose prior state lives at address 0x1234.
let d: DeltaRef = UpdateDelta::new_shared_delta(b"hello world", 0x1234, 7);

assert!(d.data().is_update());
assert_eq!(d.pid(), 7);
assert_eq!(d.prior_state_ptr(), 0x1234);
assert_eq!(d.payload(), b"hello world");

Downcasting a type-erased [`DeltaRef`]

use pagedelta::{DeltaRef, UpdateDelta, downcast_delta};
use std::sync::Arc;

let d: DeltaRef = UpdateDelta::new_shared_delta(b"kv", 0, 1);
let concrete = downcast_delta::<UpdateDelta>(&d).expect("wrong type");
assert!(concrete.data().is_update());

Building a [`PageState`] chain and iterating it

use pagedelta::{BasePage, PageState, UpdateDelta, FlushDelta, PartialSwapDelta};
use std::sync::Arc;

let base = Arc::new(PageState::Base(BasePage::small()));
let s1   = base.push_delta(UpdateDelta::new_shared_delta(b"op1", 0, 0));
let s2   = s1.push_delta(FlushDelta::new_shared_delta(0xDEAD, 0));
let flush_point = Arc::clone(&s2);
let s3   = s2.push_partial_swap(
    PartialSwapDelta::new_shared_delta(b"swap", 0, 0, 0),
    flush_point,
);

// The iterator visits every node exactly once, even the shared flush node.
for node in s3.iter() {
    println!("{:?}", node);
}

pagedelta 0.1.0

data_objects — LLAMA's Primary Data Units