Information Technology Reference
In-Depth Information
nodes. When a node is full (that is, there is no more room in the block on disk),
it gets “closed off”, and the latest end time found in the intervals it contains
becomes the node's end time. A new sibling node is then added to its right. If the
maximum number of nodes is reached in the parent, a new sibling is added to
the parent, and so on up to the root node. Figure 4 shows the steps of a tree that
gets built from scratch (from left to right). The numbers represent hypothetic
start and end times of each node.
4 State System Querying and Visualization
This section investigates the querying and visualization of the values stored in
the state system in both the oine and online tracing modes.
4.1 Querying in O
ine Mode
The transient state is only required during the construction of the history. It
means that when the trace reading is completed, no more events will be sent
to the handler. Therefore, no new state changes will be created on the system.
Consequently, at trace end, all transient intervals are closed and added to the
state history. The state history is then complete and ready for future queries.
Once the history is completed, the state system is ready to receive queries.
The user application can access the attribute tree and resources hierarchy, and
use it to extract and browse the different state values of the attributes.
A typical query starts by providing a timestamp and a resource (attribute).
Since the attribute tree always resides in main memory, we can use a multi-level
hashmap of the attribute's path elements, which will give us the key of the given
resource or attribute in the attribute tree. Having a timestamp and attribute key,
a search in the history tree will be started from the root node downwards, explor-
ing only the branch that can possibly contain the target timestamp. Within each
node, it iterates through all possible intervals and return only those intersecting
the target time. (Since intervals are sorted in the node by their end times, we
can cut in half, on average, the number of intervals to iterate over.) All returned
key/value pairs are returned and the external application is then free to look at
the contents for whatever information it needs. Figure 5 shows an example of
a complete and closed-off tree, on which we would run a query for timestamp
t = 280.
4.2 Live Mode
Note that if we are querying a “live” state system, it is possible for some infor-
mation to still be “current” and not yet part of the state history. Indeed, the
start timestamp may be earlier than the queried time but still ongoing. Thus,
the query system first looks at the current state and, if the value is not found,
then searches the state history.
