MVV and step visibility and pruning errors

[Nathan Williams]

Persistit r369

When utilizing the step capability of transactions there appears to be inconsistencies in how it is treated between reading, writing, removing, and pruning. Particularly when steps of a single transaction appear out of order in a single MVV.

Observe the following test code that loads keys 1, 2, and 3. Then, in a single transaction, keys 1 and 3 are removed at step 1 and written at step 2 where key 2 is updated at step 2 and removed at step 1. The expected behavior is all 3 keys are visible at the end with their new values.

public void update(Exchange ex, int k, int v) throws Exception {
    _persistit.getTransaction().setStep(2);
    ex.getKey().clear().append(k);
    ex.getValue().clear().put(v);
    ex.store();
}

public void remove(Exchange ex, int k) throws Exception {
    _persistit.getTransaction().setStep(1);
    ex.getKey().clear().append(k);
    ex.remove();
}

@Test
public void mvvStepCheck() throws Exception {
    Transaction txn = _persistit.getTransaction();
    Exchange ex = _persistit.getExchange(UnitTestProperties.VOLUME_NAME, "new_tree1", true);

    txn.begin();
    for(int i = 1; i <= 3; ++i) {
        ex.getKey().clear().append(i);
        ex.getValue().clear().put(i*10);
        ex.store();
    }
    txn.commit();
    txn.end();
    treeCheck(ex, "Initial");

    txn.begin();
    for(int i = 1; i <= 3; ++i) {
        ex.clear().append(i);
        if(i == 2) {
            update(ex, i, i*100);
            remove(ex, i);
        } else {
            remove(ex, i);
            update(ex, i, i*100);
        }
    }
    treeCheck(ex, "Post update, pre commit");
    txn.commit();
    txn.end();

    treeCheck(ex, "Updated, committed");
}

The method as written gives the following output.
Initial
  {1} => 10
  {2} => 20
  {3} => 30
Post update, pre commit
  {1} => 100
  {2} => 200
  {3} => 300

Looks good so far. However, 2 inconsistent cases have been observed by inserting some code at the end.

Case 1: Read after prune yields missing key/value
Code:
    while(_persistit.getCleanupManager().getPerformedCount() < _persistit.getCleanupManager().getAcceptedCount()) {
        Thread.sleep(100);
    }
    treeCheck(ex, "Updated, committed, pruned");
Output:
Updated, committed, pruned
  {1} => 100
  {3} => 300

Case 2: Read after TransactionIndex cleanup yields non-removable but visible key
Code:
    _persistit.getTransactionIndex().cleanup();
    txn.begin();
    treeCheck(ex, "Updated, committed, TI cleaned");
    ex.clear().append(2);
    System.out.println("Removed: " + ex.remove());
    txn.commit();
    txn.end();
    treeCheck(ex, "Updated, committed, TI cleaned, removed");
Output:
Updated, committed, TI cleaned
  {1} => 100
  {2} => 200
  {3} => 300
Removed: false
Updated, committed, TI cleaned, removed
  {1} => 100
  {2} => 200
  {3} => 300

[Nathan Williams (nwilliams)]

Marking as critical since this can result in data loss.

[Peter Beaman (pbeaman)]

An invariant in MVV.storeVersion is that each version added to an MVV must have a larger ts than any version already present in the MVV. This follows from ww-dependency validation; if there's a version tsv on the MVV and my ts is before that tsv, by definition I'm current with it and can't write.

But, the step handling code breaks that. A transaction can't conflict with itself, so no code prevents insertion of versions with step numbers out of sequence. MVV.storeVersion does not rearrange the MVV in step order, and the pruning code simply keeps the last value found for each concurrent transaction. Therefore in the test case for key={2}, the AntiValue for the remove is stored after the value 200 in the MVV. The MVV looks like this:

[277<277>:20,282#02<UNCOMMITTED>:200,282#01<UNCOMMITTED>:AntiValue{}]

Pruning will then remove the value at 282#2 and keep 282#1, the AntiValue from the remove.