IP数据库

项目放在github上,python版本ipdb_creator,java版本ip-locator

IP数据库生成

首先要知道IP的分配是一直变化的,所以不会存在绝对准确的IP库。IP库需要经常更新才能保证较高的准确度。IP的分配由国际非盈利性组织ICANN负责,所以要生成最新的IP库首先需要从这里下载5个最新原始分配文件,分别是delegated-arin-latest delegated-ripencc-latest delegated-lacnic-latest delegated-afrinic-latest delegated-apnic-latest

我们需要处理的是文件中ipv4的记录,每条记录的格式如下:

1
apnic|AU|ipv4|1.0.0.0|256|20110811|assigned
  • AU: 表示澳大利亚的简称
  • ipv4: 表示记录的ip类型
  • 1.0.0.0: 表示记录的起始IP
  • 256: 表示记录从起始IP往后256个地址
  • 20110811: 表示分配时间
  • assigned(allocated): 表示已分配

国家缩写与名字的对应关系,可以直接看python项目中的country_code文件。在大部分应用场景下,国内IP需要精确到省或者市级别,国外IP大部分只需要精确到国家级别。那怎么才能得到比较准确的国内IP库呢?

现在网上有很多免费的IP查询工具,有的比较友好提供了HTTP的查询接口。经过长时间的查询对比发现,其中IP淘宝17MON的准确率相对比较高。为了得到最全面的数据,我把delegated-apnic-latest中分配给CN的所有记录拿出来,然后对每条记录中的每个24网段进行扫描,最后把得到的中国全部24网段IP地址进行合并,就得到了国内IP库。对于IP分配中一些没有指明国家码的记录也可以用同样地方法。
要注意,大部分免费提供的IP查询接口都是对频率有限制的,如上面说的两个都是限制每个来源IP每秒10次的频率。

CN记录拆分为24网段

以一条记录为例 apnic|CN|ipv4|1.0.8.0|2048|20110412|allocated,把记录转换成CIDR格式1.0.8.0/21,以java为例:

1
2
3
4
5
6
7
8
9
10
String[] params = line.split("\\|");
// do filter ...
String baseIP = params[3];
int masklen = 32 - (int) (log(Integer.parseInt(params[4]), 2));
String netcidr = baseIP + "/" + masklen;
if (masklen > 24) masklen = 24;
IPv4Network networks = new IPv4Network(prefix);
for (String subnet : networks.getSubnet(24)) {
// query ...
}

可以看到关键的方法就是getSubnet(24),简单地说就是,从起始地址开始,每隔256个IP截断,最后就得到了对应的24网段列表。来看它的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<String> getSubnet(int masklen) {
if (masklen > 32 || masklen < 8 || masklen < numericCIDR) {
throw new NumberFormatException("masklen can not be greater than 32");
}
int numberOfIPs = 1 << (32 - masklen);
Long startIP = baseIPnumeric & netmaskNumeric;
List<String> list = new ArrayList<String>();
for (int i=0; i<Math.pow(2, masklen-numericCIDR); i++) {
String subnet = IPUtil.ipLong2String(startIP) + "/" + masklen;
startIP += numberOfIPs;
list.add(subnet);
}
return list;
}

查询及频率限制

以淘宝IP查询为例,接口可以在浏览器输入 http://ip.taobao.com/service/getIpInfo.php?ip=1.0.8.1 查看返回的结果,返回结果为json格式,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private IpData queryFromTaobao(String ip) throws Exception {
limitRate.check();
String ret = HttpClientPool.getInstance().getMethod(TAOBAO_URL + "?ip=" + ip, 5000);
if (ret == null) {
return null;
} else {
JSONObject json = JSON.parseObject(ret);
if (json.getInteger("code") == 0) {
JSONObject dataJson = json.getJSONObject("data");
IpData ipData = new IpData();
ipData.setCountry(dataJson.getString("country"));
ipData.setProvince(dataJson.getString("region"));
ipData.setCity(dataJson.getString("city"));
ipData.setIsp(dataJson.getString("isp"));
ipData.setIp(ip);
return ipData;
} else {
return null;
}
}
}

其中LimitRate是本地实现的一个简单频率控制,通过Queue接口实现一个限制队列大小的LimitQueue类,然后在一个单例的LimitRate中初始化一个LimitQueue队列,指定队列大小为10,时间间隔为1000ms。每次查询前先调用LimitRate的check方法,如果队列长度小于10,直接返回;等于10就从LimitQueue队列中取出队列顶部的时间(即最早进入队列的时间)与当前时间对比,若间隔小于1000ms,则sleep(1001-间隔ms数),最后把当前时间写入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void check() throws InterruptedException {
if (queue.size() < limit)
return;
Long first = queue.peek();
if (first == null)
return;
long now = System.currentTimeMillis();
if (now - first <= duration) {
logger.info("limit rate checked, sleep a while");
Thread.sleep(duration - now + first + 1);
}
queue.offer(now);
}

虽然对查询频率做了限制,但这并不保证接口的每一次查询都能正确返回结果,所以查询结果无效时应该重新查询,直到得到有效结果为止。

IP网段合并

