Design patterns and optimization · Intermediate

Sharing data through copy-on-write

Keep readers on immutable snapshots while separating copying, publication and mutable element ownership.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Keep the reader’s structure unchanged
  2. Trace a registration during traversal
  3. Separate shallow copying from safe publication
  4. Budget copying and retained versions
  5. Ask Logeia about this articleCheck your understanding

Keep the reader’s structure unchanged

Copy-on-write data structures avoid modifying the structure currently observed by readers. A writer creates a new version and publishes it while existing readers retain the old one. A listener registry with frequent traversal and rare registration changes is a representative use case. Java CopyOnWriteArrayList demonstrates array-level copying, which differs from operating-system page-level copy-on-write. The similarity is version separation; the copying unit, publication mechanism and ownership of objects stored inside the structure need separate analysis.

Trace a registration during traversal

Assume traversal starts from the listener list [A, B], then another thread registers C. Publication creates [A, B, C], while the original reader can finish traversing [A, B]. In Java’s snapshot-style iterator, changes after iterator creation are not reflected in that iterator. A later traversal can see the newer list. This avoids structural interference, but it is not a promise that every newly registered listener receives a notification that is already being dispatched.

Separate shallow copying from safe publication

Copying an array of references does not freeze each referenced object. If listener A contains mutable fields, concurrent changes to those fields still require a suitable synchronization or immutability policy. Structural snapshots and deep snapshots are different guarantees. A custom implementation must also publish the new root safely under the language memory model and retain old versions while readers use them. Replacing a shared pointer is not a universal substitute for publication ordering and lifetime management.

Budget copying and retained versions

An array-copy implementation copies O(n) references for a mutation of an n-element list. Adding one thousand items individually to a large list can therefore allocate and copy far more than one bulk update. Persistent tree structures can instead share unchanged subtrees, with different trade-offs. Readers retaining old snapshots also postpone reclamation. Evaluate write frequency, allocation volume and retained memory alongside traversal speed; a design that is excellent for read-mostly metadata may be unsuitable for a write-heavy queue.

Removal has an equally important semantic boundary. A listener removed from the new list may still exist in an older iterator already in use. If deregistration must guarantee that no further callback can occur after it returns, replacing the structure alone may be insufficient; waiting for active traversals or another coordination scheme may be required. Define callback lifetime separately from structural membership.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 18

Understand the systems behind the web · STEP 15

Choose a learning path