高频业务：一种IP网段判断重叠的算法（其三）
内容提要
本文拓展IP重叠判断算法，将其用于业务维度碰撞，如筛选命中攻击事件的源IP。以128位结构表示IPv6，用(start,end,length)三元组描述IP段。针对CIDR嵌套继承问题，采用扫描线算法，将IP段拆为进入和离开事件，维护active集合，实现子段继承父段标签，复杂度O(N)，可高效处理百万级IP段。
延伸解读
从IP重叠到业务碰撞：算法应用面的拓展
文章指出，IP重叠判断的本质是数轴上的“碰撞”，而碰撞不仅能判断重叠，还能获取重叠区域及覆盖关系。当为IP附加业务标签（如攻击事件、僵尸网络）后，算法便可应用于筛选命中特定标签的源IP，例如判断某批IP是否与僵尸网络A的源IP重叠。这拓展了算法的应用场景，使其从单纯的IP重叠判断升级为业务维度的碰撞分析。
IPv6的128位整数表示与内存优化
针对IPv6地址长度达128位的问题，文章采用自定义结构体type u128 struct { hi uint64; lo uint64 }来表示，避免使用big.Int，从而减少动态内存分配和GC压力，并提高比较速度。IP段统一用三元组(start, end, length)描述，单IP的length为1，CIDR段则对应区间长度。这种表示方式为后续扫描线算法提供了高效的数据基础。
扫描线算法解决CIDR嵌套继承
文章使用扫描线算法处理CIDR嵌套继承问题。将每个CIDR拆分为进入和离开事件，按位置排序（同一位置start优先于end，同类型事件更大的CIDR优先），扫描时维护active集合。当遇到start事件且active非空时，当前段继承active中所有段的标签。该算法以O(N)复杂度完成维度聚合，支持任意业务标签扩展，且在100万个/24段下仍能在60秒内完成扫描与输出。
Q&A
IP网段重叠判断算法除了判断重叠，还能用来做什么？
可以用于业务维度的碰撞，例如筛选命中攻击事件的源IP、筛选与僵尸网络A的源IP相同的源IP，或筛选曾出现在美国且属于攻击组织B常用肉鸡的源IP。
为什么IPv6地址要用128位结构表示，而不是用big.Int？
使用128位结构（如type u128 struct { hi uint64; lo uint64 }）可以避免使用big.Int，避免动态内存分配，降低GC压力，并提高比较速度。
如何统一表示一个IP段？
使用三元组（start, end, length）表示一个IP段，其中length表示该IP段的长度。例如单IP 1.1.1.1转换为start=end=16843009，length=1；IP段1.1.1.0/24得到start=16843008，end=16843263，length=256。
CIDR嵌套时，子段如何继承父段的业务标签？
采用扫描线算法，将每个CIDR拆为进入和离开事件，维护一个active集合。当扫描到start事件时，如果active集合不为空，则当前段被active集合中的段包含，系统将active集合的维度复制到当前段，完成维度聚合。
扫描线算法中事件如何排序？
事件按（pos, isEnd, length）排序：先按位置从小到大扫描；同一位置，start事件优先于end事件；同一位置同类型事件，更大的CIDR优先处理。
该算法处理百万级IP段的性能如何？
算法复杂度为O(N)，速度非常快，即使在100万个/24段的情况下，仍然能在60秒内完成整个扫描与结果输出。
