TL;DR
This paper introduces NVMOVE, a static analysis tool that automatically identifies persistent data structures in C programs. This significantly simplifies the challenging process of migrating applications from traditional block-based persistence to the more efficient byte-based persistence model enabled by Non-Volatile Memory (NVM). NVMOVE successfully identifies these types with high accuracy, enabling applications to leverage NVM for faster and more robust data persistence.
What Problem Does This Paper Address?
Modern applications typically persist data using a "block-based persistence" (BLP) model. This involves serializing in-memory data into a specific format and then writing it to block storage (like SSDs or HDDs) using system calls. While this approach is well-established, it suffers from several drawbacks:
- Serialization Overhead: Converting data structures to a serialized format and back is computationally expensive.
- Complexity and Bugs: Maintaining separate in-memory and on-disk data formats increases code complexity and is a common source of bugs.
- System Call Overhead: Frequent system calls to the kernel for I/O operations add latency.
The advent of Non-Volatile Memory (NVM) technologies (like Phase Change Memory and Spin-Transfer-Torque MRAM) promises byte-addressable, low-latency access, blurring the lines between memory and storage. This opens the door to a "byte-based persistence" (BYP) model, where data can be persisted directly in place within NVM using load and store operations, eliminating the need for serialization.
While writing new applications for BYP is feasible, migrating existing BLP applications to BYP is a significant challenge. Programmers must first identify which data structures are critical for persistence, then modify their code to allocate these structures on an NVM heap, and ensure crash-consistent updates. This manual process is laborious, error-prone, and time-consuming, as evidenced by projects that have spent over a year on partial migrations. NVMOVE aims to automate the first, and often most difficult, step: identifying the persistent data structures.
Methods
NVMOVE employs static analysis of C source code to identify user-defined types that represent semantically persistent state. The core insight is that any data that needs to be persistent must be initialized or recovered during the application's startup or crash recovery phase.
The tool works by:
- Identifying Load Functions: Programmers provide NVMOVE with the names of the top-level functions responsible for initializing the application's in-memory state by reading previously persisted data (often called "load functions"). This requires minimal programmer knowledge.
- Analyzing Initialization/Recovery Code: NVMOVE analyzes the source code of these load functions and any functions they call. It identifies variables that are assigned or modified within these functions, either directly or through library calls like
memcpyormemmove. - Type Identification: For each identified variable, NVMOVE determines its user-defined type. If this type is defined within the application's source code, it is flagged as a candidate for persistence.
- Optimization: To improve efficiency and focus on correctness, NVMOVE includes several optimizations:
- It avoids parsing functions that only accept simple built-in types or no arguments.
- It treats common string manipulation functions (
strcpy,memcpy, etc.) as assignment operations. - It avoids re-analyzing library function bodies whose behavior is known.
- Each function body is analyzed only once.
The paper also briefly discusses an alternative "back-tracking from writes" approach, which analyzes system calls that write to block devices and traces data flow backward. However, this method is noted to produce many false positives due to the diverse uses of write operations (e.g., logging, network sockets).
Datasets
The paper evaluates NVMOVE on the source code of Redis (version 3.2.0, 64-bit), a widely-used key-value store with approximately 50,000 lines of code. The evaluation uses the Yahoo Cloud Serving Benchmark (YCSB) [6] and Redis-benchmark to measure performance.
Key Insights and Ideas
- Static Analysis for Persistence Identification: The core idea that persistent data must be initialized during recovery is a powerful heuristic for static analysis. This allows NVMOVE to infer persistence without needing to understand the application's runtime behavior in detail.
- Bridging the Gap to BYP: Manually migrating applications to NVM is a significant hurdle. NVMOVE tackles the most challenging part – identifying what needs to be persisted – thereby lowering the barrier to entry for adopting byte-based persistence.
- Type vs. Variable Identification: NVMOVE identifies types as persistent, which is a pragmatic approach. While this can lead to some false positives (e.g., identifying an iterator type as persistent even if only one instance is used), it simplifies the analysis and still provides substantial value.
- Performance Gains are Real: The emulation results demonstrate that migrating to BYP, even with the overhead of NVM operations, can yield significant performance improvements over traditional logging-based persistence on SSDs.
Key Results
- High Accuracy on Redis: When applied to Redis, NVMOVE identified 25 persistent types out of 122 total struct types. It achieved no false negatives (meaning all truly persistent types were found) and only 11 false positives. This accuracy was compared against a manual port of Redis by an independent team.
- Performance Improvement: Emulating the migration of identified persistent types in Redis to an NVM heap showed significant performance benefits:
- The modified Redis performed within 78% of Redis with no persistence.
- It achieved more than 2x the performance of Redis using synchronous logging on SSDs.
- Specific YCSB benchmark results showed speedups of up to 2.2x compared to baseline AOF on SSDs, with faster STT-RAM NVM showing better results than slower PCM NVM.
- Efficiency: NVMOVE runs on the Redis codebase in approximately five minutes, indicating its scalability for large codebases.
Limitations and Future Work
- Type-Level Identification: NVMOVE identifies types as persistent, not specific variables. This can lead to over-approximation, where a type is marked persistent even if only a few instances are actually used for persistence. This is acknowledged as a source of false positives.
- Volatile State: Applications may contain volatile state (e.g., reference counts) within otherwise persistent types. NVMOVE might incorrectly flag these volatile components as persistent.
- Dynamic Behavior: The current implementation focuses on static analysis and does not support applications that dynamically determine initialization through function pointers.
- Future Work:
- Reducing False Positives: The authors plan to explore techniques to decrease false positives, potentially by identifying persistent variables rather than just types. This could involve combining static analysis with dynamic/taint analysis to track variable progression through execution.
- Crash Consistency: NVMOVE currently focuses on identifying persistent data. Future work will address the crucial aspect of ensuring crash-consistent updates to these persistent structures, potentially by integrating techniques like write-ahead logging or transactions.
- Broader Language Support: While currently C-focused, the approach could be extended to other languages supported by Clang.
Summary updated