This article shows how to achieve extremely fast IP lookup to fetch country (or any predefined data, actually) with single query from Redis.
Redis sorted hash data structure is used. It basically contains a set of strings, each string having its own score. See more at Redis site.
The main idea is to store each IP range as a separate string (with score) in sorted set. We do encode IP address into score, and the string can contain any data we want to attach to given IP range (e.g. just the country name, or some JSON string).
Since Redis assigns single score to each string, you need to make sure that all your strings are unique, e.g. if you are storing 2-3 letters containing country codes, add some unique suffix to each string instance, then strip it after fetching from redis.
For each range we will store end of range (its last IP address) as a score of the range.
Then, when we will want to lookup data associated with given IP we will ask Redis to give us string with smallest score bigger than our IP. That's it.
We do calculate score from IP just by treating it as 32-bit integer: integer for
10*256*256*256 + 20*256*256 + 30*256 + 40 = 169090600
The query itself is just asking redis to obtain all strings with scores between value of given IP and end of last range (4 294 967 296 in our case), then to return first string.
For example, with these IP ranges defined:
<pre><span class="Apple-tab-span" style="white-space: pre;"> </span>0.0.0.10 - 0.0.0.19 Foo<br /><span class="Apple-tab-span" style="white-space: pre;"> </span>0.0.0.20 - 0.0.0.29 Bar </pre>
we store 2 strings to Redis (to key named
iplookup), with scores of
<span class="Apple-tab-span" style="white-space: pre;"> </span>zadd iplookup 19 Foo<br /><span class="Apple-tab-span" style="white-space: pre;"> </span>zadd iplookup 29 Bar
Having an IP from one of these ranges, e.g.
0.0.0.25 would product query:
<span class="Apple-tab-span" style="white-space: pre;"> </span>zrangebyscore iplookup 25 4294967296 limit 0 1
redis 127.0.0.1:6379> zadd iplookup 19 Foo
redis 127.0.0.1:6379> zadd iplookup 29 Bar
redis 127.0.0.1:6379> zrangebyscore iplookup 25 4294967296 limit 0 1
The nuance is that the IP addresses which are outside of any known ranges will be detected as belonging to the next range closest to them. If you are concerned about this, you probably should fill in the gaps between ranges with your defaults.
This technique can be used for various things, basically everywhere where you have some ranges defined and you need to quickly verify to which range given member does belong.
I have also created small Node.js utility to import country data into Redis, in the format described above. You can found it in this repository.
24 Feb 2014: v1.1 - Added info about string uniqueness
22 Feb 2014: v1.0 - Initial version