forgedb-storage
High-performance columnar storage engine for ForgeDB with memory-mapped file access, WAL integration, and tombstone-based deletion tracking.
Overview
forgedb-storage is the core storage engine for ForgeDB, implementing a columnar storage architecture optimized for both read and write performance. The crate provides:
- Columnar storage format - Fixed-size and variable-length columns stored separately for optimal access patterns
- Memory-mapped file access - Direct file I/O with plans for true memory mapping for zero-copy reads
- WAL integration - Write-Ahead Log support for ACID properties and crash recovery
- Tombstone tracking - Efficient soft-delete mechanism without data movement
- Type-safe API - Strong typing for columns and database operations
Architecture
Columnar Storage Format
The storage engine uses a columnar layout where each column is stored in separate files, optimized for the column's data type:
data/
├── manifest.json # Database metadata (schema, row count, columns)
├── tombstones.bin # Deletion bitmap (1 byte per row)
├── fixed/
│ └── u64_0.bin # Fixed-size column (8 bytes per row)
└── variable/
├── string_data_0.bin # Variable-length data (append-only)
└── string_offsets_0.bin # (offset, length) pairs (16 bytes per row)
Fixed-Size vs Variable-Length Columns
Fixed-Size Columns
Fixed-size columns (u64, i64, f64, uuid, etc.) are stored in files where each value occupies a fixed number of bytes:
- Storage:
fixed/u64_{index}.bin - Layout: Sequential values with no overhead
- Access: O(1) random access via
offset = index * value_size - Overhead: Zero bytes per value
Example: For u64 columns, each value takes exactly 8 bytes.
Variable-Length Columns
Variable-length columns (strings) use a two-file approach:
- Data file (
variable/string_data_{index}.bin): Append-only storage of actual string bytes - Offsets file (
variable/string_offsets_{index}.bin): Pairs of (offset, length) as u64 values
- Access: O(1) random access (read offset pair, then read string from data file)
- Overhead: 16 bytes per string (8 bytes offset + 8 bytes length)
Memory-Mapped Files
The storage engine uses direct file I/O with seek operations. Future optimizations will include true memory-mapped files for:
- Zero-copy reads
- Operating system-managed caching
- Reduced memory footprint
- SIMD-friendly sequential access patterns
Tombstone Bitmap for Deletions
Instead of physically removing data, deletions are tracked using a tombstone bitmap:
- Storage:
tombstones.bin - Format: 1 byte per row (0 = active, 1 = deleted)
- Benefits:
- No data movement required
- Fast delete operations
- Preserves row IDs
- Compaction: Background compaction can reclaim space (see
forgedb-compaction)
Usage Examples
Creating a Database
use ;
use PathBuf;
// Create or open a database
let mut db = open?;
// Define schema
let columns = vec!;
db.set_columns;
db.save_manifest?;
Reading and Writing Records
Writing to Fixed-Size Columns
use FixedColumn;
// Open a u64 column
let mut id_column = new?;
// Append values
id_column.append_u64?;
id_column.append_u64?;
id_column.append_u64?;
Writing to Variable-Length Columns
use VariableColumn;
// Open a string column
let mut email_column = new?;
// Append strings
email_column.append_string?;
email_column.append_string?;
email_column.append_string?;
Reading from Columns
// Read from fixed-size column
let id = id_column.read_u64?; // Returns 1001
assert_eq!;
// Read from variable-length column
let email = email_column.read_string?; // Returns "bob@example.com"
assert_eq!;
Tombstone Tracking
use Tombstones;
// Open tombstone file
let mut tombstones = new?;
// Mark records as active (false) or deleted (true)
tombstones.append?; // Record 0: active
tombstones.append?; // Record 1: active
tombstones.append?; // Record 2: deleted
// Check deletion status
assert_eq!;
assert_eq!;
assert_eq!;
Transaction Support via WAL Integration
The storage engine integrates with forgedb-wal for ACID properties:
use ;
// Open database with WAL enabled
let mut db = open_with_wal?;
// Check if WAL is enabled
assert!;
// Begin a transaction
if let Some = db.wal_mut
WAL Integration Example
use ;
// Open database with WAL
let mut db = open_with_wal?;
// Create a transaction
let mut txn = new;
// Add operations to transaction
txn.insert;
// Commit transaction
if let Some = db.wal_mut
API Documentation
Key Types
Database
The main entry point for storage operations. Manages the database directory and manifest.
Methods:
open(path: PathBuf) -> io::Result<Self>- Open or create a databaseopen_with_wal(path: PathBuf, fsync_policy: FsyncPolicy) -> io::Result<Self>- Open with WAL enabledsave_manifest() -> io::Result<()>- Save manifest to diskget_manifest() -> &Manifest- Get current manifestset_columns(columns: Vec<ColumnMetadata>)- Update column definitionsupdate_row_count(count: usize)- Update row count in manifestwal() -> Option<&WalManager>- Get immutable reference to WALwal_mut() -> Option<&mut WalManager>- Get mutable reference to WALhas_wal() -> bool- Check if WAL is enabledfixed_column_path(index: usize) -> PathBuf- Get path for fixed-size column filevariable_data_path(index: usize) -> PathBuf- Get path for variable-length data filevariable_offsets_path(index: usize) -> PathBuf- Get path for variable-length offsets filetombstones_path() -> PathBuf- Get path for tombstone bitmap file
Manifest
Database metadata stored in manifest.json.
Fields:
schema_version: u32- Schema version numberrow_count: usize- Total number of rows (including deleted)columns: Vec<ColumnMetadata>- Column definitionswal_enabled: bool- Whether WAL is enabledlast_checkpoint: u64- Last WAL checkpoint position
ColumnMetadata
Column definition in the manifest.
Fields:
name: String- Column namecolumn_type: ColumnType- Column data typecolumn_index: usize- Index within columns of the same type
ColumnType
Enumeration of supported column types.
Variants:
U64- Unsigned 64-bit integerString- Variable-length UTF-8 string
FixedColumn
Storage for fixed-size column data.
Methods:
new(path: PathBuf, value_size: usize) -> io::Result<Self>- Create or open column fileappend_u64(value: u64) -> io::Result<()>- Append a u64 valueread_u64(index: usize) -> io::Result<u64>- Read value at indexlen() -> usize- Get number of values
VariableColumn
Storage for variable-length column data.
Methods:
new(data_path: PathBuf, offsets_path: PathBuf) -> io::Result<Self>- Create or open column filesappend_string(value: &str) -> io::Result<()>- Append a string valueread_string(index: usize) -> io::Result<String>- Read string at indexlen() -> usize- Get number of strings
Tombstones
Deletion tracking bitmap.
Methods:
new(path: PathBuf) -> io::Result<Self>- Create or open tombstone fileappend(deleted: bool) -> io::Result<()>- Mark new row as active/deletedis_deleted(index: usize) -> io::Result<bool>- Check if row is deletedlen() -> usize- Get number of rows tracked
WAL Re-exports
The following types are re-exported from forgedb-wal for convenience:
FsyncPolicy- Controls when WAL is fsynced to diskTransaction- Groups WAL operations with atomic commitTransactionId- Unique identifier for transactionsWalEntry- Single entry in the WALWalManager- High-level WAL interfaceWalOperation- Type of operation (insert, update, delete)WalValue- Value types supported in WAL
Performance Characteristics
Memory Mapping Benefits
The columnar storage format is designed to take advantage of memory-mapped files:
- Zero-copy reads: Direct access to file contents without copying to memory
- OS-managed caching: Operating system handles page cache efficiently
- Lazy loading: Only accessed pages are loaded into memory
- SIMD operations: Sequential column layout enables vectorized operations
Columnar Scan Performance
Scanning columns is highly efficient due to:
- Sequential access: Each column is stored contiguously
- Cache-friendly: Modern CPUs prefetch sequential data effectively
- Selective reads: Only read columns needed for query
- Vectorization: SIMD operations on fixed-size numeric columns
Performance Goals:
- Random access: < 1μs per value
- Full table scan (1M rows): < 100ms
- Insert throughput: > 100K rows/sec
Write Performance
- Fixed columns: O(1) append (single seek + write)
- Variable columns: O(1) append (data write + offset write)
- Tombstones: O(1) append (single byte write)
- Manifest: Small JSON file, negligible overhead
Read Performance
- Fixed columns: O(1) random access (single seek + read)
- Variable columns: O(1) random access (two seeks: offset, then data)
- Full scan: O(n) sequential reads per column
Space Efficiency
- Fixed columns: Zero overhead (exact type size per value)
- Variable columns: 16 bytes overhead per value (offset + length)
- Tombstones: 1 byte per row
- Manifest: ~100-500 bytes (JSON metadata)
File Layout
Directory Structure
<database_root>/
├── manifest.json # Database metadata
├── tombstones.bin # Row deletion bitmap
├── wal.log # Write-Ahead Log (if WAL enabled)
├── fixed/ # Fixed-size columns directory
│ ├── u64_0.bin # First u64 column
│ ├── u64_1.bin # Second u64 column
│ └── ... # Additional fixed-size columns
└── variable/ # Variable-length columns directory
├── string_data_0.bin # First string column data
├── string_offsets_0.bin # First string column offsets
├── string_data_1.bin # Second string column data
├── string_offsets_1.bin # Second string column offsets
└── ... # Additional variable-length columns
File Naming Conventions
Fixed-Size Columns
Pattern: fixed/{type}_{index}.bin
type: Data type (e.g.,u64,i64,f64)index: Zero-based index among columns of the same type
Examples:
fixed/u64_0.bin- First u64 columnfixed/u64_1.bin- Second u64 column
Variable-Length Columns
Pattern: variable/{type}_data_{index}.bin and variable/{type}_offsets_{index}.bin
type: Data type (currently onlystring)index: Zero-based index among columns of the same type
Examples:
variable/string_data_0.bin- First string column datavariable/string_offsets_0.bin- First string column offsets
Manifest
- File:
manifest.json - Format: JSON
- Content: Schema version, row count, column metadata, WAL settings
Example manifest.json:
Tombstones
- File:
tombstones.bin - Format: Binary bitmap (1 byte per row)
- Values:
0x00= active,0x01= deleted
Write-Ahead Log
- File:
wal.log(when WAL is enabled) - Format: Binary log entries with checksums
- See:
forgedb-walcrate documentation for details
Testing
Running Tests
Run all storage tests:
Run specific test:
Run with output:
Test Coverage
The test suite includes:
- ✅ Fixed column operations (append, read, persistence)
- ✅ Variable column operations (append, read, persistence, empty/large strings)
- ✅ Tombstone tracking (append, check, persistence)
- ✅ Database manifest (save, load, column definitions)
- ✅ Out-of-bounds access error handling
- ✅ Data persistence across database reopens
Example Test
use FixedColumn;
use PathBuf;
Related Crates
- forgedb-wal: Write-Ahead Log for ACID properties and crash recovery
- forgedb-compaction: Background compaction for reclaiming tombstone space
Links to Documentation
- ForgeDB Architecture - Overall system design and data flow
- Public Crates Guide - Complete guide to runtime libraries
- Development Guide - Setting up development environment
License
Licensed under either of:
- Apache License, Version 2.0 (LICENSE-APACHE)
- MIT license (LICENSE-MIT)
at your option.