대규모 시스템 설계 기초 2 - 3장. 구글맵

해당 포스팅은, 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2 스터디를 하며 정리한 포스팅입니다.

---

이번 포스팅은 구글 맵과 관련된 서비스를 제공하기 위한 시스템 설계 부분입니다. 기능과 비기능 요구사항은 아래와 같습니다.

기능 요구사항과 비기능 요구사항 분리

기능

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

비기능

• 정확도: 사용자에게 정확한 경로를 안내해야 합니다.
• 부드러운 경로 표시: 경로 안내 지도는 부드럽게 표시되고 갱신되어야 합니다/
• 최소한의 데이터 및 배터리 사용량: 이 요구사항은 모바일 단말에 아주 중요합니다.
• 가용성 및 규모 확장성도 고려해야 합니다.

---

이와 같은 지리적 기반 서비스를 제공하기 전에 필요한 개념들이 아래와 같이 소개되어 있습니다.

위치 기반 서비스 필요 개념

• 측위 시스템: GPS와 같이 구 표면상의 사용자의 위치를 특정 좌표(위도, 경도)로 파악하여 제공하는 시스템입니다.
• 지도 투영법, 도법: 지구의 3차원 구 위의 위치를 2차원 평면에 대응시키는 절차로, 평면에 펼칠 때 왜곡이 발생하는데, 이 왜곡을 최소화하거나 특정 속성을 보존하도록 고안된 다양한 수학적 기법입니다. (용도에 맞는 적절한 도법을 선택하는 것이 핵심)
• 지오코딩 (Geocoding): 실제 위치 정보를 컴퓨터가 이해할 수 있는 위도와 경도 좌표로 변환하는 과정
  • "서울특별시 종로구 청와대로 1"이라는 주소를 입력하면, 지오코딩을 통해 해당 위치의 위도와 경도 좌표를 얻을 수 있습니다.
  • 리버스 지오코딩 (Reverse Geocoding) : 역으로 위도와 경도 좌표를 입력하면, 주소나 장소 이름으로 변환하는 과정입니다.
• 지오해싱 (Geohasing): 지리적 위치 정보를 고유한 문자열로 인코딩하는 방법
  
  • 지구 표면을 격자 형태의 사각형 구역으로 나눈 뒤, 각 구역에 고유한 문자열 코드를 부여합니다.
  • 더 자세한 내용은 해당 블로그를 참고하면 될 것 같습니다. 
• 타일(tile): 지도를 화면에 표시하는 가장 기본이 되는 개념입니다. 타일에 대한 자세한 내용은 아래 접은 글에 더 정리해 보았습니다.

타일 방식의 원리

지도 전체를 하나의 이미지로 제공하는 대신, 지도를 작은 사각형 타일로 분할하여 필요한 부분만 로딩합니다. 지도 화면이 이동하거나 확대/축소될 때, 현재 화면에 보이는 영역에 맞는 타일을 서버에서 불러옵니다. 타일은 줌 레벨에 따라 크기와 개수가 달라지며, 고해상도 지도일수록 더 많은 타일이 필요합니다.

예를 들어, 줌 레벨이 0일 때는 전 세계를 하나의 타일로 표시하고, 줌 레벨이 1로 증가하면 2x2 타일로 분할됩니다. 줌 레벨이 올라갈수록 지도는 더 세분화되어 많은 타일로 나뉘게 됩니다.

 

타일의 특징과 장점

1. 빠른 로딩과 성능 최적화: 지도 전체를 불러올 필요 없이, 사용자가 보고 있는 영역의 타일만 불러오기 때문에 로딩 속도가 빨라지고, 서버와 네트워크 부하를 줄일 수 있습니다.
2. 확대/축소에 따른 유연한 대응: 지도를 확대할 때 세밀한 타일을 불러와 고해상도 지도를 제공할 수 있습니다. 반대로 축소할 때는 적은 수의 타일만 불러오므로 메모리 사용이 효율적입니다.
3. 캐싱 용이: 타일 방식은 같은 타일 이미지를 여러 사용자에게 제공하기 쉽기 때문에, 캐싱을 통해 서버 부하를 줄이고 응답 속도를 개선할 수 있습니다.
4. 다양한 스타일 적용 가능: 지도에 서로 다른 스타일이나 정보를 겹쳐서 표시할 수 있습니다. 예를 들어, 기본 지도 위에 교통정보 타일, 날씨 정보 타일 등을 중첩하여 표시할 수 있습니다.

 

