Click here to Skip to main content
Click here to Skip to main content

IP Country lookup in single Redis query

, 24 Feb 2014
Rate this:
Please Sign up or sign in to vote.
Method description for extremely fast country detection from IP address

Introduction 

This article shows how to achieve extremely fast IP lookup to fetch country (or any predefined data, actually) with single query from Redis.

Background  

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.

Description  

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.20.30.40 is 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: 

	0.0.0.10 - 0.0.0.19 Foo
	0.0.0.20 - 0.0.0.29 Bar 

we store 2 strings to Redis (to key named iplookup), with scores of 19 and 29:

	zadd iplookup 19 Foo
	zadd iplookup 29 Bar  

Having an IP from one of these ranges, e.g. 0.0.0.25 would product query:

	zrangebyscore iplookup 25 4294967296 limit 0 1

and return Bar:

redis 127.0.0.1:6379> zadd iplookup 19 Foo
(integer) 1
redis 127.0.0.1:6379> zadd iplookup 29 Bar
(integer) 1
redis 127.0.0.1:6379> zrangebyscore iplookup 25 4294967296 limit 0 1
1) "Bar"
redis 127.0.0.1:6379>  

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

History  

24 Feb 2014: v1.1 - Added info about string uniqueness 

22 Feb 2014: v1.0 - Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Kamil Burzynski
Chief Technology Officer CodeProject Europe
Poland Poland

Kamil has been programming various devices since 1989, using C++/C, assembler (6502, M68k, PowerPC, SH4, ...), Java, Javascript, Objective-C, Ruby, C#, and much more. He actively avoided web development for a very long time, but web development is almost all that he does now. Except for the times when he puts on his Linux administrator hat.
For many years he was leading various development teams, and is currently focusing on growing the Polish branch of the CodeProject.

Kamil likes playing the Chinese board game named Go and exploring the mathematical side of Forex trading.

Follow on   Twitter

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web02 | 2.8.140721.1 | Last Updated 24 Feb 2014
Article Copyright 2014 by Kamil Burzynski
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid