Back
+30 XP
Concept

Gauntlet 03: Barebones Git Object Store

Git is not magic; it is a content-addressable directed acyclic graph (DAG) of immutable objects. Every object begins with a type header and byte size, is hashed via SHA-1, and compressed with zlib. Blobs store file data, while commits bind tree pointers to commit messages.

python
import hashlib, zlib

# Git object header: f"{type} {size}\x00{content}"
raw = f"blob {len(data)}\x00".encode() + data
sha = hashlib.sha1(raw).hexdigest()
compressed = zlib.compress(raw)

# Gauntlet 03: Barebones Git Object Store Linus Torvalds engineered Git in two weeks not by building a complex VCS, but by inventing a simple content-addressable object store. Everything in `.git/objects/` is one of four core object types: **blob**, **tree**, **commit**, or **tag**. 📦🌿 Every Git object follows a strict binary layout: 1. Header: `f"{object_type} {size_in_bytes}\x00"` 2. Followed immediately by raw object data. 3. The object's 40-character hex ID is the **SHA-1 hash** of `header + data`. 4. The entire byte stream is compressed using `zlib.compress()`. - **Blob**: Raw uncompressed file content. - **Commit**: Plain text referencing a `tree <sha>`, an optional `parent <sha>`, author info, and the commit message. ```python import hashlib import zlib header = f"blob {len(payload)}\x00".encode("ascii") sha = hashlib.sha1(header + payload).hexdigest() ``` ## Pop Quiz How does Git mathematically guarantee that commit history cannot be altered without changing the root commit hash? - [ ] Each commit embeds the cryptographic SHA-1 hash of its parent commit and root tree; modifying any ancestor changes every descendant hash. - [ ] The Git engine signs every commit with an RSA-4096 private key stored in the operating system BIOS. - [ ] Git stores commits in a centralized blockchain managed by the Linux Foundation. - [ ] Because zlib compression is mathematically irreversible without root access. ## Real-World Challenge Implement `MiniGitStore`: - `write_object(obj_type: str, data: bytes) -> str`: Formats Git header, hashes via SHA-1, compresses with `zlib`, stores in internal map, and returns 40-character hex SHA-1. - `read_object(sha: str) -> tuple[str, bytes]`: Decompresses, splits at `\x00`, and returns `(obj_type, data)`. - `create_blob(content: bytes) -> str` - `create_commit(tree_sha: str, message: str, parent_sha: str = None) -> str` <details> <summary>Solution</summary> ```python import hashlib import zlib class MiniGitStore: def __init__(self): self._objects = {} # sha1_hex -> zlib_compressed_bytes def write_object(self, obj_type: str, data: bytes) -> str: header = f"{obj_type} {len(data)}\x00".encode("ascii") full_content = header + data sha = hashlib.sha1(full_content).hexdigest() self._objects[sha] = zlib.compress(full_content) return sha def read_object(self, sha: str) -> tuple[str, bytes]: if sha not in self._objects: raise KeyError(f"Object {sha} does not exist in store") decompressed = zlib.decompress(self._objects[sha]) header, payload = decompressed.split(b"\x00", 1) type_str, size_str = header.decode("ascii").split(" ") assert len(payload) == int(size_str), "Object size corrupt" return type_str, payload def create_blob(self, content: bytes) -> str: return self.write_object("blob", content) def create_commit(self, tree_sha: str, message: str, parent_sha: str = None) -> str: body = f"tree {tree_sha}\n" if parent_sha: body += f"parent {parent_sha}\n" body += f"\n{message}\n" return self.write_object("commit", body.encode("utf-8")) # Verification git = MiniGitStore() # 1. Create a blob blob_content = b"print('Hello from Git internals!')\n" blob_sha = git.create_blob(blob_content) assert len(blob_sha) == 40 # Official git hash verification: # echo -en "blob 36\x00print('Hello from Git internals!')\n" | sha1sum # Matches Git's exact byte calculation obj_type, data = git.read_object(blob_sha) assert obj_type == "blob" assert data == blob_content # 2. Create commit DAG commit1 = git.create_commit(blob_sha, "Initial commit") commit2 = git.create_commit(blob_sha, "Second commit", parent_sha=commit1) c2_type, c2_body = git.read_object(commit2) assert c2_type == "commit" assert f"parent {commit1}".encode("utf-8") in c2_body assert b"Second commit" in c2_body ``` </details>