근접성 서비스는 음식점, 호텔, 극장, 박물관 등 현재 위치에서 가까운 시설을 찾는 데 이용된다.

1단계: 문제 이해 및 설계 범위 확정

• Q. 검색 반경을 지정할 수 있어야하는가?
  • A. 주어진 반경 내의 사업장만 대상, 이후 확장 가능
• Q. 최대 허용 반경?
  • A. 20km
• Q. 검색 반경 변경 가능?
  • A. 0.5km, 1km, 2km, 5km, 20km
• Q. 사업장 정보 CRUD는 어떻게?
  • A. 사업장 소유주가 직접 정보를 시스템에 CRUD, 새로 추가하거나 갱신된 정보는 다음날까지 반영
• Q. 사용자 현재 위치 기준으로 자동 갱신?
  • A. 상시적으로 페이지를 갱신할 필요는 없음

기능 요구사항

다음 세 가지 핵심 기능을 추려낼 수 있다.

• 사용자 위치와 검색 반경 정보에 매치되는 사업장 목록 반환
• 사업장 소유주가 사업장 정보를 추가, 삭제, 갱신할 수 있음
  • 정보가 검색 결과에 실시간으로 반영될 필요는 없음
• 고객은 사업장의 상세 정보를 살필 수 있어야함

비기능적 요구사항

기능 요구사항을 통해 다음과 같은 비기능 요구사항을 도출할 수 있다.

• 낮은 응담 지연
  • 사용자는 주변 사업장을 빠르게 검색할 수 있어야함
• 데이터 보호
  • 사용자 위치는 민감한 정보이므로 위치 기반 서비스(LBS)를 설계할 때는 사용자의 정보를 보호할 방법을 고려해야함
• 고가용성 및 규모 확장성
  • 인구 밀집 지역에서 이용자가 집중되는 시간에 트래픽이 급증해도 감당할 수 있도록 시스템을 설계해야함

개략적 규모 추정

시스템의 규모가 어느정도이며 어떤 수준의 도전적 과제를 해결해야 하는지 결정하기 위해, 개략적인 추정을 수행해본다.

DAU는 1억명, 등록된 사업장의 수는 2억개라고 가정한다.

• 1일 = 24시간 * 60분 * 60초 = 약 10^5
• 한 사용자는 하루에 5회 검색 시도한다고 가정
• QPS = (1억 * 5) / 10^5 = 5000

2단계: 개략절 설계안 제시 및 동의 구하기

API 설계

RESTful API 관례를 따르는 간단한 API를 만든다.

GET /v1/search/nearby

특정 검색 기준에 맞는 사업장 목록을 반환

• 인자
  • latitude: 위도
  • longitude: 경도
  • radius(optional): 반경, 기본값은 5000m

1
2
3
4

{
  "total": 10,
  "businesses": [{business object}]    
}

{business object}는 각 사업장을 표현하는 객체로, 검색 결과 페이지에 표시될 모든 정보를 포함한다.

사업장의 상세 정보 페이지에서는 추가 정보가 필요할 수 있으므로, 또 다른 API를 호출하여 사업장 상세 정보를 조회해야한다.

사업장 관련 API

• GET /v1/businesses/:id
  • 특정 사업장의 상세 정보 반환
• POST /v1/businesses
  • 새로운 사업장 추가
• PUT /v1/businesses/:id
  • 사업장 상세 정보 갱신
• DELETE /v1/businesses/:id
  • 특정 사업장 정보 삭제

데이터 모델

읽기/쓰기 비율

아래의 기능으로 인해 읽기 연산은 굉장히 자주 수행된다.

• 주변 사업장 검색
• 사업장 정보 확인

쓰기 연산은 사업장 정보를 추가, 삭제, 편집할 때만 발생하므로 실행 빈도가 매우 낮을 수 있다.

이렇게 읽기 연산이 압도적인 시스템에서는 MySQL 같은 관계형 데이터베이스가 바람직할 수 있다.

데이터 스키마

이 시스템의 핵심이 되는 테이블은 business 테이블과 위치 색인 테이블(geospatial index table)이다.

erDiagram
    business {
        id business_id pk
        string address
        string city
        string state
        string country
        float latitude
        float longitude
    }

지리적 위치 색인 테이블

