Explain Go's concurrent tri-color mark-and-sweep garbage collector.

Go's GC is concurrent, non-moving, non-generational, tri-color mark-sweep. Objects are in one of three sets:

• White: not yet seen. Any object still white at the end of marking is garbage.
• Grey: reachable, but its children have not been scanned yet. These sit on the work queue.
• Black: reachable, and all of its children have been scanned.

Marking starts by greying the roots: stacks, globals and runtime structures. Workers repeatedly take a grey object, grey its white children, and blacken it, until no grey objects remain. White objects are then reclaimed by the sweep, which runs lazily as spans are reused and also in the background.

Because the program (the "mutator") keeps running during marking, it could hide a white object by storing its only pointer into a black object and deleting it from a grey one. The collector would then free live memory. The tri-color invariant prevents this: a black object may never point to a white object, or, in the weak form, only if that white object is still reachable from some grey object. The write barrier maintains the invariant.

Two more details: new objects are allocated black during marking, and goroutines that allocate quickly are made to do mark assists, which is proportional marking work, so they cannot outrun the collector.

What the interviewer is looking for: the invariant, why concurrent marking needs a barrier, and that pauses are short while CPU and throughput carry the cost.