Paper Reading (2)

Posted on

NOVA

  • Conclusion:
    Adapts conventional log-structured file system techniques to exploit the fast random access that NVMs provide.

    • separate logs for each inode to improve concurrency
    • stores file data outside the log to minimize log size and reduce garbage collection costs
    • based on hardware-based NVMM emulator

  • NOVA’s logs provide metadata, data, and mmap atomicity and focus on simplicity and reliability, keeping complex metadata structures in DRAM to accelerate lookup operations

  • Contributes:

    1. It extends existing log-structured file system techniques to exploit the characteristics of hybrid memory systems.
    2. It describes atomic mmap, a simplified interface for exposing NVMM directly to applications with a strong consistency guarantee.
    3. It demonstrates that NOVA outperforms existing journaling, shadow paging, and log-structured file systems running on hybrid memory systems.
    4. It shows that NOVA provides these benefits across a range of proposed NVMM technologies.

  • Challenges:

    1. Performance: NVMM has lower latency -> Direct Access (DAX) avoids extra copy between NVMM and DRAM.
    2. Write Reordering: cache hierarchies (modern processor) -> reorder store operations -> do not guarantee when update will reach NVMMs.
      explicitly flushing caches and issuing memory barriers (fence) -> clflush instrument.
    3. Atomicity: POSIX-style file system require operations to be atomic (e.g. Rename) -> Disk only provides 8-byte atomic operation
      • three technologies to apply atomic: Journaling, Shadow Paging, Log-structuring

  • Three observations:

    1. Data structure which support fast search is hard to implement in NVMM
    2. Complexity if cleaning logs stems is unnecessary due to cheaper random access
    3. Using single log limits concurrency

  • Design Decisions:

    1. Keep logs in NVMM and indexes in DRAM (radix tree)
      • persistent log is simple and efficient
      • volatile tree structure has no consistency overhead
    2. Give each inode its own log: Allow concurrent updates across files without sync (high concurrency/scalability)
      • Per-CPU NVMM free list, journal and inode table
      • concurrent transactions and (de)allocation
    3. Use logging and lightweight journaling for complex atomic updates, making sure atomic
      • append data to logs
      • update the log tail to commit the updates (avoid duplicate writes)

    4. Implement the log as a singly linked list (4 KB NVMM pages)

      • allocate log space is easy
      • perform log cleaning at fine grained (Page level)
      • reclaiming log pages require a few pointer assignments

    5. Do not log file data

    6. Copy-on-write for file data
      • Log only contains meta-data
      • Log is short

  • Fast garbage collection

    • Log is a linked list and only contains meta-data -> fast GC deletes dead log pages from list (No copying)
    • Two different techs:
      1. Fast GC: deleting dead log page from linked list
      2. Through GC: valid log < 50% -> format a new log and atomically replace the old one -> only copy meta-data

NV-Tree

  • A consistent and cache-optimized B+Tree with reducing CPU cacheline flush

  • Motivations:

    • Keeping consistency causes a high amplification of the CPU cacheline invalidation and flush with increasing cache misses significantly
    • the consistency cost due to flush mostly comes from flushing shifted entries in order to keep LN sorted
    • not all the data needs to be consistent to keep the entire data structure consistent

  • Overview:

    • Design
      1. Selectively Enforce Data Consistency
      2. Keep Entries in LN Unsorted
      3. Organizing IN in Cache-optimized Format
    • IN - PLN - LN