• 경로 탐색(routing) 알고리즘
  • 대부분의 알고리즘은 Djikstra 알고리즘 혹은 A* 경로 탐색 알고리즘의 변종이고, 모든 경로 탐색 알고리즘은 교차로를 노드(node)로, 도로는 노드를 잇는 선(edge)으로 표현하는 그래프 자료 구조를 가정합니다.
  • 알고리즘의 성능은 주어진 그래프 크기에 아주 민감합니다. 따라서, 좋은 성능을 위해 그래프를 관리 가능한 단위로 분할할 필요가 있습니다. 그 방법 중 하나가 지오해싱과 비슷한 분할 기술을 사용하여 세계를 작은 격자로 나누고, 각 격자 안의 도로망을 노드(교차로)와 선(도로)으로 구성된 그래프 자료 구조로 변환합니다.
  • 각 격자는 경로 안내 타일이라고 부르는데, 각 타일은 도로로 연결된 다른 타일에 대한 참조(reference)를 유지합니다.
  • 이렇게 분할함으로써, 경로 탐색 알고리즘이 동작할 때 필요한 타일만 로드하므로 응답 속도가 빠르고 부드러운 사용자 경험을 제공합니다. 필요한 메모리 요구량을 낮출 수 있고, 한 번에 처리해야 하는 경로 양이 줄어들 것입니다.
• 계층적 경로 안내 타일
  • 대규모 지도 데이터에서 경로를 안내할 때, 효율적으로 데이터를 분할하고 접근하기 위해 사용하는 방식입니다.
  • 지도 데이터를 계층적으로 나누어 타일 형식으로 저장하여, 특정 경로 안내에 필요한 데이터만 빠르게 불러올 수 있도록 도와줍니다.
  • 보통 구체성 정도를 상, 중, 하로 구분하여 3가지 종류의 경로 안내 타일을 준비합니다.  상이면 구체성이 높은 타일 (local roads, 지방도), 중이면 규모가 비교적 큰 관할구(district)를, 하이면 그보다 더 큰 영역을 커버합니다.

여기까지의 내용에서, 사용자가 지도를 확대/축소할 때 레벨별로 타일을 저장한다는 것이 신기했습니다. 즉, 지도 서비스를 제공하는 곳에서 확대/축소 레벨을 설정해서 각 레벨별로 타일(일종의 지도 스냅샷)을 미리 저장해 둔다는 아이디어가 신선했습니다.

추가로, 책에서 해당 타일을 저장할 때 필요한 저장소 크기를 계산하는 과정을 보여주는데, 이 부분에서 이렇게도 계산할 수 있구나라는 것을 배울 수 있었습니다. 서비스를 설계할 때 DB 저장 데이터 크기와 QPS 등을 계산하는 것이 중요하다는 것을 다시 한번 볼 수 있었습니다.

 

---

이 책에서는 서비스를 크게 3가지로 나누어서 설계하고 있습니다.

서비스 3가지

 

위치 서비스

위치 서비스의 경우, 사용자의 위치를 기록하는 역할을 담당합니다. 하지만, 사용자의 위치가 바뀔 때마다 서버로 전송해서 DB에 저장하는 것은 비효율적입니다. 따라서, 위치 이력을 Client 쪽에서 버퍼링 해두었다가 Batch 작업으로 server로 전송하여 전송 빈도를 줄이는 것이 중요합니다.
 
이렇게 Batch 작업으로 처리를 해도 여전히 쓰기 요청 빈도는 높을 것입니다. 따라서, 사용자 위치를 DB에 쓸 때는 아주 높은 쓰기 요청 빈도에 최적화되어 있고 규모 확장이 용이한 DB가 좋습니다. 이러한 DB에는 Cassandra가 있고요.
 
추가로, 사용자 위치 정보는 경로 제공 서비스 외에도 분석 서비스나 개인화 학습 서비스, 실시간 교통 상황 서비스 등 다양한 서비스에서 활용될 수 있습니다. 각 서비스 별로 필요한 정보를 consume 해서 가지고 갈 수 있도록 Kafka 같은 Stream 처리 엔진을 활용해 위치 데이터를 로깅할 수도 있습니다. 즉, 이런 서비스들은 이력 데이터 관련 서비스로, Kafka 위치 데이터 Stream을 구독하고 있다가 비동기적으로 update 하여 상태를 항상 최신으로 유지하는 역할을 담당하는데, 이들은 아래 경로 안내 서비스에 큰 영향을 미치기 때문에 중요합니다.

 

위치 서비스

 

사용자 위치 데이터로 경로 제공뿐만 아니라  다양한 서비스를 제공할 수 있다는 점이 신기하였습니다. 실시간 교통 상황 서비스, 개인화를 위한 서비스, 새로 열린 도로나 폐쇄된 도로 탐지 서비스 등으로 활용된다는 점이 흥미로웠습니다.
처음 읽었을 때, 사용자의 최종 위치만 있으면 될 것이라 생각하고 이력은 왜 관리하는 것인지 의문이 들었는데, 이러한 서비스 제공에 도움이 되는 중요한 데이터라는 것을 깨달았습니다.

 
 

