3단계 상세 설계

이번 절에서는 우선 데이터 모델부터 살펴본다. 그런 다음 위치 서비스, 경로 안내 서비스, 지도 표시에 대한 보다 상세한 설계를 진행할 것이다.

데이터 모델

본 설계안이 다루는 시스템은 다음 네 가지 데이터를 취급한다.

1. 경로 안내 타일
2. 사용자 위치
3. 지오코딩 데이터
4. 미리 계산해 둔 지도 타일 데이터

경로 안내 타일

앞서, 애초에 필요한 도로 데이터로는 외부 사업자나 기관이 제공한 것을 이용한다고 밝힌 바 있다. 이 데이터의 용량은 수 테라바이트에 달하며, 애플리케이션이 지속적으로 수집한 사용자 위치 데이터를 통해 끊임없이 개선된다.

이 데이터는 방대한 양의 도로 및 그 메타데이터(이름, 관할구, 위도, 경도 등 의 도로 부속 정보)로 구성된다. 그래프 자료 구조 형태로 가공되지 않은 데이터이므로, 주어진 상태 그대로는 경로 안내 알고리즘의 입력으로 활용할 수 없다.

그러므로 경로 안내 타일 처리 서비스(routing tile processing service) 라 불리는 오프라인 데이터 가공 파이프라인을 주기적으로 실행하여 경로 안내 타일로 변환한다. 도로 데이터에 발생한 새로운 변경사항을 반영하기 위해서다.

지도 101절에서 살펴보았지만, 경로 안내 타일을 만들 때는 해상도를 달리 하여 세 벌을 만든다. 각 타일에는 그래프의 노드와 선분으로 표현된 해당 지역 내 교차로와 도로 정보가 들어 있다. 다른 타일의 도로와 연결되는 경우에는 해당 타일에 대한 참조 정보도 포함된다. 경로 안내 알고리즘은 이들 타일이 모인 결과로 만들어지는 도로망 데이터를 점진적으로 소비한다.

그렇다면 경로 안내 타일 처리 서비스는 가공 결과로 만든 타일을 어디에 저장해야 할까? 그래프 데이터는 메모리에 인접 리스트(adiacency list) 형태로 보관하는 것이 일반적이다. 하지만 본 설계안이 다루는 타일 데이터는 메모리에 두기에는 양이 너무 많다. 그래프의 노드와 선을 데이터베이스 레코드로 저장하는 것도 방법이겠지만 비용이 많이 든다. 게다가 경로 안내 타일의 경우 데이터베이스가 제공하는 기능이 필요 없다는 것도 문제다.

경로 안내 타일을 저장하는 효율적 방법은 S3 같은 객체 저장소(obiect stor-age)에 파일을 보관하고 그 파일을 이용할 경로 안내 서비스에서 적극적으로 캐싱하는 것이다. 인접 리스트를 이진 파일(binary file) 형태로 직렬화(serial-ize) 해주는 고성능 소프트웨어 패키지는 많다. 타일을 객체 저장소에 보관할 때는 지오해시 기준으로 분류해 두는 것이 좋다. 그러면 위도와 경도가 주어졌 을 때 타일을 신속하게 찾을 수 있다.

사용자 위치 데이터

사용자의 위치 정보는 아주 값진 데이터다. 이 데이터는 도로 데이터 및 경로 안내 타일을 갱신하는 데 이용되며, 실시간 교통 상황 데이터나 교통 상황 이력 데이터베이스를 구축하는 데도 활용된다. 아울러 데이터 스트림 프로세싱 서비스는 이 위치 데이터를 처리하여 지도 데이터를 갱신한다.

사용자 위치 데이터를 저장하려면 엄청난 양의 쓰기 연산을 잘 처리할 수 있으면서 수평적 규모 확장이 가능한 데이터베이스가 필요하다. 카산드라는 그 기준을 잘 만족시키는 후보다.
해당 데이터베이스의 레코드는 다음과 같은 형태다.

