Combinator Parser,
ip 필터,
ip-filter,
IpFilter,
IpTree,
NumberNode,
Scala,
Tree,
구현 이야기,
스카라,
스칼라,
콤비네이터 파서,
트리
주요글: 도커 시작하기
IpTree
- IP 필터 구현 이야기 발표 자료 2013.07.03
- IP 필터 만들기 2, 트리 기반 IP 목록 구현과 IP 필터 성능 2013.06.27 (2)
IP 필터 구현 이야기 발표 자료
2013. 7. 3. 00:30
IP 필터 만들기 2, 트리 기반 IP 목록 구현과 IP 필터 성능
2013. 6. 27. 14:25
지난 글 "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: 트리의 각 노드를 표현
NumberNode 구현
NumberNode는 트리의 루트 노드부터 말단 노드까지를 표현한다. 노드는 위 그림에서 보듯 세 가지 종류의 값을 갖는다.
- 숫자
- 별표(*)
- 네트워크주소표현 (예, 128/25)
이를 표현하기 위해 NumberNode 객체의 생성 부분을 아래와 같이 구현하였다.
public class NumberNode {
private final String number;
private boolean isSimpleNumber;
private int filterNumber;
private int lastValueOfNetworkNumber;
private boolean allAccept;
public NumberNode(String number) {
this.number = number;
processPattern();
}
private static int[] filterNumbers = {
0x00, // 24
0x80, // 25
0xC0, // 26
0xE0, // 27
0xF0, // 28
0xF8, // 29
0xFC // 30
};
private void processPattern() {
if (number.equals("*")) {
isSimpleNumber = false;
allAccept = true;
return;
}
int slashIdx = number.indexOf("/");
if (slashIdx == -1) {
isSimpleNumber = true;
return;
}
// 64/26과 같은 네트워크 주소 형식 처리 위한 코드
this.lastValueOfNetworkNumber = Integer.parseInt(number.substring(0, slashIdx));
int bitsOfNetworkNumber = Integer.parseInt(number.substring(slashIdx + 1));
this.filterNumber = filterNumbers[bitsOfNetworkNumber - 24];
this.isSimpleNumber = false;
}
위 코드에서 각 필드는 다음과 같다.
- isSimpleNumber: 값이 숫자면 true, 별표나 네트워크주소 표현이면 false
- allAccept: 값이 별표면 true, 아니면 false
- 네트워크 주소 관련 필드 (값 형식이 A/B 인 경우)
- lastValueOfNetworkNumber: A/B 형식에서 A 값. 예, 128/25 에서 128
- filterNumber: 데이터 비교시에 사용할 숫자 (뒤에서 설명)
값 일치 여부 확인
NumberNode를 생성한 뒤에, 해당 노드가 특정 숫자와 매칭되는지 여부를 확인하는 기능이 필요하다. 이를 위해 isMatch() 메서드를 아래와 같이 구현하였다.
public class NumberNode {
private final String number;
private boolean isSimpleNumber;
private int filterNumber;
private int lastValueOfNetworkNumber;
private boolean allAccept;
public boolean isMatch(String number) {
if (allAccept) return true; // this.number가 "*" 인 경우
if (isSimpleNumber) return this.number.equals(number); // this.number가 숫자인 경우
// this.number가 A/B 형식인 경우
int filtered = filterNumber & Integer.parseInt(number);
return filtered == lastValueOfNetworkNumber;
}
위 코드는 아래와 같이 작동한다.
NumberNode n1 = new NumberNode("128");
n1.isMatch("10"); // false
n1.isMatch("128"); // true
NumberNode n2 = new NumberNode("*");
n2.isMatch("0"); // true
n2.isMatch("123"); // true
NumberNode n3 = new NumberNode("128/25");
n3.isMatch("128"); // true
n3.isMatch("200"); // true
n3.isMatch("255"); // true
n3.isMatch("127"); // false
n3.isMatch("100"); // false
[박스] 네트워크 주소
"64/26"에 대해 약간의 설명이 필요할 것 같다. 흔히 네트워크 주소라 하면, 아래와 같이 표시한다.
2.4.8.64/26
여기서 숫자들은 각각 한 바이트를 차지하며, 여기서 마지막 64/26은 네트워크 범위를 지정하는 숫자가 된다. 이 예의 경우 64는 네트워크 범위 기준점이 되는 네 번째 바이트의 값이며, 26은 전체 주소에서 네트워크 주소로 사용될 비트 길이가 된다. 위 숫자에서 2.4.8.64는 아래와 같이 비트로 표현할 수 있는데,
00000010 00000100 00001000 01000000 (2 4 8 64)
여기서 앞에서 26개 비트, 즉 아래 값이 2.4.8.64/26 네트워크에서 사용할 네트워크 주소가 된다.
00000010 00000100 00001000 01 (앞에서부터 26비트)
이 네트워크 주소에서 사용할 수 있는 주소 범위는 아래와 같다.
00000010 00000100 00001000 01000000 ~
00000010 00000100 00001000 01111111
즉, 마지막 주소로 64 부터 127 까지가 64/26에 해당하는 숫자 범위이다. 따라서, 어떤 주소가 이 네트워크 주소 범위에 포함되는 확인하려면 다음과 같이 64/26에 해당하는 비교 값과 실제 주소 값을 AND 연산해서 네트워크 주소값이 나오는지 확인해보면 된다.
11111111 11111111 11111111 11000000 (필터 위한 비교 값)
00000010 00000100 00001000 01001100 (실제 주소)
---------------------------------- (AND 연산)
00000010 00000100 00001000 01000000 -> 네트워크 주소 값과 일치하므로, 이 주소는 네트워크 범위에 포함
앞서 NumberNode는 이 방식을 사용해서 특정 숫자가 범위에 포함되는 지 확인한다.
자식 노드 생성을 위한 메서드
NumberNode는 자식 노드를 생성/보관/검색하는 기능을 제공함으로써, 뒤에서 설명할 IpTree가 내부적으로 노드를 쉽게 구성할 수 있도록 하였다. 이와 관련된 코드는 아래와 같다.
public class NumberNode {
...
private Map<String, NumberNode> simpleChildNodeMap = new HashMap<String, NumberNode>();
private List<NumberNode> patternChildNodes = new ArrayList<NumberNode>();
public NumberNode createOrGetChildNumber(String numberPattern) {
if (simpleChildNodeMap.containsKey(numberPattern))
return simpleChildNodeMap.get(numberPattern);
for (NumberNode patternChild : patternChildNodes)
if (patternChild.number.equals(numberPattern))
return patternChild;
NumberNode childNode = new NumberNode(numberPattern);
if (childNode.isSimpleNumber)
simpleChildNodeMap.put(number, childNode);
else
patternChildNodes.add(childNode);
return childNode;
}
public NumberNode findMatchingChild(String number) {
NumberNode simpleChildNode = simpleChildNodeMap.get(number);
if (simpleChildNode != null) return simpleChildNode;
for (NumberNode patternChildNode : patternChildNodes)
if (patternChildNode.isMatch(number))
return patternChildNode;
return null;
}
...
}
createOrGetChildNumber() 메서드는 NumberNode는 자식 노드를 두 가지 방식으로 보관한다.
- 정확한 숫자는 simpleChildNodeMap 에 <숫자값, 자식노드>로 보관 (숫자값이 키)
- A/B 형식의 패턴 및 "*"은 patternChildNodes 에 추가
createOrGetChildNumber() 메서드는 동일한 숫자를 가진 자식 노드가 존재하면 그 노드를 리턴하고, 존재하지 않으면 새로 생성해서 자식 노드로 추가한다. 이 메서드는 IpTree 클래스가 IP 문자열로부터 트리 노드를 생성할 때 사용된다.
findMatchingChild() 메서드는 입력받은 숫자와 매칭되는 자식 노드를 구해서 리턴해준다. 이 메서드는 IpTree에서 특정 IP 문자열이 트리에 매칭되는 지 확인하기 위해 사용된다.
IpTree 구현
IpTree 클래스는 다음의 두 기능을 제공한다.
- IP 문자열을 트리로 구성해주는 기능을 제공한다.
- 특정 IP 문자열이 트리에 매칭되는지 확인하는 기능을 제공한다.
실제 구현은 아래와 같다.
public class IpTree {
private NumberNode root = new NumberNode("");
public void add(String ip) {
String[] ipNumbers = ip.split("\\.");
NumberNode node = root;
for (String number : ipNumbers) {
node = node.createOrGetChildNumber(number);
}
}
public boolean containsIp(String ip) {
String[] ipNumbers = ip.split("\\.");
NumberNode node = root;
for (String number : ipNumbers) {
node = node.findChildNumber(number);
if (node == null)
return false;
if (node.isAllAccept())
return true;
}
return true;
}
}
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 목록
IP 필터는 이 두 개의 IP 목록을 별도의 IpTree 타입 필드를 이용해서 보관한다. 실제 IpFilter의 구현은 다음과 같다.
public class ConfigIpFilter implements IpFilter {
private boolean defaultAllow;
private IpTree allowIpTree;
private IpTree denyIpTree;
private boolean allowFirst;
public ConfigIpFilter(Config config) {
defaultAllow = config.isDefaultAllow();
allowFirst = config.isAllowFirst();
allowIpTree = makeIpTree(config.getAllowList());
denyIpTree = makeIpTree(config.getDenyList());
}
private IpTree makeIpTree(List<String> ipList) {
IpTree ipTree = new IpTree();
for (String ip : ipList)
ipTree.add(ip);
return ipTree;
}
@Override
public boolean accept(String ip) {
if (allowFirst) {
if (allowIpTree.containsIp(ip)) return true;
if (denyIpTree.containsIp(ip)) return false;
} else {
if (denyIpTree.containsIp(ip)) return false;
if (allowIpTree.containsIp(ip)) return true;
}
return defaultAllow;
}
}
ConfigIpFilter는 Config로부터 허용 IP 목록과 차단 IP 목록을 읽어와 각각을 위한 IpTree를 생성한다. accept() 메서드는 이 IpTree 객체를 이용해서 지정한 IP가 차단 IP인지, 허용 IP인지 여부를 결정한다. 참고로, ConfigIpFilter 클래스의 사용법은 아래와 같다.
@Test
public void shouldReturnTrueToAllowedIpAndReturnFalseToDeniedIp() {
Config config = new Config();
config.setDefaultAllow(true);
config.setAllowFirst(true);
config.allow("1.2.3.4");
config.allow("1.2.3.5");
config.allow("1.2.3.64/26"); // // 01xxxxxx 범위 : 64~127
config.deny("5.6.7.8");
config.deny("101.102.103.32/27"); // 001xxxxx 범위: 32~63")
IpFilter ipFilter = new ConfigIpFilter(config);
assertTrue(ipFilter.accept("1.2.3.4"));
assertTrue(ipFilter.accept("1.2.3.5"));
assertTrue(ipFilter.accept("1.2.3.64"));
assertTrue(ipFilter.accept("1.2.3.65"));
assertTrue(ipFilter.accept("1.2.3.127"));
}
성능 확인
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.*
...
101.253.*
101.254.*
103.1.8.*
...
106.187.34.17
106.187.34.18
106.187.34.19
...
223.223.207.*
223.240.*
223.241.*
...
223.255.252.*
223.255.253.*
이 IP 설정이 포함하는 IP 개수는 약 3억 3천만이다.
테스트는 아래와 같이 진행하였다.
- 테스트 과정
- 위 IP 설정 목록을 이용해서 차단 IP 목록으로 사용하는 IpFilter 객체 생성
- 테스트 IP 범위 목록 중 랜덤하게 5개의 패턴을 뽑아, 그 패턴에 해당하는 IP 들을 차례대로 테스트 진행
- 5개의 패턴이 적어 보일 수 있으나, 36.16.0.0~36.37.255.255 범위는 약 144만 개의 IP를 테스트
- 각 IP를 검사하는 시간을 누적해서 평균 값 구함
- 이 테스트를 5회 진행
비교 테스트를 위해 두 개의 IpFilter에 대해 테스트를 진행하였다..
- 트리 기반으로 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
