[lttng-dev] Integration of the state history system in LTTv

[lttng-dev] Integration of the state history system in LTTv

[Simon Marchi]

Hi,

For those who don't know, we recently started working on the
integration of the state history system designed by Alexandre
Montplaisir in LTTv. This will include a C++ rewrite and a bit of
design work to keep the code as modular as possible. For example, we
want to make sure it is possible to use the state system without the
history part. Here is a brief description of the different parts we
plan to create.

Comments, questions and advices are very welcome !


* libState (or something like that)

The libState library can be used to represent the current state of a
system in the form of an attribute tree. An attribute is a mapping
between a key (a string) and a value (generally a string, an integer
or a null value). The attribute tree is analoguous to the structure of
a filesystem, since an attribute can contain children attributes in
addition to its own value. When the path of an attribute is specified,
it can be either absolute or relative to another attribute.

The possible operations on the attribute tree are:
- Add a new attribute, specifying its value.
- Change the value of an existing attribute.
- Delete an attribute and all its descendants.
- Get the parent attribute of an attribute.
- Get the children attributes of an attribute, or their number.
- Get the total number of attributes in the tree.

libState is independent from LTTv, is not domain-specific, and could
be packaged separately.


* libInterval (or something like that)

The libInterval library can be used to represent and save an interval
tree in memory or on disk. Each interval is characterized by begin and
end timestamps, a value and a key.

The possible operations on the interval tree are:
- Add an interval, specifying its key, value and begin/end timestamp.
- Lookup intervals that intersect a punctual time value.
- Lookup an interval that intersects a punctual time value and that
matches a given key.

Due to the nature of the storage of the interval tree on disk,
deletion of intervals probably won't be possible.

Like libState, libInterface is indenpendent from LTTv, is not
domain-specific, and could be packaged separately.


* LTTv State module

The State module's job is to receive attribute value changes and to
store them to constantly maintain the current state of all attributes
in the system. It also keeps the timestamp associated to the last
state change of every attribute, so that when the state of an
attribute changes, it is possible to create an interval for the
previous value. It defines a hook (using the LTTv hook system) that is
called every time the value of an attribute changes. The old and new
values and the associated timestamps are passed as parameters to the
callbacks. It offers a public API to other modules to send state
changes and query current state values.

The State module built around the libState library.


* LTTv StateHistory module

The StateHistory module's job is to record the state of the system for
any moment of the time lapse of the trace. The state is represented by
the combination of the values of all the attributes of the system. To
do so, it hooks on State module's hook and creates an interval in the
interval tree every time an attribute changes value. It offers a
public API to other modules to get the value of any attribute or all
available attributes at a given time.

The StateHistory module is built around the libInterval library.


We still need to figure out what changes will be needed in LTTv to
adapt the views to the this new system, but we first would like to
know if the foundations (the architecture described in this message)
sounds right.

Thanks !

Simon

[lttng-dev] Integration of the state history system in LTTv

[Alexandre Montplaisir]

Hi Simon,

Very impressive write-up, glad to see it's coming along ;)


Before going into anything too specific, I would have 2 points to comment:

