2

I've been using this implementation of B Plus Tree for some time. I've noticed that the 'Recent' cache is buggy. Here's how the bug is produced:

  1. I add some KVPs, and commit the tree.
  2. I add some more KVPs and rollback the tree.
  3. I add some more KVPs and commit the tree.
  4. I restart my application and repeat step 1,2 and 3

The tree throws an InvalidNodeHandleException when executing step 3 after the restart, which comes exactly 

at CSharpTest.Net.Collections.BPlusTree`2.NodeCacheNormal.Lock(NodePin parent, LockType ltype, NodeHandle child)
at CSharpTest.Net.Collections.BPlusTree`2.RootLock..ctor(BPlusTree`2 tree, LockType type, Boolean exclusiveTreeAccess, String methodName)
at CSharpTest.Net.Collections.BPlusTree`2.LockRoot(LockType ltype, String methodName)

The following assertion fails.

InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer)
                                                    && node != null
                                                    && node.StorageHandle.Equals(entry.Handle.StoreHandle));

Because the StorageHandle equality returns false, which in turn happens because the Unique of the two root Storage Handles are different, and not just incremental different, they are two different randoms. The root of the problem is the behavior of NodeCacheNormal.

After creation of the tree in the first run, when the tree is loaded in the second execution for the first time, it is done through the LoadStorage() call, which simply sets the _root.Node to the RootNode read from the storage. This read RootNode contains the Unique of the last execution time which was committed to the disk and is never compared with the Unique of the new Root Handle created in this execution until the tree rollbacks.

The rollback causes the cache to clear, thereby causing the RootNode in the cache to be cleared off. After rollback, if the RootNode is accessed again, it is fetched from the store and inserted in to cache except this time, its done through the main NodePin Lock(NodePin parent, LockType ltype, NodeHandle child) call which checks for the equality of handles in the above call.

Are there any known fixes for this? The cache is pretty baked into the implementation, and I can't exactly find a good workaround to this.

Edit 1:

Here's a class to produce the bug:

 public class TreeBugTest
    {
        private BPlusTree<long, long> _tree;

        public TreeBugTest()
        {
            var options = new BPlusTree<long, long>.OptionsV2(new PrimitiveSerializer(), new PrimitiveSerializer());
            options.BTreeOrder = 4;
            options.CachePolicy = CachePolicy.Recent;
            options.CallLevelLock = new SimpleReadWriteLocking();
            options.FileName = ConfigurationSettings.AppSettings["Path"];
            options.CreateFile = CreatePolicy.IfNeeded;
            options.StorageType = StorageType.Disk;
            options.LockingFactory = new LockFactory<WriterOnlyLocking>();
            options.StoragePerformance = StoragePerformance.Default;
            _tree = new BPlusTree<long, long>(options);
        }

        public void AddSomeData(long start, long end)
        {
            while (start <= end)
            {
                _tree.Add(start, start++);
            }
        }

        public void ProduceBug()
        {
            AddSomeData(1, 1000);
            _tree.Commit();
            AddSomeData(1001,2000);
            _tree.Rollback();
            AddSomeData(2001, 3000); //This is where it occurs
            _tree.Commit();
        }
    }

Just provide a filepath, create its instance and call the ProduceBug() method.

Usman Shahid
  • 101
  • 2
  • 5

1 Answers1

0

Okay, so apparently the code is buggy. The handle comparison needs to be skipped for newly created root node. For this, I moved the logic of Lock method to a private LockInternal method with signature:

private NodePin LockInternal(NodePin parent, LockType ltype, NodeHandle child, bool ignoreHandleComparison)

and changed the statements:

InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer) && node != null && node.StorageHandle.Equals(entry.Handle.StoreHandle));

to:

InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer) && node != null && ignoreHandleComparison?true:node.StorageHandle.Equals(entry.Handle.StoreHandle));

And called this private LockInternal method from the original Lock method with a false for ignoreHandleComparison. The second place I modified was the LockRoot method where initially, I made the method virtual and in the override of NodeCacheNormal, I changed the call from Lock to LockInternal with a true for ignoreHandleComparison. And this worked for me.

I guess I'll make a pull request for this fix to the repository of the project.

Usman Shahid
  • 101
  • 2
  • 5