[2/2 : 최단 거리 측정하기 최적화] GeoHash 기반 거리 측정 개선

디프만 위치기반 서비스를 개발하면서 한 약속에 참여한 사람은 실시간으로 위치를 공유하면서 비교 연산을 어마어마하게 하게 될겁니다. 여러분들 지도 앱 쓰면서 목적지 찍고 가면서 얼마나 자주 위치를 갱신하는지 대충 감이 오시나요..

실제로 UBER 에서 기사님 매칭 서비스를 개발할때 기사님들의 위치는 4초에 한번씩 갱신한다고 합니다.

그렇다면 엄청난 트래픽이 손으로 계산해도 어마어마할 것 같았습니다. 그래서 섹시하게 성능 개선한 기록을 여러분께 공유드리겠습니다.

GeoHash라는 것을 이용하기로 했는데요

GeoHash 가시화 툴

이 툴을 만져보다 보면 해시가 어떻게 생기는지 조금 이해하게 되더라구요

자 점점 가까이 가봅시다. 4 8 사각형이 있고, 각 사각형은 84 사각형이 있습니다.
이렇게 직사각형을 왼쪽으로 90도 오른쪽으로 90도 회전해가면서 정해진 해시 값을 재귀적으로 쌓아갑니다.
b -> 면 level 1인 1번째 사각형이구요 bb -> 면 b사각형 내에 8*4 번째 사각형의 오른쪽 맨 아래 사각형을 의미합니다.
이렇게 문자열의 길이와 위치를 해시로 정의할 수 있습니다.

근데 이 개념을 공부하고 길을 걷다가 거리를 계산할 필요 없이 사이에 있는 사각형 개수만을 가지고도 근사치를 만들어갈 수 있지 않을까? 라는 생각이 들었습니다.

그래서 사각형의 크기를 먼저 조사해봤습니다.

GeoHash Level

GeoHash Level 의 크기입니다.

우리 서비스에서는 사용자의 어느정도 오차가 허용된다고 판단하여 8Level 과 9Level 수준에서 거리를 비교하면된다고 판단했습니다.

Level 크기별 비교

간단하게 사각형 사이의 거리만 걷는다고 해봅시다.

Level 7 에서의 두 해시 값을 비교해보겠습니다.

위 분할 사각형은 GeoHash 7Level 입니다.
wydm6rh 해시값과 wydm6ru 값 차이가 몇일까요?
아래 그림에서 두 점을 별로 표시를 해봤습니다. 이성 2차 아파트 와 한강 사이의 거리를 지금부터 표현해보겠습니다.

7Level 의 세로 길이 * 4 를 하면 되겠죠? 그림을 보면 직관적으로 이해가 가죠?
Google 축적 기준 600m가량 나오네요

성능은 상당히 빠른 것으로 알 수 있습니다.

내부 구현된 로직을 작성해봤습니다.

    fun isArrived(promiseUser: CoordinateVo, coordinate: CoordinateVo): Boolean {
        val start = GeoHash.withCharacterPrecision(promiseUser.latitude, promiseUser.longitude, 10).toBase32()
        val end = GeoHash.withCharacterPrecision(coordinate.latitude, coordinate.longitude, 10).toBase32()
        val distance = calculateDistanceUsingGeoHash(start, end)
        return distance <= 20
    }

이게 client 함수인데요. 위 경도를 입력해주면 meter 단위로 제시해서 10미터 이내면 만났다고 판단합니다.

    fun calculateDistanceUsingGeoHash(geoHash1: String, geoHash2: String): Double {
        val commonPrefixLength = getCommonPrefixLength(geoHash1, geoHash2)
        val cellSize = getCellSize(commonPrefixLength)
        return cellSize * RADIUS_CONVERT_METER // Convert to meters
    }

geoHash(문자열- GeoHash) 생성한 객체를 넘겨서 공통된 문자열 길이를 구합니다. cd421f, cd421e 두 해시값이 있으면 공통 문자열이 5개겠죠? 그럼 Level 5 짜리 길이를 곱해주면 됩니다.

각 박스의 크기과 개수를 곱해줍니다.

    fun getCommonPrefixLength(geoHash1: String, geoHash2: String): Int {
        var commonPrefixLength = 0
        val length = minOf(geoHash1.length, geoHash2.length)

        while (commonPrefixLength < length && geoHash1[commonPrefixLength] == geoHash2[commonPrefixLength]) {
            commonPrefixLength++
        }

        return commonPrefixLength
    }

    fun getCellSize(commonPrefixLength: Int): Double {
        return 180.0 / (1 shl (commonPrefixLength * 2))
    }

가까운 거리인만큼 더 자세히 조사를 하구 엄청 멀리 떨어진 케이스의 경우 오차가 클 것으로 보입니다. 같은 지역 서비스 내에서는 크게 문제가 없을 것으로 보이나 추후 고도화를 해야할 필요가 있어 보이네요.

오늘의 주목할 점은 거리를 복잡한 공식을 사용하지 않고 문자열 비교로 거리를 계산해볼 수 있다는 점입니다.
다음에 포스팅에는 면적을 기반으로 가까운 거리들을 집계하는 기능을 추가해보겠습니다.