Tags, References, and Garbage

In one sentence: Tags are mutable pointers into an immutable blob DAG, so deleting things safely is mark-and-sweep — walk from every live root (tags and containers), keep what's reachable, sweep the rest.

Pointers move; bytes don't

Retagging latest from build 41 to build 42 rewrites one row in the reference store — the old manifest and its layers still exist, now possibly unreferenced ("dangling"). Multiply by hundreds of builds and the blob store fills with orphans. But per Lesson 8's DAG, you can never delete a blob just because one manifest stopped needing it — another image may share it. The only safe answer is reachability.

Mark and sweep

Garbage collection walks the DAG from every root: all tags in the reference store, plus every existing container (a container's image must survive even if untagged — Lesson 13's dashed edge). Everything reached is marked live; every unmarked blob is swept. The delicate part is concurrency: a push racing a GC could reference a blob mid-sweep, so real registries GC with writes paused or use grace periods for recent blobs.

flowchart TB
  T1["root: tag api:2.2"] --> M2["manifest v2.2 ✓"]
  C1["root: container c-42
(runs untagged build 41)"] --> M1["manifest v2.1 ✓"]
  M2 --> BASE["base layer ✓
(shared — 2 parents)"]
  M1 --> BASE
  M2 --> APP2["app layer v2.2 ✓"]
  M1 --> APP1["app layer v2.1 ✓"]
  M0["manifest v2.0
(no root → dangling)"] --> BASE
  M0 --> APP0["app layer v2.0 ✗ sweep"]
  style M0 fill:#fff8ec,stroke:#f2ddb0
  style APP0 fill:#fff8ec,stroke:#f2ddb0
    

sequenceDiagram
  participant GC as GC
  participant RS as Reference store
  participant CS as Container store
  participant BS as Blob store
  GC->>RS: all tags → root manifests
  GC->>CS: all containers → root images
  GC->>BS: walk DAG from roots, mark reachable
  BS-->>GC: marked: v2.1, v2.2 trees (base counted once)
  GC->>BS: sweep unmarked (v2.0 manifest + its unique layer)
  note over GC,BS: shared base survives —
it was reached from live roots