Merge lp:~pbeaman/akiban-persistit/fix-1056489-mvv-step-visibility into lp:akiban-persistit

[Peter Beaman]

Fix bug 1056489 MVV and step visibility and pruning errors. This bug arises to incorrect handling of MVV versions when a single transaction performs two or more updates at different step numbers, and when those updates are not ordered by increasing step value. For example, inserting a value with step=2 and then removing the value with step=1 will result in an MVV that sometimes yields the correct result and sometimes appears to have no value.

The assumption in MVV#storeVersion that versions could only arrive in increasing version-handle order was wrong in this case. The primary change is to allow step #01 to be inserted into the MVV at the correct location with respect to step #02 rather than at the end. A new unit test based on Nathan's original investigation code has also been added.

[Nathan Williams (nwilliams)]

Keeping the mvv array in strict order is probably simplest. Looks good.

review: Approve

[Akiban Build User (build-akiban)]

There were 2 failures during build/test:

* job persistit-build failed at build number 433: http://172.16.20.104:8080/job/persistit-build/433/

* view must-pass failed: persistit-build is red

review: Needs Fixing

[Nathan Williams (nwilliams)]

Jenkins setup of AMI failed, apache mirror down?

[Akiban Build User (build-akiban)]

There were 2 failures during build/test:

* job persistit-build failed at build number 438: http://172.16.20.104:8080/job/persistit-build/438/

* view must-pass failed: persistit-build is yellow

review: Needs Fixing

[Nathan Williams (nwilliams)]

Real failures in MVVTest that time.

[lp:~pbeaman/akiban-persistit/fix-1056489-mvv-step-visibility]

371. By Peter Beaman on 2012-09-27

Modify MVVTest contants to match reordering now done by MVV.storeVersion

[Peter Beaman (pbeaman)]

MVVTest contains constants that no longer match MVV.storeVersion. Fixed the constants.

=== modified file 'src/main/java/com/persistit/MVV.java'
--- src/main/java/com/persistit/MVV.java	2012-08-24 13:57:19 +0000
+++ src/main/java/com/persistit/MVV.java	2012-09-27 17:48:28 +0000
@@ -252,6 +252,9 @@
             final int sourceLength) {
         int existedMask = 0;
         int to = targetOffset;
+        int remainder = 0;
+        int end = targetOffset + targetLength;
+
         if (targetLimit > target.length) {
             throw new IllegalArgumentException("Target limit exceed target array length: " + targetLimit + " > "
                     + target.length);
@@ -314,8 +317,7 @@
              */
             to++;
             int next = to;
-            int end = targetOffset + targetLength;
-
+            
             while (next < end) {
                 final long curVersion = getVersion(target, to);
                 final int vlength = getLength(target, to);
@@ -340,20 +342,30 @@
                         end -= (next - to);
                         next = to;
                     }
+                } else if (curVersion > versionHandle) {
+                    if  (vh2ts(versionHandle) != vh2ts(curVersion)) {
+                        throw new IllegalStateException("Versions out of order");
+                    }
+                    remainder = end - to;
+                    break;
                 }
                 to = next;
             }
         }
-        assertCapacity(targetLimit, to + LENGTH_PER_VERSION + sourceLength);
+        assertCapacity(targetLimit, end + LENGTH_PER_VERSION + sourceLength);
+        // Move same-transaction steps that are higher
+        if (remainder > 0) {
+            System.arraycopy(target, to, target, to + sourceLength + LENGTH_PER_VERSION, remainder);
+        }
         // Append new value
         putVersion(target, to, versionHandle);
         putLength(target, to, sourceLength);
         to += LENGTH_PER_VERSION;
         System.arraycopy(source, sourceOffset, target, to, sourceLength);
         to += sourceLength;
-        Debug.$assert0.t(verify(target, targetOffset, to - targetOffset));
+        Debug.$assert0.t(verify(target, targetOffset, to - targetOffset + remainder));
 
