Google S2를 이용한 위치 검색 개선

들어가기

 

현재 개발 중인 아모르각코 [아모르겠고 모각코나 하자] 프로젝트는 위치를 기반으로 사용자들이 모각코 모임을 등록하고 참여할 수 있는 서비스입니다.

프로젝트를 구현하며 가장 큰 고민은 위치를 어떻게 저장하고 어떻게 조회할 것인지였습니다.

 

MySQL의 R-Tree 인덱스를 활용하는 방법과 PostgreSQL의 GiST인덱스를 활용하는 방법을 조사해 봤습니다.

 

이전 포스팅에서 MySQL과 PostGIS의 성능을 비교했고 더 성능이 나은 PostGIS를 선택했었습니다.

 

위치기반 서비스 데이터베이스 선택 [PostgreSQL GIS]

 

위치기반 서비스 데이터베이스 선택 [MySQL]

 

프로젝트의 핵심 요소

 

아모르각코 프로젝트의 가장 핵심 요소를 꼽자면 사용자가 지도를 움직이며 모각코를 탐색하는 것입니다.

 

다시 말해 위치 탐색은 API 요청 중 가장 빈번하게 이루어질 것으로 추측하고 있습니다.

 

따라서 해당 API의 Latency를 최대한 낮추고 DB부하 또한 줄이고 싶었습니다.

 

고민한 사항은

 

1. 공간 연산을 데이터베이스가 아닌 메모리 상에서 할 수 없을까?

2. MySQL과 같이 공간 연산, 공간 인덱스가 빈약한 DB에 공간 시스템을 구축할 순 없을까?

 

Google S2는 위 질문들에 대한 답을 줄 수 있었습니다.

 

Google S2에 대한 설명은 아래 포스팅에 적어 두었습니다.

 

Google S2

 

데이터베이스가 아닌 메모리 상에서 공간을 검색해 보자

Google S2는 위도, 경도를 Cell Token으로 변환하여 같은 셀 안에 있는 모든 위도 경도를 같은 Token값으로 취급합니다.

public class Location {
    private String cellToken;
    private double longitude;
    private double latitude;

    public Location(final double longitude, final double latitude) {
        this.latitude = latitude;
        this.longitude = longitude;
        // 모각코 모임의 위도 경도
        final S2Point point = S2LatLng.fromDegrees(latitude, longitude).toPoint();
        // 위도 경도의 Cell Token 값
        this.cellToken =
                S2CellId.fromPoint(point).parent(GoogleS2Const.S2_CELL_LEVEL.getValue()).toToken();
    }
}

 

Location 객체의 생성자로 위도와 경도를 받아 Cell Token으로 변환하여 저장하는 과정입니다.

 

위경도를 셀 토큰으로 변환하고 실제 위도 경도와 같이 데이터베이스에 저장합니다. (실제 위경도 값은 프런트엔드에서 위치 마커를 표시하기 위해 사용됩니다.)

 

셀 생성 과정 중에 parent()는 셀의 Level을 결정할 수 있게 해 주는데 저는 서비스의 특성, 성능, 정확도를 고려해 14로 결정했습니다.

 

간단히 셀 레벨의 특성을 되새겨 보자면, Cell의 레벨은 작아질수록 더 넓은 범위를 커버링 하고 커질수록 더 좁은 범위를 커버링 합니다. 그렇기 때문에 작은 레벨의 셀은 사각형 단위의 탐색에서 정확도를 높여주지만 그만큼 셀 개수가 늘어나게 됩니다.

 

직접 Cell Level을 변화시켜 가며 시각화해보겠습니다.

Cell Level 14

종로구, 중구 일대를 사용자가 탐색한다고 가정하고 Cell Level을 14로 설정했습니다.

Cell Level 14 종로구, 중구 일대

 

파란색 박스는 사용자가 모임을 조회하게 되는 지도 축적을 의미합니다.

 

