DAG (Directed Acyclic Graph)¶

Understanding Blacklake's commit graph and object relationships.

Overview¶

Blacklake uses a content-addressable directed acyclic graph (DAG) to track object relationships, similar to Git but optimized for data storage.

Object Types¶

Blob Objects¶

graph TD
    CONTENT[File Content] --> HASH[SHA-256 Hash]
    HASH --> BLOB[Blob Object]
    BLOB --> STORE[Object Store]
    BLOB --> META[Metadata]

Properties: - Content: Raw file data - Hash: SHA-256 of content - Type: blob - Immutable: Cannot be modified

Tree Objects¶

graph TD
    TREE[Tree Object] --> ENTRY1[Entry 1]
    TREE --> ENTRY2[Entry 2]
    TREE --> ENTRY3[Entry 3]

    ENTRY1 --> BLOB1[Blob Object]
    ENTRY2 --> BLOB2[Blob Object]
    ENTRY3 --> TREE2[Tree Object]

Properties: - Entries: List of child objects - Structure: Directory-like organization - References: Points to other objects

Commit Objects¶

graph TD
    COMMIT[Commit Object] --> TREE[Tree Object]
    COMMIT --> PARENT1[Parent Commit]
    COMMIT --> PARENT2[Parent Commit]
    COMMIT --> AUTHOR[Author]
    COMMIT --> MESSAGE[Message]

Properties: - Tree: Root tree object - Parents: Previous commits - Author: Creator information - Message: Commit description - Timestamp: Creation time

Tag Objects¶

graph TD
    TAG[Tag Object] --> COMMIT[Commit Object]
    TAG --> NAME[Tag Name]
    TAG --> MESSAGE[Tag Message]
    TAG --> TARGET[Target Object]

Properties: - Target: Referenced object - Name: Tag identifier - Message: Tag description - Type: tag

Object Relationships¶

Content Addressing¶

graph LR
    CONTENT[File Content] --> SHA256[SHA-256 Hash]
    SHA256 --> OBJECT[Object Store]
    OBJECT --> REFERENCE[Object Reference]
    REFERENCE --> COMMIT[Commit Object]

Benefits: - Deduplication: Same content = same hash - Integrity: Hash verification - Efficiency: Store once, reference many

Object References¶

graph TD
    COMMIT[Commit: abc123] --> TREE[Tree: def456]
    TREE --> BLOB1[Blob: ghi789]
    TREE --> BLOB2[Blob: jkl012]
    TREE --> TREE2[Tree: mno345]
    TREE2 --> BLOB3[Blob: pqr678]

Commit Graph¶

Linear History¶

graph LR
    C1[Commit 1] --> C2[Commit 2]
    C2 --> C3[Commit 3]
    C3 --> C4[Commit 4]
    C4 --> C5[Commit 5]

Branching¶

graph TD
    C1[Commit 1] --> C2[Commit 2]
    C2 --> C3[Commit 3]
    C2 --> B1[Branch 1]
    B1 --> C4[Commit 4]
    B1 --> C5[Commit 5]
    C3 --> C6[Commit 6]

Merging¶

graph TD
    C1[Commit 1] --> C2[Commit 2]
    C2 --> C3[Commit 3]
    C2 --> B1[Branch 1]
    B1 --> C4[Commit 4]
    B1 --> C5[Commit 5]
    C3 --> C6[Commit 6]
    C5 --> C7[Merge Commit]
    C6 --> C7

Object Storage¶

Storage Layout¶

.bl/
├── objects/
│   ├── ab/
│   │   └── c123...def
│   ├── cd/
│   │   └── e456...fgh
│   └── gh/
│       └── i789...jkl
├── refs/
│   ├── heads/
│   │   ├── main
│   │   └── feature
│   └── remotes/
│       └── origin/
└── HEAD

Object Types¶

Hash Addressing¶

SHA-256 Hashing¶

import hashlib

def hash_content(content: bytes) -> str:
    """Generate SHA-256 hash of content."""
    return hashlib.sha256(content).hexdigest()

# Example
content = b"Hello, World!"
hash_value = hash_content(content)
# Result: "a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e"

Object ID Format¶

blob:sha256:a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
tree:sha256:b591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
commit:sha256:c591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

References¶

Branch References¶

graph TD
    HEAD[HEAD] --> MAIN[refs/heads/main]
    MAIN --> COMMIT[Commit: abc123]
    COMMIT --> TREE[Tree: def456]
    TREE --> BLOB1[Blob: ghi789]
    TREE --> BLOB2[Blob: jkl012]

Remote References¶

graph TD
    ORIGIN[refs/remotes/origin/main] --> COMMIT[Commit: abc123]
    ORIGIN --> TREE[Tree: def456]
    TREE --> BLOB1[Blob: ghi789]
    TREE --> BLOB2[Blob: jkl012]

Object Immutability¶

Immutable Objects¶

graph TD
    OBJECT[Object: abc123] --> CONTENT[Content: "Hello"]
    OBJECT --> HASH[Hash: abc123...]
    HASH --> VERIFY[Content Verification]
    VERIFY --> VALID[Valid Object]
    VERIFY --> INVALID[Invalid Object]

Properties: - Content: Cannot be modified - Hash: Immutable identifier - Integrity: Hash verification - Deduplication: Same content = same hash

Object Verification¶

def verify_object(object_id: str, content: bytes) -> bool:
    """Verify object integrity."""
    expected_hash = object_id.split(':')[-1]
    actual_hash = hashlib.sha256(content).hexdigest()
    return expected_hash == actual_hash

Garbage Collection¶

Unreachable Objects¶

graph TD
    REACHABLE[Reachable Objects] --> REFS[References]
    REACHABLE --> COMMITS[Commits]
    REACHABLE --> TREES[Trees]
    REACHABLE --> BLOBS[Blobs]

    UNREACHABLE[Unreachable Objects] --> ORPHAN[Orphaned Blobs]
    UNREACHABLE --> DELETED[Deleted Objects]

GC Process¶

1. Mark: Find all reachable objects
2. Sweep: Remove unreachable objects
3. Compact: Optimize storage layout

Performance Considerations¶

Object Retrieval¶

graph TD
    REQUEST[Object Request] --> CACHE[Local Cache]
    CACHE --> HIT[Cache Hit]
    CACHE --> MISS[Cache Miss]
    MISS --> STORE[Object Store]
    STORE --> OBJECT[Object Data]
    OBJECT --> CACHE

Storage Optimization¶

Examples¶

Simple File¶

# Create file
echo "Hello, World!" > hello.txt

# Add to repository
blacklake add hello.txt
blacklake commit -m "Add hello.txt"

# Object structure
# blob:sha256:a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

Directory Structure¶

# Create directory
mkdir data
echo "Data 1" > data/file1.txt
echo "Data 2" > data/file2.txt

# Add directory
blacklake add data/
blacklake commit -m "Add data directory"

# Object structure
# tree:sha256:b591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
# ├── blob:sha256:c591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e (file1.txt)
# └── blob:sha256:d591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e (file2.txt)

Next Steps¶

• Architecture Overview - System architecture
• CLI Reference - Command documentation
• Metadata Model - Semantic metadata