ip2region file structure and principle

ip2region - 最自由的ip地址查询库,ip到地区的映射库,提供Binary,B树和纯内存三种查询算法,妈妈再也不用担心我的ip地址定位。

1. 99.9%准确率,定时更新:

数据聚合了一些知名ip到地名查询提供商的数据,这些是他们官方的的准确率,经测试着实比纯真啥的准确多了。

每次聚合一下数据需要1-2天,会不定时更新。

2. 标准化的数据格式:

每条ip数据段都固定了格式:城市Id|国家|区域|省份|城市|ISP

只有中国的数据精确到了城市,其他国家只能定位到国家,后前的选项全部是0,已经包含了全部你能查到的大大小小的国家。
(请忽略前面的城市Id,个人项目需求)

3. 体积小:

生成的数据库文件ip2region.db只有1.5M(1.2版本前是3.5M)

4. 多查询客户端的支持,0.0x毫秒级别的查询

已经集成的客户端有:java, php, c, python,nodejs,php扩展(支持linux, php5, php7版本已支持),golang。

提供了两种查询算法,响应时间如下:
客户端/binary算法/b-tree算法/Memory算法:
java/0.x毫秒/0.x毫秒/0.1x毫秒 (使用RandomAccessFile)
php/0.x毫秒/0.1x毫秒/0.1x毫秒
c/0.0x毫秒/0.0x毫秒/0.00x毫秒(b-tree算法基本稳定在0.02x毫秒级别)
python/0.x毫秒/0.1x毫秒/未知

任何客户端b-tree都比binary算法快,当然Memory算法固然是最快的!

5. 测试程序:
java:

cd binding/java
ant all
java -jar ip2region-{version}.jar ./data/ip2region.db

php:

php binding/php/testSearcher ./data/ip2region.db

c:

cd binding/c/
gcc -g -O2 testSearcher.c ip2region.c
./a.out ../../data/ip2region.db

python:

python binding/python/testSearcher ./data/ip2region.db

均会看到如下界面:

initializing  B-tree ...
+----------------------------------+
| ip2region test script            |
| Author: chenxin619315@gmail.com  |
| Type 'quit' to exit program      |
+----------------------------------+
p2region>> 101.105.35.57
2163|中国|华南|广东省|深圳市|鹏博士 in 0.02295 millseconds

输入ip地址开始测试,第一次会稍微有点慢,在运行命令后面接入binary,memory来尝试其他算法,建议使用b-tree算法,速度和并发需求的可以使用memory算法。

具体集成请参考不同客户端的测试源码。

6. 如何生成ip2region.db文件

从ip2region 1.2.2版本开始里面提交了一个dbMaker-{version}.jar的可以执行jar文件,用它来完成这个工作:

  • 1, 确保你安装好了java环境(不玩Java的童鞋就自己谷歌找找拉,临时用一用,几分钟的事情)
  • 2, cd到ip2region的根目录,然后运行如下命令:
1
2
3
4
5
java -jar dbMaker-{version}.jar -src 文本数据文件 -region 地域csv文件 [-dst 生成的ip2region.db文件的目录]

# 文本数据文件:db文件的原始文本数据文件路径,自带的ip2region.db文件就是/data/ip.merge.txt生成而来的,你可以换成自己的或者更改/data/ip.merge.txt重新生成
# 地域csv文件:该文件目的是方便配置ip2region进行数据关系的存储,得到的数据包含一个city_id,这个直接使用/data/origin/global_region.csv文件即可
# ip2region.db文件的目录:是可选参数,没有指定的话会在当前目录生成一份./data/ip2region.db文件
  • 3, 获取生成的ip2region.db文件覆盖原来的ip2region.db文件即可
  • 4, 默认的ip2region.db文件生成命令:
1
2
3
4
cd ip2region项目根目录
java -jar dbMaker-1.2.2.jar -src ./data/ip.merge.txt ./data/global_region.csv

# 会看到一大片的输出

一. 源数据如何存储到ip2region.db

1. 源数据来源与结构

ip2region 的ip数据来自纯真和淘宝的ip数据库,每次抓取完成之后会生成 ip.merge.txt, 再通过程序根据这个源文件生成ip2region.db 文件。

ip.merge.txt 中每一行对应一条完整记录,每一条记录由ip段和数据组成,格式如下:

0.0.0.0|0.255.255.255|未分配或者内网IP|0|0|0|0
1.0.0.0|1.0.0.255|澳大利亚|0|0|0|0
1.0.1.0|1.0.3.255|中国|华东|福建省|福州市|电信
1.0.4.0|1.0.7.255|澳大利亚|0|0|0|0
1.0.8.0|1.0.15.255|中国|华南|广东省|广州市|电信
1.0.16.0|1.0.31.255|日本|0|0|0|0
1.0.32.0|1.0.63.255|中国|华南|广东省|广州市|电信
1.0.64.0|1.0.127.255|日本|0|0|0|0
1.0.128.0|1.0.255.255|泰国|0|0|0|0
1.1.0.0|1.1.0.255|中国|华东|福建省|福州市|电信
从左到右分别表示: 起始ip,结束ip,国家,区域,省份,市,运营商。无数据区域默认为0。

