Skip to content
HeliosDB HeliosDB Nano

BRANCH STORAGE DIAGRAMS - Part 2 of 2

BRANCH STORAGE DIAGRAMS - Part 2 of 2

Advanced Diagrams

Navigation: Index | ← Part 1 | Part 2

══════════════════════════════════════════════════════════════════

Branches: main (id:1) [Active] dev (id:2) [Active]

Data: data:1:key1:100 -> v1 (main) data:1:key2:105 -> v2 (main) data:2:key1:120 -> v3 (dev)

Space freed: 2 versions + metadata ≈ 200 bytes

---


## Diagram 8: Branch Transaction Lifecycle

┌─────────────────────────────────────────────────────────────────┐ │ Branch Transaction State Machine │ └─────────────────────────────────────────────────────────────────┘

┌──────────┐
│  BEGIN   │ ──> Create BranchTransaction
└────┬─────┘     • Allocate snapshot ID
     │           • Load branch metadata
     │           • Build parent chain
     │           • Initialize write set
     ▼
┌──────────┐
│  ACTIVE  │
└────┬─────┘
     │
     ├─── get(key) ────> Read from branch + parents
     │
     ├─── put(key, val) ────> Buffer in write set
     │
     ├─── delete(key) ────> Mark as tombstone
     │
     │
     ├─── commit() ─────┐
     │                  │
     └─── rollback() ───┤
                        │
                        ▼
          ┌─────────────────────────┐
          │  Validate & Finalize    │
          │  • Check conflicts      │
          │  • Get commit timestamp │
          │  • Write to RocksDB     │
          └─────────┬───────────────┘
                    │
            ┌───────┴────────┐
            │                │
            ▼                ▼
     ┌──────────┐      ┌──────────┐
     │ COMMITTED│      │  ABORTED │
     └──────────┘      └──────────┘

Example Timeline: ═════════════════════════════════════════════════════════════════

T0: BEGIN TRANSACTION ON BRANCH dev • snapshot_id = 150 • branch_id = 2 • parent_chain = [(1, 100)] • write_set = {}

T1: SELECT * FROM users WHERE id=1 • Read from dev (not found) • Read from main (found at T100) • Return value

T2: UPDATE users SET name=‘Alice’ WHERE id=1 • Add to write_set: {users:1 -> ‘Alice’} • No database write yet

T3: INSERT INTO users VALUES (2, ‘Bob’) • Add to write_set: {users:2 -> ‘Bob’}

T4: COMMIT • Validate: No conflicts • Get commit_ts = 160 • Write: data:2:users:1:160 -> ‘Alice’ • Write: data:2:users:2:160 -> ‘Bob’ • RocksDB batch write (atomic) • State = COMMITTED

---


## Diagram 9: Storage Efficiency Comparison

┌─────────────────────────────────────────────────────────────────┐ │ Storage Overhead: Branching vs. Full Copy │ └─────────────────────────────────────────────────────────────────┘

Scenario: 1GB database, 3 branches, 10% modified per branch

Traditional Full Copy: ═════════════════════════════════════════════════════════════════

main: ████████████████████ 1GB branch1: ████████████████████ 1GB (full copy) branch2: ████████████████████ 1GB (full copy) branch3: ████████████████████ 1GB (full copy) ═══════════════════════════════════════ Total: 4GB Overhead: 300%

Copy-on-Write Branching: ═════════════════════════════════════════════════════════════════

main: ████████████████████ 1GB │ │ │ │ │ │ │ │ │ └───────────┐ │ │ │ └───────┐ │ │ │ └───┐ │ │ └───┐ │ │ │ │ │ │ │ branch1: ██ │ ── │ ── │ ── 100MB (10% modified) branch2: ── ██ ── │ ── │ 100MB (10% modified) branch3: ── ── ██ ██ ── ── 100MB (10% modified) ═══════════════════════════════════════ Total: 1.3GB Overhead: 30%

Savings: 2.7GB (67.5% reduction)

Breakdown: ═════════════════════════════════════════════════════════════════

