Git's entire object model rests on one idea: every object is keyed by the hash of its own content, not by an arbitrary assigned id. That has two consequences worth internalizing:
- Deduplication is automatic. Two files with identical bytes hash to the same key, so they're stored once, no matter how many commits or paths point at them.
- Corruption is detectable. If the bytes filed under a key ever stop matching that key, recomputing the hash of what's actually stored will no longer equal the key -- the mismatch itself is the corruption signal.
Git doesn't hash raw content directly -- it hashes a small header
prepended to it: b"{type} {length}\0" followed by the content. This is
why a blob and a tree built from identical bytes still hash differently:
the type is part of what gets hashed.
Implement:
ObjectStore.store(content, obj_type="blob")-- computeheader = b"{obj_type} {len(content)}\0", hashheader + contentwith SHA-256, and storeheader + contentunder that hash -- but only if that hash isn't already present (this is the deduplication). Return the hash (a hex string).ObjectStore.retrieve(obj_hash)-- look up the raw bytes stored underobj_hash(raiseKeyErrorif there's no such key). Recompute SHA-256 of those raw bytes and compare toobj_hash-- if they don't match, raiseCorruptObjectError. Otherwise split the raw bytes at the firstb"\0"into(header, content), parseobj_typeout of the header, and return(obj_type, content).
Example
store = ObjectStore()
h1 = store.store(b"hello world")
h2 = store.store(b"hello world")
h1 == h2 # True -- identical content dedups
store.retrieve(h1) # -> ("blob", b"hello world")
store._objects[h1] = b"blob 11\0TAMPERED!!" # simulate corruption
store.retrieve(h1) # -> raises CorruptObjectError
Constraints
store()must not re-store bytes for a hash that's already present -- dedup means the SECONDstore()call with identical(obj_type, content)is a no-op besides returning the same hash.retrieve()on an unknown hash raisesKeyError, notCorruptObjectError-- those are different failure modes (never written vs. written-then-corrupted).
Real-world grounding
- Git's object storage (loose objects: hashing, writing, and reading
back, including the exact
"{type} {size}\0"header format):object-file.c
Real Git additionally zlib-compresses loose objects on disk and, since 2.29+, supports SHA-256 as an alternative to SHA-1 as the hash function (this exercise uses SHA-256 throughout) -- but "hash the header plus the content, use that as the key, and let a mismatch on read mean corruption" is the exact mechanism underneath both.