3장 - 구글 맵

책을 읽고 중요한 부분을 기록하고, 이해가 부족했던 부분을 탐구합니다.
예상 독자는 같은 책의 같은 내용을 읽은 분들로, 편의상 상세 내용은 생략합니다.

2021년 3월 기준 구글 맵의 DAU 는 10억 명이라고 합니다. 이 장에서는 구글 맵의 다양한 기능 중 다음 세가지 기능에 집중하여 설계합니다.

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

문제 이해 및 설계 범위 확정

지오코딩

지오코딩은 주소를 지리적 측위 시스템의 좌표로 변환하는 프로세스입니다. 1600 Amphitheatre Parkway, Mountain View, CA 의 지오코딩 결과는 (위도 37.423021, 경도 -122.083739)가 되는 식이죠.

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

대부분의 경로 탐색 알고리즘은 데이크스트라 알고리즘이나 A* 경로 탐색 알고리즘의 변종이라고 합니다. 그 가운데 최적인 하나를 정하는 것은 어려운 문제로, 책에서 다루지 않았습니다.

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

전 세계 도로망을 하나의 그래프로 표현하는건 메모리도 많이 필요하고 탐색 성능도 만족스럽지 않을 것입니다. 그래서 이를 타일 기반으로 분할합니다. 지오해싱과 비슷한 분할 기순을 적용하여 세계를 작은 격자로 나누고, 각 격자 안의 도로망을 노드와 간선으로 구성된 그래프 자료 구조로 변환합니다. 이때 각 격자는 경로 안내 타일 (routing tile) 이라고 부르며 각 타일은 다른 타일에 대한 참조(reference)를 유지합니다.

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

계층적 경로 안내 타일

국토 종단 여행을 위한 경로 탐색에 지번 수준 정밀도는 필요하지 않습니다. 그렇기 때문에 처음부터 각각 다른 정밀도의 경로 안내 타일을 준비해야 하고, 서로 다른 정밀도 타일로 연결되는 선을 추가해야 합니다. 즉, 지방도A 에서 고속도로 F로 진입하는 경우 다른 정밀도를 가진 타일끼리의 연결선이 존재해야 하는 것이죠.

개략적 규모 측정

지도를 전세계 범위부터, 적당한 거리의 범위까지 확대 축소하여 볼 수 있어햐 할 것입니다. 그 거리의 범위가 어느정도인지 책에 나오진 않았지만, 21번 확대 하여 볼 수있는 수준이 적당하다고 판단한 것 같습니다.

지도를 확대할 때 마다 하나의 타일을 네 장으로 펼친다고 가정했을 때, 21번 확대할 경우 4의 21승으로 약 4.4조개의 타일이 필요하다는 계산 결과가 나옵니다. 각 하나의 타일이 256*256 픽셀 압축 PNG 파일이라고 보면, 한 개당 100KB 의 저장공간이 필요하므로 최대 확대시 필요 타일을 전부 저장하는데는 총 4.4조 * 100KB, 440PB 만큼의 저장 공간이 필요해집니다.

하지만, 지구 표면 가운데 90%는 인간이 살지 않는 자연 그대로의 바다, 사막, 호수, 산간 지역입니다. 보수적으로 보아도 80% ~ 90% 가량의 저장 용량을 절감할 수 있으므로, 저장 공간 요구량은 44PB ~ 88PB 정도로 줄어들 것입니다. 어림하여 50PB 로 잡고 넘어갑니다.

현재는 21번째 확대된 타일말 계산한 것이므로, 1번째 (1장) 부터 20번 확대되었을 때의 타일까지 모두를 더해주어야 합니다. 확대 수준이 1 떨어질 때마다 필요한 타읠 수는 1/4 로 줄어들기 때문에, 이를 계산하면 50 + 50/4 + 50/16 + 50/64 + ... =~ 67PB 정도가 된다고 합니다. 이는 개략적인 추정치입니다. 다만, 확대 수준으로 지도를 표시하기 위해 대략 100PB 가 소요된다는 정도를 알고 넘어갈 수 있을 것 같습니다.

