实际业务中,高频率往往会遇到以下业务问题:
- 判断两个IP网段是否重叠 / 多个IP网段数组是否重叠
- 对用户进行相应的提醒 / 启动相应的策略
例如,客户有两台设备,在配置时填入错误的冲突IP网段时提醒客户,或收到一个攻击源IP信息时,需要判断源IP是否命中某个IP网段。
一般的业务流程是这样走的:
- 获取比较的IP网段集合
- 选出一个网段,与其他网段做对比
- 将该IP网段移除集合
- 重复第二步直到有网段重叠或没有网段重叠
这里忽略第二步,因为通常各团队底层公共库都已在第二步加入对应的算法,主要操作一般为:
- 获取IP网段的起始IP地址和结束IP地址,并解析为ip1_start, ip1_end, ip2_start, ip2_end
- 比较这四个数,判断是否重叠
在比较两个IP网段上述算法时,性能一般已到极限。但在实际业务需求中,往往会遇到客户一次性输入成百上千IP网段的情况(由EXCEL导入或外部系统导入等),原有业务流程效率就不再被接受。绿盟科技ADBOS团队对应的优化算法如下:
众所周知,
一个IP地址可以被解析为一个int类型的数字,
一个IP范围可以被解析为两个int类型的数字,
……
则可以想象,若干IP网段最终会被映射到一个无限长的数轴之上,数轴如下图:
重叠IP网段如下图:
如何通过这个数轴表现出来的特征,判断是否出现了重叠IP网段,设计算法如下:
- 所有IP网段,均初始化在值为0的数轴上,起始位置标为1,结束位置标为-1
- 如果是IP地址,则变换为一个小范围进行初始化,如IP地址映射的整数是10000,则变换为9999.9和10000.1
- 初始化过程中如果有相同的起始位置/结束位置,则所在位置再+1/-1
- 从左到右对数轴求和
- 如果当前坐标值大于1或小于-1,说明有重叠情况
- 如果当前坐标值为-1,但此时求和不为0,说明有形如1、1、-1的情况,有重叠
- 如果当前坐标值是1,但此时的值大于1,也说明有形如1、1、-1的情况,有重叠
- 如果发生重叠判断,则记录当前坐标,和当前坐标的前一个坐标
- 如果需要返回重叠IP网段,则此处可以根据坐标获取对应的IP网段,去重放入返回集合即可。
简单来说:
- 从左到右依次求和
- 读到-1,和值为0,说明正常,除此以外的任何情况,都说明出现了重叠
- 读到-1,和值为0,说明结束了一个冲突段
前后两种算法的伪代码如下:
旧代码:
新代码:
前后两种算法的效率对比如下:
重叠IP网段:数组中的最后一个 / 数组中全部都是重叠网段
是否提前中断:无
则均为两种算法的最坏情况下的最长耗时(即遍历所有IP网段的耗时)。
性能测试结果:
输入IP网段数 | 旧算法/耗时 | 新算法/耗时 |
400 | 30s | 0.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)申请版权授权。如擅自使用,绿盟科技保留追责权利。同时,如因擅自使用博客内容引发法律纠纷,由使用者自行承担全部法律责任,与绿盟科技无关。