IpTree
- IP 필터 구현 이야기 발표 자료 2013.07.03
- IP 필터 만들기 2, 트리 기반 IP 목록 구현과 IP 필터 성능 2013.06.27 (2)
IP 필터 구현 이야기 발표 자료
IP 필터 만들기 2, 트리 기반 IP 목록 구현과 IP 필터 성능
지난 글 "IP 필터 만들기 1, 아이디어"에서 트리 구조로 허용/차단 IP 목록을 표시하는 방법을 정리해봤는데, 이번 글에서는 실제 구현을 살펴보도록 하겠다. 참고로, 본 글에서 설명하는 모든 코드는 https://github.com/madvirus/ip-filter 에 공개되어 있으니 참고하기 바란다.
IP 트리 구성을 위한 클래스: IpTree, NumberNode
ip-filter 모듈에서 사용하는 IP 목록은 아래와 같은 방식으로 표현한다.
1.2.3.4
1.2.3.64/26
5.6.7.*
10.20.*
30.*
이를 트리로 표현하기 위해 두 개의 클래스를 작성하였다.
- IpTree: 트리의 관리 및 특정 IP가 트리로 표현되는지 확인해주는 기능
- NumberNode: 트리의 각 노드를 표현
- 숫자
- 별표(*)
- 네트워크주소표현 (예, 128/25)
- isSimpleNumber: 값이 숫자면 true, 별표나 네트워크주소 표현이면 false
- allAccept: 값이 별표면 true, 아니면 false
- 네트워크 주소 관련 필드 (값 형식이 A/B 인 경우)
- lastValueOfNetworkNumber: A/B 형식에서 A 값. 예, 128/25 에서 128
- filterNumber: 데이터 비교시에 사용할 숫자 (뒤에서 설명)
- 정확한 숫자는 simpleChildNodeMap 에 <숫자값, 자식노드>로 보관 (숫자값이 키)
- A/B 형식의 패턴 및 "*"은 patternChildNodes 에 추가
IpTree 클래스는 다음의 두 기능을 제공한다.
- IP 문자열을 트리로 구성해주는 기능을 제공한다.
- 특정 IP 문자열이 트리에 매칭되는지 확인하는 기능을 제공한다.
IpTree 클래스는 아래와 같이 사용한다.
IpTree tree = new IpTree();
tree.add("1.2.3.4");
tree.add("1.2.4.5");
tree.add("1.2.5.*");
tree.add("1.2.6.128/25");
tree.containsIp("1.2.3.4"); // true
tree.containsIp("1.2.3.5"); // false
tree.containsIp("1.2.6.129"); // true
tree.containsIp("1.2.5.4"); // true
실제 IP Filter 기능 구현
IP 필터는 다음과 같이 두 개의 IP 목록을 갖는다.
- 허용 IP 목록
- 차단 IP 목록
성능 확인
ConfigIpFilter의 IP 필터 기능의 성능을 측정해 보았다. 이를 위해 다음의 IP 설정 목록을 차단 목록으로 추가하였다. 이 목록은 37,538 개 이며, 전체 목록은 https://github.com/madvirus/ip-filter/wiki/ip-list-config-for-performance-test 에서 확인할 수 있다.
1.0.1.*
1.0.2.*
1.0.3.*
...
이 IP 설정이 포함하는 IP 개수는 약 3억 3천만이다.
테스트는 아래와 같이 진행하였다.
- 테스트 과정
- 위 IP 설정 목록을 이용해서 차단 IP 목록으로 사용하는 IpFilter 객체 생성
- 테스트 IP 범위 목록 중 랜덤하게 5개의 패턴을 뽑아, 그 패턴에 해당하는 IP 들을 차례대로 테스트 진행
- 5개의 패턴이 적어 보일 수 있으나, 36.16.0.0~36.37.255.255 범위는 약 144만 개의 IP를 테스트
- 각 IP를 검사하는 시간을 누적해서 평균 값 구함
- 이 테스트를 5회 진행
- 트리 기반으로 IP 목록을 유지하는 ConfigIpFilter 클래스
- List를 이용해서 IP 목록을 유지하는 테스트용 ListIpFilter 클래스 (비교 목적으로 작성)
- IP 확인 요청이 왔을 때, 허용IP/차단IP 목록을 순차적으로 비교 확인
성능 비교 결과
테스트는 노트북에 진행했으면 노트북의 사양은 아래와 같다.
- Intel Core i5-2457M @ 1.6 GHz
- Windows 7 64bit
- JDK 6 (1.6.0_26)
성능 비교 결과 표를 아래와 같이 정리하였다.
[표1] 1개 쓰레드로 실행한 결과
- | 트리 방식 | 리스트 방식 | ||||
회차 | 실행 회수 | 실행 시간 합 | 실행 시간 평균 | 실행 회수 | 실행 시간 합 | 실행 시간 평균 |
1 | 199,680 | 678 | 0.003400 | 50,944 | 28,631 | 0.562029 |
2 | 1,450,240 | 3,648 | 0.002516 | 1,212,928 | 181,893 | 0.152436 |
3 | 22,016 | 196 | 0.008931 | 12,800 | 6,397 | 0.499768 |
4 | 804,352 | 2,109 | 0.002622 | 377,088 | 152,709 | 0.404970 |
5 | 1,120,256 | 2,723 | 0.002431 | 273,920 | 14,964 | 0.054632 |
평균 | 0.003980 | 평균 | 0.334767 |
두 방식에서 확연한 속도 차이가 느껴진다. 트리 기반의 IP 필터 기능은 한 개 검사하는 데 0.004 밀리초(즉, 0.000004 초) 걸리는데 반해 리스트 방식은 0.335 밀리초로 (즉, 0.000335 초) 약 80배 이상 차이가 난다. 또한, 트리 방식은 실행 시간 평균이 균일한데 반해, 리스트 방식은 실행 시간 평균 10 배 이상 차이가 나기도 한다.
참고로, 트리 방식과 달리 리스트 방식이 이렇게 들쑥 날쑥한 이유는 리스트 방식이 풀스캔을 하기 때문이다. 트리 방식은 DB에 비교하면 인덱스를 사용해서 검색하는 방식이고, 리스트 방식은 인덱스 없이 전체 데이터를 스캔해서 검색하는 방식이다. 따라서, 리스트 방식에서 비교 대상이 앞쪽에 위치하면 검색 속도가 빠르고, 비교 대상이 뒤쪽에 위치하면 검색 속도가 그 만큼 느려지게 된다.
위와 동일한 테스트를 동시에 10개 쓰레드를 실행해서 테스트 해 보았다. 최대한 동시에 실행되는 효과를 만들기 위해 한 쓰레드가 최대 10만개의 IP만 검사하도록 제한을 걸었다. 테스트 결과는 아래와 같다.
[표2] 10개 쓰레드로 실행한 결과 (1쓰레드 당 최대 10만개까지만 검사)
- | 트리 방식 | 리스트 방식 | ||||
회차 | 실행 회수 | 실행 시간 합 | 실행 시간 평균 | 실행 회수 | 실행 시간 합 | 실행 시간 평균 |
1 | 695,840 | 7,592 | 0.010912 | 672,033 | 745,404 | 1.110667 |
2 | 816,640 | 6,325 | 0.007746 | 847,712 | 837,813 | 0.988323 |
3 | 698,304 | 6,301 | 0.009024 | 720,576 | 633,170 | 1.101748 |
4 | 901,120 | 8,216 | 0.009118 | 792,000 | 976,851 | 1.233398 |
5 | 664,096 | 5,576 | 0.008397 | 693,024 | 1,162,127 | 1.677894 |
|
| 평균 | 0.009039 |
| 평균 | 1.205352 |
1개 쓰레드를 이용한 경우와 10개 쓰레드를 이용한 경우를 비교해보면, 트리 방식에 비해 리스트 방식의 평균 실행 시간이 더 크게 증가한 것을 알 수 있다.
비교 목적으로 사용한 ListIpFilter 클래스 코드
트리 구조와 성능 비교 하기 위해 작성한 ListIpFilter의 코드는 아래와 같다.
public class ListIpFilter implements IpFilter {
private boolean defaultAllow;
private boolean allowFirst;
private List<IpPattern> allowIpPatterns = new ArrayList<IpPattern>();
private List<IpPattern> denyIpPatterns = new ArrayList<IpPattern>();
public ListIpFilter(Config config) {
defaultAllow = config.isDefaultAllow();
allowFirst = config.isAllowFirst();
for (String ipPattern : config.getAllowList())
allowIpPatterns.add(new IpPattern(ipPattern));
for (String ipPattern : config.getDenyList())
denyIpPatterns.add(new IpPattern(ipPattern));
}
@Override
public boolean accept(String ip) {
if (allowFirst) {
if (isAllowIp(ip)) return true;
if (isDenyIp(ip)) return false;
} else {
if (isDenyIp(ip)) return false;
if (isAllowIp(ip)) return true;
}
return defaultAllow;
}
private boolean isAllowIp(String ip) {
for (IpPattern ipPattern : allowIpPatterns) {
if (ipPattern.isMatch(ip))
return true;
}
return false;
}
private boolean isDenyIp(String ip) {
for (IpPattern ipPattern : denyIpPatterns) {
if (ipPattern.isMatch(ip))
return true;
}
return false;
}
private class IpPattern {
private String exactMatchingPart;
private boolean exactMatchingPattern = false;
private boolean acceptAllPattern = false;
private boolean rangePattern = false;
private int fromNumberInRangePattern = 0;
private int toNumberInRangePattern = 0;
public IpPattern(String ipPattern) {
if (ipPattern.endsWith("*")) {
acceptAllPattern = true;
exactMatchingPart = ipPattern.substring(0, ipPattern.length() - 1);
} else {
int slashIdx = ipPattern.indexOf("/");
if (slashIdx == -1) {
exactMatchingPart = ipPattern;
exactMatchingPattern = true;
} else {
int lastDotIdx = ipPattern.lastIndexOf(".");
exactMatchingPart = ipPattern.substring(0, lastDotIdx + 1);
int rangeNumber = Integer.parseInt(ipPattern.substring(lastDotIdx + 1, slashIdx));
int bitLength = Integer.parseInt(ipPattern.substring(slashIdx + 1));
rangePattern = true;
fromNumberInRangePattern = rangeNumber;
switch (bitLength) {
case 24:
toNumberInRangePattern = fromNumberInRangePattern + 0xFF;
break;
case 25:
toNumberInRangePattern = fromNumberInRangePattern + 0x7F;
break;
case 26:
toNumberInRangePattern = fromNumberInRangePattern + 0x3F;
break;
case 27:
toNumberInRangePattern = fromNumberInRangePattern + 0x1F;
break;
case 28:
toNumberInRangePattern = fromNumberInRangePattern + 0x0F;
break;
case 29:
toNumberInRangePattern = fromNumberInRangePattern + 0x07;
break;
case 30:
toNumberInRangePattern = fromNumberInRangePattern + 0x03;
break;
}
}
}
}
public boolean isMatch(String ip) {
if (exactMatchingPattern)
return ip.equals(exactMatchingPart);
if (acceptAllPattern)
return ip.startsWith(exactMatchingPart);
if (rangePattern) {
if (!ip.startsWith(exactMatchingPart)) return false;
int lastNumberOfIp = Integer.parseInt(ip.substring(exactMatchingPart.length()));
return lastNumberOfIp >= fromNumberInRangePattern
&& lastNumberOfIp <= toNumberInRangePattern;
}
return false;
}
}
}
참고 자료
- ip-filter 소스 코드: https://github.com/madvirus/ip-filter