3장. 구글 맵 - 2편
3단계: 상세 설계
1. 데이터모델
1) 경로 안내 타일
도로 데이터는 외부 사업자나 기관이 제공한 것으로, 방대한 양의 도로 및 메타데이터로 구성된다.
가공되지 않은 데이터이므로, 경로 안내 알고리즘의 입력으로 활용할 수 없다.
경로 안내 타일 처리 서비스라 불리는 오프라인 데이터 가공 파이프라인을 주기적으로 실행하여 경로 안내 타일로 변환한다.
경로 안내 타일 처리 서비스는 가공 결과로 만든 타일을 어디에 저장해야 할까?
=> 일반적으로 그래프 데이터는 메모리에 인접 리스트 형태로 보관한다.
데이터 양이 방대하기 때문에 비용 등의 문제로 S3 같은 객체 저장소에 파일을 보관하고 파일을 이용할 경로 안내 서비스에 적극적으로 캐싱하는 방법이 효율적이다.
타일을 객체 저장소에 보관할 때는 지오해시 기준으로 분류해 두는 것이 좋다.
2) 사용자 위치 데이터
사용자 위치 데이터는 도로데이터 및 경로 안내 타일을 갱신하는데 이용되며, 실시간 교통 상황 데이터나 교통 상황 이력 데이터베이스를 구축하는데 활용된다.
사용자 위치 데이터를 저장하려면 엄청난 양의 쓰기 연산을 잘 처리할 수 있으면서 수평적 규모 확장이 가능한 데이터베이스가 필요하다.
3) 지오코딩 데이터
주소를 위도/경도 쌍으로 변환하는 정보를 보관한다.
레디스처럼 빠른 읽기 연산을 제공하는 키-값 저장소가 이 용도에 적당한데, 읽기 연산은 빈번한 반면 쓰기 연산은 드물게 발생하기 때문이다.
4) 미리 계산해 둔 지도 이미지
단말이 특정 영역의 지도를 요청하면 인근 도로 정보를 취합하여 모든 도로 및 관련 상세 정보가 표함된 이미지를 만들어 내야 한다.
계산 자원을 많이 사용할 뿐 아니라 같은 이미지를 중복 요청하는 경우가 많으므로 결과를 캐시해 두는 전략을 쓰는게 좋다.
2. 서비스
1) 위치서비스
사용자의 위치 정보가 이용되는 방식에 초첨을 맞추어 설계한다.
사용자의 위치는 계삭 변화하며 일단 변경되고 나면 이전 정보는 바로 무용해진다.
즉, 데이터 일관성보다는 가용성이 더 중요하하고 CAP 정리에 다르면 일관성, 가용성, 분할 내성 모두를 만족시킬 방법이 없다.
가용성과 분할 내성 두 가지를 만족시키는 데이터베이스인 카산드라이다.
높은 가용성을 보장하면서도 막대한 규모의 연산을 감당할 수 있도록 해준다.
데이터베이스 키로는 (user_id, timestamp)의 조합을 사용하며, 해당 키에 매달리는 값으로는 위도/경도 쌍을 저장한다.
user_id는 파티션 키이며 timestamp는 클러스터링 키로 활용한다.
user_id를 파티션 키로 사용하는 것은 특정 사용자의 최근 위치를 신속히 읽어 내기 위해서다.
| key(user_id) | timestamp | lat | long | user_mode | navigation_mode |
| 51 | 132053000 | 21.9 | 89.8 | active | driving |
사용자 위치는 쓰임새가 다양한 중요한 데이터이다.
새로 개설되었거나 폐쇄된 도로를 감지할 수 있고, 지도 데이터의 정확성을 점차 개선, 실시간 교통 현황을 파악하는 입력이 될 수 있다.
그리고, 이러한 지원을 하기위해서 사용자 위치를 데이터베이스에 기록하는 것과 별도로 메세지 큐에 로깅한다.
2) 지도표시
미리 만들어 놓는 방법과 지도 표시 최적화 기법을 살펴본다.
지도 타일 사전 계산
사용자가 보는 지도 크기나 확대 수준에 맞는 세부사항을 보여주기 위해서는 확대 수준별 지도 타일을 미리 만들어 둘 필요가 있다.
구글 맵은 21단계로 지도를 확대할 수 있고 본 설계안도 마찬가지다.
확대 수준 0은 세계 전부를 256 x 256 픽셀짜리 타일 하나로 표현한다.
확대 수준 1에 필요한 타일은 2 x 2장으로, 전부를 합친 해상도 512 x 512 픽셀이다.
확대 수준 2에 필요한 타일은 4 x 4 장으로, 전부를 합친 해상도는 1024 x 1025 픽셀이다.
확대 수준을 1단계 늘릴 때마다 해당 수준 전부를 합친 해상도는 그 이전 수준 대비 4배씩 늘어난다.
늘어나는 해상도 덕에 사용자에게 더 상세한 정보를 제공할 수 있다.
최적화: 벡터 사용
네트워크를 통해 이미지를 전송하는 대신 경로와 다각형 등의 벡터 정보를 보내는 것이다.
클라이언트는 수신된 경로와 다각형 정보를 통해 지도를 그려내면 된다.
벡터 타일의 장점으로 이미지에 비해 월등한 압축률과 매끄러운 지도 확대 경험이다.
네트워크 대역폭을 아낄 수 있으며, 벡터화 된 이미지를 사용하면 클라이언트는 요소 크기를 적절하게 조정할 수 있어 매끄러운 확대 경험을 제공할 수 있다.
3) 경로 안내
지오코딩 서비스
- 주소를 위도와 경도로 쌍으로 바꿔주는 서비스가 필요하다.
- 장소 이름으로 나타낸 주소도 있을 수 있고 지번 형태로 나타낸 주소도 있을 수 있다.
- 경로 안내 서비스는 해당 서비스를 호출하여 출발지와 목적지 주소를 위도/경도 쌍으로 변환한 뒤 추후 다른 서비스를 호출에 이용한다.
경로 계획 서비스
- 현재 교통 상황과 도로 상태에 입각하여 이동 시간 측면에서 최적화된 경로를 제안하는 역할을 담당한다.
최단 경로 서비스
- 출발지와 목적지 위도/경도를 입력으로 받아 k개 최단 경로를 반환하는 서비스다.
- 도로 구조에만 의존하여 계산을 수행한다.
(교통이나 도로 상황은 고려하지 않는다.)
예상 도착 시간 서비스
- 최단 경로 목록을 수신하면 예상 도착 시간 서비스를 호출하여 그 경로 각각에 대한 소요 시간 추정치를 구한다.
- 기계 학습을 활용해 현재 교통 상황 및 과거 이력에 근거하여 예상 도착 시간을 계산한다.
순위 결정 서비스
- ETA(예상도착서비스) 예상치를 구하고 나면 순위 결정 서비스에 관련 정보를 모두 전달하여 사용자가 정의한 필터링 조건을 적용한다.
- 유료 도로 제외, 고속도로 제외 등이 필터링 조건의 사례이다.
- 필터링이 끝나고 남은 경로를 요소 시간 순으로 정렬하여 최단 시간 경로 K개를 구한 다음 경로 안내 서비스에 결과를 반환한다.
중요 정보 갱신 서비스들
- 카프카 위치 데이터 스트림을 구독하고 있다가 중요 데이터를 비동기적으로 업데이트하여 그 상태를 항상 최신으로 유지하는 역할을 담당한다.
- 실시간 교통 정보 데이터베이스나 경로 안내 타일 등이 사례이다.
적응형 ETA와 경로 변경
- 현 설계안에서는 ETA와 경로 변경을 허용하지 않는다.
- 해당 문제를 해결하려면 서버는 현재 경로 안내를 받고 있는 모든 사용자를 추적하면서 교통 상황이 달라질 때마다 각 사용자의 ETA를 변경해주어야 한다.
아래 r_2에서 교통사고가 발생하면 어떤 사용자가 영향을 받는지 알아내기 위해 레코들 전수조사해야 한다.
레코드 수가 n이고 안내되는 경로의 평균 길이가 m이라고 하면 시간 복잡도는 O(n * m)이다.
user_1: r_1, r_2, r_3, ... , r_k
user_2: r_4, r_6, r_9, ... , r_n
user_3: r_2, r_8, r_9, ... , r_m
...
user_n: r_2, r_10, r_21, ... , r_l
다른 접근법으로 경로 안내를 받는 사용자 각각의 형재 경로 안내 타일, 그 타일을 포함하는 상위 타일, 그 상위 타일의 상위 타일을 출발지와 목적지가 모두 포함된 타일을 찾을 때까지 재귀적으로 더하여 보관한다.
이렇게 하면, 어떤 타일의 교통 상황이 변했을 떄 경로 안내 ETA가 달라지는 사요잦는, 해당 사용자의 데이터베이스 레코드 마지막 타일에 그 타일이 속하는 사용자이다.
검색 시간 복잡도가 O(n)으로 줄어들어 조금 더 효율적이다.
전송 프로토콜
데이터를 모바일 클라이언트에 전송할 안정적인 방법이 필요하다.
- 모바일 푸시알림은 메세지 크기가 제한적으로 바람직하지 않다.
- 웹소켓은 서버에 주는 부담이 크지 않아서 일반적으로 롱 풀링보다 좋은 방법이다.
=> 양방향 통신을 지원하기 때문에, 패키지나 상품이 목적지에 가까워졌을 때 실시간 양방향 통신이 필요한 경우도 있다.