TransactionDataStructureExample

From APIDesign

(Difference between revisions)
Jump to: navigation, search
Line 31: Line 31:
current = data.get();
current = data.get();
-
int r1 = combine(current.value1, current.value2);
+
// the following three operations must be performed in a "transaction" ...
-
int r2 = combine(current.value2, current.value3);
+
int v1 = combine(current.value1, current.value2);
-
int r3 = combine(current.value3, current.value1);
+
int v2 = combine(current.value2, current.value3);
 +
int v3 = combine(current.value3, current.value1);
 +
// either we want to apply them all or none at all!
-
if (data.compareAndSet(current, new Data(r1, r2, r3))) {
+
if (data.compareAndSet(current, new Data(v1, v2, v3))) {
return;
return;
}
}

Revision as of 07:10, 7 June 2025

Let's keep the internal data in a dedicated immutable object called Data. Read its current state. Compute an update. Let's use compare and swap operation to transactionally (hence the similarity with TransactionalMemory) update the state of the object or repeat everything again if there was a clash with some other thread: 


import java.util.concurrent.atomic.AtomicReference;
 
public abstract class Helper {
 
    private static final class Data {
 
        final int value1;
        final int value2;
        final int value3;
 
        Data(int value1, int value2, int value3) {
            this.value1 = value1;
            this.value2 = value2;
            this.value3 = value3;
        }
    }
 
    private AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));
 
    protected abstract int combine(int x, int y);
 
    public final void update() {
        Data current;
        while (true) {
            current = data.get();
 
            // the following three operations must be performed in a "transaction" ...
            int v1 = combine(current.value1, current.value2);
            int v2 = combine(current.value2, current.value3);
            int v3 = combine(current.value3, current.value1);
            // either we want to apply them all or none at all!
 
            if (data.compareAndSet(current, new Data(v1, v2, v3))) {
                return;
            }
        }
    }
}

Neat usage of immutability. The data that are supposed to be consistent are final in a Data class. The mutability is handled all at once with AtomicReference compareAndSet method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value. No locks involved, hence the reference to LockFreeAlgorithms. Let's call such a pattern TransactionalDataStructure.

Retrieved from "http://wiki.apidesign.org/wiki/TransactionDataStructureExample"
Personal tools
buy