-        return (to - targetOffset) | existedMask;
+        return (to - targetOffset + remainder) | existedMask;
     }
 
     /**

=== added file 'src/test/java/com/persistit/Bug1056489Test.java'
--- src/test/java/com/persistit/Bug1056489Test.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/Bug1056489Test.java	2012-09-27 17:48:28 +0000
@@ -0,0 +1,125 @@
+/**
+ * Copyright © 2012 Akiban Technologies, Inc.  All rights reserved.
+ * 
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * This program may also be available under different license terms.
+ * For more information, see www.akiban.com or contact [e-mail].
+ * 
+ * Contributors:
+ * Akiban Technologies, Inc.
+ */
+
+package com.persistit;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+import com.persistit.exception.PersistitException;
+import com.persistit.unit.UnitTestProperties;
+
+/**
+ * https://bugs.launchpad.net/akiban-persistit/+bug/1056489
+ * 
+ * When utilizing the step capability of transactions there appear to be
+ * inconsistencies between reading, writing, removing, and pruning. Particularly
+ * when steps of a single transaction appear out of order in a single MVV.
+ * 
+ * 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 concurrent 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.
+ * 
+ */
+
+public class Bug1056489Test extends PersistitUnitTestCase {
+
+    public void update(final Exchange ex, final int k, final int v) throws Exception {
+        _persistit.getTransaction().setStep(2);
+        ex.getKey().clear().append(k);
+        ex.getValue().clear().put(v);
+        ex.store();
+    }
+
+    public void remove(final Exchange ex, final int k) throws Exception {
+        _persistit.getTransaction().setStep(1);
+        ex.getKey().clear().append(k);
+        ex.remove();
+    }
+
+    @Test
+    public void mvvStepCheck() throws Exception {
+        final Transaction txn = _persistit.getTransaction();
+        final 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", 10, 20, 30);
+
+        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", 100, 200, 300);
+        txn.commit();
+        txn.end();
+
+        treeCheck(ex, "Updated, committed", 100, 200, 300);
+
+        while (_persistit.getCleanupManager().getPerformedCount() < _persistit.getCleanupManager().getAcceptedCount()) {
+            Thread.sleep(100);
+        }
+
+        treeCheck(ex, "Updated, committed, pruned", 100, 200, 300);
+
+        _persistit.getTransactionIndex().cleanup();
+        txn.begin();
+
+        treeCheck(ex, "Updated, committed, TI cleaned", 100, 200, 300);
+        ex.clear().append(2);
+        assertTrue("Removed should find key {2}", ex.remove());
+        txn.commit();
+        txn.end();
+        treeCheck(ex, "Updated, committed, TI cleaned, removed", 100, 300);
+    }
+
+    private void treeCheck(final Exchange ex, final String message, final int... expected) throws PersistitException {
+        ex.clear();
+        int index = 0;
+        while (ex.next(true)) {
+            assertTrue("Too many keys", index < expected.length);
+            assertEquals("Wrong value", expected[index++], ex.getValue().getInt());
+
+        }
+    }
+}

=== modified file 'src/test/java/com/persistit/MVVTest.java'
--- src/test/java/com/persistit/MVVTest.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/MVVTest.java	2012-09-27 17:48:28 +0000
@@ -179,8 +179,8 @@
         storedLength &= STORE_LENGTH_MASK;
         assertEquals(targetLength - 1, storedLength);
         assertArrayEqualsLen(
-                newArray(TYPE_MVV, 0, 0, 0, 0, 0, 0, 0, vh1, 0, 2, 0x4, 0x5, 0, 0, 0, 0, 0, 0, 0, vh3, 0, 4, 0x6, 0x7,
-                        0x8, 0x9, 0, 0, 0, 0, 0, 0, 0, vh2, 0, 2, 0xD, 0xE), target, storedLength);
+                newArray(TYPE_MVV, 0, 0, 0, 0, 0, 0, 0, vh1, 0, 2, 0x4, 0x5, 0, 0, 0, 0, 0, 0, 0, vh2, 0, 2, 0xD, 0xE,
+                        0, 0, 0, 0, 0, 0, 0, vh3, 0, 4, 0x6, 0x7, 0x8, 0x9), target, storedLength);
     }
 
     @Test
@@ -197,8 +197,8 @@
 
         assertEquals(targetLength + 1, storedLength);
         assertArrayEqualsLen(
-                newArray(TYPE_MVV, 0, 0, 0, 0, 0, 0, 0, vh1, 0, 2, 0x4, 0x5, 0, 0, 0, 0, 0, 0, 0, vh3, 0, 4, 0x6, 0x7,
-                        0x8, 0x9, 0, 0, 0, 0, 0, 0, 0, vh2, 0, 4, 0xC, 0xD, 0xE, 0xF), target, storedLength);
+                newArray(TYPE_MVV, 0, 0, 0, 0, 0, 0, 0, vh1, 0, 2, 0x4, 0x5, 0, 0, 0, 0, 0, 0, 0, vh2, 0, 4, 0xC, 0xD,
+                        0xE, 0xF, 0, 0, 0, 0, 0, 0, 0, vh3, 0, 4, 0x6, 0x7, 0x8, 0x9), target, storedLength);
     }
 
     @Test
@@ -220,15 +220,8 @@
 
     @Test
     public void storeBigVersions() {
-        final long versions[] = { Integer.MAX_VALUE, 10, 1844674407370955161L /*
-                                                                               * MAX
-                                                                               * /
-                                                                               * 5
-                                                                               * -
-                                                                               * ish
-                                                                               */, Short.MAX_VALUE, Long.MAX_VALUE,
-                8301034833169298227L /* MAX*0.9-ish */
-        };
+        final long versions[] = { 10, Short.MAX_VALUE, Integer.MAX_VALUE, 1844674407370955161L, 8301034833169298227L,
+                Long.MAX_VALUE };
         final byte contents[][] = { newArray(0xA0), newArray(0xB0, 0xB1), newArray(0xC0, 0xC1, 0xC2),
                 newArray(0xD0, 0xD1, 0xD2, 0xD3), newArray(0xE0, 0xE1, 0xE2, 0xE3, 0xE4),
                 newArray(0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5) };