System Design Interview

Posted Aug 2, 2025

By Hyeon Jae Kim

30 min read

위치 기반 서비스(Proximity Service)는 무엇이며, 어떤 기능을 제공하나요?

위치 기반 서비스는 Yelp나 Google Places와 같은 앱에서 주변의 식당이나 가장 가까운 주유소 등을 찾는 데 사용되는 백엔드 구성 요소이며, 사용자 위치와 검색 반경을 입력받아 해당 반경 내의 모든 비즈니스를 반환하고, 비즈니스 소유자가 비즈니스를 추가, 삭제, 업데이트할 수 있도록 합니다.

위치 기반 서비스의 핵심 비기능 요구사항은 무엇인가요?

낮은 지연 시간: 사용자가 주변 비즈니스를 빠르게 찾을 수 있어야 합니다.
높은 가용성: 피크 시간 동안 트래픽 급증을 처리할 수 있어야 합니다.

이 동영상에서는 주변 비즈니스 검색에 초점을 맞춰 Yelp나 Google Places와 같은 위치 기반 서비스를 설계하는 방법을 설명합니다. 핵심 주제는 사용자 위치의 지정된 반경 내에 있는 업체를 효율적으로 검색하는 시스템을 만드는 것입니다. 검색 성능을 최적화하기 위해 지오해시와 같은 지리공간 인덱싱 기술을 사용하는 것을 포함해 기능적 및 비기능적 요구사항, API 설계, 데이터 스키마에 대해 다룹니다. 이 동영상에서는 또한 읽기 복제본과 같은 데이터베이스 확장 전략과 높은 읽기 부하를 처리하기 위한 캐싱에 대한 고려 사항에 대해서도 설명합니다. 시청자는 이 동영상을 통해 수백만 명의 사용자와 비즈니스를 처리할 수 있는 확장 가능하고 반응성이 뛰어난 근접 서비스를 구축하는 데 필요한 인사이트를 얻을 수 있습니다.

1. 근접 서비스(Proximity Service) 및 비즈니스 리뷰 앱의 핵심 요구사항

근접 서비스는 주변 식당이나 가까운 주유소 등 사용자의 위치 주변 최적의 장소를 찾는 데 사용되는 백엔드 서비스이다
이 영상에서는 Yelp와 같은 비즈니스 리뷰 앱을 위한 근접 서비스 설계를 다룬다
다양한 앱마다 근접 서비스에 요구하는 기능이 다를 수 있으나, 본 영상에서는 주요 기능 요구사항에 초점을 맞춘다
핵심 기능 첫 번째는 사용자의 위치와 검색 반경을 입력받아 해당 반경 내 모든 비즈니스를 반환하는 것이다
두 번째로, 비즈니스 오너는 비즈니스를 추가, 삭제, 수정할 수 있으며, 이 변경사항은 실시간이 아닌 익일에도 반영되어도 된다
세 번째는 사용자가 비즈니스의 상세 정보를 조회할 수 있도록 하는 것이다

2. 비기능적 요구사항의 중요성

비기능적 요구사항은 시스템 설계에 다양한 제약조건을 부과하며, 설계를 더 흥미롭고 도전적이게 만든다
예를 들어, 대규모 사용자와 비즈니스 데이터를 고려할 때 요구되는 주요 비기능적 조건이 존재한다
첫째, 지연 시간이 낮아야 하며, 사용자가 빠르게 주변 상점을 검색할 수 있어야 한다
둘째, 서비스의 높은 가용성이 필요하며, 이는 업무 시간 피크 동안 트래픽 급증도 감당할 수 있어야 함을 의미한다

3. 검색 용량과 요청량 산출

일일 활성 사용자(DUA)가 1억 명이고, 사용자당 평균 검색 요청은 5개이기 때문에, 초당 검색 요청 수는 약 5,000개이다
이를 통해 서비스의 검색 처리량과 서버의 부하를 대략적으로 예측할 수 있다
사용자당 검색 쿼리 수는 5개로 가정하며, 이는 적절하다고 판단된다

