programming4 MIN READ

[시스템 디자인] 01. 근접성 서비스

[시스템 디자인] 01. 근접성 서비스

#systemdesign

시스템 디자인 시리즈의 글입니다.

현재 위치에서 가까운 시설을 찾는데 이용하는 근접성 서비스(yelp, kakao map, naver 지도, 구글맵) 을 설계해보자

1. 문제 이해 및 설계 범위 확장

기능요구사항 (=기획요구사항)

  • 사용자 위치가 입력 + 검색반경 입력 → 매치되는 사업자정보 반환
  • 사업장 정보는 추가/삭제/갱신 가능. 단, 실시간으로 반영될 필요는 없음. (하루 지연까지는 ok)
  • 고객은 사업장의 상세정보를 조회할수있음

비기능 요구사항 (=기술요구사항)

  • low latency
  • data privacy
  • high availability

개략적 규모 추정

DAU는 1억(=100million), 사업장수는 2억(=200million) 으로 가정 한 사용자가 하루 5회정도 검색한다고 가정했을때, (하루 = 10\^5초) QPS = 1억*5 / 10\^5초 = 5,000

2. 개략적 설계안 제시

API설계

  • 위치기반 사업장목록조회 API
  • 사업장 조회/추가/갱신/삭제 API

데이터 모델

  • 읽기/쓰기 비율 : 읽기연산은 많지만 쓰기연산은 적음.
  • 데이터 스키마
    • business 테이블 : 사업장의 상세정보를 저장
    • 지리적위치색인테이블 : 위치정보관련 연산의 효율성을 높이기 위한 테이블
  • 개략적 설계

image

  • Load balancer : 트래픽 분산
  • LBS : location based service. 주로 읽기연산 발생. qps높음
  • Business Service : 사업장 정보저장. 갱신될수있음. qps낮음
  • database cluster
    • primary : 쓰기요청 처리
    • secondary : 읽기요청 처리. 싱크가 지연될수있음.

주변 사업장 검색 알고리즘

  • redis geohash
  • PostGIS in Postgres 등이 많이 사용됨.

주로 어떤 알고리즘이 사용되는지 알아보자

  1. 2차원검색
    • 테이블 전부를 읽어서 입력받은 위치정보와 대조.
    • 위/경도에 색인을 넣어도 한차원의 검색속도만 개선되므로 적절한 방법이 아님.
  2. 균등격자
    • 지도를 작은 격자로 나누는 접근법
    • 한 격자는 여러 사업장정보를 담게됨.
    • 사업장 분포가 균등하지 않으면, 문제가될수있음.
    • 인접격자를 찾기가 어려움
  3. 지오해시(Geohash)
    • 2차원 위/경도 데이터를 1차원의 문자열로 변환
    • 비트를 늘려가면서 더 작은 격자로 분할해나감.
    • 최적의 정밀도(=격자크기)는 사용자가 지정한 반경을 덮는 최소크기.
    • 단, 몇가지 엣지케이스가 있음
    • 가까운 위치인데도 hash가 같은 prefix를 갖지 않을수있음 (→검색이어려움)
    • 매우 가까운위치인데도 다른 격자에 높일수있음. (→ 인접한 격자들을 가져와야함)
    • 한 격자에 충분한 사업장이 존재하지 않는경우 (→ 검색반경을 넓혀야함)
  4. 쿼드트리
    • 격자의 내용이 특정 기준을 만족할때까지 재귀적으로 사분면 분할하여 트리를 만듬
    • 이 트리구조를 메모리 안에 저장.
    • 트리는 서버가 시작하는 시점에 구축. (→ 배포시 유의해야함)
    • 모든 leaf node의 사업장이 100개를 넘지 않을 때까지 재귀적으로 분할
    • 사업장이 많은곳은 작은 격자를, 적은곳은 큰 격자를 적용할수있음.
    • 사업장 추가/삭제시 트리갱신이 까다로움.
  5. 구글S2
    • 힐베르트 곡선을 사용하여 위치정보를 1차원 indexing
    • 곡선상에 인접한 두 지점은 indexing 이후에도 인접함. → 검색이 효율적
    • 구글, 틴더 등 에서 사용됨.
    • 지오펜스(임의지역경계) 구현하기에 적합함
    • 영역지정 알고리즘(최소, 최대 수준과 셀 갯수를 지정) 활용 가능 → 셀 크기를 유연하게 조정할 수 있어 반환 결과가 더 상세해짐.

필자는 지오해시, 쿼드트리, S2를 추천.

지오해시vs쿼드트리

  • 지오해시
    • 구현과 사용이 쉬움
    • 정밀도 고정→ 격자크기 고정 → 동적 격자크기조정 불가능
    • 색인 갱신이 쉬움.
  • 쿼드트리
    • 구현하기 더 어려움
    • k번째로 가까운 사업3장의 목록도 구할수있음
    • 격자크기 동적 조정 가능
    • 색인 갱신 어려움 (갱신하려면 트리 순회해야함.. 트리 리밸런싱 필요하면? 지옥임.)

3. 상세 설계

데이터베이스 규모 확장

  • 사업장테이블 : 사업장id기준 샤딩하면 됨
  • 지리 정보 색인 테이블
    • 한 지오해시에 해당하는 id를 json배열로 저장 (→ 갱신까다로움)
    • 지오해시 + 사업장id 를 키로 해서 사업장당 1개row로 저장. (→ 갱신 쉬움)
    • 색인규모 확장하려면 사본DB 늘리는 방법을 추천. (지오해시테이블은 샤딩 까다로움)

캐시

정말 필요한지에대한 논의가 먼저 필요. 지오해시, 사업장 ID 는 캐시에 보관하면 유의미한 성능향상이 가능.

  • 지오해시 key - 해당하는 사업장ID
  • 사업장ID - 사업장 상세정보

지역 및 가용성구역

여러 지역/가용성구역에 설치하면

  • 사용자 / 시스템 사이 물리적 거리 최소화
  • 트래픽 분산
  • 지역별 privacy law에 맞는 운영 가능

최종설계도

image