3장 구글 맵 (1)

조예슬·2024년 6월 17일

3장 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2 구글 맵

이번 장에서는 기존에 우리가 사용하는 구글 맵 보다는 단순한 형태의 구글 맵을 설계해보도록 한다.
구글 맵은 엄청나게 복잡한 제품이므로, 설계에 앞서 어떤 기능에 초점을 맞추어야 하는지 확인해야 한다.

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

기능 요구 사항

사용자 위치 갱신
경로 안내 서비스 (ETA - 예상 도착 시간 서비스 포함)
지도 표시

비기능 요구사항 및 제약 사항

정확도 : 사용자에게 잘못된 경로를 안내하면 안된다.
부드러운 경로 표시 : 클라이언트를 통해 제공되는 경로 안내 용도의 지도는 화면에 아주 부드럽게 표시되고 갱신되어야 한다.
데이터 및 배터리 사용량 : 클라이언트는 가능한 한 최소한의 데이터와 배터리를 사용해야 한다. 모바일 단말에 아주 중요한 요구사항이다.
일반적으로 널리 통용되는 가용성 및 규모 확장성 요구사항을 만족해야 한다.

설계 하기전 관련된 몇가지 기본 개념 및 용어를 먼저 살펴보자.

지도 101

측위 시스템

지구는 축을 중심으로 회전하는 구이다. 측위 시스템은 이 구 표면 상의 위치를 표현하는 체계를 말한다.
이 시스템에서 위도는 주어진 위치가 얼마나 북쪽/남쪽인지를 나타내며, 경도는 얼마나 동쪽/서쪽인지를 나타낸다.

3차원 위치의 2차원 변환

3차원 구 위의 위치를 2차원 평면에 대응시키는 절차를 지도 투영법 또는 도법이라고 부른다.
도법은 다양하며, 그 각각은 다른 도법과는 차별되는 장단점을 갖는다. 하지만 거의 모든 투영법은 실제 지형의 기하학적 특성을 왜곡한다는 공통점을 갖는다.
아래는 대표적인 도법 4개의 차이점을 나타내는 그림이다.

구글 맵은 메르카토르 도법을 조금 변경한 웹 메르카토르 도법을 택하고 있다.

지오코딩

지오코딩은 주소를 지리적 측위 시스템의 좌표로 변화하는 프로세스이다.
지오코딩을 수행하는 한 가지 방법은 인터폴레이션 이다. GIS와 같은 다양한 시스템이 제공하는 데이터를 결합한다는 뜻이다.
GIS는 도로망을 지리적 좌표 공간에 대응시키는 방법을 제공하는 여러 시스템 가운데 하나이다.

지오해싱

지오해싱 은 지도 위 특정 영역을 영문자와 숫자로 구성된 짧은 문자열에 대응시키는 인코딩 체계이다. 이는 이전 장에서도 소개 했던 바가 있기 때문에, 간단하게 그림만 첨부한다.

지도 표시

지도를 화면에 표시하는데 가장 기본이 되는 개념은 타일이다. 지도 전부를 하나의 이미지로 표시하는 대신, 작은 타일로 쪼개어 표시하는 것이다.

클라이언트는 사용자가 보려는 영역에 관계된 타일만 다운받아 모자이크처럼 이어 붙인 다음 화면에 뿌린다.

지도의 확대/축소를 지원하려면 확대 수준에 따라 다른 종류의 타일을 준비해야한다. 클라이언트는 현재 클라이언트가 보려는 지도 확대 수준에 근거하여 어떤 크기의 타일을 가져올지 고른다.

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

대부분의 경로 탐색 알고리즘은 다익스트라 알고리즘이나 A* 경로 탐색 알고리즘의 변종이다. 모든 경로 탐색 알고리즘은 교차로를 노드로, 도로는 노드를 잇는 선으로 표현하는 그래프 자료 구조를 가정한다는 것이다.

대부분의 경로 탐색 알고리즘의 성능은 주어진 그래프 크기에 아주 민감하다. 따라서 본 설계안이 가정하는 규모에서 좋은 성능을 보이려면 그래프를 관리 가능 단위로 분할할 필요가 있다.

전 세계 도로망을 더 작은 단위로 분할하는 방법 가운데 하나는 지도 표시에 사용하는 타일 기반 분할법과 아주 유사하다. 지오해싱과 비슷한 분할 기술을 적용하여 세계를 작은 격자로 나누고, 각 격자 안의 도로망을 노드와 선으로 구성된 그래프 자료 구조로 변환한다.

