Problem)
Current implementation of range scan can read duplicated keys repeatedly in multi-threads environment and can return value buffer, unsorted by keys. The node scan mechanism of FAST_FAIR proposed in FAST'18 paper changes node scan direction only when insertion and deletion operations are switched each other during scanning. It is understood that this mechanism can correctly address exact matching query, but not for range scan. Please refer to below example.
Example)
"v" is scanner's pointer
Insertion 5, 6
Switch counter = 2 Switch counter = 2 Switch counter = 2
Scan buffer (10) Scan buffer (10, 6) Scan buffer (10, 6, 10)
v v v
(10, 20, 30, 40, 50) -----> (5, 6, 10, 20, 30, 40, 50) -----> (5, 6, 10, 20, 30, 40, 50)
Solution)
In current implementation, switch counter is only changed with odd or even number depending on whether insertion and deletion operations are switched or not. Our proposed solution is to constantly increase switch counter whenever insertion and deletion operations perform. If applying this solution, range scanner thread can realize that concurrent insertion or deletion is working in the same node, and then restart scanning with rolling back the increased buffer's index number.
Problem)
Current implementation of range scan can read duplicated keys repeatedly in multi-threads environment and can return value buffer, unsorted by keys. The node scan mechanism of FAST_FAIR proposed in FAST'18 paper changes node scan direction only when insertion and deletion operations are switched each other during scanning. It is understood that this mechanism can correctly address exact matching query, but not for range scan. Please refer to below example.
Example)
"v" is scanner's pointer
Solution)
In current implementation, switch counter is only changed with odd or even number depending on whether insertion and deletion operations are switched or not. Our proposed solution is to constantly increase switch counter whenever insertion and deletion operations perform. If applying this solution, range scanner thread can realize that concurrent insertion or deletion is working in the same node, and then restart scanning with rolling back the increased buffer's index number.