Optimistic Lock Coupling Scales Read-Heavy Trees Without the Usual Race Conditions
Safe Optimistic Lock Coupling
A binary tree with lock coupling suffers physical contention on the root lock, limiting scalability on many-core CPUs. Optimistic Lock Coupling lets readers avoid writes, but risks races if validation is forgotten. The author shows how to encode validation in the type system using unvalidated values and optimistic views, so the compiler enforces correctness. The result is near-lock-free read scalability with safe concurrent writes.
The compiler catches the mistakes that would otherwise become subtle race conditions at runtime.
- PeterWhittaker
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)?
- dichloromethane
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.
- windenntw
Well written, good content, doesn't try to sell random junk, +10 would read again :)