3장. 구글 맵 - 1편

1단계: 설계 범위

1) 기능 요구사항

지원하는 단말은 모바일, 스마트폰이다.

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

2) 비기능 요구사항

• 정확도: 사용자에게 잘못된 경로를 안내하면 안 된다.
• 부드러운 경로 표시: 경로 안내 용도의 지도는 부드럽게 표시되고 갱신되어야 한다.
• 데이터 및 배터리 사용량: 클라이언트는 최소한의 데이터와 배터리를 사용해야한다.
• 가용성 및 확장성

3) 기본 개념 및 용어

측위 시스템

세계는 축을 중심으로 회전하는 구인데, 측위 시스템은 구 표면 상의 위치를 표현하는 체계이다.

위경도 기반의 측위 시스템의 경우, 최상단에는 북근 최하단에는 남극이 있다.

 

위도(Latitude)는 주어진 위치가 얼마나 남쪽/북쪽인지를 나타낸다.

경도(Longitude)는 얼마나 동쪽/서쪽인지를 나타낸다.

 

3차원 위치의 2차원 변환

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

모든 투영법은 실제 지형의 가하학적 특성을 왜곡한다는 공통점을 갖는다.

 

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

 

지오코딩

주소를 지리적 측위 시스템의 좌표로 변환하는 프로세스이다.

예를 들어, 미국 주소 '1600 Amphitheatre Parkway, Mountain View, CA의 지오코딩 결과는 위도 37.423021, 경도 -122.083739 이다.

 

지오코딩을 수행하는 방법은 인터폴레이션(interpolcation)으로, GIS (Geographic Information System)와 같은 다양한 시스템이 제공하는 데이터를 결합한다는 뜻이다.

GIS는 도로망을 지리적 좌표 공간에 대응시키는 방법을 제공하는 여러 시스템 가운데 하나이다.

 

지오해싱

지도 위 특정 영역을 영문자와 숫자로 구성된 짧은 문자열에 대응시키는 인코딩 체계.

지오해싱은 2차원의 평면 공간으로 표현된 지리적 영역 위의 격자를 더 작은 격자로 재귀적으로 분할해 나간다. 격자는 정사각형일 수도 있고 사각형일 수 있다.

 

출처: https://guzene.tistory.com/337

지도표시

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

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

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

 

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

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

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

 

대부분의 경로 탐색 알고리즘의 성능은 주어진 그래프 크기에 민감하다.

좋은 성능을 보이려면 그래플르 관리 기능 단위로 분할할 필요가 있다.

 

지오해싱과 비슷한 분할 기술을 적용하여 세계를 작은 격자로 나누고, 각 격자 안의 도로망을 노드(교차로)와 선(도로)로 구성된 그래프 자료 구조로 변환한다.

각 격자는 경로 안내 타일이라고 부르고, 각 타일은 도로로 연결된 다른 타일에 대한 참조를 유지한다.

 

지도 타일은 PNG 이미지인 반면 경로 안내 타일은 도로 데이터로 이루어진 이진 파일(binary file)이다.

 

계층적 경로 안내 타일

지번 수준 정밀도 타일을 가지고 알고리즘을 동ㄹ리면 결과를 얻는데 많은 시간이 걸린다.

구체성 정도를 상,중,하로 구분하여 세 가지 종류의 경로 안내 타일을 준비한다.

상 타일의 경우, 크기가 아주 크고 이런 타일에는 지방도 데이터만 둔다.

중 타일의 경우, 더 넓은 지역을 커버하며 규모가 비교적 큰 관할구를 잇는 간선 도로 데이터만 둔다.

하 타일의 경우, 도시와 주를 연결하는 주요 고속도로 데이터만 둔다.

 

4) 개략적 규모 추정

저장소 사용량

아래와 같이 세 가지 종류의 데이터를 저장한다.

• 세계 지도
• 메타데이터: 각 지도 타일의 메타 데이터는 크기가 아주 작아서 무시해도 지장이 없을 정도.
• 서버 대역폭: 외부에서 받은 수 TB 용량의 도로 데이터를 보유하고 있음.

 

세계지도

확대수준 별로 지도 타일을 하나씩 두어야 한다.

타일 전부를 보관하는데 필요한 용량을 가늠하려면 최대로 확대하여 보는데 필요한 타일 개수를 따져보면 좋다.

 

