Research: Holotree Packfile Format for Reduced Filesystem Churn

[joshyorko]

Research: Holotree Packfile Format

Executive Summary

Following PR #64 (zstd compression), profiling shows that filesystem operations are now the dominant bottleneck at 25-40% of CPU time, not decompression or hashing. This issue explores a Git-inspired packfile format to reduce syscall overhead.

---

🔬 RESEARCH FINDINGS (Self-Answered Questions)

Q1: Relocation Handling ✅ ANSWERED

Data from actual catalogs:

Catalog	Total Files	Relocations	%
Large env (cd27b9ae)	25,367	666	2.6%
Micromamba layer (68705df3)	11,443	652	5.7%

Conclusion: 94-97% of files need NO relocation handling!

Strategy:

• Stream 94%+ directly without seek-back
• For relocatable files: write first, then seek back for rewrites
• OR: Hybrid approach - keep relocatable files as individual files

---

Q2: Windows AV Behavior ✅ ANSWERED

Research findings:

• Windows Defender scans on WRITE (file creation), not just read
• Each new file triggers an AV scan event
• Many small files = many scan events = slow
• Single large file = fewer scan events = faster

Benchmark (Linux, pattern applies cross-platform):

Operation                    Time        Speedup
──────────────────────────────────────────────────
Create 1000 x 1KB files     2.103s      baseline
Create 1 x 1MB file         0.005s      420x faster!
Read 1000 individual files  0.013s      baseline
Read 1 packed file          0.001s      13x faster

Impact Analysis:

Operation	Current	Packfile	Benefit
READ from hololib	10,563 opens	2 opens	✅ 99.98% reduction
WRITE to holotree	10,563 creates	10,563 creates	❌ Unchanged
AV scan events (read)	~10,563	~2	✅ Major reduction
AV scan events (write)	~10,563	~10,563	❌ Still required

Conclusion: Packfile helps the READ side dramatically (~50% syscall reduction). The WRITE side is unchanged - we still must create individual destination files. However, eliminating temp files (.part files) could help:

Current flow:

1. open(hololib/digest)           # AV scan
2. create(dest.part)              # AV scan  
3. write data
4. rename(dest.part → dest)       # AV scan

Optimized flow (streaming):

1. read from pack (single open)   # 1 AV scan for entire pack
2. create(dest)                   # AV scan
3. stream write directly

This eliminates the .part temp file, reducing AV events by ~33% on the write side too.

---

Q3: Enterprise / Shared Storage ✅ ANSWERED

Code analysis (common/variables.go, htfs/commands.go):

• SharedHolotree mode already exists
• Uses file locking (pathlib.Locker) for coordination
• RCC_REMOTE_ORIGIN for pulling from shared locations

Packfile is BETTER for shared storage:

Factor	Individual Files	Packfile
Network round-trips	~10,563	~2
Lock contention	Per-file	Per-pack
Atomic updates	Complex	Simple (write + rename)
Integrity check	Per-file hash	Single pack hash

Concern: Pack corruption affects all files (vs single file)
Mitigation:

• Pack-level checksums (already planned)
• Atomic write (temp + rename)
• Existing catalog still tracks individual file hashes

---

Current State Analysis

Profiling Data (Large Environment - pandas, SQLAlchemy, pymongo)

Component	gzip (before)	zstd (after)	% of Time
Decompression	2.99s (43%)	0.19s (3%)	✅ Fixed by PR #64
SHA256 hashing	1.09s (15.7%)	1.27s (20.5%)	Acceptable
Syscalls (I/O)	1.32s (19%)	1.60s (25.8%)	🎯 New bottleneck

File Statistics (Real Environment)

Hololib unique files: 10,563
Holotree files: 12,455

Size distribution:
  < 1KB:     5,051 (48%) ← HIGH SYSCALL OVERHEAD
  1-10KB:    4,595 (43%)
  10-100KB:    774 (7%)
  > 100KB:     143 (1%)

Average file size: 16,768 bytes
Total size: 169 MB

Per-File Syscall Overhead

Each file restore currently requires:

1x open()      - source file (hololib)
1x fstat()     - get metadata
1x open()      - destination file (create)
Nx read()/write() - copy data
1x chmod()     - set permissions
2x close()
1x rename()    - atomic move to final location
─────────────────────────────────────────
≈ 8-10 syscalls per file minimum

For 10,563 files: ~85,000-106,000 syscalls just for restore

Syscall Breakdown from Profiling

Operation        Time    % of I/O
─────────────────────────────────
openat()         0.40s   25%
rename()         0.33s   21%
unlinkat()       0.25s   16%
fstatat()        0.21s   13%
write()          0.26s   16%
chmod()          0.09s   6%
lstat()          0.11s   7%

---

Proposed Solution: Holotree Packfile Format

Inspiration: Git Packfiles

Git packfiles solve a similar problem:

• Store multiple objects in a single file
• Single I/O operation to read many objects
• Index file for fast object lookup
• Checksum trailer for integrity verification

Proposed Format: hololib.pack

┌────────────────────────────────────────────────┐
│ HEADER (32 bytes)                              │
├────────────────────────────────────────────────┤
│ Magic: "HPAK" (4 bytes)                        │
│ Version: uint32 (4 bytes)                      │
│ Flags: uint32 (4 bytes)                        │
│ Object Count: uint64 (8 bytes)                 │
│ Uncompressed Size: uint64 (8 bytes)            │
│ Reserved: (4 bytes)                            │
├────────────────────────────────────────────────┤
│ OBJECT ENTRIES (variable)                      │
├────────────────────────────────────────────────┤
│ ┌──────────────────────────────────────────┐   │
│ │ Entry Header:                            │   │
│ │   Digest: [32]byte (SHA256)              │   │
│ │   Compressed Size: uint32                │   │
│ │   Uncompressed Size: uint32              │   │
│ │   Mode: uint32                           │   │
│ │   Relocation Count: uint16               │   │
│ │   Relocation Offsets: []int64            │   │
│ ├──────────────────────────────────────────┤   │
│ │ Compressed Data (zstd)                   │   │
│ └──────────────────────────────────────────┘   │
│ ... (repeated for each object)                 │
├────────────────────────────────────────────────┤
│ FOOTER                                         │
├────────────────────────────────────────────────┤
│ Pack Checksum: SHA256 (32 bytes)               │
└────────────────────────────────────────────────┘

