구글 맵 설계

『가상 면접 사례로 배우는 대규모 시스템 설계 기초 2』를 읽으며 정리하는 시리즈의 세 번째 글입니다.
3장은 구글 맵(Google Maps) 을 단순화한 버전을 설계합니다.
지도를 보여 주고, 사용자 위치를 받아 경로를 안내하고, 도착 예정 시간(ETA)을 알려 주는 기능이 중심입니다.

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

기능 요구사항

• 사용자 위치 갱신
• 경로 안내 서비스 (ETA 포함)
• 지도 표시

비기능 요구사항

• 정확도: 사용자에게 잘못된 경로를 안내하면 안 된다.
• 부드러운 경로 표시: 지도 화면이 끊기지 않고 부드럽게 갱신되어야 한다.
• 데이터 및 배터리 사용량: 모바일 단말에서는 중요한 고려사항이라 최소한으로 써야 한다.
• 가용성 및 규모 확장성: 일반적인 대규모 서비스 수준의 가용성과 확장성을 갖춰야 한다.

지도 101

설계에 들어가기 전에 지도를 다룰 때 알아야 할 기본 개념을 정리합니다.

📌 3차원 위치의 2차원 변환

지구는 3차원 구에 가깝지만, 화면에 보여 주는 지도는 2차원 평면입니다.
3차원 위치를 2차원 평면에 옮기는 방법을 지도 투영법(map projection)이라고 합니다.
모든 투영법은 실제 지형의 기하학적 특성(거리, 면적, 모양 등)을 어느 정도 왜곡한다는 공통점이 있으므로, 이를 고려해야 합니다.
구글 맵은 메르카토르 도법을 조금 고친 웹 메르카토르(Web Mercator) 를 씁니다.

📌 지오해싱

지오해싱(geohashing)은 2차원 평면으로 표현된 지리적 영역 위의 격자를 더 작은 격자로 재귀적으로 분할해 나가는 방법입니다.
격자를 네 칸으로 나누고, 각 칸을 다시 네 칸으로 나누는 과정을 원하는 정밀도가 될 때까지 반복합니다.

이 장에서는 지오해시를 지도를 타일(tile) 단위로 나누는 기준으로 씁니다.
지도 타일과 뒤에 나올 경로 안내 타일 모두 이 격자를 따라 나뉩니다.
지오해시의 원리는 1장에서 자세히 다뤘습니다 → 근접성 서비스 설계: 지오해시와 쿼드트리 › 방안 3: 지오해시

📌 경로 안내 알고리즘을 위한 도로 데이터 처리

경로 탐색에는 보통 다익스트라(Dijkstra) 알고리즘이나 이를 개량한 A* 알고리즘을 씁니다.
둘 다 그래프 탐색 알고리즘이라 그래프가 필요하므로, 교차로를 노드(node)로, 도로를 간선(edge)으로 표현하는 그래프 자료 구조를 가정합니다.

이런 알고리즘의 성능은 그래프 크기에 크게 좌우됩니다.
전 세계 도로망을 그래프 하나로 만들면 메모리도 많이 차지하고 탐색도 느려지므로, 그래프를 작게 나눠야 합니다.

• 지오해싱과 비슷한 방법으로 세계를 작은 격자로 나누고, 각 격자 안의 도로망을 그래프로 변환한다.
• 이 그래프를 경로 안내 타일(routing tile) 이라고 부른다.
• 각 타일은 도로로 연결된 다른 타일에 대한 참조(reference)를 유지한다.
• 경로 탐색 알고리즘은 필요한 타일만 불러와, 연결된 타일을 따라가며 큰 도로망을 탐색할 수 있다.

📌 계층적 경로 안내 타일

경로 안내 타일을 한 종류의 해상도로만 만들면, 먼 거리를 탐색할 때 아주 많은 타일을 거쳐야 합니다.
그래서 타일의 구체성(상세한 정도)을 상/중/하로 나눠, 각 단계가 담는 도로를 다르게 합니다.

구체성이 높을수록 타일 하나가 덮는 범위는 좁고 도로는 촘촘합니다.
장거리 경로라면 출발지 근처는 '상' 타일로, 중간 구간은 '하' 타일의 고속도로로 탐색해 거쳐야 할 타일 수를 줄일 수 있습니다.

개략적 규모 추정

📌 저장소 사용량

세계 지도를 21단계까지 확대할 수 있다고 하면, 가장 높은 확대 수준에서는 약 4.4조 개의 타일이 필요합니다.
확대 수준을 한 단계 올릴 때마다 타일 하나가 가로·세로 두 칸씩, 즉 네 칸으로 나뉘므로 21단계의 타일 수는 4²¹ ≈ 4.4조 개입니다.
타일 한 장이 256 × 256 픽셀의 압축 PNG 파일이라면 한 장에 약 100KB가 필요합니다.

4.4조 × 100KB = 440PB

하지만 지구 표면의 대부분은 바다, 사막, 호수, 산처럼 사람이 살지 않는 곳입니다.
이런 지역의 타일은 거의 같은 그림이라 아주 많이 압축할 수 있으므로, 실제 저장 공간은 440PB의 10~20%인 44~88PB 정도로 줄어듭니다.
책에서는 이를 어림잡아 50PB로 놓고 계산합니다.

확대 수준이 한 단계 내려가면 필요한 타일 수는 1/4로 줄어듭니다.
그래서 낮은 확대 수준의 타일까지 모두 더해도 가장 높은 확대 수준 용량의 4/3배 정도입니다.

50 + 50/4 + 50/16 + 50/64 + ... ≈ 67PB

규모 추정은 정확한 값보다 자릿수를 맞추는 게 목적이라, 67PB를 대략 100PB로 잡습니다.

📌 서버 대역폭

서버가 처리할 요청은 크게 두 종류입니다.

• 경로 안내 세션 시작 메시지 전송
• 경로 안내 중의 위치 갱신 요청

이 가운데 요청 수가 훨씬 많은 위치 갱신 요청을 기준으로 계산합니다.

DAU: 10억 명
사용자 한 명이 경로 안내를 평균 주당 35분 이용

10억 × 35분 = 주당 350억 분
→ 하루 50억 분

GPS 위치를 매초 전송한다고 하면
50억 분 × 60초 = 하루 3,000억 건

하루 ≈ 10^5초로 어림하면
QPS: 3,000억 ÷ 10^5 = 300만

매초 요청을 보내면 서버에 부하가 크기 때문에, 클라이언트가 위치를 모아 두었다가 한 번에 보내면 QPS를 낮출 수 있습니다.

15초마다 모아서 보낸다고 하면

QPS: 300만 ÷ 15 = 20만

요청 횟수가 줄어드는 만큼 단말이 통신하는 횟수도 줄어들기 때문에, 비기능 요구사항의 "데이터 및 배터리 사용량 최소화"에도 도움이 됩니다.

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

위치 서비스

클라이언트가 t초마다 자기 위치를 서버에 전송한다고 가정합니다.
앞에서 계산한 것처럼 매초 보내지 않고, 위치를 모아 두었다가 주기적으로 한 번에 보냅니다.

이렇게 쌓인 위치 데이터는 데이터 스트림으로 흘려보내 여러 곳에 활용할 수 있습니다.

• 실시간 교통 상황 파악
• 새로 열린 도로나 폐쇄된 도로 탐지
• 사용자 행태 분석

또 실시간에 가까운 위치 정보를 쓰기 때문에 ETA를 더 정확하게 계산할 수 있습니다.

지도 표시

📌 언제 타일을 가져오는가

모든 지도 타일을 클라이언트가 미리 가지고 있는 것은 앞에서 계산한 100PB를 생각하면 실용적이지 않습니다.
그래서 필요할 때 서버에서 타일을 가져오는 방법이 바람직합니다.

• 사용자가 지도를 확대하거나 이동하며 탐색할 때
• 경로 안내 중에 현재 타일을 벗어나 인접 타일로 이동할 때

📌 방법 1: 즉석에서 타일 만들기

클라이언트가 보고 있는 위치와 확대 수준에 맞춰 서버가 그때그때 지도 타일을 만들어 보내는 방법입니다.

• 사용자 위치와 확대 수준의 조합이 사실상 무한하므로, 모든 타일을 동적으로 만들어야 해서 서버 클러스터에 부하가 크다.
• 같은 타일이 다시 요청될 일이 거의 없어서 캐시를 활용하기 어렵다.

📌 방법 2: 미리 만들어 둔 타일을 CDN으로 제공

지오해싱 같은 분할법으로 확대 수준마다 타일을 미리 만들어 두고, 사용자의 위치와 확대 수준에 따라 필요한 타일 집합을 고르는 방법입니다.
각 타일은 지오해시로 만든 고유한 URL을 가지므로 CDN으로 서비스할 수 있습니다.

https://cdn.map-provider.com/tiles/9q9hvu.png

