Range Locking: explore other data structures

MDEV-21574 didn't succeed in improving performance of range locking.

This task is to look at other data structures with similar properties to lock tree.

I was able to find B-Trees and Skip Lists.

Bronson's tree

It doesn't have an established name so I'm calling it "Bronson tree".

A widely-cited paper: https://stanford-ppl.github.io/website/papers/ppopp207-bronson.pdf
Slides: https://ppl.stanford.edu/papers/ppopp207-bronson-slides.pdf
Research implementation in Java: https://github.com/nbronson/snaptree

It is

• Based on AVL tree, too.
• Uses lock-free traversals (going from parent to child is done with
  read+validate in the same way Toku's tree uses parent-child mutexes)
• Employs "routing nodes" - a deleted node may remain in the tree for a while
  if it was not convenient to remove it right away
• does local re-balances

(There is a re-implementation in C https://github.com/LPD-EPFL/ASCYLIB/tree/master/src/bst-bronson . It seems to be of prototype-level quality)

Other trees

There are papers mentioning other kinds of concurrent trees.

• This paper from 2017: https://arxiv.org/pdf/1702.04441.pdf
• Or this one from 2015 https://dl.acm.org/doi/10.1145/2688500.2688551

But it seems none of them have ended up in a production-ready library. Also, the language they use is typically Java

Skip List

(RocksDB's SkipList doesn't have a remove operation and so cannot be used)

The most referenced-to seems to be
http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/OPODIS2006-BA.pdf

and folly/ConcurrentSkipList implements it:
https://github.com/facebook/folly/blob/master/folly/ConcurrentSkipList.h

It does support node removal:

Features:

  4. Lazy removal with GC support.  The removed nodes get deleted when

     the last Accessor to the skiplist is destroyed.

Caveats:

  6. Freed nodes will not be reclaimed as long as there are ongoing

     uses of the list.

But the "Caveat" is there. A test program with N threads that keep adding/removing elements will have its memory usage grow, with no apparent limits.

if I make all threads to pause for a bit, this seems to give it a chance to reclaim memory. Mem usage stops growing for a while (while freed memory is reused) then starts growing again.

Another issue: folly/ConcurrentSkipList requires strict ordering of elements that are stored. One needs to define std::less<Element>. Ranges can overlap. I'm not sure if it is valid to assume overlapping ranges equal.