A quite important milestone was reached last week : the finalization of the "partial history" provider. I've been hacking at it for 2-3 weeks now, but I finally fixed the remaining (annoying!) bugs, and now it works!

Typically a History Tree (the disk-based interval data structure) would contain the complete history of a trace. This would make the Tree independant of the trace, as it had all the information.

Unfortunately, with the sample Event handler that was provided, for very dense traces the result History file would be very big, usually bigger than the trace itself. This is not a surprise per se (it's to be expected that the amount of state information is proportional to the size of the original trace) but it would mean that any extra information (additional statistics, etc.) would add another x1 the size of the trace each time. This could get very big very fast!

Enters the concept of the partial histories. Instead of storing every single existing state intervals, we only store those crossing specific timestamps, called "checkpoints". Stabbing queries run at timestamps equal to checkpoints would return a full Current State, as normal.
However, for queries between checkpoints (which is usually the case), we could go back to the trace and "replay" the events in order to obtain the Current State at the wanted time.

This is a bit similar to the method used in LTTV: LTTV saves "snapshots" of the state at different times ; on queries it reloads the previous snapshot and updates the ongoing state by reading the trace.

The Partial History method used here has 2 main differences with LTTV's snapshots method. First, the state information is stored on disk (unlike the snapshots), so we are at no risk of running out of memory for very large or very long traces.

Second, more importantly, a state interval crossing many checkpoints would only be stored once in the History Tree (unlike the snapshots, which could repeat redundant information in multiple snapshots).

The benchmark results are, dare I say, hilarious. Query times increase a bit, since we have some extra processing and trace-reading to do, but not by much (x1.2 - x1.5, depending on the density of checkpoints). Resulting history-file size however drops dramatically : it's about a thousand (yes 1000) times smaller!

History file sizes:

http://www.dorsal.polymtl.ca/~alexmont/results/2011-07-05-full-vs-partial-history/filesize1.png

http://www.dorsal.polymtl.ca/~alexmont/results/2011-07-05-full-vs-partial-history/filesize2.png

Query times:

http://www.dorsal.polymtl.ca/~alexmont/results/2011-07-05-full-vs-partial-history/queries1.png

Building the history is also a bit faster (since we don't have as much to write to disk):

http://www.dorsal.polymtl.ca/~alexmont/results/2011-07-05-full-vs-partial-history/creation_time.png

It's still a bit slower than the equivalent done in LTTV (parsing the trace + generating snapshots) but it's really not bad, considering we:

  • use a generic, non-hardcoded way of defining our attributes and state changes
  • are using a virtualized language (Java), vs. -02'ed native code.
  • don't use any RCU zero-copy spliced memory buffers or what-have-you, just good old Collections.

Although I'm multi-threaded, LTTV is not, so it helps. (This explains why it takes roughly the same amount of time for different numbers of checkpoints, probably the event processing is the bottleneck not the writing to disk.)

Note : the checkpoints are defined per every *number of events in the trace*, and not per timestamp. This is by design (it would have been easier to do per timestamp in fact...) because this way we algorithmically cap the amount of processing to do : we will never have to process more than n-1 events, where n is the number of events between checkpoints (and it's n/2 on average).

However, when using a partial history we lose the ability to follow a particular attribute throughout the tree (with getNextStateChange() and getPreviousStateChange()) or the ability to call Single Queries (we can only load a complete Current State). Both "complete" and "partial" options are there, depending on your use case and space limitations.

Future work: what could be interesting would be to store different attributes in different providers... For example, really important attributes we want to run dependency analysis and the like on, those we could store in a complete provider. But other, less important attributes, like statistics, those could be stored in a partial history and be recomputed on-the-fly.

And I also have in the back of my head some kind of "statistics provider", which would store real statistics at checkpoints, but to recompute in between we'd do a simple rule-of-three to approximate the number with a simple linear curve...