대규모 시스템 설계 기초2 - 구글 맵

구글 맵 문제 정의 & 범위

기능

 - 위치 갱신

 - 경로 안내: ETA(Estimated Time of Arrival) 예상 도착 시간 포함. 교통 상황 고려. 다양한 이동 방법 지원. 경유지 x.

 - 지도 표시: 사업장의 사진은 고려하지 않기로 함.

 

비기능

 - 정확도

 - 부드러운 경로 표시

 - 데이터 및 배터리 사용량

 - 일반적으로 널리 통용되는 가용성 및 규모 확장성 요구사항 만족

 

모바일 플랫폼 사용

일간 능동 사용자 수 : 10억 DAU

도로 데이터 규모 : 수 TB. 가공되지 않은 데이터.

 

3차원 데이터 -> 2차원 -> 1차원 변환

구글맵은 전세계를 따진다.

지구인 3차원의 구를 2차원 평면에 대응시키는 절차를 '지도 투영법' 또는 '도법'이라고 부른다.

 

도법은 각각 차별되는 장단점을 가진다.

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

 

도법을 적용하여 위도,경도,고도에서 위도,경도만으로 구성한다.

 

실제 주소를 2차원의 위도,경도로 나타낼때 사용되는게 지오코딩이다. 반대는 역 지오코딩(reverse geocoding)

ex) 미국 주소 '1600 Amphitheatre Parkway, Mountain View, CA' -> (위도 37.423021, 경도 -122.083739)

 

지오코딩을 수행하는 한 가지 방법은 GIS의 인터폴레이션이다.

GIS에서 인터폴레이션이란?
지도 위에 일부 지점의 데이터만 있는 상황에서, 그 사이의 값을 계산해 전체 지도를 완성하는 기법입니다.
위치 기반 예측, 공간 분석, 환경 모델링 등 거의 모든 지리 데이터 처리에 필수적으로 쓰입니다.

 

2차원의 데이터를 1차원으로 하는 방법은 지오해싱을 통해 지도 위 특정 지역을 영문자와 숫자로 구성죈 짧은 문자열에 대응시킨다.

 

지도 표시 방법

지도를 화면에 표시하는 방법의 기본 개념은 타일이다.

지도 전부를 하나의 이미지로 표시하는 대신, 작은 타일로 쪼개어 표시한다.

 

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

지도의 확대/축소를 지원하려면 확대 수준에 따라 다른 종류의 타일을 준비해서 보여준다.

지도 확대 수준에 근거하여 어떤 크기의 타일을 가져올지 결정한다.

 

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

대부분의 경로 탐색 알고리즘은 다익스트라 알고리즘이나 A*(A-star) 경로 탐색 알고리즘의 변종이다.

 

경로 탐색 알고리즘은 교차로를 노드로, 도로는 노드를 잇는 선으로 표현하는 그래프 자료 구조를 가정한다.

경로 탐색에서 좋은 성능을 보일려면 그래프를 관리 가능 단위로 분할해야한다.

 

지도 표시방법에서 사용되었던 타일 기반 분할법과 유사하게,

세계를 작은 격자로 나누고, 각 격자 안의 도로망을 노드와 선으로 구성된 그래프 자료 구조로 변환한다.

각 격자는 경로 안내 타일이라 부른다.

각 타일은 도로로 연결된 다른 타일에 대한 참조를 유지한다.

그래야 경로 탐색 알고리즘이 연결된 타일들을 지나갈 때 보일 더 큰 도로망 그래프를 그릴 수 있다.

 

분할로 인해 얻을 수 있는 이점은 알고리즘이 동작하는데 필요한 메모리 요구량을 낮추고 한번에 연산해야할 양을 줄인다.

 

보통 구체성 정도를 기반으로 3가지 종류의 경로 안내 타일을 준비해두는 편.

(지방도, 간선 도로, 고속도로 형태)

 

개략적 규모 추정

저장소 사용량

아까 얘기했던 지도 타일은 확대 수준별로 지도 타일을 한벌씩 두어야 한다.

