TL;DR
This paper introduces a novel approach for deterministic replay of multithreaded programs running on Java Virtual Machines (JVMs). By efficiently tracking and replaying cross-thread data dependencies, their system achieves accurate replay with low overhead, even for programs with data races, a significant challenge for existing methods.
What Problem Does This Paper Address?
Multithreaded programs are notoriously difficult to debug due to their inherent nondeterminism. Different thread interleavings can lead to rare, hard-to-reproduce bugs. While "record and replay" techniques aim to solve this by capturing an execution and replaying it deterministically, existing methods struggle with:
- Data Races: Many approaches either ignore data races (making them unsound) or incur very high overhead to track them.
- Managed Runtimes (JVMs): JVMs themselves introduce many sources of nondeterminism (e.g., dynamic compilation, garbage collection, class loading) that make deterministic replay challenging.
- Overhead: Existing solutions often impose significant performance penalties, making them impractical for real-world use.
- Limited Functionality: Some systems only support online or offline replay, but not both.
This paper tackles these limitations by proposing a system that can deterministically replay multithreaded executions, including those with data races, on commodity JVMs with manageable overhead.
Methods
The core of the proposed solution lies in two dynamic analyses: RECORD and REPLAY.
- RECORD: This phase builds upon prior work (Octet) to efficiently track "happens-before" edges, which are crucial for implying all cross-thread data dependencies. It uses a novel state-tracking mechanism for shared objects (WrEx, RdEx, RdSh) to identify accesses that might be involved in cross-thread dependencies. When such accesses occur, it triggers state transitions that are used to record happens-before edges. RECORD is optimized for the common case of accesses not involved in dependencies, using a "fast path."
- REPLAY: This phase takes the recorded happens-before edges and enforces them during a second execution. Crucially, REPLAY elides (skips) program synchronization operations (like locks). This is a key innovation because it avoids deadlocks that would occur if synchronization were replayed naively alongside data dependencies. REPLAY also uses a "fast path" for accesses not involved in recorded dependencies.
To address JVM-specific nondeterminism, the authors introduce:
- JVM Modifications: They modify Jikes RVM to control sources of nondeterminism like garbage collection, hash codes, and system time.
- Fork-and-Recompile Methodology: For dynamic compilation and class loading, they use a two-phase approach: a "warmup" phase to compile and initialize everything, followed by forking the process. One process runs RECORD, and the other runs REPLAY. This ensures both executions start from a consistent state.
Datasets
The paper evaluates their system using benchmarked versions of large, real-world applications:
- DaCapo benchmarks: Versions 2006-10-MR2 and bach-9.12 (excluding single-threaded or problematic benchmarks).
- SPECjbb2000 and SPECjbb2005: Fixed-workload versions.
The authors note that they exclude the eclipse6 benchmark due to issues with the fork-and-recompile methodology and determinism support.
Key Insights and Ideas
- Eliding Synchronization is Key: The most surprising insight is that REPLAY must elide synchronization operations, not replay them. This is counter-intuitive to many record/replay systems but is essential to avoid deadlocks and achieve efficient replay.
- Happens-Before Edges as a Sufficient Abstraction: The system relies on the fact that accurately replaying happens-before edges is sufficient to guarantee deterministic replay of all cross-thread data dependencies.
- JVM Nondeterminism is a Major Hurdle: The paper highlights that even with efficient data dependency tracking, making JVMs behave deterministically for replay is a significant engineering challenge, requiring specific modifications and methodologies.
- REPLAY Can Be Faster Than RECORD: By eliding synchronization and only replaying necessary dependencies, REPLAY can sometimes outperform even the RECORD phase, and occasionally even baseline execution.
Key Results
- Successful Replay: The system achieved successful deterministic replay for most benchmarks (e.g., 100% for many in Table 3), demonstrating its effectiveness.
- Low Overhead:
- RECORD (using adaptive methodology) added an average overhead of 49%.
- RECORD (using fork-and-recompile) added an average overhead of 44%.
- REPLAY (using fork-and-recompile) added an average overhead of 29%.
- These overheads are competitive with or better than prior work that supports online and offline replay for racy executions.
- Performance Advantage for REPLAY: REPLAY often outperformed RECORD and even baseline execution due to the elision of synchronization operations, enabling more parallelism.
- Failure of Alternative Configurations: Configurations that ignored happens-before edges or kept synchronization failed consistently, highlighting the necessity of the proposed approach.
Limitations and Future Work
- Fork-and-Recompile Methodology: The authors acknowledge that their fork-and-recompile methodology is not suitable for production environments. They suggest that with more engineering effort, a JVM could be modified to control nondeterminism without this workaround.
- Production Readiness: While the system demonstrates effectiveness, it's a research prototype. Making it production-ready would require addressing more subtle JVM and system-level nondeterminism.
- Generalizing JVM Determinism: The paper focuses on Jikes RVM and its specific challenges. Extending these solutions to other JVMs or managed runtimes might require different approaches.
- Online Replay: While the approach is suited for online replay, the current implementation primarily focuses on offline replay.
- High-Conflict Objects: The paper mentions that programs with a high rate of conflicting transitions incur more overhead, and refers to ongoing work to address this.
Summary updated