QBrowsCap & QGeoIP: detecting browsers and locations

In December and January, I’ve continued working on my master thesis, while simultaneously preparing for my exams in January (which I passed without problems).
In a previous blog post, I had indicated that I ran into problems while parsing dates: Qt uses the system locale for this, but on Mac OS X there turned out to be a severe performance problem with that functionality. I solved that by developing QCachingLocale, which is a class that introduces a caching layer to prevent said performance degradations.

Further parsing

Now, parsing the date was of course only one tiny part of the problem: I also had to parse the episodes information embedded in each Episodes log file line (which is trivial), as well as map the IP address to a physical location and an ISP and map the user-agent string to a platform and actual browser.
Finally, we also want to map the episode duration to either duration:slow, duration:acceptable or duration:fast. This is called ‘discretization’: continuous values (in our case: durations) are mapped to discrete values.

QBrowsCap: user-agent string → platform + browser

After spending a very long time looking for a C++ library to map user-agent strings to their corresponding browser name and version (and platform), I had to give up. No such library existed.
Because it is impossible to write a single, standardized routine that parses this information from the user-agent string, I had to rely on BrowsCap, the Browsers Capabilities project. This is the same dataset the PHP language relies on to identify browsers.

I have developed a C++ library that relies on BrowsCap to do just that — I baptized it ‘QBrowsCap’ because it is specifically optimized to be used with Qt-based projects.
QBrowsCap makes it easy to download this dataset, and keep it up-to-date. It parses the browscap.csv file and stores it in a SQLite database, which allows for faster mapping of user-agent strings (BrowsCap relies on ‘globbing’, and SQLite has built-in support for this). To maximize performance, it uses an in-memory hash table. QBrowsCap has also been made thread-safe, to allow for concurrent (i.e. by using a MapReduce-approach, implemented in C++/Qt with Qt’s QtConcurrent) user-agent details lookup by multiple threads (therefor allowing greater user-agent details lookup speeds).

Sample result

The user-agent string Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1) is mapped to

("ua:WinXP",
 "ua:WinXP:IE",
 "ua:WinXP:IE:6",
 "ua:WinXP:IE:6:0")

QGeoIP: IP address → location + ISP

Unfortunately, no library was available for Qt to map IP addresses to physical locations either. Fortunately, I did find a C library which I made easier to use by wrapping it in a Qt-friendly manner — I called the end result ‘QGeoIP’. QGeoIP also simplifies the build process of the C library by using Qt’s build system instead of an arcane Makefile. QGeoIP uses MaxMind’s libGeoIP.
I encountered one major problem with using libGeoIP though: GeoIP_delete() does not actually free the memory consumed by libGeoIP’s in-memory cache. I tried debugging this, but I can’t get it to work. Maybe it’s an OS X-specific issue? I did not try it on Linux. Likely related to these memory release issues, there is the problem that it seems to be impossible to make QGeoIP work in a thread-safe manner, thus unfortunately not allowing for concurrent IP to location + ISP mapping by using multiple threads.

Sample result

The IP address 218.56.155.59 is mapped to

("location:AS",
 "location:AS:China",
 "location:AS:China:Shandong",
 "location:isp:China:AS4837 CNCGROUP China169 Backbone")

EpisodesDurationDiscretizer: continuous episode durations → discrete speeds

The Episodes timing information contains <episode name>:<episode duration> pairs. It’s far more difficult to perform association rule mining to continuous data than to discrete data; therefor we discretize the continous data in these pairs: the episode durations. As explained in the introduction, we want to discretize these continuous episode durations to discrete speeds: duration:slow, duration:acceptable or duration:fast.
To do this, I wrote the EpisodesDurationDiscretizer class (.h/.cpp) class, which accepts a .csv file that defines the mappings. Such a .csv file looks like this:

domready,fast,150,acceptable,1000,slow
frontend,fast,100,acceptable,1500,slow
headerjs,fast,100,acceptable,1000,slow
footerjs,fast,100,acceptable,1000,slow
css,fast,100,acceptable,500,slow
DrupalBehaviors,fast,100,acceptable,200,slow
tabs,fast,10,acceptable,20,slow
ToThePointShowHideChangelog,fast,10,acceptable,20,slow

As you probably derived yourself, the first column contains the episode name, the second column contains the “speed name” for the fastest discretization, which goes from 0 ms to the value in the third column. As many discretizations as desired can be defined. In our case, there are three discretization levels for each episode. For example, these are the three discretization levels for the domready episode durations:

1. “fast”: 0—150 ms
2. “acceptable”: 151—1000 ms
3. “slow”: 1001—∞ ms

Sample result

The Episodes timing information

css:203,headerjs:94,footerjs:500,domready:843,tabs:110,ToThePointShowHideChangelog:15,DrupalBehaviors:141,frontend:1547

is mapped to

(("episode:css", "duration:acceptable"),
 ("episode:headerjs", "duration:fast"),
 ("episode:footerjs", "duration:acceptable"),
 ("episode:domready", "duration:acceptable"),
 ("episode:tabs", "duration:slow"),
 ("episode:ToThePointShowHideChangelog", "duration:acceptable"),
 ("episode:DrupalBehaviors", "duration:acceptable"),
 ("episode:frontend", "duration:slow"))

End result

Now that we can map meaningless strings and numbers to meaningful items, we can apply association rule mining. But more on that in a future blog post.

We will end here with looking at the result of a single line as it gets parsed and processed by my master thesis’ code.
We begin with:

"218.56.155.59 [Sunday, 14-Nov-2010 06:27:03 +0100] "?ets=css:203,headerjs:94,footerjs:500,domready:843,tabs:110,ToThePointShowHideChangelog:15,DrupalBehaviors:141,frontend:1547" 200 "http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1)" "driverpacks.net"

This gets parsed and processed into:

("episode:css", "duration:acceptable", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:headerjs", "duration:fast", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:footerjs", "duration:acceptable", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:domready", "duration:acceptable", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:tabs", "duration:slow", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:ToThePointShowHideChangelog", "duration:acceptable", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:DrupalBehaviors", "duration:acceptable", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0") 
("episode:frontend", "duration:slow", "url:http://driverpacks.net/driverpacks/windows/xp/x86/chipset/10.09", "location:AS", "location:AS:China", "location:AS:China:Shandong", "location:isp:China:AS4837 CNCGROUP China169 Backbone", "ua:WinXP", "ua:WinXP:IE", "ua:WinXP:IE:6", "ua:WinXP:IE:6:0")

As you can see, this single Episodes log file line results in eight transactions. The careful reader will have noticed this matches the number of episodes in the original Episodes log file line. More specifically, each episode gets its own transaction, along with its corresponding discretized speed and all request metadata (URL, location, ISP, platform, browser). (Note that this is a simple example; in the actual implementation, the HTTP status code is also included if it’s not a 200 status code and a ua:isMobile item is included in the transaction if it’s a mobile user agent.)
This is because we want to find associations for specific episodes’ speeds. Hence we need a transaction for each episode with its speed, plus all possible environmental factors that can cause this particular speed. On these resulting transactions, we can then apply association rule mining.

Conclusion

Both QBrowsCap and QGeoIP are unlicensed (as is the master thesis in its whole), so feel free to use them in your applications and contribute back! They also include unit tests and tiny sample applications that can easily be built with Qt Creator.

When integrated with my master thesis’ EpisodesParser, I’m able to achieve over 4,000 parsed & processed lines per second on my 2.66 GHz Core 2 Duo machine, resulting in ±40,000 transactions. Not bad! :)