Safe Optimistic Lock Coupling | Hacker News Reader

Safe Optimistic Lock Coupling

databasearchitects.blogspot.com

51 pointsgreghn9 comments

This code seems broken, though. The big challenge with these kinds of lock-free parallel algorithms is always how to deal with lifetimes and prevent use-after-frees (unless you never want to free anything from this tree, which seems a bit unlikely).

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.

LeanStore found a very elegant solution to this: https://dl.acm.org/doi/abs/10.1145/3596225.3596228

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.

I think in the real world LeanStore doesn't do the the MADV_DONTNEED bit at all though because of performance concerns? Overhead is high (syscall cost, and frequent thrashing about in the kernel VM subsystem). If I recall the vmcache paper gets into this (Virtual-Memory Assisted Buffer Management, SIGMOD 2023). Lots of talk about TLB shootdowns and throughput concerns.

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.

That is a very cool idea. Maybe a bit annoying to use, as you need a fixed size (I think?) special purpose allocator, and having these span across a page boundary doesn't seem possible.

I definitely need to try this out, though.

Naive question, since this isn't my area of expertise, but Rust has RwLock: Why wouldn't one simply use RwLock to allow many readers and a single writer?

How does this approach outperform RwLock (for arbitrary interpretations of outperform) and how does RwLock outperform this approach (ditto)?

Typically, in a RwLock, once a Writer locks, Readers are blocked, until the Writer unlocks. Similarly, a Writer lock waits until all current Readers unlock too, so you get contention on both sides. RwLock only lets multiple concurrent Readers lock against themselves, but any mixture causes full locking.

In this article, the locks are mutually exclusive. Reads are not blocked by Writes, and vice-versa, but Writers would block against other Writers.

The downside is that Readers need to check which "version" of the data they read, to see if it was modified during the operation by a Writer--since Writers do not block for Readers like they do with RwLock.

It's elegant because, in most scenarios, Readers will not need to re-read because the version won't change mid-run between an optimistic read lock and its unlock. In the cases where that does happen, your code needs to handle retrying the read / loop logic, which is why the article argues for a compiler mechanism to enforce that check and avoid "foot gun" scenarios.

This sort of approach relies on it being safe to read torn updates, which technically is UB in C++

As someone else mentions, it's also difficult for anybody to free memory (which for many purposes is actually fine)

Well written, good content, doesn't try to sell random junk, +10 would read again :)

Great, well-written read.

Reply on news.ycombinator.com