纯真ip数据库怎么使用（纯真网络ip地址查询）
在移动互联网的应用中，经常需要根据用户的位置信息等做一些用户侧信息的统计分析。而要拿到用户的位置信息，一般有两个方法： gps 定位的信息和用户 ip 地址。由于每个手机都不一定会打开 gps，而且有时并不太需要太精确的位置（到城市这个级别即可），所以根据 ip 地址入手来分析用户位置是个不错的选择。 要做到这个功能得需要一个 ip 和地理位置的映射关系库，并依赖这个库启动一个 ip 转地理位置的服务。本文从需求入手，结合 github 上拥有 8.4k 星的 ip2region 来分析映射关系库的设计以及 ip 如何快速转换成地理位置。
介绍
ip 定位服务很常见，而且很多公司都提供了类似的付费服务，比如阿里，高德，百度等，当然也有公开的免费服务，像 geoip，纯真ip等。这些服务要么通过 html 页面解析，要么通过接口请求，但不管怎样都离不开一次 http 请求，更不用说大部分服务都对 qps 作了限制。下表枚举了一些常见的通过 ip 获取地址的方式。
在日常工作通常需要将大量用户请求日志中 ip 转换成用户位置信息，用作后续的分析。这其中的关键是数据量大，处理要快。显然每次都通过请求 api 公共服务的方式无法满足我们的日常需求。
暴力生成 ip 库
对于日常的需求，一种简单粗暴的做法就是提前通过 api 获取所有公网 ip 对应的位置信息，按照下面的 tips 中我们可以估算出如果通过访问淘宝ip地址库来遍历 3.3 亿的国内 ip 地址要 10 年。如果是高德的企业用户遍历国内 ip 地址大概要 11 天。感觉这个 11 天还是能够接受的。
tips: ipv4
目前所说的 ip 地址是指 ipv4，它是使用 32 位（4 字节）地址，因此地址空间约有 42.9 亿$2^32=4294967296$个, 不过一些地址是作为特殊用途所保留的，如专用网络（约 1800 万个）和多播地址（约 2.7 亿个），这些减少了可在互联网上路由的地址数量。 据 wiki 上统计，中国的 ipv4 数量达到 3.3 亿，而美国有 15.4 亿个。
这里我们约定一下位置信息的数据格式： 国家|区域|省份|城市|isp，如果接口中返回的字段没有对应的信息，则对应的字段填充0。那么我们通过顺序请求 api 服务可以获取到如下文件数据（地址依次递增）：
0.0.0.0|0|0|0|内网ip|内网ip
0.0.0.1|0|0|0|内网ip|内网ip
...
1.0.15.255|中国|0|广东省|广州市|电信
...
255.255.255.255|0|0|0|内网ip|内网ip
只要有了这个文件，可以将其读到内存中，使用字典保存，键为 ip 地址，值为位置信息。程序可以在 o(1) 时间复杂度内返回位置信息，不过该程序或文件占用的大小我们可以粗略的计算一下。 假定我们使用 utf-8 进行存储，一条记录最短的情况是 0.0.0.0|0|0|0|0|0，占用17个字节，ip 库文件的大小为 17*4294967296 = 73014444032 b = 71303mb = 71gb。这个大小是任意一个程序不能接受的。
空间优化
ip 库文件优化
从上面的文件数据发现大量的相邻 ip 拥有相同的位置信息（客户在申请一段 ip 地址都会尽量连在一起），所以我们可以将这样的记录合成一条记录。如下文件数据（地址段依次递增）：
0.0.0.0|0.255.255.255|0|0|0|内网ip|内网ip
...
1.0.8.0|1.0.15.255|中国|0|广东省|广州市|电信
...
224.0.0.0|255.255.255.255|0|0|0|内网ip|内网ip
ip2region 库中最新的 ip.merge.txt 共有 658207 记录，文件大小 39 m。
ip地址优化
从上面的文件数据发现大量的ip地址以字符串形式存储，而 ipv4 是使用 32 位地址。所以将其转换成整型进行存储可以大大节省空间，比如像最短的字符串 0.0.0.0 占据 7 字节，最长的字符串 111.111.111.111 占据 15 字节，如果将其转换成整型，他们都占据 4 字节。0.0.0.0 是 int(0), 111.111.111.111 是 int(1869573999)。
位置信息优化
从上面的文件数据发现相同的位置信息会对应不同的 ip 段（客户可能在不同的时间段去申请 ip 段），所以还是有大量的位置信息在 ip 库文件中，在内存中我们可以只保留一份位置信息，并使用指针或者文件偏移量+数据长度来获取对应的位置信息。
优化后的ip库
根据上面的优化，我们可以生成最终的ip库：ip2region.db，该文件只有8.1m。
ip库的结构
ip 库文件ip2region.db的结构分为四个部分：super 块， header索引区，数据区，索引区。具体如下图所示：
- super 块
用来保存索引块的起始地址和结束地址，第一个索引指针指向索引块的开始位置，也就是第一个索引分区的第一个索引块， 最后一个索引指针 指向索引块的结束位置-12，也就是最后一个索引分区的最后一个索引块的头地址。这样查询的时候直接读取super块 8 个字节，就能快速获取索引块的地址范围。 - header 索引区
header索引是对索引块的二级索引，专门为b+tree搜索服务的。索引区总长度除以索引分区长度12*(1024*8/12-1)就是 header 索引的实际索引数。该区域大小为 2048*8 bytes, 由 2048 个 8 bytes 的 header 索引块组成。header索引块前四个字节存储每个索引分区第一个索引块的起始ip值，后四个字节指向该索引块的地址。
header索引区之所以定义为接近16k，是因为可以通过四次磁盘读取读取整个header索引区，然后在内存中进行查询，查询的结果可以确定该ip在索引区的某个索引分区内，然后再根据地址两次读取8k 索引分区到内存，再在内存中查询，从而减少磁盘读取的次数。 - 数据区
保存的数据，数据格式如下：中国|华南|广东省|深圳市|鹏博士， 分别表示国家，区域，省份，城市，运营商 - 索引区
索引区是由索引块构成， 每个索引块占 12 字节，包括起始ip, 结束ip, 数据信息。数据信息中前三个字节保存数据地址，后一个字节保存数据长度。 每一条索引块对应 ip.merge.txt 中的一条记录，表示一个 ip 段的索引。在检索中当指定 ip 在某个索引块的起始ip和结束ip中间，即表示命中索引。再通过索引块中的数据地址和数据长度，就能从 ip2region.db 读取对应的位置信息数据。
ip库的生成
ip2region 的 github 仓库中提供了 ip2region.db 的生成过程，是用 java 写的，其类图如下所示：
通过熟悉生成 ip2region.db 的源码，简述一下其生成过程如下：
- 通过 randomaccessfile 在文件中预留 8 bytes 的 super 块和 2048*8 bytes 的 header 索引区
- 扫描 ip.merge.txt 文件，对每一条记录作如下处理：
依据每一条记录的起始ip, 结束ip 和数据，生成一个索引块， 前四个字节存储起始ip, 中间四个字节存储结束ip, 后四个字节存储已经计算出的数据地址（通过 randomaccessfile 写入，这里维护一个位置信息到文件位置的字典，保证同一个位置信息只写入一次。），并将索引块暂存在 indexpool 链表中。这一步会将数据区的所有位置信息确定。 - 扫描完 ip.merge.txt 中所有的记录， 将 indexpool 中所有的索引块写到数据区后面。在此过程中将 int(1024*8/12-1)= 681 个索引块组成一个索引分区，并记录下每个索引分区第一个索引块的起始ip和地址信息（header块），并暂存在 headerpool 链表中。此外还会将索引区的起始位置和结束位置记录下来。
- 调整 randomaccessfile 指向文件开头，写入索引区的起始位置存储到 super 块的前四个字节，结束位置存储到 super 块的后四个字节。
- 继续将 headerpool 中的 header 块写入到 header 区。
- 调整 randomaccessfile 指向文件结尾，写入时间戳和版权信息。
tips: ip2region 仓库中还使用了 global_region.csv 数据，该文件有5列（行号，，区域，，邮政编码），对应着区域的具体信息，可以往数据区每个位置信息中填充。
快速搜索
ip2region 提供三种查询算法，最差的查询耗时都是ms级别的。分别是内存二分搜索，b+tree搜索，二分查找。耗时依次增加。其搜索结构图如下：
二分搜索
通过 super 块可以拿到索引区的起始位置和结束位置，而且每个索引块都是 12 bytes，其中的 ip 地址都是递增的，所以可以使用二分搜索来快速获取位置信息。其步骤如下：
- 把 ip 值通过 ip2long 方法转为整型
- 读取 super 块获取索引区的起始位置和结束位置，二者相减 +1 可得索引块的总个数
- 采用二分法直接求解，比较索引块中起始ip，结尾ip 和当前 ip 的大小，即可找到该 ip 对应的索引块，根据索引块后面四个字节得到数据地址和数据长度，从而拿到位置信息。
b+tree搜索
b+tree 搜索用到了 header 索引区，第一步先在 header 索引区中使用二分搜索，定位到某个索引分区后，再在对应的索引分区中使用二分搜索。相比较二分搜索而言，它的速度更快，原因是读磁盘的次数远低于二分搜索。其步骤如下：
- 把 ip 值通过 ip2long 转为整型
- 使用二分法在 header 索引区中搜索，比较得到对应的 header 索引块以及其对应的索引分区。
- 读取对应索引分区，再通过二分法定位到对应的索引块，从而获得位置信息。
基于内存的二分搜索
该方法和二分搜索方法类似，区别就是前者将 ip2region.db 全部读进内存中，后者则是通过不断读取 ip2region.db 文件。
总结
ip2region 库只解决了一个非常常见的 ip 定位问题，但将这个服务做到了又小又快（当然还提供了多语言的客户端），从而在 github 上获得了 8.4k 的 star。
占用内存小
- 相邻 ip 的位置信息相同，通过 ip 段来解决相邻 ip 对应相同位置信息，避免位置信息被重复存储
- ip 转换成 int，像字符串 111.111.111.111 被转换成int（1869573999），从 15byte 缩小到 4byte
- 不同的 ip 段也有相同的位置信息，通过指针来指向特定的位置信息，保证位置信息只保存一次（全量扫描存储进字典中）
搜索速度快
- ip 有序，使用二分搜索将时间复杂度降到 o(logn)
- 二级索引 header 索引区的使用，降低磁盘读写频率，先确定索引分区，再从索引分区确定索引位置，在确定位置信息数据。
多语言客户端支持
支持 java、c#、php、c、python、nodejs、php扩展(php5和php7)、golang、rust、lua、lua_c, nginx。
参考文献
- ip2region 数据库文件结构及原理
- ip2region源码
- ipv4的*
- 各国ipv4地址分配列表
- 高德地图api
- 百度地图api