16장 - 근접성 서비스

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단계의 정밀성을 가진다.

    

  • 최적의 정밀도를 구하는 방법