Consistency for disk write in a model object graph

Question

You're writing an app where the model (as in MVC) is an object graph. Occasionally, you want to save this object graph to disk. What are some best practices to ensure that the write is consistent? (That is, how do you prevent the object graph from mutating in the middle of a serialization/write?)

In my app, whenever a write is triggered, I make a quick in-memory copy of my object graph (blocking the model thread in the meantime), serialize that copy in a background thread, and then write it out. But this doesn't seem like a very elegant solution, especially if the model is fairly large. I don't want my UI to freeze while the copy is happening.

I can imagine locking the object graph to prevent mutation in the middle of a disk write, but this would either require loss of user input, or maintenance of a pending operation queue for the duration of the write.

I can also imagine versioning the model and incrementing the version number with each mutation, but this would additionally require persisting the version of the graph that's being written out. If we don't want to do a full copy on write, we would have to trigger a copy each time a model object is mutated during a write. Seems like it could get fairly complex.

Where can I read more about strategies used to tackle this issue? What approach is generally used to handle this problem?

• CodesInChaos: Your object graph consists of several million entities (not counting value objects)?
• Archagon: Not several million, no, but the copy is still a problem on older mobile devices.
• Archagon: (I did make a poor decision early on to not keep my model allocated in the same place in memory, so it's very badly fragmented at the moment. Still, I can imagine the question being relevant for really, really large models, e.g. project files for multimedia applications.)

Answer 1

You could make your object graph immutable and model updates as operations on an immutable data structure.

In general, if you want to build a new version of an immutable data structure you do not need to copy the whole data structure, but only the parts that are mutated. So you could write to disk the current immutable version of the object graph while another thread builds a new version of the object graph, which shares the unchanged part with the old graph.

You could find useful ideas in Purely Functional Data Structures

• Archagon: The leaves of my object graph are arrays of points that require very frequent updates. (Possibly dozens over the course of a frame, ~1/60th of a second.) Making the leaves immutable in this case would affect performance immensely.
• CodesInChaos: @Archagon Depending on your update patterns a well chosen immutable data structure might have good performance. Do you change a large fraction of the points each frame?
• Giorgio: @Archagon: Does the rest of the graph (since you speak about leaves: is it a tree or at least a DAG?) change a lot?
• Archagon: Yeah, it's a tree. As I mentioned earlier, the leaves are arrays of points. Only a couple of leaves mutate at a time in common use (though with some rare operations every leaf can be affected), but these changes must incur very low CPU overhead to attain 60fps with real-time user input on an iPad 3 (for example). I'm not too familiar with immutable data structures; perhaps there are some that can mimic the read/write performance of a C array while presenting an immutable interface to the user. However, I know from profiling that deleting and recreating the leaves with each mutation is a no-go.
• Giorgio: @Archagon: Ok, how are the arrays mutated? Do they change size? How big are they? Is it feasible to recreate the arrays or are the too big to copy each time?