이 때 각 격자는 경로 안내 타일이라고 부르고, 이 타일은 도로로 여결된 다른 타일에 대한 참조를 유지한다. 그래야 경로 탐색 알고리즘이 연결된 타일들을 지나갈 때 보일 더 큰 도로망 그래프를 만들어 낼 수 있다.

도로망을 언제든 불러올 수 있는 경로 안내 타일로 분할해 놓으면 경로 탐색 알고리즘이 동작하는 데 필요한 메모리 요구량을 낮출 수 있을 뿐 아니라 한번에 처리해야 하는 경로의 양이 줄어들고, 필요한 만큼만 불러오면 되기 때문에 경로 탐색 성능도 좋아진다.

계층적 경로 안내 타일

경로 안내가 효과적으로 동작하려면 필요한 수준의 구체성을 갖춘 도로 데이터가 필요하다. 보통 구체성 정도를 상, 중, 하로 구분하여 세 가지 종류의 경로 안내 타일을 준비한다.

가장 구체성이 높은 타일(상) 의 경우 그 크기는 아주 작으며, 이런 타일에는 지방도 데이터만 둔다.
그 다음 레벨의 타일(중) 은 더 넓은 지역을 커버하며, 규모가 비교적 큰 관할구를 잇는 간선 도로 데이터만 둔다.
마지막으로 구체성이 가장 낮은 타일(하) 은 그보다 더 큰 영역을 커버하며, 그런 타일에는 도시와 주를 연결하는 주요 고속도로 데이터만 둔다.
각 타일에는 다른 정밀도 타일로 연결되는 선이 있을 수 있다. 예를 들어 지방도 A에서 고속도로 F로 진입하는 경로를 표시하려면 도로 A의 특정 지점을 나타내는 노드에서 도로 F의 특정 지점을 나타내는 노드 사이에 연결선이 있어야만 한다.

개략적 규모 추정

이제 기본적인 지식은 습득하였으니 풀어야 할 문제 규모를 간단히 추정해보자. 설계 초점이 모바일 단말이므로, 데이터 사용량과 배터리 효율을 중요하게 따져 봐야 한다.
추정에 앞서 도량형 변환 규칙 몇 가지를 참고 삼아 정리해두겠다.

1피트 = 0.3048미터
1킬로미터 = 0.6214마일
1킬로 = 1,000미터

저장소 사용량

다음 세 가지 종류의 데이터를 저장해야 한다.

세계 지도 : 상세한 저장 용량 계산식은 잠시 후 다룬다.
메타데이터 : 각 지도 타일의 메타데이터는 크기가 아주 작아서 무시해도 지장이 없을 정도이므로, 본 추정에서는 제외한다.
도로 정보 : 면접관과의 문답을 통해, 외부에서 받은 수 TB 용량의 도로 데이터를 보유하고 있음을 확인한 바 있다. 이 데이터를 경로 안내 타일로 변환하여야 한다. 변환 결과의 용량도 비슷할 것이다.

세계 지도
지원하는 확대 수준별로 지도 타일을 한 벌씩 두어야 한다. 그 타일 전부를 보관하는 데 필요한 용량을 가늠하려면 최대 확대 수준, 즉 지도를 최대한 확대하여 보는 데 필요한 타일 개수를 따져보면 좋다.

지도를 확대할 때마다 하나의 타일을 네 장의 타일로 펼친다고 가정하자. 세계 지도를 21번 확대하여 볼 수 있으려면 최대 확대 수준을 대상으로 했을 때 약 4.4조 개의 타일이 필요하다.

한 장의 타일이 256 X 256 픽셀 압축 PNG 파일이라면 한 장당 100KB의 저장 공간이 필요하므로, 최대 확대 시 필요 타일을 전부 저장하는 데는 총 4.4조 X 100KB = 440PB 만큼의 저장 공간이 필요할 것이다.

하지만 지구 표면 가운데 90%는 인간이 살지 않는 자연 그대로의 바다, 사막, 호수, 산간 지역임에 유의하자. 이들 지역의 이미지는 아주 높은 비율로 압축할 수 있으므로, 보수적으로 보아 80%에서 90% 가량의 저장 용량을 절감할 수 있다. 따라서 저장 공간 요구량은 44PB에서 88PB 가량으로 줄어든다. 어림하여 50PB 정도가 필요하다고 보고 넘어가자.

서버 대역폭
서버 대역폭을 추정하기 위해서는 어떤 유형의 요청을 처리해야 하는지 살펴봐야 한다. 서버가 처리해야하는 요청은 크게 두 가지다.