지리적 위치 색인 테이블은 위치 정보 관련 연산의 효율성을 높이는데 쓰이는데, 지오해시(Geohash)에 대한 지식이 필요하므로 이후 논의한다.

개략적 설계

이 시스템은 위치 기반 서비스와 사업장 관련 서비스 두 부분으로 구성된다.

• 로드 밸런서
  • 유입 트래픽을 자동으로 여러 서비스에 분산시키는 컴포넌트
  • 로드밸런서에 단일 DNS 진입점을 지정하고, URL 경로를 분석하여 어느 서비스에 트래픽을 전달할 지 결정한다.
• 위치 기반 서비스(LBS)
  • 시스템의 핵심으로 주어진 위치와 반경 정보를 이용해 주변 사업장을 검색한다.
  • 쓰기 요청이 없는, 읽기 요청만 빈번하게 발생한다.
  • QPS가 높음, 특히 특정 시간대의 인구 밀집 지역일수록 그 경향이 심해진다.
  • 무상태 서비스이므로 수평적 규모 확장이 쉽다.
• 사업장 서비스
  • 쓰기
    • 사업장 소유주가 사업장 정보를 생성, 갱신, 삭제한다.
    • QPS가 높지 않다.
  • 읽기
    • 고객이 사업장 정보를 조회한다.
    • 특정 시간대에 QPS가 높아진다.

데이터베이스 클러스터

데이터베이스 클러스터는 주-부 데이터베이스 형태로 구성할 수 있다.

• 주 데이터베이스는 쓰기 요청을 처리한다.
• 부 데이터베이스, 즉 사본 데이터베이스는 읽기 요청을 처리한다.

데이터가 주 데이터베이스에 기록된 후 사본 데이터베이스로 복제되기 때문에 지연으로 인해 두 데이터베이스에 차이가 있을 수 있다.

그렇더라도 사업장 정보는 실시간으로 갱신 될 필요는 없기 때문에 문제가 되지는 않는다.

사업장 서비스와 LBS의 규모 확장성

사업장 서비스와 LBS 둘 다 무상태 서비스이므로 점심시간 같은 특정 시간대에 집중적으로 몰리는 트래픽에는 자동으로 서버를 추가하여 대응하고, 야간 등 유휴 시간대에는 서버를 삭제하도록 구성할 수 있다.

시스템을 클라우드에 둔다면 여러 지역, 여러 가용성 구역에 서버를 두어 시스템의 가용성을 높일 수 있다.

주변 사업장 검색 알고리즘

실제로는 많은 회사가 레디스 지오해시(Geohash in Redis)나 PostGIS 확장을 설치한 포스트그레스(Postgres) 데이터베이스를 활용한다.

면접관은 이런 데이터베이스의 내부 구조를 알 거라고 기대하지 않으므로 데이터베이스 이름을 나열하기 보다는 지리적 위치 색인이 어떻게 동작하는지 설명함으로써 문제 풀이 능력과 기술적 지식을 갖추었음을 보이는 것이 좋다.

2차원 검색

주어진 반경으로 그린 원 안에 놓인 사업장을 검색하는 방법이다.

가장 직관적이지만 지나치게 단순하다는 문제가 있다.

이 절차를 유사 SQL 질의문으로 옮기면 다음과 같다.

1
2
3
4
5

SELECT business_id, latitude, longitude
FROM business
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius)
  AND (longitude BETWEEN {:my_lon} - radius AND {:my_lon} + radius)
;

위와 같은 질의는 테이블 전부를 읽어야 하므로 효율적이지 않다.

위도, 경도 컬럼에 인덱스를 만든다면 데이터 집합 1과 데이터 집합 2는 빠르게 추출할 수 있지만, 주어진 반경 내 사업장을 얻으려면 이 두집합의 교집합을 구해야한다.

그럴 경우 각 집합에 속한 데이터양이 많기 때문에 효율적일 수 없다.

따라서 2차원 데이터를 한 차원에 대응시킬 방법을 적용해야하며, 지리적 정보에 색인을 만드는 방법은 두 종류이다.

