我已经使用B Plus Tree的这种实现一段时间了。我注意到"最近"缓存有问题。以下是该错误的生成方式:
- 我添加了一些 KVP,并提交树。
- 我添加了更多的 KVP 并回滚树。
- 我添加了更多 KVP 并提交树。
- 我重新启动应用程序并重复步骤 1、2 和 3
该树在重新启动后执行步骤 3 时抛出 InvalidNodeHandleException,这恰好是
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)
以下断言失败。
InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer)
&& node != null
&& node.StorageHandle.Equals(entry.Handle.StoreHandle));
因为 StorageHandle 相等性返回 false,这反过来又是因为两个根存储句柄的Unique
不同,而不仅仅是增量不同,它们是两个不同的随机数。问题的根源是NodeCacheNormal
的行为。
在第一次运行中创建树后,当树首次在第二次执行中加载时,它是通过 LoadStorage()
调用完成的,该调用只是将_root.Node
设置为从存储中读取RootNode
。此读取RootNode
包含提交到磁盘的上次执行时间的Unique
,并且在树回滚之前,永远不会与此执行中创建的新根句柄的Unique
进行比较。
回滚会导致缓存清除,从而导致缓存中的根节点被清除。回滚后,如果再次访问 RootNode,则会从存储中获取它并将其插入到缓存中,但这次除外,它通过主NodePin Lock(NodePin parent, LockType ltype, NodeHandle child)
调用完成,该调用检查上述调用中句柄的相等性。
是否有任何已知的修复程序?缓存已经融入了实现中,我无法完全找到一个好的解决方法。
编辑 1:
下面是一个产生错误的类:
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();
}
}
只需提供一个文件路径,创建其实例并调用 ProduceBug()
方法。
好的,所以显然代码有问题。对于新创建的根节点,需要跳过句柄比较。为此,我将Lock
方法的逻辑移动到带有签名的私有LockInternal
方法:
private NodePin LockInternal(NodePin parent, LockType ltype, NodeHandle child, bool ignoreHandleComparison)
并更改了语句:
InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer) && node != null && node.StorageHandle.Equals(entry.Handle.StoreHandle));
自:
InvalidNodeHandleException.Assert(Storage.TryGetNode(child.StoreHandle, out node, NodeSerializer) && node != null && ignoreHandleComparison?true:node.StorageHandle.Equals(entry.Handle.StoreHandle));
并从原始的Lock
方法调用了这个私有LockInternal
方法,并带有用于ignoreHandleComparison
的false
。我修改的第二个地方是LockRoot
方法,最初,我将该方法设置为虚拟,并且在NodeCacheNormal
的覆盖中,我将调用从 Lock
更改为 LockInternal
,并带有ignoreHandleComparison
true
。这对我有用。
我想我会向项目的存储库提出此修复程序的拉取请求。