● Stage 03 • Storage & Hashing
Content-Addressable Object Store
Construct a version control storage engine. Implement content-addressable SHA-1 hashing, zlib stream compression, directory tree serialization, and commit DAG traversal.
First steps
- Read one file. Add the header blob <byte_count>\0 before its bytes.
- Calculate SHA-1. Check that it matches git hash-object <file>.
- Compress the object with zlib. Save it and read it back before adding trees.
Project Goal
- Understand content-addressable storage models where file content determines storage location.
- Serialize and parse immutable binary objects using SHA-1 digests and stream compression.
- Represent directory file trees and commit histories as directed acyclic graphs (DAGs).
- Achieve strict binary-level interoperability with the official Git binary.
Skills Acquired
Content Addressing
SHA-1 Hashing
zlib Deflate/Inflate
Binary Tree Packing
Directed Acyclic Graphs (DAG)
CLI Tool Architecture
Technical Specification
- CLI Binary: mygit with commands: init, hash-object, cat-file, write-tree, and commit-tree.
- Object Storage Path: Files stored at .git/objects/<sha1[0:2]>/<sha1[2:40]> compressed with zlib.
- Tree Entry Format: <mode_ascii> <filename>\0<20_binary_sha1_bytes>.
Milestones
03.1
Repository Directory Setup (init)
Create the .git/ folder with objects/ and refs/heads/ directories. Write ref: refs/heads/main\n to .git/HEAD.
03.2
Blob Object Writer (hash-object)
Prepend header blob <length>\0 to file bytes. Compute 40-character SHA-1 hash. Deflate payload with zlib and write to object store.
03.3
Object Parser & Extractor (cat-file)
Locate object file by hash. Inflate with zlib, parse type and length header, and output raw payload to stdout (-p flag).
03.4
Tree Object Serializer (write-tree)
Recursively traverse the directory. Write blobs for files and binary tree objects for directories. Store 20-byte binary SHA-1 checksums per entry.
03.5
Commit Object Writer (commit-tree)
Construct a commit object linking tree hash, author info, timestamp, and message. Update reference file at .git/refs/heads/main.
Verification Commands
Build mygit and put it on your PATH. Run this in a new scratch directory, not inside this website's repository. Your commit-tree command should update refs/heads/main as specified above.
# 1. Initialize and commit with custom CLI
mygit init
echo "print('hello world')" > app.py
TREE=$(mygit write-tree)
COMMIT=$(mygit commit-tree $TREE -m "Initial commit")
# 2. Inspect with system git binary
git fsck --full --strict
git log --oneline
git cat-file -p $COMMITAcceptance Criteria
git fsck --full --strict must report zero dangling pointers, zero corrupted objects, and zero format errors against repositories created by mygit.