flowchart
    index[인덱스]
    
    hash[해시]
    evenGrid[균등 격자]
    geohash[지오해시]
    cartesianTiers[카르테시안 계층]
    
    tree[트리]
    quadTree[쿼드트리]
    s2[구글 S2]
    rtree[R 트리]
    
    index --> hash
    index --> tree
    
    hash --> evenGrid
    hash --> geohash
    hash --> cartesianTiers
    
    tree --> quadTree
    tree --> s2
    tree --> rtree

• 해시 기반 방안
  • 균등 격자(even grid), 지오해시(geohash), 카르테시안 계층(cartesian tiers) 등
• 트리 기반 방안
  • 쿼드트리(quadtree), 구글 S2, R 트리(R-tree) 등

각 색인법의 구현 방법은 서로 다르지만 모두 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만든다.

• 지오해시, 쿼드트리, 구글 S2는 실제로 가장 널리 사용되는 방안이다.

균등 격자

지도를 작은 격자 또는 구획으로 나누는 단순한 접근법이다.

하나의 격자는 여러 사업장을 담을 수 있고, 하나의 사업장은 오직 한 격자 안에만 속하게 된다.

• 사업장 분포가 균등하지 않기 때문에, 전 세계를 동일한 크기의 격자로 나누면 데이터 분포는 전혀 균등하지 않다.
• 주어진 격자의 인접 격자를 찾기가 까다로울 수 있다.
  • 격자 식별자 할당에 명확한 체계가 없기 때문

지오해시(Geohash)

2차원의 위도 경도 데이터를 1차원의 문자열로 변환한다.

지오해시 알고리즘은 비트를 하나씩 늘려가면서 재귀적으로 세계를 더 작은 격자로 분할해 나간다.

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

이 절차를 원하는 정밀도(precision)를 얻을 때까지 반복하며, Base32 표현법으로 바꾼다.

• 구글 본사 지오해시 (길이 = 6)
  • 1001 10110 01001 10000 11011 11010 → 9q9hvu
• 메타 본사 지오해시 (길이 = 6)
  • 1001 10110 01001 10001 10000 10111 → 949jhr

지오해시는 12단계 정밀도를 낮는데, 이 정밀도가 격자의 크기를 결정한다.

지오해시의 길이가 6보가 길어지면 한 격자가 너무 작아지고, 4보다 작으면 격자가 너무 커진다.

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

이 접근법은 대체로 잘 동작하지만, 격자 가장자리 처리 방식에 관한 경계 조건(edge case)이 몇 가지 있다.

격자 가장자리 이슈 1

해시값의 곹통 접두어(prefix)가 긴 격자들이 서로 더 가깝게 놓이도록 보장하지만, 그 역은 참이 아니다.

아주 가까운 두 위치가 어떤 공통 접두어도 갖지 않는 일이 발생할 수 있다.

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

이 문제점으로 인해 단순한 접두어 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없다.

1

SELECT * FROM geohash_index WHERE geohash LIKE '9q8zn%';

격자 가장자리 이슈 2

공통 접두어 길이는 길지만 서로 다른 격자에 놓이는 경우가 존재할 수 있다.

가장 흔히 사용되는 해결책은 현재 격자를 비롯한 인접한 모든 격자의 모든 사업장 정보를 가져오는 것이다.

• 특정 지오해시의 주변 지오해시를 찾는 것은 상수 시간에 가능한 연산이다.

표시할 사업장이 충분하지 않은 경우

현재 격자와 주변 격자를 다 살펴보아도 표시할 사업장을 충분히 발견할 수 없는 경우는 2가지 방법을 고려할 수 있다.

• 주어진 반경 내 사업장만 반환
  • 사용자가 만족할만한 수의 사업장 정보를 반환하지 못한다.
• 검색 반경 키우기
  • 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용해 주변 사업장을 검색한다.
  • 만족할만한 수를 채울 때 까지 지워 범위를 다시 확장할 수 있다.

쿼드트리

쿼드트리는 격자의 내용이 특정 기준을 만족할 때가지 2차원 공간을 재귀적으로 사분면 분할하는 데 흔히 사용되는 자료구조이다.

• ex) 격자에 담긴 사업장 수가 100이하가 될 때가지 분할한다.

이 자료구조는 각각의 LBS 서버에 존재해야 하며, 서버가 시작하는 시점에 구축된다.

