위치 기반 서비스를 위한 아키텍처 설계 - 구글 맵

※ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2권 - 챕터 3을 읽고 정리한 글입니다.

 

들어가며

위치 기반 서비스 설계에 대한 마지막 장으로, 구글 맵처럼 지도 탐색이나 경로 안내 등이 가능한 웹 기반의 지도 서비스를 설계해봅니다. 지도 이미지를 어떤 식으로 보여주도록 설계할 수 있는지, 경로 안내를 어떤 식으로 보여주도록 설계할 수 있는지 등에 대해 살펴보겠습니다. 

 

다음과 같은 기능적 요구사항을 가정합니다.

• 주기적으로 사용자의 현재 위치를 갱신시킬 수 있어야 합니다.
• 출발지와 목적지가 주어졌을 때 경로 안내를 할 수 있어야 합니다.
• 지도 표시를 할 수 있어야 하며, 사업장들의 위치나 사진은 표시하지 않아도 됩니다.

 

다음과 같은 비기능적 요구사항도 가정합니다.

• 사용자에게 잘못된 경로를 안내하면 안 됩니다.
• 클라이언트는 가능한 한 최소한의 데이터와 배터리를 사용해야 합니다.
• 일반적으로 널리 통용되는 가용성과 확정성을 갖춰야 합니다.

 

 

개략적인 규모 추정

다음과 같이 가정합니다.

1. 일간 활성 사용자(DAU) : 10억 명
2. 일별 경로 안내 기능 사용 시간 : 50억 분 (각 사용자가 주당 35분 이 기능 사용)
3. QPS : 20만으로 가정 (경로 안내 기능 사용 중에 사용자 위치 갱신)
4. 최대 QPS :평균치의 5배 = 100만으로 가정

 

그리고 기본적으로 다음 4가지의 데이터를 보유한 상태로 시작해야 합니다.

1. 세계 지도 이미지 : 하나의 커다란 이미지를 표시하는 대신 작은 타일들로 쪼갠 뒤 클라이언트는 필요한 영역의 타일들만 이어붙여 보도록 할 수 있습니다. 확대 수준에 따라 이미지 세트를 여러 개 준비해야 하며, 여기서는 총 100PB가 소요된다고 가정합니다.
2. 메타데이터 : 각 지도 이미지들의 메타데이터로, 크기가 아주 작으므로 신경쓰지 않아도 됩니다.
3. 도로 데이터 : 경로 안내에 사용되며 수 TB 수준의 raw data를 미리 확보해 둔 상태로 가정합니다. 경로 안내를 위해 그래프 형태의 자료구조로 변환할 필요가 있으나 변환 결과의 용량도 비슷하다고 유추할 수 있습니다.
4. 위도 경도 페어 : 책에는 안 나와있으나.. 경로 안내를 위해 출발지 목적지를 위도 경도 페어로 바꿔야 하는데 이 데이터들을 지오코딩DB에 저장합니다. 하나의 레코드에 66Byte가 든다고 가정(주소 50, 위도 8, 경도 8)하고 전 세계의 주소를 20억 개(추정..)로 한다면 러프하게 132GB 정도의 용량이 필요합니다.

 

 

개략적인 설계안 제시

이 시스템은 위치 갱신 기능, 도로 데이터를 통한 경로 안내 기능, 세계 지도 이미지를 통한 지도 표시 기능을 제공해야 합니다. 개략적으로 다음과 같은 설계안을 제시할 수 있습니다.

 

 

1) 위치 서비스의 개략적 설계

사용자의 위치를 기록하는 역할을 담당합니다. 클라이언트가 t초 간격으로 자기 위치를 전송하게 할 수 있으며, 해당 데이터 스트림을 활용해 실시간 교통 상황 감지(정체되는 구간 분석 등), 사용자 행동 양태 분석 등에 활용 가능합니다.

 

