skip to content

In an editor that keeps every past document version reachable, what is actually retained in memory as edits accumulate?

level: seniorimportance: should knowfreq 38%

answer

  1. reachable from any live root
  2. overlap, not versions times size
  3. superseded is not the same as freed
  4. one stale root pins replaced nodes
  5. history depth is a policy choice

basics

~20 s

Everything any live version root can still reach. Because versions overlap heavily, the total is the common base plus the nodes each update replaced - not versions times document size - and a node is freed only when no live root reaches it.

solid answer

~40 s

Each retained version is a root, and a node lives as long as some live root can reach it. The versions overlap, so a thousand keystroke-sized edits do not cost a thousand documents: they cost the base structure plus roughly the nodes each update rewrote along its own path. That is the good news and the trap at once - retaining is cheap enough that nobody notices an unbounded history growing. Two failure shapes follow. An uncapped undo or version list keeps every root alive, so memory tracks edit count. And one long-lived stale reference - a cache entry, a closure, a pending request holding yesterday's root - keeps alive every node only that root can reach, including data every newer version has replaced.

code

pseudocode · 11 lines
pseudocode
let history = [current]

for each keystroke in session:
    current = applyEdit(current, keystroke)
    history.append(current)        // every root here pins what only it can reach

// trimming drops roots, and dropping roots is what makes nodes unreachable
history = lastN(history, 50)

// but this one reference is outside the policy and pins its own root anyway
cache.put("yesterday", versionFromYesterday)

go deeper

for a junior

Recall that holding an old version keeps its data in memory, and that versions share most of their content, so keeping several is far cheaper than keeping several copies.

for a middle

Explain the reachability rule and do the arithmetic: base plus roughly one short path per edit, not edits times document size. Say why superseded is not the same as freed.

for a senior

Diagnose the two real shapes - an unbounded history and a stale root outside the history policy - and know the tell: retained size that does not fall when the history is trimmed. Bound it with a cap, coarser snapshots and a re-root when a history is finished.

for a principal

Decide the retention policy as a product constraint: how far back users can go, what that costs at the worst realistic session length, and what it means for a deletion request when older versions still reach the data.

## What a root keeps alive A version in a persistent structure is a root. Everything reachable from a live root must stay in memory, because that version is still a valid, readable document. Everything no live root can reach is garbage. That single rule explains every memory behaviour this material has. The consequence people miss is the direction of it: **a node is freed when nothing can reach it, not when it is superseded.** A newer version replacing a node does not free the old one. It only stops the *new* root from reaching it. If any older root still can, it stays. ## Why the bill is not versions times size The naive model - a thousand versions of a large document means a thousand documents - is wrong, and the arithmetic is worth doing out loud. Each small edit rewrites the nodes on one root-to-slot path and leaves everything else reachable from both the old and the new root. With a wide-branching structure that path is a handful of nodes. So for k successive edits over a structure of n entries: - the **base** is paid once: the structure as it stood before the history began; - each edit adds roughly a path's worth of new nodes - a handful, not n; - total retention is therefore about *base + k x path*, not *k x n*. | model | cost of 1,000 edits | |---|---| | copying the whole document per edit | 1,000 full documents | | persistent versions, all retained | one document plus about 1,000 short paths | | persistent versions, history capped at 50 | one document plus about 50 short paths, once the older roots are dropped | ## The two shapes that actually leak **1. An unbounded history.** Nothing in the structure bounds it; retention is a policy the application owns. A session that appends a root per keystroke and never drops one grows for as long as the session lasts. It grows slowly, which is why it reaches production - the profile looks fine for an hour and wrong overnight. **2. A single stale root held somewhere unexpected.** This is the nastier one, because it is invisible in the history policy. A cache entry, a memoised result, a closure captured by a scheduled task, an in-flight request that took a version at the start and has not finished - any of these pins a root. That root keeps alive every node **only it can reach**, which is precisely the data every newer version replaced. Trimming the undo history does nothing about it. The symptom is a structure whose retained size does not fall when the history is trimmed, and the diagnosis is to find what still references the old root, not to look for a bug in the structure. ## Deletion is not erasure This follows from the same rule and deserves naming separately. Removing an entry produces a new version without it. The entry is still reachable from every earlier retained version. So in a system holding history, "delete" means "the newest version no longer has it", not "the value is gone from memory". Where the value is something that must actually stop existing on request, versioned history is a design constraint to plan for, not an implementation detail - the newest version is not where it lives. ## Bounding it deliberately - **Cap the history.** Keep the last N roots, or roots at coarser intervals the further back you go. Dropping a root is what makes its unshared nodes collectable. - **Snapshot at meaningful boundaries** rather than per keystroke, so the number of retained roots tracks user-visible actions instead of input events. - **Audit long-lived holders.** Any component that stores a version rather than re-reading the current one is a potential pin; store an identifier and look the version up if you do not truly need to read the old one. - **Re-root when a history is genuinely finished.** Build a fresh structure from the newest version and drop every old root, so the shared-but-stale interior can be collected. - **Measure retention, not allocation.** The allocation rate of a persistent structure looks alarming and is usually fine; what predicts the failure is how much is still reachable, and from which roots. ## How to say it in an interview The answer that lands is the rule plus the two shapes: everything a live root can reach is retained; overlap makes that far less than versions times size; and the failures are an unbounded history and a stale reference that outlives the history policy. Getting the direction right matters - superseded is not freed, unreachable is freed.

  • The history is trimmed to the last 50 versions and retained memory barely falls. What do you look for?
    A holder outside the history policy. Some component still references an older root - a cache, a memoised value, a closure captured by a scheduled task, an unfinished request - and that root keeps alive every node only it can reach. The fix is at the holder, not in the structure; a retention graph showing which root reaches the surviving nodes points straight at it.
  • Does removing a value from the newest version stop it being reachable?
    No. The removal produces a new version without it, while every retained earlier version still reaches it. In a system that keeps history, deletion means the newest version lacks the entry - not that the value has left memory. If a value genuinely has to stop existing on request, the version history has to be part of that design.
  • Allocation rate looks alarming in the profile. Is that the number to act on?
    Usually not on its own. A persistent structure allocates small nodes constantly by design, and most of them die immediately because no root keeps them. The number that predicts failure is live retained size and which roots reach it. Act on allocation only when the update rate itself is the hot path.

saying these in an interview costs you the question

  • Says a thousand versions cost a thousand full documents
  • Believes a superseded node is freed immediately
  • Thinks trimming the history frees nodes a stale reference still reaches
  • Assumes a removed entry is gone from memory
  • Treats history depth as a property of the structure rather than a policy
  • Reads a high allocation rate as proof of a leak