最后需要对扫描的结果进行合并,由于扫描时全部拆分成24网段,而IP的分配又是不连续的,所以合并的时候要仔细,不要出错。首先要对扫描结果按IP排序,然后依次取出每一条结果,如果第n条与第n-1条的结果是相同的,则存入临时队列,直到当n与n-1的结果不同,这时把临时队列中的数据进行合并,合并结果存入最终的输出队列,并清空临时队列,循环此过程,最后就可以得到合并的结果。
以下面三条结果的合并为例:

1
2
3
1.0.1.0/24;中国;福建省;福州市;电信;1.0.1.123;256
1.0.2.0/24;中国;福建省;福州市;电信;1.0.2.20;256
1.0.3.0/24;中国;福建省;福州市;电信;1.0.3.247;256

(1) 首先对每一个网段的IP范围,如1.0.1.0/24的IPRange是1.0.1.0~1.0.1.255对应的long型范围是16777472-16777727,
1.0.2.0/24对应16777728-16777983,如果16777728 - 1 <= 16777727,则说明两个网段是连续的,则合并成新的IPRange:16777472-16777983,以此类推,最后得到16777472-16778239(如果网段中存在不连续的情况,则会得到多个IPRange)。

(2) 接着处理得到的IPRange(s),先把IPRange转换成能包含它本身的最小IP网段,16777472-16778239的startIP为16777472,endIP为16778239,n从1开始,n++直到满足

$$endIP - 2^n <= startIP$$

$$endIP - 2^{n-1} > startIP$$

得到结果startIP/(32-n)转换成可读形式:1.0.0.0/22。

(3) 最后,由于合并后网段包含范围超出了原本的三个网段,所以要对该结果再进行拆分。如果合并后的网段的起始IP小于合并前的起始IP,则以合并前的最小网段为界,把合并后网段拆分为小于,等于,大于合并前的最小网段的三个范围(合并后的网段的最大IP大于合并前的最大IP情况,也同理可推),这里的实现稍微有点复杂,通过代码来理解会比较容易一些,对应方法为IPUtil.cidrPartition()。最后得到合并后的网段:

1
2
1.0.1.0/24;中国;福建省;福州市;电信;1.0.3.247;256
1.0.2.0/23;中国;福建省;福州市;电信;1.0.3.247;512

IP数据库使用

完整的数据库已经生成,那么如何使用它呢?

RadixTree

RadixTree(基树)是通用的字典类型数据结构,在Linux内核及Nginx中被用于路由表的设计。RadixTree与传统的二叉树差不多,只是在寻找方式上,利用比如一个unsigned int的类型的每一个比特位作为树节点的判断。比如一个数 10001010101010100101010100101010按照Radix树的插入就是在根节点,如果遇到0,就指向左节点,如果遇到1就指向右节点,在插入过程中构造树节点,在删除过程中删除树节点。

插入

由于java中没有无符号整型,为了能表示最大的ipv4,我们用long型的低32位代替。key为ip的主机字节序,mask为网段的子网掩码,value为该网段的信息。以1.0.1.0/24为例,key=0x01000100,mask=0xFFFFFF00。从最高位开始,判断key的每一个位,1则前往右节点,0则前往左节点。如果当前节点不存在,则创建新的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public void put(long key, long mask, IpData value) {
long bit = 0x80000000L; // 128.0.0.0
int node = ROOT_PTR;
int next = ROOT_PTR;
// 从最高位开始,判断key的每一个位,1则前往右节点,0则前往左节点
while ((bit & mask) != 0) {
next = ((key & bit) != 0) ? rights[node] : lefts[node];
if (next == NULL_PTR) // 节点不存在,跳出循环
break;
bit >>= 1;
node = next;
}
if (next != NULL_PTR) {
// next不为NULL,是因bit&mask为0,也就是已经判断过key的最后一位,而退出上面的while的,则覆盖当前节点的值
values[node] = value;
return;
}
while ((bit & mask) != 0) {
if (size == allocatedSize)
expandAllocatedSize();
next = size; // 新增一个空节点
values[next] = NO_VALUE;
rights[next] = NULL_PTR;
lefts[next] = NULL_PTR;
if ((key & bit) != 0) {
rights[node] = next;
} else {
lefts[node] = next;
}
bit >>= 1;
node = next;
size++;
}
values[node] = value; // 最后走完key的所有位,到达目标节点,存入value
}

查找

如果明白插入的原理,那么查找就比较简单了。给定一个ip,首先将ip地址转换成主机字节序的四个字节,从32位的key的最高位开始,0就转向左节点,1就转向右节点,这样从树的根节点开始,直到找到对应的叶子节点为止,在此查找路径上最后一个值不为NO_VALUE的node的value就是查找的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public IpData selectValue(long key) {
long bit = 0x80000000L;
IpData value = NO_VALUE;
int node = ROOT_PTR;
while (node != NULL_PTR) {
if (values[node] != NO_VALUE)
value = values[node];
node = ((key & bit) != 0) ? rights[node] : lefts[node];
bit >>= 1;
}
return value;
}

结束

为了省点买IP付费数据库的钱,也不容易啊。方案还在进一步完善中,目前由于是单台机器,在1秒10次的频率限制下,完整跑一次需要的时间较长,正在考虑设置代理请求,加快查询频率,如果出口IP够多的话,可以大幅提高速度。