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(예상 도착시간 서비스)는 교통상황과 경로를 기계학습해 시간을 도출한다.
•
어떤 경로를 우선시 할건지도 제공한다. (큰길, 유료도로 등)
•
경로 중 도로상황에 의해 새로운 경로를 안내하려할 때 자신의 목적지와 출발지를 모두 포함한 수준으로 타일을 확대해서 가지고 있다가 교통사고가 발생한 타일이 있는지만 확인하고 재계산한다.
◦
속도를 높일 수 있다.
