If the shared routing table is immutable and needs no lock, which part of that design still needs coordination between publishers?

middlemust knowfreq 58%

answer

one mutable cell remains
the reference, not the value
publishing is read-modify-write
two publishers, one lost change
funnel or install conditionally

basics

~20 s

The mutable reference that names the current table. It has to hand over in one indivisible step, and two publishers that each derive a new table from the same old one will lose one of the changes unless publication is serialised.

solid answer

~40 s

Immutability removes coordination from the value, not from the design. One mutable cell remains: the reference that says which version is current. It has to change in a way that a reader sees either the old value or the new one whole, and it must never expose a value whose construction has not finished. The subtler requirement is on the publishers themselves. Publishing is read-current, build-from-it, install, which is a read-modify-write on that cell; if two publishers both start from version v1, the second install silently discards the first one's change. The usual answers are to funnel all publication through one writer, or to install only while the reference still holds the version the new value was derived from.

Immutability removes coordination from the value, not from the design. One mutable cell remains: the reference that says which version is current. It has to change in a way that a reader sees either the old value or the new one whole, and it must never expose a value whose construction has not finished. The subtler requirement is on the publishers themselves. Publishing is read-current, build-from-it, install, which is a read-modify-write on that cell; if two publishers both start from version `v1`, the second install silently discards the first one's change. The usual answers are to funnel all publication through one writer, or to install only while the reference still holds the version the new value was derived from.

code

pseudocode · 11 lines

pseudocode

// publisher: derive from a version, then install only if that version still holds
function publish(change)
    repeat
        seen  = currentTable                   // the version this update is derived from
        fresh = buildTableFrom(seen, change)   // built off to the side
    until installIfStillAt(seen, fresh)        // otherwise: re-read and rebuild

// without the guard, both publishers derive from `seen`
// and the later install silently discards the earlier change
function publishUnguarded(change)
    currentTable = buildTableFrom(currentTable, change)

go deeper

for a junior

Remember that something mutable always remains: the reference that says which version is current. The value is safe to share; the pointer to it is the part that changes.

for a middle

Be able to explain publishing as read-current, build-from-it, install, and to show how two publishers starting from the same version lose one change even though neither mutated anything.

for a senior

Demonstrate the fix and its price. Funnelling publication through one writer is simple and cheap on a rare path; conditional installs keep publishers parallel but waste rebuilds when they collide.

for a principal

Own the rate argument. Decide where contention is allowed to live based on measured read-to-publish ratios, and be clear that you are trading rebuild waste and staleness for an uncontended read path.

The one mutable cell

Stop and count what is still mutable once the routing table itself is never edited. Exactly one thing: the shared reference that answers the question which version is current. Every handler reads it; every publisher writes it. All of the concurrency requirements the design once spread across a whole data structure now collect on that single cell.

That cell has to provide two different things, and mixing them up is the common failure.

Requirement one: an indivisible handover

A reader that reads the reference must get either the old value or the new one, whole. Two things have to hold:

the read must never yield a torn or partly written reference;
the value it yields must be fully constructed, so a reader cannot follow the reference into a half-built table.

The primitives that provide those guarantees, and the rules about when a newly built value becomes safely visible to other participants, belong to the concurrency toolbox rather than to this paradigm. What belongs here is the shape: the design needs that guarantee in one place, on a path taken rarely, instead of around every structure on the path taken constantly.

Requirement two: publishers do a read-modify-write

Publishing is not a blind write. It is:

read the reference to get the current table;
build a new table derived from it plus the change;
install the result.

Steps 1 and 3 touch the same shared cell with a gap in between, which is the classic lost-update shape. Trace two publishers adding different routes:

Step	Publisher A	Publisher B	Shared reference
1	reads `v1`		`v1`
2		reads `v1`	`v1`
3	builds `v1` plus route X		`v1`
4		builds `v1` plus route Y	`v1`
5	installs its table		`v2`: has X, no Y
6		installs its table	`v3`: has Y, no X

After step 6 the reference names a table containing Y and not X. Route X was never rejected, never logged as failed, never rolled back: it was simply built on top of a version that stopped being current. No reader ever saw an inconsistent table, and the data is still wrong. Immutability guaranteed that every version is internally coherent; it guaranteed nothing about the succession of versions.

Two ways to close it

Funnel publication. Let one writer own the cell: a single background publisher, or a queue every change passes through. Publications become sequential by construction, so step 1 always reads what step 3 of the previous publication installed.
Install conditionally. Install only while the reference still holds the version the new table was derived from; otherwise re-read and rebuild. This keeps publishers concurrent at the cost of wasted rebuilds when they collide.

Both leave the read path untouched. That is the asymmetry that makes the whole design pay: a routing table might be read millions of times a minute and published a few times a day, so serialising publishers costs essentially nothing while serialising readers would have cost everything.

What this does not mean

