주변 지오펜스 조회 성능 개선 (like 주변 맛집 검색)

지오펜스 후보 조회 성능 개선

마주친 문제

드론 충돌회피 시스템에서 현재 드론 위치를 기준으로 지오펜스 침범/근접 여부를 실시간으로 판단해야 했다.
DB에는 다수의 지오펜스 데이터가 존재했고, 드론 위치 이벤트가 발생할 때마다 모든 지오펜스 Polygon과 현재 위치를 비교하는 방식은 지오펜스 개수에 비례해 연산량이 증가하는 문제가 있었다.

초기 구조는 다음과 같은 한계를 가졌다.

현재 드론 위치 수신
        ↓
전체 지오펜스 목록 순회
        ↓
각 지오펜스 Polygon과 거리/포함 여부 계산
        ↓
O(N) 연산 반복

드론 위치 이벤트는 지속적으로 발생하기 때문에, 매번 전체 지오펜스를 대상으로 정밀 기하 연산을 수행하는 구조는 실시간 평가에 적합하지 않았다.
따라서 현재 위치 기준 검색 반경 내에 존재할 가능성이 있는 지오펜스 후보만 먼저 추출하고, 해당 후보에 대해서만 정밀 침범/거리 판단을 수행하는 구조가 필요했다.

---

1차 해결: Grid Cell 기반 GeofenceSpatialIndex 적용

전체 지오펜스를 매번 순회하지 않기 위해 위경도 기반 Grid Index를 직접 구현했다.
공간을 일정 크기의 Grid Cell로 나누고, 지오펜스의 bounding box가 걸치는 모든 Cell에 해당 지오펜스를 등록했다.

조회 시에는 현재 드론 위치와 검색 반경을 기준으로 검색 bounding box를 만들고, 이 box가 걸치는 Grid Cell만 순회하여 후보 지오펜스를 추출했다.

 Grid Cell 생성 관련코드

// 지오펜스 bounding box가 걸치는 Grid Cell 범위 계산
GeoGridKey minKey = GeoGridKey.from(
        geofence.getMinLatDeg(),
        geofence.getMinLonDeg(),
        gridSizeDeg
);

GeoGridKey maxKey = GeoGridKey.from(
        geofence.getMaxLatDeg(),
        geofence.getMaxLonDeg(),
        gridSizeDeg
);

// 지오펜스가 걸치는 모든 Grid Cell에 같은 geofence를 등록
for (int lat = minKey.getLatIndex(); lat <= maxKey.getLatIndex(); lat++) {
    for (int lon = minKey.getLonIndex(); lon <= maxKey.getLonIndex(); lon++) {
        GeoGridKey key = new GeoGridKey(lat, lon);

        index.computeIfAbsent(key, k -> new ArrayList<>())
                .add(geofence);
    }
}

 

전체 공간을 Grid Cell로 분할

+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    | G1 | G1 | G1 |    |
+----+----+----+----+----+
|    | G1 | G1 | G1 |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+

G1 지오펜스가 걸치는 Cell마다 G1을 등록

조회 흐름은 다음과 같다.

현재 위치 기준 검색 반경
        ↓
검색 반경을 감싸는 bounding box 생성
        ↓
bounding box가 걸치는 Grid Cell 계산
        ↓
해당 Cell에 등록된 지오펜스만 후보로 조회
        ↓
geofenceId 기준 중복 제거

이 방식으로 전체 지오펜스를 매번 순회하지 않고, 현재 위치 주변 후보군만 추출할 수 있었다.

주변 지오펜스 조회 관련 코드

SearchRange range = SearchRange.from(latDeg, lonDeg, radiusM);

GeoGridKey minKey = GeoGridKey.from(
        range.getMinLat(),
        range.getMinLon(),
        gridSizeDeg
);

GeoGridKey maxKey = GeoGridKey.from(
        range.getMaxLat(),
        range.getMaxLon(),
        gridSizeDeg
);

// 같은 지오펜스가 여러 Cell에서 조회될 수 있으므로 중복 제거
Map<String, GeofenceModel> dedup = new LinkedHashMap<>();