• 쿼드 트리는 메모리 안에 놓이는 자료 구조일 뿐, 데이터베이스가 아님에 유의하자.

트리의 루트 노드는 세계 전체 지도를 나타내며, 이 루트 노드를 사분면 각각을 나타내는 하위노드를 통해 어떤 노드의 사업장도 100개를 넘지 않을 때 까지 재귀적으로 분할한다.

쿼드트리 전부를 저장하는 데 얼마나 많은 메모리가 필요한가?

어떤 데이터가 쿼드트리에 보관되는지 살펴봐야한다.

말단 노드에 수록되는 데이터

내부 노드에 수록되는 데이터

트리 구축 프로세스가 한 격자에 허용되는 사업장 수의 초댓값에 좌우되기는 하지만 데이터베이스 레코드가 이미 최댓값을 고려하여 분할되어 있으므로 트리 안에 저장하지 않아도 된다.

총 메모리 요구량은 대략 1.71GB으로 꽤 작은 것을 알 수 있다.

쿼드 트리 인덱스는 메모리를 많이 잡아먹지 않으므로 서버 한 대에 충분히 올릴 수 있다.

전체 쿼드트리 구축에 소요되는 시간은?

각 말단 노드에는 대략 100개 사업장 ID가 저장된다.

전체 사업장 수를 n이라고 하였을 때 트리를 구축하는 시간 복잡도는 n/100 log n/100이다.

200m 개의 사업장 정보를 인덱싱하는 쿼드트리 구축에는 몇 분 정도 소요될 수 있다.

쿼드트리로 주변 사업장을 검색하려면?

1. 메모리에 쿼드트리 인덱스를 구축한다.
2. 검색 시작점이 포함된 말단 노드를 만날 때가지, 트리의 루트 노드로부터 탐색한다.
   • 해당 노드에 100개 사업장이 있는 경우에는 해당 노드만 반환
   • 그렇지 않은 경우 충분한 사업장 수가 확보될 때까지 인접 노드도 추가

쿼드트리 운영 시 고려사항

200m개 사업장을 갖는 쿼드트리를 구축하는 데 몇 분이 소요된다.

따라서 서버를 시작하는 순간에 트리를 구축하면 서버 시작 시간이 길어질 수 있다는 점을 따져봐야 한다.

• 쿼드트리를 만들고 있는 동안 서버는 트래픽을 처리할 수 없다.

새로운 버전의 서버 소프트웨어를 릴리스 할 때는 동시에 너무 많은 서버에 배포하지 않도록 조심해야 한다.

• 새 서버 소프트웨어를 테스트 환경의 모든 서버에 동시 배포하면 200m개 사업장 정보를 데이터베이스에서 동시에 읽게 되어 시스템에 큰 부하가 가해질 수 있다.

사업장이 추가/삭제 되었을 때 쿼드 트리를 갱신하는 문제도 고려해야한다.

• 점진적 갱신
  • 점진석으로 서버 중 몇 개씩만 갱신한다.
  • 짧은 시간 동안이지만 낡은 데이터가 반환될 수 있다.
  • 요구사항이 엄격하지 않다면 일반적으로 용인할 수 있다.
• 밤사이에 일괄 갱신
  • 수많은 키가 한번에 무효화되어 캐시 서버에 막대한 부하가 가해질 수 있다.
• 실시간 갱신
  • 설계가 복잡해진다.
  • 여러 스레드가 쿼드트리 자료 구조를 동시에 접근하는 경우 락 매커니즘을 사용해야한다.

실제 쓰이는 쿼드트리 사례

인구 밀집 지역에는 작은 격자를, 그렇지 않은 지역에는 큰 격자를 사용하고 있다.

구글 S2

구글 S2 기하 라이브러리는 아주 유명한 솔루션이다.

쿼드트리와 마찬가지로 메모리 기반이다.

지구를 힐베르트 곡선(Hilbert curve)라는 공간 채움 곡선을 사용하여 1차원 색인화 하는 방안이다.

힐베르트 곡선은 곡선 상에서 인접한 두 지점은 색인화 이후 1차원 공간 내에서도 인접한 위치에 존재한다는 특징이 있다.