구글맵에선 21개의 확대수준을 두고 있고, 확대를 한번할때마다 하나의 타일을 4장의 타일로 펼친다고 가정.

21확대수준이면 총 4.4조개의 타일이 필요. 1장의 타일은 256*256 픽셀 압축 png 파일이면 100KB로 가정.

4.4조 * 100KB = 440PB 필요.

지구는 90%가 인간이 살지 않는 지역이므로 해당 지역들은 높은 비율로 압축 가능.

80%는 압축된다는 가정하에 440*0.2 = 88PB 대략 50PB라고 가정.

확대 수준 별로 가지고 21확대가 50PB이니,

50 + 50/4 + 50/16 + ... = 67PB. 모든 확대수준을 가진다고 가정하에 67PB.

 

지도 타일의 메타데이터는 크기가 매우 작으므로 무시.

도로 정보는 아까 얘기했던 수 TB에서 결로 안내 타일로 변환해도 비슷한 용량.

 

QPS 추정

서버가 처리하는 요청은 크게 2가지.

경로 안내 요청과 사용자 위치 갱신 요청.

 

경로 안내 요청은 클라이언트가 경로 안내 세션을 시작할때 전송하는 메세지.

 

사용자 위치 갱신 요청이 큰데, 경로 안내를 할때 사용자의 위치 갱신이 주기적으로 이루어져야하기 때문.

 

DAU 10억. 각 사용자는 경로 안내 기능을 평균적으로 주당 35분 사용. 하루에 50억분.

하루에 3600억 요청.  초당 위치를 갱신한다고 하면, 대략 416만 qps지만, 계산 편의를 위해 300만 qps로 보겠음.

하지만 클라이언트단에서 위치정보를 갱신하고 있다가 15~30초 중 15초 단위로 서버에 동기화해준다는 가정하면,

qps는 20만. 최대는 평균치의 5배라고 가정.

 

최종 추정치

최대 qps 100만.

평균 qps 20만

 

개략적 설계안

위치서비스

위치 서비스는 그냥 15초동안은 클라이언트내에서 위치정보를 업데이트하다가 서버에게 일괄 요청하는 형태.

하지만, 이렇게 하더라도 위에서 추정했듯 높은 쓰기 요청을 해야함.

책에선 카산드라를 추천했지만, 자주 사용되고 익숙한 Nosql기반 MongoDB를 쓸 것 같음...

 

통신 프로토콜로는 http에 keep-alive를 추천함.(지속적 연결을 가지는 형태)

 

경로 안내 서비스

경로 안내 서비스는 출발지와 목적지가 인자로 전달되고,

응답으로 예상 도착 시간과 지오코딩 기반의 값들이 같이 온다.

 

지도 표시

클라이언트의 위치를 기반으로 확대 수준별로 미리 만들어둔 지도 타일을 전달하기만 하는 방법이 좋다.

현재 위치와 확대 수준에 근거하여 지도 타일 집합을 결정하고, 지오해시 url로 변환한다.

이렇게 미리 만들어둔 정적 이미지는 cdn을 통해 제공한다.

 

cdn 비용 추산

cdn은 세계적으로 뿌려져있고 가장 가까운 cdn을 통해서 캐싱된 데이터를 빠르게 가져오므로 효과적이다.

cdn도 비용이 발생하므로 추정해보자.

 

사용자가 30km/h 속도로 이동중이며, 클라이언트가 확대 수준이 200m x 200m 표현하도록 확대해서 지도를 보고 있다고 가정하자.

 

1km x 1km 영역을 표현하는데 25장 이미지가 필요하고 2.5MB가 필요하다. (이미지 1개당 100KB로 위에서 추정함)

30km/h이므로 시간당 75MB. 이는 분당 1.25MB의 데이터를 사용한다.

 

앞서 얘기했던 하루에 50억 분의 경로 안내를 처리한다고 했으니,

50억 * 1.2MB = 6.25PB/일의 트래픽양이 결정된다. 초당으로 계산하면 62,500MB.