위 경우 탐색 범위를 넘어서까지 셀이 커버링 됩니다. 즉 사용자의 지도 크기보다 더 큰 범위를 조회하게 됩니다.

 

Cell Level 17

Cell Level 17 종로구, 중구 일대

 

탐색 범위를 넘어서까지 커버링 되긴 하지만 그 영역이 매우 작습니다. Level 14보다 정확도가 높다는 것을 알 수 있습니다.

 

하지만 그만큼 셀 토큰의 개수가 비약적으로 증가하게 되고 데이터베이스에 질의해야 할 조건의 개수가 너무나 많아집니다.

 

Cell Level을 달리해 API 테스트 진행

테스트 데이터는 서울 지역 한식 가게 4만 6천 건을 준비했습니다.

 

테스트 데이터는 파이썬을 이용해 위경도 값을 14 Level로 토큰화시켜 MySQL에 미리 저장해 두었습니다.

from s2sphere import LatLng, CellId
def get_s2_cell_id_token(lat, lng):
    lat_lng = LatLng.from_degrees(lat, lng)
    cell_id = CellId.from_lat_lng(lat_lng).parent(14)
    return cell_id.to_token()

koreanFood['cell_id'] = koreanFood.apply(lambda row: get_s2_cell_id_token(row['latitude'], row['longitude']), axis=1)

 

Cell Level 14 종로구, 중구 일대

 

파란색 박스에 대한 영역을 S2를 이용해 생성하고 14 레벨의 셀들을 찾아냅니다.

 

찾아온 셀들을 토큰화시키고 데이터베이스에 WHERE IN 절을 이용해 질의합니다.(cell token에 대한 인덱스는 생성돼 있습니다.)

    public List<KoreanFood> search(){
        final S2LatLngRect rectangle = S2LatLngRect.fromPointPair(
                S2LatLng.fromDegrees(37.51020864434067,126.90949337172142),
                S2LatLng.fromDegrees(37.599948437288575,127.04128756997528)
        );
        final S2RegionCoverer coverer =
                S2RegionCoverer.builder()
                        .setMinLevel(14)
                        .setMaxLevel(14)
                        .build();
        final ArrayList<S2CellId> cellIds = new ArrayList<>();
        coverer.getCovering(rectangle, cellIds);
        List<String> tokens = cellIds.stream().map(S2CellId::toToken).toList();
        log.info("size:{}",tokens.size());
        return koreanFoodRepository.findByTokens(tokens);
    }

 

총 토큰 개수는 542개이고 10회 평균 152ms가 소요됐습니다.

 

 

마찬가지로 17 Level로 위경도를 미리 MySQL에 저장하고 조회 또한 17 Level로 진행해 봤습니다.

 

총 토큰 개수는 30922개이고 10회 평균 329ms가 소요됐습니다.

 

WHERE IN의 검색 조건이 비약적으로 많아지기 때문에 셀 레벨이 커질수록 Latency는 커집니다.

 

하지만 반대로 셀 레벨을 무작정 낮출 수는 없습니다. 정확도와 성능 사이의 트레이드오프를 고려해 14 레벨로 결정했습니다.

 

14 Level로 한반도 전역을 탐색 대상으로 삼게 된다면?

결론부터 논하자면 OOM이 터지게 됩니다.

 

S2 Library는 Cell 연산이 고속으로 이루어지긴 하지만 한반도 스케일의 셀 연산은 그 개수가 너무나 많아 14 Level이라도 OOM이 발생합니다.(14 Level 셀로 한반도를 덮으려는 시도자체를 해서는 안됩니다.)

 

탐색 범위에 따라 달라지는 검색 전략 도입 [전략패턴]

직접 구글맵을 이용해 어떤 방식으로 가게를 표출해주는 지 확인해봤습니다.

 

아래 두 사진 처럼 지도의 확대 정도에 따라서 보여지는 음식점이 다릅니다.

 

모든 음식점을 보여주지 않고 축적에 따라서 사용자에게 보여지는 양을 조절합니다.

 