경로 안내 서비스

이 서비스는 출발지 A에서 목적지 B까지 가는 합리적으로 빠른 경로를 찾아주는 서비스입니다. 

• 지오 코딩 서비스: 주소를 위도/경도 쌍으로 바꿔주는 서비스 
• 경로 계획 서비스
  • 현재 교통 및 도로 상황에 기반하여 이동 시간 측면에서 최적화된 경로 제안하는 역할
    • 최단 경로 서비스: k개 최단 경로 반환하는데, 교통이나 도로 상황을 고려하지는 않습니다. 즉, 도로 구조에만 의존하여 계산을 수행합니다. 경로 안내 타일과 연결되어 있어서 (아래 데이터 모델 섹션 참고) 출발지와 목적지 경로 안내 타일을 얻고, 출발지 타일에서 시작하여 그래프 자료 구조를 탐색해 나갑니다. (도로망 그래프는 거의 정적이므로 cache 해 두는 것이 좋습니다.)
    • 예상 도착 시간 서비스: 최단 경로 목록 (k개)을 수신하면, 예상 도착 시간 서비스(ETA service)를 호출하여 그 경로 각각에 대한 소요 시간 추정치를 구합니다. 이때, 기계 학습을 통해 현재 교통 상황 및 과거 이력에 근거하여 계산합니다. (10분, 20분 뒤 교통 상황도 예측해야 하는 까다로운 문제입니다.) 
    • 순위 결정 서비스: ETA 예상치를 구하고 나면, 해당 서비스에 관련 정보를 전달하여 사용자가 정의한 필터링 조건을 적용합니다. 필터링되고 남은 경로를 소요 시간 순으로 정렬하여 최단 시간 경로 k개를 결과로 반환합니다.

 
위의 사용자 위치 데이터의 kafka를 구독하고 있는 서비스들이 경로 안내 서비스에 중요한 역할을 하는 이유가 바로 여기에 있습니다. kafka를 구독하고 있는 서비스들 중, 실시간 교통 상황 서비스를 예로 들어보겠습니다. 실시간 교통 상황 데이터베이스에 실시간 교통 상황이 잘 반영이 되어 있어야 예상 도착 시간 서비스가 더욱 정확한 결과를 낼 수 있게 되는 것입니다.

 

CDN (지도 표시)

사용자가 지도를 확대할 때마다 서비스는 새로운 지도 사진을 보여주어야 합니다. 이를 제공하기 위해서 사용자의 요구사항에 맞게 지도 타일을 즉석에서 만드는 방법은 시스템에 심각한 부하를 초래할 것입니다. 따라서, 지도 확대/축소 레벨별로 미리 지도 타일을 만들어 두고 저장해서 이를 전달하는 방법이 필요합니다. 
 
