高性能IP数据库格式详解 qqzeng-ip.dat
#include "GeoIP.h"
#include "string.h"
#include <stdlib.h>
char *IP_FILENAME = "qqzeng-ip-3.0-ultimate.dat";
//编码：utf-8
//性能：C语言性能之王 每秒解析1680万+ip
//环境：CPU i7-7700K + DDR2400 16G + win10 X64 (Release)
//创建：qqzeng-ip 于 2018-06-21
geo_ip *geoip_instance()
{
geo_ip *ret = (geo_ip *)malloc(sizeof(geo_ip));
if (geoip_loadDat(ret) >= 0)
{
return ret;
}
if (ret)
{
free(ret);
}
return NULL;
}
int32_t geoip_loadDat(geo_ip *p)
{
FILE *file;
uint8_t *buffer;
long len = 0;
int k, i, j;
uint32_t RecordSize, offset, length;
errno_t err = fopen_s(&file, IP_FILENAME, "rb");
if (err == 2)
{
printf("%s", "没有此文件或目录");
return -2;
}
fseek(file, 0, SEEK_END);
len = ftell(file);
fseek(file, 0, SEEK_SET);
buffer = (uint8_t *)malloc(len * sizeof(uint8_t));
fread(buffer, 1, len, file);
fclose(file);
for (k = 0; k < 256; k++)
{
i = k * 8 + 4;
p->prefStart[k] = geoip_read_int32(p, buffer, i);
p->prefEnd[k] = geoip_read_int32(p, buffer, i + 4);
}
RecordSize = geoip_read_int32(p, buffer, 0);
p->endArr = (uint32_t *)malloc(RecordSize * sizeof(uint32_t));
p->addrArr = (char **)malloc(RecordSize * sizeof(char*));
for (i = 0; i < RecordSize; i++)
{
j = 2052 + (i * 8);
p->endArr[i] = geoip_read_int32(p, buffer, j);
offset = geoip_read_int24(p, buffer, 4 + j);
length = (uint32_t)buffer[7 + j];
char *result = (char *)malloc((length + 1) * sizeof(char));
memcpy(result, buffer + offset, length);
result[length] = '\0';
p->addrArr[i] = result;
}
return 0;
}
char *geoip_query(geo_ip *p, char *ip)
{
uint32_t pref, cur, intIP, low, high;
if (NULL == p)
{
return NULL;
}
intIP = geoip_ip2long(p, ip, &pref);
low = p->prefStart[pref];
high = p->prefEnd[pref];
cur = (low == high) ? low : geoip_binary_search(p, low, high, intIP);
return p->addrArr[cur];
}
uint32_t geoip_binary_search(geo_ip *p, uint32_t low, uint32_t high, uint32_t k)
{
uint32_t M = 0;
while (low <= high)
{
uint32_t mid = (low + high) >> 1;
uint32_t endipNum = p->endArr[mid];
if (endipNum >= k)
{
M = mid;
if (mid == 0)
{
break;
}
high = mid - 1;
}
else
low = mid + 1;
}
return M;
}
uint32_t geoip_ip2long(geo_ip *p, char *addr, uint32_t *prefix)
{
uint32_t c, octet, t;
uint32_t ipnum;
int i = 3;
octet = ipnum = 0;
while ((c = *addr++))
{
if (c == '.')
{
ipnum <<= 8;
ipnum += octet;
i--;
octet = 0;
}
else
{
t = octet;
octet <<= 3;
octet += t;
octet += t;
c -= '0';
octet += c;
if (i == 3)
{
*prefix = octet;
}
}
}
ipnum <<= 8;
return ipnum + octet;
}
uint32_t geoip_read_int32(geo_ip *p, uint8_t *buf, int pos)
{
uint32_t result;
result = (uint32_t)((buf[pos + 3] << 24 & 0xff000000) | (buf[pos + 2] << 16 & 0x00ff0000) | (buf[pos + 1] << 8 & 0xff00) | (buf[pos] & 0xff));
return result;
}
uint32_t geoip_read_int24(geo_ip *p, uint8_t *buf, int pos)
{
uint32_t result;
result = (uint32_t)((buf[pos + 2] << 16 & 0x00ff0000) | (buf[pos + 1] << 8 & 0xff00) | (buf[pos] & 0xff));
return result;
}
int main(int argc, char **argv)
{
geo_ip *finder = geoip_instance();
if (!finder)
{
printf("the IPSearch instance is null!");
return -1;
}
char *ip = "8.8.8.8";
char *local = geoip_query(finder, ip);
printf("%s\n",local);
system("pause");
return 0;
}
#ifndef __GEO_IP_H_
#define __GEO_IP_H_
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#ifdef __cplusplus
extern "C" {
#endif
typedef struct tag_geoip
{
uint32_t prefStart[256];
uint32_t prefEnd[256];
uint32_t *endArr;
char **addrArr;
}geo_ip;
geo_ip* geoip_instance();
int32_t geoip_loadDat(geo_ip* p);
char* geoip_query(geo_ip* p, char *ip);
uint32_t geoip_binary_search(geo_ip* p,uint32_t low, uint32_t high, uint32_t k);
uint32_t geoip_ip2long(geo_ip* p,char *addr, uint32_t* prefix);
uint32_t geoip_read_int32(geo_ip* p,uint8_t *buf, int pos);
uint32_t geoip_read_int24(geo_ip* p,uint8_t *buf, int pos);
#ifdef __cplusplus
}
#endif
#endif高性能IP数据库格式详解 qqzeng-ip.dat
编码：UTF8和GB2312 字节序：Little-Endian
返回多个字段信息（如：亚洲|中国|香港|九龙|油尖旺|新世界电讯|810200|Hong Kong|HK|114.17495|22.327115）
------------------------ 文件结构 3.0 版 -------------------------
//文件头 4字节
[IP段记录]
//前缀区 8字节(4-4) 256*8
[索引区start第几个][索引区end第几个]
//索引区 8字节(4-3-1) ip段行数*8
[结束IP数字][地区流位置][流长度]
//内容区 长度无限制
[地区信息][地区信息]……唯一不重复
------------------------ 文件结构 3.0 版 ---------------------------
优势：压缩形式将数据存储在内存中，通过减少将相同数据读取到内存的次数来减少I/O.
较高的压缩率通过使用更小的内存中空间提高查询性能。
前缀区为作为缩小查询范围,索引区和内容区长度一样,
解析出来一次性加载到数组中,查询性能提高3-5倍！
压缩：原版txt为38.5M,生成dat结构为3.68M 。
和上一版本2.0不同的是索引区去掉了[开始IP数字]4字节,节省多1-2M。
3.0版本只适用[全球版]，条件为ip段区间连续且覆盖所有IPV4。
2.0版本适用[全球版][国内版][国外版]
性能：每秒解析1000多万ip (环境：CPU i7-7700K + DDR2400 16G + win10 X64)
------------------------ 文件结构 2.0 版 ---------------------------
//文件头 16字节(4-4-4-4)
[索引区第一条流位置][索引区最后一条流位置][前缀区第一条的流位置][前缀区最后一条的流位置]
//内容区 长度无限制
[地区信息][地区信息]……唯一不重复
//索引区 12字节(4-4-3-1)
[起始IP][结束IP][地区流位置][流长度]
//前缀区 9字节(1-4-4)
[0-255][索引区start索引][索引区end索引]
------------------------ 文件结构 2.0 版 ---------------------------
优势：索引区分为[起始IP][结束IP][地区偏移][长度],减少多级偏移跳转步骤和长度的解析,提高效率;
根据ip第一位数字作为前缀,解析出以这个数字为前缀的第一个索引和最后一个索引,缩小查询区间,
然后在这区间再用二分查找快速查找到对应区间,效率提高几个等级
压缩：原版txt为35M,生成这种dat结构为3.36M
性能：解析900万+ip耗时1秒
对比：相比其他dat更简洁更高效
测试环境：CPU i7-7700K + DDR2400 16G + win10 X64
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 3690万ip->2.262秒 每秒1631.299735万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 9900万ip->5.954秒 每秒1662.747733万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 17820万ip->10.64秒 每秒1674.654638万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 12870万ip->7.689秒 每秒1673.819742万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 18450万ip->11.27秒 每秒1673.165866万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 7380万ip->4.441秒 每秒1661.787886万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 1107万ip->0.670秒 每秒1652.238806万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 135万ip->0.078秒 每秒1730.769231万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 5724万ip->3.398秒 每秒1684.520306万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 4806万ip->2.853秒 每秒1684.542587万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 5913万ip->3.529秒 每秒1675.545480万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 2943万ip->1.751秒 每秒1680.753855万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 1836万ip->1.093秒 每秒1679.780421万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 2673万ip->1.594秒 每秒1676.913425万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 6777万ip->4.026秒 每秒1683.308495万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 252万ip->0.153秒 每秒1647.058824万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 109.8万ip->0.065秒 每秒1689.230769万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 167.4万ip->0.100秒 每秒1674.000000万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 354.6万ip->0.213秒 每秒1664.788732万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 432万ip->0.257秒 每秒1680.933852万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 15.99万ip->0.009秒 每秒1776.666667万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 90.48万ip->0.053秒 每秒1707.169811万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 48.36万ip->0.028秒 每秒1727.142857万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 54.99万ip->0.031秒 每秒1773.870968万次
C 解析 qqzeng-ip-ultimate.dat 【3.0】内存优化版 76.83万ip->0.044秒 每秒1746.136364万次
其他语言 参考
查询 qqzeng-ip.dat 【3.0】内存优化版 3414万ip->3.318秒 每秒1028.93309222423万次
查询 qqzeng-ip.dat 【3.0】内存优化版 4439万ip->4.199秒 每秒1057.1564658252万次
查询 qqzeng-ip.dat 【3.0】内存优化版 4056万ip->3.821秒 每秒1061.50222454855万次
查询 qqzeng-ip.dat 【3.0】内存优化版 1781万ip->1.68秒 每秒1060.11904761905万次
查询 qqzeng-ip.dat 【3.0】内存优化版 3862万ip->3.66秒 每秒1055.1912568306万次
查询 qqzeng-ip.dat 【3.0】内存优化版 3479万ip->3.31秒 每秒1051.05740181269万次
查询 qqzeng-ip.dat 【3.0】内存优化版 2892万ip->2.713秒 每秒1065.97862145227万次
查询 qqzeng-ip.dat 【3.0】内存优化版 3484万ip->3.263秒 每秒1067.72908366534万次
查询 qqzeng-ip.dat 【3.0】内存优化版 2699万ip->2.548秒 每秒1059.26216640502万次
查询 qqzeng-ip.dat 【3.0】内存优化版 2175万ip->2.063秒 每秒1054.28986912264万次
查询 qqzeng-ip.dat 【3.0】内存优化版 42万ip->0.041秒 每秒1024.39024390244万次
查询 qqzeng-ip.dat 【3.0】内存优化版 159万ip->0.152秒 每秒1046.05263157895万次
查询 qqzeng-ip.dat 【3.0】内存优化版 88万ip->0.084秒 每秒1047.61904761905万次
查询 qqzeng-ip.dat 【3.0】内存优化版 123万ip->0.118秒 每秒1042.37288135593万次
查询 qqzeng-ip.dat 【3.0】内存优化版 106万ip->0.101秒 每秒1049.50495049505万次
查询 qqzeng-ip.dat 【3.0】内存优化版 61万ip->0.059秒 每秒1033.89830508475万次
查询 qqzeng-ip.dat 【3.0】内存优化版 177万ip->0.169秒 每秒1047.33727810651万次
查询 qqzeng-ip.dat 【3.0】内存优化版 106万ip->0.101秒 每秒1049.50495049505万次
查询qqzeng-ip.dat 【2.0】内存优化版 1971万ip->2.168秒 每秒909.132841328413万次
查询qqzeng-ip.dat 【2.0】内存优化版 1070万ip->1.127秒 每秒949.423247559894万次
查询qqzeng-ip.dat 【2.0】内存优化版 1392万ip->1.463秒 每秒951.46958304853万次
查询qqzeng-ip.dat 【2.0】内存优化版 933万ip->0.98秒 每秒952.040816326531万次
查询qqzeng-ip.dat 【2.0】内存优化版 1896万ip->1.996秒 每秒949.899799599198万次
查询qqzeng-ip.dat 【2.0】内存优化版 1029万ip->1.123秒 每秒916.295636687444万次
查询qqzeng-ip.dat 【2.0】内存优化版 1684万ip->1.94秒 每秒868.041237113402万次
查询qqzeng-ip.dat 【2.0】内存优化版 740万ip->0.791秒 每秒935.524652338812万次
查询qqzeng-ip.dat 【2.0】内存优化版 863万ip->0.928秒 每秒929.956896551724万次
查询qqzeng-ip.dat 【2.0】内存优化版 633万ip->0.669秒 每秒946.188340807175万次
查询qqzeng-ip.dat 【2.0】内存优化版 908万ip->0.956秒 每秒949.79079497908万次
查询qqzeng-ip.dat 【2.0】内存优化版 1176万ip->1.237秒 每秒950.687146321746万次
查询qqzeng-ip.dat 【2.0】内存优化版 1739万ip->1.833秒 每秒948.717948717949万次
查询qqzeng-ip.dat 【2.0】内存优化版 1147万ip->1.232秒 每秒931.006493506493万次
查询qqzeng-ip.dat 【2.0】内存优化版 1005万ip->1.061秒 每秒947.219604147031万次
查询 qqzeng-ip.dat 【2.0】普通优化版 1464万ip->3.408秒 每秒429.577464788732万次
查询 qqzeng-ip.dat 【2.0】普通优化版 352万ip->0.803秒 每秒438.356164383562万次
查询 qqzeng-ip.dat 【2.0】普通优化版 1357万ip->3.042秒 每秒446.088099934254万次
查询 qqzeng-ip.dat 【2.0】普通优化版 184万ip->0.43秒 每秒427.906976744186万次
查询 qqzeng-ip.dat 【2.0】普通优化版 752万ip->1.697秒 每秒443.134944018857万次
查询 qqzeng-ip.dat 【2.0】普通优化版 1795万ip->4.032秒 每秒445.188492063492万次
查询 qqzeng-ip.dat 【2.0】普通优化版 1823万ip->4.076秒 每秒447.252208047105万次
查询 qqzeng-ip.dat 【2.0】普通优化版 723万ip->1.622秒 每秒445.745992601726万次
查询 qqzeng-ip.dat 【2.0】普通优化版 136万ip->0.319秒 每秒426.332288401254万次
查询 qqzeng-ip.dat 【2.0】普通优化版 334万ip->0.756秒 每秒441.798941798942万次
查询 qqzeng-ip.dat 【2.0】普通优化版 636万ip->1.435秒 每秒443.205574912892万次
查询 qqzeng-ip.dat 【2.0】普通优化版 701万ip->1.578秒 每秒444.233206590621万次
查询 qqzeng-ip.dat 【2.0】普通优化版 1807万ip->4.07秒 每秒443.980343980344万次
查询 qqzeng-ip.dat 【2.0】普通优化版 489万ip->1.105秒 每秒442.533936651584万次