TransactionDataStructureExample

From APIDesign

(Difference between revisions)
Jump to: navigation, search
Current revision (09:40, 7 June 2025) (edit) (undo)
 
(8 intermediate revisions not shown.)
Line 1: Line 1:
-
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:
+
Let's keep the internal data in a dedicated immutable structure called '''Data'''. When performing an update:
 +
* Read the '''current''' state.
 +
* Compute an update based on the '''current''' state
 +
* Use ''compare and swap'' operation to ''transactionally'' (hence the similarity with [[TransactionalMemory]]) update the state of the object
 +
* repeat everything again if there was a clash
 +
* and the '''current''' value was modified by some other thread meanwhile
Line 22: Line 27:
}
}
-
private AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));
+
private final AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));
protected abstract int combine(int x, int y);
protected abstract int combine(int x, int y);
Line 31: Line 36:
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))) {
 +
// CAS checks the value in data is still == to current
 +
// if so it changes it to new Data and we can return
return;
return;
}
}
 +
// otherwise try again
}
}
}
}
Line 43: Line 53:
</source>
</source>
-
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 {{JDK|java/util/concurrent/atomic|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. Let's call such this pattern [[TransactionalDataStructure]].
+
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 {{JDK|java/util/concurrent/atomic|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 [[LockFreeAlgorithm]]s. Let's call such a pattern [[TransactionalDataStructure]].

Current revision

Let's keep the internal data in a dedicated immutable structure called Data. When performing an update:

  • Read the current state.
  • Compute an update based on the current state
  • Use compare and swap operation to transactionally (hence the similarity with TransactionalMemory) update the state of the object
  • repeat everything again if there was a clash
  • and the current value was modified by some other thread meanwhile 


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 final 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))) {
                // CAS checks the value in data is still == to current
                // if so it changes it to new Data and we can return
                return;
            }
            // otherwise try again
        }
    }
}

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