Javaで複数のRange検索を比較的高速に行うコード

  • このエントリーをはてなブックマークに追加

複数のCIDR形式で記されたネットワークに該当するか、複数の定義された時間帯に現時刻が該当するか、などなどRange検索をしたい事がそれなりにあります。

単純なRange検索であれば、from <= v && v <= toのような単純なコードで判定できますが、Rangeの定義が複数ある場合、愚直に実装するとO(N)になります。それはとても嫌なのでO(log N)で判定できるようにします。全部自前で書いてやろうと思ったのですが、ライブラリに任せることにしました。

Guavaのコードを見ると、追加するたびにRangeをMergeするという方法を取っていました。あるクエリにHitする定義はどれだみたいな事は出来ないのですが、今回は含まれるか(contains)を判定できれば良いので妥協します。

実際のコード その1

ライブラリはデータ構造としてguavaRangeSet、CIDRの扱いとしてcommons-netSubnetUtilsを使います。コードの記述を減らすためにLombok、JSONの処理にはgsonを使いました。

pom.xml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>at.orz</groupId>
<artifactId>sample-range-checker</artifactId>
<version>1.0.0-SNAPSHOT</version>

<name>sample-range-checker</name>

<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<maven.compiler.source>11</maven.compiler.source>
<maven.compiler.target>11</maven.compiler.target>
</properties>

<dependencies>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.1-jre</version>
</dependency>
<dependency>
<groupId>commons-net</groupId>
<artifactId>commons-net</artifactId>
<version>3.6</version>
</dependency>
<dependency>
<groupId>com.google.code.gson</groupId>
<artifactId>gson</artifactId>
<version>2.8.5</version>
</dependency>
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.18.6</version>
<scope>provided</scope>
</dependency>
</dependencies>
</project>
App.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class App {

@Data
public static class AWSIpRanges implements Serializable {
private String syncToken;
private String createDate;
private List<IPv4Prefix> prefixes;
private List<IPv6Prefix> ipv6Prefixes;
@Data
public static class IPv4Prefix implements Serializable {
private String ipPrefix;
private String region;
private String service;
}
@Data
public static class IPv6Prefix implements Serializable {
private String ipv6Prefix;
private String region;
private String service;
}
}

public static class ImmutableIntRangeChecker {
@Delegate
private final ImmutableRangeSet<Integer> rangeSet;
public ImmutableIntRangeChecker(List<Range<Integer>> ranges) {
this.rangeSet = ImmutableRangeSet.unionOf(ranges);
}
public boolean isIPAddrContains(String ipAddr) {
int query = InetAddresses.coerceToInteger(InetAddresses.forString(ipAddr));
return rangeSet.contains(query);
}
}

public static void main(String[] args) throws IOException, InterruptedException {

URI awsIpRangesURI = URI.create("https://ip-ranges.amazonaws.com/ip-ranges.json");

// get aws-ip json file
HttpClient client = HttpClient.newHttpClient();
HttpRequest request = HttpRequest.newBuilder(awsIpRangesURI).build();
String json = client.send(request, HttpResponse.BodyHandlers.ofString(StandardCharsets.UTF_8)).body();

// parse json
Gson gson = new GsonBuilder().setFieldNamingPolicy(FieldNamingPolicy.LOWER_CASE_WITH_UNDERSCORES).create();
AWSIpRanges ipRanges = gson.fromJson(json, AWSIpRanges.class);

List<Range<Integer>> ranges = ipRanges.getPrefixes().stream()
.map(AWSIpRanges.IPv4Prefix::getIpPrefix) // List<IP-String>にする
.map(ip -> ip.contains("/") ? ip : ip + "/32") // SubnetUtilsでエラーにならないように
.map(ip -> {
// CIDR形式をパースし、ネットワークアドレスの範囲を求め、そのIPアドレスを32ビット変数に変換
SubnetUtils subnet = new SubnetUtils(ip);
subnet.setInclusiveHostCount(true);
SubnetUtils.SubnetInfo info = subnet.getInfo();
return Range.closed(info.asInteger(info.getLowAddress()), info.asInteger(info.getHighAddress()));
})
.collect(Collectors.toList());

ImmutableIntRangeChecker checker = new ImmutableIntRangeChecker(ranges);
System.out.println(checker.isIPAddrContains("35.172.155.127")); // -> true
System.out.println(checker.isIPAddrContains("8.8.8.8")); // -> false

}
}

