NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems on FAST 2015.

Single-level storage is virtual memory system which hidden the physical locations of a pages. Whether the memory pages are in DRAM or disks is not important in this storage. The NVM-based Single Level Systems mentioned in this paper replace both DRAM and disks with non-volatile memory, such as phase-change memory (PCM) and spin-transfer torque memory (STT-RAM). The consistency problem is non-trivial in this type of system, because existing CPU and memory controller may reorder memory writes. Studies use CPU instructions, such as memory fence and cacheline, to manually control CPU cacheline flush. However, these operations cause huge write amplification when using existing approaches to keep B+ tree consistent.

The problem observed including:

1. keeping consistency causes a huge amplification of the CPU cacheline invalidation and flush, which increases the cache misses significantly.
2. the consistency cost due to flush mostly comes from flushing shifted entries in order to keep LN (critical data) sorted
3. not all the data needs to be consistent to keep the entire data structure consistent

Design Decisions

Selectively Enforce Data Consistency

all the data is stored in LNs, they can be considered as critical data while INs are reconstructable data because they can always be reconstructed from LNs at a reasonably low cost

The INs need not to be updated with a consistency guarantee because they can be reconstructed from LNs.

Keep Entries in LN unsorted

The write amplification is because of the need to shift entries upon updating an ordered data structure. This paper perform update in an atomic write and allowing parallelism of accessing LN.

Organizing IN in Cache-optimized Format

This is similar to the design of TPFTL. Memory pages is located by offset instead of pointers to reduce the memory consumption.