Component Full Copy CoW Savings ───────────────────────────────────────────────────────────── Original data 1GB 1GB 0% Branch 1 data 1GB 100MB 90% Branch 2 data 1GB 100MB 90% Branch 3 data 1GB 100MB 90% Metadata 4KB 12KB - ───────────────────────────────────────────────────────────── Total 4GB 1.3GB 67.5%

Key Insight: ═════════════════════════════════════════════════════════════════

Storage overhead scales with: • Number of modified keys (not total keys) • Branch depth (metadata only)

NOT with: • Total database size • Number of branches

---


## Diagram 10: Performance Characteristics

┌─────────────────────────────────────────────────────────────────┐ │ Branch Operations Performance │ └─────────────────────────────────────────────────────────────────┘

Operation Latency (Typical): ═════════════════════════════════════════════════════════════════

CREATE BRANCH: ████ 5ms • Metadata write only • O(1) complexity • Independent of database size

DROP BRANCH: ████████████ 30ms • Metadata update + GC scheduling • O(1) for drop, O(N) for GC (async)

MERGE BRANCH (1K changes): ████████████████████ 50ms • Three-way diff • O(C) where C = changed keys

MERGE BRANCH (100K changes): ██████████████████████████████ 2s • Linear in changes • Parallel merge possible

Read Latency by Hit Type: ═════════════════════════════════════════════════════════════════

Current Branch Hit: ███ 0.1ms • Single RocksDB get • Same as non-branched read

Parent Branch Hit (depth 1): ████████ 0.3ms • 2 RocksDB gets • +0.2ms overhead

Parent Chain Hit (depth 5): ████████████████ 0.6ms • Up to 5 RocksDB gets • +0.5ms overhead

Optimization (with Bloom Filter): █████ 0.2ms • Fast path: Check bloom filter • Skip current branch if key not modified

Write Latency: ═════════════════════════════════════════════════════════════════

First Write (CoW): ██████████ 0.35ms • Parent lookup + write • +0.15ms vs non-branched

Subsequent Writes: ███████ 0.25ms • Direct write (no parent lookup) • +0.05ms vs non-branched

Throughput Impact: ═════════════════════════════════════════════════════════════════

Non-branched: ████████████████████████████████████████ 100% 50,000 reads/sec

Branched (current branch): ██████████████████████████████████████ 95% 47,500 reads/sec

Branched (parent chain depth 3): ████████████████████████████████ 85% 42,500 reads/sec

Recommendation: Keep branch depth < 5 for optimal performance

---


## Diagram 11: Conflict Detection Matrix

┌─────────────────────────────────────────────────────────────────┐ │ Merge Conflict Detection Matrix │ └─────────────────────────────────────────────────────────────────┘

Legend: Base = Value at merge base (common ancestor) Source = Value in source branch Target = Value in target branch

  •  = Key doesn't exist

⚠ = Conflict

Scenario Analysis: ═════════════════════════════════════════════════════════════════

Key Base Source Target Result Action ─────────────────────────────────────────────────────────────── 1 A A A No change Keep A 2 A B A Source change Apply B 3 A A B Target change Keep B 4 A B B Same change Apply B (no conflict) 5 A B C ⚠ CONFLICT Resolution needed 6 A - A Source delete Delete 7 A A - Target delete Keep deleted 8 A - B ⚠ CONFLICT Delete vs modify 9 A B - ⚠ CONFLICT Modify vs delete 10 - A - Source add Apply A 11 - - A Target add Keep A 12 - A B ⚠ CONFLICT Different adds

Conflict Resolution Strategies: ═════════════════════════════════════════════════════════════════

  1. branch_wins (Source Priority): Row 5: Use B (source) Row 8: Use B (source - resurrect) Row 9: Delete (source) Row 12: Use A (source)

  2. target_wins (Target Priority): Row 5: Use C (target) Row 8: Keep deleted (target) Row 9: Use B (target - resurrect) Row 12: Use B (target)

  3. fail (Manual Resolution): Row 5: ERROR: Conflict on key5 Row 8: ERROR: Conflict on key8 (delete vs modify) Row 9: ERROR: Conflict on key9 (modify vs delete) Row 12: ERROR: Conflict on key12 (different adds)

