Design Map Service

요구사항

• 위치 갱신 / 경로 안내 / ETA(예상 도착 시간) / 지도 표시 기능 제공

• 수 TB 수준의 가공되지 않은 도로 데이터

• 다양한 이동 방법 지원 안내(도보 / 대중교통 / 차량)

• 현재 교통 상황 고려 필요

기능 목록

위의 요구사항을 충족 시키기 위한 기능 목록은 다음과 같다.

• 사용자 위치 갱신

• 경로 안내 서비스(ETA 포함)

• 지도 표시

개략적 규모 추정

DAU 10억 명, 경로 안내 기능 주당 35분 사용이라고 가정했을 때, 처리해야할 트래픽은 다음과 같다.

• 하루 사용량: 10억 * 35분 / 7일 = 50억 분

• 클라이언트 GPS 갱신 주기: 15초(매초 GPS를 갱신할 필요 없이, 변경 내역을 모아두었다가 15초마다 전송한다고 가정)

• QPS: 50억 * 60초 / 15초 / 86,400초(하루) = 약 230,000QPS

• 최대 QPS: 230,000 * 5 = 1,150,000QPS(5배로 가정)

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

대부분의 경로 탐색 알고리즘은 다음과 같은 특징을 가진다.

• 데이크스트라 알고리즘이나 A* 알고리즘의 변종

• 두 알고리즘을 포함한 모든 경로 탐색 알고리즘은 노드와 엣지로 이루어진 그래프 자료 구조 사용

전 세계 도로망을 하나의 그래프로 표현하게 되면, 메모리 문제도 발생하고, 탐색 성능도 떨어지기 때문에 그래프를 관리 가능 단위로 분할할 필요가 있다. 이를 해결하기 위해 지오해싱과 비슷한 분할 기술을 적용해 작은 격자로 나누고, 나뉘어진 각 격자는 다른 타일에 대한 참조를 유지하여 필요한 타일만 로드하는 방식을 사용한다.

개략적 설계안

지도 서비스를 제공하기 위해 크게 아래 세 가지 기능으로 구분할 수 있다.

1. 위치 서비스

   • 사용자 위치를 기록하는 역할

   • 기록한 데이터로 데이터 스트림을 활용하여 시스템 개선 및 정확한 ETA 산출 가능

   • 변경 내역을 모아두었다가 일정 시간마다 전송하는 방식 사용(서버 부하 감소)

2. 경로 안내 서비스

   • 사용자의 출발지와 도착지를 입력받아 최적 경로를 제공

   • 꼭 최단 시간 경로일 필요는 없지만 정확도는 보장되어야 함

3. 지도 표시

   • 모든 지도 데이터를 한 번에 로드하는 것은 불가능하므로, 필요한 부분만 로드하는 방식 사용

   • 클라이언트의 위치 및 현재 확대 수준에 맞는 지도 데이터만 로드

   • 확대 수준별로 미리 만들어 둔 지도 타일을 클라이언트에게 전송

상세 설계

데이터 모델

지도 서비스에서는 아래 네 가지 데이터를 취급하게 된다.

1. 경로 안내 타일

   • 외부 사업자나 기관이 제공한 도로 데이터 사용(raw data)

   • 경로 안내 알고리즘에 활용할 수 있도록 가공하여 사용

   • 데이터 크기가 매우 크므로 S3 같은 객체 저장소에 저장하고, 캐싱 사용

2. 사용자 위치

   • 도로 데이터 및 경로 안내 타일 갱신에 이용

   • 실시간 교통 상황이나 교통 상황 이력 데이터 구축에도 활용

3. 지오코딩 데이터

   • 주소를 위도/경도 쌍으로 변환하는 정보 보관

   • 키-값을 빠르게 읽을 수 있도록 Redis 사용

4. 계산해 둔 지도 타일 데이터

   • 특정 영역의 정보를 취합하여 도로 및 상세 정보가 포함된 이미지 데이터

   • 자원을 많이 사용하고 중복 요청하는 경우가 많으므로 캐싱 사용

위치 서비스

