在移动互联网的应用中，经常需要根据用户的位置信息等做一些用户侧信息的统计分析。而要拿到用户的位置信息，一般有两个方法： 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|内网IP0.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 段也有相同的位置信息，通过指针来指向特定的位置信息，保证位置信息只保存一次（全量扫描存储进字典中）