클라이언트는 CDN에서 지도 타일을 받고, CDN에 없는 타일만 CDN이 원본 서버에서 가져와 캐시합니다.

• 한 번 캐시된 타일은 원본 서버까지 요청이 가지 않는다.
• 사용자가 가까운 CDN 서버(POP)에서 타일을 받으므로 규모를 늘리기 쉽다.
• 타일이 정적이라 캐시 효율이 높다.

📌 CDN 트래픽 규모

CDN으로 보내는 데이터는 어느 정도일까요?
타일 한 장이 200m × 200m 영역(256 × 256 픽셀)을 덮고 용량이 100KB라고 가정합니다.

1km × 1km 영역 = 타일 25장 = 25 × 100KB = 2.5MB

시속 30km로 이동하면 한 시간에 약 30km² 영역의 타일이 필요하다고 보고
30 × 2.5MB = 시간당 75MB
→ 분당 1.25MB

규모 추정에서 경로 안내 이용 시간을 하루 50억 분으로 잡았으므로, 하루 동안 CDN이 보내는 데이터는 다음과 같습니다.

50억 분 × 1.25MB = 하루 6.25PB

하루 ≈ 10^5초로 나누면
6.25PB ÷ 10^5초 = 초당 62,500MB

초당 62,500MB는 큰 값이지만, CDN은 이를 전 세계의 POP(Point of Presence)가 나눠 받습니다.
전 세계에 POP가 200개 있다고 하면 POP 하나가 처리할 양은 크지 않습니다.

62,500MB ÷ 200 = POP 하나당 초당 312.5MB

📌 지도 표시 흐름

1. 모바일 사용자가 타일 서비스에 타일 URL들을 요청한다.
2. 로드밸런서가 요청을 타일 서비스 서버로 전달한다.
3. 타일 서비스가 클라이언트의 위치와 확대 수준을 기준으로 타일 URL 9개를 계산해 돌려준다.
   현재 타일 1개와 주변 타일 8개다.
4. 클라이언트는 CDN에서 타일을 내려받는다.

3단계: 상세 설계

데이터 모델

📌 경로 안내 타일

외부에서 받는 도로 데이터는 가공되지 않은 원본이라 경로 안내에 그대로 쓸 수 없습니다.
그래서 오프라인 데이터 가공 파이프라인을 주기적으로 실행해, 도로 데이터를 경로 안내 타일로 바꾸고 변경 사항을 반영합니다.

• 1단계의 계층적 경로 안내 타일처럼, 해상도(상/중/하)별로 경로 안내 타일을 3벌 만든다.
• 각 타일에는 해당 지역의 교차로와 도로가 그래프의 노드와 간선으로 들어 있다.
• 다른 타일로 이어지는 도로는 그 타일에 대한 참조로 남긴다.

이 그래프를 어디에 저장할지도 정해야 합니다.
그래프는 인접 리스트(adjacency list) 형태라 DB 테이블에 담기 어렵고, 전 세계 타일을 모두 메모리에 올려 두기도 어렵습니다.
그래서 인접 리스트를 이진 파일로 직렬화(serialize)해 S3 같은 객체 저장소에 보관하고, 경로 안내 서비스가 자주 쓰는 타일을 적극적으로 캐싱하는 방법이 좋습니다.
직렬화는 이를 지원하는 소프트웨어 패키지를 이용합니다.
타일을 지오해시 기준으로 정리해 두면, 위도·경도만으로 필요한 타일을 빠르게 찾을 수 있습니다.

📌 사용자 위치 데이터

사용자 위치 데이터는 도로 데이터와 경로 안내 타일을 갱신하는 데 쓰이고, 실시간 교통 상황이나 교통 이력 DB를 만드는 데도 쓰이는 값진 데이터입니다.
위치 데이터를 처리해 지도 데이터를 갱신하는 데이터 스트림 처리 서비스도 필요합니다.

규모 추정에서 본 것처럼 위치 갱신 요청은 일괄 전송을 해도 초당 20만 건에 이릅니다.
그래서 대량의 쓰기 연산을 잘 처리하고, 수평적으로 규모를 늘리기 쉬운 DB가 필요합니다.

📌 지오코딩 데이터베이스

지오코딩(geocoding) DB는 주소를 위도·경도 쌍으로 바꾸는 정보를 저장합니다.
사용자가 출발지와 목적지를 주소로 입력하면, 이 DB로 위도·경도를 구해 경로 탐색에 넘깁니다.

