1. 지원해야 하는 기능 정리
1.1. 기능적 요구사항
•
사용자의 위치와 검색 반경 정보에 매치되는 사업장 목록 반환
•
사업장 소유주가 정보룰 추가/삭제/생긴할 수 있되, 그 정보가 실시간 반영될 필요는 없음
•
고객은 사업장의 상세 정보를 살필 수 있어야함
1.2. 비기능 요구사항
•
Low latency
•
Data Privacy : 사생활 보호법 등 준수
•
High availability / Scalability : 고가용성, 확장가능성
1.3. 개략적 규모 추정
•
DAU = 1억
•
등록된 사업장 = 2억
•
1일 = 10^5
•
한 사용자 당 하루에 검색을 5회 시도
•
QPS = (1억 x 5) / 10^5 = 5,000
2. 청사진 그리기
•
API는 내 주변 사업장을 검색하는 기능과 사업장의 CURD기능을 지원하도록 설계한다.
•
로드밸런서
•
위치 기반 서비스 (LSB)
◦
사용자 위치 기반의 주변 사업장 검색
◦
읽기가 빈번하게 발생하며 QPS가 높다
◦
무상태 서비스로 구성한다.
•
사업장 서비스
◦
사업장 소유주가 정보를 생성/갱신/삭제 한다 = QPS가 낮다.
◦
고객이 사업장을 조회한다 = QPS가 높다.
•
데이터베이스 클러스터
◦
주-부 데이터 베이스의 형태로 구성한다.
2.1. 사업장 검색 알고리즘
•
2차원 검색
◦
주어진 반경에서 사업장을 검색한다.
◦
직관적 이지만 지나치게 단순하다.
◦
쿼리문을 통해서 위도와 경도를 원의 반경 내에 검색하도록 구성한다.
◦
테이블을 풀스캔 하기 때문에 효율이 별로다.
◦
해시 기반의 지리 인덱스나 트리 기반의 지리 인덱싱을 써야한다.
▪
균등격자, 지오해시, 카르테시안 계층 등
▪
쿼드트리, 구글 S2, R트리 등
◦
구현 방법이 다를 뿐 지도를 작은 영역으로 분할해 고속 검색이 가능하도록 하게 하는 것이 목표다.
•
균등 격자
◦
지도를 작은 격자로 나누어 인덱싱하는 방법
◦
하나의 사업장은 오직 한 격자에만 담을 수 있다.
◦
문제점
▪
사업장 분포가 균등하지 않아 일정한 격자로 나누면 데이터 분포가 균등하지 않은 문제가 있다.
▪
격자 인접 격자를 찾기가 까다로울 수 있다.
•
지오해시
◦
균등 격자보다 나은 방식이다.
◦
2차원의 위도 경도 데이터를 1차원 문자열로 변환한다.
◦
알고리즘 비트를 하나씩 늘려가며 재귀적으로 더 작은 격자로 분할한다.
◦
보다 높은 정밀도를 얻을때까지 격자로 분할한다.
◦
지오해시는 통상적으로 base32 표현법을 사용한다.
◦
지오해시는 12단계의 정밀성을 가진다.
◦
최적의 정밀도를 구하는 방법
•
