근접성 서비스(Proximity Service) - 지오해시, 쿼드트리, S2

본 글은 아래 책을 읽고 요약된 정보입니다.

https://product.kyobobook.co.kr/detail/S000211656186

개요

• 현재 위치에서 가장 가까운 시설을 찾는 서비스를 개발
  • 핵심기능
    • 사용자 위치 정보와 검색 반경에 매치되는 사업장 목록 반환
    • 사업장 소유주가 사업장 정보를 추가/삭제/갱신할 수 있지만 검색 결과에 실시간 반영될 필요는 없음
    • 고객은 사업장의 상세 정보를 살필 수 있어야함
  • 비기능 요구사항(non-functional requirements)
    • 낮은 응답 지연: 사용자가 주변 사업장을 신속히 검색 가능해야함
    • 데이터 보호: 사용자 위치 정보는 민감한 개인정보
    • 고가용성, 규모 확장성: 인구 밀집 지역에서 트래픽 감당해야함
  • 개략적 규모 추정
    • DAU 1억명, 사업장 수 2억

설계안

• API 설계
  • GET /v1/search/nearbytotal 개수와 business 객체를 output으로 뱉음
  • 검색결과 페이지에서 노출할 용도
  • latitude, longitude, radius를 인자로 받음
  • GET /v1/businesses/:idPUT /v1/businesses/:id특정 상세 정보 반환과 사업장 추가/갱신/삭제 API
  • DELETE /v1/businesses/:id
  • POST /v1/businesses
• 데이터 모델
  • 데이터 스키마
  • business_id가 PK인 테이블과 지리적 위치 색인 테이블이 필요함
• read 연산이 상대적으로 훨씬 많기 때문에 MySQL 관계형 DB를 추천
• 위치 기반 서비스 (Location based service)
  • 특징QPS가 높음. 특정 시간대의 인구 밀집 지역일수록 경향이 심함
  • 무상태(stateless)서비스이므로 수평적 규모 확장이 쉬움
  • 쓰기 요청은 없음, 읽기 요청 빈번
• 사업장 서비스
  • 특징사업장 소유주가 사업장 정보를 생성,갱신,삭제함. 이 때는 쓰기 요청이며 QPS가 높지 않음
  • 고객이 사업장 정보 조회하면 특정 시간대에는 QPS가 높음
• 데이터 베이스
  • primary-secondary 구조를 지님. 실시간 갱신일 필요는 없기 때문에 secondary DB로의 복제에 걸리는 delay는 해결 가능
• Auto scaling, high availability
  • LBS와 사업장 서비스 모두 stateless하기 때문에 추구 가능

주변 사업장 검색 알고리즘

• 대다수가 Geohash in Redis나 PostGIS DB를 사용함
• 이 때 SQL문도 어떻게 만들 것인지에 따라 DB색인구조를 고민해볼 수 있음
  1. 위도 컬럼과 경도 컬럼에 색인을 만들어둔다. 이 경우 각각 집합에 대한 요소는 빠르게 추출이 가능하지만 반경 내 사업장을 얻으려면 두 집합의 교집합을 구해야한다. 이 때는 각 집합에 속한 데이터 양때문에 비효율적이게 됨.
  2. 1안은 채택 불가. 대부분 널리 사용되는 알고리즘은
  • 해시 기반 방안: even grid, geohash, cartesian tiers
  • 트리 기반 방안: quadtree, 구글 s2, R-tree

Even grid

전체 지도를 평평하게 둔 후 위도, 경도로 분할. 이 때 밀집도가 다르다는 단점

Geohash

전 세계를 자오선과 적도 기준 사분면으로 나눔. 위도, 경도 값을 hashing하여 1차원 문자열로 변환. 재귀적으로 사분면을 분할해나가 precision을 확보할 때까지 분할

• 위도 [-90,0]은 0에 대응, 위도 [0,90]은 1에 대응
• 경도 [-180,0]은 0에 대응, 경도 [0,180]은 1에 대응

base32 표현법을 사용

최적 정밀도는 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 구해야함

→ 격자 가장자리 관련 이슈가 있음

1. 지오해시는 해시값의 공통 접두어(prefix)가 긴 격자들이 서로 더 가깝게 노이도록 보장함

하지만 그 역은 참이 아님. 가령 가까운 두 위치가 어떤 공통 접두어도 갖지 않는 일이 발생할 수도 있음

두 지점이 적도의 다른쪽에 놓이거나 자오선상의 다른 반쪽에 놓이는 경우

이 한계 때문에 접두어 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없음

1. 두 지점이 공통 접두어 길이는 길지만 서로 다른 격자에 놓이는 경우

이 때문에 흔히들 현재 격자를 비롯한 인접 모든 격자의 사업장 정보를 가져옴

