jm + lock-free   7

_Building a Bw-Tree Takes More Than Just Buzz Words_, SIGMOD 2018
'An account of our disappointing journey to build a open-source lock-free Bw-Tree for the Peloton DBMS.'

'In 2013, Microsoft Research proposed the Bw-Tree (humorously
termed the “Buzz Word Tree”), a lock-free index that provides high
throughput for transactional database workloads in SQL Server’s
Hekaton engine. The Bw-Tree avoids locks by appending delta
record to tree nodes and using an indirection layer that allows it to
atomically update physical pointers using compare-and-swap (CaS).
Correctly implementing this techniques requires careful attention
to detail. Unfortunately, the Bw-Tree papers from Microsoft are
missing important details and the source code has not been released.

This paper has two contributions: First, it is the missing guide
for how to build a lock-free Bw-Tree. We clarify missing points in
Microsoft’s original design documents and then present techniques
to improve the index’s performance. Although our focus here is on
the Bw-Tree, many of our methods apply more broadly to designing
and implementing future lock-free in-memory data structures. Our
experimental evaluation shows that our optimized variant achieves
1.1–2.5× better performance than the original Microsoft proposal
for highly concurrent workloads. Second, our evaluation shows
that despite our improvements, the Bw-Tree still does not perform
as well as other concurrent data structures that use locks.'

Finally: :

'Our results show that @ViktorLeis's ART index and @xexd's MassTree and a non-fancy B+Tree are currently the best for in-memory workloads. Skip Lists are always terrible.'
skip-lists  algorithms  data-structures  storage  bw-trees  mass-trees  benchmarks  performance  multithreading  lock-free  locking  trees 
5 weeks ago by jm
Java Concurrency Tools for the JVM. This project aims to offer some concurrent data structures currently missing from the JDK:

Bounded lock free queues
SPSC/MPSC/SPMC/MPMC variations for concurrent queues
Alternative interfaces for queues (experimental)
Offheap concurrent ring buffer for ITC/IPC purposes (experimental)
Executor (planned)
concurrency  lock-free  data-structures  queues  jvm  java 
january 2015 by jm
Lock-Based vs Lock-Free Concurrent Algorithms
An excellent post from Martin Thompson showing a new JSR166 concurrency primitive, StampedLock, compared against a number of alternatives in a simple microbenchmark.
The most interesting thing for me is how much the lock-free, AtomicReference.compareAndSet()-based approach blows away all the lock-based approaches -- even in the 1-reader-1-writer case. Its code is extremely simple, too:
concurrency  java  threads  lock-free  locking  compare-and-set  cas  atomic  jsr166  microbenchmarks  performance 
august 2013 by jm
Single Producer/Consumer lock free Queue step by step
great dissection of Martin "Disruptor" Thompson's lock-free single-producer/single-consumer queue data structure, with benchmark results showing crazy speedups. This is particularly useful since it's a data structure that can be used to provide good lock-free speedups without adopting the entire Disruptor design pattern.
disruptor  coding  java  jvm  martin-thompson  lock-free  volatile  atomic  queue  data-structures 
march 2013 by jm
InfoQ: Lock-free Algorithms
Michael Barker and Martin Thompson's talk at the last QCon on the LMAX Disruptor, and other nifty lock-free techniques and patterns. 'Martin Thompson and Michael Barker explain how Intel x86_64 processors and their memory model work, along with low-level techniques that help creating lock-free software.'
lock-free  locking  mutexes  algorithms  lmax  disruptor  infoq  slides  presentations  qcon  java 
april 2012 by jm

Copy this bookmark: