점심을 먹기 위해 지도 앱을 켜고 적당한 위치로 화면을 이동한 뒤 “맛집"이라는 키워드로 검색을 한다. 그러면 해당 지도 범위 안에 있는 식당들이 검색되고 지도상에 마커와 함께 어디에 어떤 식당이 있는지 한눈에 볼 수 있다. 그중 괜찮은 식당을 선택하면 해당 지점(이하 사업장)의 상세 정보를 확인할 수 있고 서비스에 따라 바로 예약을 할 수 있는 기능도 제공된다. 이러한 특정 범위(위도/경도 + 반경) 내에서 키워드 검색으로 지도상에 노출을 해주는 “근접성 서비스(proximity service)“는 여러 서비스들에서 사용자들의 편의를 위해 다양하게 활용된다. 잠깐! 그런데 이러한 서비스를 만들기 위해서는 어떤 고민들이 되어야 할까?

또 나온다고..? 알렉스 성님 숨좀 쉽시다..출처 : 도서출판 인사이트

　이번 글에서는 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2의 “1장 근접성 서비스"라는 주제로 스터디를 하고 정리해 보고자 한다. 위경도 기반의 검색이 어떻게 이루어지고 어떤 측면을 고민하고 설계를 해야 하는지에 대한 내용이다. 물론, 국내를 비롯한 해외 지도 서비스들이 이 글에서 이야기하고 있는 방식을 그대로 차용하진 않았을 테고 또한 각 서비스마다(공개하기 어려운) 약간의 차이점이 있을 수도 있겠지만 이렇게 상상을 해보는 과정에서 여러 가지를 배울 수 있을 거라 기대해 본다.

데이터 모델

　설계를 할 때는 먼저 서비스의 형태를 면밀히 파악해야 한다. 그렇지 않으면 잘못된 설계가 되거나 오버 엔지니어링 되기 쉽다. 이 서비스에서는 읽기 연산이 굉장히 자주 수행된다. 주변 사업장을 검색한다거나 사업장의 정보를 확인하는 형태가 많기 때문이다. 반대로 사업장의 정보를 등록하거나 수정/삭제하는 쓰기 연산은 상대적으로 실행 빈도가 낮다. 서비스의 특징을 미루어 봤을 때 읽기 연산이 압도적으로 많기 때문에 책에서는 MySQL 같은 관계형 데이터베이스가 바람직하다고 이야기를 하고 있지만 스터디를 진행하면서 의구심이 들었다. 일반적으로 다른 문서들을 찾아봐도 NoSQL이 읽기 처리에 강점이 있다고 나와있는데 아마도 저자는 샤딩이나 Read Replica를 활용하여 읽기의 수평 확장성을 높이는데 의미 부여하고자 빌드업 하는 건 아닐까 생각을 해봤다. 아래에 SQL vs NoSQL에 대한 아티클을 첨부해두었으니 읽어봐도 좋을 것 같다.

그리고 사업장 상세 정보와 지리적 위치가 색인되는 테이블이 필요할 것으로 보인다.

개략적인 설계

　앞단에 로드밸런서를 위치하여 검색(읽기)과 사업장(쓰기) 트래픽을 구분하여 분산 및 관리할 수 있다. 크게 두 가지 서비스로 구분해서 생각해 보자. 먼저 사업장의 정보를 관리하는 사업장 서비스는 쓰기 요청이 있긴 하지만 앞서 이야기 한 것처럼 QPS가 그렇게 높지 않다. 반면 고객이 사업장을 조회하는 특정 시간대에는 간혹 읽기 요청 QPS가 높아지지만 데이터의 변화가 많지 않기에 적당한 주기로 캐시를 설정하거나 적절하게 주-부 (primary-secondary) 데이터베이스 형태로 구성하면 트래픽 문제를 해결할 수 있다. 이처럼 Replica 형태로 구성 시엔 데이터 복제 시 지연(delay)을 고민해야 하지만 문제 되는 수준은 아니다. 위치 기반 서비스(location-based service, LBS)는 쓰기 요청은 없고 읽기 요청만 있다. QPS 가 높고 특히 특정 시간대의 인구 밀집 지역일수록 심한 특징이 있다.

　규모 확장성 측면에서 두 서비스(사업장, LBS) 모두 무상태(stateless) 서비스이므로 쉽게 확장이 가능하다. 또한 클라우드 서버의 경우 여러 지역, 여러 가용성 구역 설정으로 시스템 가용성을 높일 수 있다. Auto Scaling 관점에서 볼 때 보통은 트래픽이 늘어나면 자동으로 서버 군을 확장해서 가용성을 높이지만 반대로 새벽같이 트래픽이 적을 때는 최소한의 서버 수로 단계적 축소를 통해 비용을 절약하는 측면도 고민을 해볼 수 있을 것 같다. (개발 환경의 경우 퇴근 후나 주말 때는 최소 한대씩 혹은 아예 서버를 내린다거나…)