지오코딩 데이터베이스

이 데이터베이스에는 주소를 위도/경도 쌍으로 변환하는 정보를 보관한다. 레디스처럼 빠른 읽기 연산을 제공하는 키값 저장소가 이 용도에 적당한데, 읽기 연산은 빈번한 반면 쓰기 연산은 드물게 발생하기 때문이다. 출발지와 목적지 주소는 경로 계획 서비스에 전달하기 전에 이 데이터베이스를 통해 위도/경도 쌍으로 변환되어야 한다.

미리 만들어 둔 지도 이미지

단말이 특정 영역의 지도를 요청하면 인근 도로 정보를 취합하여 모든 도로 및 관련 상세 정보가 포함된 이미지를 만들어 내야 한다. 계산 자원을 많이 사용 할 뿐 아니라 같은 이미지를 중복 요청하는 경우가 많으므로 이미지는 한 번만 계산하고 그 결과는 캐시해 두는 전략을 쓰는 것이 좋다.

이미지는 지도 표시 에 사용하는 확대 수준별로 미리 만들어 두고 CDN을 통해 전송한다. CDN 원 본 서버로는 아마존 S3 같은 클라우드 저장소를 활용한다.

---

서비스

데이터 모델을 살펴봤으니 이제 구글 맵 구현에 가장 중요한 위치 서비스, 지도 표시 서비스, 경로 안내 서비스를 살펴보자 !

위치 서비스

데이터베이스 설계 및 사용자 위치 정보가 이용되는 방식에 초점을 맞추어 상세 설계를 진행하겠다.

사용자 위치 데이터 저장에는 위에서 설명했듯이, 키-값 저장소를 활용한다.

초당 백만 건의 위치 정보 업데이트가 발생한다는 점을 감안하면 쓰기 연산 지원에 탁월한 데이터베이스가 필요하다.

=> NoSQL 키 값 데이터베이스나 열•중심 데이터베이스(column-oriented datalase)가 그런 요구사항에 적합하다. 또 한 가지 유의할 사항은, 사용자 위치는 계속 변화하며 일단 변경되고 나면 이전 정보는 바로 무용해지고 말기 때문에, 데이터 일관성(consistency)보다는 가용성(availability)이 더 중요하다는 점이다.

CAP 정리(theorem)에 따르면 일관성(Consistency), 가용성(Availability), 분할 내성(Partition tolerance) 모두를 만족 시킬 방법은 없다.
그러므로 주어진 요구사항에 근거하여, 본 설계안은 가용성과 분할내성 두 가지를 만족시키는 데 집중한다. 그리고 이 요구사항에 가장 적합한 데이터베이스 가운데 하나는 카산드라다. 높은 가용성을 보장하면 서도 막대한 규모의 연산을 감당할 수 있도록 해 줄 것이다.

데이터베이스 키로는 (user_id, timestamp)의 조합을 사용하며, 해당 키에 매 달리는 값으로는 위도/경도 쌍을 저장한다. 이때 user_id는 파티션 키(partition key)이며 timestamp는 클리스터링 키(clustering key)로 활용한다. user_id를 파티션 키로 사용하는 것은 특정 사용자의 최근 위치를 신속히 읽어 내기 위해서다. 같은 파티션 키를 갖는 데이터는 함께 저장되며 클러스터링 키 값에 따라 정렬된다. 이렇게 해 두면 특정 사용자의 특정 기간 내 위치도 효율적으로 읽어낼 수 있다.

사용자 위치 데이터는 어떻게 이용되는가

사용자 위치는 쓰임새가 다양한 중요 데이터다. 가령 이 데이터를 활용하면 새로 개설되었거나 폐쇄된 도로를 감지할 수 있다. 지도 데이터의 정확성을 점차로 개선하는 입력으로도 활용될 수 있다. 실시간 교통 현황을 파악하는 입력이 될 수도 있다.

