[대규모 시스템 설계 기초2] 1장 근접성 서비스 (2)

지도 주변 검색 방법

 

방안 1: 2차원 검색

주어진 반경으로 그린 원 안에 놓인 사업장을 검색하는 방법이다. 가장 직관적이지만 지나치게 단순하다는 문제가 있다. 

특히나 이를 SQL문으로 옮기게 되면 테이블 전부를 읽어야하므로 비효율적이다. index를 만드는 만들어 개선해보아도 데이터가 2차원적이므로(위도, 경도) 칼ㄹ럼별로 가져온 결과도 여전히 엄청나게 많다. 때문에 index를 추가하는건 한 차원의 검색 속도만 개선할 수 있다. 

 

지리적 정보에 색인을 만드는 방법은 두종류가 있다. 첫번째는 해시 기반 방안으로 균등격자(even grid), 지오해시(geohash), 카르테시안 계층(cartesian tiers)등이 있다. 두번째로는 트리 기반 방안으로 쿼드트리(quadtree), 구글 S2, R 트리 등이 있다.

 

두 방법은 모두 구현 방법이 다르지만 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만드는 공통점이 있다. 

 

방안 2: 균등 격자(even grid)

지도를 작은 격자 또는 구획으로 나누는 단순한 방법이다. 하나의 사업장(위치 검색 대상)은 하나의 격자에 속하고 하나의 격자에는 여러개의 사업장이 담길 수 있다. 하지만 사업장 분포가 균등하지 않다는 문제가 존재한다. 예를 들어 서울에는 굉장히 많은 음식점들이 있지만, 태평양에는 전혀 없다. 또 주어진 격자의 인접 격자를 찾기 힘들 수 있다. 왜냐하면 다른 방안과 달리 격자 식별자 할당에 명확한 체계가 없기 때문이다. 

 

방안 3: 지오 해시(Geohash)

해당 방법은 2차원의 위도, 경도 데이터를 1차원의 문자열로 변환한다. 지오 해시 알고리즘은 비트를 하나씩 늘려가면서 재귀적으로 세계를 더 작은 격자로 분할한다. 처음은 01/11/00/10으로 지도를 네등분하고 각 칸을 다시 4등분을하여 원하는 정밀도(precision)를 얻을 때까지 반복을 한다. 지오 해시는 통상적으로 base32표현법을 사용한다. 이 방법은 12단계의 정밀도를 갖는다. 정밀도로 격자의 크기를 결정할 수 있다. 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 구하여 최적 정밀도를 구하여야한다. 

 

이 접근법은 격자 가장자리 처리방법에 edge case가 있다. 

해시값의 공통 접두어가 긴 격자들이 서로 더 가깝게 놓이도록 보장하는 지오해시의 특징있다. 예를 들어 "9q8zn6"/"9q8znd" 두 격자를 가까이에 있다는 것을 알 수 있다. 하지만 역은 거짓이다. 아주 가까운 두 위치가 어떤 공통 접두어를 갖지 않을 수 있다. 이는 적도의 다른쪽 또는 경도의 반대쪽에 놓이는 경우 발생한다. 때문에 단순한 접두어 기반으로 SQL문을 사용하면 주변의 사업장 정보를 모두 불러올 수 없다. 

 

또한 두 지점이 공통 접두어 길이는 길지만 서로 다른 격자에 놓일 수 있다. 이를 해결하기 위해서는 현재 격자 인접한 모든 격자의 모든 사업장 정보를 불러와야한다. 

 

방법 4: 쿼드 트리

쿼드 트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할 하는데 흔히 사용되는 자료구조이다. 즉, 질의를 답하는데 사용하는 트리구조를 메모리에 들고 있어야한다. 이 자료 구조는 서버에 존재하며 서버가 시작하는 시점에 트리가 구축된다. 

쿼드 트리로 주변 사업장을 검색하는 과정은 다음과 같다.

검색 시작점이 포함된 말단 노드를 만날 때까지 트리의 루트노드부터 탐색하고 해당 노드에 100개의 사업장이 있을 경우 해당 노드만 반환한다. 그렇지 않다면 충분한 사업장 수가 확보될 때까지 인접 노드도 추가한다. 

 

여기서 고려해야할 점이 있다. 쿼드 트리를 구축하는데는 몇 분의 시간이 소요된다. 쿼드 트리를 만드는 동안 서버 트래픽을 처리할 수 없어서 blue/green 배포를 고려해야한다. 또한 사업장에 대한 정보는 매일 자정 업데이트하여 쿼드 트리에 반영하는 방법을 사용하면 된다. 

 

방법 5: 구글 S2

지구를 hilbert curve라는 space-filling curve을 사용하여 1차원 indexing을 하는 방안이다. 힐베르트 곡선은 굉장히 유명한 특성이 있는데 힐베리트 곡선 상에서 인접한 두 지점은 indexing 후 1차원 공간 내에서도 인접한 위치에 있다.