주변 사업장 검색 알고리즘

　구현할 서비스에서 가장 중요한 위치 기반 서비스의 주변 사업장 검색 알고리즘에 대해 고민해 보자. 먼저 간단하게 2차원 검색을 아래처럼 일반적인 query로 질의를 하기엔 데이터의 양이 많아 인덱스로 처리한다 해도 효율적이지 못하다.

SELECT business_id, latitude, longitude,
FROM business
WHERE (latitude between {:my_lat} - radius AND {:my_lat} + radius)
AND (longitude BETWEEN {:my_long} - raduis AND {:my_long} + radius)

　다음으로는 지도를 균등하게 격자로 나누어 관리를 하는 방법도 있지만 지점의 분포가 균등하지 못하여 (도심은 많고 시골은 적은) 관리에 비효율적이다. 지역에 따라 격자의 크기를 다르게 만드는 방법이 있을 수도 있지만 지점이 격자 경계선에 있을 경우 찾기가 까다로울 수 있는 단점이 있다. (인접 격자 문제) 이 책에서 이야기하는(추천하는) 가장 보편적인 방법 중에 지오해시(Geohash) 와 쿼드트리(quadtree)에 대해 알아보자.

　지오해시는 2차원의 위도/경도를 1차원의 문자열로 변환하는 형태를 의미한다. 통상적으로 base32 표현법을 사용하는데 지구 전체를 사분면으로 나누고 각 격자를 재귀적으로 나누며 반복하는 형태이다. 원하는 정밀도(precision)을 얻을 때까지 반복하고 12단계의 정밀도를 갖는데 일반적으로 4 ~ 6사이를 사용한다.

출처 : https://en.wikipedia.org/wiki/Geohash

　구글 본사가 위치한 지역의 지오해시는 10011101001001100011111111110으로 표현하고 base32로 표현하면 “9q9hvu"가 된다. 또한 메타 본사가 위치한 지역의 지오해시는 동일한 형태로 처리하면 10011101001001100111000111011 가 되고 이는 다시 “9q9jhr"로 표현할 수 있게 된다. 해시값의 공통 접두어가 긴 격자들이 서로 더 가깝게 놓이도록 보장하지만 그 역은 참이 아니다. 즉, 아주 가까운 두 위치가 공통 접두어를 갖지 않는 격자 가장자리 이슈가 여기서도 발생하는데 상수 시간에 가능한 연산이라 큰 문제가 되지 않는다. 현재 cell 인근의 격자에 대한 hash 연산으로 충분하기 때문이다. 검색하는 영역 내에 표시할 사업장이 충분하지 않는 이슈도 있다. 이 경우에도 해결 방안이 있는데 그대로 노출되는 사업장만 반환하거나 hash 값의 마지막 비트를 삭제해가면서 검색 반경을 키워 검색하는 해결 방안을 생각해 볼 수 있다. ( 카카오 지도는 w3w를 사용하는 듯 했다.)

출처 : https://developer.apple.com/documentation/gameplaykit/gkquadtree

　쿼드트리는 2차원의 공간을 재귀적으로 분할해가며 일종의 “트리"를 미리 구성하는 방식이다. 예컨대, 격자에 담긴 사업장 수가 100이하가 될 때까지 분할하는 형태이다. 단, 다른 방식과는 달리 쿼드트리는 메모리 안에 놓이는 자료구조일 뿐 데이터베이스가 아니라는 것에 유의해야 한다. 이는 각각의 LBS 서버에 존재해야 하며 서버가 시작하는 시점에 구축이 된다. 이러한 특징 때문에 고려해야 할 사항이 여러 가지가 있다. 먼저 메모리에 들고 있다는 것은 애플리케이션이 초기 로딩 될 때 계산되어 구축이 됨을 의미하기에 생성 시간 및 용량을 잘 고려해야 한다. 또한 배포 전략 측면에서 blue-green으로 한 번에 투입 시 트래픽의 유입이 갑자기 많이 되어 큰 부하를 입을 수가 있다. 또한 쿼드트리의 추가 또는 삭제 같은 갱신이 발생할 때는 지연이나 부하를 고려해야 한다.

　S2라는 구글이 만든 기하(geometry) 라이브러리 방식을 사용하는 방안도 있다. 이는 지구를 힐베르트 곡선이라는 공간 채움 곡선을 사용하여 1차원 색인화하는 방안이라고 한다. 힐베르트 곡선 상에 인접한 두 지점은 색인화 이후 1차원 공간 내에서도 인접한 위치에 있다는 특징을 가지고 있다. 즉, 2차원 공간을 1차원 공간으로 변경하면서 공간적 접근성을 유지할 수 있다는 장점이 있다. 하지만 이해하기 좀 어려운 건 사실이다. 아래 url에서 이것저것 눌러보면 조금은 이해가 될 수도 있다.

　지오해시와 쿼드트리의 장단점을 정리해 보면 다음과 같다. 기술에는 정답은 없기에 요구사항에 맞게 근거 있는 선택이 돼야 할 것이다.

  • 지오해시
    • 구현과 사용이 쉬움. 트리를 구축할 필요가 없음
    • 지정 반경 이내 사업장 검색 지원
    • 인구 밀도에 따라 동적으로 격자 크기를 조정할 수 없음
    • 색인 갱신이 쉬움
  • 쿼드트리
    • 트리 구축이 필요해서 구현이 조금 어려움
    • k 번째로 가까운 사업장까지의 목록을 구할 수 있음
    • 인구 밀도에 따라 격자 크기를 동적으로 조정할 수 있음
    • 색인 갱신이 어려움

데이터베이스의 규모 확장

　사용자가 늘어난다면 데이터베이스의 규모 또한 그에 따라 확장이 되어야 한다. 데이터가 많을 경우 단일 테이블로는 서비스하기에 한계가 있으므로 사업장 테이블의 경우 사업장 id 기준으로 샤딩을 통해 트래픽의 분산 효과를 볼 수 있다. 지리 정보 색인 테이블의 경우 geohash 와 사업장 id 목록을 json으로 관리하거나 geohash 와 사업장 id 별로 하나의 row로 관리하는 방식이 있는데 후자를 추천하는 이유는 업데이트 및 조회 측면에서 이득이기 때문이다.

　대용량 데이터 관리 측면에서 샤딩이 늘 좋은 선택지인건 아니다. 사본 데이터베이스를 구성하여 읽기 트래픽을 분산만 해도 해결될 수도 있고 오히려 샤딩 로직이 애플리케이션 계층에 구현해야 하기 때문에 까다로울 수 있는 단점도 존재한다.

상세한 설계

　캐시가 꼭 만병통치약은 아니다. 만약 RDMBS 상황에서 읽기 성능이 병목이라면 사본 데이터베이스를 증설하는 방법 또한 고려해 볼 사항이고 캐시를 둔다는 건 오히려 관리 포인트를 동반한 비용이 발생되는 점을 잊지 말아야 한다. 사업장 정보는 자주 변경되지 않기 때문에 Redis 같은 키 값 저장소에 캐시 할 수 있다. 고가용성을 보장하고 대륙 경계를 넘는 트래픽의 전송 지연을 방지하기 위해서는 레디스 클러스터를 전 세계에 각 지역별로 두고, 동일한 데이터를 각 지역에 중복해서 저장하고 서비스를 운영할 수 있다.

추가질문 : 시간대, 혹은 사업장 유형별 검색

　지오해시나 쿼드트리를 적용하면 사업장은 그렇게 많지 않을 것이다. 그렇기 때문에 사업장을 조회한 뒤 영업시간으로 필터링 하면 쉽게 해결이 가능 할수도 있다. 만약, 현재 영업 중인 100개의 사업장을 찾고 싶다는 요구사항이 있을 경우엔 100개에 도달할 때까지 계속 확장해 나가야 하기에 어려움이 있다. 이처럼 어떤 방식이든 페이징을 서버에 의존하는 것은 늘 어려움이 동반된다. 가령, 주변에 있는 예약 가능한 택시를 찾는 앱 같은 경우 점점 범위를 확장해 나가다 찾을 수 없으니 다시 시도해 달라는 서비스의 스펙으로 해결하는 경우도 있다.

마치며

　가볍게 생각해 볼 만했던 주제였지만 여러 가지 요구사항을 만족하기 위해서는 다양한 측면으로 고려를 해야 했고 특히 대용량 서비스를 대상으로 설계를 하다 보니 지오해시나 쿼드트리 같은 새로운 알고리즘을 활용해서 아주 효율적으로 위/경도 기반의 검색 시스템을 구성할 수 있었다. 특히 캐싱이나 샤딩같은 방식을 도입했을 때 무조건 장점만 있는 건 아니고 반대로 고려해야 할 사항들이 있다는 것, 더불어 배포 전략에 따라 서비스가 오히려 천국과 지옥을 오갈 수 있겠다는 점에서 평소 다루는 서비스에 배포 전략을 다시 한번 고민하는 계기가 되었던 것 같다.