IP库-ip2region结构分析和实现
一、为什么要IP库
1、显示IP属地，营造更加清朗的网络空间。
2、更好地解决定向广告精准性的问题。
3、数据平台以及归因数据分析。
二、市面上主流IP库实现分析
APP需要省市级别的定位，且仅需支持IPV4，所以选择ip2region更合适。
三、ip2region结构分析和实现
官方IP 库文件ip2region.db的结构分为四个部分：super data， header index data，record data，index data。其中header index data是对index block的二级索引，专门为b+tree搜索服务的。
七猫业务场景前台多为Go，后台多为PHP项目，所以只需要保留二分搜索方式。移除b+tree搜索方式。
1、实现方案
仅支持内存二分搜索，会在第一次使用时将所有内容加载到内存。
结构分为三个部分：super data，record data，index data。
具体如下图所示：
super data
super data用来保存index data的起始地址和结束地址，第一个索引指针指向index data的开始位置，也就是第一个index data的第一个index block， 最后一个索引指针 指向index data的结束位置-12，也就是最后一个index data的最后一个index block的头地址。这样查询的时候直接读取super data 8 个字节，就能快速获取index data的地址范围。
record data
record data保存的数据，数据格式如下：中国|内蒙古|鄂尔多斯|150600， 分别表示国家，区域，省份，城市，城市编码。
index data
index data是由index block构成， 每个index block占 12 字节，包括起始IP, 结束IP, 数据信息。数据信息中前三个字节保存数据地址，后一个字节保存数据长度。 每一条index block对应 ipv4_data.txt 中的一条记录，表示一个 IP 段的索引。 在检索中当指定 IP 在某个index block的起始IP和结束IP中间，即表示命中索引。再通过index block中的数据地址和数据长度，就能从 ip2region.db 读取对应的位置信息数据。
2、生成db文件
由于结构较官方结构做了调整，所以生成程序也需要做对应调整。
核心是Maker，具体如下图所示：
1、初始创建ip2region.db文件，并在文件中预留8bytes的super data区域。
2、扫描ipv4_data.txt文件，对每一条记录进行简单处理得到Metadata，最终得到mds。
var mds []Metadata
3、对mds的数据进行升序排序。
4、遍历mds数据，对每一条记录进行如下处理：
依据每一条记录的起始IP, 结束IP 和数据，生成一个index block， 前四个字节存储起始IP, 中间四个字节存储结束IP， 后四个字节存储已经计算出的数据地址（通过 Maker.dbFile 写入，这里维护一个位置信息到文件位置的字典regionRecordMap，保证同一个位置信息只写入一次。），并将index block暂存在 Maker.indexPool 中。这一步会将数据区的所有位置信息确定。
5、遍历完mds中所有的记录， 将 Maker.indexPool 中所有的index block写到record data后面。将index data的起始位置和结束位置记录下来。
6、调整 Maker.dbFile指向文件开头，写入index data的起始位置存储到 super data的前四个字节，结束位置存储到 super data的后四个字节。
7、调整 Maker.dbFile 指向文件结尾，写入时间戳和版权信息。
3、查询IP信息（二分搜索）
通过 super data可以拿到index data的起始位置和结束位置，而且每个index block都是 12 bytes，其中的 IP 地址都是递增的，所以可以使用二分搜索来快速获取位置信息。其步骤如下：
- 把 IP 值通过 IP2Uint32 方法转为整型。
- 读取 super data获取索引区的起始位置和结束位置，二者相减/12 +1 可得super block的总个数。
- 采用二分法直接求解，比较index block中起始IP，结尾IP 和当前 IP 的大小，即可找到该 IP 对应的index block，根据index block后面四个字节得到数据地址和数据长度，从而拿到位置信息。
4、性能
分为两个场景，
1、使用IP（1.9.71.8）格式 BenchmarkGetIpInfo
2、使用数字（17385224）格式BenchmarkGetIpInfoFromUint32
经测试结果如下：
| 名称 | 次数 | 平均耗时 |
|---|---|---|
| BenchmarkGetIpInfo-8 | 2231534 | 531.4 ns/op |
| BenchmarkGetIpInfoFromUint32-8 | 7098955 | 174.8 ns/op |
总结
ip2region 库目前的结构仅仅支持IPV4。该库能满足部分业务的阶段性要求。
应国家要求，接入APP的流量均需支持IPV6，下篇文章分析IPV4和IPV6结合库的结构和实现。
备注
1、原始文件说明和要求
中间使用|间隔，没有数据为*。
ipv4_data.txt
1.8.9.0|1.8.255.255|中国|中国|*|100000
1.9.0.0|1.9.71.7|马来西亚|马来西亚|*|*
1.9.71.8|1.9.71.15|中国|香港|*|810000
2、ip转换为int
//IP2Uint32 正常IP转换为整数
func IP2Uint32(IpStr string) (uint32, error) {
ErrInvalidIp := errors.New("ip2region: invalid ipv4 " + strconv.Quote(IpStr))
bits := strings.Split(IpStr, ".")
if len(bits) != 4 {
return 0, ErrInvalidIp
}
var sum uint32
for i, n := range bits {
bit, err := strconv.Atoi(n)
if err != nil {
return 0, ErrInvalidIp
}
if bit < 0 || bit > 255 {
return 0, ErrInvalidIp
}
sum += uint32(bit) << uint32(24-8*i)
}
return sum, nil
}