클라이언트는 지도 타일이 필요할 경우, 사용자의 현재 확대 수준에 근거해서 필요한 지도 타일 집합을 결정합니다. 그 후 그 각 위치를 지오해시(Geohash)로 변환하여 CDN으로부터 url을 통해 가져올 수 있습니다. 물론, 각 위치를 Geohash url(ex. https://cdn.map-provider.com/tiles/{geohash 문자열})로 변환하는 별도 서비스를 두는 것이 클라이언트에서 계산하는 것보다 운영 유연성 등에서 더 좋을 것입니다.

CDN 서비스

 

---

데이터 모델

위 서비스를 위해 필요한 데이터를 4가지로 분류해서 모델링하고 있습니다.

경로 안내 타일

경로 안내 서비스의 최단 경로 서비스와 연결되는 데이터입니다.
 
외부에서 도로와 그 메타데이터에 대한 데이터를 주면, 경로 탐색을 위한 알고리즘의 입력으로 활용할 수 있는 형태로 변환해야 합니다. 그래프와 같은 자료구조 형태로 말이죠. 그리고 이렇게 변환된 데이터를 S3 같은 객체 저장소에 보관하고, 해당 파일을 이용할 경로 안내 서비스에서 적극적으로 캐싱하도록 구성합니다.
 
S3와 같은 객체 저장소에 저장하는 이유는, 해당 데이터를 DB나 메모리에 저장하기에는 양이 너무 많아 비용이 많이 들기 때문입니다. 해당 데이터는 그래프끼리의 인접 리스트로 구성이 되어 있을 것인데, 인접 리스트를 이진 파일(binary file) 형태로 직렬화해주는 고성능 소프트웨어 패키지는 많아 이를 활용하면 효율적으로 데이터를 저장할 수 있을 것입니다. 그리고, 지오 해시 기준으로 분류해서 저장함으로써 신속하게 타일을 찾을 수 있습니다.
 

사용자 위치 데이터

사용자의 위치와 관련된 다양한 정보를 포함하는 데이터로, 일반적으로 GPS 좌표(위도, 경도)와 시간 정보가 포함됩니다
이 외에도 사용자의 속도, 고도, 위치 변화 이력 등이 포함될 수 있습니다. 위의 사용자 위치 서비스에서 언급한 것처럼 데이터베이스는 수평적 규모 확장이 가능한 Cassandra를 지정하고 있습니다.
 
특히나, 해당 데이터는 사용자 위치로 계속 변화하기 때문에 일관성(Consistency)보다는 가용성(Availability)이 더 중요합니다. 즉,  CAP 정리에서 Consistency 보다는 Availability, Partition tolerance를 만족시키는 DB 선택에 집중하는 것이 좋습니다. (3가지를 모두 만족시키는 DB는 없으니 말이죠.)
 

지오 코딩 데이터베이스

경로 안내 서비스의 지오 코딩 서비스와 연결되는 데이터입니다.
 
특정 주소가 Geocoding을 통해 변환된 위도/경도 쌍으로 저장된 곳입니다. 즉, 출발지와 목적지 주소가 주어지면, 경로 탐색 서비스 수행 전에 해당 데이터베이스로부터 위도/경도 쌍으로 변환되어야 합니다.
해당 데이터는 읽기 연산은 빈번하지만 쓰기 연산은 드물게 발생할 것이므로, Redis처럼 읽기 연산을 제공하는 key-value 저장소가 적당할 것입니다.
 

미리 만들어 둔 지도 이미지 (CDN)

특정 영역의 지도를 요청하면, 인근 도로의 정보 취합하여 모든 도로 및 관련 상세 정보가 포함된 이미지를 만들어야 합니다. 이 과정은 계산 자원을 많이 사용하고, 같은 이미지를 중복 요청하는 경우가 많기 때문에 한 번만 계산하고 캐시에 두는 전략이 좋을 것입니다. 즉, 확대 수준별로 미리 만들어서 CDN을 통해 전송합니다. 원본 서버로는 S3 같은 클라우드 저장소를 활용합니다.
 

---

 
최종 설계도는 아래와 같습니다.

최종 설계도

최종 설계도

 

---

 

이번 장을 통해서, 어떻게 효율적으로 지도 데이터를 저장할 수 있는지 배울 수 있었습니다. 지도를 격자로 나누고, 지도의 확대/축소 레벨별로 각 격자들을 분류해서 저장함으로써 사용자가 보고 있는 영역의 타일만 불러오기 때문에 로딩 속도가 빨라지고, 서버와 네트워크 부하를 줄일 수 있는 장점이 있습니다. 여기에 더해서, 타일 방식은 같은 타일 이미지를 여러 사용자에게 제공하기 쉽기 때문에, 캐싱을 통해 서버 부하를 줄이고 응답 속도를 개선할 수 있다는 것을 배웠습니다.
 
그 외에도, 데이터 특성 별로 어떤 DB를 사용해야 하는지 결정하는 것도 매우 중요하다는 것을 깨달았습니다. 이 과정에서 데이터 읽기/쓰기 QPS를 계산하는 것, 데이터 크기를 계산하는 것이 필수적이고, 계산하는 방법을 숙지하는 것이 필요하다고 느꼈습니다.
 
마지막으로, 사용자 데이터로도 도로 상황을 파악하고 개인화를 위한 서비스도 제공할 수 있다는 점도 흥미로웠습니다. 
 

---

 

• 스터디 진행 후 팀원들과 나눈 이야기
  • T맵과 같은 네비게이션은 어떻게 동작하는 지 궁금해졌다. 경로를 안내해 줄 때, 같은 경로로 가는 사람들이 많으면 모든 사람에게 같은 경로를 알려주지 않을 것 같다. 모두 같은 경로로 가면 병목이 심해질 것이니까...
  • 엄청나게 먼 거리도 구글맵에서 지원을 해줄까 궁금했는데, 실제로 중국에서 아프리카까지 찍어보니까 경로를 지원해 주었다...ㅎㅎ 경로를 보여주는 과정이 좀 오래 걸리긴 했는데, 경로 계산에서 메모리가 터지지 않고 제공해주는 걸 보니 경로를 바로바로 계산하는 게 아니라 어느정도는 메모리에 저장해두고 있는 것 같다...