• 지오펜스(geofence) 구현에 적합하다.
  • 
  • 지오펜스: 실제 지리적 영역에 설정한 가상의 경계
  • 임의 지역에 다양한 수준의 영역 지정이 가능하다.
  • 특정 지점 반경 몇 km, 스쿨 존, 동네 경계 등
  • 관심 있는 영역의 경계를 정한 다음 벗어난 사용자에게 알림을 보낼 수 있게된다.
  • 풍부한 기능을 제공할 수 있다.
• 영역 지정 알고리즘
  • 지오해시처럼 고정된 정밀도를 사용하는 대신 최소 수준, 최고 수준, 최대 셀 개수 등을 지정할 수 있다.
  • 셀 크기를 유연하게 조정할 수 있으므로 좀 더 상세한 결과를 반환한다.

추천

면접 시에는 지오해시나 쿼드트리 가운데 하나를 선택하는 것이 좋다.

• S2는 면접 시간 내에 분명히 설명하기 어렵다.

지오해시 vs 쿼드트리

지오해시

• 구현과 사용이 쉽다.
• 트리를 구축할 필요가 없다.
• 지정 반경 이내 사업장 검색을 지원한다.
• 정밀도를 고정하면 격자 크기도 고정된다.
  • 인구 밀도에 따라 동적으로 격자 크기를 조장할 수는 없다.
  • 반영하려면 복잡한 논리를 적용해야한다.
• 색인 갱신이 쉽다.
  • 사업장 하나를 삭제하려면, 지오해시 값과 사업장 식별자가 같은 열 하나만 제거하면 된다.

쿼드트리

• 트리 구축으로 인해 구현하기가 살짝 더 까다롭다.
• k번째로 가까운 사업장까지의 목록을 구할 수 있다.
  • 반경에 상관없이 내 위치에서 가까운 사업장 k개
  • 하위 노드 분할 과정이 숫자 k에 기반하고, 사업장을 찾을 때까지 검색 범위를 자동으로 조정할 수 있다.
• 인구 밀도에 따라 격자 크기를 동적으로 조정할 수 있다.
• 지오해시보다 색인 갱신은 까다롭다.
  • 사업자 장보를 삭제하려면 루트 노드부터 말단 노드까지 트리를 순회해야 한다.(O(log n))
  • 다중 스레드를 지원하는 경우 락을 사용해야하므로 더욱 복잡해질 수 있다.
  • 리밸런싱이 필요하다면 구현은 더욱 복잡해진다.
    • 말단 노드에 새로운 사업장을 추가할 수 없는 경우 필요함(꽉 찼을때)
    • 구간의 크기를 필요한 양보다 크게 잡으면 예방할 수 있다.

3단계: 상세 설계

데이터베이스의 규모 확장성

사업장 테이블과 지리정보 색인 테이블의 규모 확장성을 살펴본다.

사업장 테이블

사업장 테이블 데이터는 한 서버에 담을 수 없을수도 있다.

• 샤딩을 적용하기 좋은 후보이다.

가장 간단한 방법은 사업장 ID를 기준으로 샤딩하는 것으로 모든 샤드에 부하를 고르게 분산할 수 있을 뿐 아니라 운영적 측면에서도 관리하기 쉽다.

지리 정보 색인 테이블

지오해시 테이블 구성 방법은 두가지이다.

1. 각각의 지오해시에 연결되는 모든 사업장 ID를 JSON 배열로 만들어 같은 열에 저장

• 사업장 정보를 갱신하려면 JSON 배열을 읽은 다음 갱신할 사업장 ID를 찾아야한다.
• 사업장을 등록해야 하는 경우 같은 사업장 정보가 이미 있는지 확인을 위해 데이터를 전부 살펴야한다.
• 병렬적으로 실행되는 갱신 연산 결과로 데이터가 소실되는 경우를 막기 위해 락을 사용해야한다.

2. 같은 지오해시에 속한 사업장 ID 각각을 별도 열로 저장
   • 지오해시와 사업장 ID 컬럼을 합친 (geohash, business_id)를 복합키로 사용하면 사업장 정보를 추가, 삭제하기 쉽다.(락이 필요 없다)

지리 정보 색인의 규모 확장

쿼드트리 색인을 전부 보관하는데 1.71G의 메모리가 필요하므로 색인 전부를 최신 데이터베이스 서버 한 대에 충분히 수용할 수 있다.

