高频业务:一种IP网段判断重叠的算法

实际业务中,高频率往往会遇到以下业务问题:

  1. 判断两个IP网段是否重叠 / 多个IP网段数组是否重叠
  2. 对用户进行相应的提醒 / 启动相应的策略

例如,客户有两台设备,在配置时填入错误的冲突IP网段时提醒客户,或收到一个攻击源IP信息时,需要判断源IP是否命中某个IP网段。

一般的业务流程是这样走的:

  1. 获取比较的IP网段集合
  2. 选出一个网段,与其他网段做对比
  3. 将该IP网段移除集合
  4. 重复第二步直到有网段重叠或没有网段重叠

这里忽略第二步,因为通常各团队底层公共库都已在第二步加入对应的算法,主要操作一般为:

  1. 获取IP网段的起始IP地址和结束IP地址,并解析为ip1_start, ip1_end, ip2_start, ip2_end
  2. 比较这四个数,判断是否重叠

在比较两个IP网段上述算法时,性能一般已到极限。但在实际业务需求中,往往会遇到客户一次性输入成百上千IP网段的情况(由EXCEL导入或外部系统导入等),原有业务流程效率就不再被接受。绿盟科技ADBOS团队对应的优化算法如下:

众所周知,

一个IP地址可以被解析为一个int类型的数字,

一个IP范围可以被解析为两个int类型的数字,

……

则可以想象,若干IP网段最终会被映射到一个无限长的数轴之上,数轴如下图:

重叠IP网段如下图:

如何通过这个数轴表现出来的特征,判断是否出现了重叠IP网段,设计算法如下:

  1. 所有IP网段,均初始化在值为0的数轴上,起始位置标为1,结束位置标为-1
    • 如果是IP地址,则变换为一个小范围进行初始化,如IP地址映射的整数是10000,则变换为9999.9和10000.1
    • 初始化过程中如果有相同的起始位置/结束位置,则所在位置再+1/-1
  2. 从左到右对数轴求和
    • 如果当前坐标值大于1或小于-1,说明有重叠情况
    • 如果当前坐标值为-1,但此时求和不为0,说明有形如1、1、-1的情况,有重叠
    • 如果当前坐标值是1,但此时的值大于1,也说明有形如1、1、-1的情况,有重叠
  3. 如果发生重叠判断,则记录当前坐标,和当前坐标的前一个坐标
    • 如果需要返回重叠IP网段,则此处可以根据坐标获取对应的IP网段,去重放入返回集合即可。

简单来说:

  1. 从左到右依次求和
  2. 读到-1,和值为0,说明正常,除此以外的任何情况,都说明出现了重叠
  3. 读到-1,和值为0,说明结束了一个冲突段

前后两种算法的伪代码如下:

旧代码:

新代码:

前后两种算法的效率对比如下:

重叠IP网段:数组中的最后一个 / 数组中全部都是重叠网段

是否提前中断:无

则均为两种算法的最坏情况下的最长耗时(即遍历所有IP网段的耗时)。

性能测试结果:

输入IP网段数旧算法/耗时新算法/耗时
40030s0.0035 s
10000\0.0686 s
100000\1.0340 s
200000\1.5224 s

1、这里数轴没有用数组的形式构建,因为IP解析出的int值都很大,采用了字典形式来节约内存空间,通过对字典排序变相实现数轴。

2、根据不同的业务逻辑,发现重叠IP网段后,采取不同手段也会影响到算法的性能,例如:

  • 发现重叠网段立刻不再判断,不影响性能
  • 发现重叠网段后进行数据库请求,则实际耗时取决于重叠网段数 * 每次数据库请求的时间

3、针对2,需要在特定业务场景下进行优化,如对重叠网段子集合不再内存中频繁去重,一次遍历进行输入,一次遍历进行去重,或借助redis集合,实现遍历一遍,一次去重。

版权声明

本站“技术博客”所有内容的版权持有者为绿盟科技集团股份有限公司(“绿盟科技”)。作为分享技术资讯的平台,绿盟科技期待与广大用户互动交流,并欢迎在标明出处(绿盟科技-技术博客)及网址的情形下,全文转发。
上述情形之外的任何使用形式,均需提前向绿盟科技(010-68438880-5462)申请版权授权。如擅自使用,绿盟科技保留追责权利。同时,如因擅自使用博客内容引发法律纠纷,由使用者自行承担全部法律责任,与绿盟科技无关。

Spread the word. Share this post!

Meet The Author

Leave Comment