Re: [linuxtools-dev] Re: TMF indexing performance

[Francois Chouinard <fchouinard@xxxxxxxxx>]

Hi Michel,

Thanks for your input. This is very valuable insight into the type of problems that the LTTng team had to face and the solutions you implemented.

1. Time based access

For time based access, LTTng keeps a sorted array of fixed size blocks (in memory I presume). If I understand well, these blocks correspond (more or less) to disk blocks which are read in one shot. Looking for a particular event, based on a timestamp, boils down to:
[1] Perform a binary search in the sorted array of blocks
[2] Read the corresponding disk block
[3] Do a linear search (in memory) for the lucky event.

This is very similar to what is proposed in TMF at the trace level:
[0] Build an index of timestamps spaced at regular intervals
[1] Perform a binary search for the requested timestamp in the index
[2] Read the corresponding event
[3] Perform successive reads until you hit the wanted event

Why build an index in the FW? Because, in the general case, traces are not structured anywhere as well as LTTng traces are. There is likely no index to just read off the disk. So it has to be built.

What about the successive reads to find the wanted event in the block? The TMF solution (coming soon :-) is to define cache pages in TmfTrace, where each page holds N events, N being the number of events between 2 successive entries in the index. When a read request comes in, the whole page (N events) is read in cache.

So, for time based access, I think we have very similar solutions, the difference being that TMF is likely less efficient but has the arguable advantage of being more generic.


2. Rank based access

The LTTng solution is to take advantage of the time based access to "position" the traces and then read the events in sequence until the of the table is filled, presumably the visible part + 1 (or 2) page before and after.

Currently, TMF takes advantage of the index to quickly locate an event by rank. Since each index entry corresponds to N events, it is obvious that simple modulo arithmetics gets us to the "right" block (in a trace) even faster than time based event seeking.

Here, I would like to point out that finding the Nth event of a trace could very well be done "à la LTTv" i.e by linear interpolation over the trace time range. However, in the general case, how do you know that range? Again, maybe not all tracing tools are as friendly as LTTng as to provide that time range up front (specially in streaming), in which case, the trace has to be somehow scanned to determine it. It follows that if the trace has to be scanned anyway (in the general case), it would be advantageous to build that index at the same time. BTW, I am toying with the idea of indexing individual traces as they are imported and store the index (and time range, why not?) with the trace. Then, TMF will become eerily similar to LTTng :-)

I totally agree that the composition of traces at the experiment level is a potential nightmare. The LTTng solution seems to be to recompute the ranking. Same for TMF :-(


Thanks again for the insight,
/fc