하지만 읽기 연산의 빈도가 높다면 서버 한 대의 CPU와 네트워크 대역폭으로는 요청 전부를 감당하지 못할 수 있다.

이러한 상황에서는 여러 데이터베이스 서버로 부하를 분산해야한다.

관계형 데이터베이스 서버의 경우 부하 분산에는 두 가지 전략이 흔히 사용된다.

• 읽기 연산을 지원할 사본 데이터베이스 서버를 늘린다.
• 샤딩을 적용한다.
  • 지오해시 테이블은 샤딩 로직을 애플리케이션 계층에서 구현해야하기 때문에 까다롭다.
  • 데이터 전부를 서버 한 대에 담을 수 있으므로 여러 서버로 샤딩해야 할 강한 기술적 필요성은 없다.

따라서 이번 설계안에서는 읽기 부하를 나눌 사본 데이터베이스 서버를 두는 방법이 더 좋다.

캐시

캐시 계층 도입 전에는 정말 필요한지 고민해야한다.

• 처리 부하가 읽기 중심이고 데이터베이스 크기는 상대적으로 작아 모든 데이터는 한 대 데이터베이스 서버에 수용 가능
  • 이 경우 질의문 처리 성능은 I/O에 좌우되지 않으므로 메모리 캐시를 사용할 때와 비슷하다.
• 읽기 성능이 병목이라면 사본 데이터베이스를 증설해서 읽기 대역폭을 늘릴 수 있다.

캐시 도입을 의논할 때 벤치마킹과 비용 분석에 각별히 주의해야 한다는 사실을 유념해야한다.

캐시가 사업적 요구사항을 만족하는 데 주용한 역할을 하리라는 확신이 들면 실제 캐시 전략 논의를 진행해도 좋다.

캐시 키

가장 직관적인 캐시 키는 사용자 위치의 위도 경도 정보이지만 몇가지 문제가 있다.

• 사용자의 핸드폰에서 반환되는 위치 정보는 추정치일 뿐 정확하지 않다.
  • 전혀 움직이지 않는다고 해도 측정할 때마다 조금씩 달라진다.
• 이동하면 위도 경도 정보도 미세하게 변경된다.

따라서 사용자 위치 정보는 캐시 키로는 적절치 않으며, 지오해시나 쿼드트리는 같은 격자 내 모든 사업장이 같은 해시값을 갖도록 만들 수 있기 때문에 캐시 키로 적합하다.

캐시 데이터 유형

위 데이터는 캐시에 보고나하면 시스템의 성능을 전반적으로 향상시킬 수 있다.

격자 내 사업장 ID

사업장 정보는 상대적으로 안정적이라 자주 변경되지 않는다.

따라서 특정 지오해시에 해당하는 사업장 ID 목록을 미리 계산한 다음 레디스 같은 키-값 저장소에 캐시할 수 있다.

1. 주어진 지오해시에 대응되는 사업장 목록을 가져온다.

   • 1 2 3

     SELECT business_id FROM geohash_index WHERE geohash LIKE `{: geohash}%;`

2. 주어진 지오해시에 대응되는 사업장 목록을 요청받으면 캐시를 먼저 조회하고 없으면 위의 질의를 사용하여 캐시에 보관 후 반환한다.

새로운 사업장을 추가하거나, 기존 사업장 정보를 편집하거나, 아예 삭제하는 경우에는 데이터베이스를 갱신하고 캐시에 보관된 항목은 무효화(invalidate) 한다.

• 연산의 빈도가 상대적으로 낮아 락을 사용할 필요가 없어 구현하기 쉽다.

요구사항에서 사용자가 4가지 검색 반경 가운데 하나를 고를 수 있는데, 이 검색 반경은 각각 지오해시 길이 4, 5, 5, 6에 해당한다.

따라서 주변 사업장 검색 결과를 신속하게 제공하려면 세가지 정밀도(4, 5, 6) 전부에 대한 검색 결과를 레디스에 캐시해야한다.

• 레디스 저장소에 값을 저장하기 위한 필요 공간
  • 8qkdlxm * 200m * 3가지 정밀도 = ~5GB
• 레디스 저장소에 키를 저장하기 위핸 필요 공간
  • 무시할 만한 수준