데이터 저장량 예상

2억 개에 달하는 비즈니스 데이터를 저장하려면, 데이터 스키마를 더 명확히 할 필요가 있다
저장 용량 산정을 위해 데이터 구조와 저장 방식에 대한 구체적인 정보가 필요하다

요구사항에 따른 서비스 설계 방향

서비스 설계 시, 높은 요청량과 막대한 데이터 저장에 대한 효율성과 확장성을 고려해야 한다
설계 개요를 수립할 때, 요청 처리 속도와 데이터 용량 관리가 중요하다

4. API 설계 및 구조

서비스의 API는 RESTful 방식으로 설계되어 간결함을 유지한다.
검색 기능을 위한 API는 사용자 위치의 위도와 경도, 선택적 검색 반경을 입력받아 주변 업체 목록을 반환한다.
검색 결과는 업체 객체 배열과 전체 개수를 포함하며, 페이지네이션은 생략되었지만 실제 적용 시 필수적이다.
API 응답의 업체 객체는 검색 결과를 표시하는 데 필요한 최소한의 정보를 포함하며, 상세 페이지를 위해 별도의 API 엔드포인트가 필요하다.
두 번째 API 카테고리는 업체 객체의 CRUD(생성, 읽기, 수정, 삭제)를 관리하며, 이는 표준적이며 자세한 설명은 생략한다.

5. 데이터 스키마 개요 및 구성요소

서비스에는 두 개의 핵심 데이터베이스 테이블이 존재하며, 하나는 사업체(비즈니스) 정보를 저장하는 테이블이고, 다른 하나는 근처 검색을 위한 위치 정보를 저장하는 테이블이다.
사업체 테이블은 비즈니스 ID를 기본키로 하며, 상세 정보를 저장하고 CRUD 연산을 지원한다.
근처 검색용 테이블은 사업체 ID와 위치(위도, 경도)를 빠르게 검색할 수 있도록 효율적으로 인덱싱되어야 한다.
위치 인덱싱은 지리적 검색(geospatial search) 지식을 요구하며, 이후 자세히 다루어진다.
전체 데이터 크기 추정을 위해, 200 million(2억) 개 사업체를 기준으로 각각의 상세 정보는 약 1~10KB, 평균은 1KB로 예상되어 데이터 총량은 테라바이트 범위로 보인다.
위치 데이터는 사업체 수와 같거나 적으며, 각각 8바이트로 저장되어 총 약 5GB로 계산되어 매우 작은 크기를 가진다.
데이터셋이 매우 작기 때문에, 인메모리 방식 등 다양한 설계 옵션이 가능하다.
최종적으로 이 시스템은 두 개의 핵심 API 범주에 대응하는 두 부분으로 구성될 것으로 예상된다.

6. 위치 기반 검색을 위한 데이터베이스와 인덱싱 전략

이 시스템은 읽기 중심의 위치 검색 서비스로, 높은 QPS(초당 요청 수)에 적합한 설계가 필요하다.
위치 검색을 위해 지리 정보 데이터베이스와 지오스페이셜 인덱스(예: Redis GEOHASH, PostGIS 확장 사용)가 적합하다.
가장 직관적이지만 비효율적인 방법은 원을 그려 내부의 비즈니스를 찾는 것인데, 이는 테이블 스캔이 필요하여 200백만 엔트리 기준 속도가 느리다.
더 효율적으로 하려면 위도와 경도에 인덱스를 생성하되, 2차원 데이터를 1차원으로 매핑하는 지오해시(Geohash)를 사용하는 것이 좋다.

Geohash는 지구를 사분면으로 나누고, 반복적으로 더 작은 구역으로 세분화하며, 문자열로 인코딩하는 방식으로, 검색 범위에 따라 길이를 조정한다.
Geohash를 이용한 검색은 단순한 문자열 검색으로 가능하므로, 별도 지리 정보 데이터베이스 없이 관계형 데이터베이스에서도 사용할 수 있다.
근접 검색을 위해 이웃하는 8개 지오해시를 포함하여 검색 범위를 확장하는 것이 일반적이며, 라이브러리를 통해 빠르게 처리 가능하다.

Geohash의 단점은 경계에 위치한 지역의 경우 인접 구역 또는 경계선 문제가 발생할 수 있으며, 이를 위해 앱레벨에서 주변 구역도 함께 조회하는 방법이 사용된다.
Geohash의 정밀도(길이)는 검색 반경에 따라 결정되며, 4~6 길이로 사용하는 것이 적당하다.
데이터 크기와 읽기 요청 수를 고려했을 때, 모든 위치 정보는 하나의 데이터베이스에 저장하고, 필요 시 읽기 복제본으로 확장하는 것이 좋다.
비즈니스 정보(200M 개)의 크기가 수 테라바이트에 달하더라도, 최신 하드웨어에선 하나의 서버에 저장 가능하며, 샤딩은 필요하지 않다고 추정된다.
검색 요청 처리를 위해, 위치 정보, 검색 반경 및 인접 구역 정보를 활용하여 데이터를 빠르게 조회한다.
최종적으로, 검색 프로세스는 클라이언트 요청→ 로드 밸런서→ 위치 서비스→ 적절한 Geohash 길이 산출→ 인접 geohashes 계산→ 데이터베이스 조회→ 거리 계산과 정렬 순으로 진행된다.

6.1. 로드 밸런서와 서비스 분배 구조

로드 밸런서는 수신된 트래픽을 API 라우트에 따라 위치 기반 서비스와 비즈니스 서비스에 분배한다.

두 서비스는 무상태(stateless) 구조이기 때문에 로드 밸런서 뒤에서 배포하는 것이 일반적이며, 이는 쉽게 수평 확장이 가능하게 한다.

실제 환경에서는 Kubernetes의 Envoy, AWS의 API Gateway 등 다양한 방법으로 트래픽을 분배할 수 있으며, 구체적인 방식은 중요하지 않다.

위치 기반 서비스의 특성 및 역할

위치 기반 서비스는 특정 위치와 반경 내 주변 비즈니스를 빠르게 찾는 핵심 컴포넌트이다.
이 서비스는 읽기 중심(read-heavy)이며, 쓰기 요청이 거의 없다, QPS는 약 5000에 이를 것으로 추정된다.
데이터는 자주 변경되지 않으며, 따라서 수평 확장 및 캐싱이 용이하다.
장소 검색 데이터세트는 크지 않으며, 이를 고려해 최적화가 가능하다.

비즈니스 서비스와 데이터 관리

비즈니스 서비스는 CRUD 요청을 처리하는 서비스로, 읽기보다 쓰기 요청이 적으며 즉각적인 반영이 필요 없기 때문에 유연한 설계가 가능하다.
읽기 요청은 피크 시간대에 QPS가 높아질 수 있어, 캐싱 활용이 적합하다.
데이터의 크기와 읽기 요청량에 따라, 초기 설계는 primary-secondary 데이터베이스 클러스터 구성이 적합하다.

데이터베이스 구조와 고려사항

primary 데이터베이스는 쓰기 요청을 처리하며, 읽기 요청은 복제본에서 담당한다.
데이터는 먼저 primary에 저장되고, 이후 복제본으로 복제되어, 일부 데이터 불일치가 발생할 수 있다; 그러나 이는 장소 데이터 변경이 즉각적일 필요 없기 때문에 문제가 되지 않는다.
이러한 구조는 높은 읽기 요청량을 효율적으로 처리하는 데 적합하다.

6.2. 지리 데이터베이스와 지리공간 인덱스의 기본 개념

지리 기반 검색을 지원하는 데이터베이스는 지리공간 데이터베이스(geospatial databases)라고 하며, 위치 데이터를 저장하고 쿼리하는 데 최적화되어 있다.

