Information Technology Reference
In-Depth Information
3.3 Transient State and History State
When a state change is reported by the state provider, a transient state record is
created for the requested attribute and stored in memory, in the (current) state
system. Each transient record contains an attribute name, a time and a state
value. If an entry currently exists for this attribute (i. e. there was already a state
value for this particular attribute) then the current value is
replaced
by the new
value. However, the previous value is kept and stored in the state history, to be
available in subsequent enquiries. To do so, we first create one
interval record
from the available information containing and attribute (from the attribute tree),
the old status value, the old value of time (interval start time) and
new
time
value (interval end time). Start and end times represent the bounds of the period
for which the state value is valid for the corresponding attribute.
The completed interval can now be inserted into the state history to become
part of the history. This process is continuing until the end of trace, during
which we obtain a set of completed intervals (i. e. state history values) for each
attribute.
As mentioned earlier, the history state values are stored in a tree-based struc-
ture named “state history tree”. This set of data will be used later to navigate
through the state history for different time values and to reason about the run-
time behavior of the system resources.
3.4 History Tree
Finally, the biggest piece of the puzzle, the State History Tree is a data structure
to store intervals, optimized to be stored on a rotational disk. It is by no means
balanced, so there is no concept of re-balancing the tree. Its two main components
are intervals, as mentioned in the previous section, and nodes. The nodes are the
direct containers for intervals. There is a configurable size (e.g. 32KB, 64KB,
1MB,...) for the nodes. Each node also keeps track of all its children and parent.
Fig. 4.
The process of incrementally building the history tree
The State History Tree is based on the fact that insertions will be done se-
quentially, with intervals being inserted to be sorted by ascending end times as
much as possible. The tree supports inserting elements farther in the past, but
doing it too often can lead to some imbalance (higher level nodes being filled
faster than leaves), and at worst the tree would degenerate in a simple list of