• 전체 메모리 요구량은 대략 5GB

메모리 요구량으로 봤을 때 서버 한 대로도 충분할 것 같지만, 고가용성을 보장하고 대륙 경계를 넘는 트래픽의 전송 지연을 방지하기 위해 레디스 클러스터를 전 세계에 각 지역별로 두고, 동일한 데이터를 각 지역에 중복해서 저장해 두어야 한다.

클라이언트 애플리케이션에 표시할 사업장 정보

business_id를 키로 사용하고 이름, 주소, 사진 드으이 정보를 담는다.

지역 및 가용성 구역

지금까지 설펴본 위치 기반 서버스는 여러 지역과 가용성 구역에 설치한다.

• 사용자와 시스템 사이의 물리적 거리를 최소한으로 줄일 수 있다.
• 트래픽을 인구에 따라 고르게 분산하는 유연성을 확보할 수 있다.
  • 인구 밀도가 아주 높은 국가는 별도 지역으로 빼거나, 아예 한 지역 안에서도 여러 가용성 구역을 활용하여 부하를 분산시키는 것이 바람직할 수 있다.
• 그 지역의 사생활 보호법(privacy law)에 맞는 운영이 가능하다.

시간대, 혹은 사업장 유형별 검색

지오해시나 쿼드트리 같은 메커니즘을 통해 전 세계를 작은 격자들로 분할하면 검색 결과로 얻어지는 사업장 수는 상대적으로 적다.

일단은 근처 사업장 ID부터 전부 확보한 다음 사업장 정보를 전부 추출해서 영업시간이나 사업장 유형에 따라 필터링한다.

최종 설계도

주변 사업장 검색

1. 클라이언트앱은 사용자의 우치와 검색 반경을 로드밸런서로 전송
2. 해당 요청을 LBS로 보냄
3. LBS는 검색 요건을 만족할 지오해시 길이를 계산(예시에선 6)
4. LBS는 인접한 지오해시를 계산한 후 목록에 추가

   • 1	list_of_geohashes = [my_geohash, neigbor1_geohash ...]

5. list_of_geohashes 내에 있는 지오해시 각가에 대해 지오해시 레디스 서버를 호출하여 해당 지오해시에 대응하는 모든 사업장 ID를 추출
   • 가져오는 연산을 병렬적으로 수행하면 검색 결과를 내는 지연시간을 줄일 수 있다.
6. 반환된 사업장 ID들을 가지고 사업장 정보 레디스 서버를 조회하여 각 사업장의 상세 정보를 취득
   • 상세 정보에 의거하여 사업장과 사용자 간 거리를 계산하고, 우선순위를 매긴 다음 클라이언트앱에 반환

사업장 정보 조회, 갱신, 추가 그리고 삭제

모든 사업장 정보 관련 API는 분리되어 있다.

• 사업장 상세정보를 확인하기 위해 사업장 정보 서비스는 우선 해당 데이터가 사업장 정보 레디스 서버에 기록되어 있는지 살핀다.
  • 캐시되어 있는 경우 해당 데이터를 읽어 클라이언트로 반환한다.
  • 없는 경우 데이터베이스 클러스터에서 사업장 정보를 읽어 캐시에 저장한 다음 반환
• 새로 추가하거나 갱신한 정보는 다음날 반영된다는 정책으로 인해 캐시에 보관된 정보 갱신은 밤 사이 작업을 돌려 처리할 수 있다.

4단계: 마무리

주변 검색 기능의 핵심인 근접성 서비스를 설계해 보았다.

지리 정보 색인 기법을 활용하는 전형적인 LBS 서비스다.

• 색인 방안
  • 2차원 검색
  • 균등 분할 격자
  • 지오해시
  • 쿼드트리
  • 구글 S2
• 지오해시를 사용한 지리정보 색인 동작 원리
• 캐시를 활용한 지연 시간 감소 방법
• 캐시 대상 정보
• 바르게 주변 사업장을 검색하기 위한 캐시 활용법
• 복제와 샤딩을 통한 데이터베이스 규모 확장법
• LBS를 여러 지역과 가용성 구역에 설치
  • 가용성 상승
  • 사용자와 서버 사이 통신 지연 감소
  • 각 지역 별 사생활 보호법 준수하는 방법

요약