사용자 위치 데이터 저장에는 키-값 저장소를 활용하는 NoSQL 데이터베이스를 사용하는 것이 좋은데, 그 이유는 다음과 같다.

• 위치 정보 업데이트가 빈번하게 발생하므로, 빠른 읽기/쓰기 속도가 필요

• 위치 정보가 일단 변경되면 이전 데이터는 중요하지 않으므로, 일관성보다는 가용성이 중요

위 조건을 고려했을 때 Cassandra 데이터베이스가 적합하다고 볼 수 있고, 해당 테이블을 다음과 같이 구성할 수 있다.

key(user_id)	timestamp	latitude	longitude	use_mode	navigation_mode
51	132053000	37.1234	127.1234	active	driving

• 데이터베이스 키: user_id + timestamp

• 파티션 키: user_id

• 클러스터링 키: timestamp

지도 표시

사용자가 보는 지도 크기나 확대 수준에 맞는 세부사항을 보여주기 위해선 확대 수준별 지도 타일을 미리 만들어 두어야 한다. 구글 맵의 경우 총 21단계로 지도를 확대하게 되는데, 수준을 한 단계 올릴 때마다 해당 수준을 위한 타일 수는 4배로 증가하게 된다. 때문에 많은 양의 데이터를 저장해야 하는데, 이를 이미지 대신 벡터로 관리하게 되면 저장 공간을 절약할 수 있다.

• 이미지에 비해 높은 압축률로 네트워크 대역폭 절약

• 그 외에 매끄러운 확대/축소, 렌더링 품질 향상 등의 장점

경로 안내 서비스

경로 안내 서비스를 제공하기 위해 필요한 컴포넌트들은 다음과 같다.

• 지오코딩 서비스: 주소를 위도/경도 쌍으로 바꿔주는 서비스

• 경로 계획 서비스: 현재 교통 상황과 도로 상태에 입각하여 최적화된 경로 제안

• 최단 경로 서비스: 출발지와 목적지 위도/경도를 입력 받아 최단 경로 반환

  • 교통이나 도로 상황 고려 x

  • 도로 그래프는 거의 정적이므로 데이터를 캐싱하여 사용

• 예상 도착 시간 서비스: 경로 계획 서비스에서 최단 경로 목록를 수신하면 예상 도착 서비스를 호출하여 소요 시간 추정치 계산

• 순위 결정 서비스: 경로 계획 서비스에서 추정치를 구하고 나면 해당 데이터들과 사용자가 정의한 필터링 조건(고속도로 제외 등)을 적용해 최적 경로 추천

사용자가 출발지와 목적지를 입력하면, 경로 계획 서비스는 다음과 같은 과정을 거친다.

1. 출발지와 목적지를 위/경도로 변환

2. 위/경도로 경로 계획 서비스 호출

3. 경로 계획 서비스는 최단 경로 서비스 호출

4. 최단 경로 서비스는 캐싱된 도로 데이터로 최단 경로 계산 후 반환

5. 반환 받은 최단 경로를 이용해 예상 도착 시간 서비스 호출

6. 예상 도착 시간 서비스는 도로 상태와 교통 상황을 고려해 예상 소요 시간 계산 후 반환

7. 반환 받은 예상 도착 시간을 이용해 순위 결정 서비스 호출

8. 순위 결정 서비스는 사용자가 정의한 필터링 조건을 적용해 최적 경로 추천

9. 최적 경로를 사용자에게 반환

전송 프로토콜

경로 안내 중 결로의 상황이 변경될 수 있으므로, 데이터를 클라이언트에 전송할 안정적인 방법이 필요하다. 서버에서 클라이언트에 이터를 보내는 프로토콜로는 다음과 같은 것들이 있다.

• 모바일 푸시 알림: 보낼 수 있는 메시지 크기가 제한적이기 때문에 경로 안내 데이터를 보내기에는 적합하지 않음

• 서버 전송 이벤트(SSE): 서버에서 클라이언트로 이벤트를 보내는 기술

• 웹소켓: 데이터 전송에 적합, 양방향 통신이 필요한 경우가 많기 때문에 적합

참고자료

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2