for (int lat = minKey.getLatIndex(); lat <= maxKey.getLatIndex(); lat++) {
    for (int lon = minKey.getLonIndex(); lon <= maxKey.getLonIndex(); lon++) {
        GeoGridKey key = new GeoGridKey(lat, lon);
        List<GeofenceModel> bucket = index.get(key);

        if (bucket == null) {
            continue;
        }

        for (GeofenceModel geofence : bucket) {
            if (intersects(geofence, range)) {
                dedup.put(geofence.getGeofenceId(), geofence);
            }
        }
    }
}

return new ArrayList<>(dedup.values());

---

추가로 발견한 문제

Grid Index 방식은 후보군 축소에는 효과가 있었지만, 지오펜스가 “점”이 아니라 “면” 데이터라는 점에서 성능 한계가 발생했다.

지오펜스 하나가 여러 Grid Cell에 걸치기 때문에, 하나의 지오펜스가 여러 Cell에 중복 등록되었다.

큰 지오펜스 하나가 여러 Cell에 걸치는 경우

+----+----+----+----+----+----+
| G1 | G1 | G1 | G1 | G1 | G1 |
+----+----+----+----+----+----+
| G1 | G1 | G1 | G1 | G1 | G1 |
+----+----+----+----+----+----+
| G1 | G1 | G1 | G1 | G1 | G1 |
+----+----+----+----+----+----+

G1 하나가 다수의 Cell에 반복 등록됨

ex)
cell(1,1) -> [G1]
cell(1,2) -> [G1]
cell(1,3) -> [G1]

cell(2,1) -> [G1]
cell(2,2) -> [G1]
cell(2,3) -> [G1]

cell(3,1) -> [G1]
cell(3,2) -> [G1]
cell(3,3) -> [G1]

Grid 크기를 작게 잡을수록 후보 조회의 오차 범위는 줄어들지만, 반대로 지오펜스 하나 등록되는 Cell 수가 급격히 증가했다.
예를 들어 위도 기준 0.001도는 약 111m 수준이고, 더 세밀한 Grid를 사용하면 큰 지오펜스 하나가 수백 개 이상의 Cell에 등록될 수 있었다.

이로 인해 다음과 같은 문제가 발생했다.

- 지오펜스 개수가 많아질수록 인덱스 rebuild 비용 증가
- 지오펜스 면적이 클수록 하나의 지오펜스가 다수 Cell에 중복 등록
- Grid 크기를 작게 잡을수록 메모리 사용량 증가
- 등록/수정/삭제 이벤트 발생 시 전체 인덱스 재구성 비용 증가

결과적으로 Grid Index는 전체 순회 문제를 완화했지만, 지오펜스 데이터가 증가하거나 큰 지오펜스가 많아질수록 인덱스 생성 비용과 메모리 사용량이 커지는 한계가 있었다.

---

최종 개선: JTS STRtree 기반 GeofenceStrtreeIndex 적용

Grid 방식의 중복 등록 문제를 해결하기 위해 Java 진영의 공간 기하 라이브러리인 JTS를 검토했고, JTS에서 제공하는 STRtree를 적용했다.

STRtree는 지오펜스를 Grid Cell마다 쪼개 저장하지 않고, 각 지오펜스의 Geometry를 감싸는 Envelope, 즉 bounding box를 공간 인덱스에 등록한다.

실제 지오펜스 Polygon

        /\
       /  \
      /____\

Polygon을 감싸는 Envelope

   +--------+
   |   /\   |
   |  /__\  |
   +--------+

STRtree에는 Envelope 기준으로 등록

Grid 방식과 비교하면 다음과 같다.

Grid 방식
- 공간을 작은 Cell로 나눔
- 지오펜스가 걸치는 모든 Cell에 반복 등록
- 큰 지오펜스일수록 중복 등록 증가

cell(1,1) -> G1
cell(1,2) -> G1
cell(2,1) -> G1
cell(2,2) -> G1

