카카오맵, CCH 알고리즘 도입으로 자전거 길찾기 TPS 70배 향상

카카오맵이 도보 및 자전거 길찾기 서비스의 탐색 엔진을 A 알고리즘**에서 **Customizable Contraction Hierarchies(CCH)**로 전면 개편했다. 기존 A는 휴리스틱을 적용해도 거리가 멀어지면 탐색 시간이 급격히 증가하는 한계가 있었으며, 특히 전국 단위 쿼리를 지원하는 자전거 길찾기에서는 수십 초의 응답 지연이 발생했다.

CCH는 그래프의 연결 구조와 비용을 분리하여 처리하는 알고리즘으로, 비용이 변경되어도 전체 지름길을 재계산하지 않고 일부만 수정하면 된다. 이를 통해 카카오맵은 자전거 길찾기 TPS를 70배, 도보 길찾기 TPS를 3배 향상시켰다. 실제 서버 대수는 1/15로 줄어들었으며, 도보 길찾기의 30km 거리 제한도 해제 가능한 수준으로 성능이 개선됐다.

기술적 최적화

CCH 적용 과정에서 카카오맵은 **Inertial Flow Cutter(IFC)**를 활용해 그래프 파티셔닝을 최적화하고, 회전 비용을 처리하기 위해 Line Graph 변환을 적용했다. IFC Ordering과 재배치(reordering)를 통해 불필요한 간선을 제거함으로써 CCH 그래프의 아크 수를 약 46% 감소시켜 메모리 효율을 높였다.