확대된 지도

 

축소된 지도

 

지도를 많이 축소한 상태에선 굳이 음식점을 표출하지 않음으로서 DB 질의를 줄이는 것으로 판단됩니다.

 

이러한 동작을 참고해 사용자의 지도 크기에 따라서 DongLevel, GuLevel, CityLevel로 나누어 검색 전략을 달리 가져갔습니다.

 

현재 프론트 엔드에서는 카카오맵을 사용하고 있고 사용자의 지도 남서쪽, 북동쪽, 중심 좌표를 서버로 넘기도록 구현돼 있습니다.

 

서버는 남서쪽, 북동쪽 좌표로 대각선 거리를 구해 대각선 거리 기준으로

 

7.5km 이하는 동 단위 전략을

 

7.5km 초과 14.2km 이하는 구 단위 전략을

 

14.2km 초과는 도시 단위 전략으로 런타임에서 검색 전략이 결정됩니다.

 

아래는 전체적인 클래스 다이어그램 입니다.

 

S2CellSearch 클래스는 GroupSearchStrategy 타입의 빈들을 주입받습니다.

@RequiredArgsConstructor
@Component
public class S2CellSearch {

    private final List<GroupSearchStrategy> searchStrategies;

    public List<String> getCellTokens(final GroupSearchRequest request) {
        final double diagonalDistance = getDiagonalDistance(request);
        final GroupSearchStrategy groupSearchStrategy = getSearchStrategy(diagonalDistance);
        return groupSearchStrategy.selectCellTokens(request);
    }

    private GroupSearchStrategy getSearchStrategy(final double diagonalDistance) {
        return searchStrategies.stream()
                .filter(s -> s.isValid(diagonalDistance))
                .findFirst()
                .orElseThrow(IllegalAccessException::invalidDiagonalDistance);
    }

    private double getDiagonalDistance(final GroupSearchRequest request) {
        return LocationCalculator.getDistance(
                request.southWestLon(),
                request.southWestLat(),
                request.northEastLon(),
                request.northEastLat());
    }
}

 

각 전략 객체들은 isValid() 메서드를 오버라이딩해 대각선 거리 기준으로 ture/false를 반환합니다.

 

적절한 전략객체를 찾았다면 selectCellTokens()를 호출해 셀 토큰 리스트를 받아옵니다.

 

추상 클래스 GroupSearchStrategy

아래는 모든 전략 객체들이 상속 받을 추상클래스입니다.

public abstract class GroupSearchStrategy {
    public abstract boolean isValid(double diagonalSize);

    public S2LatLngRect createRectangle(final GroupSearchRequest request) {
        return S2LatLngRect.fromPointPair(
                S2LatLng.fromDegrees(request.southWestLat(), request.southWestLon()),
                S2LatLng.fromDegrees(request.northEastLat(), request.northEastLon()));
    }

    protected final List<String> getCoveringCells(final GroupSearchRequest request) {
        final S2LatLngRect rectangle = createRectangle(request);
        final S2RegionCoverer coverer =
                S2RegionCoverer.builder()
                        .setMinLevel(GoogleS2Const.S2_CELL_LEVEL.getValue())
                        .setMaxLevel(GoogleS2Const.S2_CELL_LEVEL.getValue())
                        .build();
        final ArrayList<S2CellId> cellIds = new ArrayList<>();
        coverer.getCovering(rectangle, cellIds);
        return cellIds.stream().map(S2CellId::toToken).toList();
    }

    public List<String> selectCellTokens(final GroupSearchRequest request) {
        final List<String> cellTokens = getCoveringCells(request);
        return findHalfOfCells(cellTokens);
    }

    private List<String> findHalfOfCells(final List<String> cellTokens) {
        return IntStream.range(0, cellTokens.size() - 1)
                .filter(i -> i % 2 == 0)
                .mapToObj(cellTokens::get)
                .toList();
    }
}

 