CDN을 사용시엔 전 세계에 흩어져있는 POP를 통해 제공되고(약 200개라고 가정),
POP마다 골고루 사용된다는 가정하면 각 POP는 62,500MB/200. 수백 MB 정도의 트래픽을 처리하면 될 것이다.

 

추가적인 지오해시 계산 처리 위치

클라이언트단에서 계산해도 되나, 클라이언트단 계산 시 지원해야할 플랫폼이 많을 때의 문제상황과 모바일 앱의 경우 배포하는데 오래걸린다. 그래서 별도의 서비스를 구현해두는 게 좋다.

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

그럼 클라이언트는 url로 cdn을 통해 다운로드하여 보여준다.

 

상세 설계

데이터 모델

경로 안내 타일

경로 안내 타일(그래프형태의 데이터)은 s3같은 객체 저장소에 파일을 보관하고 그 파일을 이용할 경로 안내 서비스에서 적극적으로 캐싱하는 것이다.

타일을 객체 저장소에 저아할 때 지오해시 기준으로 분류해 두는 것이 좋다.

그러면 위도와 경도가 주어졌을 때 타일을 신속하게 찾을 수 있다.

(지오 해시 값을 키값으로 저장. 이후 서비스에서 위치에 해당하는 지오해시 셋을 구해와서 s3에 조회하여 구성)

 

사용자 위치 데이터

사용자 위치 데이터는 도로 데이터 및 경로 안내 타일을 갱신하는데 이용되며,

실시간 교통 상황 데이터나 교통 상황 이력 데이터베이스를 구축하는 데도 활용된다.

아주 많은 쓰기 연산을 잘 처리할 수 있는 수평 확장 데이터베이스가 필요하다.

 

지오코딩 데이터베이스

주소를 위도/경도 쌍으로 변환하는 정보를 보관.

쓰기 작업은 적고 읽기 작업을 빠르게 반환해야하기 때문에 레디스가 적합.

 

미리 만들어 둔 지도 이미지

특정 영역의 지도를 요청하면 인근 도로 정보를 취합하여 모든 도로 및 관련 상세 정보가 포함된 이미지를 만들어야 한다.

이미지는 확대 수준별로 미리 만들어두고 cdn을 통해 전송한다.

 

위에서 얘기했듯 이후 사용자가 특정 위치의 지도를 요청하면, 해당 위치와 확대 수준에 대응되는 정적 지도 타일들을 CDN에서 가져와 모자이크처럼 조합하여 지도 화면을 구성한다.

 

서비스

위치 서비스

위치 데이터 저장은 키-값 저장소르 활용한다.

초당 백만 건의 위치 정보 업데이트가 발생한다는 점을 감안하면 noSQL 키-값 데이터 베이스나 열-중심 데이터베이스가 그런 요구에 적합.

 

사용자의 위치는 계속 변화하며 이전 정보는 무의미하기에, 데이터의 일관성보단 가용성이 더 중요. ( AP 가용성 & 분할 내성 챙기기 )

 

user_id, timestamp, lat, long, user_mode, navigation_mode 등의 데이터를 받으며,

user_id와 timestampl의 조합으로 데이터베이스 키를 잡는다.

 

사용자의 위치 데이터는 카프카를 통해 다양한 서비스에서 섭취해서 사용하게 처리한다.

(실시간 교통 상황 서비스, 개인화를 위한 기계 학습 서비스, 경로 안내 타일 처리 서비스, 분석 서비스 등)

 

지도 표시

위에서 얘기했던 타일형태로, 확대 수준에 따라 타일들을 불러와서 보여준다.

최적화 방법중에 하나론 벡터 사용이 있는데,
네트워크를 통해 이미지를 전송하는 대신 경로와 다각형 등의 벡터 정보를 보내고 클라이언트는 해당 데이터로 지도를 그려내는 형태다.

이미지보다 월등한 압축률에 의해 네트워크 대역폭을 많이 아낄 수 있다.

 

그리고 매끄러운 지도 확대 경험이다.

기존 이미지를 이어 붙이는 형태에선, 확대 수준을 높이는 순간 이미지가 늘어지고 픽셀이 도드라져 보일 수 있는데,

