Merge lp:~pbeaman/akiban-persistit/fix-1058650-ISE-out-of-order-MVV into lp:akiban-persistit

[Peter Beaman]

Fix bug 1058650 IllegalStateException due to out-of-order MVVs. The bug is caused by a race between the prune/wwDependency check/storeVersion sequence in Exchange#storeInternal and a transaction in another thread aborting. If the transaction aborts after pruning, but before wwDependency check, then it's version is left in the MVV. If the other transaction started with a higher timestamp that the current transaction, this condition will be recognized as an out-of-order version sequence in MVV#storeVersion. Currently storeVersion has no way to query the transaction status of the now-aborted transaction and is not equipped to further prune the entries. Rather than modifying that method, the fix is a simple retry loop that repeats the prune operation to get rid of the aborted version. This seems reasonable because the condition occurs so rarely.

I did not add a unit test since sequencing this is a bit tricky with ThreadSequencer, but I did confirm by running the MixtureTxn1 stress test that instances of retry do occur and yield the correct result.

Part of the implementation is a new VersionsOutOfOrderException. As proposed this is a subclass of IllegalStateException, which is permitted (ISE is not final) but perhaps a little funky. I would be happy to change this to subclassing RuntimeException or alternatively returning a distinguished value from storeVersion to signal the retry. Advice is welcome.

Note that the assert statement that detects this condition was added only recently, and the condition in which an aborted transaction's version is out-of-sequence with another version must have occurred often and harmlessly before this. The fix chosen here is to prune that version away rather than leaving it since (a) it's an opportune time to prune, and (b) it keeps the ordering logic and assertion simple.

[Nathan Williams (nwilliams)]

Rare and subtle indeed.

Is this retry loop safe? I'm thinking of something like a prune that really does change the array, so getEncodedSize() != spareSize, and then a failed store. Wouldn't the next call to prune and visit think the array is bigger than it actually is?

review: Needs Information

[Peter Beaman (pbeaman)]

Thanks for the good find. I think I fixed that by resetting the spareValue encoded size to the pruned size. I also discovered a break statement inside of the new retry loop that was intended to break the outer loop. Added a break label, which is kind of ugly syntax. Tell me if this offends and you see a better alternative.

[Nathan Williams (nwilliams)]

Works for me.

review: Approve

[Peter Beaman (pbeaman)]

Conflicts with other branch

[lp:~pbeaman/akiban-persistit/fix-1058650-ISE-out-of-order-MVV]

376. By Peter Beaman on 2012-10-02

Merge from trunk and resolve conflicts

377. By Peter Beaman on 2012-10-02

Fix format

Unmerged revisions

=== modified file 'src/main/java/com/persistit/Exchange.java'
--- src/main/java/com/persistit/Exchange.java	2012-09-28 21:39:44 +0000
+++ src/main/java/com/persistit/Exchange.java	2012-10-02 20:50:24 +0000
@@ -52,6 +52,7 @@
 import com.persistit.exception.RetryException;
 import com.persistit.exception.RollbackException;
 import com.persistit.exception.TreeNotFoundException;
+import com.persistit.exception.VersionsOutOfOrderException;
 import com.persistit.exception.WWRetryException;
 import com.persistit.policy.JoinPolicy;
 import com.persistit.policy.SplitPolicy;
@@ -251,6 +252,8 @@
 
     private final static int RIGHT_CLAIMED = 2;
 
+    private final static int VERSIONS_OUT_OF_ORDER_RETRY_COUNT = 3;
+
     private Persistit _persistit;
 
     private final Key _key;