It does not mean readers wait while a publisher is building. The new table is built on the side, and readers continue on the current one throughout.
It does not mean the guard belongs on the read path. Readers perform one plain read of the reference and never retry.
It does not mean a fast publisher is a correct publisher. Shrinking the gap between reading the current version and installing the next one narrows the window; it does not remove it.
It does not mean one indivisible handover covers everything a publisher changed. It covers exactly one reference.

The sentence to leave an interviewer with: immutability moved every coordination requirement off the data and onto one reference, where it became a single question about how versions succeed one another.

## The one mutable cell Stop and count what is still mutable once the routing table itself is never edited. Exactly one thing: the shared reference that answers the question *which version is current*. Every handler reads it; every publisher writes it. All of the concurrency requirements the design once spread across a whole data structure now collect on that single cell. That cell has to provide two different things, and mixing them up is the common failure. ## Requirement one: an indivisible handover A reader that reads the reference must get either the old value or the new one, whole. Two things have to hold: - the read must never yield a torn or partly written reference; - the value it yields must be fully constructed, so a reader cannot follow the reference into a half-built table. The primitives that provide those guarantees, and the rules about when a newly built value becomes safely visible to other participants, belong to the concurrency toolbox rather than to this paradigm. What belongs here is the shape: the design needs that guarantee in **one** place, on a path taken rarely, instead of around every structure on the path taken constantly. ## Requirement two: publishers do a read-modify-write Publishing is not a blind write. It is: 1. read the reference to get the current table; 2. build a new table derived from it plus the change; 3. install the result. Steps 1 and 3 touch the same shared cell with a gap in between, which is the classic lost-update shape. Trace two publishers adding different routes: | Step | Publisher A | Publisher B | Shared reference | |---|---|---|---| | 1 | reads `v1` | | `v1` | | 2 | | reads `v1` | `v1` | | 3 | builds `v1` plus route X | | `v1` | | 4 | | builds `v1` plus route Y | `v1` | | 5 | installs its table | | `v2`: has X, no Y | | 6 | | installs its table | `v3`: has Y, no X | After step 6 the reference names a table containing Y and not X. Route X was never rejected, never logged as failed, never rolled back: it was simply built on top of a version that stopped being current. No reader ever saw an inconsistent table, and the data is still wrong. Immutability guaranteed that every version is internally coherent; it guaranteed nothing about the succession of versions. ## Two ways to close it - **Funnel publication.** Let one writer own the cell: a single background publisher, or a queue every change passes through. Publications become sequential by construction, so step 1 always reads what step 3 of the previous publication installed. - **Install conditionally.** Install only while the reference still holds the version the new table was derived from; otherwise re-read and rebuild. This keeps publishers concurrent at the cost of wasted rebuilds when they collide. Both leave the read path untouched. That is the asymmetry that makes the whole design pay: a routing table might be read millions of times a minute and published a few times a day, so serialising publishers costs essentially nothing while serialising readers would have cost everything. ## What this does not mean - It does not mean readers wait while a publisher is building. The new table is built on the side, and readers continue on the current one throughout. - It does not mean the guard belongs on the read path. Readers perform one plain read of the reference and never retry. - It does not mean a fast publisher is a correct publisher. Shrinking the gap between reading the current version and installing the next one narrows the window; it does not remove it. - It does not mean one indivisible handover covers everything a publisher changed. It covers exactly one reference. The sentence to leave an interviewer with: immutability moved every coordination requirement off the data and onto one reference, where it became a single question about how versions succeed one another.

Why does serialising publication cost so little in this design?
Because of the rate asymmetry. Reads outnumber publications by many orders of magnitude, and serialising the rare path leaves the frequent path completely untouched. Handlers never acquire anything, never retry and never wait for a publisher; a publisher waiting briefly for another publisher is invisible in the system's overall behaviour.
Do handlers have to wait while a publisher is building the next table?
No. The new table is assembled on a value nothing else can reach, so building it is private work of any duration. Handlers keep reading the current reference and keep using the version it names, right up to the instant of the handover, after which later reads see the new one.
A publisher's install is rejected because the reference moved on. What should it do?
Re-read the reference and rebuild its change on top of the version now current, then try again. The work discarded is the rebuild, not the change itself. If collisions are frequent enough for that waste to matter, the design should stop being optimistic and funnel publication through one writer instead.

saying these in an interview costs you the question

Says immutability alone leaves the design with no coordination at all
Assumes two publishers can each rebuild from the current table safely
Thinks a lost update is impossible because nobody mutated anything
Puts the retry loop on the read path instead of the publish path
Believes readers are paused while the next version is being built
Thinks publishing faster removes the window between read and install

If the shared routing table is immutable and needs no lock, which part of that design still needs coordination between publishers?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The one mutable cell

Requirement one: an indivisible handover

Requirement two: publishers do a read-modify-write

Two ways to close it

What this does not mean

▾common follow-ups3 questions

▾red flags6 flags

The one mutable cell

Requirement one: an indivisible handover

Requirement two: publishers do a read-modify-write

Two ways to close it

What this does not mean

answer

go deeper