직접 그리는 형태에선 클라이언트가 각 요소 크기를 적절하게 조정할 수 있어서 보다 매끄럽다.

 

경로 안내 서비스

경로 안내를 하기 위해 가장 먼저 해야할 것은

지오코딩 서비스로 주소 기반으로 위도/경도 쌍으로 바꿔주는 서비스이다.

 

해당 서비스로 출발지와 목적지 주소를 위도/경도 쌍으로 변환 후 다른 서비스 호출에 사용된다.

 

경로 계획 서비스는 현재 교통 상황과 도로 상태에 입각하여 이동시간 측면에서 최적화된 경로를 제안하는 역할을 담당한다.

 

최단 경로 서비스는 k개의 최단 경로를 반환하는 서비스이다.

출발지와 목적지의 위도/경도를 받고, 지오해시로 변환한 다음 출발지와 목적지의 경로 안내 타일을 얻는다.

출발지 타일에서 시작하여 그래프 자료 구조를 탐색해나간다.

필요한 주변 타일은 s3객체에서 가져옴. 같은 지역의 다른 확대 수준 타일로도 연결이 존재할 수 있음을 주의할 것.

 

예상 도착 시간 서비스(ETA)

경로 각각에 대한 소요 시간 추정치를 구하는 서비스.

기계 학습을 활용해 현재 교통상황 및 과거 이력에 근거하여 예상 도착 시간을 계산한다.

까다로운점은 미래의 시간대에 교통 상황이 어떻게 달라질지 예측해서 해야한다는 점.

 

순위 결정 서비스

경로 계획 서비스는 ETA 예상치를 뽑은 후 순위 결정 서비스에게 관련 정보를 모두 전달하여 사용자가 정의한 필터링 조건을 적용시키고 남은 경로를 소요 시간 순 정렬하여 최단 시간 경로 k개를 구한 다음 경로 안내 서비스에 결과를 반환한다.

 

중요 정보 갱신 서비스

해당 부류의 서비스는 카프카 위치 데이터 스트림을 구독하고 있다가 중요 데이터를 비동기적으로 업데이트하여 항상 최신으로 유지하는 역할을 담당.

교통 정보 데이터베이스, 경로 안내 타일등이 있음.

 

적응형 ETA와 경로 변경

해당 사항을 적용하려면, 아래 2가지를 확인해야한다.

 

현재 경로 안내를 받고 있는 사용자를 추적.

수백만 경로 가운데 교통 상황 변화에 영향을 받는 경로와 사용자를 효율적으로 가려낼 수 있어야함.

 

1) 교통 상황 악화 케이스

만약, 추적데이터로 특정 사용자가 안내 받은 경로를 그대로 db에 저장한다고 했을 시,

user1 : r_1,r_2,r_3,....r_k

user2 : r_4_r_6,r_7,...r_n

user3 : r_2, r_8, r_9,...r_m

 

형태이면 r_2를 찾으려면 유저 수 n * 경로의 평균 길이 m = n*m 데이터를 저장하게 되고 O(n*m) 시간복잡도가 나옴.

 

해당 속도를 더 높이는 방법으로는,

재귀를 통해 출발지와 목적지를 다 포함하는 가장 상위의 타일 한개만 저장하면 됨.

 

그러면 O(n)의 데이터만 저장하게 되고
타일 id의 prefix(확대수준 등)까지 index 처리를 하면 (공간 인덱스 - 트리구조)
색인 과정에서 O(log n)까지 감소 가능하다.

 

2) 교통 상황 개선 케이스

gps 기반의 해당 타일과 근처의 유저를 조회하여 처리하던가 ( 공간 인덱스 기반 O(log n) )

과거 추천받았던 경로를 다 저장해두고 ETA를 재계산해서 재추천하는 형태 ( O(log n) * 추천받았던 경로 개수 k )

 

전송 프로토콜

경로 안내 중에 경로의 상황이 변경될 수 있으므로, 양방향 통신이 많은 관계로 웹소켓이 좋다.

( 모바일 푸시 알림, 롱 폴링, 웹소켓, SSE 중에서 )