Searching logfiles with multiple threads
At my day job it's not uncommon that I'll get
a list of IP addresses, networks, and/or hostnames that are suspected to
be used by various bad actors, and then I'll need to go search through
previous firewall, web-access, and DNS query logs to see if they show up
anywhere. And sometimes there's a LOT of log data to search through, or
a lot of suspect data to look for. I've found that grep -f (aka fgrep)
sometimes freaks out if I have a really large number of regex patterns to
search for, or takes a very long time to complete, or never completes.
More than once I've wound up writing a script to break up a list of things
I'm grep'ing for into multiple files so I can search for them in parallel
and because fgrep sometimes just doesn't work well wil large files.
I see a hand out there... Yeah, I know, I should have a better logging
solution than just syslog-ng splitting stuff up into multiple log files that
get rotated and gzip'd nightly. Yeah, yeah... Sue me. I've been working on
other things first such as getting some functional network intrusion
detection working and monitoring more than just internet/dmz/edge traffic.
And, frankly, what I've got with syslog-ng and oak is far superior
to what I found when I first started. :-) What can I say, it's a work in
Anyway, in the meantime, I needed a better/faster way to search things. For
instance, when the FBI announced the blackshades operation, I suddenly had
over 13,000 hostnames/domains to search for in recent DNS query logs. Ugh.
Try that with fgrep. So I blew the dust off my KnR book and wrote
a multi-threaded C program to do that. I mentioned it in passing to my
brother and he made a similar tool in a language he uses at work called
scala. :-) But he also pointed out (duh!) that what I was looking
for in the case of the blackshades data didn't require full regex parsing
and mebbe I should just use substrings at least as an option.
Boy did I feel dumb.
So now not only does my tool use multiple threads for doing regex searches,
it will also (by default now) just do substring searches which is by far
faster. You can download it here if you want it. Note
that this isn't at all polished, merely functional. For instance, it doesn't
support reading from stdin, just from another file like this:
tfgrep2 --patternfile=bsdomains.txt --inputfile=query.log --threads=8
There's some hardwired limitations that I haven't bothered to code around
yet. For instance, there's a hard limit on the maximum number of patterns
it will support. Sometime I'll rewrite the code that reads the pattern file
so it uses malloc and realloc so you can have as many as you have memory for.
There's also a maximum line length at the moment (though I'm careful to make
sure if you have an input line longer than that (8k I think) it will just
break it into multiple lines, not suffer a buffer overflow. But for my
purposes this is no big deal.
The reason it doesn't do stdin, if you're curious, was I wanted to optimize
how I parallelized it. I wanted to avoid using mutexes if I could.
One thing I later found was that when there's a really large number of
this blackshades example, using mutexes wouldn't hurt performance because far
more time is spent checking for matches than is spent reading lines. So,
at some point I'll add a feature so you can read from stdin and the main
program will just build a work queue using a mutex for safety and each
worker thread can pull a line out of this queue to work on.
However, where this won't work nicely is when there's a really big file you
want to search (another good reason to parallelize) but not a lot of things
to search for. In that case, the work-queue mutex will could be a big
bottleneck. In fact, the way I parallelized tfgrep2.c right now is very
simple and would work with a big file and small number of patterns. What it
does is gets the size of the file in bytes, divides it by the number of worker
threads, then it seeks to the start of this split, reads to the start of the
next line, notes the file position and then spawns a thread starting from
byte offset 0 and using this current position as a ending offset. It uses it
as the starting offset for the next thread, finds the end of the line after
the next break and spawns the next thread. So each worker thread has a
roughly equal number of lines it needs to read and they all open the file
with their own file handle and reads as fast as it wants - no queues, no
mutexes, tidy, simple, fast.
And no stdin... :-( But mebbe when I add support stdin, I'll try 'n keep the
mutexes from being a bottleneck by feeding the input file in chunks to each
worker thread rather than just line by line. Maybe I just have a CLI option
to set the number of lines at a time to feed to each worker thread? Or
maybe each worker thread will look at the clock at the start and end of a
task and if it's less than, say, a second or two it (using another mutex)
doubles the "chunk size" - the number of lines the main program reads into
the work queue before unlocking the mutex and the number of lines each
worker thread reads out of the queue before proceeding to go to work on them?
I'm not sure what the best approach here will be but it'll be interesting to
find out. :-)
Of course, with smaller numbers of patterns, and having to read things in
chunks to feed to the worker threads will mean this work queue will need
a lot more memory. But that's ok. :-)