Syscall Reduction Estimate

Operation	Current	Packfile	Reduction
Source opens	10,563	2	99.98%
fstat calls	10,563	~0	100%
Dest creates	10,563	10,563	0%
chmod	10,563	10,563	0%
rename	10,563	0 (direct write)	100%
Total	~85,000	~32,000	~62%

---

Implementation Recommendation: Hybrid Approach

Based on our research, a hybrid approach minimizes risk while capturing most benefits:

File Type	Storage	% of Files	Rationale
Small (<10KB) + no relocation	Pack	~85%	Maximum syscall reduction
Large (>10KB)	Individual	~9%	Streaming efficiency
Has relocations	Individual	~6%	Easy seek-back

Phase A: Hybrid (Low Risk)

1. Pack small, non-relocatable files together
2. Keep large and relocatable files separate
3. Dual-format read (like gzip→zstd migration)

Phase B: Full Packfile (Once Proven)

1. All files in single pack
2. Streaming unpack with relocation post-processing
3. Eliminate .part temp files

---

Estimated Impact

Platform	Current	With Packfile	Improvement
Linux SSD	1.8s	~1.2s	33%
Windows SSD	3-5s	~1.5-2s	50-60%
macOS SSD	2-3s	~1.5s	40-50%
NFS/SMB mount	10-30s	~5-10s	50-70%

Windows and NFS see the biggest gains due to:

• Windows: Reduced AV scan events
• NFS: Reduced network round-trips

---

Security Considerations

✅ Preserved:

• Full integrity verification (pack checksum)
• No hardlinks (files still copied)
• Relocation security (same as current)
• SharedHolotree locking still works

⚠️ New considerations:

• Pack corruption affects all files (vs single file)
• Index tampering could misdirect reads
• Mitigation: Sign pack + index together, atomic writes

---

Conclusion

The packfile approach addresses the I/O bottleneck exposed by zstd compression (PR #64). Key findings:

1. Relocations are rare (2.6-5.7%) - streaming is viable
2. Windows AV benefits from fewer file opens - pack helps read side
3. Enterprise/shared storage benefits most - fewer network ops

Recommendation: Start with hybrid approach (Phase A) to validate with minimal risk.

---

Research conducted via profiling, code analysis, and benchmarking - December 2024

[vjmp]

I have some (rethoric?) questions:

• Why is additional speed important? And on which use-case? [on Lift or Drop; on first environment or additional environments; on full or partial lift or drop; on machines with few CPUs or many CPUs; on single user (developer) or multi user (enterprise computer farm) machine;cloud machine, cloud container, personal power developer machine, corporate developer lower end machine, or enterprise computer farm]
• Which is more important, speed or simplicity of algorithm? [Of course: speed is what users want, and simplicity is what code maintenance needs.]
• Does this new format support parallel/concurrent access [when many/few CPUs; anywork workers]?
• Can you keep this algorithm in your head? [when you go for walk, can you reason about features/bugs in your head]
• When new environments add just few files (different pack?), how accessing them will be done? [Does file exist already? On which pack file?]
• Does this reduce or increase disk space usage, when there are many different envrionments involved?
• Does this remove new plan for GC?
• If something [disk failure] corrupts just one byte/segment in middle pack, is that pack invalid, and does it then invalidate restoration of all environments that depend on some of files inside that pack?
• If there is custom pack file format (not just "they are gzipped files"), how to tell enterprises how to "check" pack content?
• What happens when pack files are accessed concurently? When multiple different processes are creating new environments and storing files in hololib [on their own pack files, without knowledge that other processes are doing "same thing"; this is different than what git is doing ...]?
• Is it ok, that same hash/identity is on multiple pack files? Which one to access and use when adding additional environments?

On old hololib:

• some optimizations were not done, because I valued maintenance simplicity over absolute speed (thinking on long game)
• disk and filesystem enables parallelism/concurrency (multiple workers inside one rcc process, and multiple rcc processes working over [shared] hololib but on their own restored environments)
• filesystem is both index and data storage directly (direct lookup, direct data access)
• operation concurrency is only limited if different processes are working exactly same file on exact same time [on write]; on read can be as parallel as needed
• existence check: is file (hash) already in hololib, then no additional lifting needed
• if one file is corrupted, only those environments that have exactly that file cannot be restored anymore
• more environment get "stacked" on one hololib, less space each new environment will take on disk (but only on similar depencency trees, version differences)

[vjmp]

Some additional notes:

• it is faster to restore "little bit dirty" environment vs. creating totally new environment instance (and to exploit this, some of tooling uses fixed number round-robin environment allocation)
• on computer farm machines, rcc can "clock" the computer (and slow it down dramatically), when multiple users accounts are starting their "3 AM" task at exactly same time [and rcc implementation cannot solve this problem, since rcc is not aware of "load" on a machine]
• some flow on enterprises is: limited set of people create environments, environments are security checked before delivery, environments are distributed to mass worker machines, mass worker machines are only allowed to use existing catalog environments, worker machines are either cloning fresh work dirs or reusing existing (maybe dirty) work dirs

[joshyorko]

@vjmp sorry I missed this.

I will address on seperate PR