The fundamental problem is that nothing prevents a reader from dereferencing a node the writer has free()'d. Fixing this requires either adding RCU or Hazard pointers.
They don’t actually free the memory, but rather put it back into the memory pool with an incremented version counter. It can later be re-used as a new node, the version counter _not_ being reset.
In LeanStore’s use case they either way have a fixed amount of memory they’d like to use (since it’s a page buffer on top of disk data) so there’s no actual need to give the memory back to the OS.
If you’d like to actually free the memory back it’s a lot easier since you can now treat this more of an infrequent operation. The cost of that will be amortized very well.
EDIT: They also describe another very cool idea: If the memory is allocated with mmap you can deallocate it by using madvise DONT_NEED. This will cause the version counter to be “0” which you can interpret as “invalid”. You can then deallocate it at a later point when you’re absolutely sure no threads could access it. You’re basically doing a two-stage deallocation where the first stage releases the memory, but the page information is kept until the second stage.
In my own experiments I confirmed the same thing. Just using explicit free lists / allocator techniques was far more performant.
And actually-existing LeanStore on github doesn't use it, anyways. And strangely never has (looking through git history). Even though the paper (2018) describes it. Maybe Leis or Alhamsi can explain.
Curious if Umbra and the CedarDB stuff that came from it do use this approach, too. I seem to recall the Umbra talk speaks about using it.
As a lazy "eventually reclaim when I've got free cycles" technique maybe ok? But revealing that the actual LeanStore C++ code never does it.
I definitely need to try this out, though.