一种IP命中交叉网段的查找算法
tammypi
2019-05-22 09:31
202
0
1.问题描述
假设有一堆网段，如下所示：
192.168.1.100-192.168.1.120，AAA，id1
192.168.1.50-192.168.1.150，BBB，id2
10.67.1.1/24，CCC，id3
10.67.1.1，DDD，id4
10.67.1.0，EEE，id5
第一列是单IP或者网段，第二列是设备hash，第三列是这个IP或者网段的唯一标志。IP与网段、网段与网段之间是可以有交叉的，比如192.16.1.100-192.168.1.120和192.168.1.50-192.168.1.150就是存在一部分交叉的。
要求，当一个日志过来过来时，需要得到它里面的IP的唯一ID，比如10.67.1.125过来，我们就知道它是属于10.67.1.1/24网段，那么就是用id3来标志它；比如10.67.1.1过来时，我们发现既可以命中10.67.1.1（id4）也可以命中10.67.1.1/24(id3),那么就提取日志里记录的hash值，比如hash是CCC,那么我们就知道它的唯一ID应该是id3。
2.解题思路
1.首先将网段拆开为多个不交叉的段，并且记录每个段对应的相关信息
2.在一个日志过来时，提取其IP在网段里进行二分查找，当查找到的相关信息唯一时，直接返回；当查找到的相关信息不唯一时，使用hash值进行比对，从而拿到命中值
2.1网段拆分为不交叉段
对于一组数据，如下所示：
s1,e1,id1
s2,e2,id2
s3,e3,id3
s和e分别代表起始数值，id为唯一标志。它们的范围如下图所示：
我们可以按数值的大小进行排序，注意，如果两个值相等的情况下，起始值排在结束值之前，排序之后如下所示：
s1,s2,s3,e1,e2,e3
分析的过程如下图所示：
在step1，得到的结果应该是:[s1,s2-1] id1
在step2，得到的结果应该是:[s2,s3-1] id1,id2
在step3，得到的结果应该是:[s3,e1] id1,id2,id3
在step4，得到的结果应该是:[e1+1,e2] id2,id3
在step5，得到的结果应该是:[e2+1,e3] id3
那么总结的处理过程如下：
从排序后的数值list里拿到两个元素n1,n2，用一个全局的S记录id值
- 如果n1是s类型，则a=n1，且将n1对应的id加入S中;如果n1是e类型，则a=n1+1，则将n1对应的id从S中移除
- 如果n2是s类型，则b=n2-1;如果n2是e类型，则b=n2
- 如果a<=b且S不为空，则对于[a,b]以及S进行输出
以此循环，直至对于list处理结束。
核心代码如下所示：
public List<OutputNode> init(List<IpRangeAsset> list){
List<GapRangeNode> gapRangeNodeList = new ArrayList<>();
for(int i=0;i<list.size();i++){
gapRangeNodeList.add(new GapRangeNode(list.get(i).getStartIpInt(),i,false));
gapRangeNodeList.add(new GapRangeNode(list.get(i).getEndIpInt(),i,true));
}
Collections.sort(gapRangeNodeList, new Comparator<GapRangeNode>() {
@Override
public int compare(GapRangeNode o1, GapRangeNode o2) {
return o1.getNumber()-o2.getNumber()<0||(o1.getNumber()==o2.getNumber()&&o2.isEnd())?-1:1;
}
});
OutputNode outputNode = new OutputNode(-1,-1);
List<OutputNode> resultList = new ArrayList<OutputNode>();
for(int i=0;i<gapRangeNodeList.size()-1;i++){
GapRangeNode n1 = gapRangeNodeList.get(i);
GapRangeNode n2 = gapRangeNodeList.get(i+1);
long n = -1;
long m = -1;
if(n1.isEnd()){
n = n1.getNumber()+1;
outputNode.removeAssetIndex(list.get(n1.getIndex()));
}else{
n = n1.getNumber();
outputNode.addAssetIndex(list.get(n1.getIndex()));
}
if(n2.isEnd()){
m = n2.getNumber();
}else{
m = n2.getNumber() - 1;
}
if(n <= m && outputNode.getAssetIndexSet().size() > 0){
OutputNode copyNode = new OutputNode(n,m);
Iterator<IpRangeAsset> iterator = outputNode.getAssetIndexSet().iterator();
while(iterator.hasNext()){
copyNode.addAssetIndex(iterator.next());
}
resultList.add(copyNode);
}
}
return resultList;
}网段拆分的效果如下：
2.2二分查找
由于已经将网段拆分成了不相交的网段，所以可以直接将网段按照从小到大进行排序，得到一个有序的数组。然后使用二分查找来找寻IP所属的网段，如果命中的网段对应着多个结果，那么使用hash找到对应的结果。在IP范围数目为100万的情况下，如果使用二分查找，最坏的比对次数为math.log(1000000,2)约等于20次，而直接顺序查找最坏的比对次数为1000000次。
二分查找的核心代码如下：
public IpRangeAsset search(long ipint,String devHash,List assetList){
int low = 0;
int high = assetList.size()-1;
IpRangeAsset ipRangeAsset = null;
while(low <= high){
int index = (low+high)/2;
if(ipint > assetList.get(index).getEnd()){
low = index + 1;
}else if(ipint < assetList.get(index).getStart()){
high = index - 1;
}else{
if(assetList.get(index).getAssetIndexSet().size() == 1){
ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
}else{
Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
while(iterator.hasNext()){
IpRangeAsset entry = (IpRangeAsset) iterator.next();
if(entry.getDevHash().equals(devHash)){
ipRangeAsset = entry;
break;
}
}
}
break;
}
}
return ipRangeAsset;
}3.性能对比
对于IP、IP范围数目为100万的情况下，对于50000个IP进行查找的耗时进行了比对，比对结果如下所示：
二分查找耗时为27ms，而普通查找为35974ms，耗时大概相差3个数量级，差距还是比较明显的。
下面附上完整代码：
IpRangeAsset.java
package com.formatengine.asset.v4;
import com.alibaba.fastjson.JSONObject;
import net.ripe.commons.ip.Ipv4;
import net.ripe.commons.ip.Ipv4Range;
import java.io.Serializable;
import java.util.HashMap;
import java.util.Map;
/**
* Created by dell on 2019/5/17.
* 主机型资产和网段型资产对应的类
*/
public class IpRangeAsset implements Serializable{
private String startIp;
private String endIp;
private String devHash;
private Long startIpInt;
private Long endIpInt;
//地理位置、资产id等增强信息存储之处
private Map additional = new HashMap();
public IpRangeAsset(String ip,String devHash,Map additional){
if(ip.contains("/")){
String[] tempIps = ip.split("/");
this.startIp = Ipv4.of(tempIps[0]).lowerBoundForPrefix(Integer.valueOf(tempIps[1])).toString();
Ipv4Range ipv4Range = Ipv4Range.parse(startIp+"/"+tempIps[1]);
this.endIp = ipv4Range.end().toString();
this.startIpInt = ipv4Range.start().asBigInteger().longValue();
this.endIpInt = ipv4Range.end().asBigInteger().longValue();
}else if(ip.contains("-")){
Ipv4Range ipv4Range = Ipv4Range.parse(ip);
this.startIp = ipv4Range.start().toString();
this.startIpInt = ipv4Range.start().asBigInteger().longValue();
this.endIp = ipv4Range.end().toString();
this.endIpInt = ipv4Range.end().asBigInteger().longValue();
}else{
this.startIp = ip;
this.endIp = ip;
this.devHash = devHash;
this.additional = additional;
startIpInt = Ipv4.of(ip).asBigInteger().longValue();
endIpInt = Ipv4.of(ip).asBigInteger().longValue();
}
this.devHash = devHash;
this.additional = additional;
}
public String getStartIp() {
return startIp;
}
public void setStartIp(String startIp) {
this.startIp = startIp;
}
public String getDevHash() {
return devHash;
}
public void setDevHash(String devHash) {
this.devHash = devHash;
}
public String getEndIp() {
return endIp;
}
public void setEndIp(String endIp) {
this.endIp = endIp;
}
public Long getStartIpInt() {
return startIpInt;
}
public void setStartIpInt(Long startIpInt) {
this.startIpInt = startIpInt;
}
public Long getEndIpInt() {
return endIpInt;
}
public void setEndIpInt(Long endIpInt) {
this.endIpInt = endIpInt;
}
public Map getAdditional() {
return additional;
}
public void setAdditional(Map additional) {
this.additional = additional;
}
public String toString(){
return JSONObject.toJSONString(this);
}
}
OutputNode.java
package com.formatengine.asset.v4;
import com.alibaba.fastjson.JSONObject;
import net.ripe.commons.ip.Ipv4;
import java.io.Serializable;
import java.util.HashSet;
import java.util.Set;
/**
* Created by dell on 2019/5/20.
* 用于进行资产范围切分输出的model
*/
public class OutputNode implements Serializable{
private long start;
private long end;
private String startIp;
private String endIp;
private Set indexAssetSet = null;
public OutputNode(long start, long end) {
this.start = start;
this.end = end;
this.indexAssetSet = new HashSet();
if(this.start != -1){
this.startIp = Ipv4.of(start).toString();
}
if(this.end != -1){
this.endIp = Ipv4.of(end).toString();
}
}
public long getStart() {
return start;
}
public void setStart(long start) {
this.start = start;
this.startIp = Ipv4.of(start).toString();
}
public long getEnd() {
return end;
}
public void setEnd(long end) {
this.end = end;
this.endIp = Ipv4.of(end).toString();
}
public Set getAssetIndexSet() {
return indexAssetSet;
}
public void setAssetIndexSet(Set indexSet) {
this.indexAssetSet = indexSet;
}
public void removeAssetIndex(IpRangeAsset val){
this.indexAssetSet.remove(val);
}
public void addAssetIndex(IpRangeAsset val){
this.indexAssetSet.add(val);
}
public String getStartIp() {
return startIp;
}
public String getEndIp() {
return endIp;
}
public String toString(){
return JSONObject.toJSONString(this);
}
}
GapRangeNode.java
package com.formatengine.asset.v4;
import java.io.Serializable;
/**
* Created by dell on 2019/5/20.
* 用于进行资产范围拆分的model
*/
public class GapRangeNode implements Serializable{
private long number;
private int index;
private boolean end;
public GapRangeNode(long number, int index, boolean end) {
this.number = number;
this.index = index;
this.end = end;
}
public long getNumber() {
return number;
}
public void setNumber(long number) {
this.number = number;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public boolean isEnd() {
return end;
}
public void setEnd(boolean end) {
this.end = end;
}
}
BinarySearch.java
package com.formatengine.asset.v4;
import net.ripe.commons.ip.Ipv4;
import java.io.Serializable;
import java.util.*;
/**
* Created by dell on 2019/5/17.
* 二分查找类
*/
public class BinarySearch implements Serializable{
public List init(List list){
List gapRangeNodeList = new ArrayList<>();
for(int i=0;i() {
@Override
public int compare(GapRangeNode o1, GapRangeNode o2) {
return o1.getNumber()-o2.getNumber()<0||(o1.getNumber()==o2.getNumber()&&o2.isEnd())?-1:1;
}
});
OutputNode outputNode = new OutputNode(-1,-1);
List resultList = new ArrayList();
for(int i=0;i 0){
OutputNode copyNode = new OutputNode(n,m);
Iterator iterator = outputNode.getAssetIndexSet().iterator();
while(iterator.hasNext()){
copyNode.addAssetIndex(iterator.next());
}
resultList.add(copyNode);
}
}
return resultList;
}
public IpRangeAsset search(long ipint,String devHash,List assetList){
int low = 0;
int high = assetList.size()-1;
IpRangeAsset ipRangeAsset = null;
while(low <= high){
int index = (low+high)/2;
if(ipint > assetList.get(index).getEnd()){
low = index + 1;
}else if(ipint < assetList.get(index).getStart()){
high = index - 1;
}else{
if(assetList.get(index).getAssetIndexSet().size() == 1){
ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
}else{
Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
while(iterator.hasNext()){
IpRangeAsset entry = (IpRangeAsset) iterator.next();
if(entry.getDevHash().equals(devHash)){
ipRangeAsset = entry;
break;
}
}
}
break;
}
}
return ipRangeAsset;
}
public IpRangeAsset normalSearch(long ipint,String devHash,List assetList){
IpRangeAsset ipRangeAsset = null;
for(int index=0;index= ipint && assetList.get(index).getEnd() <= ipint){
if(assetList.get(index).getAssetIndexSet().size() == 1){
ipRangeAsset = assetList.get(index).getAssetIndexSet().iterator().next();
}else{
Iterator iterator = assetList.get(index).getAssetIndexSet().iterator();
while(iterator.hasNext()){
IpRangeAsset entry = (IpRangeAsset) iterator.next();
if(entry.getDevHash().equals(devHash)){
ipRangeAsset = entry;
break;
}
}
}
break;
}
}
return ipRangeAsset;
}
public static void main(String[] args){
List list = new ArrayList();
list.add(new IpRangeAsset("192.168.1.100-192.168.1.120","AAA",null));
list.add(new IpRangeAsset("192.168.1.50-192.168.1.150","BBB",null));
list.add(new IpRangeAsset("10.67.1.1/24","CCC",null));
list.add(new IpRangeAsset("10.67.1.1","DDD",null));
list.add(new IpRangeAsset("10.67.1.255","EEE",null));
list.add(new IpRangeAsset("10.67.1.254-10.67.1.255","FFF",null));
list.add(new IpRangeAsset("10.67.1.0","HHH",null));
Random random = new Random();
//100万个资产
for(int i=0;i<1000000;i++){
String ipStart = String.valueOf(random.nextInt(255));
String ipEnd = String.valueOf(random.nextInt(255));
String randomStart = ipStart + "." + ipEnd + ".1.100";
String randomEnd = ipStart + "." + ipEnd + ".1.255";
list.add(new IpRangeAsset(randomStart + "-" + randomEnd, "", null));
}
BinarySearch binarySearch = new BinarySearch();
List assetList = binarySearch.init(list);
long startTime = System.currentTimeMillis();
for(int i=0;i<50000;i++){
String ip = "10.67.1.0";
binarySearch.search(Ipv4.of(ip).asBigInteger().longValue(),"DDD",assetList);
}
long endTime = System.currentTimeMillis();
System.out.println("binary search waste:"+(endTime-startTime)+"ms");
long startTime1 = System.currentTimeMillis();
for(int i=0;i<50000;i++){
String ip = "10.67.1.0";
binarySearch.normalSearch(Ipv4.of(ip).asBigInteger().longValue(), "DDD", assetList);
}
long endTime1 = System.currentTimeMillis();
System.out.println("normal search waste:"+(endTime1-startTime1)+"ms");
}
}
IP和大整型转换的依赖：
net.ripe.commons commons-ip-math 1.23
发表评论