STRtree 방식
- 지오펜스별 Envelope를 공간 인덱스에 등록
- 검색 Envelope와 겹치는 후보만 빠르게 조회
- 후보에 대해서만 정밀 기하 연산 수행

Envelope(G1) -> G1

STRtree 생성 관련 코드

STRtree newIndex = new STRtree();

for (GeofenceModel geofence : store.values()) {
    Geometry geometry = geofence.getJtsGeometry();

    if (geometry == null || geometry.isEmpty()) {
        continue;
    }

    // 지오펜스 Geometry를 감싸는 Envelope를 STRtree에 등록
    newIndex.insert(geometry.getEnvelopeInternal(), geofence);
}

newIndex.build();
activeIndex.set(newIndex);

 

조회 흐름은 다음과 같이 개선했다.

현재 드론 위치 수신
        ↓
현재 위치 기준 검색 Envelope 생성
        ↓
STRtree에서 검색 Envelope와 겹치는 지오펜스 후보 조회
        ↓
후보에 대해서만 JTS covers()/distance() 수행
        ↓
침범 중이거나 반경 이내인 지오펜스만 반환

조회 관련 코드

Envelope searchEnv = new Envelope(
        localPoint.getX() - radiusM,
        localPoint.getX() + radiusM,
        localPoint.getY() - radiusM,
        localPoint.getY() + radiusM
);

// 검색 Envelope와 겹치는 후보만 조회
List<GeofenceModel> candidates = activeIndex.get().query(searchEnv);

List<GeofenceModel> result = new ArrayList<>();

for (GeofenceModel geofence : candidates) {
    boolean invaded = geofence.getJtsGeometry().covers(point);
    double distanceM = invaded
            ? 0.0
            : geofence.getJtsGeometry().distance(point);

    if (invaded || distanceM <= radiusM) {
        result.add(geofence);
    }
}

return result;

 

 

이를 통해 전체 지오펜스를 매번 순회하지 않고, 공간 인덱스를 통해 1차 후보를 빠르게 줄인 뒤 정밀 계산을 수행하도록 개선했다.

또한 인덱스 갱신 시 기존 Grid 방식처럼 기존 인덱스를 clear()한 뒤 다시 채우는 방식이 아니라, 새 STRtree를 별도로 완성한 뒤 AtomicReference로 교체하는 copy-build-swap 구조를 적용했다.

기존 activeIndex 유지
        ↓
새 STRtree 생성 및 build
        ↓
build 완료 후 activeIndex swap
        ↓
조회 스레드는 항상 완성된 인덱스만 참조

이를 통해 인덱스 rebuild 중에도 실시간 조회 로직이 비어 있거나 일부만 구성된 인덱스를 참조하지 않도록 안정성을 개선했다.

---

결과

Grid Cell 기반 후보 조회를 통해 전체 순회 문제를 1차적으로 해결했고, 이후 Grid 방식의 중복 등록 및 rebuild 비용 증가 한계를 JTS STRtree 기반 공간 인덱스로 개선했다.

최종적으로 지오펜스 후보 조회 구조를 다음과 같이 변경했다.

Before
전체 지오펜스 순회
또는
Grid Cell 기반 후보 조회 + 다수 Cell 중복 등록

After
STRtree Envelope 기반 후보 조회
+ 후보 대상 JTS 정밀 거리/포함 판단
+ copy-build-swap 기반 안전한 인덱스 갱신

이를 통해 지오펜스 데이터 증가에 따른 후보 조회 비용과 인덱스 관리 부담을 줄이고, 실시간 드론 위치 평가에 적합한 구조로 개선했다.

 

정리

Grid 방식: 실제 운영 데이터 기준 50,000,000회까지 연산으로 인해  rebuild 시간과 메모리 사용량 증가의 주요 원인이 되었다.
STRtree 방식: STRtree로 변경한 뒤에는 지오펜스별 Envelope를 한 번씩 insert하는 방식으로 변경되어 약 10,000회로 연산 수치가 줄어들며 불필요한 연산 수치를 5000배 줄일 수 있었다.