세계 지도를 21번 확대하여 볼 수 잇으려면 4.4개의 타일이 필요하고, 한 장의 타일이 256 * 256 픽셀이라면 한 장당 100kb 저장공간이 필요하므로 440PB(4.4조 * 100KB) 공간이 필요하다.

(사람이 살지 않는 자연 타일은 최대한 압축 가능)

 

서버 대역폭

서버가 처리해야하는 요청은 크게 두 가지이다.

첫 번째: 경로 안내 요청으로, 클라이언트가 경로 안내 세션을 시작할 때 전송하는 메세지

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

 

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

• DAU: 10억
• 사용 시간: 주당 35분
• (35분 * 10억명) / 7 = 50억분

하루 3000억 건 요청(50억 * 60분)  = 3백만 QPS

 

하지만, 클라이언트가 매초 새로운 GPS 좌표를 보낼 필요가 없을 수도 있다.

GPS 위치 변경 내역을 모아두었다가 15초마다 한 번씩 서버로 보내도록 가정한다.

2단계: 개략적 설계안

1) 위치 서비스

사용자의 위치를 기록하는 역할을 담당

클라이언트가 t초마다(설정 가능한 값) 주기적으로 위치 전송을 하면 몇가지 좋은 점이 있다.

 

첫 번째, 데이터 스트림을 활용하여 시스템을 점차 개선할 수 있다.

실시간 교통 상황을 모니터링하는 용도로 활용할 수 있고, 새로 만들어진 도로나 폐쇄된 도로를 탐지할 수 있고, 사용자 행동 패턴을 분석하여 개인화된 경험을 제공할 수 있다.

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

 

위치 이력을 클라이언트에 버퍼링해 두었다가 일괄 요청(batch request)하면 전송 빈도를 줄일 수 있다.

구글 맵과 같은 시스템은 위치 갱신 요청 빈도를 줄여도 많은 쓰기 요청을 처리해야 한다. 따라서 카산드라 같은 데이터베이스가 필요하다. 또한 카프카 같은 스트림 처리 엔진을 활용하여 위치 데이터를 로깅해야 할 수도 있다.

HTTP를 keep-alive 옵션과 함께 사용하면 효율을 높일 수 있다.

 

2) 경로 안내 서비스

해당 컴포넌트는 A에서 B 지점으로 가는 합리적으로 빠른 경로를 찾아 주는 역할을 한다.

• 결과를 얻는데 드는 시간 지연은 어느 정도 감내할 수 있다.
• 계산된 경로는 최단 시간 경로일 필요는 없으나 정확도는 보장되어야 한다.
• 해당 요청에는 추발지와 목적지가 인자로 전달 된다.

 

3) 지도 표시

클라이언트가 지도 타일을 가지고 있는 것은 실용적인 방법이 아니다.

서버에서 가져오는 접근법이 바람직한데 몇 가지 시나리오를 생각해 볼 수 있다.

 

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

 

선택지 1

현재 클라이언트가 보는 지도의 확대 수준에 근거하여 필요한 지도 타일을 즉석에서 만드는 방법이다.

해당 방안은 몇 가지 문제가 있다.

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

선택지 2

확대 수준별로 미리 만들어 둔 지도 타일을 클라이언트에 전달하는 방법

• 미리 만들어 둔 정적 이미지는 CDN을 통해 서비스한다.
  (지도 타일이 담당하는 지리적 영역은 지오해싱 같은 분할법을 사용해 만든 고정된 사각형 격자로 표현되므로 정적)
• 해당 방법은 규모 확장이 용이하고 성능 측면에서 유리하다.
  (사용자에게 가장 가까운 POP(Poin of Presence)에서 파일을 서비스하기 때문)

클라이언트는 CDN에서 지도 타일을 가져올 URL을 어떻게 결정할까?

• 선택지 2 방법을 사용하기 때문에 미리 만들어 둔 것을 사용한다.
• 클라이언트의 위치 및 현재 지도 확대 수준을 입력으로 화면에 표시할 지도 타일에 대응 되는 지오해시는 아주 쉽게 계산할 수 있다.
  ex) https://cdn.map-provider.com/tiles/9q9hvbu.png
• 만약 맵 타일 인코딩 방식을 교체하면 많은 노력과 위험성이 크다.
  => 주어진 위도/경고 및 확대 수준을 타일 URL로 변환하는 알고리즘 구현을 별도 서비스에 두는 방법이 있다.