  We consider durable data structures for non-volatile main memory, such as the
new Intel Optane memory architecture. Substantial recent work has concentrated
on making concurrent data structures durable with low overhead, by adding a
minimal number of blocking persist operations (i.e., flushes and fences). In
this work we show that focusing on minimizing the number of persist
instructions is important, but not enough. We show that access to flushed
content is of high cost due to cache invalidation in current architectures.
Given this finding, we present a design of the queue data structure that
properly takes care of minimizing blocking persist operations as well as
minimizing access to flushed content. The proposed design outperforms
state-of-the-art durable queues.
  We start by providing a durable version of the Michael Scott queue (MSQ). We
amend MSQ by adding a minimal number of persist instructions, fewer than in
available durable queues, and meeting the theoretical lower bound on the number
of blocking persist operations. We then proceed with a second amendment to this
design, that eliminates accesses to flushed data. Evaluation shows that the
second amendment yields substantial performance improvement, outperforming the
state of the art and demonstrating the importance of reduced accesses to
flushed content. The presented queues are durably linearizable and lock-free.
Finally, we discuss the theoretical optimal number of accesses to flushed
content.