첫 번째는 경로 안내 요청으로, 클라이언트가 경로 안내 세션을 시작할 때 전송하는 메세지다. 두 번째는 위치 갱신 요청이다.
클라이언트가 경로 안내를 진행하는 동안 변경된 사용자 위치를 전송하는 메세지다.

이런 경로 안내 요청을 처리하기 위한 서버 대역폭을 분석해보자. DAU는 10억이고, 각 사용자는 경로 안내 기능을 평균적으로 주당 35분 사용한다고 하자. 이는 환산하면 주당 350억 분, 즉 하루에 50억 분이다.

단순한 접근법 하나는 GPS 좌표를 매초 전송하는 것인데, 그렇게 하면 하루에 3000억 건의 요청이 발생하고 (50억분 X 60) 이는 3백만 QPS에 해당한다.
하지만 클라이언트가 매초 새로운 GPS 좌표를 보낼 필요가 없을 수도 있다.
가령 이들 요청을 클라이언트 쪽에서 모아 두었다가 덜 자주 보내도록 하면(가령 15초나 30초마다 한 번씩) 쓰기 QPS를 낮출 수 있을 것이다.

얼마나 자주 보내면 좋을지는 사용자의 이동 속도 등 다양한 요건에 좌우된다. 가령 사용자가 꽉 막힌 도로 한가운데 있다면 GPS 위치 업데이트를 그렇게 자주 보낼 필요는 없을 것이다. 본 설계안의 경우에는 GPS 위치 변경 내역은 모아 두었다가 15초 마다 한 번씩 서버로 보낸다고 가정하겠다. 이렇게 하면 QPS는 20만으로 줄어든다.

최대 QPS는 평균치의 다섯 배 가량으로 가정하겠다. 따라서 위치 정보 갱신 요청 최대 QPS는 200,000 X 5 = 1백만이다.

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

이제 구글 맵에 대해 많은 것을 배웠으니 개략적 설계안을 제안해보도록 하자.

개략적 설계안

이 개략적 설계안은 다음 세 가지 기능을 제공한다.

위치 서비스
경로 안내 서비스
지도 표시 서비스

위치 서비스

위치 서비스는 사용자의 위치를 기록하는 역할을 담당한다.

본 기본 설계 안은 클라이언트가 t초마다 자기 위치를 전송한다고 가정한다. 여기서 t는 설정이 가능한 값이다. 이렇게 주기적으로 위치 정보를 전송하면 몇 가지 좋은 점이 있다.

첫 번째는 해당 데이터 스트림을 활용하여 시스템을 점차 개선할 수 있다는 점이다. 실시간 교통 상황을 모니터링하는 용도로 활용할 수 있고, 새로 만들어진 도로나 폐쇄된 도로를 탐지할 수도 있고, 사용자 행동 양태를 분석하여 개인화된 경험을 제공하는데 활용할 수도 있다.

두 번째 장점은 클라이언트가 보내는 위치 정보가 거의 실시간 정보에 가까우므로 ETA를 좀 더 정확하게 산출할 수 있고, 교통 상황에 따라 다른 경로를 안내할 수도 있다는 점이다.

하지만 사용자의 위치가 바뀔 때마다 그 즉시 서버로 전송해야만 할까 ? 아마 아닐 것이다. 위치 이력을 클라이언트에 버퍼링해 두었다가 일괄 요청하면 전송 빈도를 줄일 수 있다.

위치 변경 내역은 매초 측정하긴 하지만 서버로는 15초마다 한번 보내놓도록 설정해놓은 사례이다. 구글 맵과 같은 시스템은 이렇게 해서 위치 갱신 요청 빈도를 줄여도 여전히 많은 쓰기 요청을 처리해야만 한다. 따라서 아주 높은 쓰기 요청 빈도에 최적화되어 있고 규모 확장이 용이한 카산드라 같은 데이터베이스가 필요하다.
또한 카프카 같은 스트림 처리 엔진을 활용하여 위치 데이터를 로깅해야 할 수도 있다.

통신 프로토콜로는 HTTP를 keep-alive 옵션과 함께 사용하면 효율을 높일 수 있으므로 좋은 선택이 될 것이다.

POST /v1/locations
인자:
locs: JSON으로 인코딩한 (위도, 경도, 시각) 순서쌍 배열

경로 안내 서비스

이 컴포넌트는 A에서 B 지점으로 가는 합리적으로 빠른 경로를 찾아 주는 역할을 담당한다. 결과를 얻는 데 드는 시간 지연은 어느 정도 감내할 수 있다.
계산된 경로는 최단 시간 경로일 필요는 없으나 정확도는 보장되어야 한다.

앞에 그림에서도 봤듯이, 사용자가 보낸 경로 안내 HTTP 요청은 로드밸런서를 거쳐 서비스에 도달한다. 이 요청에는 출발지와 목적지가 인자로 전달된다.
해당 API 요청은 대략 다음과 같은 형태이다.

GET /v1/nav?origin=1355+market+street, SF&destination=Disneyland

그 결과로 만들어지는 경로 안내 결과는 아래와 같다.

{
  'distance': {'text': '0.2 mi', 'value': 259},
  'duration': {'text': '1 min', 'value': 83},
  'end location': {'lat': 37.4038943, 'Ing': -121.9410454},
  'html instructions': 'Head <b>northeast</b> on <b>Brandon St</b>
  toward <b>Lumin Way</b><div style="font-size:0.9em"> Restricted usage road</div>',
  'polyline': {'points': '_fhcFjbhgVuAwDsCal'},
  'start location': {'lat': 37.4027165, 'Ing': -121.94358095,
  'geocoded_waypoints': [
  {
  "geocoder_status" : "OK",
  "partial_match" : true,
  "place_id" : "ChIJwZNMtilfawwRO2aVVVX2yKg",
  "types" : [ "locality', "political" ]
  },
  {
  "geocoder status" : "OK"'
  "partial_match" : true,
  "place_id" : "ChIJ3aPgQGtXawwRLYeiBMUi7bM"
  "types" : [ "locality", "political" ]
  }
  ],
  'travel mode': 'DRIVING'
}

지금까지는 경로 재탐색이나 교통 상황 변화 같은 문제는 고려하지 않았따. 이런 문제들을 상세 설계를 진행하면서 살펴볼 적응형 ETA를 통해 해결할 수 있다.

지도 표시

대략적으로 시스템 규모를 추정할 때 알아본 바에 따르면, 확대 수준별로 한 벌씩 지도 타일을 저장하려면 수백 PB가 필요하다. 그 모두를 클라이언트가 가지고 있는 것은 실용적인 방법이 아니다. 클라이언트의 위치 및 현재 클라이언트가 보는 확대 수준에 따라 필요한 타일을 서버에서 가져오는 접근법이 바람직하다.

클라이언트가 지도 타일을 서버에서 가져오는 시나리오는 다음과 같이 생각해볼 수 있다.

사용자가 지도를 확대 또는 이동시켜주며 주변을 탐색
경로 안내가 진행되는 동안 사용자의 위치가 현재 지도 타일을 벗어나 인접한 타일로 이동한다.

다량의 지도 타일 데이터를 서버에서 효과적으로 가져오려면 어떻게 해야 하는지 알아보자.

선택지 1
이 방법은 클라이언트의 위치, 현재 클라이언트가 보는 지도의 확대 수준에 근 거하여 필요한 지도 타일을 즉석에서 만드는 방안이다. 사용자 위치 및 확대 수준의 조합은 무한하다는 점을 감안하면, 이 방안에는 몇 가지 심각한 문제가 있다.

모든 지도 타일을 동적으로 만들어야 하는 서버 클러스터에 심각한 부하가
걸린다.
캐시를 활용하기가 어렵다.

선택지2
다른 방법은 확대 수준별로 미리 만들어 둔 지도 타일을 클라이언트에 전달하 기만 하는 방법이다. 각 지도 타일이 담당하는 지리적 영역은 지오해싱 같은 분할법을 사용해 만든 고정된 사각형 격자로 표현되므로 정적이다. 클라이언트는 지도 타일이 필요할 경우 현재 확대 수준에 근거하여 필요한 지도 타일 집합을 결정한다. 그런 다음 그 각 위치를 지오해시 URL로 변환한다.
이렇게 미리 만들어 둔 정적 이미지는 CDN을 통해 다음 그림과 같이 서비스한다.

위 다이어그램에서 모바일 단말 사용자는 지도 타일 요청을 CDN에 보낸다. 해당 타일이 CDN을 통해 서비스된 적이 없는 경우, CDN은 원본 서버에서 해당 파일을 가져와 그 사본을 캐시에 보관한 다음 사용자에게 반환한다.

그 뒤로 다른 사용자가 같은 파일을 요청하면 CDN은 캐시에 보관한 사본을 서비스하 며, 원본 서버는 다시 접촉하지 않는다.

이 접근법은 규모 확장이 용이하고 성능 측면에서도 유리하다. 사용자에게 가장 가까운 POP(Point of Presence)에서 파일을 서비스하기 때문이다.

지도 타일은 정적이므로 캐시를 통해 서비스하기에 아주 적합하다.

모바일 데이터 사용량을 줄이는 것은 중요하다. 그러니 경로 안내를 진행하 는 동안 클라이언트가 일반적으로 필요로 할 데이터 양을 계산해 보자.

다음 쪽의 계산 결과는 클라이언트 측 캐시는 고려하지 않았음에 유의하자. 사람들은 같은 길을 일상적으로 이용하는 경향이 있으므로, 클라이언트에 캐시를 두 면 데이터 사용량을 많이 줄일 수 있을 것이다.

데이터 사용량

사용자가 30km/h 속도로 이동 중이며, 한 이미지가 200mx 200m 영역을 표 현하도록 확대하여 지도를 표시하고 있는 상황이라고 하자. (이미지 하나 는 256x256픽셀 이미지이며 평균 이미지 크기는 100KB이다.) 1kmx 1km 영역을 표현하려면 이미지 25장이 필요하며, 이는 저장 용량으로 환산하면 2.5MB(25X 100KB)이다. 그러므로 30km/h 속도로 이동한다고 하면 시간당
75MB의 데이터가 소진되며(30x2.5MB), 이는 분당 1.25MB에 해당한다.

CDN을 통해 서비스 되는 트래픽 규모

앞서 언급하였듯, 우리는 매일 50억 분(minutes) 가량의 경로 안내를 처리한다. 이는 50억 x 1.25MB = 6.25PB/일에 해당하는 양이다. 그러므로 초당 전송해야 하는 지도 데이터의 양은 62,500MB가 된다.

CDN을 사용하면 이 지도 이미지는 전 세계에 흩어져 있는 POP를 통해 제공될 것이다. 전 세계에 200개의 POP가 있다고 하자. 각 POP는 수백 MB 정도의 트래픽만 처 리하면 될 것이다 (62,500/200)

이제 앞에서 간단히 언급하기는 했지만 자세히 살펴보지는 않았던 마지막 한 가지 사항을 조금 더 구체적으로 알아보자.

클라이언트는 CDN에서 지도 타일을 가져올 URL을 어떻게 결정할까? 앞 절에서 살펴본 두 가지 선택지 가운데 후자를 이용할 것이다. 따라서 지도 타일은 이미 정의된 격자에 맞게 확대 수준별로 한 벌씩 미리 만들어 둔 것을 사용하게 된다.

지오해시를 사용해 격자를 나누므로 모든 격자는 고유한 지오해시 값을 갖는다. 따라서 위도/경도로 표현된 클라이언트의 위치 및 현재 지도 확대 수준 입력으로 화면에 표시할 지도 타일에 대응되는 지오해시는 아주 쉽게 계산해 낼 수 있다.

그 계산은 지도를 화면에 표시할 클라이언트가 수행하며, 그 해당 지오해시 및 URL로 CDN에서 지도 타일을 가져오면 된다.

예를 들어 구글 본사가 속한 지도 타일 이미지를 가져오는 URL은 다음과 비슷한 형태일 것이다.

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

앞에서 서술한 대로 지오해시 계산은 클라이언트가 수행해도 된다. 하지만 해당 알고리즘을 클라이언트에 구현해 놓으면 지원해야 할 플랫폼이 많을 때 문제가 될 수 있음은 주의하자.

모바일 앱 업데이트 배포는 시간도 많이 걸리고 때로는 위험한 프로세스다. 따라서 앞으로도 오랫동안 맵 타일 인코딩에는 지오해싱을 사용하리라는 보장이 있어야 한다. 혹시라도 다른 인코딩 방안으로 교체해야 한다면 많은 노력이 필요하며 위험성도 만만치 않을 것이다.

고려해 볼 만한 다른 한 가지 선택지는 주어진 위도 경도 및 확대 수준을 타일 URL로 변환하는 알고리즘 구현을 별도 서비스에 두는 것이다. 이 서비스는 위도, 경도, 현재 확대 수준을 입력으로 하여 타일 URL을 계산하는 역할만 담당하는 아주 간단한 서비스이다. 운영 유연성이 높아지는 이점이 있으므로 고려할 가치가 있다. 장단점을 면접관과 논의해 보면 아주 흥미로울 것이다.

사용자가 새로운 위치로 이동하거나 확대 수준을 변경하면 지도 타일 서비스는 어떤 타일이 필요한지 결정하여 해당 타일들을 가져오는 데 필요한 URL 집합을 계산해 낸다.