대표적인 지리공간 데이터베이스로 Redis GEOHASH와 PostGIS 확장된 Postgres가 있다.

이러한 데이터베이스들은 공통된 지리공간 인덱스 알고리즘을 사용하며, 이를 이해하면 적합한 솔루션 선택에 도움을 줄 수 있다.

가장 직관적이지만 비효율적인 방법은 원(circle)을 그리고 내부의 비즈니스 정보를 찾는 것이다.

이 방법은 경계 박스(bounding box)를 이용하지만, 속도가 느리고 큰 테이블 스캔이 필요하여 200만 이상의 엔트리에서는 비효율적이다.

인덱스 생성만으로는 한계가 있으며, 특히 경도(longitude)와 위도(latitude) 각각에 인덱스를 만들어도 큰 성능 향상은 기대하기 어렵다.

데이터는 2차원(위도, 경도)에 분포하며, 이를 1차원으로 맵핑하여 인덱스를 하나만 만들어 성능을 개선하는 것이 가능하다.

두 가지 지리공간 인덱싱 방법과 문제점

두 가지 인덱싱 방법은 해시 기반(hash-based)과 트리 기반(tree-based)로 나뉘며, 각각 Even Grid, Geohash, Quadtree, Google S2 등이 대표적이다.
두 방법 모두 맵을 작은 영역으로 분할해 빠른 검색을 위한 인덱스를 만든다.
해시 기반 방법은 세계를 균일하게 그리드로 나누는 방식으로, 각 그리드에 속하는 비즈니스를 저장한다.
그러나 이 방식의 문제는 비즈니스 분포가 고르게 분포되지 않으며, 밀집 지역과 희소 지역 간 그리드 크기를 조절하지 못하는 점이다.
따라서 밀집 지역에는 세분화된 작은 그리드, 희소 지역에는 큰 그리드를 사용하는 것이 이상적이다.

6.3. Geohash의 구조와 작동 방식

지구를 4개의 사분면으로 나눈 후, 각 사분면은 2비트로 표시되며, 이 과정을 반복하여 하위 그리드를 생성한다.

여러 단계의 세분화를 통해, 특정 위치와 크기에 맞는 그리드 크기를 정한다; 이때, 문자열 길이(precisions 또는 levels)가 그리드 크기를 결정한다.

예를 들어, 구글 본사 위치는 1,200m×600m 크기의 그리드에 해당하며, base32 문자열로 인코딩된 길이로 그 정밀도를 알 수 있다.

위치 검색 시, 보통 4~6 길이의 geohash를 사용하며, radius에 따라 적절한 길이를 선택한다.

geohash는 문자열 형태로 되어 있어, 검색이 매우 간단하며 특히 관계형 데이터베이스에서도 효율적이다.

지오해시의 경계 문제와 해결 방안

서로 긴 접두사를 공유하는 포인트는 가까운 위치를 암시하지만,반대는 성립하지 않으며, 이는 지구의 위도/경도 경계에서 발생한다.
두 위치가 긴 접두사를 공유하더라도 다른 그리드에 속할 수 있으며, 이는 그리드 경계가 불완전하기 때문이다.
이 문제를 해결하기 위해, 현재 그리드와 8개 인접 그리드까지 포함하여 검색하는 방법이 일반적이다.
라이브러리를 이용하여 인접 geohash를 손쉽게 계산할 수 있다.

트리 기반 인덱스와 상대적 특징

대표적 트리 구조인 quadtree는 2차원 공간을 재귀적으로 4개 분할하는 방식으로 작동한다.
quadtree는 인메모리 데이터 구조로, 데이터베이스가 아니며 서버 내에서 구축된다.
트리 인덱스는 특정한 비즈니스 수에 따라 계속 세분화하는 방식이며, 운영 및 배포 측면이 geohash와 다르다.
본 설계에서는 geohash 방식을 선택하여 위치 검색에 활용한다.

