Shortcut 변화 시점만 저장하는 CATCHUp 미래 경로탐색 (2023-01)

출발 시각을 반영하는 Time-Dependent 경로탐색

티맵은 목적지를 고른 뒤 출발 시간을 바꿔 가며 소요시간과 경로를 확인하는 기능을 제공합니다. 이 계산에는 실사용자 GPS 데이터로 만든 예측 교통정보와 맵데이터가 쓰입니다.

핵심은 도로마다 진입 시각을 계산해 그 시점의 교통정보와 유고정보를 쓰는 것입니다. 원문의 예로, 서울에서 부산까지 오전 9시 30분에 출발하는 경로를 구할 때 대구 근처 도로는 오후 1시쯤의 정보로 비용을 계산합니다.

기존 엔진은 AStar 기반으로 이 기능을 제공했습니다. 단방향 Dijkstra나 AStar로 구현하는 일 자체는 어렵지 않았습니다. 다만 사용자와 요청 수의 증가, 장거리 응답 속도, 외부 제공 API의 성능 요구가 AStar로는 풀리지 않아 CCH 기반의 Thor 엔진을 도입했고, 알고리즘을 고를 때부터 시간 의존성을 염두에 두어 CATCHUp을 택했다고 합니다. CCH에 관한 설명은 경로탐색엔진 1편에 있습니다.

시간대별 비용을 모두 저장할 때의 메모리

CATCHUp은 CCH를 시간 의존적 탐색으로 확장한 알고리즘이고, 세 단계로 나뉩니다. Preprocessing은 그래프 구조가 바뀔 때 Shortcut을 만들며 보통 2주에 한 번 돕니다. Customization은 Shortcut의 시간대별 가중치를 계산하며 패턴 교통정보 갱신 주기에 맞춰 하루에 한 번 돕니다. Query는 이렇게 만든 데이터로 경로를 찾습니다.

문제는 메모리였습니다. Shortcut을 포함한 Arc는 약 9천만 개로, 원본 2천만에 Shortcut 7천만을 더한 규모입니다. 5분 단위 스냅샷 하나는 4바이트로 인코딩해 360MB입니다. 그런데 예측 교통정보는 평상시 일주일에 연휴 최대 9일을 합쳐 최대 16일 치를 다뤄야 합니다. 이를 5분 단위로 모두 저장하면 23,040배인 약 8.3TB가 되어, 서버 메모리 증설로는 해결할 수 없다고 원문은 설명합니다.

변화 시점의 경로만 저장하는 Shortcut Unpacking Data

CATCHUp의 아이디어는 비용의 원천인 교통정보는 시간에 따라 많이 변해도, Shortcut을 이루는 Witness-Path는 자주 바뀌지 않는다는 관찰입니다. Customization 단계는 모든 Arc의 비용을 저장하는 대신 Witness-Path가 바뀌는 시점의 경로만 Shortcut Unpacking Data로 남깁니다. 비용과 경로가 필요한 Query 단계에서 이 데이터를 Original Arc가 나올 때까지 재귀적으로 풀어 계산합니다. 구현은 스택을 썼습니다.

Customization은 Shortcut 비용의 하한과 상한도 따로 저장합니다. 뒤의 최적화가 이 값을 씁니다.

Query의 두 단계와 세 가지 최적화

시간 의존적 환경에서는 역방향 탐색 때 도로의 진입 시각을 알 수 없습니다. 그래서 Query를 둘로 나눕니다. 먼저 Elimination Tree를 따라 출발지와 도착지에서 루트까지 올라가며 Subgraph를 만들고, 이 Subgraph에서 정방향 Time-Dependent Dijkstra를 돌립니다. Subgraph에는 최단 경로가 들어 있어 정확도가 보장된다고 합니다.

기본 구현만으로는 성능이 부족해 논문의 최적화 세 가지를 붙였습니다.

• Corridor: 저장해 둔 하한과 상한으로 relaxation을 수행해 더 작은 Subgraph를 만듭니다.
• Lazy Unpacking: 진출 Arc는 풀지 않고 Corridor에 넣어 중복 연산을 줄입니다. 논문에서는 1.3~3배의 성능 향상이 있었다고 합니다.
• Corridor AStar: 하한을 휴리스틱 함수로 써서 AStar로 탐색합니다. 하한은 실제 비용보다 크지 않아 정확성 조건을 만족합니다.

앞의 두 가지만 적용했을 때는 나쁘지 않았지만 예상보다 부족했습니다. 목표는 어떤 경우에도 응답 500ms 이내였습니다.

성능과 도입 결과

Corridor AStar까지 적용한 뒤에는 CPU 사용률 90% 이상에서도 평균 응답이 50ms였고, 400km 이상의 장거리도 평균 300ms 이하였습니다. 측정 인스턴스는 r6g.4xlarge(vCPU 16, 메모리 128GB)입니다.

개발에는 논문 검토부터 기본 기능까지 4~5개월, 최적화와 검증에 2~3개월이 더 걸렸습니다. 미래 시간 길 찾기를 Thor로 옮긴 뒤 자동차 경로탐색 요청을 m6g.12xlarge 서버 2대로 여유 있게 처리합니다. Thor는 사내외 여러 서비스에서 플랫폼 기능으로 쓰이며, 2023년에는 트래픽이 가장 많은 내비게이션 실시간 경로안내로 확장할 준비를 한다고 밝혔습니다.