그렇다고 사용자 위치가 바뀔 때마다 서버로 위치 기록 요청을 보내면 부하가 상당합니다(책에선 하루에 50억 분을 경로 안내에 사용한다고 말하며, 그 시간 동안 위치 기록이 이루어집니다). 이때 클라이언트가 위치 변경을 15초 정도 버퍼링하다가 일괄로 위치 기록을 요청하는 식으로 구현하면 부하를 크게 줄일 수 있습니다. 그러나 여전히 부하가 크고 특히 쓰기 연산이 많이 일어날 것이므로, 쓰기 성능이 탁월(메모리에 데이터를 모으다가 한 번에 디스크로 쓰는 방식을 통해 디스크 I/O가 적음)한 카산드라DB를 사용 가능합니다. 

 

2) 경로 안내 서비스의 개략적 설계

출발지에서 목적지로 가는 빠른 경로를 찾아주는 역할을 합니다. 문자열 주소로 주어지는 목적지와 출발지를 각각 알맞은 위도 경도 페어로 바꾸고(이를 지오코딩이라 함), 이를 통해 목적지까지 가는 경로를 찾아 사용자에게 반환합니다.

 

지오코딩용 DB는 읽기 연산 위주의 DB이고, 각 주소에는 하나의 위도 경도 페어만 대응되므로 레디스 등의 인메모리 키-밸류 DB를 사용하는 것이 성능 차원에서 유리합니다. 개략적 규모 추정에서 살펴봤듯 132GB의 데이터를 담고 있어야 하므로, 샤딩을 통한 데이터 분배를 고려할 수 있습니다.

 

앞서 설명했듯 도로 데이터는 수 TB를 raw data로 가지고 있다고 가정하고 있으므로 이를 그래프 형태의 자료구조로 변환하여 경로 안내에 사용해야 합니다. 그러나 전세계 도로망을 하나의 그래프로 표현하면 메모리 + 성능 차원에서 비효율적이므로 여러 그래프로 분리한 다음 필요한 그래프만 가져와서 연산하는 것이 효율적입니다. 이를 위해 2차원 공간을 여러 격자로 나누고(지오해싱 등 사용 가능), 각 격자별로 그래프를 관리하게 할 수 있습니다. 또한 각 격자(타일)들이 도로로 연결된 다른 타일에 대한 참조를 가지게 하고, 효과적인 경로 안내를 위해 계층적으로 타일을 구성시킬 수 있습니다. 참고로 이런 그래프 데이터는 메모리에 인접 리스트 형태로 두는 것이 일반적이나 이 시스템에선 수 TB 수준으로 양이 상당하므로, S3같은 객체 저장소에 두고 캐싱을 활용하게 하는 것이 좋습니다.

 

3) 지도 표시의 개략적 설계

개략적인 규모 추정에서 언급했듯이 지도 이미지는 총 100PB가 존재하므로, 이를 클라이언트가 다 가지게 한 뒤에 필요한 부분만 너희가 알아서 렌더링해서 보라고 하는 것은 실용적이지 않습니다. 클라이언트가 보고 있는 위치와 확대 수준에 따라 필요한 영역의 이미지만 가져오는 접근법이 실용적입니다. 이때 미리 지도 타일들을 만들어 저장해두고 필요한 영역의 타일 집합들을 요청(지오해싱 등을 활용)해서 해당 타일들을 받아오도록 할 수 있습니다. 

 

지도 이미지의 양이 상당하고 이 서비스는 글로벌 서비스를 가정(DAU가 10억)하므로, CDN을 통해 지도 이미지를 서비스하도록 구성할 수 있습니다. CDN 사용은 사용자들이 자신과 가까운 곳으로부터 컨텐츠를 받아볼 수 있으므로 지연속도가 빨라진다는 장점 등이 있으며, 다음 순서대로 동작하게 됩니다.

 

