근접성 서비스
💡 현재 위치에서 가까운 시설을 찾는 서비스
개략적 설계안 제시 및 동의 구하기
API 설계
- 특정 검색 기준에 맞는 사업장 반환
- GET /v1/search/nearby
- 인자: latitude, longitude, radius
- 사업장 API
- GET v1/businesses/:id 등
DB 설계
읽기가 굉장히 자주 수행 ⇒ 읽기 연산이 압도적인 시스템에서는 관계형 DB가 좋음
- business 테이블 - 사업장 테이블
- 지리적 위치 색인 테이블
계략적 설계
- 위치 기반 서비스
- 사업장 서비스
주변 사업장 검색 알고리즘
실제로는 레디스 지오해시, postGIS 를 활용
2차원 검색 - 주어진 반경으로 그린 원 안에 놓인 사업장 검색
- select * from business where latitude between {:my_lat} - radius AND {:my_lat} + radius and longitude between {:my_lat} - radius AND {:my_lat} + radius
- 위도와 경도에 인덱스를 걸어도 효율적이지 않음
- 반경 내 사업장을 얻으려면 두 집합의 교집합을 구해야한다. 이 때는 각 집합에 속한 데이터 양때문에 비효율적이게 됨
- ⇒ 해시 기반 방안: even grid, geohash, cartesian tiers
- ⇒ 트리 기반 방안: quadtree, 구글 s2, R-tree
- ⇒ 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만든다.
균등 격자 - even grid
- 전체 지도를 평평하게 둔 후 위도, 경도로 분할.
- ⇒ 데이터 분포가 균일하지 않음
지오해시 - geohash
- 위도, 경도 값을 1차원 문자열로 변환. 재귀적으로 사분면을 분할해나가 정밀도(precision)을 확보할 때까지 분할S$
- S통상적으로 base32 표현법을 사용
- 지오해시는 12단계의 정밀도(지오해시 길이)를 가지고 있고 정밀도가 격자 크기를 결정한다.(12단계가 매우 정밀도가 높음)
- 최적 정밀도는 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 구해야함
- ⇒ 격자 가장자리 관련 이슈가 있음
- 지오해시는 해시값의 공통 접두어가 긴 격자들이 서로 더 가깝게 노이도록 보장함
- 그 역은 참이 아니다. 가까운 두 위치가 어떤 공통 접두어도 갖지 않는 일이 발생
- 이 한계 때문에 접두어 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없음
- 이 때문에 흔히들 현재 격자를 비롯한 인접 모든 격자의 사업장 정보를 가져옴
- 만약 표시할 사업장 수가 많지 않은 경우
- 주어진 반경 내 사업장만 반환
- 검색 반경을 재귀적으로 키움 (네이버 지도?)
쿼드 트리 - quadtree
⇒ 격자에 담긴 사업장 수가 기준에 만족할때까지 분할
- 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할
- 데이터베이스 구조가 아니라 메모리에 놓인 자료 구조 ⇒ 서버가 시작하는 시점에 구축
- 이 때 쿼드트리를 저장하는데 소비될 메모리 양을 계산하려면 어떤 데이터가 보관될지 정해야함
- 밑단 노드: 격자 식별자(좌상단&우하단 좌표), 격자 내 사업자 ID목록
- 내부 노드: 격자 식별자, 하위 노드 4개를 가르킬 포인터
한번 더 보기
구글의 S2
- S2 geometry 라이브러리는 이 분야에서 아주 유명한 솔루션
- quadtree와 마찬가지로 이 방법도 in-memory 기반
-
- 사각형 형태의 ‘Cell’로 쪼개어 넘버링한 시스템 ⇒ 각 cell은 유니크 값이 있음
- 기본적인 원리
- 아래는 지구를 정육면체로 보고 펼친것
- faceCell(숫자 써있는 부분)을 선택해 다시 사각형으로 나누면서 재귀적으로 들어감힐베르트 곡선이라는 space-filling curve를 사용하는데, 곡선 상에서 인접한 두 지점이 1차원 공간 내에서도 인접한 위치에 두도록 함
- 1차원 공간 내의 검색은 2차원 공간에서의 검색보다 훨씬 더 효율적임
- 지오펜스
- 지오펜스(Geofence)를 사용하는 것을 지오펜싱(Geofencing)이라 하며, 지오펜스는 쉽게 말해 특정 위치로부터 반경 x미터의 가상 구역을 만드는 것
- 지오펜스를 활용하면 관심 있는 영역의 경계를 정한 다음 해당 경계를 벗어난 사용자에게 알림 보내는 등의 기능 제공
- 영역 알고리즘
- 지오해시처럼 고정된 정밀도를 사용하는 대신 최소수준, 최고수준, 최대 셀 개수 등을 지정할 수 있어 s2가 반환하는 결과가 좀 더 상세하다.