背景
上篇文章分析了ip2region的结构和实现，相对简单。且ip2region的方式仅仅支持IPv4，无法支持IPv6。
APP需支持IPv6 访问，所以需要研究下怎样能同时支持IPv4和IPv6的高并发访问。
查找资料的过程中发现多篇论文提到Trie树，结合之前实现禁词库的经验，深入研究之后发现可行。该处就将IP段生成Trie树过程的剪枝实现进行简单的讨论。
实现
前置知识
前置知识需自行百度，此处不表。
- IPv4/IPv6基础
- IPv4转为IPv6
- 位运算知识
- Trie树的基础
Trie树和IP映射
IPv6是128位（此处IPv4转化为IPv6），即有128位0或1构成。
例如：
####IPV4
1.92.255.255 转换为IPV6 => ::ffff:015c:ffff
#二进制 为了方便展示 每组64位
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000111111111111111100000001010111001111111111111111
####IPV6
2001:250:6031:ffff:ffff:ffff:ffff:ffff
#二进制 为了方便展示 每组64位
0010000000000001000000100101000001100000001100011111111111111111
1111111111111111111111111111111111111111111111111111111111111111
可以将所有IP看成一个深度129（根节点为独立节点）的Trie树。
暴力生成IP库
IPv4的数量约42.9亿，IPv6的数量。。。（此处写不下）。如果使用穷举的方式，那生成的Trie树将是任何计算机都不能完成的。
IP段优化
通过对IP地址信息的观察发现，大量的相邻 IP 拥有相同的位置信息，也就是按照IP段进行出现的。
例如：
1.0.0.0 1.0.0.255
我们截取其中一段IP 1.0.0.2 1.0.0.15，生成Trie树进行观察。
将startIP （1.0.0.2），endIP （1.0.0.15）生成Trie树。前面相同节点都省略，只保留不相同的部分。
左边标黑数字为 00010，代表startIP 1.0.0.2;
右边标黑数字为01111，代表endIP 1.0.0.15。
观察上图就会发现在黄色填充的节点内记录数据，即可完整覆盖到startIP（1.0.0.2）和endIP（1.0.0.15）之间的所有IP。
我们假定每个IP段内都存在少量特定的节点就可以完整的覆盖整个IP段，那么现在我们需要用程序找出这些节点，进行相关的剪枝操作就可以大大减小树的体积。
逻辑流程图
代码实现
//处理数据
func deal(startIP, endIP string) error {
startIPByte := net.ParseIP(startIP)
if startIPByte == nil {
return errors.New(fmt.Sprintf("invalid startIP:%s --deal", startIP))
}
startIPSet := IP2Bit(startIPByte)
fmt.Println(fmt.Sprintf("%s startIPSet", startIPSet.DumpAsBits()))
//结束IP
endIPByte := net.ParseIP(endIP)
if endIPByte == nil {
return errors.New(fmt.Sprintf("invalid endIP:%s --deal", endIP))
}
endIPSet := IP2Bit(endIPByte)
fmt.Println(fmt.Sprintf("%s endIPSet", endIPSet.DumpAsBits()))
return dealRow(startIPSet, endIPSet)
}
//dealRow 处理单行数据
func dealRow(startIPSet, endIPSet *bitset.BitSet) error {
tStartIPSet := startIPSet.Clone()
//比较大小
cap0 := tStartIPSet.Cap128(endIPSet)
//当startIP>endIP，直接报错返回，结束
if cap0 == 1 {
return errors.New(fmt.Sprintf("invalid startIP:%s --dealRow", "111"))
}
//当startIP==endIP
if cap0 == 0 {
//startIP的右1位写入，结束。
fmt.Println(fmt.Sprintf("%s 的从右到左第 %d 位", tStartIPSet.DumpAsBits(), 1))
return nil
}
//当startIP<endIP，继续逻辑。
isIBitLatest := tStartIPSet.Test(0)
if isIBitLatest {
//最后一位为1
//tStartIPSet的右1位写入，继续。
fmt.Println(fmt.Sprintf("%s 的从右到左第 %d 位", tStartIPSet.DumpAsBits(), 1))
//newStartIPSet=startIPSet+1
newStartIPSet := tStartIPSet.Incr128()
if newStartIPSet == nil {
return errors.New(fmt.Sprintf("invalid newStartIP:%s --dealRow", "222"))
}
err := dealRow(newStartIPSet, endIPSet)
if err != nil {
return err
}
} else {
//最后一位为0
//startIP从右到左第一位非0位，非下标
m := tStartIPSet.FirstSet()
err := dealRow0(tStartIPSet, endIPSet, m)
if err != nil {
return err
}
}
return nil
}
//dealRow0 128位为0的处理逻辑
//m 为从右到左的位数，非下标
func dealRow0(startIPSet, endIPSet *bitset.BitSet, m uint) error {
tStartIPSet := startIPSet.Clone()
//特殊处理
if m == 0 {
m = 129
}
//m-2得到需要处理的最大下标 [0,m-1)
tIPSet := tStartIPSet.FlipRange(0, m-1)
cap1 := tIPSet.Cap128(endIPSet)
//相等
if cap1 == 0 {
//tIP的右m位写入，结束。
fmt.Println(fmt.Sprintf("%s 的从右到左第 %d 位", tIPSet.DumpAsBits(), m))
return nil
}
//大于
if cap1 == 1 {
err2 := dealRow0(startIPSet, endIPSet, m-1)
if err2 != nil {
return err2
}
}
//小于
if cap1 == -1 {
//tIP的右m位写入，继续。
fmt.Println(fmt.Sprintf("%s 的从右到左第 %d 位", tIPSet.DumpAsBits(), m))
//newStartIPSet=tIPSet+1
newStartIPSet := tIPSet.Incr128()
if newStartIPSet == nil {
return errors.New(fmt.Sprintf("invalid tIP:%s", "333"))
}
err1 := dealRow(newStartIPSet, endIPSet)
if err1 != nil {
return err1
}
}
return nil
}
校验
假定测试IP段为startIP （1.0.0.2），endIP（1.0.0.15）。
func Test_deal(t *testing.T) {
startIP := "1.0.0.2"
endIP := "1.0.0.15"
err := deal(startIP, endIP)
if err != nil {
t.Log(err)
}
}
输出如下：
程序输出结果和上图Trie树结果相同（此处可以使用多组数据自行验证）。
Trie树剪枝通过。
总结
使用剪枝后的IPv4和IPv6全量数据文件可以控制在15MB以内，效果显著。
本文是在现有业务需要的背景下进行的研究，仅能满足当下业务的需求。但是其还有很多方面可以进行更加深入的研究。例如在提供的IP数据为单条非连续数据时，应该怎样进行剪枝等等。欢迎大家一起探讨学习。
备注
1、bitset库扩展
在进行扩展使用时，一定要注意库的开源协议。
https://github.com/bits-and-blooms/bitset
//FirstSet b最后为1的所在位置（非下标），从右到左
func (b *BitSet) FirstSet() uint {
panicIfNull(b)
for i := uint(0); i < b.length; i++ {
if b.set[i>>log2WordSize]&(1<<wordsIndex(i)) != 0 {
return i + 1
}
}
return 0
}
//Incr128 增加1
func (b *BitSet) Incr128() *BitSet {
panicIfNull(b)
if (b.set[0] & allBits) == allBits {
//低位已经为最大数，则设置为0
b.set[0] = 0
} else {
//低位未为最大数，则设置+1；并直接返回b
b.set[0] += 1
return b
}
if (b.set[1] & allBits) == allBits {
//低位已经为最大数，则设置为0
return nil
} else {
//低位未为最大数，则设置+1；并直接返回b
b.set[1] += 1
return b
}
}
// Cap128 128位对比b和c的大小。b>c返回1；b==c 返回0；b<c返回-1。
func (b *BitSet) Cap128(c *BitSet) int {
panicIfNull(b)
panicIfNull(c)
if b.set[1] > c.set[1] {
return 1
} else if b.set[1] < c.set[1] {
return -1
} else {
if b.set[0] > c.set[0] {
return 1
} else if b.set[0] < c.set[0] {
return -1
} else {
return 0
}
}
}
2、IP转换为bit
//IP2Bit IP转换为bit
func IP2Bit(IP net.IP) *bitset.BitSet {
IPBitSet := bitset.New(128)
for i := 0; i < 128; i++ {
//该IP在当前位上的值
iBit := ((0xFF & int(IP[i>>3])) >> uint(7-(i%8))) & 1
//计算当前位的位置
off := uint(128 - 1 - i)
//初始化数字设置位
if iBit == 1 {
IPBitSet.Set(off)
}
}
return IPBitSet
}
3、IP信息
IPv4
1.0.0.0 1.0.0.255
1.68.113.27 1.68.113.83
1.68.113.84 1.68.113.84
1.68.113.85 1.68.114.15
IPv6
2001:250:6415:: 2001:250:6415:ffff:ffff:ffff:ffff:ffff
2001:250:6416:: 2001:250:6416:ffff:ffff:ffff:ffff:ffff
2001:250:6417:: 2001:250:641a:ffff:ffff:ffff:ffff:ffff
2001:250:641b:: 2001:250:641b:ffff:ffff:ffff:ffff:ffff