実際のコード その2

Intで扱わない場合です。RangeクラスはComparatorの実装を要求しますがInetAddrクラスは実装していないので、ラッパークラスを作成します。

またCheckerクラスを汎用的に実装し、FunctionクラスによってKeyの変換も定義します。今回はStringからComparableInetAddrに変換する関数を定義します。

App2.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static class ComparableInetAddr implements Serializable, Comparable<ComparableInetAddr> {
@Delegate
private final InetAddress inetAddress;
private final int intIP;
private ComparableInetAddr(InetAddress inetAddress) {
this.inetAddress = inetAddress;
this.intIP = InetAddresses.coerceToInteger(inetAddress);
}
public ComparableInetAddr(String ipAddr) {
this(InetAddresses.forString(ipAddr));
}
@Override
public int compareTo(ComparableInetAddr o) {
return Integer.compare(this.intIP, o.intIP);
}
}

public static class ImmutableRangeChecker<T, C extends Comparable> {
@Delegate
private final ImmutableRangeSet<C> rangeSet;
private final Function<T, C> queryTransformer;
public ImmutableRangeChecker(List<Range<C>> ranges, Function<T, C> queryTransformer) {
this.rangeSet = ImmutableRangeSet.unionOf(ranges);
this.queryTransformer = queryTransformer;
}
public boolean contains(T value) {
C query = queryTransformer.apply(value);
return rangeSet.contains(query);
}
}

差分のコードだけ。ComparableIntAddrをRangeクラスに入れるようにした

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Range<ComparableInetAddr>> ranges = ipRanges.getPrefixes().stream()
.map(AWSIpRanges.IPv4Prefix::getIpPrefix)
.map(ip -> ip.contains("/") ? ip : ip + "/32")
.map(ip -> {
SubnetUtils subnet = new SubnetUtils(ip);
subnet.setInclusiveHostCount(true);
SubnetUtils.SubnetInfo info = subnet.getInfo();
// ここを変更した
return Range.closed(new ComparableInetAddr(info.getLowAddress()), new ComparableInetAddr(info.getHighAddress()));
})
.collect(Collectors.toList());

ImmutableRangeChecker<String, ComparableInetAddr> checker =
new ImmutableRangeChecker<>(
ranges,
ipString -> new ComparableInetAddr(InetAddresses.forString(ipString)));

System.out.println(checker.contains("35.172.155.127")); // false
System.out.println(checker.contains("8.8.8.8")); // true

時間の範囲を判定する場合

例えば、1日のうちの10時から12時と14時から16時。とか。1週間のうちの月曜日の午前中と火曜日の午前中とか。前者の場合は0から86400の整数として扱えば良いし、後者は月曜始まりの0時を0とした整数として扱うとかすれば良いと思います。

もしくは上記のコードでComparableが実装されているDate系のクラスを使えば良いと思います。

その他

今回はImmutableRangeSetを使いましたが、他にもTreeRangeSetの実装があります。こっちはInstanceを生成後にRangeを追加することができます。個人的にはIntegerではなくPrimitiveのintで扱いたいです。

RangeがMergeされるのを確認したコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Test
public void rangeSample1() {
ImmutableList<Range<Integer>> x = ImmutableList.of(Range.open(1, 100), Range.open(200, 300)).asList();
TreeRangeSet<Integer> im = TreeRangeSet.create();
im.addAll(x);
im.add(Range.open(50, 250));
System.out.println(im); // [(1..300)]
}
@Test
public void rangeSample2() {
ImmutableList<Range<Integer>> x = ImmutableList.of(Range.closed(1, 100), Range.closed(200, 300)).asList();
TreeRangeSet<Integer> im = TreeRangeSet.create();
im.addAll(x);
im.add(Range.open(50, 150)); // [[1..150), [200..300]]
System.out.println(im);
}

参考

CIDRに限ってしまえばもっと高速にできるみたいです。