1. Storage

Content-Addressable Object Store

midversion-control-internalsstorage

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") -- compute header = b"{obj_type} {len(content)}\0", hash header + content with SHA-256, and store header + content under 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 under obj_hash (raise KeyError if there's no such key). Recompute SHA-256 of those raw bytes and compare to obj_hash -- if they don't match, raise CorruptObjectError. Otherwise split the raw bytes at the first b"\0" into (header, content), parse obj_type out 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 SECOND store() call with identical (obj_type, content) is a no-op besides returning the same hash.
  • retrieve() on an unknown hash raises KeyError, not CorruptObjectError -- 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.

hints
object_store.pysign in to run
Loading...
test result

This is a preview. Sign in to run this exercise against the real tests.

Content-Addressable Object Store — nossletter.tech