근접성 서비스 는 음식점, 호텔 등 현재 위치에서 가까운 시설을 찾는 데 이용되며, 엘프 앱의 경우는 주변에 있는 좋은 식당 검색, 구글 맵의 경우에는 가까운 k개 주유소 검색 등의 기능 구현에 이용된다.
1단계 문제 이해 및 설계 범위 확정
기능 요구사항
- 사용자의 위치(경도와 위도 쌍)와 검색 반경 정보에 매치되는 사업장 목록을 반환
- 사업장 소유주가 사업장 정보를 추가, 삭제, 갱신할 수 있도록 하되, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다고 가정
- 고객은 사업장의 상세 정보를 살필 수 있어야 함
비기능 요구사항
방금 살펴본 사업 요구사항으로부터 다음과 같은 비기능 요구사항을 도출할 수 있다.
- 낮은 응답 지연 (latency) : 사용자는 주변 사업장을 신속히 검색할 수 있어야 한다.
- 데이터 보호 (data privacy) : 사용자의 위치는 민감한 정보이기 때문에, 위치 기반 서비스 (LBS) 를 설계할 때는 언제나 데이터 사생활 보호 법안을 준수하도록 해야 한다.
- 고가용성 및 규모 확장성 요구사항 : 인구 밀집 지역에서 이용자가 집중되는 시간에 트래픽이 급증해도 감당할 수 있도록 시스템을 설계해야 한다.
개략적 규모 추정
시스템의 규모가 어느 정도이며 어떤 수준의 도전적 과제를 해결해야 하는지 결정하기 위해, 개략적인 추정을 해보도록 하자.
DAU는 1억명, 등록된 사업장 수는 2억이라고 하자.
- 한 사용자는 하루에 5회 검색을 시도한다고 가정한다.
- QPS (Query per second) : (1억 X 5) / 10^5 = 5,000
2단계 개략적 설계안 제시 및 동의 구하기
이번 절에서는 다음 내용을 논의한다.
- API 설계
- 개략적 설계안
- 주변 사업장 검색 알고리즘
- 데이터 모델
API 설계
RESTful API 관례에 따르는 간단한 API를 만들어 보도록 하겠다.
GET /V1/search/nearby
- 특정 검색 기준에 맞는 사업장 목록을 반환하는 API
- 보통 페이지 단위로 나눠 반환
- request params : latitude(검색할 위도, decimal), longitude(검색할 경도, decimal), radius(선택적 인자, 생략할 경우 기본값은 5000M, int)
- response body
{
"total" : 10,
"businesses" : [{business object}]
}- 위의 business object, 즉 각 사업장을 표현하는 객체는 검색 결과 페이지에 표시된 모든 정보를 포함한다.
사업장 관련 API
다음 표는 사업장 객체 관련 API 목록이다.
데이터 모델
이번 절에서는 읽기/쓰기 비율 및 스키마 설계에 대해 알아본다.
읽기/쓰기 비율
읽기 연산은 굉장히 자주 수행되는데, 다음 두 기능의 이용 빈도가 높기 때문이다.
- 주변 사업장 검색
- 사업장 정보 확인
한편 쓰기 연산 실행 빈도는 낮은데, 사업장 정보를 추가하거나 삭제, 편집하는 행위는 빈번하지 않기 때문이다.
읽기 연산이 압도적인 시스템에는 MySQL 같은 관계형 데이터베이스가 바람직할 수 있다.
데이터 스키마
이 시스템의 핵심되는 테이블은 business 테이블과 지리적 위치 색인 테이블이다.
개략적 설계
이 시스템은 위치 기반 서비스와 사업장 관련 서비스 두 부분으로 구성된다.
로드밸런서
로드밸런서는 유입 트래픽을 자동으로 여러 서비스에 분산시키는 컴포넌트이다. 통상적으로 로드밸런서를 사용하는 회사는 로드밸런서에 단일 DNS 진입점(entry point)을 지정하고, URL 경로를 분석하여 어느 서비스에 트래픽을 전달할지 결정한다.
위치 기반 서비스 (LBS)
LBS는 시스템의 핵심 부분으로, 주어진 위치와 반경 정보를 이용해 주변 사업장을 검색한다.
- 쓰기 요청이 없는, 읽기 요청만 빈번하게 발생하는 서비스이다.
- QPS가 높다. 특히 특정 시간대의 인구 밀집 지역일수록 그 경향이 심하다.
- 무상태 서비스이므로 수평적 규모 확장이 쉽다.
사업장 서비스
- 사업장 소유주가 사업장 정보를 생성, 갱신, 삭제한다. 기본적으로 쓰기 요청이며, QPS는 높지 않다.
- 고객이 사업장 정보를 조회한다. 특정 시간대에 QPS가 높아진다.
데이터베이스 클러스터
데이터베이스 클러스터는 주-부 데이터베이스 형태로 구성할 수 있다. 해당 구성에서 주 데이터베이스는 쓰기 요청을 처리하며, 부 데이터베이스, 즉 사본 데이터베이스는 읽기 요청을 처리한다.
데이터는 일단 주 데이터베이스에 기록된 다음에 사본 데이터베이스로 복사된다. 복제에 걸리는 시간 지연 때문에 주 데이터베이스 데이터와 사본 데이터베이스 데이터 사이에는 차이가 있을 수 있다.
주변 사업장 검색 알고리즘
실제로 많은 회사가 레디스 지오해시나 PostGIS 확장을 설치한 포스트그레스 데이터베이스를 활용한다.
이런 데이터베이스의 이름을 나열하기보다는 지리적 위치 색인이 어떻게 동작하는지 설명함으로써 문제 풀이 능력과 기술적 지식을 갖추었음을 보이는 것이 좋다.
다음으로는 주변 사업장 검색 방법들을 살펴볼 것이다. 몇 가지 방안을 훑어보고 그 이면의 사고 프로세스를 검토한 다음, 각 방안에 어떤 타협적 측면이 존재하는지 논의할 것이다.
방안 1: 2차원 검색
주어진 반경으로 그린 원 안에 놓인 사업장을 검색하는 방법이다.
이 절차를 유사 SQL 질의문으로 옮기면 다음과 같다.
SELECT business_id, latitude, longitude,
FROM business
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + redius)
AND
(longitude BETWEEN {:my_long} - radius AND {:my_long} + radius)이 질의는 근데 데이터를 전부 읽어야 하므로 효율적이지 않다. 데이터가 2차원적이므로 칼럼별로 가져온 결과도 엄청난 결과이다.
이 방안의 문제는 데이터베이스 색인으로는 오직 한 차원의 검색 속도만 개선할 수 있다는 것이다.
2차원 데이터를 한 차원에 대응시킬 방법이 있을까 ? 있다.
그전에 우선 색인을 만드는 방법들부터 살펴보자.
크게 보자면 지리적 정보에 색인을 만드는 방법은 두 종류다. 아래 그림 중 강조 표시한 알고리즘은 업계에서 널리 사용되는 것들로, 이번 장에서 살펴볼 내용이다.
- 해시 기반 방안 : 균등격자, 지오해시, 카르테시안 계층
- 트리 기반 방안 : 퀴드트리, 구글 S2, R 트리
각 색인법의 구현 방법은 서로 다르지만 개략적 아이디어는 같다. 즉, 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만드는 것이다.
방안 2: 균등 격자
그림과 같이 작은 격자 또는 구획으로 나누는 단순한 접근법이다. 이렇게 하면 하나의 격자는 여러 사업장에 담을 수 있고, 하나의 사업장은 오직 한 격자 안에만 속하게 된다.
이 방법은 동작은 하지만 중요한 문제가 있다. 사업장의 분포가 균등하지 않다는 것이다.
방안 3: 지오해시
지오해시는 균등 격자보다 나은 방안이다. 지오해시는 2차원의 위도 경도 데이터를 1차원 문자열로 변환한다.
지오해시 알고리즘은 비트를 하나씩 늘려가면서 재귀적으로 세계를 더 작은 격자로 분할해 나간다.
위처럼 계속해서 분할해나가는 것을 원하는 정밀도가 얻어질 때까지 반복한다.
최적 정밀도를 정하는 것은 사용자가 지정한 반경으로 그린 원을 덮는, 최소 크기 격자를 만드는 지오해시 길이를 구해야 한다.
지오해시는 총 12단계 정밀도를 갖고, 지오해시 길이에 따른 격자 너비 X 높이가 있다.
아래 표는 위의 지오해시 길이와 반경 사이의 관계를 보여준다.
격자 가장자리 관련 이슈
지오해시는 해시값의 공통 접두어(prefix)가 긴 격자들이 서로 더 가깝게 놓이도록 보장한다. 그림을 보면 인접한 모든 격자가 공통 접두어 9q8zn을 갖고 있음을 확인할 수 있다.
격자 가장자리 이슈 1
하지만 그 역은 참이 아니다. 가렁 아주 가까운 두 위치가 어떤 공통 접두어도 갖지 않는 일이 발생할 수 있다. 두 지점이 적도의 다른 쪽에 놓이거나, 자오선상의 다른 반쪽에 놓이는 경우다.
예를 들어 프랑스 라 호슈 샬레라는 곳은 지오해시 u000으로 표현되는데, 이 위치는 지오해시 ezzz 값을 갖는 포메홀(Pomerol)이라는 지역에서 불과 30km 떨어져 있다. 이 두 지오해시 사이에는 어떤 공통 접두어도 없다.
이 문제점 때문에 아래와 같이 단순한 접두어 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없다.
SELECT * FROM geohash_index WHERE geohash LIKE '9q8zn%'격자 가장자리 이슈 2
또 다른 문제점은 두 지점이 공통 접두어 길이는 길지만 서로 다른 격자에 놓이는 경우이다.
가장 흔히 사용되는 해결책은 현재 격자를 비롯한 인접한 모든 격자의 모든 사 업장 정보를 가져오는 것이다. 특정 지오해시의 주변 지오해시를 찾는 것은 상수 시간(constant time)에 가능한 연산이.
표시할 사업장이 충분하지 않은 경우
이제 보너스 문제 하나를 더 살펴보자. 현재 격자와 주변 격자를 다 살펴보아도 표시할 사업장을 충분히 발견할 수 없는 경우에는 어떻게 해야 하는가?
선택지 1: 주어진 반경 내 사업장만 반환한다. 이 방안은 구현하기 쉽지만 단점 도 분명하다. 사용자의 욕구를 만족하기 충분한 수의 사업장 정보를 반환하지 못한다.
선택지 2: 검색 반경을 키운다. 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용해 주변 사업장을 검색하는 것이다. 그래도 충분한 사업장 이 없을 경우 또 한 비트를 지워서 범위를 다시 확장한다. 이를 반복하면 원하는 수 이상의 사업장을 얻을 때까지 격자 크기는 확장된다. 아래 그림은 이 과정을 개념적으로 요약한 다이어그램이다.
방안 4: 쿼드트리
또 한 가지 널리 사용되는 해결책은 쿼드트리(quadltree)다. 쿼드트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할 하는데 흔히 사용되는 자료 구조다.
예를 들자면 격자에 담긴 사업장 수가 100이하가 될 때까지 분할하는 것이다. 여기서 제시한 100이라는 숫자는 예일 뿐이며, 실제 수치는 사업적 필요에 따라 결정하면 된다. 쿼드트리를 사용한다는 것은 결국 질의에 답하는 데 사용될 트리 구조를 메모리 안에 만드는 것이다.
쿼드트리는 메모리 안에 놓이는 자료 구조일 뿐 데이터베이스가 아니라는 것에 유의하자. 이 자료 구조는 각각의 LBS 서버에 존재해야 하며, 서버가 시작하는 시점에 구축된다.
아래 그림은 세계를 쿼드트리를 사용해 분할하는 과정을 개념적으로 요약한 것이다. 전 세계에 200m(m = million, 즉 백만)개의 사업장이 있다고 가정했다.
이 트리의 루트 노드 (root node)는 세계 전체 지도를 나타낸다. 이 루트 노드를 사분면 각각을 나타내는 하위 노드로, 어떤 노드의 사업장도 100개를 넘지 않을 때까지 재귀적으로 분할한다.
그 과정을 의사 코드(pseudo code)로 나타내면 다음과 같다.
public void buildQuadtree (TreeNode node) {
if (countNumber0fBusinessesInCurrentGrid(node) > 100) {
node.subdivide();
for (TreeNode child : node.getChildren ()) {
buildQuadtree(child);
}
}
}쿼드트리 전부를 저장하는 데 얼마나 많은 메모리가 필요한가?
이 질문에 답하려면 어떤 데이터가 쿼드트리에 보관되는지 살펴봐야 한다.
트리 구축 프로세스가 한 격자에 허용되는 사업장 수의 최댓값에 좌우되기는 하지만 그 값은 트리 안에 저장하지 않아도 된다. 데이터베이스 레코드가 이미 그 최댓값을 고려하여 분할되어 있기 때문이다.
쿼드트리로 주변 사업장을 검색하려면?
- 메모리에 쿼드트리 인덱스를 구축한다.
- 검색 시작점이 포함된 말단 노드를 만날 때까지, 트리의 루트 노드부터 탐색한다. 해당 노드에 100개 사업장이 있는 경우에는 해당 노드만 반환한다.
그렇지 않은 경우에는 충분한 사업장 수가 확보될 때까지 인접 노드도 추가한다.
쿼드트리 운영 시 고려사항
앞서 설명한 대로, 200m개 사업장을 갖는 쿼드트리를 구축하는 데는 몇 분이 소요된다. 따라서 서버를 시작하는 순간에 트리를 구축하면 서버 시작 시간이 길어질 수 있다는 점을 따져 봐야 한다. 이것은 운영상 중요한 문제다. 쿼드트리를 만들고 있는 동안 서버는 트래픽을 처리할 수 없기 때문이다. 따라서 새로운 버전의 서버 소프트웨어를 릴리스 할 때는 동시에 너무 많은 서버에 배포 하지 않도록 조심해야 한다. 그렇게 해야만 서버 클러스터의 상당 부분이 동시에 꺼져서 서비스 품질이 저하되는 일을 막을 수 있다.
청/녹 배포(blue/green deployment)방안, 즉 프로덕션 환경의 절반가량을 항상 실제 서비스가 아닌 신규 이미지 테스트에만 사용하고, 테스트에 통과한 경우 네트워크 설정을 조정하여 테스트 환경과 실제 서비스 환경을 맞바꾸는 배포 전략을 택하는 경우에는 새 서버 소프트웨어를 테스트 환경의 모든 서버에 동시 배포하면 200m개 사업장 정보를 데이터베이스에서 동시에 읽게 되어 시스템에 큰 부하가 가 해질 수 있다는 점을 유의해야 한다. 사용 불가능한 배포 방안은 아니지만 설계가 복잡해질 수 있다. 면접 시에 반드시 그 사실을 언급하도록 하자.
운영에 고려할 또 한 가지는 시간이 흘러 사업장이 추가/삭제되었을 때 퀴드 트리를 갱신하는 문제다. 가장 쉬운 방법은 점진적으로 갱신하는 것이다. 다시 말해 클러스터 내에 모든 서버를 한 번에 갱신하는 대신 점진적으로 몇 개씩만 갱신하는 것이다. 하지만 그러나 보면 짧은 시간 동안이지만 낡은 데이터가 반환될 수 있다. 그러나 요구사항이 엄격하지 않다면 그 정도는 일반적으로 용인 할 수 있다. 새로 추가하거나 갱신한 사업장 정보는 다음날 반영된다는 식의 협약을 맺어 놓으면 더욱 사소한 문제가 된다. 밤 사이에 캐시를 일괄 갱신하면 된다는 뜻이다. 이 접근법의 한 가지 문제는 수많은 키(key)가 한 번에 무효화되어 캐시 서버에 막대한 부하가 가해질 수 있다는 점이다.
쿼드트리를 실시간으로 갱신하는 것도 가능하다. 하지만 그러면 설계는 복잡해진다. 여러 스레드가 퀴드트리 자료 구조를 동시 접근하는 경우에는 더욱 그렇다. 그런 상황을 처리하려면 모종의 락(lock) 메커니즘을 사용해야 하기 때문이다.
방안 5: 구글 S2
이 부분은 면접 시 언급하기 복잡하기 때문에 생략.
추천
주변 사업장을 효과적으로 검색하는 데 사용할 수 있는 솔루션 몇 가지를 지금까지 살펴보았다. 지오해시, 쿼드트리, S2 등이 있고 아래 표는 어느 회사가 어떤 기술을 택했는지 요약한 것이다.
면접 시에는 지오해시나 쿼드트리 가운데 하나를 선택하길 추천한다. S2는 면접 시간 동안에 분명하게 설명하기 까다롭다.
지오해시 VS 쿼드트리
지오해시
- 구현과 사용이 쉽다. 트리를 구축할 필요가 없다.
- 지정 반경 이내 사업장 검색을 지원한다.
- 정밀도를 고정하면 적자 크기도 고정된다. 인구 밀도에 따라 동적으로 격자 크기를 조정할 수는 없다. 그러려면 더욱 복잡한 논리를 적용해야 한다.
- 색인 갱신이 쉽다. 예를 들어 색인에서 사업장 하나를 삭제하러면, 지오해시 값과 사업장 식별자가 같은 열 하나를 제거하기만 하면 된다. 그림과 같이 하면 된다.
쿼드트리
- 구현하기가 살짝 더 까다롭다. 트리 구축이 필요해서다.
- k번째로 가까운 사업장까지의 목록을 구할 수 있다. 때로 사용자는 검색 반 경에 상관없이 내 위치에서 가까운 사업장 K개를 찾기를 원한다. 예를 들어 여행 도중에 차량 연료가 떨어져 간다면 거리에 상관없이 가까운 주유소를 찾아야 한다. 비록 가까이에 있지 않더라도, 가장 근거리의 1개의 주유소만 찾으면 된다. 그런 연산에는 쿼드트리가 적당한데 하위 노드 분할 과정이 숫자 k에 기반하는 데다 k개 사업장을 찾을 때까지 검색 범위를 자동으로 조정할 수 있기 때문이다.
인구 밀도에 따라 격자 크기를 동적으로 조정할 수 있다(그림 1.15의 덴버
지역 사례 참조). - 지오해시보다 색인 갱신은 까다롭다. 퀴드트리는 말 그대로 트리 형태 자료구조다. 사업장 정보를 삭제하려면 루트 노드부터 말단 노드까지 트리를 순회해야 한다. 예를 들어 ID= 2인 사업장을 삭제하려면 그림과 같이 루트 노드부터 말단까지 탐색해야 한다. 따라서 색인 갱신 시간 복잡도는 O(logn)이다. 한편 다중 스레드(multi-thread)를 지원해야 하는 경우에는 그 구현은 더욱 복잡해질 수 있다. 락(lock)을 사용해야 하기 때문이다.
또한 트리의 균형을 다시 맞추는 소위 리밸런싱(relalancing)이 필요하다면 구현은 더욱 복잡해진다. 가렁 말단 노드에 새로운 사업장을 추가할 수 없는 경우에는 리밸런싱을 해야 한다. 한 가지 해결책은 말단 노드가 담당해야 하는 구간의 크기를 필요한 양보다 크게 잡는 것이다.