6.4. ️ 지리정보 인덱스로서의 Geohash와 테이블 구조

Geohash는 위치 검색 속도를 높이기 위해 지리적 인덱스로 사용되며, 그래프 데이터베이스가 아닌 관계형 데이터베이스에서도 활용 가능하다.

테이블은 geohash와 사업 ID 두 컬럼으로 구성되며, 이 두 컬럼이 복합 키를 형성한다.

geohash 컬럼에는 각 사업의 적합한 정밀도를 갖는 geohash 값이 저장되며, 위치를 위경도로 변환하는 작업은 라이브러리로 간단히 처리할 수 있다.

여러 비즈니스가 동일 geohash를 공유하므로, 같은 geohash 내의 다양한 사업 ID는 각각 다른 행에 저장된다.

검색 시에는 SQL의 LIKE 연산자를 사용하여 prefix 길이를 조절하여 주변 검색이 가능하다.

Geohash 정밀도와 검색 범위

geohash 정밀도는 4에서 6 사이로 설정되며, 이는 각각 0.5km에서 20km의 검색 반경에 대응한다.
테이블의 geohash 컬럼은 모두 정밀도 6으로 저장되어, 더 긴 prefix를 활용한 검색이 이뤄진다.

💾 테이블 크기와 저장/확장 전략

각 행은 약 30바이트이며, 200백만 비즈니스 데이터를 저장 시 총 크기는 약 6GB로, 이는 현대 서버에서 충분히 수용 가능하다.
초기에는 하나의 데이터베이스 서버로 충분하지만, 높은 읽기 요청 (QPS 5000 이상)으로 인해 성능 저하가 발생할 수 있다.
읽기 부하 분산을 위해, 읽기 복제본을 활용하거나, 샤딩(sharding) 방식을 사용할 수 있으나, 샤딩은 애플리케이션 로직이 복잡해지기 때문에 복제본 방식이 더 적합하다.

6.5. 캐시 층 도입 여부와 그 영향

캐시 층이 필요할지 여부는 명확하지 않으며, 캐시로 인한 이점이 확실하지 않다.

읽기 중심의 워크로드에서, 지리공간 데이터셋은 크지 않기 때문에 성능 향상에 큰 도움이 되지 않을 수 있다.

읽기 성능이 병목일 경우, 읽기 복제본을 추가하는 것도 고려할 수 있다.

비즈니스 테이블 데이터 크기와 샤딩 전략

비즈니스 테이블은 약 2억 개의 비즈니스를 포함하며, 크기는 테라바이트 수준으로 추정된다.
최신 하드웨어에서는 이 크기가 크지 않으며, 샤딩이 필요할지 판단할 수 있는 경계선에 있다.
이 테이블의 갱신 빈도는 낮고, 읽기 위주이기 때문에 캐시를 사용하는 게 유리하며, 이를 통해 성장 여력을 확보할 수 있다.
읽기 부하 분산을 위해 읽기 복제본 도입도 한 방법이다.
초기에는 단일 데이터베이스로 시작하고, 성장과 모니터링 결과에 따라 샤딩, 읽기 복제, 캐시 도입 등을 결정하는 것이 권장된다.

검색 요청 처리 과정 요약

클라이언트는 위치와 반경 정보를 로드 밸런서에 전달한다.
요청은 위치기반 서비스로 전달되며, 검색 반경에 맞는 지오해시정밀도를 산출한다(여기서는 500미터 ≈ 지오해시길이 6).
주변 지오해시들을 계산한 후, 지리정보 인덱스 테이블에 9개 지오해시를 쿼리한다.
쿼리 결과로 비즈니스 ID와 위경도 쌍을 받아오고, 이를 이용해 사용자와 비즈니스 간 거리 및 순위를 계산한다.
이 과정을 통해 근접한 식당 정보를 반환한다.

References

FAANG System Design Interview: Design A Location Based Service (Yelp, Google Places)

시스템, 디자인

system-design

This post is licensed under CC BY 4.0 by the author.