•
근접성 서비스는 음식점, 호텔, 극장 등 장소를 기반으로 현재 위치에서 가장 가까운 시설을 찾는데 사용된다.
◦
옐프 앱의 경우, 주변에 있는 좋은 식당 검색, 구글 맵의 경우 가까운 k개의 주유소 검색 등에 사용된다.
1단계: 문제 이해 및 설계 범위 확정
•
역시, 요구사항을 명확히 이해하고 설계 범위를 확정짓는 것이 가장 먼저다.
◦
사용자가 검색 반경을 지정하는가? 검색 반경 내에 조회된 장소가 미달된다면 시스템이 검색 반경을 알아서 넓혀야 하는가?
◦
최대 허용 반경은 얼마인가?
◦
사용자가 UI에서 검색 반경을 변경할 수 있어야 하는가?
◦
사업장 정보는 어떻게 관리되며 조회 시 실시간 성을 보장해야하는가?
◦
이동 중에는 시간 흐름에 따라 조회 데이터가 달라질 텐데, 화면을 자동 갱신해야 하는가?
기능 요구사항
•
위 질문들을 토대로 다음, 세 가지 핵심 기능을 추려내볼 수 있다.
◦
사용자의 위치와 검색 반경 정보에 매칭되는 사업장 목록을 반환한다.
◦
사업장 소유주가 사업장 정보를 관리할 수 있도록 하되, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다.
◦
고객은 사업자의 상세 정보를 조회할 수 있어야 한다.
비기능 요구사항
•
비기능 요구사항은 다음 정도로 추려진다.
◦
낮은 응답 지연: 사용자는 주변 사업장을 신속히 검색할 수 있어야 한다.
◦
데이터 보호: 사용자 위치는 민감한 정보이므로 위치 기반 서비스를 설계할 때는 항상 이 데이터를 보호할 방법을 찾아야한다.
▪
GDPR, CCPA 같은 데이터 사생활 보호 법안을 준수해야 한다.
◦
고가용성 및 규모 확장성: 인구 밀집 지역에서 트래픽이 느는 경우, 감당할 수 있도록 시스템을 설계해야 한다.
개략적 규모 추정
•
DAU가 1억 명이며 등록된 사업장은 2억이라고 가정해보자.
2단계: 개략적 설계안 제시 및 동의 구하기
API 설계
•
GET /v1/search/nearby
◦
이 API는 특정 검색 기준에 맞는 사업장 목록을 반환한다.
▪
보통 조회의 경우, 페이지네이션을 제공하므로 사용하지 않더라도 한 번 언급하면 좋을 것이다.
•
사업장 관련 API
◦
GET /v1/businesses/:id
◦
POST /v1/businesses
◦
PUT /v1/businesses/:id
◦
DELETE /v1/businesses/:id
데이터 모델
•
읽기/쓰기 비율
◦
읽기 요청이 더 많을 것이다. 이 경우, MySQL과 같은 관계형 데이터베이스가 바람직할 수 있다.
•
데이터 스키마
◦
business 테이블
◦
지리적 위치 색인 테이블
▪
이 경우, 위치 정보 관련 연산의 효율성을 높이는데 사용되며 해당 기술을 사용하기 위한 지오해시에 대한 지식이 필요하다.
개략적 설계
•
로드밸런서
•
위치 기반 서비스
◦
시스템의 핵심 부분으로, 주어진 위치와 반경 정보를 이용해 주변 사업장을 검색하는 서비스다.
◦
다음과 같은 특징을 갖는다.
▪
쓰기 요청이 없으며 읽기 요청만 발생한다.
▪
QPS가 높다.
▪
무상태 서비스이므로 수평적 규모 확장이 유리하다.
•
사업장 서비스
•
데이터베이스 클러스터
◦
주-부 데이터베이스 형태로 구성하여, 주 데이터베이스에는 쓰기 요청을, 부 데이터베이스에는 읽기 요청을 전담시킨다.
◦
데이터는 주에 먼저 기록된 다음 사본으로 복사되는데, 이때 복제에 걸리는 시간 지연 때문에 주-부 간의 데이터 차이가 있을 수 있다.
•
사업장 서비스와 LBS의 규모 확장성
◦
무상태 서비스이므로 수평적 확장을 이용해 트래픽에 대응할 수 있다.
◦
시스템을 클라우드에 둔다면 여러 리전에 두어 가용성을 더 확보해볼 수 있다.
주변 사업장 검색 알고리즘
•
많은 회사가 레디스 지오해시나 PostGIS 확장을 설치한 Postgres 데이터베이스를 활용한다.
•
이런 데이터베이스들을 알고 있는 것도 좋지만 몇 가지 방안을 훑어보고 그 이면의 사고 프로세스를 검토한 다음, 각 방안에 어떤 상충 관계가 존재하는지 논의해보자.
◦
방안 1: 2차원 검색
▪
주어진 반경, 원 안의 사업장을 검색하는 방법이다. 가장 직관적이지만 지나치게 단순하다.
▪
보통 성능 향상을 위해 데이터 색인을 도입할 것이다. 그러나 이 방안의 문제는 데이터베이스 색인으론 오직 한 차원의 검색 속도만 개선할 수 있다는 것이다.
▪
지리적 정보에 색인을 거는 방법
•
해시 기반 : 균등 격자, 지오해시, 카르테시안 계층 등
•
트리 기반 : 쿼드트리, 구글 S2, R 트리 등
◦
방안 2: 균등 격자
▪
지도를 작은 격자 또는 구획으로 나누는 단순한 접근법이다.
▪
사업장 분포가 균등하지 않아 이슈가 생길 수 있다. 이상적으로는 인구밀집 지역에는 작은 격자, 그렇지 않은 지역에는 큰 격자를 사용할 수 있다면 좋을 것이다.
◦
방안 3: 지오해시
▪
지오해시는 2차원의 위도, 경도 데이터를 1차원의 문자열로 변환한다.
▪
하나의 지도를 원하는 정밀도를 얻을 때까지 재귀적으로 4분할하여 대응시키는 것이다.
▪
이 접근법은 대체로 잘 동작하지만 격자 가장자리 처리 방식에 관한 경계 조건이 몇 가지 있다.
•
지오해시는 해시값의 공통 접두어가 긴 격자들이 서로 더 가깝게 놓이도록 보장하는데, 공통 접두어를 가졌음에도 먼 경우가 생길 수 있다.
⇒ 이 문제점 때문에 단순한 접두어 기반 SQL 질의문은 주변 모든 사업장을 가져온다고 보장할 수 없다.
•
두 지점이 공통 접두어의 길이는 같지만 서로 다른 격자에 놓이는 경우다.
•
표시할 사업장을 충분히 발견할 수 없는 경우
⇒ 주어진 반경 내 사업장만 반환하거나 검색 반경을 키워야 한다. 주어진 지오해시 값의 접두어를 하나씩 제거해가며 반경을 키우면 된다.
◦
방안 4: 쿼드트리
▪
쿼드트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는데 흔히 사용되는 자료 구조다.
◦
방안 5: 구글 S2
▪
구글 S2 기하 라이브러리는 쿼드 트리와 마찬가지로 메모리 기반 솔루션이다.
▪
지구를 힐베르트 곡선이라는 공간 채움 곡선을 사용해 1차원 색인화하는 방안으로 힐베르트 곡선의 특성 중 하나인 곡선 상 인접한 두 점은 1차원 공간 내에서도 인접하다는 것을 사용한다.
▪
지오펜스 구현에 유용한데, 임의 지역에 다양한 수준의 영역 지정이 가능해서다. 또 한가지 장점은 영역 지정 알고리즘을 유연하게 제공할 수 있다.
◦
추천
색인 방법 | 회사 |
지오해시 | 빙, 레디스, 몽고DB, 리프트 |
쿼드트리 | 엑스트 |
지오해시 + 쿼드트리 | 엘라스틱서치 |
S2 | 구글 맵, 틴더 |
▪
면접 시에는 쿼드 트리나 지오해시 중 하나를 선택하길 추천한다. S2는 면접 시간 안에 설명을 끝마치기에 까다롭기 때문이다.
지오해시 vs 쿼드트리
•
지오해시
◦
구현과 사용이 쉽다. 트리를 구축할 필요가 없다.
◦
지정 반경 이내 사업장 검색을 지원한다.
◦
정밀도를 고정하면 격자 크기도 고정된다. 인구 밀도에 따라 동적으로 조정이 불가하며 가능케하려면 복잡한 논리를 적용해야 한다.
◦
색인 갱신이 쉽다.
•
쿼드트리
◦
구현하기가 살짝 더 까다롭다. 트리 구축이 필요하기 때문이다.
◦
k 번째로 가까운 사업장까지의 목록을 구할 수 있다.
◦
인구 밀도에 따라 격자 크기를 동적으로 조정할 수 있다.
◦
색인 갱신이 까다롭다. 트리 형태이므로 추가, 삭제 등 조작이 발생하는 경우, 조정이 필요하다.
3단계: 상세 설계
데이터베이스의 규모 확장성
•
사업장
◦
한 서버에 담을 수 없을 수 있으므로 샤딩을 적용하기 좋다.
◦
사업장 ID를 기준으로 샤딩하여 모든 샤드에 부하를 고르게 분산할 수 있다.
•
지리 정보 색인
◦
좀 더 단순한 지오해시를 기준으로 구성한다면 다음 두 가지 방안이 존재한다.
1.
각각의 지오해시에 연결되는 모든 사업장 ID를 JSON 배열로 만들어 같은 열에 저장한다.
2.
같은 지오해시에 속한 사업장 ID 각각을 별도 열로 저장한다.
◦
두 번째 방법을 추천하는데, 그 이유는 사업장 정보 갱신시 JSON 배열을 찾아내 갱신할 사업장 ID를 찾아야하므로 모든 데이터를 살펴봐야 한다.
◦
2의 경우, 이때 지오해시와 사업장 ID 칼럼을 합친 복합 인덱스를 사용하면 사업장 정보 관리가 쉽다.
•
지리 정보 색인의 규모 확장
◦
데이터가 그리 크지 않기에 저장 자체는 하나의 데이터베이스에서도 충분히 수행할 수 있으나 QPS가 높으므로 읽기 연산을 지원하는 사본을 도입할 수 있다.
캐시
•
캐시 계층 도입 전에는 항상 정말 필요한가?라는 질문을 날려야 한다.
•
처리 부하가 읽기 중심이고 데이터베이스 크기는 상대적으로 작아서 하나의 데이터베이스 서버가 수용하므로 가급적 모든 데이터를 메모리에 올려놓고 처리할 가능성이 있다.
•
읽기 성능이 병목이라면 사본 데이터베이스를 늘려 읽기 옵션을 추가해줄 수 있다.
•
지오해시의 경우, 지오해시 값을 캐시 키로 사용하여 캐시 계층을 도입할 수 있다.
지역 및 가용성 구역
•
사용자와 시스템 간의 물리적 거리를 줄이기 위해 도입해볼 수 있다.
시간대, 혹은 사업장 유형별 검색
•
사업장 ID부터 확보한 후, 사업장 내부 정보를 토대로 필터링을 수행하면 얻을 수 있다.
4단계: 마무리
•
지리 정보 색인 기법을 사용하는 전형적인 LBS 서비스를 설계했다. 이번 장에서는 다음 몇 가지 색인 방안을 살펴보았다.
◦
2차원 검색
◦
균등 분할 격자
◦
지오해시
◦
쿼드트리
◦
구글S2
1장 요약
•
근접성 서비스
◦
1단계
▪
기능적 요구사항
•
주변 사업장 검색
•
사업장 정보 관리
•
사업장 정보 조회
▪
비기능적 요구사항
•
낮은 응답지 연
•
데이터 보호
•
5k 검색 QPS
◦
2단계
▪
API 설계
•
검색 API
•
사업장 정보 관리 API
•
페이지 분할
▪
데이터 모델
•
읽기/쓰기 연산 비율
•
데이터 스키마
▪
개략적인 설계
▪
알고리즘
•
2차원 검색
•
균등 분할 격자
•
지오해시
•
쿼드트리
•
구글 S2
•
지오해시 vs 쿼드트리
◦
3단계
▪
데이터베이스 규모 확장
•
사업장
•
지리 정보 색인
▪
캐시
•
캐시 키
•
데이터 유형
▪
지역 및 가용성 구역
▪
결과 필터링
▪
최종 설계
◦
4단계
▪
마무리
