대규모 시스템 설계 기초 2 (3장)

가상 면접 사례로 배우는 대규모 시스템 설계 기초 2 (3장) 의 내용 중, 인상적이었던 부분을 발췌 및 요약합니다.

구글 맵

세 가지 기능을 지원할 예정이다.

• 사용자 위치 갱신
• 경로 안내 서비스(ETA 서비스 포함)
• 지도 표시

지오 코딩

지오코딩은 주소를 지리적 측위 시스템의 좌표로 ㅈ변환하는 프로세스다.

지오해싱

지도 위 특정 영역을 영문자와 숫자로 구성된 짧은 문자열에 대응시키는 인코딩 체계다. 2차원의 평면 공간으로 표현된 지리적 영역 위의 격자를 더 작은 격자로 재귀적으로 분할해 나간다.

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

경로 탐색은 다익스트라 알고리즘과 같은 경로 탐색 알고리즘의 변종이다. 교차로를 노드로, 도르를 엣지로 표현한 그래프로 추상화함으로서 경로를 탐색할 수 있다.
그러나, 전 세계 도로망을 하나의 그래프로 표현하는 것이 아니라, 격자 크기마다 다른 도로를 갖고 있어야 한다. 이를 routing tile 이라고 부른다. 타일에 따라서 지방도의 데이터를 담고 있고 > 간선 도로를 담고 있고 > 고속 도로를 담고 있는 형식이다.

위치 서비스

사용자의 위치가 바뀔 때마다 서버로 전송할 필요는 없다. 약 15 초 정도의 버퍼를 두면, 클라이언트가 서버에 보내는 요청의 수를 줄일 수 있을 것이다. 이 데이터를 db 에 저장하기 위해서는 쓰기 요청에 최적화된 db 가 필요하다.
카산드라와 같은 쓰기 요청과 규모 확장에 용이한 db 를 고려해보자. 이벤트 기반 처리 엔진을 활용하면 위치 데이터를 로깅할 수도 있을 것이다. 위치를 전송하는 동안에는 http keep-alive 를 사용해서 효율을 높여보자.

cap 정리 에 따르면, 이번 시스템은 일관성(정확한 위치 데이터의 저장)보다 가용성(지속적인 응답)이 중요하다고 판단된다. 카산드라는 이런 측면에서 높은 가용성을 보장한다.

경로 안내 서비스

도로 데이터는 매우 방대하고, 내가 원하는 형태로 가공된 형태가 아닐 것이다. 이를 위해 데이터 가공 파이프라인을 주기적으로 실행하여 경로 안내 타일로 변환이 필요할 것이다.
최단 경로 서비스는 출발지와 목적지를 입력 받아 k 개 최단 경로를 반환해야 한다. 도로 구조에만 의존하여 계산을 수행하면 된다. 주변의 경로 타일을 가져오면서 다익스트라와 같은 알고리즘을 수행한다.

예상 도착 시간 서비스

예상 도착 시간은 실시간 교통 상황 데이터 뿐 아니라 얼마 후의 교통 상황에 대해서도 예측해야 한다. ETA 예상치를 구하면, 순위 결정 서비스에 관련 정보를 전달하여 필터링된 결과를 사용자에게 보내주면 된다.

적응형 ETA 와 경로 변경

이를 위해서는 2가지 문제가 있다.

• 현재 경로 안내를 받고 있는 사용자를 추적하는 방법
• 수백만 경로 가운데 교통 상황 변화에 영향을 받는 경로와 사용자를 효율적으로 가려낼 방법은 무엇인가?

전체 경로 정보를 전수 조사해서 문제가 발생한 특정 타일을 추적하는 것은 효율적인 방법은 아닐 것이다. 이는 O(n * m) 의 시간 복잡도를 가진다.
검색 속도를 더 높이기 위해서는, 경로 안내를 받는 사용자 각각의 현재 경로 타일, 타일의 상위 타일, 상위의 상위 타일을 출발지와 목적지가 모두 포함된 타일을 찾을 때까지 재귀적으로 더하여 보관하는 것이다.
마지막 가장 큰 타일에 문제가 발생한 타일이 속하는 사용자라면 영향을 받을 것이다. 이는 시간 복잡도가 O(n) 이므로 좀 더 효율적이다.