주소 정보는 자주 바뀌지 않지만 조회는 아주 많습니다.
읽기 연산이 많고 쓰기 연산은 적으므로, 레디스처럼 읽기가 빠른 키-값 저장소가 적당합니다.

위치 서비스

📌 사용자 위치 데이터베이스

피크 타임에 초당 백만 건의 위치 정보 업데이트가 발생한다고 보면, 쓰기 연산에 강한 NoSQL 키-값 DB나 열 중심(column-oriented) DB가 요구사항에 잘 맞습니다.
책에서는 그 예로 카산드라(Cassandra)를 씁니다.

사용자의 위치는 계속 바뀌기 때문에, 새 위치가 들어오면 이전 위치는 금방 쓸모가 없어집니다.
그래서 데이터 일관성보다 가용성을 우선합니다.
CAP 정리로 보면 네트워크 분할이 생겼을 때 일관성(C)보다 가용성(A)을 고르는 AP 시스템에 해당합니다.

이렇게 두면 특정 사용자의 위치 이력을 시간 순서대로 빠르게 읽을 수 있습니다.

📌 사용자 위치 데이터는 어떻게 이용되는가

위치 데이터는 DB에 저장하는 것만이 아니라, 여러 서비스가 함께 써야 하는 데이터입니다.
그래서 카프카(Kafka)처럼 응답 지연이 낮고 많은 데이터를 동시에 처리할 수 있는 데이터 스트리밍 플랫폼으로 실시간 데이터 피드를 제공합니다.
위치 서비스가 위치 데이터를 카프카에 보내면, 이 데이터가 필요한 서비스들이 각자 구독해 씁니다.

• 실시간 교통 상황 파악
• 실시간 교통량 데이터베이스 갱신
• 새로 열린 도로나 폐쇄된 도로 탐지

지도 표시

📌 지도 타일 사전 계산

지도 타일은 확대 수준마다 미리 만들어 둡니다.
한 단계 확대할 때마다 동서 방향으로 두 배, 남북 방향으로 두 배 늘어나서, 타일 수는 이전 단계의 4배가 됩니다.

확대 수준이 올라갈수록 지도는 자세해지지만, 클라이언트가 내려받는 데이터 양이 그만큼 늘어나지는 않습니다.
화면을 채우는 데 필요한 타일 수는 확대 수준과 상관없이 비슷하고, 클라이언트는 현재 확대 수준에 맞는 타일만 받기 때문입니다.
그래서 대역폭을 많이 쓰지 않고도 화면에 맞는 크기의 지도를 보여 줄 수 있습니다.

📌 최적화: 벡터 사용

이미지 타일을 보내는 대신 지도를 그리는 데 필요한 정보만 벡터 형태로 보내고, 클라이언트가 받은 정보로 지도를 직접 그리는 방법입니다.
클라이언트에서는 WebGL 같은 기술로 지도를 그립니다.

• 점(point)
• 경로(path)
• 다각형(polygon)

벡터를 쓰면 좋은 점은 두 가지입니다.

• 압축률이 높다: 벡터 데이터는 이미지보다 압축이 잘 되어, 네트워크로 보내는 데이터 양이 줄어든다.
• 확대·축소가 부드럽다: 이미지 타일은 확대 수준 사이에서 늘려 보이며 흐려지지만, 벡터는 클라이언트가 확대 수준에 맞게 다시 그려서 부드럽게 보인다.
  비기능 요구사항의 "부드러운 경로 표시"와 이어진다.

경로 안내 서비스

📌 최단 경로 서비스

출발지와 목적지의 위도·경도를 받아 k개의 최단 경로를 돌려주는 서비스로, A* 알고리즘을 씁니다.

1. 출발지와 목적지의 위도·경도를 지오해시로 바꿔, 두 지점이 속한 경로 안내 타일을 불러온다.
2. 출발지 타일에서 A* 탐색을 시작하고, 탐색이 타일 밖으로 나가면 참조를 따라 인접 타일을 그때그때 불러온다.
3. 장거리 경로라면 계층적 타일을 써서, 중간 구간은 고속도로만 담은 넓은 타일로 탐색한다.

이 서비스는 교통 상황이나 도로 상황을 고려하지 않고 도로 구조만 봅니다.
도로망 그래프는 자주 바뀌지 않는 정적인 데이터라서, 경로 안내 타일과 탐색 결과를 캐싱해 두기 좋습니다.

📌 예상 도착 시간 서비스

최단 경로 서비스가 돌려준 경로마다 예상 도착 시간을 계산합니다.
기계 학습을 활용해 현재 교통 상황과 과거 이력을 바탕으로 계산합니다.