이런 다양한 기능들을 지원하기 위해서 사용자 위치를 데이터베이스에 기록하는 것과 별도로 카프카와 같은 메시지 큐에 로깅한다. 카프카는 응답 지연이 낮고 많은 데이터를 동시에 처리할 수 있는 데이터 스트리밍 플랫폼으로, 실시간 데이터 피드(data feed)를 지원하기 위해 고안되었다. 아래 그림은 카프카를 활용하여 개선한 설계안이다.

개별 서비스는 카프카를 통해 전달되는 사용자 위치 데이터 스트림을 각자 용도에 맞게 활용한다. 예를 들어 실시간 교통 상황 서비스는 해당 스트림을 통해 읽은 데이터로 실시간 교통량 데이터베이스를 갱신한다. 경로 안내 타일 처리 서비스는 해당 데이터를 활용해 새로 열린 도로나 폐쇄된 도로를 탐지하고 해당 변경 내역을 객체 저장소의 경로 안내 타일에 반영함으로써 점진적으로 지도의 품질을 개선한다.

지도 표시

이번 절에서는 지도 타일을 미리 만들어 놓는 방법과 지도 표시 최적화 기법을 살펴본다.

지도 타일 사전 계산
앞서 언급했듯이 사용자가 보는 지도 크기나 확대 수준에 맞는 세부사항을 보여주기 위해서는 확대 수준별 지도 타일을 미리 만들어 둘 필요가 있다. 구글 맵은 21단계로 지도를 확대할 수 있으며 본 설계안도 마찬가지다.

확대 수준 0은 세계 전부를 256 x 256픽셀짜리 타일 하나로 표현한다.
확대 수준을 1단계 올릴 때마다 해당 수준을 위한 전체 타일 수는 동서 방향으로 두 배, 남북 방향으로 두 배 늘어난다. 각 타일 크기는 여전히 256 x 256픽 셀이다. 아래 그림에서 보듯, 확대 수준 1에 필요한 타일은 2 x 2장으로, 그 전 부를 합친 해상도는 512 x 512픽셀이다.

확대 수준 2에 필요한 타일은 4 x 4장 으로, 그 전부를 합친 해상도는 1024 x 1024 픽셀이다. 확대 수준을 1단계 늘릴 때마다 해당 수준 전부를 합친 해상도는 그 이전 수준 대비 4배씩 늘어난다. 이 늘어난 해상도 덕에 사용자에게 더 상세한 정보를 제공할 수 있다. 아울러 클라이언트는 해당 정보를 제공하기 위한 타일을 다운 받는데 많은 네트워크 대역폭을 소진하지 않고도 클라이언트에 설정된 확대 수준에 최적인 크기의 지도를 표시할 수 있다. 화면에 한번에 표시 가능한 지도 타일 개수는 달라지지 않기 때문이다.

최적화: 벡터 사용
지도 표시에 WebGL 기술을 채택하면 어떤 혜택이 있을까? 네트워크를 통해 이미지를 전송하는 대신 경로(path)와 다각형(polygon) 등의 벡터(vector) 정보를 보내는 것이다. 클라이언트는 수신된 경로와 다각형 정보를 통해 지도를 그려내면 된다.

벡터 타일의 한 가지 분명한 장점은 이미지에 비해 월등한 압축률이다. 따라서 네트워크 대역폭을 많이 아낄 수 있다.
그다지 뚜렷하진 않지만 기대할 수 있는 또 다른 장점은 훨씬 매끄러운 지도 확대 경험이다. 래스터 방식 이미지(rasterized image)를 사용하면 클라이언트가 확대 수준을 높이는 순간에 이미지가 늘어지고(stretch) 픽셀이 도드라져 보이는 문제가 있다. 시각 효과 측면에서는 상당히 거슬릴 수 있다. 하지만 벡터화 된 이미지를 사용하면 클라이언트는 각 요소 크기를 적절하게 조정할 수 있어서 훨씬 매끄러운 확대 경험을 제공할 수 있다.

