Report on lr_dlf2xml performance
Francis J. Lacoste
flacoste at logreport.org
Wed Mar 13 19:45:33 CET 2002
Hello everyone!
I've worked on the performance of the reporting engine (lr_dlf2xml)
this week-end and here are my preliminary results.
Here are the different performance area that are problematic as the
number of DLF records we have to process grows:
1- Disk space.
lr_dlf2xml will use disk space to hold the derived and extended DLF
files. Since each extended DLF files would contains the original DLF
data plus the extended fiels, this means that the disk space
requirements grows linearly with the number of DLF records.
Initially, all the extended and derived schemas were generated at the
beginning of the report generation. This meant the amount of disk
space needed was also proportional to the number of extended schema
used. For example, to process a 100Meg DLF www file, you would have
needed at least 600Megs of disk space. I've make this better by
creating the extended and derived schemas just before processing the
reports that need them and deleting the file after. This way, we would
need about only twice the size of the DLF file. The trade off is that
we have to process the DLF file more times. But frankly, this is not
really the place where we lose the most time (see next item). This
represents between 1% and 2% of the overall time when using the best
algorithm. This represents a lot less when using the slower algorithm.
Increasing the processing time by between 1% and 5% (depending on the
number of time we have to process the DLF file) to obtain huge saving
on disk space seems like a nice trade off. Remember, this trade off is
only active when we are using extended and derived schemas.
2- Processing the DLFs
The different algorithm reads the DLF files a number of different
time. The involved code is:
while ( $line = <$dlf_fh> ) {
chomp $line;
my $dlf = split [ /\s/, $line];
}
Using the Benchmark, you can find out that processing 200K cisco DLF
records that way takes 7.76usr + 0.10sys. This represent 2% of the
overall time when we process the DLF only once. But as we repeat the
process, it represent a higher proportion of the processed time. For
example, in the below benchmarks, this is the main area where the
parallel and sequential algorithm differ. Since the firewall
superservice contains 21 reports, the DLF file was processed 21 times
instead of 1 and there the read, chomp, split part represented 20% of the
processing time.
3- Memory
Memory usage is a big performance point. lr_dlf2xml uses in-memory
hashes to implement the group operation. In a simple group operation
(for example, a top-client_host report), memory usage is proportional
to the number of keys (client_host) you'll find in the DLF file. When
using nested group (for example, in a top-client_host-by-day report or
a top-pkt-dst-by-src reports), memory usage will be higher: number of
different key A (pkt-dst) x number of different key B (src). (This is
the worst case, it assumes that all key A appears for each key B.)
As the memory usage grow, performance can degrade if there isn't
enough RAM to hold the whole process: since lr_dlf2xml will swap and
could even trash.
There are two ways to solve this problem. The first one is to use a
disk-based hash table. This is really slow since this will mean a lot
more disk accesses, plus the overhead of marshalling/demarshalling the
datastructures. The other solution, is to work with an input DLF sorted
on the keys. This way we can use a sorted array in memory to limit the
number of item we hold (we can discard keys that we know won't make
the top-X because there is already 10 items that sort before it).
Trade-off here is that sorting takes time.
Different algorithm tested
==========================
In the last Lire release (and currently in CVS), there are two
different algorithm used: parrallel and sequential.
Parrallel
- Read the DLF one time to determine number of records, start and end time.
- Read the DLF one time to generate all the extended and derived
schema.
- Process each generated DLF (main, extended or derived) one time to
compute the reports using that DLF.
- Uses in memory hash to implement the group operation.
Sequential
- Read the DLF one time to determine number of records, start and end time.
- Read the DLF one time to generate all the extended and derived
schema.
- Compute each report, one at a time, by processing the appropriate
DLF source.
- Uses in memory hash to implement the group operation.
The choice between the two algorithms is based on the size (in bytes)
of the main DLF. As you can understand from what I said about memory
usage, this is not an precise figure to estimate the memory usage.
Besides, even when using the sequential algorithm, you could run out
of memory for some DLF.
I've implemented a new algorithm this weekend.
Sort
- Read the DLF one time to determine number of records, start and end time.
- Read the main DLF once for each extended or derived DLF that needs
to be created. (This is the disk space/speed trade off).
- Process all reports that need comparable "sort order" at the same
time. (Comparable means that we will process at the same time a
report that needs non-sorted DLF, one that needs a DLF sorted on
time, and another that needs the DLF sorted by time and action).
- Uses sort(1) to sort the DLF file according to the required sort order
by operations.
- Group uses a sorted array data structure to hold only the required
number of items in memory.
Benchmark were run using two different superservices: www using a 250K
records DLF file and firewall using a 240K records DLF file. The www
file contained less than one day of data. The firewall DLF file
spanned more than 30 days. (This is important for timegroup/group
operations which can be memory hungry). Also, you need to remember
that the firewall superservice doesn't use any extended or derived
schema but that the www superservice does (1 derived schema and 6
extended schemas).
Here are the results:
IIS log file containing less than one day of data
=================================================
Parallel algorithm
Input size Real User System Vsize RSS
5K 25 22.85 1.2 9124K 7848K
50K 229 215.17 9.88 12244K 10960K
100K 477 429.12 20.92 15428K 14112K
250K 1454 1354.81 69.21 17248K 14976K
Sequential algorithm
Input size Real User System Vsize RSS
5K 30 28.33 0.21 8896K 7640K
50K 271 266.83 2.11 10804K 9520K
100K 551 538.93 4.86 12732K 10128K
250K 1387 1350.58 12.48 17248K 14076K
Sort algorithm
Input size Real User System Vsize RSS
5K 30 26.98 0.24 8396K 7136K
50K 293 251.17 1.89 8744K 7484K
100K 581 497.57 4.1 9128K 7852K
250K 1792 1261.16 9.44 10032K 6676K
Cisco log containing 1 month of data
====================================
Parallel algorithm
Input size Real User System Vsize RSS
5K 10 10.3 0.07 10104K 8840K
50K 95 94.27 0.2 36144K 34716K
100K 188 187.36 0.47 64500K 62836K
240K 451 430.19 0.98 128908K 124480K
Sequential algorithm
Input size Real User System Vsize RSS
5K 13 12.32 0.12 9372K 8108K
50K 120 116.44 0.53 26776K 25328K
100K 235 230.66 0.97 46064K 44404K
240K 549 535.83 1.99 86920K 82196K
Sort algorithm
Input size Real User System Vsize RSS
5K 14 13.23 0.05 7664K 6404K
50K 131 123.4 0.3 8920K 7612K
100K 267 246.14 0.4 9956K 8584K
240K 637 563.66 1.28 12308K 9656K
All tests run on a relatively idle PIII 600Mhz, 192Megs station. All
metrics comes from the statistics generated by Lire itself.
Highlights:
-----------
The sort algorithm takes a lot less memory everytime but is always
slower than the parallel and sequential algorithm. It is slower in
terms of user time it takes because it processes the DLF files more
times (depending on the number of different sort order needed). In the
case of the firewall reports, it takes between 5-8% more user time to
complete (altough this decrease as the number of records grow) and in
the www case, it takes actually less user time to complete than the
sequential algorithm. The always higher real time is caused by the use
of sort(1) which is not included in the user and system statistics.
But the memory saving are quite drastic, especially in the firewall
superservice case.
Short-term proposal
-------------------
Two solution are possible:
1- Uses the slower but always functional sort based algorithm. This
will make Lire slower than it is currently, but it will make it
possible to process very large log files without problems.
2- Develop a selection algorithm which will switch between the hash
and sort based group implementations for each report based on the
actual number of keys present in the DLF file. This will add some
analysis time to the run (basically a cut -d ' ' -f X | sort -u | wc -l)
for each fields that are implicated in group operation. With this
approach we *may* be able to achieve run time between the parallel
and sort algorithm. This all depends on how much we gain regarding the
extra processing needed in order to analyze the DLF keys. It will also
add some complexity to the code.
Long-term proposal
------------------
In order to achieve really better performance, I think what would be
the most cost-effective in term of performance gain and time to
develop, would be to implement a SQL based report generation. SQL
servers are dedicated to optimizing queries so they'll make a better
job than what we can achieve. The current architeccture was designed
for such an alternatve implementation of the reporting framework. The
basic idea would be that the DLF converters would insert their data in
the SQL database and the lr_dlf2xml would uses SQL queries (generated
automatically based on the report specifications) to generate the XML
report.
I would postpone this to our post-1.0 release. This will then offer
two alternatives to our users: standalone Lire with simple ASCII DLF
support which is fine for small-scale use (but also functional for
large-scale altough a lot less performant), and SQL DLF for high-end
scale.
Questions, comments or suggestions ?
Francis J. Lacoste
--
Francis J. Lacoste . . http://www.logreport.org
/^LogReport$/ . . flacoste at logreport.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.logreport.org/pipermail/development/attachments/20020313/769f97a2/attachment.bin
More information about the Development
mailing list