서버 대역폭

경로 안내 요청을 처리하기 위한 서버 대역폭을 분석해 봅시다.

DAU는 10억, 주당 35분 사용한다고 가정하였을 때 주당 350억분, 하루에 50억 분. 초로 변경하면 3000억. 3000억을 하루를 초로 변환한 값을 어림잡아 나누면, 3000억/10^5 = 3백만이 됩니다.

다만 이는 GPS 좌표를 매 초 서버로 전송한다 가정한 것이고, 그렇게 업데이트를 자주할 필요가 없기 때문에 이를 15초 주기로 보내도록 설정할 수 있을 것입니다. 

그렇게 되면, 3백만 / 15 = 20만, 즉 QPS 는 20만이 됩니다.

최대 QPS 는 평균치의 다섯배, 1백만이라고 가정할 수 있습니다.

개략적 설계안 제시

위치 서비스

본 기본 설계안은 클라이언트가 t초마다 자기 위치를 전송한다고 가정합니다. 이렇게 주기적으로 위치 정보를 전송 하면 좋은 점이, 해당 데이터 스트림을  활용하여 시스템을 점차 개선할 수 있다는 점입니다.

실시간 교통 상황 모니터링, 새로 만들어지거나 폐쇄된 도로 탐지, 사용자 행태 분석을 통한 개인화된 경험 제공에 활용될 수 있죠.

다만, 사용자 위치가 바뀔 때 마다 그 즉시 서버로 전송하는 것은 비효율 적이고, 클라이언트에 버퍼링 후 일괄 요청하는 방법을 떠올려 볼 수 있습니다.

그럼에도, 구글 맵과 같은 시스템은 여전히 엄청난 트래픽이 들어올 것으로 예상됩니다. 따라서 아주 높은 쓰기 요청 빈도에 최적화 되어 있고 규모 확장이 용이한 카산드라 같은 데이터베이스가 필요하죠.

또한, 카프카와 같은 스트림 처리 엔징르 통해 데이터를 로깅해야 할 수 있습니다. 자세한 내용은 상세설계에서 고민해 볼 수 있을 것 같습니다.

지도 표시

사용자가 지도를 확대 또는 이동시켜 주변을 탐색하는 경우, 경로 안내가 진행되며 사용자의 위치가 현재 지도 타일을 벗어나 인접한 타일로  이동하는 경우에 클라이언트는 새로운 지도 타일을 요청할 것입니다.

이를 동적으로 생성하여 돌려주는게 가능은 하겠지만, 서버 클러스터에 심각한 부하가 걸리고 캐시를 활용하기 어렵습니다. 

따라서, 확대 수준별로 미리 만들어 둔 지도 타일을 클라이언트에게 전달하기만 하는 방법이 낫습니다. 클라이언트 요청으로 이의 확대 수준에 근거하여 필요한 지도 타일 집합을 결정하고, 그 각 위치를 지오해시 URL로 변환하여 돌려줍니다.

이렇게 만들어둔 정적 이미지는 CDN을 통해 서비스 할 수 있습니다.

CDN은 요청받은 타일이 서비스된적 없는 경우 원본 서버에서 이를 가져오고 그 사본을 캐시에 보관합니다. 그 뒤의 요청은 캐시에서 빠르게 꺼내서 ㄷ로려줄 수 있는 것이죠.

이는 규모 확장 및 성능 측면에서도 유리합니다. 사용자에게 가장 가까운 POP (Point of Presence) 에서 파일을 서비스하기 때문이죠. 

데이터 사용량을 한번 계산해 봅시다.

