[시스템 디자인] 03. 구글 맵

시스템 디자인 시리즈의 글입니다.

단순한 형태의 구글맵을 설계해보자.

1. 문제 이해 및 설계 범위 확정

기능 요구사항

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

비기능 요구사항

• 정확도 : 사용자에게 잘못된 경로를 안내하면 안됨
• 부드러운 경로 표시
• 데이터 및 배터리 사용량
• 가용성
• 규모확장성

지도101 (지도에대한 기초내용)

• 측위시스템 : 구 표면상의 위치를 표현하는 체계. 위/경도로 표기
• 3차원 → 2차원 변환 (=지도투영법=도법)
  • 메크카토르 도법 등 다양한 도법 존재
  • 구글맵은 웹 메르카토르 도법 사용
• 지오코딩 : 주소 → 좌표로 변환하는 프로세스
• 역 지오코딩 : 좌표 → 주소로 변환하는 프로세스
• 지오해싱 : 지도 위 특정 영역을 짧은 문자열에 대응시키는 인코딩 체계
• 지도표시 : 지도를 전부 표시하는 대신, 작은 타일로 쪼개서 표시
• 경로 안내 알고리즘을 위한 도로 데이터 처리
  • 대부분 다익스트라 or A* 알고리즘 변형
  • 교차로는 노드로, 도로는 엣지로 표현
  • 알고리즘 성능은 그래프 크기에 민감
  • 성능을 위해 그래프를 관리 가능 단위로 분할할 필요가 있음
  • 각 타일은 도로로 연결된 다른 타일에대한 참조를 유지
  • 타일 분할 방법은 메모리 요구량을 낮추고 성능을 향상시킴
• 계층적 경로 안내 타일
  • 경로안내 위해서는 구체적인 도로 데이터가 필요
  • 구체성 정도를 상/중/하로 나누어 경로안내 타일을 준비
    • 상 : 크기는 작음. local road(지방도로) 데이터를 다룸.
    • 중 : 더 넓은 지역 커버. district(관할구)를 잇는 arterial roads(간선도로) 데이터 다룸.
    • 하 : 가장 큼. 주요 고속도로 데이터를 다룸
  • 다른 정밀도 타일 간에도 서로 연결됨

대략적 규모 추정

모바일 단말에서 사용되는 어플리케이션이기때문에 데이터사용량과 배터리 효율을 중요하게 봐야함

저장소 사용량

• 세계지도
  • 지원하는 확대 수준(zoom level)에 따라 지도 타일을 가지고있어야함
  • 최대 21배 확대 가능하다고 할 때, 약 4.4조개 타일 필요
  • 한 장의 타일 크기를 100KB라고할때, 최대 확대시 4.4조 * 100KB = 440 PB
  • 지구 표면의 90% 는 인간이 사용하지 않은 지역
  • 따라서 실제 10%정도의 데이터만 사용한다고하면 대략 50PB 저장공간 필요
  • zoom level별 저장공간 : 확대수준을 낮출때마다 필요한 타일 수 1/4
  • 50 + 50/4 + 50/4\^2 + … 50/4\^21 ~= 67PB
  • 대략 100PB 라고 하자.
• 서버 대역폭
  • 경로안내 요청 / 위치갱신 요청
  • DAU 10억, 주당 35분정도 경로안내 기능 사용 = 주당 350억 분 = 하루 50억분
  • GPU 좌표 매초 전송시 하루 3천억건(50억분*60) 요청 발생 = 하루 300만 QPS
  • 15초마다 전송시 300만/15 = 20만 QPS
  • 하루 최대 QPS는 넉넉하게 5배까지해서 100만이라고 하자.

2. 개략적 설계안 제시

위치서비스

• 사용자의 위치를 기록하는 역할.
• 클라이언트가 t초마다 자신의 위치를 전송한다고 가정.
  • 데이터 스트림을 활용하여 시스템 개선 가능 (ex. 교통상황 모니터링, 폐쇄도로 탐지, 개인화..)
  • 클라이언트가 보내는 위치정보가 실시간에 가깝기때문에 ETA(예상도착시간)을 정확히 산출 가능
• 위치 이력을 클라에 버퍼링해뒀다가 일괄요청하여 빈도를 줄일 수 있음
• 카산드라같이 높은 쓰기를 감당가능한 DB 추천
• 카프카같은 스트림처리엔진 활용하여 로깅하면 굿.
• HTTP를 keep-alive 옵션과 함께 사용하면 효율 굿. (연결 재사용)

경로 안내 서비스

• A에서 B 지점으로 가는 합리적으로 빠른 경로를 찾아주는 역할
• 시간 지연은 어느정도 감내 가능
• 단, 정확도는 보장되어야함

지도 표시

