Snapshot-based undo can consume unbounded memory. What concrete strategies bound the cost of retaining mementos while keeping the history useful?
answer
- bytes ≈ snapshot size × depth
- ring buffer / byte budget / purge on save
- scoped snapshot, delta + keyframe
- structural sharing of immutable subtrees
- skip caches & handles; coalesce keystrokes
basics
~20 sMemory grows as snapshot size times history depth. Bound it by capping the number of snapshots (a ring buffer), snapshotting only at meaningful boundaries instead of every change, storing deltas instead of full copies, sharing unchanged parts between snapshots, and spilling older snapshots to disk.
solid answer
~50 sCost is roughly sizeof(state) x historyDepth, so attack both factors. Bound depth with a fixed-size ring buffer or a memory-budget eviction policy (evict oldest until under N megabytes), which gives predictable worst-case usage; also drop the whole history at natural boundaries such as save, document close, or logout. Reduce per-snapshot size by capturing only the affected sub-state (scoped mementos), storing deltas against the previous snapshot with occasional full keyframes, using persistent/immutable structures so unchanged subtrees are shared by reference rather than copied, and excluding derived or rebuildable data (caches, indexes, open handles) that restore can recompute. Coalesce rapid changes so a burst of keystrokes produces one snapshot rather than fifty. For large media, keep recent snapshots in memory and spill older ones to disk or a temp file, accepting slower deep undo. Finally, measure: snapshot size, history bytes, and capture latency should be observable, and the policy should degrade gracefully under memory pressure rather than crashing.
go deeper
Say memory grows with snapshot size times how many you keep, and give one bound (limit undo to N steps).
Add coalescing, excluding derived state, and purging history at save/close; note capture cost on the UI path.
Bring in scoped snapshots, delta plus keyframe schemes, structural sharing with immutable structures, byte-budget eviction, and copy-on-write capture.
Frame retention as a product and reliability policy: measured bytes-per-snapshot and edit rates, graceful degradation under memory pressure, spill-to-disk with encryption and cleanup for sensitive state, and the explicit statement that no policy makes external side effects undoable.
## Where the cost comes from Total retained bytes ≈ **sizeof(snapshot) × number of retained snapshots**, plus allocation and copying time at each capture (capture is on the interactive path, so latency matters as much as bytes). Two independent levers: make each snapshot smaller, keep fewer of them. ## Lever 1 — bound the depth - **Fixed-size ring buffer / bounded stack.** Keep the last N snapshots; pushing evicts the oldest. Simple, predictable, and the user-visible contract ("undo up to 100 steps") is easy to explain. - **Memory-budget eviction.** Track actual bytes; evict oldest until under budget. Better when snapshot sizes vary wildly (a 3-character document vs a 200-page one). Requires a size estimate per snapshot. - **Boundary purges.** Clear history on save, document close, session end, or after a destructive milestone. Also a correctness measure: stale snapshots referencing deleted external resources are a bug source. - **Time-based decay.** Keep every step for the last minute, one per minute after that (log-spaced retention). Matches how people actually undo — fine-grained recently, coarse further back. Watch out for **weak/soft-reference caches** ("the garbage collector will drop them if memory is tight"): they make undo depth unpredictable and non-deterministic, which users experience as a bug. ## Lever 2 — shrink each snapshot - **Scoped mementos.** Capture only the part touched: the edited paragraph, the modified tile, the one changed field — not the whole document. Requires knowing the affected region at capture time, which is exactly what a command-style design gives you. - **Deltas with keyframes.** Store a diff against the previous snapshot, plus a full snapshot every N steps so restoring does not require replaying the whole chain. This is the same keyframe/delta scheme as video codecs and incremental backups. Trade-off: restore gets slower and more complex, and one corrupt delta invalidates a run. - **Structural sharing (persistent data structures).** If the state is an immutable tree, an update returns a new root sharing every unchanged subtree. A "full snapshot" then costs only the changed path — typically O(log n) nodes. This makes conceptually-full snapshots practical and is why immutable state models pair so well with undo. Cost moves to allocation churn and GC pressure. - **Exclude derived state.** Caches, search indexes, layout results, memoized values, open file handles, sockets, and GPU resources should generally *not* be captured; restore recomputes or reopens them. This shrinks snapshots and avoids restoring stale or invalid handles. Document which fields are transient. - **Compression / spill to disk.** Compress cold snapshots, or write them to a temp file and keep only recent ones resident. Deep undo becomes slower but stays possible. Consider encryption and cleanup if the state is sensitive. - **Coalescing / debouncing.** Group rapid changes into one snapshot: typing a word, dragging a slider, a burst of programmatic updates. Usually keyed on time window plus operation type, and it also makes undo *feel* right (one undo removes a word, not a letter). ## Timing, not just size Capture happens synchronously before a user action, so a deep copy of a large state stalls the UI. Options: capture lazily (copy-on-write, so the copy cost is paid only if the state is later mutated), capture off the critical path when the state is immutable, or snapshot at coarser boundaries. ## Correctness hazards that come with these optimizations - **Aliasing.** A "cheap" snapshot that shares mutable structure is not a snapshot. Structural sharing is only safe when the shared parts are genuinely immutable. - **Partial snapshots and consistency.** Scoped mementos must cover everything an operation touched, including indexes and back-references, or restore leaves the object internally inconsistent. - **Redo interaction.** Evicting snapshots to save memory must not silently break the redo stack; decide and document what happens. - **External state.** Snapshots do not roll back files, network calls, or committed rows. Bounding memory does not change that. ## What to say in an interview Name the formula, then two levers with one concrete technique each, then admit the measurement point: you cannot pick a retention policy without knowing typical snapshot size and edit frequency for *your* data. A crisp answer is "ring buffer of 100 plus coalescing, scoped snapshots for large media, and I'd measure bytes-per-snapshot before choosing deltas."
- Why is it usually wrong to hold undo snapshots behind weak or soft references?Undo depth then depends on garbage-collector timing and memory pressure, so the same action sometimes can and sometimes cannot be undone. Users read that as a bug. Use an explicit bounded policy so the behaviour is deterministic and explainable.
- Which parts of an object's state should normally be excluded from a snapshot?Derived and rebuildable data: caches, indexes, memoized computations, layout results, and live resources such as file handles, sockets, or GPU buffers. Restore recomputes or reacquires them, which shrinks the snapshot and prevents restoring stale or invalid handles.
- How does coalescing improve both memory and user experience?Grouping a burst of changes (a typed word, a slider drag) into one snapshot cuts snapshot count dramatically, and it makes each undo step correspond to a meaningful user action rather than a single character or pixel of movement.
Video encoding: storing every frame in full is a lossless mess, so codecs keep periodic keyframes plus small inter-frame deltas. Snapshot histories use the same keyframe-and-delta economics.
saying these in an interview costs you the question
- Keeping an unbounded history and assuming memory pressure will sort itself out.
- Using weak/soft references so undo depth becomes non-deterministic.
- Deep-copying the whole document on every keystroke, stalling the UI thread.
- Calling a snapshot 'cheap' when it shares mutable structure with live state.
- Adding delta storage without keyframes, so restoring an old state replays the entire chain.
- Capturing live handles (files, sockets, GPU buffers) into the snapshot and restoring them later.