@@ -1382,7 +1385,8 @@
         try {
 
             Value valueToStore = value;
-            for (;;) {
+
+            mainRetryLoop: for (;;) {
                 Debug.$assert0.t(buffer == null);
                 if (Debug.ENABLED) {
                     Debug.suspend();
@@ -1427,7 +1431,7 @@
 
                         Debug.$assert0.t(valueToStore.getPointerValue() > 0);
                         insertIndexLevel(key, valueToStore);
-                        break;
+                        break mainRetryLoop;
                     }
 
                     Debug.$assert0.t(buffer == null);
@@ -1488,57 +1492,77 @@
                         if (doMVCC) {
                             valueToStore = spareValue;
                             final int valueSize = value.getEncodedSize();
-                            /*
-                             * If key didn't exist the value is truly
-                             * non-existent and not just undefined/zero length
-                             */
-                            byte[] spareBytes = spareValue.getEncodedBytes();
-                            int spareSize = keyExisted ? spareValue.getEncodedSize() : -1;
-                            spareSize = MVV.prune(spareBytes, 0, spareSize, _persistit.getTransactionIndex(), false,
-                                    prunedVersions);
-
-                            final TransactionStatus tStatus = _transaction.getTransactionStatus();
-                            final int tStep = _transaction.getStep();
-
-                            if ((options & StoreOptions.ONLY_IF_VISIBLE) != 0) {
-                                /*
-                                 * Could be single visit of all versions but
-                                 * current TI would still require calls to both
-                                 * commitStatus() and wwDependency()
-                                 */
-                                _mvvVisitor.initInternal(tStatus, tStep, MvvVisitor.Usage.FETCH);
-                                MVV.visitAllVersions(_mvvVisitor, spareBytes, 0, spareSize);
-                                final int offset = _mvvVisitor.getOffset();
-                                if (!_mvvVisitor.foundVersion()
-                                        || (_mvvVisitor.getLength() > 0 && spareBytes[offset] == MVV.TYPE_ANTIVALUE)) {
-                                    // Completely done, nothing to store
-                                    keyExisted = false;
+                            int retries = VERSIONS_OUT_OF_ORDER_RETRY_COUNT;
+
+                            for (;;) {
+                                try {
+                                    /*
+                                     * If key didn't exist the value is truly
+                                     * non-existent and not just undefined/zero
+                                     * length
+                                     */
+                                    byte[] spareBytes = spareValue.getEncodedBytes();
+                                    int spareSize;
+                                    if (keyExisted) {
+                                        spareSize = MVV.prune(spareBytes, 0, spareValue.getEncodedSize(),
+                                                _persistit.getTransactionIndex(), false, prunedVersions);
+                                        spareValue.setEncodedSize(spareSize);
+                                    } else {
+                                        spareSize = -1;
+                                    }
+
+                                    final TransactionStatus tStatus = _transaction.getTransactionStatus();
+                                    final int tStep = _transaction.getStep();
+
+                                    if ((options & StoreOptions.ONLY_IF_VISIBLE) != 0) {
+                                        /*
+                                         * Could be single visit of all versions
+                                         * but current TI would still require
+                                         * calls to both commitStatus() and
+                                         * wwDependency()
+                                         */
+                                        _mvvVisitor.initInternal(tStatus, tStep, MvvVisitor.Usage.FETCH);
+                                        MVV.visitAllVersions(_mvvVisitor, spareBytes, 0, spareSize);
+                                        final int offset = _mvvVisitor.getOffset();
+                                        if (!_mvvVisitor.foundVersion()
+                                                || (_mvvVisitor.getLength() > 0 && spareBytes[offset] == MVV.TYPE_ANTIVALUE)) {
+                                            // Completely done, nothing to store
+                                            keyExisted = false;
+                                            break mainRetryLoop;
+                                        }
+                                    }
+
+                                    // Visit all versions for ww detection
+                                    _mvvVisitor.initInternal(tStatus, tStep, MvvVisitor.Usage.STORE);
+                                    MVV.visitAllVersions(_mvvVisitor, spareBytes, 0, spareSize);
+
+                                    final int mvvSize = MVV.estimateRequiredLength(spareBytes, spareSize, valueSize);
+                                    spareValue.ensureFit(mvvSize);
+                                    spareBytes = spareValue.getEncodedBytes();
+
+                                    final long versionHandle = TransactionIndex.tss2vh(
+                                            _transaction.getStartTimestamp(), tStep);
+                                    int storedLength = MVV.storeVersion(spareBytes, 0, spareSize, spareBytes.length,
+                                            versionHandle, value.getEncodedBytes(), 0, valueSize);
+
+                                    incrementMVVCount = (storedLength & MVV.STORE_EXISTED_MASK) == 0;
+                                    storedLength &= MVV.STORE_LENGTH_MASK;
+                                    spareValue.setEncodedSize(storedLength);
+
+                                    Debug.$assert0.t(MVV.verify(_persistit.getTransactionIndex(), spareBytes, 0,
+                                            storedLength));
+
+                                    if (spareValue.getEncodedSize() > maxSimpleValueSize) {
+                                        newLongRecordPointerMVV = getLongRecordHelper().storeLongRecord(spareValue,
+                                                _transaction.isActive());
+                                    }
                                     break;
+                                } catch (final VersionsOutOfOrderException e) {
+                                    if (retries <= 0) {
+                                        throw e;
+                                    }
                                 }
                             }
-
-                            // Visit all versions for ww detection
-                            _mvvVisitor.initInternal(tStatus, tStep, MvvVisitor.Usage.STORE);
-                            MVV.visitAllVersions(_mvvVisitor, spareBytes, 0, spareSize);
-
-                            final int mvvSize = MVV.estimateRequiredLength(spareBytes, spareSize, valueSize);
-                            spareValue.ensureFit(mvvSize);
-                            spareBytes = spareValue.getEncodedBytes();
-
-                            final long versionHandle = TransactionIndex.tss2vh(_transaction.getStartTimestamp(), tStep);
-                            int storedLength = MVV.storeVersion(spareBytes, 0, spareSize, spareBytes.length,
-                                    versionHandle, value.getEncodedBytes(), 0, valueSize);
-
-                            incrementMVVCount = (storedLength & MVV.STORE_EXISTED_MASK) == 0;
-                            storedLength &= MVV.STORE_LENGTH_MASK;
-                            spareValue.setEncodedSize(storedLength);
-
-                            Debug.$assert0.t(MVV.verify(_persistit.getTransactionIndex(), spareBytes, 0, storedLength));
-
-                            if (spareValue.getEncodedSize() > maxSimpleValueSize) {
-                                newLongRecordPointerMVV = getLongRecordHelper().storeLongRecord(spareValue,
-                                        _transaction.isActive());
-                            }
                         }
                     }
 

=== modified file 'src/main/java/com/persistit/MVV.java'
--- src/main/java/com/persistit/MVV.java	2012-09-28 21:41:44 +0000
+++ src/main/java/com/persistit/MVV.java	2012-10-02 20:50:24 +0000
@@ -27,6 +27,7 @@
 import com.persistit.exception.PersistitException;
 import com.persistit.exception.PersistitInterruptedException;
 import com.persistit.exception.TimeoutException;
+import com.persistit.exception.VersionsOutOfOrderException;
 import com.persistit.util.Debug;
 import com.persistit.util.Util;
 
@@ -343,7 +344,7 @@
                     }
                 } else if (curVersion > versionHandle) {
                     if (vh2ts(versionHandle) != vh2ts(curVersion)) {
-                        throw new IllegalStateException("Versions out of order");
+                        throw new VersionsOutOfOrderException("Versions out of order");
                     }
                     remainder = end - to;
                     break;

=== added file 'src/main/java/com/persistit/exception/VersionsOutOfOrderException.java'
--- src/main/java/com/persistit/exception/VersionsOutOfOrderException.java	1970-01-01 00:00:00 +0000
+++ src/main/java/com/persistit/exception/VersionsOutOfOrderException.java	2012-10-02 20:50:24 +0000
@@ -0,0 +1,40 @@
+/**
+ * Copyright © 2005-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.exception;
+
+/**
+ * Thrown by {@link com.persistit.Transaction} when
+ * {@link com.persistit.Transaction#commit commit} fails, or when
+ * {@link com.persistit.Transaction#rollback rollback} is invoked.
+ * 
+ * @version 1.0
+ */
+public class VersionsOutOfOrderException extends IllegalStateException {
+
+    private static final long serialVersionUID = 8247927727242238555L;
+
+    public VersionsOutOfOrderException() {
+        super();
+    }
+
+    public VersionsOutOfOrderException(final String msg) {
+        super(msg);
+    }
+
+    public VersionsOutOfOrderException(final Throwable t) {
+        super(t);
+    }
+}