Merge lp:~pbeaman/akiban-persistit/transaction-tree-management into lp:akiban-persistit

[Peter Beaman]

This branch makes the creation and removal of Tree instances transactional. That is, a Tree created within a transaction is not visible outside of that transaction until it commits (and then only to transactions that start after the creator's commit timestamp), and a Tree removed within a transaction remains visible to concurrent transactions; its removal is visible only to transactions that start after the removing transaction commits. Attempts by concurrent transactions to alter the existence of a Tree (either to create or remove it) result in write-write conflicts so that only one such transaction performing a tree creation or deletion can commit.

These changes will support DDL operations on Akiban Server. For example, a new index can be created inside of a transaction; the entire Tree becomes visible only when the transaction commits. Further, since the entire Tree would be removed in the event the transaction rolls back, the updates within the tree are made without writing MVVs that need to be pruned.

Similarly, the removal of an index by removing its Tree within a transaction will be visible only to transactions that start after the removal commits; concurrent transactions continue to see the tree.

To accommodate these behaviors, removing a tree within a transaction does not immediately add the tree's physical pages to the garbage chain. Instead, a version is recorded in memory, and when that version is eventually pruned the physical storage of the tree is removed.

The unit test TreeTransactionalManagementTest demonstrates some of the new behaviors.

The changes in the proposal are widespread because of many side effects. The following is a guide. I expect review questions and will expand upon areas that are unclear.
----

The largest body of new code is the TimelyResource class. It provides a general capability of maintaining a versioned history of a cached resource. It is intended as a mechanism within Persistit that can manage any kind of versioned object, where the object represents state created within a transaction. For example, a TimelyResource could be used to house versions of metadata (the AIS and/or schema) so that concurrent transactions can acquire and use the correct version. For this proposal, it is used to hold Tree.TreeVersion instances.

A TimelyResource manages Version instances, and TimelyResource is generic with respect to a particular Version implementation class. Each TimelyResource is added to a set maintained by the root Persistit instance, and these are polled periodically by the CleanupManager to perform pruning. If a Version maintained by a TimelyResource implements the subinterface PrunableVersion, then prune() method is called for any Version which has become obsolete according to our standard MVCC notion of liveness (i.e., no other active transaction needs the Version for a valid snapshot). The semantics of TimelyResource are documented in its JavaDoc, hopefully accurately and clearly.

Each Tree now uses one TimelyResource instance to manage its transactional state. A Tree created within a transaction has a Tree.TreeVersion instance within the TimelyResource. That version contains most of the state that was formerly held by the Tree object itself. Removing a Tree within a transaction adds a TreeVersion denoted the removed state; the actual reclamation of space held by that three is done when the versions are pruned.

Most of the accessors for state on the Tree object now delegate to the TreeVersion that is visible according to the currently active transaction.

There are some messy bits:

- The serialized state of a Tree represents its existence (which is transactional) and its physical B-Tree allocation (which is not). There are accommodations for this in the VolumeStructure class. We might have preferred a cleaner serialized representation, but the current version works, does not fundamentally limit the design, and is backward compatible. Another accommodation is that the update operations that change the serialized state of the Tree within the directory itself tree must not be reapplied during recovery. Instead, the state changes of the directory tree are implied by the operations that create and remove the trees themselves. Therefore the Transaction#store method explicitly prevents writing of certain directory tree updates even though they occur within the scope of a transaction.

- To make the new Exchange#lock method work properly, it was necessary to disable the transactional nature of tree creation/removal in the temporary volume used for locks. On the basis that this is likely the only temporary volume that will be shared among multiple threads, the current test creates and removes all trees in temporary volumes in a non-transactional (primordial) fashion. We could make this more precise, or we could simply define the transactional tree semantics as affecting only non-temporary volumes (which I think I prefer).

- The tree used by ClassIndex needs to be primordial to avoid unwanted write-write dependencies. Therefore there's an explicit call to create the tree during initialization.

- TreeStatistics are now maintained within a TreeVersion. Because the serialized form needs to be a snapshot view, these are now flushed within the checkpoint cycle only, and not periodically. As a consequence I believe the recovered tree statistics are always consistent with their state at checkpoint plus whatever updates are performed during recovery. Needless to say, the count of read operations performed after the keystone checkpoint is lost. This is not keeping me awake at night.

Because the semantic change here is pretty big, I am proposing a new major version increment to 3.3. Unlike other changes, this one does not merely add new methods; it subtly changes the fundamental behavior.

At the moment I have not run the server tests within this, nor have I run benchmarks to assess performance changes. These should be done before we approve the proposal.

[lp:~pbeaman/akiban-persistit/transaction-tree-management]

416. By Peter Beaman on 2013-01-29

Skip directory tree updates in RecoveryManager#DefaultRecoveryListener rather than Transaction#store/#remove

[Peter Beaman (pbeaman)]

Updated to store but not recover directory tree updates in the journal. Needed because rollback needs the records in order to prune. Otherwise we get an assertion on a negative mvvCount.

[Peter Beaman (pbeaman)]

Information only. Here's what we need to deal with in server:

Results :

Failed tests: deleteMissingRow(com.akiban.server.test.it.dxl.CBasicIT): open cursors remaining:{CursorId[session 2712, table 39, cursor 1407]=ScanData[cursor=Cursor(created=1359482331405, state=FINISHED, request=com.akiban.server.api.dml.scan.ScanAllRequest@60ac2d55), columns=[0, 1]]}
  testYaml [test-bug1025059](com.akiban.sql.pg.PostgresServerMiscYamlIT): src/test/resources/com/akiban/sql/pg/yaml/bugs/test-bug1025059.yaml: org.postgresql.util.PSQLException: An I/O error occured while sending to the backend.

Tests in error:
  dropGroupingForeignKeyMiddleOfGroup(com.akiban.server.test.it.dxl.AlterTableBasicIT): PERSISTIT_ERROR: Persistit Data Layer error: null
  setDataType_C_id(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  setDataType_O_id(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  dropColumn_C_id(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  dropColumn_O_id(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  dropPrimaryKey_C(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  dropPrimaryKey_O(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  addGroupingForeignKey_C(com.akiban.server.test.it.dxl.AlterTableCAOIIT): PERSISTIT_ERROR: Persistit Data Layer error: null
  dropGroupingForeignKey_O(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  setDataType_O_cid(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  dropColumn_O_cid(com.akiban.server.test.it.dxl.AlterTableCAOIIT)
  deleteMissingRow(com.akiban.server.test.it.dxl.CBasicIT): Unexpected exception, expected<com.akiban.server.error.NoSuchRowException> but was<com.akiban.server.error.PersistitAdapterException>
  testRepeated(com.akiban.sql.pg.PostgresServerCacheIT): An I/O error occured while sending to the backend.
  testMultipleUpdate [commit-1](com.akiban.sql.pg.PostgresServerMultipleUpdateIT): An I/O error occured while sending to the backend.

Tests run: 2245, Failures: 2, Errors: 14, Skipped: 99

[Nathan Williams (nwilliams)]

Very nice! The meat of the changes really aren't too complicated and everything seems to fit nicely.

The only code change I would suggest, ask about really, is the live-ness determination in TimelyResource#prune(). I don't suspect it to be wrong but it is performing the same thing as MVV#prune(). They are operating on structures so different that I don't see a simple way to merge, but I had to convince myself they did the same thing. Can you think of anything to share the logic between them?

I would also like to see a handful of tests around what is in the directory tree, shutdown and recovery where multiple versions were present, and the (lack of) MVVs in writes to trees created in the same transaction.

The rest is a smattering of feedback, ranging from small to nits.

TimelyResource
- JavaDoc has a number of invalid links. Lots of other docs like that too, but this is all new.
- Should getVersionCount() should be public? Fairly harmless, but I don't think we leak information like that from other places (Exchange, etc)
- Should delete() check for _first != null? Seems like deleting a resource with no versions should be exception or assert worthy.

Exchange
- Why was the assertCorrecThread() removed from init(), hasChildren(), and isDirectoryExchange??
- The semantic change on checkThread (null-ing out of !set) is subtle. Perhaps renaming the method to checkAndSetThread or checkSetOrClearThread or something would help.
- A couple places call throttle() and now have multiple conditions. A helper may be in order.
- The addition of 'spareValue.isDefined() || !_tree.isTransationPrivate' in store() isn't clear to me. When would doMVCC be be true and the value be empty?

Tree
- End of the new paragraph of JavaDoc has two open <code> tags instead of open and close.
- version() has a // TODO about throwing a RuntimeException
- There are now a number of places where isValid() and isDeleted() must be called together. Maybe a new helper? A more drastic change, but perhaps safer, would be to make it protected in SharedResource and not promote it to public in Tree.

VolumeStructure
- remoteTree() now only returns true (or throws)

TimelyResourceTest
- testAndPruneResources(boolean) might want to append withTransactions to the assert messages. Does the CleanupManager need disabled to avoid spurious failures?
- doConcurrentTransaction() is called from threads so using fail() won't cause the test to fail but only generate console output. This needs to get propagated back to the main thread somewhere. There are lightly used helpers in ConcurrentUtil for this.
- deleteResources() uses a raw assert instead of jUnits.

TreeTransactionalLifetimeTest
- simplePruning() has a 5s sleep and a commented out manual cleanup call. The latter seems cleaner and more deterministic, does it not work?
- I'd like to see some tests around the behavior regarding steps. I believe having trees obey it just like data makes the most sense, which is what it does now, but confirming it would be good.
- The TExec helper is duplicating part of the functionality in ConcurrentUtil and doesn't handle errors in a way that will fail the test.

review: Needs Fixing

[lp:~pbeaman/akiban-persistit/transaction-tree-management]

417. By Peter Beaman on 2013-03-10

Modifications per review comments

418. By Peter Beaman on 2013-03-10

Source code cleanup

419. By Peter Beaman on 2013-03-11

Fix up documentation. Optimization: don't add new version to delete resource created with same version handle

420. By Peter Beaman on 2013-03-11

Add some crash and stop/start tests

421. By Peter Beaman on 2013-03-11

& -> &&

422. By Peter Beaman on 2013-03-11

assert -> assertTrue

[Peter Beaman (pbeaman)]

Thanks. The updated version is changed as follows:

1. The only code change I would suggest, ask about really, is the live-ness determination in TimelyResource#prune().

- No change yet. Will look at that again tomorrow.

2. I would also like to see a handful of tests around what is in the directory tree, shutdown and recovery where multiple versions were present, and the (lack of) MVVs in writes to trees created in the same transaction.

- I believe these cases are covered by new tests added to TreeTransactionalLifetimeTest.

3. TimelyResource:

 - JavaDoc fixed. I believe there are no broke links in the Javadoc - if you find some, please let me know.
 - getVersionCount() - reduced to package private
 - delete() - check for null and throw IllegalStateException. Fixed a test that relied on lenient behavior.

Exchange

 - Why was assertCorrectThread() removed - in every case removed I determined there was another call made by a subordinate method. The removed calls were redundant.
 - checkThread(boolean) - I believe the implementations are identical except that the new one does not set _thread to t when it is known already to be t. Since _thread is volatile this may reduce memory contention. (Actually, I'm not sure if it matters.)
 - throttle() - a new helper, as suggested..
 - doMVCC && (spareValue.isDefined() || !tree.isTransactionPrivate()). This is an attempted optimization. In particular, it might be helpful when building a new index within a transaction by avoiding the need to write and prune MVVs. A rollback range-deletes the entire tree, so no value written inside the tree can ever become visible, even though it was written as primordial. There was an error related to different steps - that's fixed with the rather arcane new boolean argument of isTransactionPrivate(boolean). (I thought about two methods with different names but lacked the imagination to name them.) The main point is that in the case where the tree is unknown to any other transaction and there are no step-py things going on, we can simply write a primordial value since (a) no other transaction can see the transaction, and (b) any step that could see the tree must be later than the step that writes the primordial value. To answer your specific question, I believe doMVCC is true whenever a transaction writes a value to a key that did not previously exist.

Tree
 - Javadoc issues: fixed
 - version() now throws a subclass of RuntimeException and does not have a TODO
 - isValue && !isDeleted() is now computed by helper isLive()

VolumeStructure
- removeTree() is now properly void

TimelyResourceTest
- Append withTransactions - done
- doConcurrentTransaction() - reworked to use ConcurrentUtil. Note that I modified ConcurrentUtil extensively to expose more options for use. This was done to allow doConcurrentTransactions to replace threads during execution. I now fully understand the elegance of ConcurrentUtil (which I had not previously paid much attention to) and will endeavor to replace lots of cases in unit tests that created and join background threads with it.
- assert - fixed

TreeTransactionLifetimeTest
- simplePruning() sleep - fixed
- I'd like to see new tests...

[Peter Beaman (pbeaman)]

Note that Akiban Server requires changes to work with transactional trees. Branch lp:~pbeaman/akiban-server/try-transactional-tree contains more or less minimal changes necessary to complete tests. It does not make use of transactional trees to enhance DDL operations, however.

[Nathan Williams (nwilliams)]

Thanks for all the tweaks. Aside from the (possibly unrealistic) desire to unify the live-ness determination, this all looks good to me.

Have we ran the long stress suite or tpcc against this? I assume we'll want to before putting into trunk.

[lp:~pbeaman/akiban-persistit/transaction-tree-management]

423. By Peter Beaman on 2013-03-14

Merge from trunk with changes for lock pruning fix

424. By Peter Beaman on 2013-03-14

Synchronize volume open

[Peter Beaman (pbeaman)]

Stress tests have run four successful nightly iterations.

[lp:~pbeaman/akiban-persistit/transaction-tree-management]

425. By Peter Beaman on 2013-04-29

Merge from trunk

=== modified file 'pom.xml'
--- pom.xml	2013-04-10 20:09:48 +0000
+++ pom.xml	2013-04-29 21:38:25 +0000
@@ -4,7 +4,7 @@
 
     <groupId>com.akiban</groupId>
     <artifactId>akiban-persistit</artifactId>
-    <version>3.2.9-SNAPSHOT</version>
+    <version>3.3-SNAPSHOT</version>
     <packaging>jar</packaging>
 
     <parent>

=== modified file 'src/main/java/com/persistit/Buffer.java'
--- src/main/java/com/persistit/Buffer.java	2013-03-06 16:20:57 +0000
+++ src/main/java/com/persistit/Buffer.java	2013-04-29 21:38:25 +0000
@@ -1424,7 +1424,6 @@
         if (Debug.ENABLED) {
             assertVerify();
         }
-
         final boolean exactMatch = (foundAt & EXACT_MASK) > 0;
         final int p = foundAt & P_MASK;
 
@@ -3869,7 +3868,7 @@
      * @return a human-readable inventory of the contents of this buffer
      */
     public String toStringDetail() {
-        return toStringDetail(-1, 42, 42, 0, true);
+        return toStringDetail(-1, 42, 82, 0, true);
     }
 
     /**

=== modified file 'src/main/java/com/persistit/CheckpointManager.java'
--- src/main/java/com/persistit/CheckpointManager.java	2013-02-04 16:32:35 +0000
+++ src/main/java/com/persistit/CheckpointManager.java	2013-04-29 21:38:25 +0000
@@ -245,6 +245,7 @@
                 final List<Accumulator> accumulators = _persistit.takeCheckpointAccumulators(txn.getStartTimestamp());
                 _persistit.getTransactionIndex().checkpointAccumulatorSnapshots(txn.getStartTimestamp(), accumulators);
                 Accumulator.saveAccumulatorCheckpointValues(accumulators);
+                _persistit.flushStatistics();
                 txn.commit(CommitPolicy.HARD);
                 _currentCheckpoint = new Checkpoint(txn.getStartTimestamp(), System.currentTimeMillis());
                 _outstandingCheckpoints.add(_currentCheckpoint);

=== modified file 'src/main/java/com/persistit/ClassIndex.java'
--- src/main/java/com/persistit/ClassIndex.java	2012-08-24 13:57:19 +0000
+++ src/main/java/com/persistit/ClassIndex.java	2013-04-29 21:38:25 +0000
@@ -94,11 +94,21 @@
      * 
      * @param persistit
      *            Owning Persistit instance.
+     * @throws PersistitException
      */
     ClassIndex(final Persistit persistit) {
         _persistit = persistit;
     }
 
+    void initialize() throws PersistitException {
+        /*
+         * Called during Persistit initialization. This has the desired
+         * side-effect of the class index tree outside of a transaction so that
+         * its existence is primordial.
+         */
+        getExchange();
+    }
+
     /**
      * @return Number of <code>ClassInfo</code> objects currently stored in this
      *         ClassIndex.
@@ -178,8 +188,9 @@
             } catch (final PersistitException pe) {
                 throw new ConversionException(pe);
             } finally {
-                if (ex != null)
+                if (ex != null) {
                     releaseExchange(ex);
+                }
             }
         }
     }

=== modified file 'src/main/java/com/persistit/Exchange.java'
--- src/main/java/com/persistit/Exchange.java	2013-03-23 21:59:48 +0000
+++ src/main/java/com/persistit/Exchange.java	2013-04-29 21:38:25 +0000
@@ -413,7 +413,6 @@
     }
 
     void init(final Volume volume, final String treeName, final boolean create) throws PersistitException {
-        assertCorrectThread(true);
         if (volume == null) {
             throw new NullPointerException();
         }
@@ -441,6 +440,7 @@
             _tree = tree;
             _treeHolder = new ReentrantResourceHolder(_tree);
             _cachedTreeGeneration = -1;
+            _isDirectoryExchange = tree == _volume.getDirectoryTree();
             initCache();
         }
         _splitPolicy = _persistit.getDefaultSplitPolicy();
@@ -503,7 +503,7 @@
 
     private void checkLevelCache() throws PersistitException {
 
-        if (!_tree.isValid()) {
+        if (!_tree.isLive()) {
             if (_tree.getVolume().isTemporary()) {
                 _tree = _tree.getVolume().getTree(_tree.getName(), true);
                 _treeHolder = new ReentrantResourceHolder(_tree);
@@ -1356,11 +1356,7 @@
         if (!isDirectoryExchange()) {
             _persistit.checkSuspended();
         }
-        if (!_ignoreTransactions && !_transaction.isActive()) {
-            _persistit.getJournalManager().throttle();
-        }
-        // TODO: directoryExchange, and lots of tests, don't use transactions.
-        // Skip MVCC for now.
+        throttle();
         int options = StoreOptions.WAIT;
         options |= (!_ignoreTransactions && _transaction.isActive()) ? StoreOptions.MVCC : 0;
         storeInternal(key, value, 0, options);
@@ -1551,7 +1547,13 @@
                             }
                         }
 
-                        if (doMVCC) {
+                        /*
+                         * If the Tree is private to an active transaction, and
+                         * if this is a virgin value, then we can store it
+                         * primordially because if the transaction rolls back,
+                         * the entire Tree will be removed.
+                         */
+                        if (doMVCC && (_spareValue.isDefined() || !_tree.isTransactionPrivate(true))) {
                             valueToStore = spareValue;
                             final int valueSize = value.getEncodedSize();
                             int retries = VERSIONS_OUT_OF_ORDER_RETRY_COUNT;
@@ -3188,7 +3190,6 @@
      * @throws PersistitException
      */
     public boolean hasChildren() throws PersistitException {
-        assertCorrectThread(true);
         _key.copyTo(_spareKey2);
         final int size = _key.getEncodedSize();
         final boolean result = traverse(GT, true, 0, _key.getDepth() + 1, size, null);
@@ -3228,30 +3229,16 @@
      */
     public void removeTree() throws PersistitException {
         assertCorrectThread(true);
+        _persistit.checkSuspended();
         _persistit.checkClosed();
 
-        final long timestamp = _persistit.getCurrentTimestamp();
-        for (int i = 0; i < 100; i++) {
-            _persistit.checkClosed();
-            _persistit.checkSuspended();
-            _persistit.getJournalManager().pruneObsoleteTransactions();
-            if (_persistit.getJournalManager().getEarliestAbortedTransactionTimestamp() > timestamp) {
-                break;
-            }
-            Util.sleep(1000);
-        }
+        _volume.getStructure().removeTree(_tree);
         if (!_ignoreTransactions) {
+            assert !isDirectoryExchange();
             _transaction.removeTree(this);
         }
-
-        clear();
-
+        _key.clear();
         _value.clear();
-        /*
-         * Remove from directory tree.
-         */
-        _volume.getStructure().removeTree(_tree);
-
         initCache();
     }
 
@@ -3410,9 +3397,8 @@
         if (!isDirectoryExchange()) {
             _persistit.checkSuspended();
         }
-        if (!_ignoreTransactions && !_transaction.isActive()) {
-            _persistit.getJournalManager().throttle();
-        }
+
+        throttle();
 
         if (_ignoreTransactions || !_transaction.isActive()) {
             return raw_removeKeyRangeInternal(key1, key2, fetchFirst, false);
@@ -3422,6 +3408,15 @@
 
         _transaction.remove(this, key1, key2);
 
+        /*
+         * If the Tree was created within this transaction then we can just
+         * range-delete the tree since it is not visible outside this
+         * transaction.
+         */
+        if (_tree.isTransactionPrivate(true)) {
+            return raw_removeKeyRangeInternal(key1, key2, fetchFirst, false);
+        }
+
         checkLevelCache();
 
         _value.clear().putAntiValueMVV();
@@ -3994,7 +3989,7 @@
 
     boolean prune(final Key key) throws PersistitException {
         Buffer buffer = null;
-        Debug.$assert1.t(_tree.isValid());
+        Debug.$assert1.t(_tree.isLive());
         try {
             search(key, true);
             buffer = _levelCache[0]._buffer;
@@ -4014,7 +4009,7 @@
         Buffer buffer = null;
         boolean pruned = false;
 
-        Debug.$assert1.t(_tree.isValid());
+        Debug.$assert1.t(_tree.isLive());
         try {
             search(key1, true);
             buffer = _levelCache[0]._buffer;
@@ -4132,13 +4127,30 @@
         assert checkThread(set) : "Thread " + Thread.currentThread() + " must not use " + this + " owned by " + _thread;
     }
 
+    /**
+     * Ensure the this Exchange is compatible with the current Thread; if a
+     * Thread was previously assigned then this thread must be the same one.
+     * 
+     * @param set
+     *            whether to assign the current thread
+     * @return true if and only if there was no assigned Thread or the assigned
+     *         Thread is same as the current Thread.
+     */
     private boolean checkThread(final boolean set) {
         final Thread t = Thread.currentThread();
-        final boolean okay = _thread == null || _thread == t;
-        if (okay) {
-            _thread = set ? t : null;
-        }
-        return okay;
+        if (_thread == t) {
+            if (!set) {
+                _thread = null;
+            }
+            return true;
+        }
+        if (_thread == null) {
+            if (set) {
+                _thread = t;
+            }
+            return true;
+        }
+        return false;
     }
 
     /**
@@ -4187,7 +4199,6 @@
      *         <code>false</code>.
      */
     boolean isDirectoryExchange() {
-        assertCorrectThread(true);
         return _isDirectoryExchange;
     }
 
@@ -4426,4 +4437,15 @@
             _ignoreMVCCFetch = savedIgnore;
         }
     }
+
+    private void throttle() throws PersistitInterruptedException {
+        /*
+         * Don't throttle operations on the directory tree since that makes some
+         * unit tests very slow. This test is now necessary because a directory
+         * tree update can now occur within the scope of a transaction.
+         */
+        if (!_ignoreTransactions && !_transaction.isActive() && !isDirectoryExchange()) {
+            _persistit.getJournalManager().throttle();
+        }
+    }
 }

=== modified file 'src/main/java/com/persistit/JournalManager.java'
--- src/main/java/com/persistit/JournalManager.java	2013-02-15 15:39:42 +0000
+++ src/main/java/com/persistit/JournalManager.java	2013-04-29 21:38:25 +0000
@@ -2862,6 +2862,11 @@
             return false;
         }
 
+        @Override
+        public boolean createTree(final long timestamp) throws PersistitException {
+            return false;
+        }
+
     }
 
     /**

=== modified file 'src/main/java/com/persistit/MVV.java'
--- src/main/java/com/persistit/MVV.java	2012-10-03 14:43:25 +0000
+++ src/main/java/com/persistit/MVV.java	2013-04-29 21:38:25 +0000
@@ -451,7 +451,7 @@
                     if (tc == UNCOMMITTED) {
                         final long ts = vh2ts(versionHandle);
                         if (uncommittedTransactionTs != 0 && uncommittedTransactionTs != ts) {
-                            throw new CorruptValueException("Multiple uncommitted version");
+                            throw new CorruptValueException("Multiple uncommitted versions");
                         }
                         uncommittedTransactionTs = ts;
                         mark(bytes, from);

=== modified file 'src/main/java/com/persistit/Persistit.java'
--- src/main/java/com/persistit/Persistit.java	2013-03-20 16:04:52 +0000
+++ src/main/java/com/persistit/Persistit.java	2013-04-29 21:38:25 +0000
@@ -29,6 +29,7 @@
 import java.lang.management.MemoryMXBean;
 import java.lang.management.MemoryUsage;
 import java.lang.ref.SoftReference;
+import java.lang.ref.WeakReference;
 import java.rmi.RemoteException;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -264,6 +265,8 @@
 
     private final Set<AccumulatorRef> _accumulators = new HashSet<AccumulatorRef>();
 
+    private final Set<WeakReference<TimelyResource<?>>> _timelyResourceSet = new HashSet<WeakReference<TimelyResource<?>>>();
+
     private final WeakHashMap<SessionId, CLI> _cliSessionMap = new WeakHashMap<SessionId, CLI>();
 
     private boolean _readRetryEnabled;
@@ -440,6 +443,7 @@
             startJournal();
             startBufferPools();
             preloadBufferPools();
+            initializeClassIndex();
             finishRecovery();
             startTransactionIndexPollTask();
             flush();
@@ -672,6 +676,10 @@
         _enableBufferInventory.set(_configuration.isBufferInventoryEnabled());
     }
 
+    private void initializeClassIndex() throws PersistitException {
+        _classIndex.initialize();
+    }
+
     void startCheckpointManager() {
         _checkpointManager.start();
     }
@@ -793,17 +801,21 @@
         }
     }
 
-    synchronized void addVolume(final Volume volume) throws VolumeAlreadyExistsException {
-        Volume otherVolume;
-        otherVolume = getVolume(volume.getName());
-        if (otherVolume != null) {
-            throw new VolumeAlreadyExistsException("Volume " + otherVolume);
+    void addVolume(final Volume volume) throws VolumeAlreadyExistsException {
+        synchronized (_volumes) {
+            Volume otherVolume;
+            otherVolume = getVolume(volume.getName());
+            if (otherVolume != null) {
+                throw new VolumeAlreadyExistsException("Volume " + otherVolume);
+            }
+            _volumes.add(volume);
         }
-        _volumes.add(volume);
     }
 
-    synchronized void removeVolume(final Volume volume) throws PersistitInterruptedException {
-        _volumes.remove(volume);
+    void removeVolume(final Volume volume) throws PersistitInterruptedException {
+        synchronized (_volumes) {
+            _volumes.remove(volume);
+        }
     }
 
     /**
@@ -965,7 +977,6 @@
         }
         List<Exchange> stack;
         final SessionId sessionId = getSessionId();
-
         synchronized (_exchangePoolMap) {
             stack = _exchangePoolMap.get(sessionId);
             if (stack == null) {
@@ -986,7 +997,9 @@
      * @return the List
      */
     public List<Volume> getVolumes() {
-        return new ArrayList<Volume>(_volumes);
+        synchronized (_volumes) {
+            return new ArrayList<Volume>(_volumes);
+        }
     }
 
     /**
@@ -1000,9 +1013,10 @@
      * @return the List
      * @throws PersistitException
      */
-    public synchronized List<Tree> getSelectedTrees(final TreeSelector selector) throws PersistitException {
+    public List<Tree> getSelectedTrees(final TreeSelector selector) throws PersistitException {
         final List<Tree> list = new ArrayList<Tree>();
-        for (final Volume volume : _volumes) {
+        final List<Volume> volumes = getVolumes();
+        for (final Volume volume : volumes) {
             if (selector.isSelected(volume)) {
                 if (selector.isVolumeOnlySelection(volume.getName())) {
                     list.add(volume.getDirectoryTree());
@@ -1239,10 +1253,10 @@
         if (name == null) {
             throw new NullPointerException("Null volume name");
         }
+        final List<Volume> volumes = getVolumes();
         Volume result = null;
-
-        for (int i = 0; i < _volumes.size(); i++) {
-            final Volume vol = _volumes.get(i);
+        for (int i = 0; i < volumes.size(); i++) {
+            final Volume vol = volumes.get(i);
             if (name.equals(vol.getName())) {
                 if (result == null)
                     result = vol;
@@ -1256,8 +1270,8 @@
         }
 
         final File file = new File(name).getAbsoluteFile();
-        for (int i = 0; i < _volumes.size(); i++) {
-            final Volume vol = _volumes.get(i);
+        for (int i = 0; i < volumes.size(); i++) {
+            final Volume vol = volumes.get(i);
             if (file.equals(vol.getAbsoluteFile())) {
                 if (result == null)
                     result = vol;
@@ -1477,16 +1491,17 @@
      */
     private Volume getSpecialVolume(final String propName, final String dflt) throws VolumeNotFoundException {
         final String volumeName = _configuration.getSysVolume();
-
-        Volume volume = getVolume(volumeName);
-        if (volume == null) {
+        synchronized (_volumes) {
             if ((_volumes.size() == 1) && (volumeName.equals(dflt))) {
-                volume = _volumes.get(0);
-            } else {
-                throw new VolumeNotFoundException(volumeName);
+                return _volumes.get(0);
             }
         }
-        return volume;
+        final Volume volume = getVolume(volumeName);
+        if (volume == null) {
+            throw new VolumeNotFoundException(volumeName);
+        } else {
+            return volume;
+        }
     }
 
     /**
@@ -1512,13 +1527,8 @@
      */
     void cleanup() {
         closeZombieTransactions(false);
-        final List<Volume> volumes;
-        synchronized (this) {
-            volumes = new ArrayList<Volume>(_volumes);
-        }
-        for (final Volume volume : volumes) {
-            volume.getStructure().flushStatistics();
-        }
+        _transactionIndex.updateActiveTransactionCache();
+        pruneTimelyResources();
     }
 
     /**
@@ -1653,7 +1663,6 @@
 
             if (flush) {
                 for (final Volume volume : volumes) {
-                    volume.getStructure().flushStatistics();
                     volume.getStorage().flush();
                 }
             }
@@ -1755,7 +1764,7 @@
         // the volume files - otherwise there will be left over channels
         // and FileLocks that interfere with subsequent tests.
         //
-        final List<Volume> volumes = new ArrayList<Volume>(_volumes);
+        final List<Volume> volumes = getVolumes();
         for (final Volume volume : volumes) {
             try {
                 volume.getStorage().close();
@@ -1824,8 +1833,11 @@
         synchronized (_accumulators) {
             _accumulators.clear();
         }
-        synchronized (this) {
+        synchronized (_volumes) {
             _volumes.clear();
+        }
+
+        synchronized (this) {
             _alertMonitors.clear();
             _bufferPoolTable.clear();
             _intArrayThreadLocal.set(null);
@@ -1867,8 +1879,8 @@
         if (_closed.get() || !_initialized.get()) {
             return false;
         }
-        for (final Volume volume : _volumes) {
-            volume.getStructure().flushStatistics();
+        final List<Volume> volumes = getVolumes();
+        for (final Volume volume : volumes) {
             volume.getStorage().flush();
             volume.getStorage().force();
         }
@@ -1894,6 +1906,13 @@
         }
     }
 
+    void flushStatistics() throws PersistitException {
+        final List<Volume> volumes = getVolumes();
+        for (final Volume volume : volumes) {
+            volume.getStructure().flushStatistics();
+        }
+    }
+
     void waitForIOTaskStop(final IOTaskRunnable task) {
         if (_beginCloseTime == 0) {
             _beginCloseTime = System.nanoTime();
@@ -1926,7 +1945,7 @@
         if (_closed.get() || !_initialized.get()) {
             return;
         }
-        final ArrayList<Volume> volumes = _volumes;
+        final List<Volume> volumes = getVolumes();
 
         for (int index = 0; index < volumes.size(); index++) {
             final Volume volume = volumes.get(index);
@@ -2236,10 +2255,6 @@
         return _transactionIndex;
     }
 
-    public long getCheckpointIntervalNanos() {
-        return _checkpointManager.getCheckpointIntervalNanos();
-    }
-
     /**
      * Replaces the current logger implementation.
      * 
@@ -2286,8 +2301,9 @@
      */
     public void checkAllVolumes() throws PersistitException {
         final IntegrityCheck icheck = new IntegrityCheck(this);
-        for (int index = 0; index < _volumes.size(); index++) {
-            final Volume volume = _volumes.get(index);
+        final List<Volume> volumes = getVolumes();
+        for (int index = 0; index < volumes.size(); index++) {
+            final Volume volume = volumes.get(index);
             System.out.println("Checking " + volume + " ");
             try {
                 icheck.checkVolume(volume);
@@ -2403,6 +2419,12 @@
         _suspendUpdates.set(suspended);
     }
 
+    void addTimelyResource(final TimelyResource<? extends Version> resource) {
+        synchronized (_timelyResourceSet) {
+            _timelyResourceSet.add(new WeakReference<TimelyResource<? extends Version>>(resource));
+        }
+    }
+
     void addAccumulator(final Accumulator accumulator) throws PersistitException {
         int checkpointCount = 0;
         synchronized (_accumulators) {
@@ -2462,6 +2484,34 @@
         return result;
     }
 
+    void pruneTimelyResources() {
+        final List<TimelyResource<?>> resourcesToPrune = new ArrayList<TimelyResource<?>>();
+        synchronized (_timelyResourceSet) {
+            for (final Iterator<WeakReference<TimelyResource<?>>> iter = _timelyResourceSet.iterator(); iter.hasNext();) {
+                final WeakReference<TimelyResource<?>> ref = iter.next();
+                final TimelyResource<?> resource = ref.get();
+                if (resource != null) {
+                    resourcesToPrune.add(resource);
+                }
+            }
+        }
+        for (final TimelyResource<?> resource : resourcesToPrune) {
+            try {
+                resource.prune();
+            } catch (final PersistitException e) {
+                _logBase.timelyResourcePruneException.log(e, resource);
+            }
+        }
+        synchronized (_timelyResourceSet) {
+            for (final Iterator<WeakReference<TimelyResource<?>>> iter = _timelyResourceSet.iterator(); iter.hasNext();) {
+                final WeakReference<TimelyResource<?>> ref = iter.next();
+                if (ref.get() == null) {
+                    iter.remove();
+                }
+            }
+        }
+    }
+
     synchronized CLI getSessionCLI() {
         CLI cli = _cliSessionMap.get(getSessionId());
         if (cli == null) {

=== modified file 'src/main/java/com/persistit/RecoveryManager.java'
--- src/main/java/com/persistit/RecoveryManager.java	2013-02-15 15:39:42 +0000
+++ src/main/java/com/persistit/RecoveryManager.java	2013-04-29 21:38:25 +0000
@@ -224,14 +224,32 @@
     private final TransactionPlayer _player = new TransactionPlayer(new RecoveryTransactionPlayerSupport());
 
     static class DefaultRecoveryListener implements TransactionPlayerListener {
+
         @Override
         public void store(final long address, final long timestamp, final Exchange exchange) throws PersistitException {
+            if (exchange.isDirectoryExchange() && exchange.getValue().isDefined()
+                    && exchange.getValue().getTypeHandle() == Value.CLASS_TREE) {
+                /*
+                 * Don't recover tree structure updates within transactions
+                 * because the allocation of root pages is not transactional.
+                 * The intent of the change is conveyed by the implicit creation
+                 * of new trees and explicit remove tree records.
+                 */
+                return;
+            }
             exchange.store();
         }
 
         @Override
         public void removeKeyRange(final long address, final long timestamp, final Exchange exchange, final Key from,
                 final Key to) throws PersistitException {
+            if (exchange.isDirectoryExchange()) {
+                /*
+                 * Don't recover directory tree removes because they are implied
+                 * by Remove Tree records in the journal.
+                 */
+                return;
+            }
             exchange.raw_removeKeyRangeInternal(from, to, false, false);
         }
 
@@ -275,6 +293,10 @@
             return true;
         }
 
+        @Override
+        public boolean createTree(final long timestamp) throws PersistitException {
+            return true;
+        }
     }
 
     class DefaultRollbackListener implements TransactionPlayerListener {
@@ -336,6 +358,11 @@
             return false;
         }
 
+        @Override
+        public boolean createTree(final long timestamp) throws PersistitException {
+            return false;
+        }
+
     }
 
     private class RecoveryTransactionPlayerSupport implements TransactionPlayerSupport {

=== modified file 'src/main/java/com/persistit/SharedResource.java'
--- src/main/java/com/persistit/SharedResource.java	2013-04-10 20:09:48 +0000
+++ src/main/java/com/persistit/SharedResource.java	2013-04-29 21:38:25 +0000
@@ -38,7 +38,7 @@
  * 
  * @author peter
  */
-class SharedResource {
+abstract class SharedResource {
 
     /**
      * Default maximum time to wait for access to this resource. Methods throw
@@ -260,10 +260,10 @@
     /**
      * A counter that increments every time the resource is changed.
      */
-    protected AtomicLong _generation = new AtomicLong();
+    private final AtomicLong _generation = new AtomicLong();
 
     protected SharedResource(final Persistit persistit) {
-        this._persistit = persistit;
+        _persistit = persistit;
     }
 
     public boolean isAvailable(final boolean writer) {

=== added file 'src/main/java/com/persistit/TimelyResource.java'
--- src/main/java/com/persistit/TimelyResource.java	1970-01-01 00:00:00 +0000
+++ src/main/java/com/persistit/TimelyResource.java	2013-04-29 21:38:25 +0000
@@ -0,0 +1,505 @@
+/**
+ * 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 com.persistit.TransactionIndex.tss2vh;
+import static com.persistit.TransactionIndex.vh2step;
+import static com.persistit.TransactionIndex.vh2ts;
+import static com.persistit.TransactionStatus.ABORTED;
+import static com.persistit.TransactionStatus.PRIMORDIAL;
+import static com.persistit.TransactionStatus.TIMED_OUT;
+import static com.persistit.TransactionStatus.UNCOMMITTED;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.persistit.Version.PrunableVersion;
+import com.persistit.Version.VersionCreator;
+import com.persistit.exception.PersistitException;
+import com.persistit.exception.PersistitInterruptedException;
+import com.persistit.exception.RollbackException;
+import com.persistit.exception.TimeoutException;
+import com.persistit.exception.WWRetryException;
+
+/**
+ * <p>
+ * Transactionally manage multiple versions of a resource. For example, a
+ * resource which caches state created and either committed or rolled back by a
+ * transaction may be use a TimelyResource to hold its versions. Each version
+ * must implement the {@link Version} interface and may optionally implement
+ * {@link PrunableVersion} in which case its {@link PrunableVersion#prune()}
+ * method is called when <code>TimelyResource</code> detects that the version is
+ * obsolete.
+ * </p>
+ * <p>
+ * The method {@link #addVersion(Version, Transaction)} attempts to add a new
+ * version on behalf of the supplied transaction.
+ * </p>
+ * <p>
+ * The method {@link #getVersion()} returns the snapshot version associated with
+ * the transaction, in other words, an instance of a P which was either
+ * committed last before this transaction started, or which was created by this
+ * transaction. If there is no such version the method returns <code>null</code>
+ * .
+ * </p>
+ * <p>
+ * The method {@link #getVersion(com.persistit.Version.VersionCreator)} does the
+ * same thing, except that if there is no snapshot version the
+ * {@link VersionCreator#createVersion(TimelyResource)} method is called to
+ * construct a new version.
+ * </p>
+ * 
+ * @author peter
+ * 
+ * @param <V>
+ *            specific type of {@link Version} this <code>TimelyResource</code>
+ *            manages
+ */
+public class TimelyResource<V extends Version> {
+
+    private final Persistit _persistit;
+    private volatile Entry _first;
+
+    public TimelyResource(final Persistit persistit) {
+        _persistit = persistit;
+        _persistit.addTimelyResource(this);
+    }
+
+    private long tss2v(final Transaction txn) {
+        if (txn == null || !txn.isActive()) {
+            return tss2vh(_persistit.getTimestampAllocator().updateTimestamp(), 0);
+        } else {
+            return tss2vh(txn.getStartTimestamp(), txn.getStep());
+        }
+    }
+
+    public synchronized void delete() throws RollbackException, PersistitException {
+        if (_first == null) {
+            throw new IllegalStateException("There is no resource to delete");
+        }
+        if (!_first.isDeleted()) {
+            final Transaction txn = _persistit.getTransaction();
+            final long version = tss2v(txn);
+            if (version == _first.getVersion()) {
+                _first.setDeleted();
+            } else {
+                final V resource = _first.getResource();
+                final Entry entry = new Entry(version, resource);
+                entry.setDeleted();
+                addVersion(entry, txn);
+            }
+        }
+    }
+
+    public void addVersion(final V resource, final Transaction txn) throws PersistitInterruptedException,
+            RollbackException {
+        if (resource == null) {
+            throw new NullPointerException("Null resource");
+        }
+        addVersion(new Entry(tss2v(txn), resource), txn);
+    }
+
+    public V getVersion() throws TimeoutException, PersistitInterruptedException {
+        final Entry first = _first;
+        if (first != null && first.getVersion() == PRIMORDIAL) {
+            return first.getResource();
+        }
+        final Transaction txn = _persistit.getTransaction();
+        return getVersion(tss2v(txn));
+    }
+
+    public V getVersion(final VersionCreator<V> creator) throws PersistitException, RollbackException {
+        final Entry first = _first;
+        if (first != null && first.getVersion() == PRIMORDIAL) {
+            return first.getResource();
+        }
+        final Transaction txn = _persistit.getTransaction();
+        V version = getVersion(tss2v(txn));
+        if (version == null) {
+            version = creator.createVersion(this);
+            addVersion(version, txn);
+        }
+        return version;
+    }
+
+    /**
+     * @return <code>true</code> if and only if this <code>TimelyResource</code>
+     *         has no <code>Version</code> instances.
+     */
+    public boolean isEmpty() throws TimeoutException, PersistitInterruptedException {
+        Entry first = _first;
+        if (first == null) {
+            return true;
+        }
+        if (first.getVersion() == PRIMORDIAL) {
+            return false;
+        }
+        first = getEntry(tss2v(_persistit.getTransaction()));
+        if (first == null) {
+            return true;
+        }
+        if (first.isDeleted()) {
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * 
+     * @return Whether this resource exists only within the context of the
+     *         current transaction.
+     * @throws TimeoutException
+     * @throws PersistitInterruptedException
+     */
+
+    public boolean isTransactionPrivate(final boolean byStep) throws TimeoutException, PersistitInterruptedException {
+        Entry entry = _first;
+        if (entry != null && entry.getVersion() == PRIMORDIAL) {
+            return false;
+        }
+        final Transaction txn = _persistit.getTransaction();
+        final long versionHandle = tss2v(txn);
+        entry = getEntry(versionHandle);
+        if (entry == null) {
+            return true;
+        } else {
+            if (byStep) {
+                return entry.getVersion() == versionHandle;
+            } else {
+                return vh2ts(entry.getVersion()) == vh2ts(versionHandle);
+            }
+        }
+    }
+
+    /**
+     * @return Count of versions currently being managed.
+     */
+    int getVersionCount() {
+        int count = 0;
+        for (Entry e = _first; e != null; e = e._previous) {
+            count++;
+        }
+        return count;
+    }
+
+    @Override
+    public String toString() {
+        final StringBuilder sb = new StringBuilder("TimelyResource(");
+        boolean first = true;
+        for (Entry entry = _first; entry != null; entry = entry.getPrevious()) {
+            if (sb.length() > 1000) {
+                sb.append("...");
+                break;
+            }
+            if (!first) {
+                sb.append(',');
+            } else {
+                first = false;
+            }
+            sb.append(entry);
+        }
+        sb.append(')');
+        return sb.toString();
+    }
+
+    synchronized void setPrimordial() {
+        if (_first != null && _first.getPrevious() == null) {
+            _first.setPrimordial();
+        } else {
+            throw new IllegalStateException("Cannot be made primordial: " + this);
+        }
+    }
+
+    /**
+     * Remove all obsolete <code>Version</code> instances. For each instance
+     * that implements <code>PrunableVersion</code>, invoke its
+     * {@link PrunableVersion#prune()} method.
+     * 
+     * @throws TimeoutException
+     * @throws PersistitException
+     */
+    void prune() throws TimeoutException, PersistitException {
+        final List<Entry> entriesToPrune = new ArrayList<Entry>();
+        PrunableVersion versionToVacate = null;
+
+        final TransactionIndex ti = _persistit.getTransactionIndex();
+
+        synchronized (this) {
+            try {
+
+                Entry newer = null;
+                Entry latest = null;
+                boolean isPrimordial = true;
+                long lastCommit = UNCOMMITTED;
+
+                for (Entry entry = _first; entry != null; entry = entry.getPrevious()) {
+                    boolean keepIt = false;
+                    final long versionHandle = entry.getVersion();
+                    final long tc = ti.commitStatus(versionHandle, UNCOMMITTED, 0);
+                    if (tc >= PRIMORDIAL) {
+                        if (tc == UNCOMMITTED) {
+                            keepIt = true;
+                            isPrimordial = false;
+                        } else {
+                            final boolean hasConcurrent = ti.hasConcurrentTransaction(tc, lastCommit);
+                            if (latest == null || hasConcurrent) {
+                                keepIt = true;
+                                if (latest == null) {
+                                    latest = entry;
+                                }
+                            }
+                            if (keepIt && ti.hasConcurrentTransaction(0, tc)) {
+                                isPrimordial = false;
+                            }
+                        }
+                        lastCommit = tc;
+                    } else {
+                        assert tc == ABORTED;
+                    }
+                    if (keepIt) {
+                        newer = entry;
+                    } else {
+                        if (tc == ABORTED ^ entry.isDeleted()) {
+                            entriesToPrune.add(entry);
+                        }
+                        if (newer == null) {
+                            _first = entry.getPrevious();
+                        } else {
+                            newer.setPrevious(entry.getPrevious());
+                        }
+                    }
+                }
+                if (isPrimordial && _first != null) {
+                    assert _first.getPrevious() == null;
+                    if (_first.isDeleted()) {
+                        final V version = _first.getResource();
+                        if (version instanceof PrunableVersion) {
+                            versionToVacate = (PrunableVersion) version;
+                        }
+                        entriesToPrune.add(_first);
+                        _first = null;
+                    } else {
+                        _first.setPrimordial();
+                    }
+                }
+            } catch (final InterruptedException ie) {
+                throw new PersistitInterruptedException(ie);
+            }
+        }
+        for (final Entry e : entriesToPrune) {
+            if (versionToVacate != null) {
+                versionToVacate.vacate();
+            }
+            e.prune();
+        }
+    }
+
+    /**
+     * Helper method that adds an Entry containing a Version and its timestamp
+     * information. This method checks for write-write dependencies throws a
+     * RollbackException if there is a conflict.
+     * 
+     * @param entry
+     * @param txn
+     * @throws PersistitException
+     * @throws RollbackException
+     */
+    private void addVersion(final Entry entry, final Transaction txn) throws PersistitInterruptedException,
+            RollbackException {
+        final TransactionIndex ti = _persistit.getTransactionIndex();
+        while (true) {
+            try {
+                synchronized (this) {
+                    if (_first != null) {
+                        if (_first.getVersion() > entry.getVersion()) {
+                            /*
+                             * This thread lost a race to make the most recent
+                             * version
+                             */
+                            throw new RollbackException();
+                        }
+                        if (txn.isActive()) {
+                            for (Entry e = _first; e != null; e = e.getPrevious()) {
+                                final long version = e.getVersion();
+                                final long depends = ti.wwDependency(version, txn.getTransactionStatus(), 0);
+                                if (depends == TIMED_OUT) {
+                                    throw new WWRetryException(version);
+                                }
+                                if (depends != 0 && depends != ABORTED) {
+                                    /*
+                                     * version is from a concurrent transaction
+                                     * that already committed or timed out
+                                     * waiting to see. Either way, must abort.
+                                     */
+                                    throw new RollbackException();
+                                }
+                            }
+                        }
+                    }
+                    entry.setPrevious(_first);
+                    _first = entry;
+                    break;
+                }
+            } catch (final WWRetryException re) {
+                try {
+                    final long depends = _persistit.getTransactionIndex().wwDependency(re.getVersionHandle(),
+                            txn.getTransactionStatus(), SharedResource.DEFAULT_MAX_WAIT_TIME);
+                    if (depends != 0 && depends != ABORTED) {
+                        /*
+                         * version is from concurrent txn that already committed
+                         * or timed out waiting to see. Either way, must abort.
+                         */
+                        throw new RollbackException();
+                    }
+                } catch (final InterruptedException ie) {
+                    throw new PersistitInterruptedException(ie);
+                }
+            } catch (final InterruptedException ie) {
+                throw new PersistitInterruptedException(ie);
+            }
+        }
+    }
+
+    /**
+     * Get the <code>Version</code> from the snapshot view specified by the
+     * supplied version handle.
+     * 
+     * @param version
+     *            versionHandle
+     * @return <code>Version</code> for given version handle
+     * @throws TimeoutException
+     * @throws PersistitInterruptedException
+     */
+    V getVersion(final long version) throws TimeoutException, PersistitInterruptedException {
+        final Entry e = getEntry(version);
+        return e == null ? null : e.getResource();
+    }
+
+    Entry getEntry(final long version) throws TimeoutException, PersistitInterruptedException {
+        final TransactionIndex ti = _persistit.getTransactionIndex();
+        try {
+            /*
+             * Note: not necessary to synchronize here. A concurrent transaction
+             * may modify _first, but this method does not need to see that
+             * version since it has not been committed. Conversely, if there is
+             * some transaction that committed before this transaction's start
+             * timestamp, then there is a happened-before relationship due to
+             * the synchronization in transaction registration; since _first is
+             * volatile, we are guaranteed to see the modification made by the
+             * committed transaction.
+             */
+            for (Entry e = _first; e != null; e = e._previous) {
+                final long commitTs = ti.commitStatus(e.getVersion(), vh2ts(version), vh2step(version));
+                if (commitTs >= 0 && commitTs != UNCOMMITTED) {
+                    if (e.isDeleted()) {
+                        return null;
+                    }
+                    return e;
+                }
+            }
+            return null;
+        } catch (final InterruptedException e) {
+            throw new PersistitInterruptedException(e);
+        }
+    }
+
+    /**
+     * <p>
+     * Holder for one instance of an object, such as a {@link Tree}, whose
+     * availability is governed by visibility within a transaction.
+     * </p>
+     * <p>
+     * An Entry has a version handle just like a version in an {@link MVV}. It
+     * is invisible to any transactions that started before the start timestamp,
+     * in write-write conflict with any concurrent transaction, and available to
+     * any transaction that starts after the version has committed. Visibility
+     * within the transaction that creates the TimelyResourceEntry is determined
+     * by the relative step numbers of the current transaction and the version
+     * handle. If there exists a TimelyResource instance with start and commit
+     * timestamps ts1, tc1 then any attempt to add another TimelyResource will
+     * fail unless ts2 > tc1.
+     * </p>
+     * 
+     * @author peter
+     */
+
+    private class Entry {
+
+        private long _version;
+        private V _resource;
+        private volatile boolean _deleted;
+        private volatile Entry _previous;
+
+        private Entry(final long versionHandle, final V resource) {
+            _version = versionHandle;
+            _resource = resource;
+        }
+
+        private V getResource() {
+            return _resource;
+        }
+
+        private void setResource(final V resource) {
+            _resource = resource;
+        }
+
+        private Entry getPrevious() {
+            return _previous;
+        }
+
+        private void setPrevious(final Entry tr) {
+            _previous = tr;
+        }
+
+        private long getVersion() {
+            return _version;
+        }
+
+        private void setPrimordial() {
+            _version = PRIMORDIAL;
+        }
+
+        private void setDeleted() {
+            _deleted = true;
+        }
+
+        private boolean isDeleted() {
+            return _deleted;
+        }
+
+        private boolean prune() throws PersistitException {
+            if (_resource instanceof PrunableVersion) {
+                return ((PrunableVersion) _resource).prune();
+            } else {
+                return true;
+            }
+        }
+
+        @Override
+        public String toString() {
+            String tcStatus;
+            try {
+                final long tc = _persistit.getTransactionIndex().commitStatus(_version, Long.MAX_VALUE, 0);
+                tcStatus = TransactionStatus.tcString(tc);
+            } catch (final Exception e) {
+                tcStatus = e.toString();
+            }
+            return String.format("(ts=%s tc=%s)->%s%s", TransactionStatus.versionString(_version), tcStatus, _resource,
+                    _previous != null ? "*" : "");
+        }
+    }
+
+}

=== modified file 'src/main/java/com/persistit/TransactionPlayer.java'
--- src/main/java/com/persistit/TransactionPlayer.java	2012-11-28 18:52:21 +0000
+++ src/main/java/com/persistit/TransactionPlayer.java	2013-04-29 21:38:25 +0000
@@ -15,11 +15,8 @@
 
 package com.persistit;
 
-/**
- * 
- * Read and apply transaction from the journal to the live database. To apply
- * a transaction, this class calls methods of a 
- */
+import static com.persistit.TransactionIndex.ts2vh;
+
 import java.nio.ByteBuffer;
 import java.util.ArrayList;
 import java.util.List;
@@ -39,6 +36,11 @@
 import com.persistit.exception.PersistitException;
 import com.persistit.exception.VolumeNotFoundException;
 
+/**
+ * Read and apply transaction from the journal to the live database. To apply a
+ * transaction, this class calls methods of a TransactionPlayerListener.
+ */
+
 class TransactionPlayer {
 
     private final AtomicLong appliedUpdates = new AtomicLong();
@@ -67,6 +69,7 @@
 
         boolean requiresLongRecordConversion();
 
+        boolean createTree(long timestamp) throws PersistitException;
     }
 
     final TransactionPlayerSupport _support;
@@ -153,93 +156,106 @@
                 case SR.TYPE: {
                     final int keySize = SR.getKeySize(bb);
                     final int treeHandle = SR.getTreeHandle(bb);
-                    final Exchange exchange = getExchange(treeHandle, address, startTimestamp);
-                    exchange.ignoreTransactions();
-                    final Key key = exchange.getKey();
-                    final Value value = exchange.getValue();
-                    System.arraycopy(bb.array(), bb.position() + SR.OVERHEAD, key.getEncodedBytes(), 0, keySize);
-                    key.setEncodedSize(keySize);
-                    final int valueSize = innerSize - SR.OVERHEAD - keySize;
-                    value.ensureFit(valueSize);
-                    System.arraycopy(bb.array(), bb.position() + SR.OVERHEAD + keySize, value.getEncodedBytes(), 0,
-                            valueSize);
-                    value.setEncodedSize(valueSize);
-
-                    if (value.getEncodedSize() >= Buffer.LONGREC_SIZE
-                            && (value.getEncodedBytes()[0] & 0xFF) == Buffer.LONGREC_TYPE) {
+
+                    final Exchange exchange = getExchange(treeHandle, address, startTimestamp, listener);
+                    if (exchange != null) {
+                        exchange.ignoreTransactions();
+                        final Key key = exchange.getKey();
+                        final Value value = exchange.getValue();
+                        System.arraycopy(bb.array(), bb.position() + SR.OVERHEAD, key.getEncodedBytes(), 0, keySize);
+                        key.setEncodedSize(keySize);
+                        final int valueSize = innerSize - SR.OVERHEAD - keySize;
+                        value.ensureFit(valueSize);
+                        System.arraycopy(bb.array(), bb.position() + SR.OVERHEAD + keySize, value.getEncodedBytes(), 0,
+                                valueSize);
+                        value.setEncodedSize(valueSize);
+
+                        if (value.getEncodedSize() >= Buffer.LONGREC_SIZE
+                                && (value.getEncodedBytes()[0] & 0xFF) == Buffer.LONGREC_TYPE) {
+                            /*
+                             * convertToLongRecord will pollute the
+                             * getReadBuffer(). Therefore before calling it we
+                             * need to copy the TX record to a fresh ByteBuffer.
+                             */
+                            if (bb == _support.getReadBuffer()) {
+                                end = recordSize - (position - start);
+                                bb = ByteBuffer.allocate(end);
+                                bb.put(_support.getReadBuffer().array(), position, end);
+                                bb.flip();
+                                position = 0;
+                            }
+                            if (listener.requiresLongRecordConversion()) {
+                                _support.convertToLongRecord(value, treeHandle, address, commitTimestamp);
+                            }
+                        }
+
+                        listener.store(address, startTimestamp, exchange);
                         /*
-                         * convertToLongRecord will pollute the getReadBuffer().
-                         * Therefore before calling it we need to copy the TX
-                         * record to a fresh ByteBuffer.
+                         * Don't keep exchanges with enlarged value - let them
+                         * be GC'd
                          */
-                        if (bb == _support.getReadBuffer()) {
-                            end = recordSize - (position - start);
-                            bb = ByteBuffer.allocate(end);
-                            bb.put(_support.getReadBuffer().array(), position, end);
-                            bb.flip();
-                            position = 0;
-                        }
-                        if (listener.requiresLongRecordConversion()) {
-                            _support.convertToLongRecord(value, treeHandle, address, commitTimestamp);
+                        if (exchange.getValue().getMaximumSize() < Value.DEFAULT_MAXIMUM_SIZE) {
+                            releaseExchange(exchange);
                         }
                     }
-
-                    listener.store(address, startTimestamp, exchange);
                     appliedUpdates.incrementAndGet();
-                    // Don't keep exchanges with enlarged value - let them be
-                    // GC'd
-                    if (exchange.getValue().getMaximumSize() < Value.DEFAULT_MAXIMUM_SIZE) {
-                        releaseExchange(exchange);
-                    }
                     break;
                 }
 
                 case DR.TYPE: {
                     final int key1Size = DR.getKey1Size(bb);
                     final int elisionCount = DR.getKey2Elision(bb);
-                    final Exchange exchange = getExchange(DR.getTreeHandle(bb), address, startTimestamp);
-                    exchange.ignoreTransactions();
-                    final Key key1 = exchange.getAuxiliaryKey3();
-                    final Key key2 = exchange.getAuxiliaryKey4();
-                    System.arraycopy(bb.array(), bb.position() + DR.OVERHEAD, key1.getEncodedBytes(), 0, key1Size);
-                    key1.setEncodedSize(key1Size);
-                    final int key2Size = innerSize - DR.OVERHEAD - key1Size;
-                    System.arraycopy(key1.getEncodedBytes(), 0, key2.getEncodedBytes(), 0, elisionCount);
-                    System.arraycopy(bb.array(), bb.position() + DR.OVERHEAD + key1Size, key2.getEncodedBytes(),
-                            elisionCount, key2Size);
-                    key2.setEncodedSize(key2Size + elisionCount);
-                    listener.removeKeyRange(address, startTimestamp, exchange, key1, key2);
+                    final Exchange exchange = getExchange(DR.getTreeHandle(bb), address, startTimestamp, listener);
+                    if (exchange != null) {
+                        exchange.ignoreTransactions();
+                        final Key key1 = exchange.getAuxiliaryKey3();
+                        final Key key2 = exchange.getAuxiliaryKey4();
+                        System.arraycopy(bb.array(), bb.position() + DR.OVERHEAD, key1.getEncodedBytes(), 0, key1Size);
+                        key1.setEncodedSize(key1Size);
+                        final int key2Size = innerSize - DR.OVERHEAD - key1Size;
+                        System.arraycopy(key1.getEncodedBytes(), 0, key2.getEncodedBytes(), 0, elisionCount);
+                        System.arraycopy(bb.array(), bb.position() + DR.OVERHEAD + key1Size, key2.getEncodedBytes(),
+                                elisionCount, key2Size);
+                        key2.setEncodedSize(key2Size + elisionCount);
+                        listener.removeKeyRange(address, startTimestamp, exchange, key1, key2);
+                        releaseExchange(exchange);
+                    }
                     appliedUpdates.incrementAndGet();
-                    releaseExchange(exchange);
                     break;
                 }
 
                 case DT.TYPE: {
-                    final Exchange exchange = getExchange(DT.getTreeHandle(bb), address, startTimestamp);
-                    listener.removeTree(address, startTimestamp, exchange);
+                    final Exchange exchange = getExchange(DT.getTreeHandle(bb), address, startTimestamp, listener);
+                    if (exchange != null) {
+                        listener.removeTree(address, startTimestamp, exchange);
+                        releaseExchange(exchange);
+                    }
                     appliedUpdates.incrementAndGet();
-                    releaseExchange(exchange);
                     break;
                 }
 
                 case D0.TYPE: {
-                    final Exchange exchange = getExchange(D0.getTreeHandle(bb), address, startTimestamp);
-                    /*
-                     * Note that the commitTimestamp, not startTimestamp is
-                     * passed to the delta method. The
-                     * Accumulator#updateBaseValue method needs the
-                     * commitTimestamp.
-                     */
-                    listener.delta(address, commitTimestamp, exchange.getTree(), D0.getIndex(bb),
-                            D0.getAccumulatorTypeOrdinal(bb), 1);
-                    appliedUpdates.incrementAndGet();
+                    final Exchange exchange = getExchange(D0.getTreeHandle(bb), address, startTimestamp, listener);
+                    if (exchange != null) {
+                        /*
+                         * Note that the commitTimestamp, not startTimestamp is
+                         * passed to the delta method. The
+                         * Accumulator#updateBaseValue method needs the
+                         * commitTimestamp.
+                         */
+                        listener.delta(address, commitTimestamp, exchange.getTree(), D0.getIndex(bb),
+                                D0.getAccumulatorTypeOrdinal(bb), 1);
+                        appliedUpdates.incrementAndGet();
+                    }
                     break;
                 }
 
                 case D1.TYPE: {
-                    final Exchange exchange = getExchange(D1.getTreeHandle(bb), address, startTimestamp);
-                    listener.delta(address, startTimestamp, exchange.getTree(), D1.getIndex(bb),
-                            D1.getAccumulatorTypeOrdinal(bb), D1.getValue(bb));
+                    final Exchange exchange = getExchange(D1.getTreeHandle(bb), address, startTimestamp, listener);
+                    if (exchange != null) {
+                        listener.delta(address, startTimestamp, exchange.getTree(), D1.getIndex(bb),
+                                D1.getAccumulatorTypeOrdinal(bb), D1.getValue(bb));
+                    }
                     appliedUpdates.incrementAndGet();
                     break;
                 }
@@ -281,7 +297,26 @@
         return String.format("JournalAddress %,d{%,d}", address, timestamp);
     }
 
-    private Exchange getExchange(final int treeHandle, final long from, final long timestamp) throws PersistitException {
+    /**
+     * Returns an Exchange on which an operation can be applied or rolled back.
+     * For a {@link TransactionPlayerListener} that performs roll backs, it is
+     * important not to create a new tree when none exists. Therefore this
+     * method may return <code>null</code> to indicate that no tree exists and
+     * therefore the requested operation should be ignored. Whether to create a
+     * new tree is determined by the
+     * {@link TransactionPlayerListener#createTree(long)} method.
+     * 
+     * @param treeHandle
+     * @param from
+     * @param timestamp
+     * @param listener
+     * @return the <code>Exchange</code> on which a recovery operation should be
+     *         applied, or <code>null</code> if there is no backing
+     *         <code>Tree</code>.
+     * @throws PersistitException
+     */
+    private Exchange getExchange(final int treeHandle, final long from, final long timestamp,
+            final TransactionPlayerListener listener) throws PersistitException {
         final TreeDescriptor td = _support.getPersistit().getJournalManager().lookupTreeHandle(treeHandle);
         if (td == null) {
             throw new CorruptJournalException("Tree handle " + treeHandle + " is undefined at "
@@ -295,6 +330,10 @@
         if (VolumeStructure.DIRECTORY_TREE_NAME.equals(td.getTreeName())) {
             return volume.getStructure().directoryExchange();
         } else {
+            final Tree tree = volume.getStructure().getTreeInternal(td.getTreeName());
+            if (!listener.createTree(timestamp) && (tree == null || !tree.hasVersion(ts2vh(timestamp)))) {
+                return null;
+            }
             final Exchange exchange = _support.getPersistit().getExchange(volume, td.getTreeName(), true);
             exchange.ignoreTransactions();
             return exchange;

=== modified file 'src/main/java/com/persistit/Tree.java'
--- src/main/java/com/persistit/Tree.java	2013-04-11 15:31:16 +0000
+++ src/main/java/com/persistit/Tree.java	2013-04-29 21:38:25 +0000
@@ -23,8 +23,13 @@
 import com.persistit.Accumulator.MinAccumulator;
 import com.persistit.Accumulator.SeqAccumulator;
 import com.persistit.Accumulator.SumAccumulator;
+import com.persistit.Version.PrunableVersion;
+import com.persistit.Version.VersionCreator;
 import com.persistit.exception.CorruptVolumeException;
 import com.persistit.exception.PersistitException;
+import com.persistit.exception.PersistitInterruptedException;
+import com.persistit.exception.RollbackException;
+import com.persistit.exception.TimeoutException;
 import com.persistit.util.Debug;
 import com.persistit.util.Util;
 
@@ -36,6 +41,20 @@
  * {@link Accumulator}s for a B-Tree.
  * </p>
  * <p>
+ * As of Persistit 3.3, this class supports version within transactions. A new
+ * <code>Tree</code> created within the cope of a {@link Transaction} is not
+ * visible within the other transactions until it commits. Similarly, if a
+ * <code>Tree</code> is removed within the scope of a transaction, other
+ * transactions that started before the current transaction commits will
+ * continue to be able to read and write the <code>Tree</code>. As a
+ * side-effect, the physical storage for a <code>Tree</code> is not deallocated
+ * until there are no remaining active transactions that started before the
+ * commit timestamp of the current transaction. Concurrent transactions that
+ * attempt to create or remove the same <code>Tree</code> instance are subject
+ * to a a write-write dependency (see {@link Transaction}); all but one such
+ * transaction must roll back.
+ * </p>
+ * <p>
  * <code>Tree</code> instances are created by
  * {@link Volume#getTree(String, boolean)}. If the <code>Volume</code> already
  * has a B-Tree with the specified name, then the <code>Tree</code> object
@@ -67,15 +86,76 @@
 
     private final String _name;
     private final Volume _volume;
-    private volatile long _rootPageAddr;
-    private volatile int _depth;
-    private final AtomicLong _changeCount = new AtomicLong(0);
     private final AtomicReference<Object> _appCache = new AtomicReference<Object>();
     private final AtomicInteger _handle = new AtomicInteger();
 
-    private final Accumulator[] _accumulators = new Accumulator[MAX_ACCUMULATOR_COUNT];
-
-    private final TreeStatistics _treeStatistics = new TreeStatistics();
+    private final TimelyResource<TreeVersion> _timelyResource;
+
+    private final VersionCreator<TreeVersion> _creator = new VersionCreator<TreeVersion>() {
+
+        @Override
+        public TreeVersion createVersion(final TimelyResource<? extends TreeVersion> resource)
+                throws PersistitException {
+            return new TreeVersion();
+        }
+    };
+
+    class TreeVersion implements PrunableVersion {
+        volatile long _rootPageAddr;
+        volatile int _depth;
+        volatile long _generation = _persistit.getTimestampAllocator().updateTimestamp();
+        final AtomicLong _changeCount = new AtomicLong();
+        volatile boolean _pruned;
+        private final Accumulator[] _accumulators = new Accumulator[MAX_ACCUMULATOR_COUNT];
+        private final TreeStatistics _treeStatistics = new TreeStatistics();
+
+        @Override
+        public boolean prune() throws PersistitException {
+            assert !_pruned;
+            _volume.getStructure().deallocateTree(_rootPageAddr, _depth);
+            discardAccumulators();
+            _pruned = true;
+            _rootPageAddr = -1;
+            return true;
+        }
+
+        @Override
+        public void vacate() {
+            clearValid();
+            _volume.getStructure().removed(Tree.this);
+        }
+
+        @Override
+        public String toString() {
+            return String.format("Tree(%d,%d)%s", _rootPageAddr, _depth, _pruned ? "#" : "");
+        }
+
+        /**
+         * Forget about any instantiated accumulator and remove it from the
+         * active list in Persistit. This should only be called in the during
+         * the process of removing a tree.
+         */
+        void discardAccumulators() {
+            for (int i = 0; i < _accumulators.length; ++i) {
+                if (_accumulators[i] != null) {
+                    _persistit.removeAccumulator(_accumulators[i]);
+                    _accumulators[i] = null;
+                }
+            }
+        }
+    }
+
+    /**
+     * Unchecked wrapper for PersistitException thrown while trying to acquire a
+     * TreeVersion.
+     */
+    public static class TreeVersionException extends RuntimeException {
+        private static final long serialVersionUID = -6372589972106489591L;
+
+        TreeVersionException(final Exception e) {
+            super(e);
+        }
+    }
 
     Tree(final Persistit persistit, final Volume volume, final String name) {
         super(persistit);
@@ -86,7 +166,35 @@
         }
         _name = name;
         _volume = volume;
-        _generation.set(1);
+        _timelyResource = new TimelyResource<TreeVersion>(persistit);
+    }
+
+    TreeVersion version() {
+        try {
+            return _timelyResource.getVersion(_creator);
+        } catch (final PersistitException e) {
+            throw new TreeVersionException(e);
+        }
+    }
+
+    public boolean isDeleted() throws TimeoutException, PersistitInterruptedException {
+        return _timelyResource.isEmpty();
+    }
+
+    boolean isLive() throws TimeoutException, PersistitInterruptedException {
+        return isValid() && !isDeleted();
+    }
+
+    boolean isTransactionPrivate(final boolean byStep) throws TimeoutException, PersistitInterruptedException {
+        return _timelyResource.isTransactionPrivate(byStep);
+    }
+
+    boolean hasVersion(final long versionHandle) throws TimeoutException, PersistitInterruptedException {
+        return _timelyResource.getVersion(versionHandle) != null;
+    }
+
+    void delete() throws RollbackException, PersistitException {
+        _timelyResource.delete();
     }
 
     /**
@@ -110,7 +218,9 @@
 
     @Override
     public boolean equals(final Object o) {
-        if (o instanceof Tree) {
+        if (o == this) {
+            return true;
+        } else if (o instanceof Tree) {
             final Tree tree = (Tree) o;
             return _name.equals(tree._name) && _volume.equals(tree.getVolume());
         } else {
@@ -126,20 +236,32 @@
      * @return The page address
      */
     public long getRootPageAddr() {
-        return _rootPageAddr;
+        final TreeVersion version = version();
+        return version._rootPageAddr;
     }
 
     /**
      * @return the number of levels of the <code>Tree</code>.
      */
     public int getDepth() {
-        return _depth;
+        return version()._depth;
+    }
+
+    @Override
+    public long getGeneration() {
+        return version()._generation;
+    }
+
+    @Override
+    void bumpGeneration() {
+        version()._generation = _persistit.getTimestampAllocator().updateTimestamp();
     }
 
     void changeRootPageAddr(final long rootPageAddr, final int deltaDepth) throws PersistitException {
         Debug.$assert0.t(isOwnedAsWriterByMe());
-        _rootPageAddr = rootPageAddr;
-        _depth += deltaDepth;
+        final TreeVersion version = version();
+        version._rootPageAddr = rootPageAddr;
+        version._depth += deltaDepth;
     }
 
     void bumpChangeCount() {
@@ -147,7 +269,7 @@
         // Note: the changeCount only gets written when there's a structure
         // change in the tree that causes it to be committed.
         //
-        _changeCount.incrementAndGet();
+        version()._changeCount.incrementAndGet();
     }
 
     /**
@@ -155,7 +277,7 @@
      *         this tree; does not including replacement of an existing value
      */
     long getChangeCount() {
-        return _changeCount.get();
+        return version()._changeCount.get();
     }
 
     /**
@@ -165,9 +287,10 @@
      */
     int store(final byte[] bytes, final int index) {
         final byte[] nameBytes = Util.stringToBytes(_name);
-        Util.putLong(bytes, index, _rootPageAddr);
-        Util.putLong(bytes, index + 8, getChangeCount());
-        Util.putShort(bytes, index + 16, _depth);
+        final TreeVersion version = version();
+        Util.putLong(bytes, index, version._rootPageAddr);
+        Util.putLong(bytes, index + 8, version._changeCount.get());
+        Util.putShort(bytes, index + 16, version._depth);
         Util.putShort(bytes, index + 18, nameBytes.length);
         Util.putBytes(bytes, index + 20, nameBytes);
         return 20 + nameBytes.length;
@@ -187,9 +310,10 @@
         if (!_name.equals(name)) {
             throw new IllegalStateException("Invalid tree name recorded: " + name + " for tree " + _name);
         }
-        _rootPageAddr = Util.getLong(bytes, index);
-        _changeCount.set(Util.getLong(bytes, index + 8));
-        _depth = Util.getShort(bytes, index + 16);
+        final TreeVersion version = version();
+        version._rootPageAddr = Util.getLong(bytes, index);
+        version._changeCount.set(Util.getLong(bytes, index + 8));
+        version._depth = Util.getShort(bytes, index + 16);
         return length;
     }
 
@@ -200,7 +324,8 @@
      * @throws PersistitException
      */
     void setRootPageAddress(final long rootPageAddr) throws PersistitException {
-        if (_rootPageAddr != rootPageAddr) {
+        final TreeVersion version = version();
+        if (version._rootPageAddr != rootPageAddr) {
             // Derive the index depth
             Buffer buffer = null;
             try {
@@ -210,8 +335,8 @@
                     throw new CorruptVolumeException(String.format("Tree root page %,d has invalid type %s",
                             rootPageAddr, buffer.getPageTypeName()));
                 }
-                _rootPageAddr = rootPageAddr;
-                _depth = type - Buffer.PAGE_TYPE_DATA + 1;
+                version._rootPageAddr = rootPageAddr;
+                version._depth = type - Buffer.PAGE_TYPE_DATA + 1;
             } finally {
                 if (buffer != null) {
                     buffer.releaseTouched();
@@ -226,10 +351,15 @@
      * <code>Tree</code> to fail.
      */
     void invalidate() {
+        final TreeVersion version = version();
         super.clearValid();
-        _depth = -1;
-        _rootPageAddr = -1;
-        _generation.set(-1);
+        version._depth = -1;
+        version._rootPageAddr = -1;
+        version._generation = _persistit.getTimestampAllocator().updateTimestamp();
+    }
+
+    void setPrimordial() {
+        _timelyResource.setPrimordial();
     }
 
     /**
@@ -238,7 +368,7 @@
      *         </code>Tree</code>
      */
     public TreeStatistics getStatistics() {
-        return _treeStatistics;
+        return version()._treeStatistics;
     }
 
     /**
@@ -248,8 +378,9 @@
      */
     @Override
     public String toString() {
-        return "<Tree " + _name + " in volume " + _volume.getName() + " rootPageAddr=" + _rootPageAddr + " depth="
-                + _depth + " status=" + getStatusDisplayString() + ">";
+        final TreeVersion version = version();
+        return "<Tree " + _name + " in volume " + _volume.getName() + " rootPageAddr=" + version._rootPageAddr
+                + " depth=" + version._depth + " status=" + getStatusDisplayString() + ">";
     }
 
     /**
@@ -278,8 +409,8 @@
     }
 
     /**
-     * Set the tree handle. The tree must may not be a member of a temporary
-     * volume.
+     * Assign and set the tree handle. The tree must may not be a member of a
+     * temporary volume.
      * 
      * @throws PersistitException
      */
@@ -397,7 +528,8 @@
         if (index < 0 || index >= MAX_ACCUMULATOR_COUNT) {
             throw new IllegalArgumentException("Invalid accumulator index: " + index);
         }
-        Accumulator accumulator = _accumulators[index];
+        final TreeVersion version = version();
+        Accumulator accumulator = version._accumulators[index];
         if (accumulator == null) {
             final AccumulatorState saved = Accumulator.getAccumulatorState(this, index);
             long savedValue = 0;
@@ -411,7 +543,7 @@
                 savedValue = saved.getValue();
             }
             accumulator = Accumulator.accumulator(type, this, index, savedValue, _persistit.getTransactionIndex());
-            _accumulators[index] = accumulator;
+            version._accumulators[index] = accumulator;
             _persistit.addAccumulator(accumulator);
         } else if (accumulator.getType() != type) {
             throw new IllegalStateException("Wrong type " + accumulator + " is not a " + type + " accumulator");
@@ -442,17 +574,4 @@
         _handle.set(0);
     }
 
-    /**
-     * Forget about any instantiated accumulator and remove it from the active
-     * list in Persistit. This should only be called in the during the process
-     * of removing a tree.
-     */
-    void discardAccumulators() {
-        for (int i = 0; i < _accumulators.length; ++i) {
-            if (_accumulators[i] != null) {
-                _persistit.removeAccumulator(_accumulators[i]);
-                _accumulators[i] = null;
-            }
-        }
-    }
 }

=== modified file 'src/main/java/com/persistit/ValueHelper.java'
--- src/main/java/com/persistit/ValueHelper.java	2012-08-24 13:57:19 +0000
+++ src/main/java/com/persistit/ValueHelper.java	2013-04-29 21:38:25 +0000
@@ -15,6 +15,8 @@
 
 package com.persistit;
 
+import com.persistit.util.Util;
+
 interface ValueHelper {
 
     int requiredLength(final byte[] target, int targetOffset, int targetLength);
@@ -102,6 +104,11 @@
         public boolean isMVV() {
             return false;
         }
+
+        @Override
+        public String toString() {
+            return _value != null ? Util.hexDump(_value.getEncodedBytes(), 0, _value.getEncodedSize()) : "null";
+        }
     };
 
     static class MVVValueWriter implements ValueHelper {
@@ -145,5 +152,10 @@
         public boolean isMVV() {
             return true;
         }
+
+        @Override
+        public String toString() {
+            return _value != null ? Util.hexDump(_value.getEncodedBytes(), 0, _value.getEncodedSize()) : "null";
+        }
     };
 }

=== added file 'src/main/java/com/persistit/Version.java'
--- src/main/java/com/persistit/Version.java	1970-01-01 00:00:00 +0000
+++ src/main/java/com/persistit/Version.java	2013-04-29 21:38:25 +0000
@@ -0,0 +1,69 @@
+/**
+ * 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 com.persistit.exception.PersistitException;
+
+/**
+ * Marker interface implemented by objects managed within the
+ * {@link TimelyResource} framework.
+ * 
+ * @author peter
+ */
+interface Version {
+    /**
+     * Sub-interface describing <code>Version</code> types that require pruning
+     * when obsolete.
+     * 
+     * @author peter
+     */
+    interface PrunableVersion extends Version {
+        /**
+         * Clean up any state held by this resource. For example, when a
+         * {@link Tree} is pruned, all pages allocated to its content are
+         * deallocated. This method is called when a newer
+         * <code>TimelyResource</code> has been created and is visible to all
+         * active transactions.
+         * 
+         * @return <code>true</code> if all pruning work for this resource has
+         *         been completed, <code>false</code> if the prune method should
+         *         be called again later
+         */
+        boolean prune() throws PersistitException;
+
+        /**
+         * Called after the last known <code>Version</code> managed by a
+         * <code>TimelyResource</code> has been pruned.
+         * 
+         * @throws PersistitException
+         */
+        void vacate() throws PersistitException;
+
+    }
+
+    /**
+     * Interface for a factory that creates Versions of the specified type.
+     * 
+     * @author peter
+     * 
+     * @param <T>
+     * @param <V>
+     */
+    interface VersionCreator<V> {
+        V createVersion(final TimelyResource<? extends V> resource) throws PersistitException;
+    }
+
+}
\ No newline at end of file

=== modified file 'src/main/java/com/persistit/Volume.java'
--- src/main/java/com/persistit/Volume.java	2013-03-13 17:14:51 +0000
+++ src/main/java/com/persistit/Volume.java	2013-04-29 21:38:25 +0000
@@ -456,8 +456,11 @@
      * 
      * @throws PersistitException
      */
-    void open(final Persistit persistit) throws PersistitException {
+    synchronized void open(final Persistit persistit) throws PersistitException {
         checkClosing();
+        if (isOpened()) {
+            return;
+        }
         if (_specification == null) {
             throw new IllegalStateException("Missing VolumeSpecification");
         }

=== modified file 'src/main/java/com/persistit/VolumeStructure.java'
--- src/main/java/com/persistit/VolumeStructure.java	2013-03-13 16:27:04 +0000
+++ src/main/java/com/persistit/VolumeStructure.java	2013-04-29 21:38:25 +0000
@@ -15,17 +15,12 @@
 
 package com.persistit;
 
-import static com.persistit.util.SequencerConstants.TREE_CREATE_REMOVE_A;
-import static com.persistit.util.ThreadSequencer.sequence;
-
 import java.lang.ref.WeakReference;
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 
-import com.persistit.AlertMonitor.AlertLevel;
-import com.persistit.AlertMonitor.Event;
 import com.persistit.exception.BufferSizeUnavailableException;
 import com.persistit.exception.CorruptVolumeException;
 import com.persistit.exception.InUseException;
@@ -131,7 +126,6 @@
 
     Exchange directoryExchange() throws BufferSizeUnavailableException {
         final Exchange ex = new Exchange(_directoryTree);
-        ex.ignoreTransactions();
         return ex;
     }
 
@@ -191,21 +185,30 @@
         if (DIRECTORY_TREE_NAME.equals(name)) {
             throw new IllegalArgumentException("Tree name is reserved: " + name);
         }
-        Tree tree;
+        Tree tree = null;
         final WeakReference<Tree> treeRef = _treeNameHashMap.get(name);
         if (treeRef != null) {
             tree = treeRef.get();
-            if (tree != null && tree.isValid()) {
-                return tree;
+            if (tree != null) {
+                if (tree.isLive()) {
+                    return tree;
+                } else {
+                    if (!createIfNecessary) {
+                        return null;
+                    }
+                }
             }
         }
+        if (tree == null) {
+            tree = new Tree(_persistit, _volume, name);
+        }
         final Exchange ex = directoryExchange();
         ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ROOT).append(name);
         final Value value = ex.fetch().getValue();
-        tree = new Tree(_persistit, _volume, name);
         if (value.isDefined()) {
             value.get(tree);
             loadTreeStatistics(tree);
+            tree.setPrimordial();
             tree.setValid();
         } else if (createIfNecessary) {
             final long rootPageAddr = createTreeRoot(tree);
@@ -216,10 +219,14 @@
         } else {
             return null;
         }
+        if (_volume.isTemporary() || _volume.isLockVolume()) {
+            tree.setPrimordial();
+        }
         if (!_volume.isTemporary()) {
             tree.loadHandle();
         }
         _treeNameHashMap.put(name, new WeakReference<Tree>(tree));
+
         return tree;
     }
 
@@ -249,13 +256,16 @@
             }
         } else {
             final Exchange ex = directoryExchange();
+            if (!tree.isTransactionPrivate(false)) {
+                ex.ignoreTransactions();
+            }
             ex.getValue().put(tree);
             ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ROOT).append(tree.getName()).store();
         }
     }
 
     void storeTreeStatistics(final Tree tree) throws PersistitException {
-        if (tree.getStatistics().isDirty() && !DIRECTORY_TREE_NAME.equals(tree.getName())) {
+        if (tree.isLive() && tree.getStatistics().isDirty() && tree != _directoryTree) {
             final Exchange ex = directoryExchange();
             if (!ex.getVolume().isReadOnly()) {
                 ex.getValue().put(tree.getStatistics());
@@ -273,43 +283,30 @@
         }
     }
 
-    boolean removeTree(final Tree tree) throws PersistitException {
+    void removeTree(final Tree tree) throws PersistitException {
         if (tree == _directoryTree) {
             throw new IllegalArgumentException("Can't delete the Directory tree");
         }
-        _persistit.checkSuspended();
 
         if (!tree.claim(true)) {
             throw new InUseException("Unable to acquire writer claim on " + tree);
         }
-
-        final int treeDepth = tree.getDepth();
-        final long treeRootPage = tree.getRootPageAddr();
-
         try {
-            tree.discardAccumulators();
-
-            synchronized (this) {
-                _treeNameHashMap.remove(tree.getName());
-                tree.bumpGeneration();
-                tree.invalidate();
-
-                tree.changeRootPageAddr(-1, 0);
-                final Exchange ex = directoryExchange();
-                ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ROOT).append(tree.getName()).remove(Key.GTEQ);
-                ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_STATS).append(tree.getName()).remove(Key.GTEQ);
-                ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ACCUMULATOR).append(tree.getName()).remove(Key.GTEQ);
-            }
-            sequence(TREE_CREATE_REMOVE_A);
+            final Exchange ex = directoryExchange();
+            ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ROOT).append(tree.getName()).remove(Key.GTEQ);
+            ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_STATS).append(tree.getName()).remove(Key.GTEQ);
+            ex.clear().append(DIRECTORY_TREE_NAME).append(TREE_ACCUMULATOR).append(tree.getName()).remove(Key.GTEQ);
+            tree.delete();
         } finally {
             tree.release();
         }
-
-        // The Tree is now gone. The following deallocates the
-        // pages formerly associated with it. If this fails we'll be
-        // left with allocated pages that are not available on the garbage
-        // chain for reuse.
-
+    }
+
+    synchronized void removed(final Tree tree) {
+        _treeNameHashMap.remove(tree.getName());
+    }
+
+    void deallocateTree(final long treeRootPage, final int treeDepth) throws PersistitException {
         int depth = treeDepth;
         long page = treeRootPage;
         while (page != -1) {
@@ -341,7 +338,6 @@
                 deallocateGarbageChain(deallocate, 0);
             }
         }
-        return true;
     }
 
     /**
@@ -362,25 +358,22 @@
     /**
      * Flush dirty {@link TreeStatistics} instances. Called periodically on the
      * PAGE_WRITER thread from {@link Persistit#cleanup()}.
+     * 
+     * @throws PersistitException
      */
-    void flushStatistics() {
-        try {
-            final List<Tree> trees = new ArrayList<Tree>();
-            synchronized (this) {
-                for (final WeakReference<Tree> ref : _treeNameHashMap.values()) {
-                    final Tree tree = ref.get();
-                    if (tree != null && tree != _directoryTree) {
-                        trees.add(tree);
-                    }
+    void flushStatistics() throws PersistitException {
+        final List<Tree> trees = new ArrayList<Tree>();
+        synchronized (this) {
+            for (final WeakReference<Tree> ref : _treeNameHashMap.values()) {
+                final Tree tree = ref.get();
+                if (tree != null && tree != _directoryTree) {
+                    trees.add(tree);
                 }
             }
-            for (final Tree tree : trees) {
-                storeTreeStatistics(tree);
-            }
-        } catch (final Exception e) {
-            _persistit.getAlertMonitor().post(
-                    new Event(AlertLevel.ERROR, _persistit.getLogBase().adminFlushException, e),
-                    AlertMonitor.FLUSH_STATISTICS_CATEGORY);
+        }
+
+        for (final Tree tree : trees) {
+            storeTreeStatistics(tree);
         }
     }
 

=== modified file 'src/main/java/com/persistit/logging/LogBase.java'
--- src/main/java/com/persistit/logging/LogBase.java	2012-10-04 20:23:10 +0000
+++ src/main/java/com/persistit/logging/LogBase.java	2013-04-29 21:38:25 +0000
@@ -226,6 +226,9 @@
     @Message("WARNING|%s while pruning transaction record %s")
     public final LogItem pruneException = PersistitLogMessage.empty();
 
+    @Message("WARNING|%s while pruning TimelyResource %s")
+    public final LogItem timelyResourcePruneException = PersistitLogMessage.empty();
+
     @Message("WARNING|Transaction %s pruning incomplete at %s after rollback")
     public final LogItem pruningIncomplete = PersistitLogMessage.empty();
 

=== modified file 'src/main/java/com/persistit/util/SequencerConstants.java'
--- src/main/java/com/persistit/util/SequencerConstants.java	2012-10-10 16:06:49 +0000
+++ src/main/java/com/persistit/util/SequencerConstants.java	2013-04-29 21:38:25 +0000
@@ -61,17 +61,6 @@
             array(WRITE_WRITE_STORE_A, WRITE_WRITE_STORE_C) };
 
     /*
-     * Used in testing sequencing between tree creation and removal
-     */
-    int TREE_CREATE_REMOVE_A = allocate("TREE_CREATE_REMOVE_A");
-    int TREE_CREATE_REMOVE_B = allocate("TREE_CREATE_REMOVE_B");
-    int TREE_CREATE_REMOVE_C = allocate("TREE_CREATE_REMOVE_C");
-
-    int[][] TREE_CREATE_REMOVE_SCHEDULE = new int[][] { array(TREE_CREATE_REMOVE_A, TREE_CREATE_REMOVE_B),
-            array(TREE_CREATE_REMOVE_B), array(TREE_CREATE_REMOVE_A, TREE_CREATE_REMOVE_C),
-            array(TREE_CREATE_REMOVE_A, TREE_CREATE_REMOVE_C) };
-
-    /*
      * Used in testing sequencing between pageNode reading and invalidation in
      * JournalManager
      */
@@ -104,7 +93,7 @@
             array(DEALLOCATE_CHAIN_A, DEALLOCATE_CHAIN_C) };
 
     /*
-     * Used in testing delete/deallocate sequence in Bug1022567Test
+     * Used in testing delete/deallocate sequence in Bug1064565Test
      */
     int ACCUMULATOR_CHECKPOINT_A = allocate("ACCUMULATOR_CHECKPOINT_A");
     int ACCUMULATOR_CHECKPOINT_B = allocate("ACCUMULATOR_CHECKPOINT_B");

=== modified file 'src/test/java/com/persistit/AccumulatorRecoveryTest.java'
--- src/test/java/com/persistit/AccumulatorRecoveryTest.java	2013-04-10 20:09:48 +0000
+++ src/test/java/com/persistit/AccumulatorRecoveryTest.java	2013-04-29 21:38:25 +0000
@@ -167,6 +167,11 @@
                 return true;
             }
 
+            @Override
+            public boolean createTree(final long timestamp) throws PersistitException {
+                return true;
+            }
+
         };
         plan.applyAllRecoveredTransactions(commitListener, plan.getDefaultRollbackListener());
         assertEquals(15, recoveryTimestamps.size());

=== modified file 'src/test/java/com/persistit/AccumulatorTest.java'
--- src/test/java/com/persistit/AccumulatorTest.java	2013-04-10 20:09:48 +0000
+++ src/test/java/com/persistit/AccumulatorTest.java	2013-04-29 21:38:25 +0000
@@ -375,7 +375,7 @@
      */
     @Test
     public void testRecreateAccumulatorAfterCheckpoint() throws PersistitException {
-        final int PASS_COUNT = 2;
+        final int PASS_COUNT = 5;
         final int ROW_COUNT = 10;
         final int ACCUM_INDEX = 0;
         final String TEST_VOLUME_NAME = UnitTestProperties.VOLUME_NAME;

=== modified file 'src/test/java/com/persistit/Bug1018526Test.java'
--- src/test/java/com/persistit/Bug1018526Test.java	2012-11-20 17:45:51 +0000
+++ src/test/java/com/persistit/Bug1018526Test.java	2013-04-29 21:38:25 +0000
@@ -92,7 +92,7 @@
             final TreeDescriptor td = map.remove(handle);
             assertNotNull("Permanent Tree should be un the tree map", td);
         }
-        // expect 1: the directory tree
-        assertEquals("Recovered tree map should contain only permanent trees", 1, map.size());
+        // expect 2: _directory and _classIndex
+        assertEquals("Recovered tree map should contain only permanent trees", 2, map.size());
     }
 }

=== modified file 'src/test/java/com/persistit/Bug920754Test.java'
--- src/test/java/com/persistit/Bug920754Test.java	2013-04-10 20:09:48 +0000
+++ src/test/java/com/persistit/Bug920754Test.java	2013-04-29 21:38:25 +0000
@@ -68,6 +68,7 @@
         while (dir.next(true)) {
             keys++;
         }
-        assertEquals("There should be no remaining keys in the directory tree", 0, keys);
+        // _classIndex
+        assertEquals("There should be one remaining key in the directory tree", 1, keys);
     }
 }

=== modified file 'src/test/java/com/persistit/Bug932097Test.java'
--- src/test/java/com/persistit/Bug932097Test.java	2012-11-25 20:14:58 +0000
+++ src/test/java/com/persistit/Bug932097Test.java	2013-04-29 21:38:25 +0000
@@ -21,6 +21,7 @@
 
     @Test
     public void testInjectedAbortTransactionStatus() throws Exception {
+        final Exchange ex = _persistit.getExchange("persistit", "test", true);
         /*
          * Create a bunch of incomplete transactions
          */
@@ -28,7 +29,6 @@
             _persistit.setSessionId(new SessionId());
             final Transaction txn = _persistit.getTransaction();
             txn.begin();
-            final Exchange ex = _persistit.getExchange("persistit", "test", true);
             ex.getValue().put(RED_FOX);
             txn.begin();
             for (int k = 1; k < 10; k++) {

=== modified file 'src/test/java/com/persistit/CorruptVolumeTest.java'
--- src/test/java/com/persistit/CorruptVolumeTest.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/CorruptVolumeTest.java	2013-04-29 21:38:25 +0000
@@ -37,7 +37,8 @@
             exchange.to(i).store();
         }
         // Corrupt the volume by zonking the the index page
-        final Buffer buffer = exchange.getBufferPool().get(exchange.getVolume(), 4, true, true);
+        final long pageAddr = exchange.fetchBufferCopy(1).getPageAddress();
+        final Buffer buffer = exchange.getBufferPool().get(exchange.getVolume(), pageAddr, true, true);
         Arrays.fill(buffer.getBytes(), 20, 200, (byte) 0);
         buffer.setDirtyAtTimestamp(_persistit.getTimestampAllocator().updateTimestamp());
         buffer.releaseTouched();

=== modified file 'src/test/java/com/persistit/IOFailureTest.java'
--- src/test/java/com/persistit/IOFailureTest.java	2012-11-20 17:45:51 +0000
+++ src/test/java/com/persistit/IOFailureTest.java	2013-04-29 21:38:25 +0000
@@ -283,7 +283,6 @@
 
     @Test
     public void testJournalEOFonRecovery() throws Exception {
-        final Properties properties = _persistit.getProperties();
         final JournalManager jman = _persistit.getJournalManager();
         final Exchange exchange = _persistit.getExchange(_volumeName, "RecoveryTest", true);
         exchange.getValue().put(RED_FOX);
@@ -465,6 +464,10 @@
         boolean done = false;
         while (System.currentTimeMillis() < expires) {
             try {
+                /*
+                 * Needed to avoid leaving a dirty page during checkpoint
+                 */
+                _persistit.flushStatistics();
                 _persistit.copyBackPages();
                 done = true;
                 break;

=== modified file 'src/test/java/com/persistit/IntegrityCheckTest.java'
--- src/test/java/com/persistit/IntegrityCheckTest.java	2012-11-20 17:45:51 +0000
+++ src/test/java/com/persistit/IntegrityCheckTest.java	2013-04-29 21:38:25 +0000
@@ -173,6 +173,8 @@
                 txn.end();
             }
         }
+        _persistit.checkAllVolumes();
+        System.out.println();
         final Configuration config = _persistit.getConfiguration();
         _persistit.crash();
         _persistit = new Persistit();

=== modified file 'src/test/java/com/persistit/JournalManagerTest.java'
--- src/test/java/com/persistit/JournalManagerTest.java	2013-04-10 20:09:48 +0000
+++ src/test/java/com/persistit/JournalManagerTest.java	2013-04-29 21:38:25 +0000
@@ -59,6 +59,12 @@
 
     private final String _volumeName = "persistit";
 
+    @Override
+    public void setUp() throws Exception {
+        super.setUp();
+        _persistit.getExchange(_volumeName, "JournalManagerTest1", true);
+    }
+
     @Test
     public void testJournalRecords() throws Exception {
         store1();
@@ -216,6 +222,11 @@
                 return true;
             }
 
+            @Override
+            public boolean createTree(final long timestamp) throws PersistitException {
+                return true;
+            }
+
         };
         rman.applyAllRecoveredTransactions(actor, rman.getDefaultRollbackListener());
         assertEquals(commitCount, recoveryTimestamps.size());
@@ -298,6 +309,7 @@
         // Allow test to control when pruning will happen
         _persistit.getJournalManager().setRollbackPruningEnabled(false);
         _persistit.getJournalManager().setWritePagePruningEnabled(false);
+
         final Transaction txn = _persistit.getTransaction();
         for (int i = 0; i < 10; i++) {
             txn.begin();

=== modified file 'src/test/java/com/persistit/MVCCPruneBufferTest.java'
--- src/test/java/com/persistit/MVCCPruneBufferTest.java	2013-03-06 16:20:57 +0000
+++ src/test/java/com/persistit/MVCCPruneBufferTest.java	2013-04-29 21:38:25 +0000
@@ -320,6 +320,8 @@
 
     @Test
     public void testWritePagePrune() throws Exception {
+        _persistit.getJournalManager().setWritePagePruningEnabled(false);
+        final Exchange exchange = exchange(1);
         final Transaction txn = _persistit.getTransaction();
         try {
             txn.begin();
@@ -328,8 +330,8 @@
         } finally {
             txn.end();
         }
-        final Volume volume = _persistit.getVolume(TEST_VOLUME_NAME);
-        final Buffer buffer = volume.getPool().get(volume, 3, true, true);
+        final long pageAddr = exchange.fetchBufferCopy(0).getPageAddress();
+        final Buffer buffer = exchange.getBufferPool().get(exchange.getVolume(), pageAddr, true, true);
         assertTrue("Should have multiple MVV records", buffer.getMvvCount() > 2);
         _persistit.getJournalManager().setWritePagePruningEnabled(true);
         _persistit.getTransactionIndex().updateActiveTransactionCache();
@@ -340,14 +342,17 @@
     }
 
     private void storeNewVersion(final int cycle) throws Exception {
-        final Exchange exchange = _persistit.getExchange(TEST_VOLUME_NAME,
-                String.format("%s%04d", TEST_TREE_NAME, cycle), true);
+        final Exchange exchange = exchange(cycle);
         exchange.getValue().put(String.format("%s%04d", RED_FOX, cycle));
         for (int i = 1; i <= 100; i++) {
             exchange.to(i).store();
         }
     }
 
+    private Exchange exchange(final int cycle) throws PersistitException {
+        return _persistit.getExchange(TEST_VOLUME_NAME, String.format("%s%04d", TEST_TREE_NAME, cycle), true);
+    }
+
     private void removeKeys(final int cycle) throws Exception {
         final Exchange exchange = _persistit.getExchange(TEST_VOLUME_NAME, TEST_TREE_NAME, true);
         for (int i = (cycle % 2) + 1; i <= 100; i += 2) {

=== modified file 'src/test/java/com/persistit/PersistitUnitTestCase.java'
--- src/test/java/com/persistit/PersistitUnitTestCase.java	2012-11-20 18:18:02 +0000
+++ src/test/java/com/persistit/PersistitUnitTestCase.java	2013-04-29 21:38:25 +0000
@@ -136,4 +136,15 @@
         _persistit.getCleanupManager().setPollInterval(-1);
         _persistit.getJournalManager().setWritePagePruningEnabled(false);
     }
+
+    protected void drainJournal() throws Exception {
+        _persistit.flush();
+        /*
+         * Causes all TreeStatistics to be marked clean so that the subsequent
+         * checkpoint will not add another dirty page.
+         */
+        _persistit.flushStatistics();
+        _persistit.checkpoint();
+        _persistit.getJournalManager().copyBack();
+    }
 }

=== modified file 'src/test/java/com/persistit/RecoveryTest.java'
--- src/test/java/com/persistit/RecoveryTest.java	2012-11-20 17:45:51 +0000
+++ src/test/java/com/persistit/RecoveryTest.java	2013-04-29 21:38:25 +0000
@@ -83,9 +83,7 @@
         store1();
         JournalManager jman = _persistit.getJournalManager();
         assertTrue(jman.getPageMapSize() > 0);
-        _persistit.flush();
-        _persistit.checkpoint();
-        jman.copyBack();
+        drainJournal();
         assertEquals(0, jman.getPageMapSize());
         _persistit.close();
         _persistit = new Persistit(_config);
@@ -159,6 +157,11 @@
                 return true;
             }
 
+            @Override
+            public boolean createTree(final long timestamp) throws PersistitException {
+                return true;
+            }
+
         };
         plan.applyAllRecoveredTransactions(actor, plan.getDefaultRollbackListener());
         assertEquals(15, recoveryTimestamps.size());
@@ -193,8 +196,7 @@
         store1();
 
         jman.rollover();
-        _persistit.checkpoint();
-        jman.copyBack();
+        drainJournal();
         assertEquals(0, jman.getPageMapSize());
 
         final Transaction txn = _persistit.getTransaction();
@@ -203,8 +205,10 @@
         store1();
         txn.commit();
         txn.end();
-        // Flush an uncommitted version of this transaction - should
-        // prevent journal cleanup.
+        /*
+         * Flush an uncommitted version of this transaction - should prevent
+         * journal cleanup.
+         */
         txn.begin();
         store0();
         txn.flushTransactionBuffer(true);
@@ -212,14 +216,13 @@
         txn.end();
 
         jman.rollover();
-        _persistit.checkpoint();
-        jman.copyBack();
-        //
-        // Because JournalManager thinks there's an open transaction
-        // it should preserve the journal file containing the TX record
-        // for the transaction.
-        //
+        drainJournal();
         assertEquals(0, jman.getPageMapSize());
+        /*
+         * Because JournalManager thinks there's an open transaction it should
+         * preserve the journal file containing the TX record for the
+         * transaction.
+         */
         assertTrue(jman.getBaseAddress() < jman.getCurrentAddress());
         txn.begin();
         store1();
@@ -229,6 +232,7 @@
         jman.unitTestClearTransactionMap();
 
         jman.rollover();
+        _persistit.flushStatistics();
         _persistit.checkpoint();
         /*
          * The TI active transaction cache may be a bit out of date, which can
@@ -238,8 +242,7 @@
          * copier does the right thing.
          */
         _persistit.getTransactionIndex().updateActiveTransactionCache();
-        jman.copyBack();
-
+        drainJournal();
         assertEquals(jman.getBaseAddress(), jman.getCurrentAddress());
         assertEquals(0, jman.getPageMapSize());
 
@@ -381,9 +384,13 @@
         assertTrue(_persistit.getJournalManager().getHandleCount() > updatedHandleValue);
     }
 
+    private final static int T1 = 1000;
+    private final static int T2 = 2000;
+
     @Test
     public void testIndexHoles() throws Exception {
         _persistit.getJournalManager().setAppendOnly(true);
+
         final Transaction transaction = _persistit.getTransaction();
         final StringBuilder sb = new StringBuilder();
         while (sb.length() < 1000) {
@@ -392,7 +399,7 @@
 
         final String s = sb.toString();
         for (int cycle = 0; cycle < 2; cycle++) {
-            for (int i = 1000; i < 2000; i++) {
+            for (int i = T1; i < T2; i++) {
                 final Exchange exchange = _persistit.getExchange("persistit", "RecoveryTest" + i, true);
                 transaction.begin();
                 try {
@@ -407,7 +414,7 @@
             }
 
             for (int j = 0; j < 20; j++) {
-                for (int i = 1000; i < 2000; i++) {
+                for (int i = T1; i < T2; i++) {
                     final Exchange exchange = _persistit.getExchange("persistit", "RecoveryTest" + i, true);
                     transaction.begin();
                     try {
@@ -419,7 +426,7 @@
                 }
             }
 
-            for (int i = 1000; i < 2000; i += 2) {
+            for (int i = T1; i < T2; i += 2) {
                 transaction.begin();
                 try {
                     final Exchange exchange = _persistit.getExchange("persistit", "RecoveryTest" + i, true);
@@ -430,6 +437,7 @@
                 }
             }
         }
+        _persistit.checkAllVolumes();
         _persistit.crash();
 
         _persistit = new Persistit();

=== modified file 'src/test/java/com/persistit/SplitPolicyTest.java'
--- src/test/java/com/persistit/SplitPolicyTest.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/SplitPolicyTest.java	2013-04-29 21:38:25 +0000
@@ -253,7 +253,7 @@
         //
         // forward sequential
         //
-        for (long page = 2; page < 20; page++) {
+        for (long page = ex.clear().append(0).fetchBufferCopy(0).getPageAddress(); page < 20; page++) {
             final Buffer buffer = ex.getBufferPool().get(ex.getVolume(), page, false, true);
             if (buffer.isDataPage()) {
                 final int available = buffer.getAvailableSize();

=== added file 'src/test/java/com/persistit/TimelyResourceTest.java'
--- src/test/java/com/persistit/TimelyResourceTest.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/TimelyResourceTest.java	2013-04-29 21:38:25 +0000
@@ -0,0 +1,290 @@
+/**
+ * Copyright © 2011-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 com.persistit.TransactionIndex.tss2vh;
+import static com.persistit.TransactionStatus.UNCOMMITTED;
+import static com.persistit.unit.ConcurrentUtil.assertSuccess;
+import static com.persistit.unit.ConcurrentUtil.createThread;
+import static com.persistit.unit.ConcurrentUtil.join;
+import static com.persistit.unit.ConcurrentUtil.start;
+import static com.persistit.util.Util.NS_PER_S;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.Semaphore;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import org.junit.Test;
+
+import com.persistit.Version.PrunableVersion;
+import com.persistit.Version.VersionCreator;
+import com.persistit.exception.PersistitException;
+import com.persistit.exception.RollbackException;
+import com.persistit.unit.ConcurrentUtil.ThrowingRunnable;
+import com.persistit.unit.ConcurrentUtil.UncaughtExceptionHandler;
+import com.persistit.util.Util;
+
+public class TimelyResourceTest extends PersistitUnitTestCase {
+
+    private int _idCounter;
+
+    static class TestVersion implements PrunableVersion {
+        final int _id;
+        final TimelyResourceTest _test;
+        final AtomicInteger _pruned = new AtomicInteger();
+
+        TestVersion(final int id, final TimelyResourceTest test) {
+            _id = id;
+            _test = test;
+        }
+
+        @Override
+        public boolean prune() {
+            _pruned.incrementAndGet();
+            return true;
+        }
+
+        @Override
+        public void vacate() {
+            System.out.println("No more versions");
+        }
+
+        @Override
+        public String toString() {
+            return String.format("<%,d:%,d>", _id, _pruned.get());
+        }
+
+        TimelyResourceTest getContainer() {
+            return _test;
+        }
+    }
+
+    @Test
+    public void testAddAndPruneResources() throws Exception {
+        testAddAndPruneResources1(false);
+        testAddAndPruneResources1(true);
+    }
+
+    private void testAddAndPruneResources1(final boolean withTransactions) throws Exception {
+        final Transaction txn = _persistit.getTransaction();
+        final TimelyResource<TestVersion> tr = new TimelyResource<TestVersion>(_persistit);
+        final long[] history = new long[5];
+        final TestVersion[] resources = new TestVersion[5];
+        for (int i = 0; i < 5; i++) {
+            if (withTransactions) {
+                txn.begin();
+            }
+            final TestVersion resource = new TestVersion(i, this);
+            resources[i] = resource;
+            if (!tr.isEmpty()) {
+                tr.delete();
+            }
+            tr.addVersion(resource, txn);
+            if (withTransactions) {
+                txn.commit();
+                txn.end();
+            }
+            history[i] = _persistit.getTimestampAllocator().updateTimestamp();
+        }
+        assertEquals("Incorrect version count " + withTransactions, 9, tr.getVersionCount());
+
+        for (int i = 0; i < 5; i++) {
+            final TestVersion t = tr.getVersion(tss2vh(history[i], 0));
+            assertTrue("Missing version " + withTransactions, t != null);
+            assertEquals("Wrong version " + withTransactions, i, t._id);
+        }
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        tr.prune();
+        assertEquals("Should have one version left " + withTransactions, 1, tr.getVersionCount());
+        assertEquals("Wrong version " + withTransactions, 4, tr.getVersion(tss2vh(UNCOMMITTED, 0))._id);
+
+        tr.delete();
+
+        assertEquals("Should have two versions left " + withTransactions, 2, tr.getVersionCount());
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        tr.prune();
+        assertEquals("Should have no versions left " + withTransactions, 0, tr.getVersionCount());
+
+        for (int i = 0; i < 5; i++) {
+            assertEquals("Should have been pruned " + withTransactions, 1, resources[i]._pruned.get());
+        }
+    }
+
+    @Test
+    public void concurrentAddAndPruneResources() throws Exception {
+        final TimelyResource<TestVersion> tr = new TimelyResource<TestVersion>(_persistit);
+        final Random random = new Random(1);
+        final long expires = System.nanoTime() + 10 * NS_PER_S;
+        final AtomicInteger sequence = new AtomicInteger();
+        final AtomicInteger rollbackCount = new AtomicInteger();
+        final List<Thread> threads = new ArrayList<Thread>();
+        final UncaughtExceptionHandler handler = new UncaughtExceptionHandler();
+        int threadCounter = 0;
+        while (System.nanoTime() < expires) {
+            for (final Iterator<Thread> iter = threads.iterator(); iter.hasNext();) {
+                if (!iter.next().isAlive()) {
+                    iter.remove();
+                }
+            }
+            while (threads.size() < 20) {
+                final Thread t = createThread(String.format("Thread_%06d", ++threadCounter), new ThrowingRunnable() {
+                    @Override
+                    public void run() throws Exception {
+                        doConcurrentTransaction(tr, random, sequence, rollbackCount);
+                    }
+                });
+                threads.add(t);
+                start(handler, t);
+            }
+            Util.sleep(10);
+            tr.prune();
+        }
+        join(Long.MAX_VALUE, handler.getThrowableMap(), threads.toArray(new Thread[threads.size()]));
+        assertSuccess(handler.getThrowableMap());
+        assertTrue("Every transaction rolled back", rollbackCount.get() < sequence.get());
+        System.out.printf("%,d entries, %,d rollbacks\n", sequence.get(), rollbackCount.get());
+    }
+
+    private void doConcurrentTransaction(final TimelyResource<TestVersion> tr, final Random random,
+            final AtomicInteger sequence, final AtomicInteger rollbackCount) throws PersistitException {
+        try {
+            final Transaction txn = _persistit.getTransaction();
+            for (int i = 0; i < 25; i++) {
+                txn.begin();
+                try {
+                    final int id = sequence.incrementAndGet();
+                    tr.addVersion(new TestVersion(id, this), txn);
+                    final int delay = (1 << random.nextInt(3));
+                    // Up to 7/1000 of a second
+                    Util.sleep(delay);
+                    final TestVersion mine = tr.getVersion();
+                    assertEquals("Should not have been pruned yet", 0, mine._pruned.get());
+                    assertEquals("Wrong resource", id, mine._id);
+                    if (random.nextInt(10) == 0) {
+                        txn.rollback();
+                    } else {
+                        txn.commit();
+                    }
+                } catch (final RollbackException e) {
+                    txn.rollback();
+                    rollbackCount.incrementAndGet();
+                } finally {
+                    txn.end();
+                }
+            }
+        } catch (final RollbackException e) {
+            rollbackCount.incrementAndGet();
+        }
+    }
+
+    @Test
+    public void deleteResource() throws Exception {
+        final TimelyResource<TestVersion> tr = new TimelyResource<TestVersion>(_persistit);
+        _idCounter = 0;
+        final VersionCreator<TestVersion> creator = new VersionCreator<TestVersion>() {
+
+            @Override
+            public TestVersion createVersion(final TimelyResource<? extends TestVersion> resource)
+                    throws PersistitException {
+                return new TestVersion(++_idCounter, TimelyResourceTest.this);
+            }
+        };
+        final Transaction txn1 = _persistit.getTransaction();
+        _persistit.setSessionId(new SessionId());
+        final Transaction txn2 = _persistit.getTransaction();
+        TestVersion v1;
+        txn1.begin();
+        v1 = tr.getVersion(creator);
+        assertTrue("Version ID mismatch", v1._id == _idCounter);
+        txn2.begin();
+        txn1.incrementStep();
+        tr.delete();
+        tr.prune();
+        assertEquals("Should still be two versions", 2, tr.getVersionCount());
+        txn2.commit();
+        txn1.commit();
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        tr.prune();
+        assertEquals("Should now have no versions", 0, tr.getVersionCount());
+        txn1.end();
+        txn2.end();
+
+    }
+
+    @Test
+    public void versions() throws Exception {
+        final TimelyResource<TestVersion> tr = new TimelyResource<TestVersion>(_persistit);
+        _idCounter = 0;
+        final VersionCreator<TestVersion> creator = new VersionCreator<TestVersion>() {
+
+            @Override
+            public TestVersion createVersion(final TimelyResource<? extends TestVersion> resource)
+                    throws PersistitException {
+                return new TestVersion(++_idCounter, TimelyResourceTest.this);
+            }
+        };
+        final Semaphore semaphore1 = new Semaphore(0);
+        final Transaction txn = _persistit.getTransaction();
+        final Thread[] threads = new Thread[10];
+        for (int i = 0; i < 10; i++) {
+            try {
+                txn.begin();
+                tr.addVersion(creator.createVersion(tr), txn);
+                txn.commit();
+            } finally {
+                txn.end();
+            }
+            final Semaphore semaphore2 = new Semaphore(0);
+            threads[i] = new Thread(new Runnable() {
+                @Override
+                public void run() {
+                    final Transaction txn = _persistit.getTransaction();
+                    try {
+                        txn.begin();
+                        final TestVersion t = tr.getVersion();
+                        assertEquals(t._id, _idCounter);
+                        semaphore2.release();
+                        semaphore1.acquire();
+                        txn.commit();
+                    } catch (final Exception e) {
+                        e.printStackTrace();
+                    } finally {
+                        txn.end();
+                    }
+                }
+            });
+            threads[i].start();
+            semaphore2.acquire();
+        }
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        tr.prune();
+        assertEquals(10, tr.getVersionCount());
+        semaphore1.release(10);
+        for (final Thread thread : threads) {
+            thread.join();
+        }
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        tr.prune();
+        assertEquals(1, tr.getVersionCount());
+        assertEquals("Surviving primordial version should be last one committed", 10, tr.getVersion(null)._id);
+    }
+
+}

=== modified file 'src/test/java/com/persistit/TreeLifetimeTest.java'
--- src/test/java/com/persistit/TreeLifetimeTest.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/TreeLifetimeTest.java	2013-04-29 21:38:25 +0000
@@ -15,20 +15,6 @@
 
 package com.persistit;
 
-import static com.persistit.util.SequencerConstants.TREE_CREATE_REMOVE_A;
-import static com.persistit.util.SequencerConstants.TREE_CREATE_REMOVE_B;
-import static com.persistit.util.SequencerConstants.TREE_CREATE_REMOVE_C;
-import static com.persistit.util.SequencerConstants.TREE_CREATE_REMOVE_SCHEDULE;
-import static com.persistit.util.ThreadSequencer.addSchedules;
-import static com.persistit.util.ThreadSequencer.array;
-import static com.persistit.util.ThreadSequencer.describeHistory;
-import static com.persistit.util.ThreadSequencer.describePartialOrdering;
-import static com.persistit.util.ThreadSequencer.disableSequencer;
-import static com.persistit.util.ThreadSequencer.enableSequencer;
-import static com.persistit.util.ThreadSequencer.historyMeetsPartialOrdering;
-import static com.persistit.util.ThreadSequencer.out;
-import static com.persistit.util.ThreadSequencer.rawSequenceHistoryCopy;
-import static com.persistit.util.ThreadSequencer.sequence;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
@@ -38,7 +24,6 @@
 
 import java.util.Arrays;
 import java.util.List;
-import java.util.concurrent.ConcurrentLinkedQueue;
 
 import org.junit.Test;
 
@@ -49,9 +34,6 @@
 
 public class TreeLifetimeTest extends PersistitUnitTestCase {
     private static final String TREE_NAME = "tree_one";
-    final int A = TREE_CREATE_REMOVE_A;
-    final int B = TREE_CREATE_REMOVE_B;
-    final int C = TREE_CREATE_REMOVE_C;
 
     private Volume getVolume() {
         return _persistit.getVolume(UnitTestProperties.VOLUME_NAME);
@@ -62,11 +44,34 @@
     }
 
     @Test
-    public void testRemovedTreeGoesToGarbageChain() throws PersistitException {
+    public void testRemovedTreeGoesToGarbageChainNoTxn() throws PersistitException {
+        Exchange ex = getExchange(true);
+        for (int i = 0; i < 5; ++i) {
+            ex.clear().append(i).getValue().clear().put(i);
+            ex.store();
+        }
+        _persistit.releaseExchange(ex);
+        ex = null;
+
+        ex = getExchange(false);
+        final long treeRoot = ex.getTree().getRootPageAddr();
+        ex.removeTree();
+        _persistit.releaseExchange(ex);
+        ex = null;
+        _persistit.cleanup();
+
+        final List<Long> garbage = getVolume().getStructure().getGarbageList();
+        assertTrue("Expected tree root <" + treeRoot + "> in garbage list <" + garbage.toString() + ">",
+                garbage.contains(treeRoot));
+    }
+
+    @Test
+    public void testRemovedTreeGoesToGarbageChainTxn() throws PersistitException {
         final Transaction txn = _persistit.getTransaction();
+        Exchange ex;
 
         txn.begin();
-        Exchange ex = getExchange(true);
+        ex = getExchange(true);
         for (int i = 0; i < 5; ++i) {
             ex.clear().append(i).getValue().clear().put(i);
             ex.store();
@@ -84,7 +89,7 @@
         txn.end();
         _persistit.releaseExchange(ex);
         ex = null;
-
+        _persistit.cleanup();
         final List<Long> garbage = getVolume().getStructure().getGarbageList();
         assertTrue("Expected tree root <" + treeRoot + "> in garbage list <" + garbage.toString() + ">",
                 garbage.contains(treeRoot));
@@ -143,71 +148,4 @@
         assertNull("Tree should not exist after cleanup action", getVolume().getTree(TREE_NAME, false));
     }
 
-    @Test
-    public void testReanimatedTreeCreateAndRemoveSynchronization() throws PersistitException, InterruptedException {
-        enableSequencer(true);
-        addSchedules(TREE_CREATE_REMOVE_SCHEDULE);
-
-        final ConcurrentLinkedQueue<Throwable> threadErrors = new ConcurrentLinkedQueue<Throwable>();
-
-        final Exchange origEx = getExchange(true);
-        for (int i = 0; i < 5; ++i) {
-            origEx.clear().append(i).store();
-        }
-        _persistit.releaseExchange(origEx);
-
-        final Thread thread1 = new Thread(new Runnable() {
-            @Override
-            public void run() {
-                Exchange ex = null;
-                try {
-                    ex = getExchange(false);
-                    ex.removeTree();
-                } catch (final Throwable t) {
-                    threadErrors.add(t);
-                }
-                if (ex != null) {
-                    _persistit.releaseExchange(ex);
-                }
-            }
-        });
-
-        final Thread thread2 = new Thread(new Runnable() {
-            @Override
-            public void run() {
-                sequence(TREE_CREATE_REMOVE_B);
-                Exchange ex = null;
-                try {
-                    ex = getExchange(true);
-                    int count = 0;
-                    while (ex.next(true)) {
-                        ++count;
-                    }
-                    sequence(TREE_CREATE_REMOVE_C);
-                    assertEquals("New tree has zero keys in it", 0, count);
-                } catch (final Throwable t) {
-                    threadErrors.add(t);
-                }
-                if (ex != null) {
-                    _persistit.releaseExchange(ex);
-                }
-            }
-        });
-
-        thread1.start();
-        thread2.start();
-
-        thread1.join();
-        thread2.join();
-
-        assertEquals("Threads had no exceptions", "[]", threadErrors.toString());
-
-        final int[] actual = rawSequenceHistoryCopy();
-        final int[][] expectedSequence = { array(A, B), array(out(B)), array(C), array(out(A), out(C)) };
-        if (!historyMeetsPartialOrdering(actual, expectedSequence)) {
-            assertEquals("Unexpected sequencing", describePartialOrdering(expectedSequence), describeHistory(actual));
-        }
-
-        disableSequencer();
-    }
 }

=== added file 'src/test/java/com/persistit/TreeTransactionalLifetimeTest.java'
--- src/test/java/com/persistit/TreeTransactionalLifetimeTest.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/TreeTransactionalLifetimeTest.java	2013-04-29 21:38:25 +0000
@@ -0,0 +1,277 @@
+/**
+ * Copyright © 2013 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 com.persistit.unit.ConcurrentUtil.assertSuccess;
+import static com.persistit.unit.ConcurrentUtil.createThread;
+import static com.persistit.unit.ConcurrentUtil.join;
+import static com.persistit.unit.ConcurrentUtil.start;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Map;
+import java.util.concurrent.Semaphore;
+
+import org.junit.Test;
+
+import com.persistit.exception.PersistitException;
+import com.persistit.unit.ConcurrentUtil.ThrowingRunnable;
+
+public class TreeTransactionalLifetimeTest extends PersistitUnitTestCase {
+    final static int TIMEOUT_MS = 10000;
+
+    final Semaphore semA = new Semaphore(0);
+    final Semaphore semB = new Semaphore(0);
+    final Semaphore semT = new Semaphore(0);
+    final Semaphore semU = new Semaphore(0);
+
+    /*
+     * This class needs to be in com.persistit because of some package-private
+     * methods used in controlling the test.
+     */
+
+    private Tree tree(final String name) throws PersistitException {
+        return vstruc().getTree(name, false);
+    }
+
+    private Exchange exchange(final String name) throws PersistitException {
+        return _persistit.getExchange("persistit", name, true);
+    }
+
+    private VolumeStructure vstruc() {
+        return _persistit.getVolume("persistit").getStructure();
+    }
+
+    @Test
+    public void simplePruning() throws Exception {
+
+        final Transaction txn = _persistit.getTransaction();
+        for (int i = 0; i < 2; i++) {
+            txn.begin();
+            final Exchange ex = exchange("ttlt");
+            ex.getValue().put(RED_FOX);
+            ex.to(1).store();
+            ex.to(2).store();
+            txn.rollback();
+            txn.end();
+        }
+        _persistit.cleanup();
+        assertEquals("There should be no tree", null, tree("ttlt"));
+        assertTrue(vstruc().getGarbageRoot() != 0);
+    }
+
+    @Test
+    public void createdTreeIsNotVisibleUntilCommit() throws Exception {
+        final Thread t = createThread("ttlt", new TExec() {
+            @Override
+            void exec(final Transaction txn) throws Exception {
+                final Exchange ex1 = exchange("ttlt");
+                ex1.getValue().put(RED_FOX);
+                ex1.to(1).store();
+                semA.release();
+                semB.acquire();
+                txn.commit();
+            }
+        });
+        final Map<Thread, Throwable> errors = start(t);
+        semA.acquire();
+        assertEquals(null, _persistit.getVolume("persistit").getTree("ttlt", false));
+        semB.release();
+        join(TIMEOUT_MS, errors, t);
+        assertSuccess(errors);
+        final Exchange ex = exchange("ttlt");
+        assertTrue(ex.to(Key.BEFORE).next());
+        assertEquals(1, ex.getKey().decodeInt());
+    }
+
+    @Test
+    public void removeTreeIsNotVisibleUntilCommit() throws Exception {
+        final Exchange ex = exchange("ttlt");
+        ex.getValue().put(RED_FOX);
+        ex.to(1).store();
+        final Thread t = createThread("ttlt", new TExec() {
+            @Override
+            void exec(final Transaction txn) throws Exception {
+                final Exchange ex1 = exchange("ttlt");
+                ex1.removeTree();
+                semA.release();
+                semB.acquire();
+                txn.commit();
+            }
+        });
+        final Map<Thread, Throwable> errors = start(t);
+        semA.acquire();
+        assertEquals(ex.getTree(), ex.getVolume().getTree("ttlt", false));
+        semB.release();
+        join(TIMEOUT_MS, errors, t);
+        assertNull(ex.getVolume().getTree("ttlt", false));
+    }
+
+    @Test
+    public void removeCreateRemove() throws Exception {
+
+        final Exchange ex = exchange("ttlt");
+        ex.getValue().put(RED_FOX);
+        ex.to(1).store();
+        final Thread t = createThread("ttlt", new TExec() {
+            @Override
+            void exec(final Transaction txn) throws Exception {
+                final Exchange ex1 = exchange("ttlt");
+                ex1.removeTree();
+                final Exchange ex2 = exchange("ttlt");
+                ex2.getValue().put(RED_FOX);
+                ex2.to(2).store();
+                ex2.removeTree();
+                final Exchange ex3 = exchange("ttlt");
+                ex3.getValue().put(RED_FOX);
+                ex3.to(3).store();
+                final Exchange ex4 = exchange("ttlt");
+                ex4.to(Key.BEFORE);
+                assertTrue(ex4.next());
+                assertEquals(3, ex4.getKey().decodeInt());
+                assertTrue(!ex4.next());
+                semA.release();
+                semB.acquire();
+                txn.rollback();
+            }
+        });
+        final Map<Thread, Throwable> errors = start(t);
+        semA.acquire();
+        assertEquals(ex.getTree(), ex.getVolume().getTree("ttlt", false));
+        semB.release();
+        join(TIMEOUT_MS, errors, t);
+        _persistit.getTransactionIndex().updateActiveTransactionCache();
+        _persistit.pruneTimelyResources();
+        assertTrue(ex.to(Key.BEFORE).next());
+        assertEquals(1, ex.getKey().decodeInt());
+        assertTrue(!ex.next());
+        assertTrue(ex.getVolume().getStructure().getGarbageRoot() != 0);
+    }
+
+    @Test
+    public void createRemoveByStep() throws Exception {
+        createRemoveByStepHelper("ttlt1", false, true, false, false, "0,1:,2:a=step2,3,4:b=step4", "0:b=step4");
+        createRemoveByStepHelper("ttlt2", false, false, false, false, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt3", true, true, false, false, "0:,1:,2:a=step2,3,4:b=step4", "0:b=step4");
+        createRemoveByStepHelper("ttlt4", true, false, false, false, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+
+        createRemoveByStepHelper("ttlt5", false, true, false, true, "0,1:,2:a=step2,3,4:b=step4", "0:b=step4");
+        createRemoveByStepHelper("ttlt6", false, false, false, true, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt7", true, true, false, true, "0:,1:,2:a=step2,3,4:b=step4", "0:b=step4");
+        createRemoveByStepHelper("ttlt8", true, false, false, true, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+
+        createRemoveByStepHelper("ttlt1cr", false, true, true, false, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt2cr", false, false, true, false, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt3cr", true, true, true, false, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+        createRemoveByStepHelper("ttlt4cr", true, false, false, false, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+
+        createRemoveByStepHelper("ttlt5cr", false, true, true, true, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt6cr", false, false, true, true, "0,1:,2:a=step2,3,4:b=step4", "0");
+        createRemoveByStepHelper("ttlt7cr", true, true, true, true, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+        createRemoveByStepHelper("ttlt8cr", true, false, true, true, "0:,1:,2:a=step2,3,4:b=step4", "0:");
+    }
+
+    private void createRemoveByStepHelper(final String treeName, final boolean primordial, final boolean commit,
+            final boolean crash, final boolean restart, final String expected1, final String expected2)
+            throws Exception {
+
+        final Transaction txn = _persistit.getTransaction();
+        final Volume volume = _persistit.getVolume("persistit");
+        if (primordial) {
+            volume.getTree(treeName, true);
+        }
+        txn.begin();
+        try {
+            txn.setStep(1);
+            volume.getTree(treeName, true);
+
+            txn.setStep(2);
+            final Exchange ex1 = exchange(treeName);
+            ex1.getValue().put("step2");
+            ex1.to("a").store();
+
+            txn.setStep(3);
+            ex1.removeTree();
+
+            txn.setStep(4);
+            final Exchange ex2 = exchange(treeName);
+            ex2.getValue().put("step4");
+            ex2.to("b").store();
+
+            assertEquals("Expected contents at steps", expected1, computeCreateRemoveState(treeName, 5));
+
+            if (crash) {
+                _persistit.checkpoint();
+                _persistit.crash();
+            } else {
+                if (commit) {
+                    txn.commit();
+                } else {
+                    txn.rollback();
+                }
+            }
+        } finally {
+            if (!crash) {
+                txn.end();
+            }
+        }
+        if (restart) {
+            _persistit.close();
+        }
+        if (crash || restart) {
+            _persistit = new Persistit(_config);
+            _persistit.initialize();
+        }
+        assertEquals("Expected contents at steps", expected2, computeCreateRemoveState(treeName, 1));
+    }
+
+    private String computeCreateRemoveState(final String treeName, final int steps) throws PersistitException {
+        final StringBuilder sb = new StringBuilder();
+        for (int step = 0; step < steps; step++) {
+            _persistit.getTransaction().setStep(step);
+            if (sb.length() > 0) {
+                sb.append(",");
+            }
+            sb.append(step);
+            if (_persistit.getVolume("persistit").getTree(treeName, false) != null) {
+                sb.append(":");
+                final Exchange ex = exchange(treeName);
+                ex.append(Key.BEFORE);
+                while (ex.next()) {
+                    sb.append(ex.getKey().decodeString()).append("=").append(ex.getValue().getString());
+                }
+            }
+        }
+        return sb.toString();
+    }
+
+    abstract class TExec extends ThrowingRunnable {
+
+        @Override
+        public void run() throws Exception {
+            final Transaction txn = _persistit.getTransaction();
+            txn.begin();
+            try {
+                exec(txn);
+            } finally {
+                txn.end();
+            }
+        }
+
+        abstract void exec(final Transaction txn) throws Exception;
+    }
+}

=== modified file 'src/test/java/com/persistit/unit/ConcurrentUtil.java'
--- src/test/java/com/persistit/unit/ConcurrentUtil.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/unit/ConcurrentUtil.java	2013-04-29 21:38:25 +0000
@@ -21,11 +21,49 @@
 import java.util.HashMap;
 import java.util.Map;
 
+/**
+ * Helper methods to create, start, join and check error status of test threads.
+ * The key element is a Map<Thread, Throwable> the can be checked after threads
+ * run for unhandled exceptions. The {@link #assertSuccess(Map)} method is
+ * called in the main thread to aggregate and report all exceptions that
+ * occurred in other threads.
+ */
 public class ConcurrentUtil {
+
+    /**
+     * An implementation of {@link Thread.UncaughtExceptionHandler} which
+     * records any uncaught errors or exceptions in a map. A test case can pass
+     * the map to the {@link ConcurrentUtil#assertSuccess(Map)} method verify
+     * that no exceptions or errors were caught on test threads.
+     * 
+     */
+    public static class UncaughtExceptionHandler implements Thread.UncaughtExceptionHandler {
+        final Map<Thread, Throwable> throwableMap = Collections.synchronizedMap(new HashMap<Thread, Throwable>());
+
+        @Override
+        public void uncaughtException(final Thread t, final Throwable e) {
+            throwableMap.put(t, e);
+        }
+
+        public Map<Thread, Throwable> getThrowableMap() {
+            return throwableMap;
+        }
+    }
+
+    /**
+     * A version of Runnable in which the #run method throws Exception.
+     */
     public static abstract class ThrowingRunnable {
         public abstract void run() throws Throwable;
     }
 
+    /**
+     * Create a named thread from a ThrowableRunnable.
+     * 
+     * @param name
+     * @param runnable
+     * @return
+     */
     public static Thread createThread(final String name, final ThrowingRunnable runnable) {
         return new Thread(new Runnable() {
             @Override
@@ -40,34 +78,49 @@
     }
 
     /**
-     * Start and join on all given threads. Wait on each thread, individually,
-     * for <code>timeout</code> milliseconds. The {@link Thread#join(long)}
-     * method is used for this (<code>0</code> means indefinite).
+     * Start all given threads. Return a map on which unhandled exceptions will
+     * be reported.
      * 
-     * @param timeout
-     *            How long to join on each thread for.
      * @param threads
-     *            Threads to start and join.
+     *            Threads to start.
      * 
      * @return A map with an entry for each thread that had an unhandled
      *         exception or did not complete in the allotted time. This map will
      *         be empty if all threads completed successfully.
      */
-    public static Map<Thread, Throwable> startAndJoin(final long timeout, final Thread... threads) {
-        final Map<Thread, Throwable> throwableMap = Collections.synchronizedMap(new HashMap<Thread, Throwable>());
-
-        final Thread.UncaughtExceptionHandler handler = new Thread.UncaughtExceptionHandler() {
-            @Override
-            public void uncaughtException(final Thread t, final Throwable e) {
-                throwableMap.put(t, e);
-            }
-        };
-
+    public static Map<Thread, Throwable> start(final Thread... threads) {
+        final UncaughtExceptionHandler handler = new UncaughtExceptionHandler();
+        start(handler, threads);
+        return handler.getThrowableMap();
+    }
+
+    /**
+     * Start all given threads with the supplied UncaughtExceptionHandler. The
+     * handler will record any uncaught exceptions or errors in a map associated
+     * with the handler.
+     * 
+     * @param handler
+     * @param threads
+     */
+    public static void start(final UncaughtExceptionHandler handler, final Thread... threads) {
         for (final Thread t : threads) {
             t.setUncaughtExceptionHandler(handler);
             t.start();
         }
 
+    }
+
+    /**
+     * Wait on each thread, individually, for <code>timeout</code> milliseconds.
+     * The {@link Thread#join(long)} method is used for this (<code>0</code>
+     * means indefinite). Add an Exception to the error map for any thread that
+     * did not end within its timeout.
+     * 
+     * @param timeout
+     * @param throwableMap
+     * @param threads
+     */
+    public static void join(final long timeout, final Map<Thread, Throwable> throwableMap, final Thread... threads) {
         for (final Thread t : threads) {
             Throwable error = null;
             try {
@@ -78,12 +131,42 @@
             } catch (final InterruptedException e) {
                 error = e;
             }
-
             if (error != null) {
                 throwableMap.put(t, error);
             }
         }
-
+    }
+
+    /**
+     * Assert that no thread had any unhandled exceptions or timeouts.
+     * 
+     * @param throwableMap
+     *            map in which threads accumulated any unhandled Exceptions
+     */
+    public static void assertSuccess(final Map<Thread, Throwable> throwableMap) {
+        String description = "";
+        for (final Map.Entry<Thread, Throwable> entry : throwableMap.entrySet()) {
+            description += " " + entry.getKey().getName() + "=" + entry.getValue().toString();
+        }
+        assertEquals("All threads completed successfully", "{}", "{" + description + "}");
+    }
+
+    /**
+     * Call {@link #start(Thread...)} for all threads and then
+     * {@link #join(long, Map, Thread...)} for all threads.
+     * 
+     * @param timeout
+     *            How long to join on each thread for.
+     * @param threads
+     *            Threads to start and join.
+     * 
+     * @return A map with an entry for each thread that had an unhandled
+     *         exception or did not complete in the allotted time. This map will
+     *         be empty if all threads completed successfully.
+     */
+    public static Map<Thread, Throwable> startAndJoin(final long timeout, final Thread... threads) {
+        final Map<Thread, Throwable> throwableMap = start(threads);
+        join(timeout, throwableMap, threads);
         return throwableMap;
     }
 
@@ -98,11 +181,7 @@
      *            Threads to start and join.
      */
     public static void startAndJoinAssertSuccess(final long timeout, final Thread... threads) {
-        final Map<Thread, Throwable> errors = startAndJoin(timeout, threads);
-        String description = "";
-        for (final Map.Entry<Thread, Throwable> entry : errors.entrySet()) {
-            description += " " + entry.getKey().getName() + "=" + entry.getValue().toString();
-        }
-        assertEquals("All threads completed successfully", "{}", "{" + description + "}");
+        final Map<Thread, Throwable> throwableMap = startAndJoin(timeout, threads);
+        assertSuccess(throwableMap);
     }
 }

=== modified file 'src/test/java/com/persistit/unit/TransactionTest1.java'
--- src/test/java/com/persistit/unit/TransactionTest1.java	2012-08-24 13:57:19 +0000
+++ src/test/java/com/persistit/unit/TransactionTest1.java	2013-04-29 21:38:25 +0000
@@ -88,7 +88,7 @@
         } finally {
             txn.end();
         }
-        assertTrue(!ex.getTree().isValid());
+        assertTrue(ex.getTree().isDeleted());
         try {
             ex.clear().append("test1").hasChildren();
             fail("Should have thrown an exception");