Efficient Model to Query and Visualize the System States Extracted from Trace Data

Catalog abstract summary

The accessible chapter preview describes a tree-based model of system states and intervals extracted from traces, with online/offline operation and interactive analysis at approximately 1 TB trace scale.

Source: Springer two-page chapter preview, paraphrased; complete chapter not obtained.

Problem and motivation

Multicore traces containing system calls, scheduling, and interrupts grow to gigabytes. Replay and checkpoint approaches are expensive, while analysts need arbitrary state-at-time and interval queries for interactive views.

Method and contribution

The implementation uses LTTng kernel and user-space traces with the Eclipse TMF/Linux Tools ecosystem. A state provider maps event types to state changes; an in-memory Attribute Tree represents current state, while a disk State History Tree stores intervals ordered by end time. Incremental block construction, configurable disk blocks, and partial-history granularities of 20,000, 50,000, and 100,000 events support online/offline use. The State System Explorer and control-flow/resource views expose states such as USER, syscall, WAIT, and WAIT_FOR_CPU. The paper states logarithmic query complexity and compares the disk structure with an R-tree.

Findings and evidence

On the stated Intel Core i7 920/6 GB/Eclipse 3.7/OpenJDK 7/LTTng 0.232 setup, the disk-backed history is the key enabler for large traces, and partial updates reduce storage/build cost while still allowing inspection of the event stream. The R-tree comparison shows higher cost from rebalancing in the evaluated workload. Figures cover traces from zero to roughly 12,000 MB, although the paper does not provide a single consolidated numeric benchmark table.

Limitations and future directions

Limitations: The validation is centered on LTTng and a single machine; late interval insertion can imbalance the structure, the event-to-state mapping is partly hard-coded, and the study does not establish behavior under all trace schemas or distributed clocks.

Future work: Support additional tracing ecosystems such as DTrace and ETW, improve balancing and late insertion, make mappings more declarative, and evaluate query latency, storage, and update cost across larger heterogeneous and distributed traces.

Sources and identifiers

• Published version published
• Springer two-page chapter preview public_preview

When to cite this paper

Cite this paper when building disk-backed, incrementally queryable state histories from large execution traces.

• The State History Tree and Attribute Tree representation.
• Event-to-state mapping for LTTng kernel/user traces and interactive state queries.
• Partial history updates and the R-tree comparison.
• The stated logarithmic query model and single-platform evaluation caveat.

Citation

@inproceedings{ezzatiJivan2013efficientmodel,
  author = {Alexandre Montplaisir and Naser Ezzati-Jivan and Florian Wininger and Michel R. Dagenais},
  title = {Efficient Model to Query and Visualize the System States Extracted from Trace Data},
  year = {2013},
  booktitle = {Runtime Verification 2013 (RV 2013)},
  pages = {219-234},
  publisher = {Springer Berlin Heidelberg},
  issn = {0302-9743, 1611-3349},
  isbn = {9783642407864, 9783642407871},
  doi = {10.1007/978-3-642-40787-1_13},
  url = {https://doi.org/10.1007/978-3-642-40787-1_13}
}

Montplaisir, A., Ezzati-Jivan, N., Wininger, F., & Dagenais, M. R. (2013). Efficient Model to Query and Visualize the System States Extracted from Trace Data. In Runtime Verification 2013 (RV 2013) (pp. 219-234). https://doi.org/10.1007/978-3-642-40787-1_13

A. Montplaisir, N. Ezzati-Jivan, F. Wininger, and M. R. Dagenais, "Efficient Model to Query and Visualize the System States Extracted from Trace Data," in Runtime Verification 2013 (RV 2013), pp. 219-234, 2013, doi: 10.1007/978-3-642-40787-1_13