createRectangle : 지도 크기에 맞는 사각형 영역을 생성합니다.

 

 

getCoveringCells : 모든 전략이 갖어야할 공통 메서드입니다. 지도 크기에 맞는 셀들을 반환합니다.

 

selectCellTokens : 셀 토큰을 구합니다. 기본적으로 찾아온 셀들의 절반만 반환합니다.

 

DongLevelSearchStrategy : 구현체

@Component
public class DongLevelSearchStrategy extends GroupSearchStrategy {

    @Override
    public boolean isValid(final double diagonalSize) {
        return diagonalSize <= DiagonalDistanceConst.MIN_DISTANCE.getValue();
    }

    @Override
    public List<String> selectCellTokens(final GroupSearchRequest request) {
        return getCoveringCells(request);
    }
}

 

동 단위는 대각선 거리가 7.5km 이하인 요청에 선택되도록 isValid를 오버라이딩합니다.

 

7.5km이하는 탐색할 셀의 개수가 작기 때문에 selectCellTokens()를 오버라이딩해 모든 토큰을 반환하도록 합니다.

 

GuLevelSearchStrategy : 구현체

@Component
public class GuLevelSearchStrategy extends GroupSearchStrategy {

    @Override
    public boolean isValid(final double diagonalSize) {
        return DiagonalDistanceConst.MIN_DISTANCE.getValue() < diagonalSize
                && diagonalSize <= DiagonalDistanceConst.MAX_DISTANCE.getValue();
    }
}

 

구 단위는 7.5km 초과 14.2km 이하인 경우 선택되는 전략객체입니다.

 

해당 전략은 GroupSearchStrategy에 기본적으로 구현된 대로 전체 셀 중 절반의 셀을 가져와 DB에 질의합니다.

 

전체 셀 중 절반의 셀로 변환

CityLevelSearchStrategy : 구현체

@Component
public class CityLevelSearchStrategy extends GroupSearchStrategy {

    private static final double LATITUDE_SIZE = 0.07;
    private static final double LONGITUDE_SIZE = 0.14;

    @Override
    public boolean isValid(final double diagonalSize) {
        return diagonalSize > DiagonalDistanceConst.MAX_DISTANCE.getValue();
    }

    @Override
    public S2LatLngRect createRectangle(final GroupSearchRequest request) {
        return S2LatLngRect.fromCenterSize(
                S2LatLng.fromDegrees(request.centerLat(), request.centerLon()),
                S2LatLng.fromDegrees(LATITUDE_SIZE, LONGITUDE_SIZE));
    }
}

 

도시 단위는 14.2km를 초과한 경우에 다른 전략과 달리 사용자의 탐색 범위를 강제로 축소시킵니다.

 

앞서 언급했듯 한반도 전역 크기로 지도를 축소하면 찾아야할 셀이 너무 많기 때문에 DB에 질의를 하기도 전에 OOM이 나기 때문입니다.

 

S2LatLngRect.fromCenterSize()를 이용해서 중심좌표 기준으로 위도 경도 크기를 지정해 탐색할 사각형을 고정시킬 수 있습니다.

 

도시 단위 전략도 구 단위와 마찬가지로 전체 셀 중에서 절반의 셀만 DB에 질의합니다.

 

Google S2 , PostGIS 성능 테스트

기존에 적용하고 있던 PostgreSQL의 PostGIS와 MySQL + Google S2의 성능을 측정해 봤습니다.

 

테스트 데이터는 앞서 언급했던 서울지역 한식 가게 4만 6천건 위에서 진행했습니다.

반경이 넓어질 수록 성능 차이는 더 두드러집니다.

 

Google S2를 사용하면 R-Tree를 사용하지 않고 MySQL의 일반적인 B-Tree인덱스를 사용할 수 있게됩니다.

 

DB에서 공간연산을 하지 않고 메모리 상에서 특정 영역의 셀 토큰을 미리 찾아와 DB에 질의하기만 하기 때문에 성능 상승합니다.