Example Output: ═════════════════════════════════════════════════════════════════

MERGE BRANCH dev INTO main WITH (conflict_resolution = ‘fail’);

ERROR: Merge conflicts detected (3 conflicts)

Conflict 1: key=“users:123” Base: {“name”: “Alice”, “age”: 30} Source: {“name”: “Alice”, “age”: 31} Target: {“name”: “Alice Smith”, “age”: 30}

Conflict 2: key=“orders:456” Base: {“status”: “pending”} Source: DELETED Target: {“status”: “shipped”}

Conflict 3: key=“products:789” Base: (not exists) Source: {“name”: “Widget A”, “price”: 10} Target: {“name”: “Widget B”, “price”: 15}

Resolution required. Use ‘branch_wins’ or ‘target_wins’, or resolve manually.

---


## Diagram 12: MVCC + Branching Integration

┌─────────────────────────────────────────────────────────────────┐ │ MVCC Snapshot Isolation + Branch Isolation │ └─────────────────────────────────────────────────────────────────┘

Timeline with 2 Branches (main, dev): ═════════════════════════════════════════════════════════════════

Time: T0 T10 T20 T30 T40 T50 T60 T70 T80 T90 T100 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ main: │ ■────┼────┼────■────┼────┼────■────┼────┼────┤ │ A │ │ B │ │ C │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └────┼────┼────┴────┼────┼────┼────┼────┼────┤ │ │ │ │ │ │ │ │ │ dev: └─────────●────┼─────────■────┼────■────┼────┼────┤ (branch) │ D │ E │ │ │ T20 │ │ │ │ │ │ │

Transaction Visibility: ═════════════════════════════════════════════════════════════════

Tx1: main, snapshot@T50 ├─ Can see: A@T10, B@T40 ├─ Cannot see: C@T70 (future) └─ Cannot see: dev branch (different branch)

Tx2: dev, snapshot@T75 ├─ Can see: D@T50, E@T60 ├─ Cannot see: A@T10 (before branch point T20) ├─ Can see: A@T10 via parent (main@T20) └─ Cannot see: C@T70 (different branch, after branch point)

Tx3: main, snapshot@T100 ├─ Can see: A@T10, B@T40, C@T70 └─ Cannot see: dev branch (isolated)

Visibility Rules: ═════════════════════════════════════════════════════════════════

For transaction TX on branch B with snapshot S:

Version V is visible IF: 1. V.branch == B AND V.timestamp <= S (same branch, MVCC visibility)

OR


2. V.branch in parent_chain(B) AND
   V.timestamp <= snapshot_at_branch_point(B, V.branch)
   (parent branch, at branch creation time)

Implementation: ═════════════════════════════════════════════════════════════════

fn is_visible( version: &Version, tx_branch: BranchId, tx_snapshot: SnapshotId, parent_chain: &[(BranchId, SnapshotId)] ) -> bool { // Rule 1: Same branch MVCC if version.branch_id == tx_branch { return version.timestamp <= tx_snapshot; }

// Rule 2: Parent chain visibility
for (parent_id, parent_snapshot) in parent_chain {
    if version.branch_id == *parent_id {
        return version.timestamp <= *parent_snapshot;
    }
}


false

}

---


## Summary


These diagrams illustrate:


1. **Copy-on-Write Efficiency**: Minimal storage overhead through shared data
2. **Hierarchy Navigation**: Parent chain resolution for reads
3. **Physical Layout**: RocksDB key space organization
4. **Transaction Lifecycle**: Complete read/write/commit flow
5. **Merge Process**: Three-way merge with conflict detection
6. **Garbage Collection**: Automatic cleanup of dropped branches
7. **Performance**: Sub-10ms branch creation, <5% read overhead
8. **Conflict Resolution**: Comprehensive conflict detection matrix
9. **MVCC Integration**: Snapshot isolation + branch isolation
10. **Storage Efficiency**: 67.5% savings vs. full copy


**Next Steps**:
- Review architecture document: BRANCH_STORAGE_ARCHITECTURE.md
- Begin implementation with core data structures
- Implement unit tests for each component
- Performance benchmarking and optimization