Hello new readers, in this kind-of blog I will be reporting status updates on the State History project. Since this is the first of a series, let's start with some definitions:

State History

"State History" is the name given to the global project/library/system/paradigm/watchamacallit, which contains all the other elements below.



An event is simply "something" that happened at a specific, single timestamp. Here obviously the use case is trace events, but the State History is generic enough that it could be used with any kind of events.


State intervals and State values

Unlike an Event, a State has a duration. It also represents "something", but has a start time and a end time (where an event is infinitesimal). The "something" is defined with a State value, which can really be anything. In my implementation, State values can be either 32-bit integers or variable-length strings.



An attribute is a basic unit that can "be in" a state. When we talk about "the state of the system", it's in fact "the state value of every attribute in the system". This allows us to only look at the parts of the state that interest us.

Before using the State History, you need to break down your system (or whatever it is) in attributes. They can be arranged either in a list (one level), or in a tree (many levels, like directories and files). For example, here are some attributes that are used in the kernel-trace state system in the reference implementation:

  • CPUs
  • CPUs/0
  • CPUs/0/current_thread
  • CPUs/0/irq_stack
  • CPUs/1
  • ...

This forms the "attribute tree". Each attribute can also be referred to by its unique integer identifier, which is called a "quark" (in the same spirit as Glib's GQuarks (http://developer.gnome.org/glib/2.29/glib-Quarks.html)).

For most of the functions in the State History system, we use quarks to refer to the attributes. The Attribute Tree allows us to do the conversion from the quark (integer representation) to the slash-separated string or "path".


State change

A state change consists of 3 things:

  • timestamp
  • attribute
  • state value

It's a pseudo-object (it's made with a direct function call in fact, but could be a standalone object too) which basically says that the state of 'attribute' changed to 'state value' at time 'timestamp'.


Current State / "state of the system"

Using the definitions above we can now define the "current state" at a given timestamp 't', which is a representation of the real state of the system as it was at time 't'.

A complete Current State is represented as an array of State values (one for each attribute, the offset in the array == the quark of the attribute). Each state value corresponds to the state of each attribute as it was at time 't'.

The basic method of querying the State System (see below) is to pass a timestamp, and it will return us the Current State at that timestamp.


Event handler

The event handler is the mapping between Events and State Changes. One of the goals of this project was to separate this "definition of the state" from the programming logic.

In my implementation I provide an example Handler for kernel traces in the lttng-2.6 trace format. It's a bit raw, but you can see what it looks like at
http://git.dorsal.polymtl.ca/~alexmont?p=libstatehistory-java.git;a=blob;f=statehistory/src/statehistory/eventHandler/VSTF_Handler.java;h=fcaef6ef5392... starting around line 142.

Note that the attributes are always accessed using their quarks (to avoid useless re-hashing of strings whenever possible). Also note that it is very possible to assign more than one State Change to a given type of Event.


State System (a bit too generic, this could use a better name)

The "state system" object is the interface we normally access externally. It's used for both insertions (where we insert a state change at a specific timestamp), and queries (where we [in the basic form] provide a timestamp/attribute pair and it returns the state of that attribute at that time).

The State System has 3 main components:

Attribute Tree

As defined above. This structure is held in memory and is populated as we see new attribute paths.


Transient State

The Transient State is simply "the Current State where we are now". It is used to store the ongoing State values of the attributes. When a state change occurs, the state that got replaced will be removed from the Transient State and will be inserted in the History.

For offline (post mortem) traces, the Transient State is only active when we are reading the trace and building the history for the first time. The  role of the Transient State become more interesting in live traces and/or if we are using a Partial History Provider.


History Provider

The "History" represents everything before the Transient State. For any query about a State value and timestamp, the information is either in the Transient State or in the History.

The Provider defines how to store this History (it could be in RAM, on disk, in the cloud, etc.). The main provider that is studied here is the History Tree.


Small note: complete history vs. partial history

A complete history is when we store ALL the state information the History. This means that the container (whatever it is) is usable standalone and can restore the state at any point in time.

A partial history is when the History does not contain all the state information we have available. To recreate the state at any arbitrary timestamp we will need access to the original container (in our case here, the original trace).


History Tree

The History Tree is the disk-based interval data structure that was the subject of pretty much the first year of this project. We insert intervals in ascending order of end time, and then can run stabbing queries at any time stamp.



So if we look at the big picture, we go:
[events (trace)] -> Event Handler -> [state changes] -> State System -> [intervals] -> History Tree

where the stuff in [brackets] are the objects being passed and the other in between the processing functions converting from one to the next.
Note that you can use any of those parts independently (ie, if your "trace" has state changes or even intervals already in it). In our use case here we're starting with punctual events and want to end with a series of intervals, so we need the whole thing.