  Persistent Memory (PM) makes possible recoverable applications that can
preserve application progress across system reboots and power failures. Actual
recoverability requires careful ordering of cacheline flushes, currently done
in two extreme ways. On one hand, expert programmers have reasoned deeply about
consistency and durability to create applications centered on a single
custom-crafted durable datastructure. On the other hand, less-expert
programmers have used software transaction memory (STM) to make atomic one or
more updates, albeit at a significant performance cost due largely to ordered
log updates.
  In this work, we propose the middle ground of composable persistent
datastructures called Minimally Ordered Durable (MOD) datastructures. MOD is a
C++ library of several datastructures---currently, map, set, stack, queue and
vector--- that often perform better than STM and yet are relatively easy to
use. They allow multiple updates to one or more datastructures to be atomic
with respect to failure. Moreover, we provide a recipe to create more
recoverable datastructures.
  MOD is motivated by our analysis of real Intel Optane PM hardware showing
that allowing unordered, overlapping flushes significantly improves
performance. MOD reduces ordering by adapting existing techniques for
out-of-place updates (like shadow paging) with space-reducing structural
sharing (from functional programming). MOD exposes a Basic interface for single
updates and a Composition interface for atomically performing multiple updates.
Relative to the state-of-the-art Intel PMDK v1.5 STM, MOD improves map, set,
stack, queue microbenchmark performance by 40%, and speeds up application
benchmark performance by 38%.
