使用Python和DB-IP免费数据库实现IP地理位置的查询。复习一下二分查找算法。
我在工作中负责系统的日志部分，正好又对数据分析和挖掘有些兴趣，所以想利用最近比较空闲的这段时间做一些日志分析方面的工作。之前没有太多经验，先从一些简单的东西入手：看看用户的地理分布情况。接入层日志中带有请求来源的IP地址，我要做的就是提取请求IP，转换成对应的地理位置，然后按区域统计。这里介绍一下我获取地理位置的方法。
首先需要一个IP数据库。谷歌之后有3个选择：国外的DB-IP、MaxMind和国内的IPIP。其中后两者不但提供免费的数据库下载，还有封装好的Python接口可以直接使用。不过什么都是拿来主义，就没意思了。所以我决定使用DB-IP的数据库，自己实现查找。这里使用DB-IP的城市级IP数据库。数据库以纯文本的csv格式提供，每一行包含5列，对应一个IP地址段的起始地址、终止地址和国家、省份、城市等位置信息。下面是几个例子：
"1.0.8.0","1.0.15.255","CN","Guangdong","Guangzhou"
"1.0.16.0","1.0.31.255","JP","Tokyo","Chiyoda"
"1.0.32.0","1.0.63.255","CN","Guangdong","Guangzhou"
"1.0.64.0","1.0.127.255","JP","Hiroshima","Hiroshima"
DB-IP的数据库按照IP地址升序排列，因此这是个典型的有序序列查找问题，可以用二分查找来解决。首先要把文件读进内存建立索引。IP地址其实是一个四字节（32位）的整数[1]，写成“192.168.1.1”这种形式只是为了方便人的阅读和记忆，现在既然要让机器来处理，不妨把它再转换成整数。下面代码实现了这个转换过程。
from struct import pack, unpack
def ip2int(ip_str):
b = map(lambda x: int(x), ip_str.split('.'))
buf = pack('!BBBB', b[0], b[1], b[2], b[3])
o = unpack('!I', buf)[0]
return o
ip2int()函数的第一行将IP字符串按“.”分割成四部分，分别转换成整数，然后放入一个list。这里使用了两个函数式编程的小技巧，让代码更简洁一些：
- map()函数。第一个参数是函数f，第二个参数是一个iterable对象（可以是list、tuple等），map函数将对参数2中的每一个对象调用函数f。
- lambda表达式。即匿名函数，lambda x表示该函数接受一个参数x，函数返回值就是“:”后面的表达式的值。
第二行将4个整数打包（pack）到一段4字节的缓冲区中，每个整数占一个字节，并以网络序存放，第三行再以32位无符号整数（unsigned int）的形式将缓冲区解包（unpack）。这段利用了Python标准库中的struct包提供的pack()和unpack()两个函数，实现了将4个单字节整数合并成一个4字节整数的过程。如果用传统的写法，代码可能是下面这个样子：
o = 0
for x in b:
o = o << 8
o |= x
return o
load_ipdb()函数把数据库文件读入内存，每行记录转换成一个元组（tuple）：(ip_start, ip_end, location)，将所有元组依次追加到一个列表（list）中。由于文件本身是有序的，我们就得到了一个有序的索引。
def load_ipdb(file_path):
ip_range_list = []
with open(file_path) as f:
for line in f:
fields = line.strip().split(',')
fields = [f[1:-1] for f in fields]
if len(fields) != 5:
stderr.write(line)
continue
ip_start, ip_end, nation, province, city = fields
ip_start = ip2int(ip_start)
ip_end = ip2int(ip_end)
ip_range_list.append((ip_start, ip_end, province, city))
return ip_range_list
接下来就可以使用二分查找算法，根据给定的IP地址，找到对应的地址段，从而确定其地理位置。
def ip_lookup(ip_range_list, ip):
ip_bin = ip2int(ip)
min_idx = 0
max_idx = len(ip_range_list)
mid = 0
while True:
if min_idx > max_idx:
break
mid = (min_idx + max_idx) / 2
entry = ip_range_list[mid]
if ip_bin > entry[1]:
min_idx = mid + 1
continue
elif ip_bin < entry[0]:
max_idx = mid - 1
continue
else:
break
if ip_bin >= entry[0] and ip_bin <= entry[1]:
return entry[2]
else:
return None
DB-IP的数据库包含了全球的IP地址，有630MB。而实际上我们感兴趣的只是国内的部分，可以先筛选出国家代码为CN的记录，只需要一条grep命令，就可以大大缩短日志统计时查找地理位置的时间。最后附上一张根据统计结果绘制的热度图。绘图使用的是百度ECharts。可以看到，来自广东的请求数量完爆其他省份，其次则是河南、河北、山东和江苏这一片区域。用户的热度分布大致上跟各省的人口情况是相符的。
-
这里只讨论IPv4，IPv6地址为6个字节。 ↩