경로 안내 서비스

이제 경로 안내 서비스를 좀 더 자세히 살펴보자. 이 기능은 가장 빠른 경로를 안내하는 역할을 담당한다.

해당 그림에 등장하는 각 컴포넌트를 살펴보자.

지오코딩 서비스
우선, 주소를 위도와 경도 쌍으로 바꿔주는 서비스가 필요하다. 주소의 표현 방식은 다양할 수 있다는 점을 고려해야 한다. 즉, 장소 이름으로 나타낸 주소도 있을 수 있고 지번 형태로 나타낸 주소도 있을 수 있다.

다음은 구글 지오코딩 API의 요청/응답 사례다.

요청:
https://maps.googleapis.com/maps/api/geocode/json?address=1600+Amphit
heatre+Parkway, +Mountain+View, +CA

JSON 응답:
{
  "results" : [
    {
    "formatted_address" : "1600 Amphitheatre Parkway, MountainView, CA 94043, USA",
    "geometry": {
    "location" : {
      "lat": 37.4224764,
      "Ing" : - 122.0842499
    },
    "location_type" : "ROOFTOP",
    "viewport" : {
      "northeast": {
        "lat": 37.4238253802915,
        "Ung" : - 122.0829009197085
       }, 
      "southwest": {
        "lat" : 37.4211274197085,
        "Ing" : - 122.0855988802915
      }
    },
    "place_id" : "ChIJZeUgeAK6j4ARbn5u_WAGQWA",
    "plus code": {
        "compound_code": "CWC8+W5 Mountain View, California,
        United States",
        "global_ code": "849VCWC8+W5"
        },
        "types" : [ "street_address" ]
        }
    }
  ],
  "status" : "OK"
}

경로 안내 서비스는 이 서비스를 호출하여 출발지와 목적지 주소를 위도 경도 쌍으로 변환한 뒤 추후 다른 서비스 호출에 이용한다.

경고 계획 서비스

경로 계획 서비스(route planner selvice)는 현재 교통 상황과 도로 상태에 입각하여 이동 시간 측면에서 최적화된 경로를 제안하는 역할을 담당한다. 뒤이어 설명할 다른 서비스들과 통신하여 결과를 만들어 낸다.

최단 경로 서비스

최단 경로 서비스(shortest path service)는 출발지와 목적지 위도/경도를 입력으로 받아 k개 최단 경로를 반환하는 서비스다. 이때 교통이나 도로 상황은 고려하지 않는다. 다시 말해 도로 구조에만 의존하여 계산을 수행한다. 도로망 그래프는 거의 정적이므로 캐시해 두면 좋다.

최단 경로 서비스는 객체 저장소에 저장된 경로 안내 타일에 대해 A* 경로 탐색 알고리즘의 한 형태를 실행한다.

• 입력으로 출발지와 목적지의 위도/ 정도를 받는다. 이 위치 정보를 지오해시 로 변환한 다음 출발지와 목적지 경로 안내 타일을 얻는다.
• 출발지 타일에서 시작하여 그래프 자료 구조를 탐색해 나간다. 탐색 범위를 넓히는 과정에서 필요한 주변 타일은 객체 저장소에서(과거에 가져온 적이 있는 경우에는 캐시에서) 가져온다. 같은 지역의 다른 확대 수준 타일로도 연결이 존재할 수 있음에 유의하자. 고속도로만 있는 더 큰 타일로 진입하 거나 할 수 있는 것은 알고리즘이 그런 연결을 선택할 수 있기 때문이다. 최단 경로가 충분히 확보될 때까지 알고리즘은 검색 범위를 계속 확대해 나가면서 필요한 만큼 타일을 가져오는 작업을 반복할 것이다.

예상 도착 시간 서비스

