On efficiently geo-referencing IPs with MaxMind GeoIP and MySQL GIS
Geo-referencing IPs is, in a nutshell, converting an IP address, perhaps from an incoming web visitor, a log file, a data file, or some other place, into the name of some entity owning that IP address. There are a lot of reasons you may want to geo-reference IP addresses to country, city, etc., such as in simple ad targeting systems, geographic load balancing, web analytics, and many more applications.
This is a very common task, but I have never actually seen it done efficiently in MySQL in the wild. There is a lot of questionable adviceon forums, blogs, and other sites out there on this topic. After working with a Proven Scaling customer, I recently did some thinking and some performance testing on this problem, so I thought I would publish some hard data and advice for everyone.
Unfortunately, R-tree (spatial) indexes have not been added to InnoDB yet, so the tricks in this entry only work efficiently with MyISAM tables (although they should work with InnoDB, they will perform poorly). This is actually OK for the most part, as the geo-referencing functionality most people need doesn’t really need transactional support, and since the data tables are basically read-only (monthly replacements are published), the likelyhood of corruption in MyISAM due to any server failures isn’t very high.
The data provided by MaxMind
MaxMind is a great company that produces several geo-referencing databases. They release both a commercial (for-pay, but affordable) product called GeoIP, and a free version of the same databases, called GeoLite. The most popular of their databases that I’ve seen used is GeoLite Country. This allows you look up nearly any IP and find out which country (hopefully) its user resides in. The free GeoLite versions are normally good enough, at about 98% accurate, but the for-pay GeoIP versions in theory are more accurate. In this article I will refer to both GeoIP and GeoLite as “GeoIP” for simplicity.
GeoIP Country is available as a CSV file containing the following fields:
- ip from, ip to (text) — The start and end IP addresses as text in dotted-quad human readable format, e.g. “3.0.0.0″. This is a handy way for a human to read an IP address, but a very inefficient way for a computer to store and handle IP addresses.
- ip from, ip to (integer) — The same start and end IP addresses as 32-bit integers1, e.g. 50331648.
- country code — The 2-letter ISO country code for the country to which this IP address has been assigned, or in some cases other strings, such as “A2″ meaning “Satellite Provider”.
- country name — The full country name of the same. This is redundant with the country code if you have a lookup table of country codes (including MaxMind’s non-ISO codes), or if you make one from the GeoIP data.
A simple way to search for an IP
Once the data has been loaded into MySQL (which will be explained in depth later), there will be a have a table with a range (a lower and upper bound), and some metadata about that range. For example, one row from the GeoIP data (without the redundant columns) looks like:
| ip_from | ip_to | country_code |
| 50331648 | 68257567 | US |
The natural thing that would come to mind (and in fact the solutionoffered by MaxMind themselves2) is BETWEEN. A simple query to search for the IP 4.2.2.1 would be:
SELECT country_code
FROM ip_country
WHERE INET_ATON("4.2.2.1") BETWEEN ip_from AND ip_to
Unfortunately, while simple and natural, this construct is extremely inefficient, and can’t effectively use indexes (although it can use them, it isn’t efficient). The reason for this is that it’s an open-ended range, and it is impossible to close the range by adding anything to the query. In fact I haven’t been able to meaningfully improve on the performance at all.
A much better solution
While it probably isn’t the first thing that would come to mind,MySQL’s GIS support is actually perfect for this task. Geo-referencing an IP address to a country boils down to “find which range or ranges this item belongs to”, and this can be done quite efficiently usingspatial R-tree indexes in MySQL’s GIS implementation.
The way this works is that each IP range of (ip_from, ip_to) is represented as a rectangular polygon from (ip_from, -1) to (ip_to, +1) as illustrated here:
In SQL/GIS terms, each IP range is represented by a 5-point rectangular POLYGON like this one, representing the IP range of 3.0.0.0 – 4.17.135.31:
POLYGON(( 50331648 -1, 68257567 -1, 68257567 1, 50331648 1, 50331648 -1 ))
The search IP address can be represented as a point of (ip, 0), and that point with have a relationship with at least one of the polygons (provided it’s a valid IP and part of the GeoIP database) as illustrated here:
It is then possible to search these polygons for a specific point representing an IP address using the GIS spatial relationship functionMBRCONTAINS and POINT3 to search for “which polygon contains this point” like this:
SELECT country_code
FROM ip_country
WHERE MBRCONTAINS(ip_poly, POINTFROMWKB(POINT(INET_ATON('4.2.2.1'), 0)))
Pretty cool huh? I will show how to load the data and get started, then take look at how it performs in the real world, and compare the raw numbers between the two methods.
Loading the data and preparing for work
First, a table must be created to hold the data. A POLYGON field will be used to store the IP range. Technically, at this point the ip_from andip_to fields are unnecessary, but given the complexity of extracting the IPs from the POLYGON field using MySQL functions, they will be kept anyway. This schema can be used to hold the data4:
CREATE TABLE ip_country ( id INT UNSIGNED NOT NULL auto_increment, ip_poly POLYGON NOT NULL, ip_from INT UNSIGNED NOT NULL, ip_to INT UNSIGNED NOT NULL, country_code CHAR(2) NOT NULL, PRIMARY KEY (id), SPATIAL INDEX (ip_poly) );
After the table has been created, the GeoIP data must be loaded into it from the CSV file, GeoIPCountryWhois.csv, downloaded from MaxMind. The LOAD DATA command can be used to do this like so:
LOAD DATA LOCAL INFILE "GeoIPCountryWhois.csv"
INTO TABLE ip_country
FIELDS
TERMINATED BY ","
ENCLOSED BY """
LINES
TERMINATED BY "n"
(
@ip_from_string, @ip_to_string,
@ip_from, @ip_to,
@country_code, @country_string
)
SET
id := NULL,
ip_from := @ip_from,
ip_to := @ip_to,
ip_poly := GEOMFROMWKB(POLYGON(LINESTRING(
/* clockwise, 4 points and back to 0 */
POINT(@ip_from, -1), /* 0, top left */
POINT(@ip_to, -1), /* 1, top right */
POINT(@ip_to, 1), /* 2, bottom right */
POINT(@ip_from, 1), /* 3, bottom left */
POINT(@ip_from, -1) /* 0, back to start */
))),
country_code := @country_code
;
During the load process, the ip_from_string, ip_to_string, andcountry_string fields are thrown away, as they are redundant. A few GIS functions are used to build the POLYGON for ip_poly from theip_from and ip_to fields on-the-fly. On my test machine it takes about 5 seconds to load the 96,641 rows in this month’s CSV file.
At this point the data is loaded, and everything is ready to go to use the above SQL query to search for IPs. Try a few out to see if they seem to make sense!
Performance: The test setup
In order to really test things, a bigger load testing framework will be needed, as well as a few machines to generate load. In my tests, the machine being tested, kamet, is a Dell PowerEdge 2950 with Dual Dual Core Xeon 5050 @ 3.00Ghz, and 4GB RAM. We have four test clients, makalu{0-3}, which are Apple Mac Mini with 1.66Ghz Intel CPUs and 512MB RAM. The machines are all connected with aNetgear JGS524NA 24-port GigE switch. For the purposes of this test, the disk configuration is not important. On the software side, the server is running CentOS 4.5 with kernel 2.6.9-55.0.2.ELsmp. The Grinder 3.0b32 is used as a load generation tool with a custom Jython script and Connector/J 5.1.5 to connect to MySQL 5.0.45.
There are a few interesting metrics that I tested for:
- The latency and queries per second with a single client repeatedly querying.
- Does the number of queries handled increase as the number of clients increases?
- Is latency and overall performance adversely affected by many clients?
The test consisted of an IP search using the two different methods, and varying the number of clients between 1 and 16 in the following configurations:
| Clients | Machines | Threads |
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 4 | 1 | 4 |
| 8 | 2 | 4 |
| 16 | 4 | 4 |
Each test finds the country code for a random dotted-quad format IP address passed in as a string.
How does it perform? How does it compare?
There are a few metrics for determining the performance of these searches. If you tried the BETWEEN version of this query, you may have noticed that, in terms of human time, it doesn’t take very long anyway: I pretty consistently got 1 row in set (0.00 sec). But don’t let that fool you.
It’s clear that GIS wins hands down.
First, a look at raw performance in terms of queries per second.
Using BETWEEN, we max out at 264q/s with 16 clients:
Using MBRCONTAINS, we max out at 17600q/s with 16 clients, and it appears that it’s the test clients that are maxed out, not the server:
Next, a look at latency of the individual responses.
Using BETWEEN, we start out with a single client at 15.5ms per request, which is not very good, but still imperceptible to a human. But with 16 clients, the latency has jumped to 60ms, which is longer than many web shops allocate to completely construct a response. As the number of test clients increases, the latency gets much worse, because the query is so dependent on CPU:
Using MBRCONTAINS, we start out with a single client at 0.333ms per request, and even with 16 clients, we are well under 1ms at 0.743ms:
Conclusion
Definitely consider using MySQL GIS whenever you need to search for a point within a set of ranges. Performance is fantastic, and it’s relatively easy to use. Even if you are an all-InnoDB shop, as most of our customers are (and we would recommend), it may very well be worth it to use MyISAM specifically for this purpose.
Update 1: Another way to do it, and a look at performance
Andy Skelton and Nikolay Bachiyski left a comment below suggesting another way this could be done:
SELECT country_code
FROM ip_country
WHERE ip_to >= INET_ATON('%s')
ORDER BY ip_to ASC
LIMIT 1
This version of the query doesn’t act exactly the same as the other two — if your search IP is not part of any range, it will return the next highest range. You will have to check whether ip_from is <= your IP within your own code. It may be possible to do this in MySQL directly, but I haven’t found a way that doesn’t kill the performance.
Andy’s version actually performs quite well — slightly faster and more scalable than MBRCONTAINS. I added two new performance testing configurations to better show the differences between the two:
| Clients | Machines | Threads |
| 32 | 4 | 8 |
| 64 | 4 | 16 |
Here’s a performance comparison of MBRCONTAINS vs. Andy’s Method:
Latency (ms) — Lower is better:
Queries per second — Higher is better:
Once I get some more time to dig into this, I will look at why exactlyBETWEEN is so slow. I’ve also run into an interesting possible bug in MySQL: If you add a LIMIT 1 to the BETWEEN version of the query, performance goes completely to hell. Huh?
Thanks for the feedback, Andy and Nikolay.
No comments:
Post a Comment