The old house had forty-seven rooms and three generations living in it. Nobody could say who owned the camphor chest in the upstairs east wing, or whether anyone still wanted it. Every autumn, Mr. Murray the steward cleared the house out.

He never asked “does anyone still want this?” — ask that and no one can answer. He did one thing only: he started from the front hall.

On the front hall wall hung a short row of keys: the ones the master, the mistress, the kitchen and the counting-room actually used each day. Murray’s rule was simple. Whatever you can reach from that row of keys, door after door, the household still wants. Whatever you cannot reach goes out on the cart at dawn.

That night he walked with an oil lamp and pockets full of red ribbon.

He began with the first key in the front hall. Open the door, step in, tie a ribbon on every object inside — just tie it, don’t study it yet. On the doorframe of a room he had ribboned but not yet searched, he drew a faint chalk mark: remember, you owe this room another visit. Only when he had pulled open every drawer and followed every key inside did he rub the chalk mark off. That room was finished. He need never come back.

So all night the house sorted itself into three kinds of thing: the chalk rubbed off (finished), the chalk still there (ribboned, not yet searched), and the bare (untouched). Murray watched only the middle pile. One chalk mark left anywhere and his night’s work wasn’t done; no chalk marks left, and everything still bare was, by definition, wanted by no one.

The trouble was that this family did not sleep.

The cook would carry a silver dish from the dining room into a pantry Murray had already finished. The young master would lift a key off the study wall and pocket it. Murray had promised himself never to re-enter a finished room — so if someone slipped a bare object into one, that object would ride out on the dawn cart, even though somebody was plainly still using it.

Which is why a footman stood in every doorway. All night the footmen did nothing at all except this: when anything was carried into a finished room, or any key was moved from one place to another, the footman tied a ribbon on it first and only then let it pass. Tie too many, never miss one. That was the whole secret — a finished room must never contain a bare thing.

Near dawn Murray stood in the front hall and counted. No chalk marks. He opened the courtyard gate and the carter loaded everything without a ribbon — including the two old cabinets in the attic, each holding the other’s key. For years those two had vouched for one another’s usefulness, but neither could be reached from the front hall, so out they went together.

Some ribboned things were dead too. The silver dish the cook carried into the pantry at midnight and lost interest in by morning sat safe until next autumn. Murray didn’t mind. A year’s delay costs nothing; hauling away something still in use costs everything.

— by now you’ve probably recognized him: the steward is doing tri-color mark-and-sweep garbage collection.

The concept

A tracing garbage collector never asks “is this memory still referenced?” It walks the object graph outward from the GC roots — stack, globals, registers — and keeps whatever it can reach. The tri-color abstraction partitions objects into white (unvisited), gray (marked, references not yet scanned) and black (marked, all references scanned). When the gray set empties, marking is done and every remaining white object is swept.

The hard part is doing this concurrently. Collectors like Go’s and Java’s ZGC must mark while application threads keep running, because a full stop-the-world pause would be unacceptably long. But a running program mutates pointers, and it can hide a white object inside a black one — black is finished and will never be rescanned, so a live object gets collected. The fix is a write barrier: on every pointer write, shade the new referent gray (Dijkstra style) or the overwritten value gray (Yuasa style), preserving the invariant that no black object points to a white one. The barrier is deliberately conservative: objects that die after being marked survive the cycle as floating garbage and are collected next time.

This is also why tracing beats reference counting — a cycle of mutually referencing garbage never drops its refcount to zero, but a reachability walk sees straight through it. In practice you meet this concept in GOGC tuning, GC pause histograms, and every “why is memory coming down slower than I expected” investigation.

Metaphor mapping

• the row of daily-use keys in the front hall → GC roots (stack, globals, registers)
• reachable / unreachable by walking → reachability, not “is anyone referencing it”
• the red ribbon → the mark bit: proven live
• the chalk mark on the doorframe → the gray set: marked, references not yet scanned
• rubbing the chalk off → turning black: all outgoing references traced
• bare objects → white: unmarked this cycle
• no chalk marks left anywhere → gray set empty, marking phase complete
• the dawn cart → the sweep phase reclaiming white objects
• the family moving about all night → concurrent marking with mutator threads running
• the footmen in the doorways → the write barrier
• “no bare thing in a finished room” → the tri-color invariant: no black-to-white pointer
• tie too many ribbons rather than miss one → the barrier is conservative; it only over-approximates liveness
• the two attic cabinets holding each other’s keys → a reference cycle, uncollectable by reference counting
• the silver dish that survives till next autumn → floating garbage, collected in a later cycle