A chat server replaces the whole room roster on each join instead of mutating it — what does that cost?

Replacing a value wholesale is the move that makes the immutable style work under concurrency: nothing that a reader holds is ever written, so no reader needs permission from anyone. The interesting engineering is in what that move costs, because the costs are real and they scale differently from the ones it removes. ## The copy, and what `n` is Let `n` be the number of participants on the roster and `c` the number of changes per second (joins plus leaves). Building the successor of a flat list copies all `n` entries, so the style's steady-state work is proportional to `n x c`. That product, not either factor alone, is the number to reason about: - A room with 8 participants that churns constantly: `n` is tiny, copying is invisible. - A room with 50,000 participants that changes twice an hour: `c` is tiny, copying is invisible. - A room with 50,000 participants where people join and leave every second: the product is large, and copying now dominates everything else the server does for that room. The important refinement is that `n` entries is the cost of a **flat** structure. A **persistent structure with structural sharing** — a tree whose unchanged subtrees are reused by the successor — copies only the nodes along one path, roughly proportional to the depth rather than to `n`, and shares the rest. That changes the arithmetic from `n x c` to something much flatter, at the price of a slower walk and more indirection on every read. Choosing the representation is therefore part of choosing the style, not a detail below it. ## Allocation is a different cost from waiting The guarded style's cost is *time spent waiting*, which appears as latency on the threads that wanted the state. The value style's cost is *objects created and discarded*, which appears somewhere else entirely: in memory traffic, in collection pauses, in cache pressure as the working set stops fitting. Two teams can both be right that their style is faster and be measuring different things. The honest comparison names both: 1. Measure the guarded arrangement by how long accesses wait and how that grows with the read rate. 2. Measure the value arrangement by bytes allocated per change and how that grows with roster size. 3. Compare them at the *busy* rates, not the average ones — both styles are fine when the room is quiet. ## Wholesale replacement does not remove the writer's problem This is the part candidates most often skip. Consider two joins arriving together. Each reads the current roster, each builds a successor containing its own new participant, each installs it. One of the two participants is simply gone — not corrupted, not half-written, gone, because the second publication overwrote a value built from a stale base. An immutable value guarantees that nobody observes a half-built roster; it guarantees nothing about which of two successors survives. So the style still needs exactly one agreed way to move `current` forward — an owner, or a publication that refuses when the base has moved. ## Staleness, and why it is usually fine here A delivery loop that captured the roster before a join completes will finish its fan-out against the captured version. A participant who joined during the fan-out misses that message; one who left may still receive it. The window is as long as one fan-out. For a chat room this is ordinarily invisible and acceptable. For a state where the answer must be current at the moment it is used — a limit check, an authorisation decision — it is not, and that is the signal to keep the state guarded instead of published. ## Where the style stops paying | Condition | Effect on the value style | |---|---| | Roster small, change rate low | Copying is free in practice; the style wins outright | | Reads heavily outnumber changes | Best case: cost lands on the rare event | | Roster large and churning | Copy cost times change rate becomes the bottleneck | | Readers must see the newest change | Captured versions are the wrong tool; guard instead | | Structure shares unchanged parts | Copy cost falls to the changed path, and the style stretches much further | The summary an interviewer is listening for: wholesale replacement buys coordination-free reading and pays for it in copying, allocation and a bounded staleness window, while leaving the writers to agree among themselves. It is a trade, sized by two numbers you can actually measure, not a free upgrade.