1. 클라이언트가 지도 타일 요청을 CDN에 보냄
2. 해당 이미지가 CDN을 통해 서비스된 적 없다면 지정된 원본 서버에서 해당 이미지를 가져와서 캐싱하고 사용자에게 반환
3. CDN을 통해 서비스된 적 있다면 바로 사용자에게 반환

 

또한 잠깐 말했듯이 지도 이미지 요청 시 지오해시 값을 계산하여 요청할 수 있는데, 이때 클라이언트가 직접 지오해시를 계산하는 방법을 사용한다면 여러 클라이언트(웹, 앱 등)를 따로 관리해야 하는 불편함이 생길 수 있습니다. 따라서 지오해시 값을 계산하는 서비스를  별도로 분리하면 좀 더 유연성을 가져갈 수 있습니다.

 

 

 

상세 설계

1) 위치 서비스의 상세 설계

앞서 살펴봤듯 쓰기 연산이 많이 일어나는 서비스이므로 카산드라같이 쓰기 성능에 좋은 DB를 고려할 수 있습니다. 카산드라는 키-밸류 데이터베이스이므로 (사용자 식별자, 위치 변경 타임스탬프)를 키로, 위도 경도 페어를 밸류로 기록하게끔 설계할 수 있습니다. 이때 사용자 식별자를 파티션 키(데이터를 어떤 노드에 저장할지 결정하는 데 사용)로 설정하고 타임스탬프를 클러스터링 키(동일한 파티션 내에서 데이터를 정렬하는 데 사용)로 설정한다면 특정 사용자의 특정 기간 내 위치를 효율적으로 읽도록 할 수 있습니다.

 

사용자 위치를 DB에 기록하는 것과 별개로, 카프카같은 데이터 스트리밍 플랫폼을 통해 실시간 교통 상황 서비스 등의 개별 서비스로 위치 데이터 스트림을 전달하도록 설계할 수 있습니다.

 

 

2) 경로 안내 서비스의 상세 설계

개략적인 설계에서 좀 더 세분화하여 다음과 같이 여러 역할을 가진 컴포넌트들로 설계할 수 있습니다.

 

 

경로 안내 서비스가 지오코딩 서비스를 호출하여 출발지와 목적지의 위도 경도 페어를 가져온 뒤 경로 계획 서비스를 호출하게 하고, 경로 계획 서비스는 현재 교통 상황이나 도로 상황에 입각해 이동 시간 측면에서 가장 최적화된 경로를 안내하도록 합니다.

 

a) 최단 경로 서비스

출발지와 목적지의 위도 경도 페어와 객체 저장소에 저장된 경로 안내 타일들을 활용해 특정 개수만큼의 최단 경로들을 반환하게 합니다. 즉 교통 상황은 고려 대상이 아닙니다. 경로 안내 타일에 쓰이는 그래프 데이터는 거의 정적인 데이터이므로 캐시를 적극 활용하는 것도 고려할 수 있습니다. 

 

b) 예상 도착 시간 서비스

최단 경로 서비스가 반환한 경로 목록들에 대한 소요 시간 추정치를 구하게 합니다. 이 서비스는 머신 러닝을 통해 과거의 교통 상황을 근거로 한 도착 시간들을 학습하고, 현재의 교통 상황을 입력으로 하여 예상 도착 시간을 계산하도록 설계할 수 있습니다.

 

c) 순위 결정 서비스

최단 경로 서비스가 구한 경로들에 대해 예상 도착 시간 서비스가 경로별로 예상 도착 시간들까지 구했다면, 순위 결정 서비스를 통해 사용자가 정의한 필터링 조건(도보로만 가기 등)을 적용한 경로들을 얻게끔 합니다. (책에서는 예상 도착 시간들을 구한 뒤 필터링을 적용하나, 개인적으론 필터링을 먼저 적용한 뒤 남은 경로들에 대해 예상 도착 시간을 구하는 것이 연산 횟수가 더 적을 것 같다는 생각이 듭니다.)