Scaling concurrent queues by using HTM to profit from failed atomic operations

Abstract

Queues are fundamental concurrent data structures, but despite years of research, even the state-of-the-art queues scale poorly. This poor scalability occurs because of contended atomic read-modify-write (RMW) operations.

This paper makes a first step towards designing a scalable linearizable queue. We leverage hardware transactional memory (HTM) to design TxCAS, a scalable compare-and-set (CAS) primitive---despite HTM being targeted mainly at uncontended scenarios.

Leveraging TxCAS's scalability requires a queue design that does not blindly retry failed CASs. We thus apply TxCAS to the baskets queue, which steers enqueuers whose CAS fails into dedicated basket data structures. Coupled with a new, scalable basket algorithm, we obtain SBQ, the scalable baskets queue. At high concurrency levels, SBQ outperforms the fastest queue today by 1.6X on a producer-only workload.

BibTeX

@inproceedings{Ostrovsky-Morrison:PPOPP20,
  author    = {Or Ostrovsky and
               Adam Morrison},
  title     = {Scaling concurrent queues by using {HTM} to profit from failed atomic operations},
  booktitle = {PPoPP},
  pages     = {89--101},
  publisher = {{ACM}},
  year      = {2020},
}

Scaling concurrent queues by using HTM to profit from failed atomic operations

Abstract

Related papers