사용자가 30km/h 로 이동 중이며, 한 이미지가 200m * 200m 영역을 표현하도록 확대하여 지도를 표시하고 있는 상황입니다. 1km * 1km 영역을 표현하려면 25장의 이미지가 필요하며, 각 100KB 로 가정했으므로 2.5MB 가 됩니다. 30km/h 로 달린다고 하였으니 한시간에 75MB 의 데이터가 소진되며, 이는 분당 1.25MB 에 해당합니다.

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

앞서 50억 분 가량의 경로 안내를 처리한다고 했으므로, 50억 X 1.25MB 는 6.25PB, 즉 하루에 6.26PB 가 처리됩니다. 그러므로 초당 전송해야 하는 지도 데이터의 양은 62,500 MB 가 됩니다. (6.25PB/10^5/하루). 

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

상세 설계

이 설계안이 다루는 시스템은 네 가지 데이터를 취급합니다.

1. 경로 안내 타일
2. 사용자 위치
3. 지오코딩 데이터
4. 미리 계산해 둔 지도 타일 데이터

경로 안내 타일

경로 안내 타일은 뭘로 만드는 걸까요? 외부 사업자나 기관이 제공한 로우한 도로 데이터를 활용해서 만들어야 합니다. 이는 수 테라바이트에 달하는 방대한 양일 것으로 예상됩니다.

그러므로 경로 안내 타일 처리 서비스를 통하여 오프라인 데이터 가공 파이프라인을 주기적으로 실행하여 경로 안내 타일로 변환해야 할 것입니다.

해상도 별로 세 벌을 만들고, 각 타일에 그래프와 노드 등이 포함될 것입니다.

그렇다면 이 결과는 어디다 보관해야 할까요? 그래프 데이터는 메모리에 인접 리스트 (adjacency list) 형태로 보관하는 것이 일반적입니다. 하지만 이 설계안이 다루는 데이터는 양이 너무 많기 때문에 다른 방법이 필요합니다.

그래프의 노드와 선을 데이터베이스 레코드로 저장해 볼 수 있겠지만, 비용이 많이들고 따로 데이터베이스가 제공하는 다른 기능이 필요 없다는 것도 문제입니다.

가장 효율적인 방법은 S3 같은 객체  저장소에 파일을 보관하고 이를 경로 안내 서비스에서 적극적으로 캐싱하는 형태일 것 같습니다. 즉, 인접 리스트를 이진 파일(binaray file) 형태로 직렬화 하여 보관하는 것이죠. 이를 보관할 때 지오해시 기준으로 분류해두면 위도와 경도가 주어졌을 때 신속하게 타일을 찾을 수 있을 것입니다.

사용자 위치 데이터

사용자 위치 데이터를 저장하려면 엄청난 양의 쓰기 연산을 감당할 수 있어야 할 것입니다. 따라서 카산드라를 고려해 볼 필요가 있을 것 같습니다.

레코드는 다음과 같은 형태입니다.

user_id, timestamp, user_mode, driving_mode, location 

지오코딩 데이터베이스

이 데이터베이스에는 주소를 위도/경도 쌍으로 변환하는 정보를 보관할 수 있습니다. 읽기 연산은 빈번하지만 쓰기 연산은 드물게 발생하기 때문에, 레디스를 활용하여 이를 최적화 할 수 있을 것입니다.

미리 만들어둔 지도 이미지

특정 영역의 지도를 요청하면 인근 도로 정보를 취합하여 모든 도로 및 관련 상세 정보가 포함된 이미지를 만들어 내야 할 수 있습니다. 중복 요청하는 경우가 많기 때문에 한번만 계산하고 그 결과는 캐시해 두는 전략을 쓰는 것이 좋습니다. 이미지는 지도표시에 사용하는 확대 수준별로 미리 만들어 두고 CDN을 통해 전송하는 것이죠. CDN 원본 서버로는 아마존 S3 같은 클라우드 저장소를 활용할 수 있습니다.

위치서비스