경로 계획 서비스는 최단 경로 목록을 수신하면 예상 도착 시간 서비스 (ETA service)를 호출하여 그 정로 각각에 대한 소요 시간 추정치를 구한다. 예상 도 착 시간 서비스는 기계 학습을 활용해 현재 교통 상황 및 과거 이력에 근거하여 예상 도착 시간을 계산한다.

이때 까다로운 문제는 실시간 교통 상황 데이터만 필요한 게 아니라 앞으로 10분에서 20분 뒤에 교통 상황이 어떻게 달라질지도 예측해야 한다는 것이다. 이런 문제는 알고리즘 차원에서 풀어야 하며 이번 절에서는 상세하게 다루지 않는다.

순위 결정 서비스
경로 계획 서비스는 ETA 예상치를 구하고 나면 순위 결정 서비스(ranker)에 관 련 정보를 모두 전달하여 사용자가 정의한 필터링 조건을 적용한다. 유료 도로 제외, 고속도로 제외 등이 그런 필터링 조건의 사례다. 순위 결정 서비스는 필터링이 끝나고 남은 경로를 소요 시간 순으로 정렬하여 최단 시간 경로 k개를 구한 다음 경로 안내 서비스에 결과를 반환한다.

중요 정보 갱신 서비스들
이 부류의 서비스는 카프카 위치 데이터 스트림을 구독하고 있다가 중요 데이터를 비동기적으로 업데이트하여 그 상태를 항상 최신으로 유지하는 역할을 담당한다. 실시간 교통 정보 데이터베이스나 경로 안내 타일 등이 그 사례다.

경로 안내 타일 처리 서비스는 도로 데이터에 새로 발견된 도로, 폐쇄되었음이 확인된 도로 정보를 반영하여 경로 안내 타일을 지속적으로 갱신한다. 그 덕에 최단 경로 서비스는 더 정확한 결과를 낼 수 있게 된다.

실시간 교통 상황 서비스는 활성화 상태 사용자가 보내는 위치 데이터 스트림에서 교통 상황 정보를 추출한다. 그 결과로 찾아낸 정보는 실시간 교통 상황 데이터베이스에 반영되며, 예상 도착 시간 서비스가 더욱 정확한 결과를 내는 데 쓰인다.

적응형 ETA와 경로 변경

현 설계안은 적응형 ETA와 경로 변경을 허용하지 않는다. 이 문제를 해결하려면 서버는 현재 경로 안내를 받고 있는 모든 사용자를 추적하면서 교통 상황이 달라질 때 마다 각 사용자의 ETA를 변경해 주어야 한다. 그러려면 다음 중요한 질문에 답할 수 있어야 한다.

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

간단하긴 하지만 그다지 효율적이지 않은 방법부터 살펴보자. 사용자 user_1이 안내 받은 경로가 아래 그림 같이 경로 안내 타일 r_1, r_2, r_3, …, r로 구성되어 있다고 하자.

경로 안내 서비스를 받고 있는 사용자와 그 경로 정보를 데이터베이스에 저장한다고 하면 그 형상은 아마 다음과 같을 것이다.

user_1: r_1, r_2, r_3, ..., r_k 
user_2: r_4, r_6, r_9, ..., r_n 
user_3: r_2, r_8, r_9, ..., r_m
...
user_n: r_2, r_10, r_21, ..., r_1

이때 경로 안내 타일 r_2에서 교통사고가 발생했다고 하자. 어떤 사용자가 영향을 받는지 알아내려면 위의 레코드를 전수 조사해서 어떤 사용자가 해당 타일을 가지고 있는지 알아보아야 한다.

user_1: r_1, _**r_2**_, r_3, ..., r_k
user_2: r_4, r_6, r_9, ..., r_n 
user_3: _**r_2**_, r_8, r_9, ..., r_m
...
user_n: _**r_2**_, r_10, r_21, .... r_1

이 테이블에 보관된 레코드 수가 n이고 안내되는 경로의 평균 길이가 m이라고하면 교통 상황 변화에 영향 받는 모든 사용자 검색의 시간 복잡도는 O(n x m) 일 것이다.