最新的ip.merge.txt 有122474条记录,并且根据开始ip地址升序排列。

2. 如何生成ip2region.db

给定一个ip,如何快速从ip.merge.txt中找到该ip所属记录?最简单的办法就是顺序遍历,当该ip在某条记录起始和结束ip之间时,即命中。

这是低效的做法,如何提高查询性能?用过mysql和其他数据库的的都知道,使用索引。所以ip2region.db使用了内建索引,直接将性能提升到0.0x毫秒级别。

根据ip.merge.txt,为所有数据生成一份索引,并和数据地址组成一个索引项(index block), 然后按起始ip升序排列组成索引,并存储到数据文件的末尾,最终生成的ip2region.db文件大小只有3.5M。

此时的数据库文件中的每一条索引都指向一条对应的数据,也就是说如

|中国|华南|广东省|广州市|电信
这样的数据在文件中被重复存储了很多次,再经过去重优化之后,ip2region.db只有1.5M了,此时把数据库文件全部读取到内存再查找都是非常可行的。

二. ip2region.db 结构

生成 ip2region.db 的时候,首先会在首部预留 8 bytes 的SUPER BLOCK 和 8k 的 HEADER INDEX。

再根据ip.merge.txt,依据每一条记录的起始ip, 结束ip和数据,生成一个index block, 前四个字节存储起始ip, 中间四个字节存储结束ip, 后四个字节存储已经计算出的数据地址,并暂存到INDEX区。

当 INDEX 索引区和 DATA 数据区确定下来之后,再把 INDEX 的起始位置存储到 SUPER BLOCK 的前四个字节,结束位置存储到 SUPER BLOCK 的后四个字节。

再把 INDEX 分成大小为 4K 的索引分区,把每个分区起始位置的索引的起始ip和该索引的位置存入一个 header index block, 组成 HEADER INDEX 区域, 最后写入ip2region.db。

  • SUPER BLOCK

用来保存 INDEX 的起始地址和结束地址,first index ptr 指向INDEX起始位置的index block, last index ptr 指向最后一个index block的地址。这样查询的时候直接读取superblock 8个字节,就能快速获取 INDEX 索引区域的地址。

  • HEADER INDEX

HEADER INDEX 区是对 INDEX 区的二级索引, INDEX总长度除以 4K 就是 HEADER INDEX 的实际索引数。

该区域长度为8k, 由 8 bytes 的 header index block 组成。

header index block 前四个字节存储每个4K分区起始位置的index block 的起始ip值,后四个字节指向该index block的地址。

把HEADER INDEX 区定义为8k,可以通过一次磁盘读取读取整个HEADER INDEX 区,然后在内存中进行查询,查询的结果可以确定该ip在INDEX区的某个4k分区内,然后再根据地址一次读取4k index 到内存,再在内存中查询,从而减少磁盘读取的次数。

  • DATA

保存的数据,数据格式如下:

2163|中国|华南|广东省|深圳市|鹏博士
分别表示 城市ip,国家,区域,省份,城市,运营商

  • INDEX

索引区域,索引元素为 index block (12 字节), 分成三个部分,起始ip, 结束ip, 数据信息, 每一条 index block 对应 ip.merge.txt 中的一条记录。

数据信息:前一个字节保存数据长度, 后三个字节保存数据地址(DATA中)。

每个index block 表示一个ip段的索引。当指定ip 在某个 index block 的起始ip和结束ip中间,即表示命中索引。

再通过 index block 中的数据地址和数据长度,就能从ip2region.db读取对应的地址。

三. 搜索方法

binary搜索

  • 把ip值通过ip2long方法转为长整型
  • 通过 SUPER BLOCK 拿到INDEX的起始位置和结束位置
  • 相减+1得出index block 总数
  • 采用二分法直接求解,比较 index block 和当前ip的大小,即可找到该ip属于的 index block
  • 拿到该 index block 的后面四个字节, 分别得到数据长度和数据地址
  • 从数据地址读取拿到的所得长度的字节,即是搜索结果

b-tree 搜索

  • 把ip值通过ip2long 转为长整型
  • 使用二分法在 HEADER INDEX 中搜索,比较得到对应的 header index block
  • header index block 指向 INDEX 中的一个 4K 分区,所以直接把搜索范围降低到 4K
  • 采用二分法在获取到的 4K 分区搜索,得到对应的 index block
  • 拿到该 index block 的后面四个字节, 分别得到数据长度和数据地址
  • 从数据地址读取拿到的所得长度的字节,即是搜索结果