高频业务：一种IP网段判断重叠的算法（其三）
内容提要
提出一种IP重叠判断算法：将IP段映射到数轴，用扫描线算法处理CIDR嵌套继承，使小段自动继承大段业务标签。IP段用(start,end,length)三元组表示，采用u128结构避免溢出。通过维度聚合，将(ip,维度,值)排序后线性扫描，以O(N)复杂度完成标签继承与去重，可应用于攻击源IP匹配等场景，百万级/24段60秒内完成。
延伸解读
从重叠判断到业务标签碰撞
文章将IP重叠判断算法拓展到业务维度碰撞。核心思路是：任何针对IP属性标签的碰撞需求，本质上都是计算重叠。例如，筛选与僵尸网络A源IP相同的IP，或筛选曾出现在美国且属于攻击组织B常用肉鸡的IP。通过给IP加上维度标签，算法能自动继承和聚合标签，从而支持复杂的业务筛选场景。
u128结构避免大整数开销
针对IPv6的128位地址，文章采用自定义的u128结构（hi和lo各64位）表示整数，避免使用big.Int和动态内存分配，降低GC压力并提高比较速度。IP段统一用(start, end, length)三元组表示，单IP的start等于end且length为1，CIDR段则对应连续区间。属性标签存储在字典中，可任意定义。
扫描线算法实现CIDR嵌套继承
扫描线算法通过将每个CIDR拆分为进入和离开事件，按位置排序（同位置start优先于end，同类型大CIDR优先），维护active集合。当扫描到start事件时，若active非空，则当前段被active中的段包含，从而继承其维度标签。该算法以O(N)复杂度解决嵌套继承，支持任意维度扩展，且子段继承父段几乎无开销。
性能与适用场景
文章声称该算法速度极快，在100万个/24段的情况下，能在60秒内完成整个扫描与结果输出。其优势在于线性复杂度、灵活的业务维度扩展以及高效的继承操作。适用于攻击源IP匹配、僵尸网络筛选等需要基于IP属性进行碰撞的高频业务场景。
Q&A
IP网段重叠判断算法除了判断重叠，还能获取哪些额外信息？
当得出重叠的段时，可以获取到重叠的IP所在的数轴区域，以及重叠的IP究竟被什么IP所覆盖（碰撞）。
如何用数据结构表示IPv6地址以避免溢出？
使用type u128 struct { hi uint64 lo uint64 }表示128位整数，其中hi表示高64位，lo表示低64位。这样可以避免使用big.Int、避免动态内存分配、降低GC压力、提高比较速度。
IP段在数轴上映射后有什么性质？
小段始终被大段包裹，并且小段和小段之间不会重叠。
扫描线算法如何解决CIDR嵌套继承问题？
扫描线算法通过将每个CIDR拆为进入和离开事件，按位置排序（同一位置start优先于end，同类型事件更大的CIDR优先），维护active集合。当扫描到start事件时，如果active集合不为空，则当前段被active集合中的段包含，将active的维度复制到当前段，完成维度聚合。
该算法处理百万级/24段需要多长时间？
即使在100万个/24段的情况下，仍然能在60秒内完成整个扫描与结果输出。
该算法可以应用于哪些业务场景？
可以应用于筛选存在与僵尸网络A的源IP相同的源IP，筛选曾经出现在美国且处于攻击组织B的常用肉鸡的源IP等场景。
