17장 - 구글 맵

1. 지원해야 하는 기능 정리#

• 10억 DAU
• 위치 갱신, 경로 안내, ETA 지도 표시 등에 초점 맞추기
• 수 TB의 가공되지 않은 도로 데이터 저장
• 교통 상황을 고려해 정확한 도착시간 계산
• 자동차 이외에도 다양한 이동수단 고려

1.1. 기능적 요구사항#

• 사용자 위치 갱신
• 경로 안내 서비스
• 지도 표시

1.2. 비기능적 요구사항#

• 정확도 : 잘못된 경로를 안내하면 안된다.
• 부드러운 경로 표시 : 지도 안내를 부드럽게 표시
• 데이터 및 배터리 사용량 : 가능한 최소한의 데이터와 배터리 사용
• 일반적으로 널리 통용되는 가용성/규모 확장성 요구사항을 만족

1.3. 지도101#

1.3.1. 측위 시스템#

• 세계는 축을 중심으로 회전하는 구다
• 측위 시스템은 구 표면 상의 위치를 표현하는 체계로, 위경도 기반의 시스템의 경우 최상단에는 북극, 최하단에는 남극이 있다.
• 이 시스템에서 위도는 주어진 위치가 얼마나 북/남쪽인지 나타내고, 경도는 동/서쪽인지 나타낸다.

1.3.2. 3차원 위치의 2차원 변환#

• 지도 투영법(도법) = 3차원의 구를 2차원의 평면에 대응 시키는 방법
• 다양한 도법이 존재하며 각각 장/단점을 가진다.
• 구글 맵은 메르카토르 도법을 조금 변경한 웹 메르카토르 도법을 사용한다.

1.3.3. 지오코딩#

• 주소를 지리적 측위 시스템의 좌표로 변환하는 프로세스
• 지오코딩 반대의 프로세스를 역 지오코딩이라 부름
• 수행하는 한 방법은 인터폴레이션이다.
• GIS는 도로망을 지리적 좌표 공간에 대응시키는 제공 방법 중 하나

1.3.4. 지오해싱#

• 지도 위 특정 영역을 영문자와 숫자로 구성된 짧은 문자열에 대응시키는 인코딩 체계
• 어떤 격자를 재귀적으로 분할한 결과로 생성된 더 작은 격자에는 0부터 3까지 번호를 부여함
• 지오해싱의 용도는 다양하나 본 설계안은 맵 타임 관리에 지오해싱을 적용함

1.3.5. 지도표시#

• 지도 렌더링은 가장 기본적으로 지도를 작은 타일로 쪼개서 표시하는 방법이 있다.
• 지도의 확대/축소에 따라 다양한 종류의 타일을 준비해야 한다.

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

• 대부분의 경로 탐색 알고리즘은 다익스트라 알고리즘이나 A* 알고리즘의 변종이다.
• 경로탐색 알고리즘은 교차로를 노드로, 도로는 노드를 잇는 엣지로 표현하여 그래프 자료구조를 가진다.
• 전 세계 도로망을 작은 단위로 분할하는 타일 기법과 유사하게 세계를 작은 격자로 나누고, 각 격자안 도로망을 노드와 선으로 구성된 그래프 자료로 변환한다.
• 도로망을 언제든 불러올 수 있는 경로 안내 타일로 분할해 놓으면 경로 탐색 알고리즘이 동작하는 데 필요한 메모리 요구량을 낮출 수 있고, 한번에 처리해야 하는 양이 줄어들어 성능도 좋아진다.

1.3.7. 계층적 경로 안내 타일#

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

  • 구체성에 따라 상 > 중 > 하로 두며 고속도로나 간선도로 등을 저장한다.

2. 청사진 그리기#

2.1. 위치 서비스#

• 사용자 위치 갱신을 너무 짧게 하면 서버에 부하가 생기고 비효율적이다.
• 클라이언트가 자신의 버퍼를 만들고 15초 정도마다 보내면 조금 더 효율적으로 보낼 수 있다.

2.2. 경로안내#

• 경로안내는 최단 시간을 계산해야 하기 때문에 약간의 레이턴시는 감내할 수 있다.

2.3. 지도표시#

• 지도 표시는 미리 쪼개둔 지도 데이터를 CDN에 캐싱해서 클라이언트에 전달하도록 한다.

  • 타일 단위로 쪼개는건 지오 해시를 통해서 나눠두는 것이다.
• 단일 서버 운용시엔 레이턴시가 너~무 길기 때문이다.
• 그리고 타일을 미리 쪼개두고 CDN을 쓰며 규모확장이 용이하다!
• 거기에 클라이언트 측에 캐시까지 쓴다면?

  • Wow 비용과 속도 모두 잡았다!
• 지오 해시는 계산이 쉬워서 클라이언트 측에서 계산 후 원하는 타일을 가져가면 된다.

  • 단, 서버 배포보다 클라 배포가 더 시간이 많이 걸려서 문제가 될 수 있다.
• 이 문제를 해결하기 위해 이런 계산만을 해주는 서비스를 독립적으로 분리하는 것이다. (클라가 위도 경도를 주면 계산 후 전달)

3. 실제 설계#

3.1. 데이터 모델#

• 경로 안내 타일은 일반적으로 인접 리스트 형태로 보관한다.

  • 그런데 해당 설계안의 타일데이터를 모두 담기엔 용량이 너무 큼
  • 가장 효율적 방법은 S3같은 객체 저장소에 파일을 보관/캐싱 하는 것
  • 지오해시 기준으로 분류해두면 위/경도가 주어졌을때 신속하게 찾을 수 있다.
• 카산드라를 통해서 사용자 위치정보를 저장한다.

  • 카산드라는 규모확장이 쉽다.
  • 사용자 위치정보는 다양하게(교통상황, 도로 데이터 갱신 등) 이용된다.
• 지오코딩 데이터베이스는 키/값 데이터베이스로 저장한다.
• 지도 이미지는 S3클라우드 저장소를 이용하고, CDN을 이용해 레이턴시를 줄인다.

3.2. 서비스#

• 위치 서비스는 키/값 저장소를 사용한다.

  • 쓰기 연산이 자주 발생하기 때문에 이에 탁월하다.
  • 데이터 일관성보다는 가용성이 더 중점을 둬야한다.
• 사용자 위치 데이터는 다양하게 사용된다.

3.3. 지도표시#

• 확대 수준별 타일을 제공한다.
• 최적화를 위해 벡터를 이용한다.

  • 일반 이미지에 비해 월등한 압축률 덕에 네트워크 대역폭을 아낄 수 있다.

3.4. 경로안내 서비스#

• 지오코딩 서비스를 통해 위도와 경도를 변환한다.
• 경로 계획 서비스를 통해서 교통상황/도로 상태에 입각해 최적화된 경로를 제안한다.
• 대략적으로 아래 프로세스로 진행

  • 위도 경도를 받아 지오해시로 변환
  • 출발지 타일에서 시작해 그래프로 탐색 시작
• ETA(예상 도착시간 서비스)는 교통상황과 경로를 기계학습해 시간을 도출한다.
• 어떤 경로를 우선시 할건지도 제공한다. (큰길, 유료도로 등)
• 경로 중 도로상황에 의해 새로운 경로를 안내하려할 때 자신의 목적지와 출발지를 모두 포함한 수준으로 타일을 확대해서 가지고 있다가 교통사고가 발생한 타일이 있는지만 확인하고 재계산한다.

  • 속도를 높일 수 있다.