"Journaling" or "transactions" design pattern? [closed]

Question

I'm looking to implement an object that is journaled, or has a persistent transaction in it. That is, the object contains data (a Map perhaps). As changes are made to the data, those changes are held separately, sandboxed if you will, so that any outside object can either reference the base state (before the changes) or can access the latest data. Then there is another operation which commits the changes into the base state.

It reminds me somewhat of the Linux journaling file system. File system changes are written to a journal, and are only later committed into permanent storage.

It is also perhaps more similar to the concept of a "transaction" in the relational database world; that is, you have some data, you begin a transaction and manipulate the data in some way. Concurrent processes will see the old data with none of your changes. Then you can either "rollback" the transaction, or "commit" your changes.

I'm specifically looking to implement this in Java, but obviously it is a general object-oriented pattern, if it even exists. I'm hoping that it can at least be created but I'm not terribly sure of the best way to implement it.

Also, assume the object holds a whole ton of data, a whole hierarchy (sub objects and so on). So one cannot just keep two copies of the whole data tree; it would be very wasteful of memory and the copy operation (on commit) would take much too long. I'm looking to implement this in the context of a game, with one commit operation per frame, so it really needs to be optimal.

Answer 1

The best way to achieve what you want is to make the object and all of its subobjects immutable. Then the two threads can operate on them without any conflicts, and you don't have to maintain two copies of everything. The only things that would require two copies are the things that actually change, and those can be very small.

Suppose object A is composed of objects B and C. Object B is composed of objects D and E. And object C is composed of objects F and G. So A, B, and C are each just two pointers, and D, E, F, and G are whatever they are.

First you create your initial instance and give it to both threads.

ThreadOne -> A1{ B1{ D1, E1 } C1{ F1, G1 } } 
ThreadTwo -> A1{ B1{ D1, E1 } C1{ F1, G1 } } 

So both threads are pointing at the same instance, no additional memory is consumed, and there are no threading issues, because the objects do not ever change.

Now ThreadOne needs to modify object F. To do this, it just creates a new F, a new C to contain it, and a new A to contain the new C. The original B, D, E, and G are unchanged, and do not need to be copied.

ThreadOne -> A2{ B1{ D1, E1 } C2{ F2, G1 } } 
ThreadTwo -> A1{ B1{ D1, E1 } C1{ F1, G1 } } 

The two threads are sharing the instances of B, D, E, and G.

Now ThreadOne needs to modify object E.

ThreadOne -> A3{ B2{ D1, E2 } C2{ F2, G1 } } 
ThreadTwo -> A1{ B1{ D1, E1 } C1{ F1, G1 } } 

Now ThreadTwo needs the latest version, so ThreadOne just gives it a pointer to its copy.

ThreadOne -> A3{ B2{ D1, E2 } C2{ F2, G1 } } 
ThreadTwo -> A3{ B2{ D1, E2 } C2{ F2, G1 } } 

Since the objects are immutable, there is no danger of any threading issues, and ThreadOne can go right on making changes, each time creating a new instance of only the parts that have changed, and their containers.

ThreadOne -> A4{ B3{ D2, E2 } C2{ F2, G1 } } 
ThreadTwo -> A3{ B2{ D1, E2 } C2{ F2, G1 } } 

ThreadOne -> A5{ B3{ D2, E2 } C3{ F3, G1 } } 
ThreadTwo -> A3{ B2{ D1, E2 } C2{ F2, G1 } } 

This is fast, memory efficient, and thread safe.