현재 교통 상황뿐 아니라 10분 뒤, 20분 뒤의 교통 상황까지 예측해야 하고, 영향을 주는 요소도 많아서 알고리즘 차원에서 어려운 문제입니다.
책에서도 이 부분은 깊게 다루지 않습니다.

📌 중요 정보 갱신 서비스들

카프카의 위치 데이터 스트림을 구독하고, 도로 정보를 반영해 경로 안내 타일을 계속 갱신합니다.
새로 열린 도로나 폐쇄된 도로를 찾아 반영하면, 최단 경로 서비스는 최신 도로망으로 경로를 찾을 수 있습니다.

📌 적응형 ETA와 경로 변경

교통 상황은 계속 바뀌므로, 경로 안내를 받고 있는 모든 사용자를 추적하면서 바뀐 교통 상황에 맞춰 ETA를 다시 계산해 줘야 합니다.
이를 위해 두 가지 질문에 답해야 합니다.

• 경로 안내를 받는 사용자들은 어떻게 추적할까?
• 교통 상황이 바뀌었을 때 영향을 받는 사용자를 어떻게 효율적으로 찾을까?

가장 단순한 방법은 사용자마다 경로가 지나는 경로 안내 타일 목록을 저장해 두는 것입니다.
어떤 타일의 교통 상황이 바뀌면, 모든 사용자의 타일 목록에 그 타일이 있는지 하나씩 확인합니다.
안내받는 사용자가 N명이고 경로 하나가 평균 M개의 타일을 지난다면 O(N × M) 이 들어 비효율적입니다.

개선한 방법은 사용자마다 현재 위치의 타일에서 시작해, 출발지와 목적지를 모두 포함하는 타일을 찾을 때까지 더 큰 타일을 재귀적으로 저장해 두는 것입니다.

사용자 1: 현재 타일 → 그 타일을 포함하는 더 큰 타일 → … → 출발지와 목적지를 모두 포함하는 타일

교통 상황이 바뀐 타일이 사용자 목록의 마지막 타일, 즉 출발지와 목적지를 모두 포함하는 가장 큰 타일 안에 있는지만 확인하면 됩니다.
그 안에 없으면 그 사용자는 영향을 받지 않으므로, 사용자마다 한 번씩만 확인해 O(N) 으로 줄어듭니다.

반대로 교통 상황이 나아져서 막혔던 경로를 다시 쓸 수 있게 되었을 때, 이를 사용자에게 어떻게 알릴지도 생각해야 합니다.
안내받는 사용자의 ETA를 주기적으로 다시 계산하면, 더 빠른 경로가 생겼을 때 자연스럽게 알려 줄 수 있습니다.

📌 전송 프로토콜

경로 안내 중에는 ETA나 경로 변경 같은 정보를 서버가 클라이언트에 먼저 보내야(push) 합니다.
이때 쓸 수 있는 프로토콜은 다음과 같습니다.

폴링은 요청마다 연결을 맺고 끊지만, 웹소켓은 하나의 연결을 계속 쓰기 때문에 서버에 주는 부담이 더 적습니다.
또 웹소켓은 양방향 통신을 지원하므로, 양방향 통신이 필요하다면 웹소켓을 고를 수 있습니다.
웹소켓은 주변 친구 설계에서도 위치 공유에 썼습니다.

최종 설계안

마치며

위치 갱신, ETA, 경로 계획, 지도 격자 나누기, 그래프 구성 및 저장 같은 내용으로 구글 맵의 핵심 기능을 갖춘 애플리케이션을 설계해 보았는데, 책으로만 볼 때는 쉬웠지만 스터디 그룹에서 진행한 스터디는 만만치 않았습니다.

읽기만 할 때는 다 이해한 줄 알았는데, 문제로 접하니 쉽지 않았습니다.
문제를 풀다 막힌 부분도 있었는데, 도로가 폐쇄되었을 때 폐쇄를 반영하는 건 쉬웠지만 언제 다시 열지 정하는 건 어려웠습니다.
또 해당 간선의 비용을 무한대로 늘려 경로 탐색에서 제외시키는 방법처럼, 책에 나온 내용 말고도 많은 이야기가 스터디에서 나왔습니다.
실제 실무에서는 훨씬 많은 문제를 마주하게 된다는 걸 다시 한 번 깨닫는 한 주였습니다.

참고

• 알렉스 쉬, 산 란, 『가상 면접 사례로 배우는 대규모 시스템 설계 기초 2』, 인사이트 — 3장 구글 맵