• 서비스는 확대 수준별로 지도를 저장
• 클라가 보는 확대 수준에 따라 필요한 타일을 서버에서 가져와야함
  • 선택지 1. 위치, 확대수준에 따라 필요한 지도타일을 즉석에서 만듬
  • 선택지 2. 확대수준별로 미리 만들어둔 지도타일을 가져옴
• 선택지 2가 규모확장에 용이하고 캐싱도 사용할 수 있음.
• CDN을 사용하여 POP(Point of Presence)에서 파일 서비스 가능
• 클라이언트 캐시 쓰면 더 효율이 좋음
• 지오해시를 사용하여 URL을 결정하고 CDN에서 특정 지도타일을 가져올수있음
• 클라에 지오해시 계산 로직을 넣는 방법도 있겠지만, 따로 지오해시 변환 서비스를 두면 운영 유연성이 높아짐

3. 상세설계

데이터 모델

• 경로 안내 타일
  • 도로 + 메타데이터
  • 가공되지 않은 데이터를 파이프라인을 거쳐 경로안내 타일로 변환
  • 상 / 중 / 하 3벌의 해상도로 타일 만듬
  • 교차로와 도로정보, 연결 도로에대한 참조정보 포함
  • 인접리스트(adjacency list)에 보관
  • 메모리에 두기에는 용량이 크므로, s3같은 object storage에 binary file로 직렬화하여 보관
  • 지오해시 기준으로 분류해두면 신속하게 타일 찾기 가능
• 사용자 위치 데이터
  • 아주 값진 데이터
  • 도로데이터 및 경로안내 타일 갱신에 사용
  • 실시간 교통상황 DB 구축에 활용
  • 지도데이터 갱신
  • 엄청난 양의 쓰기연산을 잘 수행해야함 → 카산드라처럼 수평규모확장 가능 DB 추천
• 지오코딩 데이터베이스
  • 주소 → 위경도 쌍으로 변환하는 정보 보관
  • key-value 저장소가 적당
  • 읽기연산 >>> 쓰기연산
• 미리 만들어 둔 지도 이미지
  • 특정 영역의 지도 요청을 받으면 인근 도로정보 취합하여 상세정보가 포함된 이미지를 만들어야함
  • 한번 계산된 이미지는 캐시해두면 좋음
  • 확대 수준별로 미리 지도를 만들어두고 CDN으로 전송
  • CDN 원본서버로는 s3같은 클라우드 저장소 활용

서비스

• 위치서비스
  • 위치데이터는 key-value DB 혹은 column-oriented DB를 추천.
  • 일관성보다는 가용성이 더 중요. (CAP중 AP) - ex) 카산드라
  • key : (user_id, timestamp)
  • value : 위/경도
  • user id는 파티션키로 사용하면 특정사용자의 최근위치데이터를 신속히 읽기 가능
  • timestamp는 클러스터링 키로 활용하면 시간에 따라 정렬하여 특정기간 위치를 신속히 읽기 가능
  • 사용자 위치데이터 이용
    • 새로 개설 or 폐쇄된 도로 감지
    • 지도데이터 정확성 개선
    • 실시간 교통 현황 파악
  • 카프카같은 데이터 스트리밍 플랫폼을 사용해 용도에 맞게 사용
• 지도 표시
  • 지도 타일 사전계산 : 확대 수준별 지도타일을 미리 만들어둠
  • 최적화 : 벡터 사용.
    • 월등한 압축률
    • 네트워크 대역폭 아낌
    • 매끄러운 지도 확대 경험.
• 경로 안내 서비스 : 가장 빠른 경로 안내
  • 지오코딩 서비스 : 주소 → 위경도 쌍
  • 경로계획서비스 : 현재 교통 상황과 도로상태에 입각해 최적의 경로 제안
  • 최단경로 서비스 : 출발지, 목적지를 입력받아 k개 최단 경로 반환
  • 예상 도착 시간 서비스 : 최단경로목록을 받아 각 경로에대한 소요시간 추정치를 구함.
  • 순위결정서비스 : 사용자가 정의한 필터링 조건을 적용, 소요시간순으로 정렬하여 k개 반환
  • 주요 정보 갱신 서비스 : 카프카 구독하여 중요데이터를 비동기적으로 업데이트
    • 실시간 교통정보
    • 경로안내 타일
  • 적응형 ETA와 경로변경
    • 현재 경로 안내를 받고있는 사용자를 추적하여, 교통상황이 달라질때마다 ETA를 변경 (네비처럼..)
    • 경로안내서비스 사용자(n)를 찾고 경로정보(m)를 또 찾으면 → O(n * m)
    • 현재경로타일의 상위타일을 재귀적으로 더하여 보관하면, 특정 타일의 상황이 변했을때 해당 사용자를 찾기가 쉬워짐 → O(n)
  • 전송 프로토콜 : 웹소켓 추천.

4. 마무리

최종설계