초당 백만 건의 위치 정보 업데이트가 발생하기 때문에 쓰기 연산 지원에 탁월한 데이터베이스가 필요합니다. 또한, CAP 정리에 따르면 일관성, 가용성, 분할 내성 중 한가지는 포기해야 하기 때문에 그 중 가용성과 분할 내성을 만족시키는 데 집중하는게 좋을 것 같습니다. (위치 정보가 조금 다르게 읽힌다고 크게 문제가 되진 않을 것 같기 때문?)

이러한 요구사항에 가장 적합한 데이터 베이스는 카산드라입니다. 높은 가용성을 보장하면서도 막대한 규모의 연산을 감당할 수 있도록 해줍니다.

카산드라에 대해서 더 공부를 해보아야 겠지만, 데이터 베이스 키로는 (user_id, timestamp) 의 조합을 사용하며, 매달리는 값으로 위도/경도 쌍을 저장합니다. 이 때 user_id 는 파티션 키, timestamp 는 클러스터링 키로 활용하게 되면, user_id 로 특정 사용자으 최근 위치를 신속히 읽어 내기 위함이며, 같은 파티션 키를 갖는 데이터는 클러스터링 키 값에 의해 정렬되기 때문에 클러스터링 키를 통해 특정 기간 내 위치도 효율적으로 읽어낼 수 있게 됩니다.

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

사용자 위치 데이터는 쓰임새가 다양합니다. 새로 개설 및 폐쇄된 도로를 감지할 수 있고, 지도 데이터의 정확성을 점차 개선하는데 활용할 수도 있고, 실시간 교통 현황을 파악하는 입력이 될 수 있습니다.

이 여러가지 용례를 만족하기 위해 카프카와 같은 메세지 큐를 활용할 수 있습니다.

개별 서비스는 카프카를 통해 전달되는 사용자 위치 데이터 스트림을 각자 용도에 맞게 활용할 수 있습니다.

경로 안내 서비스

경로 안내 서비스의 설계도를 살펴보겠습니다.

순차적으로 살펴보겠습니다.

먼저, 경로 안내 서비스가 지오코딩 서비스를 호출하여 주소를 위도/경도 쌍으로 변환해 올 것입니다. 이후 경로 계획 서비스 가 다른 서비스들과 통신하여 결과를 만들어 냅니다.

먼저, 최단 경로 서비스 에 출발지와 목적지의 위도/경도 쌍을 전송하여 k개의 최단 경로를 받아옵니다. 내부적으로는 A* 경로 탐색과 같은 알고리즘이 실행되고 경로 안내 타일이 추가되는 형태로 탐색 과정이 반복됩니다.

경로계획 서비스가 최단 경로 서비스로부터 최단 경로 목록을 수신하면 이를 가지고 예상 도착시간 서비스를 호출합니다. 이제 그 경로 각각에 대한 소요 시간 추정치를 구하는 것이죠. 내부적으로는 기계 학습을 활용해 현재 교통 상황 및 과거 이력에 근거한 예상 도착 시간을 각각 내놓을 것입니다. 

각 경로에 대한 ETA, 예상 도착시간을 구하고 나면 순위 결정 서비스가 호출되어 사용자가 정의한 필터링 조건(유료 도로 제외, 고속도로 제외 등)을 적용합니다. 필터링이 끝나고 남은 경로는 소요 시간 순으로 정렬하여 경로계획 서비스에게 반환합니다.

마무리

이번 장에선 위치 갱신, ETA, 경로 계획, 지도 표시 등의 핵심 기능을 지원하는 단순화된 구글 맵 어플리케이션을 설계하였습니다. 이 시스템의 확장에 관심이 있다면 경유지 기능을 제공하는 것을 고려해 보는 것도 좋을 것 같습니다.

참고문헌

[1] Developing — Google Maps: https://medium.com/@sidgangs99/developing-google-maps-3c3320a365d