이 검색 속도를 더 높일 방법은 없을까? 다른 접근법을 알아보자.

경로 안내를 받는 사용자 각각의 현재 경로 안내 타일, 그 타일을 포함하는 상위 타일(즉, 확대 수준이 더 낮은 타일), 그 상위 타일의 상위 타일을 출발지와 목적지가 모두 포함된 타일을 찾을 때까지 재귀적으로 더하여 보관하는 것이다.

그 결과를 데이터베이스에 보관한다고 하면 레코드 하나의 형태는 다음과 같을 것이다.

user_1, r_1, super(r_1), super(super(r_1)), ...

이렇게 해 두면, 어떤 타일의 교통 상황이 변했을 때 경로 안내 ETA가 달라지는 사용자는, 해당 사용자의 데이터베이스 레코드 마지막 타일에 그 타일이 속하는 사용자다. 그 이외의 사용자에게는 아무 영향이 없다. 검색 시간 복잡도가 O(n)으로 줄어들기 때문에 좀 더 효율적이다.

그러나 이 접근법은 교통 상황이 개선되었을 때 해야 하는 일까지 해결해주지는 않는다. 예를 들어 경로 안내 타일 2의 교통 상황이 회복되어서 사용자가 옛날 경로로 돌아가도 된다고 하자. 경로 재설정이 가능하다는 사실을 어떻게 감지하고 알릴 것인가? 한 가지 방안은 현재 경로 안내를 받는 사용자가 이용 가능한 경로의 ETA를 주기적으로 재계산하여 더 짧은 ETA를 갖는 경로가 발견되면 알리는 것이다.

전송 프로토콜

경로 안내 중에 경로의 상황이 변경될 수 있으므로, 데이터를 모바일 클라이언트에 전송할 안정적인 방법이 필요하다. 이 경우에 서버에서 클라이언트로 데이터를 보내는 데 활용할 수 있는 프로토콜로는 모바일 푸시 알림(mobile push noification), 롱 폴링(long polling), 웹소켓(webSocket), 서버 전송 이벤트(Server-Sent Events, SSE) 등이 있다.

• 모바일 푸시 알림은 보낼 수 있는 메시지 크기가 매우 제한적이므로 (iOS의 경우에는 최대 4,096바이트) 사용하지 않는 게 바람직하다. 게다가 웹 애플리케이션은 지원하지 않는다.
• 웹소켓은 서버에 주는 부담이 크지 않아서 일반적으로 롱 폴링보다 좋은 방안으로 본다.
• 모바일 푸시 알림과 롱 폴링을 지원하지 않기로 하였으므로 남은 선택지는 웹소켓과 SSE다. 두 방법 모두 괜찮은 방법이긴 하지만 본 설계안에서는 웹 소켓을 사용할 것이다. 양방향 통신을 지원하기 때문인데, 가렁 패키지나 상품이 목적지에 가까워졌을 때는 실시간 양방향 통신이 필요한 경우도 있기 때문이다.

이 모든걸 합친 설계도는 아래와 같다.

4단계 마무리

이번 장에서 우리는 위치 갱신, ETA, 경로 계획, 지도 표시 등의 핵심 기능을 지 원하는 단순화된 구글 맵 애플리케이션을 설계해 보았다. 이 시스템의 확장에 관심이 있다면, 기업 고객 대상으로 중간 경유지 설정 기능을 제공하는 것을 고려해 보면 좋을 것이다. 예를 들어 고객이 하나가 아닌 여러 목적지를 입력하면 그 모두를 어떤 순서로 방문해야 가장 빨리 경유할 수 있을지 실시간 교통 상황을 고려하여 안내하는 것이다. 이런 기능을 제공하면 도어대시(Door Dash), 우버(Uber), 리프트(Lyft) 같은 배달 서비스에 아주 유용할 것이다.