• 만약 표시할 사업장 수가 많지 않은 경우
  1. 주어진 반경 내 사업장만 반환
  2. 검색 반경을 재귀적으로 키움
  → 이 때 quadtree를 보통 해결책으로 채택함

Quadtree

quadtree는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할

데이터베이스 구조가 아니라 메모리에 놓인 자료 구조임

• pseudo code
• public void buildQuadtree(TreeNode node) if (countNumberOfBusinessInCurrentGrid(node) > 100) { node.subdivide(); for (TreeNode child : node.getChildren()) { buildQuadtree(child); } } }

이 때 쿼드트리를 저장하는데 소비될 메모리 양을 계산하려면 어떤 데이터가 보관될지 정해야함

• 밑단 노드: 격자 식별자(좌상단&우하단 좌표), 격자 내 사업자 ID목록
• 내부 노드: 격자 식별자, 하위 노드 4개를 가르킬 포인터
• 내부 노드의 수는 말단 노드 수의 1/3

각 노드의 메모리 총량 합계와 밑단, 내부 노드 수르 곱하면 총 메모리 요구량이 나옴

이 때 밑단 노드에 저장될 사업장의 최대 개수는 앞서 ‘특정 기준’과 동일하니 계산이 가능

그럼 전체 quadtree를 저장하는데 소요되는 시간 복잡도: n/100 * log n/100

따라서 서버를 시작하는 순간에 트리를 구축하면 서버 시작 시간이 너무 길어짐. 이 시간 동안은 트래픽을 처리할 수 없기 때문에 새로운 버전의 소프트웨어를 릴리즈 할 때는 너무 많은 서버에 동시 배포하지 않도록 주의

blue/green deployment 방안 - production 환경의 절반 가량을 실제 서비스가 아닌 신규 이미지 테스트에만 사용

따라서 quadtree를 갱신할 때에도 old data를 반환하는 기준이 너무 critical하지 않다면 점진적으로 서버를 갱신할 것

구글의 S2

S2 geometry 라이브러리는 이 분야에서 아주 유명한 솔루션

quadtree와 마찬가지로 이 방법도 in-memory 기반

힐베르트 곡선이라는 space-filling curve를 사용하는데, 곡선 상에서 인접한 두 지점이 1차원 공간 내에서도 인접한 위치에 두도록 함

1차원 공간 내의 검색은 2차원 공간에서의 검색보다 훨씬 더 효율적임

Geofence

세계 지리적 영역에서 설정한 가상의 경계, 예를 들어 school zone이나 동네 경계와 같이 이미 존재하는 경계선들을 묶을 수 있음

이 때 사용자가 해당 경계를 벗어나면 알림을 보내는 등 단순 주변 사업장 검색보단 훨씬 풍부한 기능 제공이 가능하다

Geohash vs Quadtree

지오해시 쿼드트리

구현과 사용이 쉬움. 트리 구축 필요 X	구현하기가 살짝 더 까다로움. 트리 구축이 필요
지정한 반경 이내 사업장 검색 지원	k번째로 가까운 사업장까지의 목록을 구할 수 있음
예를 들어 가는 길에 가까운 주유소 찾기 등
정밀도를 고정하면 격자 크기도 고정됨	색인 갱신 과정이 까다로움.
트리 자료 구조이기 때문에 말단 노드까지 순회해야함.
이 때 multi-thread 방식이라면 lock을 구현해야하기 때문에 복잡해질 수 있음
그리고 트리 균형을 다시 맞추는 re-balancing 과정이 있어야할 수도
색인 갱신이 쉬움
예를 들어 삭제시 지오해시값과 사업장 식별자가 같은 열 하나만 제거하면 됨

데이터베이스 규모 확장성

• Business 테이블은 샤딩을 적용하기 좋은 후보
• 지리 정보 색인 테이블
  • 지오해시인 경우 각 지오해시에 연결되는 모든 사업장 ID를 JSON 배열로 만들어 동일 열에 저장
• 이 경우에는 샤딩을 적용하는 것이 좋지 않을 수 있음. 왜냐하면 application layer에서 구현해야하기 때문
  • 따라서 읽기 부하를 감당할 수 있는 사본 데이터베이스를 두는 방법이 좋을 것

캐시

• 정말 캐시가 필요할까? 라는 질문을 던질 필요가 있음
• 만약 보관하게 된다면 지오해시에 대응되는 사업장 목록을 저장한다면 좋을 듯
  • 사용자 위치 정보를 해시 키로 두는 것은 옳지 않음
• 지역 및 가용성 구역
  • 일본이나 한국과 같은 경우 인구 밀도가 높기 때문에 트래픽을 인구에 따라 유연하게 분산할 필요가 있음