Hi, I found an issue with getChillren() function in line 103 of Tree.cpp inside lookupRange() of ARTOLC implementation.
|
N::getChildren(node, 0u, 255u, children, childrenCount); |
When it is directed to each specific node type, e.g.,
Node4, Node16, Node48, Node256, it checks if it needs to restart upon read-write conflicts.
When conflict is detected, it restarts locally, but this can cause an infinite loop when running with write operations.
The dynamic node adjustment replaces a node with a larger/smaller node, which marks the original obsolete and reclaimed. However, when running concurrent queries of range lookups with a mixture of write operations such as insert and remove, threads executing range queries keep trying locally to collect child pointers due to obsoleteness detection which will never succeed.
I think the getChildren() in each node type should either
- distinguish the write latch acquisition state and obsolete state, and when obsolete, retry from parent (may recursively backtrack up).
- abort upon conflicts, and retry globally (from the root).
Hi, I found an issue with
getChillren()function inline 103ofTree.cppinsidelookupRange()of ARTOLC implementation.ARTSynchronized/OptimisticLockCoupling/Tree.cpp
Line 103 in 849ef27
When it is directed to each specific node type, e.g.,
Node4, Node16, Node48, Node256, it checks if it needs to restart upon read-write conflicts.When conflict is detected, it restarts locally, but this can cause an infinite loop when running with write operations.
The dynamic node adjustment replaces a node with a larger/smaller node, which marks the original obsolete and reclaimed. However, when running concurrent queries of range lookups with a mixture of write operations such as insert and remove, threads executing range queries keep trying locally to collect child pointers due to obsoleteness detection which will never succeed.
I think the
getChildren()in each node type should either