•
구글 맵이란 웹 기반 지도 서비스로 위성 이미지, 거리 뷰, 실시간 교통 상황, 경로 계획 등 다양한 서비스를 제공하고 있다.
•
구글 맵은 일반적으로 사용자가 목적지와 경로를 찾을 수 있도록 도우며 현재 DAU는 대략 10억이다.
•
구글 맵은 엄청나게 복잡한 제품이므로, 설계에 앞서 어떤 기능에 초점을 맞추어야 하는지 확인해야 한다.
1단계: 문제 이해 및 설계 범위 확정
•
요구사항 가정
◦
10억 DAU
◦
주요 기능은 위치 갱신, 경로 안내, ETA, 지도 표시
◦
도로 데이터는 수 TB 수준의 가공되지 않은 데이터
◦
ETA 고려 시, 교통 상황을 고려
◦
이동 시, 도보, 대중교통 등 다양한 교통수단 고려
◦
경로 안내 시 다양한 경유지 선택 가능하도록
◦
사업장 위치 및 사진 등 다양한 정보 등의 부가적인 요소는 고려하지 않음
기능 요구사항
•
이번 장에서는 세 가지 주요 기능을 구현하는데 집중한다. 지원할 주 단말은 스마트폰이다.
◦
사용자 위치 갱신
◦
경로 안내 서비스(ETA 서비스 포함)
◦
지도 표시
비기능 요구사항 및 제약 사항
•
정확도 : 사용자에게 정확한 경로를 안내해야 한다.
•
부드러운 경로 표시 : 클라이언트를 통해 제공되는 경로 안내 용도의 지도는 화면에 부드럽게 표시되고 갱신되어야 한다.
•
데이터 및 배터리 사용량 : 클라이언트는 최소한의 데이터와 배터리를 사용해야 한다.
•
일반적으로 널리 통용되는 가용성 및 규모 확장성 요구사항을 만족해야 한다.
설계에 앞선 기본 개념 및 용어
•
지도 101
◦
측위 시스템
▪
측위 시스템은 구 표면 상의 위치를 표현하는 체계를 의미하는데, 위경도 기반 측위의 경우 최상단에는 북극, 최하단에는 남극이 있다.
◦
3차원 위치의 2차원 변환
▪
이는 지도 투영법 또는 도법이라 부른다.
▪
다양한 도법이 존재하며 각각 장단점이 존재한다. 하지만 모두 공통적으로 실제 지형의 기하학적 특성을 왜곡할 수 밖에 없다.
▪
구글 맵은 메르카토르 도법을 조금 변경한 웹 메르카르토 도법을 택하고 있다.
◦
지오코딩
▪
지오코딩은 주소를 지리적 측위 시스템의 좌표로 변환하는 프로세스다.
▪
지오코딩 결과를 반대로 주소로 변환하는 과정은 역지오코딩이라고 한다.
▪
지오코딩을 수행하는 방법 중 하나는 인터폴레이션으로 GIS와 같은 다양한 시스템이 제공하는 데이터를 결합한다는 뜻이다.
◦
지오해싱
▪
지도 위 특정 영역을 문자열에 대응시키는 인코딩 체계다.
•
지오해싱은 2차원의 평면 공간으로 표현된 지리적 영역 위의 격자를 더 작은 격자로 재귀적으로 분할해 나간다.
◦
지도 표시
▪
지도를 화면에 표시할 때 가장 기본이 되는 개념은 타일이다. 지도 전부를 한의 이미지로 표현하는 대신 쪼개어 타일로 표시하는 것이다.
◦
경로 안내 알고리즘을 위한 도로 데이터 처리
▪
대부분의 경로 탐색 알고리즘은 데익스트라나 A* 경로 탐색 알고리즘의 변형으로 그 중 최적인 하나를 결정하는 것은 너무 구체적이므로 다루지 않는다.
▪
중요한 것은 모든 경로 탐색 알고리즘이 교차로를 노드로 도로는 노드를 잇는 선으로 표현하는 그래프형 자료구조로 가정하고 푼다는 것이다.
▪
다만 이때, 경로가 여러 타일에 걸쳐있는 경우, 참조를 통해 접근해야 한다.
◦
계층적 경로 안내 타일
▪
경로 안내가 효과적으로 동작하려면 여러 구체성 수준을 갖춘 도로 데이터가 필요하다.
▪
도로가 세밀하게 퍼져있는 경우, 상, 순환도로 등 큰 관할구를 잇는 도로는 중, 다른 도로와 도로를 잇는 고속도로는 하 등으로 체계화시켜 관리한다.
개략적 규모 추정
•
저장소 사용량
◦
세계 지도
▪
지원하는 확대 수준 별로 지도 타일을 구성해두어야 한다. 그래야 더 효율적으로 데이터를 제공해줄 수 있다.
▪
고수준의 확대 수준을 가질수록 각 타일을 4분할하여 접근한다고 가정하면 대략 21개의 확대 수준을 가지는 경우, 4^0부터 4^21까지의 총합 * 각 타일별 이미지 용량 크기 수준의 데이터 저장소가 필요할 것이다.
▪
그 외의 사막, 바다 등 조회가 자주 일어나지 않아 압축이 가능한 데이터를 압축한다고 가정하면 용량을 절감할 수 있을 것이다.
•
서버 대역폭
◦
먼저 서버가 처리하는 요청은 크게 두 가지다. 첫 번째는 경로 요청이고 사용자 위치 갱신 요청이다.
▪
경로 안내 요청의 경우, DAU 10억, 가정한 경로 안내 기능 평균 사용 시간인 주당 35분을 계산해보면 하루에 대략 50억분이라는 계산이 나오고 이를 60으로 나누면 대략 1초당 300만 회라는 QPS 수치가 나온다.
▪
사용자 이동 속도나 그외 정확도 저하를 감수한다면 갱신 기간을 늘려 QPS를 더 줄일 수 있다.
2단계 : 개략적 설계안 제시 및 동의 구하기
개략적 설계안
•
위치 서비스
◦
본 설계안은 t초마다 자기 위치를 전송한다고 가정하며, 이때의 t 값은 설정 가능한 값이다.
◦
이렇게 주기적으로 위치 정보를 전송하면 몇 가지 좋은 점이 있다.
▪
첫 번째는 해당 데이터 스트림을 활용하여 시스템을 점차 개선할 수 있다.
▪
두 번째는 클라이언트가 보내는 위치 정보가 거의 실시간 정보에 가까우므로 ETA를 더 정확하게 산출할 수 있다.
◦
이렇게 최적화를 시켜도 여전히 구글 맵과 같은 서비스는 많은 쓰기 요청을 처리하므로 데이터베이스론 쓰기 요청에 적합한 카산드라 같은 데이터베이스가 적절할 것이다.
•
경로 안내 서비스
◦
이 서비스는 A에서 B 지점으로 가는 적절한 경로를 찾아 주는 역할을 담당한다.
◦
경로 재탐색이나 교통 상황 변화 고려 등은 상세 설계를 거치며 구체적으로 잡아나가는 것이 낫다.
•
지도 표시
◦
지도 표시를 위해 필요한 타일 수십 PB를 클라이언트에게 가지고 있도록 하는 것은 바람직하지 못하다.
◦
그렇다면 클라이언트는 어떻게 서버로부터 타일을 받아올 수 있을까?
◦
미리 타일들을 만들어두고 CDN으로 제공하는 것이 바람직할 수 있다.
▪
일부 데이터를 클라이언트 내부에 캐시해두면 더 쾌적한 성능을 제공할 수 있을 것이다.
3단계: 상세 설계
데이터 모델
•
경로 안내 타일
◦
이름, 관할구, 위도, 경도 등의 도로 부속 정보 메타데이터들은 그래프 자료 구조 형태로 가공되지 않으므로 경로 안내 타일 처리 서비스를 사용해 경로 안내 타일로 변환해야 한다.
◦
이렇게 경로 안내 타일을 가공할 땐, 상, 중, 하로 만들어 도로망 데이터를 점진적으로 소비할 수 있도록 한다.
◦
이렇게 만들어진 타일은 S3에 저장해두고 그 파일을 이용할 경로 안내 서비스에서 캐싱하여 사용한다.
•
사용자 위치 데이터
◦
사용자의 위치 데이터를 저장하려면 엄청난 쓰기 연산을 지원하며 수평적 규모 확장에 용이해야 하므로 카산드라 데이터베이스가 적절한 선택이 되어줄 수 있다.
◦
지오코딩 데이터베이스
▪
주소는 경로 계획 서비스에 전달되기 전에, 위도/경도 쌍으로 변환되어야 한다.
•
서비스
◦
위치 서비스
▪
사용자 위치 데이터 저장에는 키-값 저장소를 사용하며 역시 쓰기 연산 지원에 탁월한 데이터베이스를 선택한다.
◦
지도 표시
▪
WebGL 기술을 채택하면 네트워크를 통해 이미지를 전송하는 대신 경로와 다각형 등의 벡터 정보를 보내어 지도를 그리게끔하여 압축률에 따른 네트워크 대역폭 절감 효과를 볼 수 있다.
▪
또 다른 장점이 될 수 있는 것은 매끄러운 확대를 제공한 유저 경험 향상이다.
◦
경로 안내 서비스
▪
지오코딩 서비스
▪
경로 계획 서비스
•
현재 교통 상황과 도로 상태에 입각하여 이동 시간 측면에서 최적화된 경로를 제안하는 역할을 담당한다.
▪
최단 경로 서비스
•
출발지와 목적지 위도/경도를 입력으로 받아 k개의 최단 경로를 반환하는 서비스다.
•
최당 경로 서비스는 객체 저장소에 저장된 경로 안태 타일에 대해 A* 경로 탐색 알고리즘의 한 형태로 실행한다.
◦
입력으로 출발지와 목적지의 위도, 경로를 받아, 지오 해시로 변환한다음 출발지와 목적지 경로 안내 타일을 획득한다.
◦
출발지 타일에서 시작하여 그래프 자료 구조를 탐색해 나간다. 탐색 범위 확장에 필요한 타일은 객체 저장소에서 획득한다.
▪
예상 도착 시간 서비스
•
최단 경로 목록을 수신하면 예상 도착 시간 서비스를 호출하여 경로 별, 소요 시간 추정치를 구한다.
▪
순위 결정 서비스
•
사용자가 정의한 필터링 조건(유료 도료 제외, 고속도로 제외 등)을 적용하여 남은 경로들을 소요 시간 별로 정렬하여 제공한다.
▪
중요 정보 갱신 서비스들
•
이 부류의 기능들은 카프카 위치 데이터 스트림을 구독하고 있다가 중요 데이터를 비동기적으로 업데이트하여 그 상태를 항상 최신으로 유지하는 역할을 담당한다.
▪
적응형 ETA와 경로 변경
•
이 문제를 해결하려면 현재 경로 안내를 받고 있는 모든 사용자를 추적하면서 교통 상황이 달라지는 이벤트가 발생할 때마다 각 사용자의 ETA를 변경해주어야 한다.
•
그렇다면 현재 경로 안내를 받고 있는 사용자는 어떻게 추적할까? 그리고 수백만 경로 가운데 교통 상황 변화에 영향을 받는 경로와 사용자를 효율적으로 찾아낼 방법은 무엇일까?
•
너무 구체적이라 다루지 않겠다..
4단계: 마무리
•
구글 맵은 위치 갱신, ETA, 경로 계획, 지도 표시 등의 핵심 기능을 지원한다.
•
이 시스템의 확장에 관심이 있다면 추가적으로 기업 고객 대상, 중간 경유지 설정 기능을 제공하는 것을 고려해보면 좋을 것이다.
