Information Technology Reference
In-Depth Information
the state values for events whose time value is greater than or equal to
t
0
but
lower than
t
. Then, the resulting updated state is returned as response to the
user. Figure 1 represents a trace and its various snapshots at checkpoints. It also
shows the process of resolving a user query for the time indicated by
X
.
The checkpoint method avoids having to reread the trace from the beginning
every time. Using such a method works well enough for small traces (tens or
hundreds of MB). However, it brings some storage scalability issues, since the
snapshot storage space grows with both the number of state elements and the
trace duration. There is some wasteful redundancy arising from the fact that
some information may not change from one checkpoint to another and yet is
repeated in each snapshot. In addition, the size of each snapshot increases on a
larger system, if there are more processes running and more activity at the same
time. If these checkpoints are stored in RAM, there is a hard limit on the size
of the trace that can be analyzed. It could, up to a certain point, reduce the
number of checkpoints, but that would degrade the query performance of the
state system.
A dynamic checkpoint method is proposed in [EJD13], which uses dynamic
intervals, instead of a fixed number of events, for storing the snapshots. Although
it utilizes the memory better than the previous solution, but still encompasses
the other potential problems of the checkpoint method.
Another possible alternative is to store state information directly in the trace.
This does not replace the need for state storage, but avoids the viewer hav-
ing to define the state changes associated with events. This approach is used
by [CGL08]. Their traces contain both specific events and states with associ-
ated time interval. They display the events and states with the Jumpshot tool
[ZLGS99] which clearly shows the communication between MPI processes. Our
work focuses on the management of state information at the viewer level, not
in the tracer. The generation and processing of this information, during tracing,
however, may be explored in a future work.
The proposed state history database stores different intervals representing
the state value changes. Several data structures have been presented in the lit-
erature to store and manage the records of intervals [GG98] like segment-tree,
interval-tree, Hb-tree, R-tree (and its many variants). These solutions are mostly
designed to work inside the main memory, rather than the disk, which threaten
the scalability and can not be used well for very large traces (in the range of hun-
dreds of gigabytes). Even by forcing and changing the above methods to store
the data in disk, a problem still exists. These data structures work properly
for static data sets, but not for the incrementally built intervals. For instance,
the R-Tree has to be constantly rebalanced to cope with the incrementally re-
ceived intervals which requires a large number of nodes splitting and merging
(re-balancing) operations. This resulted in very long history construction times,
which makes them inappropriate to use in trace viewers where the data is re-
ceived incrementally.
Another disk based interval management method, SLOG File Format, is pro-
posed by Chan et al. [CGL08], which is a hierarchical r-tree based file format to