- Where is the separation between "libstate" and the LTTV state module?
Actually, why is there a separation at all? By itself, libstate doesn't
seem to have any useful functionality and would depend on the LTTV
module (which wouldn't be available, for example, in lttng-top). I have
an example inline below.

- You also decided to separate the history creation part from the
queries part. On the Java side, we have both insertions and queries go
through "StateSystem" which is probably equivalent to "libstate" here. I
don't think yours is a bad idea either, however it does not hurt to have
the queries go through the "central" state system :
Let's suppose you want to query a history that is being built. The
information is either in the current (transient) state, OR in the
history, and this will vary per attribute (depending on the start time
of the latest state change). If it's in the "transient state", you
return it straight from memory. If it's in the history however, you will
do a normal query on the history on disk.

So I would suggest having one central location for queries and
insertions, and it would make sense to put that in libstate. That way
other applications could use that functionality. libinterval could then
be, optionally of course, used by libstate if you want a history (with
dlopen() maybe?)


- (third point, sorry I lied) In fact, why would you need a LTTV module
at all? If your goal is to make a full-blown shared library, wouldn't it
be easier to simply link LTTV dynamically with it? Genuinely asking
here, as I am not too familiar with LTTV's inner architecture, and
wondering what could make it easier for you guys.


One more comment below,

On 12-01-26 06:46 PM, Simon Marchi wrote:
> Hi,
>
> For those who don't know, we recently started working on the
> integration of the state history system designed by Alexandre
> Montplaisir in LTTv. This will include a C++ rewrite and a bit of
> design work to keep the code as modular as possible. For example, we
> want to make sure it is possible to use the state system without the
> history part. Here is a brief description of the different parts we
> plan to create.
>
> Comments, questions and advices are very welcome !
>
>
> * libState (or something like that)
>
> The libState library can be used to represent the current state of a
> system in the form of an attribute tree. An attribute is a mapping
> between a key (a string) and a value (generally a string, an integer
> or a null value). The attribute tree is analoguous to the structure of
> a filesystem, since an attribute can contain children attributes in
> addition to its own value. When the path of an attribute is specified,
> it can be either absolute or relative to another attribute.
>
> The possible operations on the attribute tree are:
> - Add a new attribute, specifying its value.
> - Change the value of an existing attribute.
> - Delete an attribute and all its descendants.
> - Get the parent attribute of an attribute.
> - Get the children attributes of an attribute, or their number.
> - Get the total number of attributes in the tree.
>
> libState is independent from LTTv, is not domain-specific, and could
> be packaged separately.
>
>
> * libInterval (or something like that)
>
> The libInterval library can be used to represent and save an interval
> tree in memory or on disk. Each interval is characterized by begin and
> end timestamps, a value and a key.
>
> The possible operations on the interval tree are:
> - Add an interval, specifying its key, value and begin/end timestamp.
> - Lookup intervals that intersect a punctual time value.
> - Lookup an interval that intersects a punctual time value and that
> matches a given key.
>
> Due to the nature of the storage of the interval tree on disk,
> deletion of intervals probably won't be possible.
>
> Like libState, libInterface is indenpendent from LTTv, is not
> domain-specific, and could be packaged separately.
>
>
> * LTTv State module
>
> The State module's job is to receive attribute value changes and to
> store them to constantly maintain the current state of all attributes
> in the system.
> It also keeps the timestamp associated to the last
> state change of every attribute, so that when the state of an
> attribute changes, it is possible to create an interval for the
> previous value.

Ok so this is the part we were calling the "transient state" (which
represents the current state of the system as it was, at the point where
we are now reading the trace). But you mentionned earlier that libstate
would allow to

- Change the value of an existing attribute.

Changing the value of an existing attribute implies having to maintain
the transient state, which in turn implies creating the intervals for
the old states that get replaced. This is mainly where I think you
should keep "libstate" and the "lttv state module" together.



Thoughts, questions, comments, please let me know!


Cheers,

-- 
Alexandre Montplaisir
DORSAL lab,
?cole Polytechnique de Montr?al

[lttng-dev] Integration of the state history system in LTTv

[Alexandre Montplaisir]

Hi Daniel,

It's nice to see there is interest ;)


On 12-01-27 10:01 AM, Thibault, Daniel wrote:
>> * libState (or something like that)
>>
>> The libState library can be used to represent the current state of a
>> system in the form of an attribute tree. An attribute is a mapping
>> between a key (a string) and a value (generally a string, an integer
>> or a null value). The attribute tree is analoguous to the structure of
>> a filesystem, since an attribute can contain children attributes in
>> addition to its own value. When the path of an attribute is specified,
>> it can be either absolute or relative to another attribute.
>>
>> The possible operations on the attribute tree are:
>> - Add a new attribute, specifying its value.
>> - Change the value of an existing attribute.
>> - Delete an attribute and all its descendants.
>> - Get the parent attribute of an attribute.
>> - Get the children attributes of an attribute, or their number.
>> - Get the total number of attributes in the tree.
>>
>> libState is independent from LTTv, is not domain-specific, and could
>> be packaged separately.
>    I suspect provision must be made for attributes that are arrays.  For instance, any of the attributes of processors in a multi-processor system.  Or is it expected to handle this by introducing a layer of index attributes?  (e.g. /processor/0/attribute, processor/1/attribute, etc.)

Every attribute in the model has a unique integer identifier, which we
call a "quark" (in reference to Glib's quarks for interned strings). So
it could be possible to build an "index" (similar to a database index)
of specific attributes by simply remembering their quarks within the
application.

For example you could ask for the quarks matching a pattern, like:
/processor/*/status

and it would return you the quarks for the /status attribute of each
processor in the trace. If you use those quarks for queries afterwards,
performance will be better (since you don't have to re-hash the same
strings over and over).


>
>> * libInterval (or something like that)
>>
>> The libInterval library can be used to represent and save an interval
>> tree in memory or on disk. Each interval is characterized by begin and
>> end timestamps, a value and a key.
>>
>> The possible operations on the interval tree are:
>> - Add an interval, specifying its key, value and begin/end timestamp.
>> - Lookup intervals that intersect a punctual time value.
>> - Lookup an interval that intersects a punctual time value and that
>> matches a given key.
>>
>> Due to the nature of the storage of the interval tree on disk,
>> deletion of intervals probably won't be possible.
>>
>> Like libState, libInterface is indenpendent from LTTv, is not
>> domain-specific, and could be packaged separately.
>    A distinction may need to be made between inclusive and exclusive bounds: e.g. the intervals [t1..t2], [t1..t2[, ]t1..t2] and ]t1..t2[ are all different from each other.

Indeed, this is not very hard to do, but it's very important to be clear
about it.

One thing that makes it easier is that timestamps are not continuous,
they are discrete. In LTTng traces, the smallest unit is a nanosecond.
We could also go down to the TSC counter, but even that wouldn't be
continuous. Between two nanoseconds, nothing happens in the trace. So
the two intervals:

[10, 20]
]11, 21[

are equivalent here. In my implementation, all the intervals are
inclusive, like [t1, t2]

If there is a state change at time t, the new state is valid right away.
So if we have changes at t1 and t2, the first state will be valid during
[t1, t2-1] and the second one will be valid from [t2, ...  onwards


Also, since all state intervals are juxtaposed to each other, it's
possible to "jump" from one state to another by taking the current
interval's end time "t_end" and doing a query at "t_end + 1" to get the
next interval.


Cheers,

-- 
Alexandre Montplaisir
DORSAL lab,
?cole Polytechnique de Montr?al

[lttng-dev] Integration of the state history system in LTTv

[Thibault, Daniel]

> * libState (or something like that)
>
> The libState library can be used to represent the current state of a
> system in the form of an attribute tree. An attribute is a mapping
> between a key (a string) and a value (generally a string, an integer
> or a null value). The attribute tree is analoguous to the structure of
> a filesystem, since an attribute can contain children attributes in
> addition to its own value. When the path of an attribute is specified,
> it can be either absolute or relative to another attribute.
>
> The possible operations on the attribute tree are:
> - Add a new attribute, specifying its value.
> - Change the value of an existing attribute.
> - Delete an attribute and all its descendants.
> - Get the parent attribute of an attribute.
> - Get the children attributes of an attribute, or their number.
> - Get the total number of attributes in the tree.
>
> libState is independent from LTTv, is not domain-specific, and could
> be packaged separately.

   I suspect provision must be made for attributes that are arrays.  For instance, any of the attributes of processors in a multi-processor system.  Or is it expected to handle this by introducing a layer of index attributes?  (e.g. /processor/0/attribute, processor/1/attribute, etc.)

> * libInterval (or something like that)
>
> The libInterval library can be used to represent and save an interval
> tree in memory or on disk. Each interval is characterized by begin and
> end timestamps, a value and a key.
>
> The possible operations on the interval tree are:
> - Add an interval, specifying its key, value and begin/end timestamp.
> - Lookup intervals that intersect a punctual time value.
> - Lookup an interval that intersects a punctual time value and that
> matches a given key.
>
> Due to the nature of the storage of the interval tree on disk,
> deletion of intervals probably won't be possible.
>
> Like libState, libInterface is indenpendent from LTTv, is not
> domain-specific, and could be packaged separately.

   A distinction may need to be made between inclusive and exclusive bounds: e.g. the intervals [t1..t2], [t1..t2[, ]t1..t2] and ]t1..t2[ are all different from each other.

> * LTTv State module
>
> The State module's job is to receive attribute value changes and to
> store them to constantly maintain the current state of all attributes
> in the system. It also keeps the timestamp associated to the last
> state change of every attribute, so that when the state of an
> attribute changes, it is possible to create an interval for the
> previous value. It defines a hook (using the LTTv hook system) that is
> called every time the value of an attribute changes. The old and new
> values and the associated timestamps are passed as parameters to the
> callbacks. It offers a public API to other modules to send state
> changes and query current state values.
>
> The State module built around the libState library.

> * LTTv StateHistory module
>
> The StateHistory module's job is to record the state of the system for
> any moment of the time lapse of the trace. The state is represented by
> the combination of the values of all the attributes of the system. To
> do so, it hooks on State module's hook and creates an interval in the
> interval tree every time an attribute changes value. It offers a
> public API to other modules to get the value of any attribute or all
> available attributes at a given time.
>
> The StateHistory module is built around the libInterval library.

Daniel U. Thibault
R & D pour la d?fense Canada - Valcartier (RDDC Valcartier) / Defence R&D Canada - Valcartier (DRDC Valcartier)
Syst?me de syst?mes (SdS) / System of Systems (SoS)
Solutions informatiques et exp?rimentations (SIE) / Computing Solutions and Experimentations (CSE)
2459 Boul. Pie XI Nord
Qu?bec, QC  G3J 1X5
CANADA
Vox : (418) 844-4000 x4245
Fax : (418) 844-4538
NAC: 918V QSDJ
Gouvernement du Canada / Government of Canada
<http://www.valcartier.drdc-rddc.gc.ca/>