TL;DR
This paper introduces Optimized Shadow Paging (OSP), a novel technique to significantly reduce the overhead of writing data to byte-addressable non-volatile memory (BNVM) for transactional consistency. By leveraging cache-line level mappings and virtual memory indirection, OSP achieves up to 1.96x fewer writes compared to traditional undo-logging, making BNVM more practical for persistent data structures.
What Problem Does This Paper Address?
Byte-addressable non-volatile memory (BNVM) promises the speed of DRAM with the persistence of storage, enabling simpler and more efficient application development. However, ensuring data integrity after unexpected system shutdowns (crashes) is a major challenge. Traditional methods like logging and shadow paging, used to guarantee consistency, impose significant performance and energy overhead due to the need to write extra data to BNVM. This overhead, especially the cost of persisting data to BNVM, hinders the widespread adoption of BNVM.
Methods
The core innovation is Optimized Shadow Paging (OSP). Unlike traditional shadow paging that operates at the granularity of memory pages (typically 4-8KB), OSP provides fine-grained persistence at the cache-line level.
Here's how it works:
- Cache-Line Level Mappings: OSP uses two physical pages (PO and P1) for each virtual page. Within these pages, it maintains two bitmaps: a "committed bitmap" and an "updated bitmap." These bitmaps track the state of individual cache lines.
- Virtual Memory Indirection: OSP leverages virtual memory indirection. When a transaction updates a cache line, the write goes to one of the physical pages (determined by the bitmaps), and the "updated bitmap" is set. Reads are directed to the correct version (either the committed or the updated one) based on these bitmaps.
- Optimized Commit: During a commit, the "updated bitmap" is XORed into the "committed bitmap," and the "updated bitmap" is cleared. This atomically updates the persistent state.
- Page Consolidation: To avoid wasting memory, virtual pages that are no longer actively accessed are consolidated into a single physical page, freeing up the other. This is done lazily, typically upon TLB eviction.
- Atomicity for Multi-Page Transactions: For transactions spanning multiple pages, OSP uses either lightweight journaling (recording changes to the consistent state table) or "super pages" (a dedicated page to store the consistent state table) to ensure atomicity. The paper focuses on lightweight journaling.
OSP's key advantage is avoiding the need to copy entire data pages or log actual data, significantly reducing BNVM writes.
Datasets
Not discussed in the paper. The evaluation uses simulated workloads.
Key Insights and Ideas
- Cache-line granularity is key: The paper demonstrates that operating at the cache-line level, rather than the page level, is crucial for significantly reducing BNVM write overhead. This is because typical transactions modify only a small fraction of a page.
- Virtual memory indirection is powerful: OSP effectively reuses the existing virtual memory infrastructure to manage data versions, avoiding the need for separate logging areas and complex address remapping.
- OSP is hardware-friendly: The proposed mechanisms are simple and require minimal changes to hardware (e.g., extended TLB entries), suggesting it can be implemented efficiently.
- Trade-offs are manageable: While OSP might slightly increase TLB size or require a separate hardware unit, this overhead is considered acceptable compared to the performance gains. Page consolidation addresses the potential memory waste of maintaining two pages per virtual page.
Key Results
The paper presents preliminary simulation results comparing OSP to a hardware undo-logging approach.
- Reduced CPU Flushes: OSP reduces overall CPU flushes (which represent writes to persist data) by an average of 1.6x and up to 1.96x compared to undo-logging.
- Locality Matters: The performance benefits are most pronounced for workloads with good spatial and temporal locality. For workloads with poor locality, OSP still performs comparably to logging but eliminates most of the storage consistency cost for well-localized workloads.
- Minimal Overhead for Journaling/Consolidation: The overhead from journaling and page consolidation is shown to be manageable, especially when compared to the cost of persisting actual data in undo-logging.
Limitations and Future Work
- Virtually-Addressed Caches: The current OSP approach works best with physically-addressed caches. The authors acknowledge that supporting virtually-addressed caches is an area for future exploration.
- TLB Shootdown: Managing transactions that don't fit within the TLB and handling TLB shootdowns efficiently are identified as future work.
- Hardware Transactional Memory (HTM) Integration: The authors plan to investigate integrating OSP with HTM to provide general, ACID transactions, leveraging OSP's efficient rollback capabilities.
- Asynchronous Page Consolidation: Exploring asynchronous page consolidation to further minimize its impact on performance is also on the roadmap.
Summary updated