카카오맵에서는 도보·자전거 길찾기 서비스를 제공하고 있습니다. 일반적으로 길찾기 서비스는 다음과 같은 과정을 거쳐 서비스됩니다.

도로 형상에서 그래프 형태의 도로 네트워크 구축
출도착점에서 적절한 출도착 간선 선택
경로 탐색 알고리즘으로 최단 경로 생성
경로 후처리 및 가이드 생성

이 중 도로 네트워크 관리나 출도착 간선 선택, 가이드 생성과 같은 부분은 카카오맵 이용자분들의 피드백을 빠르게 수용하여 조금이라도 더 좋은 경로로, 쉽게 이해할 수 있는 방식으로 안내를 하려고 지속적으로 개선하고 있습니다.

하지만 탐색 알고리즘의 경우 길찾기의 응답시간이나 TPS를 가장 많이 좌우하는 부분임에도 불구하고 쉽게 개선을 할 수 없었습니다. 알고리즘 자체의 한계가 뚜렷하고 우회적인 방법으로 처리하는 것에는 한계가 있기 때문에 엔진단에서부터의 개편이 필요한 상황이었습니다.

그러던 중에도 카카오맵 사용자 수는 꾸준히 늘어나고 있었고, 신규 서비스 오픈 등의 이슈가 생기면서 전면적인 개편을 진행하게 되었습니다.

**너무 느린 A* 알고리즘**

기존 서비스에서는 A* 알고리즘을 탐색 알고리즘으로 사용하고 있었습니다.

다익스트라 알고리즘은 확장 가능한 정점을 우선순위 큐에 넣고, 그중 가장 작은 비용의 정점을 꺼내서 검토하는 것을 반복하며, 목적지에 도달하면 종료합니다. 새로운 정점을 검토할 때마다 큐 삭제가, 확장할 때마다 큐 삽입이 발생합니다. 일반적인 경우 삽입/삭제는 보통 O(log n) 의 복잡도를 가지며, 큐의 크기 n 은 탐색 범위에 비례하기 때문에 A* 에서는 휴리스틱한 방법을 추가해 최대한 탐색 범위를 줄입니다.

가장 대표적인 휴릭스틱은 정점에서 도착지까지의 직선거리입니다. 목적지 방향으로 가는 게 최단 경로일 확률이 높기 때문에 이런 곳을 우선적으로 가보면 탐색 범위를 꽤나 많이 줄일 수 있습니다. PathFinding.js에서 두 알고리즘을 시각화해보면 꽤 유의미한 성능 향상이 있다는 것을 알 수 있습니다.

휴리스틱을 사용하면 탐색 범위가 원 형태인 r^2 에서 타원 형태인 rh 로 변경되어 많은 탐색을 줄일 수 있습니다. 하지만 목적지가 먼 경우 여전히 많은 정점을 방문하기 때문에 느립니다. 도보 길 찾기의 경우 모든 쿼리를 30km 이하로 제한했기 때문에 성능이 나쁘지 않았지만, 자전거 길 찾기는 전국 단위의 쿼리를 지원해야 했기 때문에 A*로도 수십 초 이상 필요했습니다.

이미지 출처: https://www.graphhopper.com/blog/2017/08/14/flexible-routing-15-times-faster/

기존에는 최대한 성능을 끌어올리기 위해 거리에 따라 탐색 가능한 도로 등급을 제한하거나, 직선거리에 가중치를 많이 주어 직선에서 떨어진 옆길로 빠지는 경우를 줄이는 등 극단적인 휴리스틱을 사용했었습니다. 하지만 여기서 적용한 휴리스틱대로 탐색한다고 해서 모든 경우의 좋은 경로를 우선적으로 가지는 못합니다. 직선거리가 먼 쪽으로 돌아가는 경우가 최단거리일 수 있고, 도로 등급으로 탐색 정점을 줄이는 방법은 자전거 길찾기에서 큰 도움이 되지 않기 때문입니다.

자동차의 경우 일반적으로 고속도로와 같은 큰 도로를 타기 시작하면 목적지에 다가가기 전까지 작은 도로로 빠져나오지 않고 도로의 구분도 국도, 고속도로, 이면 도로와 같이 명확해서 도로 등급 제한이 큰 효과를 발휘하지만, 자전거 도로의 경우 도로 등급의 구분이 명확하지 않고 중간중간 작은 도로로 가는 쪽이 더 좋은 경우도 많았으며 심지어는 그런 도로를 이용하지 않으면 가능한 경로가 없는 경우도 있었습니다.

더욱 근본적인 문제는 이런 꼼수를 사용하더라도 결국 '거리가 늘어나면 탐색 시간도 심각하게 늘어난다’라는 한계점을 벗어나지 못하기 때문에 더 빠르고 안정적인 방법으로 탐색을 하는 알고리즘이 필요하게 되었습니다.

지름길을 만들어서 찾아보자

효율적인 지름길을 만들어놓고 지름길을 통해 필요한 곳만 탐색한다면 어떨까요? Contraction Hierarchies(CH) 알고리즘은 이 간단한 아이디어에서부터 시작됩니다.

다음과 같이 일자형 그래프가 있을 때, 양 끝 점끼리의 경로를 탐색하려면 중간의 모든 정점을 거쳐서 탐색을 해봐야 합니다.

여기에 하나의 지름길을 만들어두면 어떨까요? 양 끝 점 쿼리의 경우 지름길을 타고 한 번에 탐색을 할 수 있게 됩니다. 하지만 중간에서 끝 점까지의 쿼리는 여전히 많은 정점을 탐색해봐야 하죠.

아니면 아예 모든 정점 쌍 사이에 지름길을 놓는다면 어떨까요? 쿼리는 굉장히 효율적으로 되겠지만, 간선 수가 폭발적으로 늘어나 현실적으로 말이 되지 않습니다. 이렇게 할 바에야 차라리 2차원 배열에 모든 최단 경로를 전처리하는 게 낫겠죠.

하지만 이렇게 적절하게 필요한 곳에만 지름길을 만들면 적은 수의 지름길을 추가하고도 꽤나 효율적으로 탐색할 수 있습니다.

이렇게 CH는 적절하게 지름길을 만들어두고 효율적으로 탐색을 할 수 있게 하는 알고리즘입니다. 여기서 CH는 추가적으로 정점 사이에 랭킹을 두고, 랭킹이 높아지는 쪽으로만 탐색하게 하여 더 효율적으로 탐색할 수 있게 합니다. 그렇기 때문에 Contraction(단축 경로를 생성해서) Hierarchy(계층을 두고 탐색)이라는 이름을 가지게 된 것입니다.

실시간으로 바뀌는 도로 정보 반영

CH는 그래프의 모양이 똑같더라도 간선의 비용(길이, 이동시간, 도로 상태 등등)이 달라지면 지름길도 다르게 생성이 됩니다. 따라서 갑자기 도로가 침수되어 이용을 하지 못한다거나, 인파가 많아져서 이동시간이 길어지는 등의 비용 변화가 생기면 CH는 처음부터 다시 지름길을 만들어주는 작업을 해줘야 하기 때문에 실시간성 이슈에 대응을 하기 힘듭니다.

하지만 Customizable Contraction Hierarchy는 비용에 상관없이 그래프의 연결 관계가 같다면 항상 같은 지름길이 생기고, 여기서 일부 비용이 바뀐다고 해도 그 부분과 연관된 일부 지름길의 비용만 수정하기 때문에 굉장히 빠르게 실시간 비용 변경을 적용할 수 있습니다. 이런 특성 때문에 Customizable이라는 수식어가 붙게 된 거죠.

카카오맵의 도보·자전거 길찾기에서는 실시간성 비용 변경은 없지만 충분히 추가될 수 있는 부분이고, 최단거리 외에도 편안한 길 등의 여러 가지 옵션을 제공할 때에도 CH는 모든 옵션마다 그래프 자체가 달라지지만 CCH는 같은 그래프에서 비용 값만 따로 저장을 하는 식으로 효율적으로 처리할 수 있기 때문에 CCH 알고리즘을 신규 엔진에서 사용할 탐색 알고리즘으로 정하게 되었습니다.

신규 개편에서 구현한 CCH 를 통해 수행된 탐색을 시각화하면 엄청나게 적은 범위를 탐색하고도 서울에서 부산까지의 최적경로를 탐색하는 것을 볼 수 있습니다.

빨간 부채꼴 모양은 출발지인 파주시에서부터 탐색한 정점들이고, 초록 부채꼴 모양은 도착지인 부산에서부터 탐색한 정점들입니다. 빨간 삼각형과 초록 원이 만나는 곳은 출도착지의 마지막 탐색 정점과 인접한 곳이 만나는 지점입니다.

CCH 특성상 마치 지도를 여러 파트로 쪼개놓고 경계선 부분을 따라 탐색하는 것처럼 탐색하는 것을 볼 수 있습니다.

서비스 성능 향상

**“그래서 도대체 CCH를 사용하면 얼마나 효과가 있는 거지?”**라는 궁금증이 있으신 분들을 위해 결과부터 말씀드리면 굉장한 수준으로 개선되었습니다.

TPS

자전거 : 70배 향상

도보 : 3배 향상

30km 거리 제한이 있는 도보 길찾기는 약 3배 정도의 성능 향상이 있었지만, 전국 단위 탐색이 가능한 자전거 길찾기는 약 70배 정도 성능이 향상됐습니다.

실제 자전거 길찾기 서버 수도 1/15로 줄어들었고, 그마저도 기존 서비스보다 수용 가능한 TPS가 훨씬 늘어난 상태입니다.

도보 길찾기의 경우에도 예전에는 성능 이슈와 필요성에 대한 의문으로 30km 거리 제한을 두었지만, 현재는 별다른 이슈 없이 의사결정만 있으면 바로 거리 제한을 해제해도 문제없을 정도로 개선되었습니다.

응답시간

응답시간 역시 자전거의 경우 기존에는 4초 넘게 탐색을 해도 결과를 못 찾는 경우가 있었는데, 현재는 높게 튀는 경우 없이 안정적이고 빠르게 개선되어 카카오맵 사용자들이 조금 더 쾌적한 환경에서 서비스를 이용할 수 있게 되었습니다.

CCH 알고리즘

CCH가 어떤 기준으로 지름길을 만들고 어떻게 비용을 전처리하며 쿼리는 어떻게 하는지 대한 상세한 내용이 궁금하신 분들을 위해 조금 더 자세하게 정리해보았습니다.

장단점

우선 CCH의 장단점부터 살펴보면 다음과 같습니다.

장점

빠른 쿼리 (놀랍게도 우선순위 큐를 사용하지 않고 탐색을 합니다.)
거리와 거의 상관없는 균일한 쿼리 성능
빠른 간선 가중치 업데이트

단점

긴 전처리 시간
간선 수 증가로 인한 메모리 증가
길찾기 옵션별 가중치 전처리로 인한 메모리 증가 (카카오맵에서의 큰길 우선, 최단거리, 편안한 길 모두 따로 전처리를 하고 있습니다.)
효율적인 1:N 탐색 불가 (출도착 후보지 개수에 비례해서 탐색 시간이 늘어납니다)

CH 알고리즘

CCH를 알아보기 전에 기본이 되는 아이디어인 CH 알고리즘을 알아놓으면 이해하기가 쉽습니다.

CH 알고리즘에서는 정점에 랭크를 매기고, 랭크가 낮은 순으로 정점을 뽑아가며 지름길을 만드는 Contraction이라는 작업을 합니다. 그 후 Contraction이 완료된 정점은 전처리 과정이 끝날 때까지 임시적으로 제외합니다.

Contraction 은 현재 정점 u 가 뽑혔을 때, u 와 인접한 정점 s, t 에 대해 경로 P(s,u,t) 가 s 에서 t 로 가는 최단 경로인 경우 dist(s, u) + dist(u, t) 값을 가진 지름길을 추가하는 작업입니다.

예를 들어 아래와 같이 검은색 점선과 실선이 원본 간선인 그래프에서 정점의 랭크를 매기고 1번 정점을 Contract 하면 빨간색 실선의 지름길이 추가됩니다.

2→3 의 최단 경로가 P(2, 1, 3) 이고, 2→4 의 최단 경로가 P(2, 1, 4) 이기 때문입니다.

그러나 3→4 의 경우 P(3, 1, 4) 가 아닌 P(3, 5, 4) 가 최단 경로이기 때문에 지름길이 추가되지 않습니다.

이렇게 지름길이 생성된 그래프에서 u→v 최단 경로를 쿼리 할 때는 u, v 양쪽에서 시작하는 양방향 다익스트라로 탐색을 하는데, 이미 지름길에 랭크가 낮은 쪽으로 탐색하는 경우가 포함되어 있기 때문에 현재 정점보다 랭크가 높은 쪽으로만 탐색하도록 하여 쿼리 성능을 높입니다.

전처리

CH에서는 지름길 추가와 비용 전처리를 동시에 진행하지만, CCH 에서는 이것을 두 단계로 나눠서 처리합니다.

그래프 형태만 보고 지름길로 사용할 수 있는 간선 추가
각 간선마다의 비용 전처리

Contraction (지름길 간선 추가)

CCH의 Contraction은 비용과 상관없이 그래프의 형태만 보고 진행합니다.

CH와 비슷하게 정점마다 랭크를 매기고 Contraction을 진행하는데, 이때 CCH에서는 최단 경로와 상관없이 u 와 인접한 모든 정점들 사이에 지름길을 추가하게 됩니다.

// rank가 낮은 순으로 돌면서 contraction을 합니다.
for (int rank = 0; rank < n; ++rank) {
  Vertex u = graph.getVertexByRank(rank);
  Vertex minNeighbor = graph.getUpperRankedNeighbors(u)).stream()
    .min(Comparator.comparing(Vertex::getRank))
    .orElseGet(null);
  for (Vertex v : graph.getUpperRankedNeighbors(u)) {
    if (v != minNeighbor) {
      graph.addEdge(minNeighbor, v);
    }
  }
}

예를 들어 1번 정점을 Contract 하면 인접한 2, 3, 4 정점들 사이에 모두 지름길을 추가해 줍니다. CH와 비교하면 3→4 간선도 추가된 것을 알 수 있습니다.

Contraction이 끝나면 그래프는 아래와 같이 Chordal 한 형태가 되며, 이 특성은 비용 전처리에서 유용하게 쓰입니다.

정점에 랭크를 매기는 Ordering에 따라 지름길 간선이 추가되는 수와 형태가 매우 달라지기 때문에 효율적인 Ordering을 하는 것이 CCH에서는 중요한 과제입니다. 이 부분은 뒤의 최적화 부분에서 다루겠습니다.

Metric Customization (비용 전처리)

그래프의 Chordal 한 특성에 따라 모든 아크는 특정 삼각형들의 변에 속하게 됩니다.

여기에 아크의 두 정점의 랭크와 나머지 한 정점의 랭크의 관계에 따라 각 아크에 대한 lower/intermediate/upper triangle들을 정의할 수 있습니다.

예를 들어 아래와 같은 삼각형은 각 아크에 따라 다르게 정의됩니다.

2→3 에 대해서 lower triangle
1→3 에 대해서 intermediate triangle
1→2 에 대해서 upper triangle

실제 탐색에서는 CH와 마찬가지로 랭크가 상승하는 쪽으로만 탐색을 할 것이기 때문에, 랭크가 낮은 쪽으로 가는 경우를 비용 전처리 단계에서 처리해 줘야 합니다.

from, to 정점의 랭크로 비교했을 때 랭크가 낮은 아크부터 bottom-up으로 순회하며 아크의 lower triangle 을 이용하는 것이 최단 경로인지 처리를 합니다.

즉, 아크 x→y 에 대해 처리할 때 lower triangle (x, y, z_i)를 돌면서 C(x, y) = min(C(x, y), C(x, z) + C(z, y))를 계산합니다.

// 편의를 위해 아크 방향성에 상관없이 같은 비용을 가진다고 가정했을 때의 Customization
for (Arc arc : graph.getAllArcsSortedByRank()) {
  long minLowerCost = graph.getLowerTriangle(arc).stream()
    .map(lowerTriangle 
         -> lowerTriangle.fromSideArc().getCost() + lowerTriangle.toSideArc().getCost())
    .min();
  if (minLowerCost < arc.getCost()) {
    arc.setCost(minLowerCost);
  }
}

최초 Customization 이후에 일부 아크의 가중치만 바뀌는 경우, 전체 아크를 모두 업데이트하지 않고 업데이트가 필요한 아크만 골라서 Customize를 하면 빠르게 변경사항을 적용시킬 수 있습니다.

비용이 바뀐 아크들을 랭크를 기준으로 하는 우선순위 큐에 넣고 큐가 빌 때까지 위와 같은 방식으로 Customize를 진행하는데, 현재 아크의 비용이 바뀐 경우 이것에 영향을 받을만한 상위 아크들도 큐에 추가해 줍니다.

x→y 아크의 비용이 변경된 경우 intermediate triangle (x, i, y)과 upper triangle (x, y, u)를 돌며 기존에 i→y나 y→u 가 x→y를 이용한 경로를 최단 경로로 사용하고 있었는지 확인합니다.

만약 그런 경우, x→y 비용 변경에 따라 해당 아크들의 비용도 변경되었을 가능성이 있어서 큐에 추가해 소음과 줘야 합니다. 혹은, 새로운 비용이 기존 비용보다 작을 경우에도 최단 경로가 갱신될 수 있기 때문에 이 경우 무조건 두 아크를 큐에 추가해 줘야 합니다.

priorityQueue.addAll(toBeUpdatedArcs);
while (!priorityQueue.empty()) {
  Arc arc = priorityQueue.poll();
  long oldCost = arc.getCost();
  long newCost = calcNewCost(arc); // 이전 코드와 같은 방식으로 새로 바뀔 값을 계산합니다.
  if (newCost != oldCost) {
    boolean costReduced = newCost < oldCost;
    for (Triangle itmTriangle : graph.getIntermediateTriangles()) {
      Arc fromSide = itmTriangle.fromSideArc();
      Arc toSide = itmTriangle.toSideArc();
      // C(i, y) == C(i, x) + oldC(x, y) 이면 업데이트 큐에 추가합니다.
      if (costReduced || toSide.getCost() == fromSide.getCost() + oldCost) {
        priorityQueue.add(toSide);
      }
    }
    for (Triangle itmTriangle : graph.getIntermediateTriangles()) {
      Arc fromSide = itmTriangle.fromSideArc();
      Arc toSide = itmTriangle.toSideArc();
      // C(y, u) == oldC(y, x) + C(x, u) 이면 업데이트 큐에 추가합니다.
      if (costReduced || toSide.getCost() == oldCost + fromSide.getCost()) {
        priorityQueue.add(toSide);
      }
    }
    arc.setCost(newCost);
  }
}

경로 쿼리

비용 전처리 단계에서 하위 랭크 정점을 통한 경로는 전처리된 상태이기 때문에 탐색은 상위 랭크로 가는 방향으로만 해도 됩니다.

CH처럼 양방향 다익스트라를 사용하여 출도착 지점으로부터 상위 랭크로 향하는 아크로만 탐색을 해도 되지만, Elimination Tree라는 개념을 이용하면 우선순위 큐 없이도 탐색을 할 수 있습니다.

Elimination Tree 란 CCH 그래프에서 각 정점마다 상위 랭크인 이웃 중 랭크가 가장 작은 정점으로 가는 아크만을 남겨두어 트리 형태로 만든 것입니다.

s→t 최단 경로를 탐색할 때, 다음과 같이 우선순위 큐 없이 Elimination Tree를 사용해 탐색할 수 있습니다.

forward/backward 탐색에서 사용할 최단거리 저장 배열인 d_f, d_b를 ∞ 로 초기화 해놓습니다.
Elimination Tree에서 s, t 의 최소 공통 조상인 x 를 구합니다.
s→x 트리 경로의 정점을 순서대로 순회하며 d_f를 relax 합니다.
t→x 트리 경로의 정점을 순서대로 순회하며 d_b를 relax 합니다.
d_f® + d_b® 가 최소가 되는 r 을 지나는 경로가 최단경로가 됩니다.

CCH에서의 Elimination Tree 높이는 굉장히 낮기 때문에 실제로는 굉장히 적은 범위만을 탐색하게 됩니다. 또한 실제 거리와는 상관없이 일정한 쿼리 성능을 가지게 됩니다.

실제 경로를 찾을 때는 CCH 그래프의 아크가 지름길일 수도 있어서 unpack 하는 과정을 거쳐야 합니다.

아래 그림과 같이 CCH 아크로 이루어진 경로 P(p(1) … p(k)) 가 있을 때 각각의 CCH 간선을 unpack 해야 하는데, u→v 아크를 unpack 할 때 해당 arc의 lower triangle (u, v, x)을 순회하며 C(u, v) = C(u, x) + C(x, v) 이면 unpack(u, x), unpack(x, v) 로 재귀적으로 경로를 구합니다.

private void unpackPath(Arc arc, List resultPath) {
  for (Triangle lowerTriangle : graph.getLowerTriangle(arc)) {
    Arc fromSideArc = lowerTriangle.fromSideArc();
    Arc toSideArc = lowerTriangle.toSideArc();
    if (arc.getCost() == fromSideArc.getCost() + toSideArc.getCost()) {
      unpackPath(fromSideArc, resultPath);
      unpackPath(toSideArc, resultPath);
      return;
    }
  }
  resultPath.add(arc);
}

최적화

Ordering

Contraction 과정에서 어떻게 정점들의 순서를 매기느냐에 따라 CCH 성능이 많이 달라집니다. 좋은 Ordering일수록 추가적으로 생성되는 지름길 간선 수가 적고, Elimination Tree의 깊이도 균일하고 얕게 형성되기 때문입니다.

CCH에서는 균형 잡힌 그래프 파티셔닝을 통해 Ordering을 합니다. 균형 잡힌 그래프 파티셔닝이란 그래프에서 일부 정점들을 Separator로 분류하고 삭제하여 두 개 이상의 파트로 최대한 균일하게 Separator에 속하는 정점은 최대한 적게 쪼개는 작업입니다.

예를 들어 아래의 그래프에서는 빨간 정점을 Separator로 쪼개는 것이 좋은 파티셔닝 방법입니다.

이 그래프 파티셔닝을 CCH Ordering에 사용하면 좋은 결과를 얻을 수 있습니다.

그래프를 G라고 하고, G의 separator가 S, 분리된 두 부분 그래프가 A, B 일 때 Ordering 결과를 f(G)라고 할 때 다음과 같이 재귀적으로 그래프 파티셔닝을 하며 Ordering을 합니다.

f(G) = { f(A), f(B), S }

원본 논문에서는 NDMetis와 KaHIP을 파티셔닝 툴로 소개하고 있으며, 카카오에서는 CCH에서 더 유리한 네트워크 플로우 기반 파티셔닝 방식인 Inertial Flow Cutter를 오픈소스로 사용하고 있습니다.

글 윗부분에서 CCH 탐색을 시각화했을 때 그래프의 separator 을 타고 탐색을 하는 것처럼 시각화된 이유가 ordering 자체를 그래프 파티셔닝에 따라 했기 때문입니다. 같은 separator의 정점들은 elimination tree 상의 인접한 곳에 위치하게 되고, separator 을 건너뛰며 탐색하기 때문에 트리 높이가 낮아지는 것입니다.

Line Graph 사용

길찾기 서비스에서 아크의 비용뿐 아니라 아크와 아크의 관계에서 존재하는 비용을 처리해야 할 때도 있습니다.

아래 그림과 같이 도로 속성이 변할 때 비용을 추가하고 싶거나 좌회전 불가와 같은 로직을 추가하고 싶으면 현재 아크뿐 아닌 직전에 지나온 아크의 정보도 필요합니다.

회전 제어 그림의 북쪽 아크의 입장에서 남쪽 아크에서 온 경우에는 문제없이 지나갈 수 있지만, 서쪽 아크에서 온 경우에는 지나갈 수 없고, 이때 비용은 ∞ 로 처리해야 합니다.

이런 아크와 아크의 관계를 처리하기 위해 기본적인 그래프를 Line Graph라는 형태로 바꿔서 처리하는데, Line Graph 란 정점이 기본 그래프의 아크가 되고, 아크가 기본 그래프의 아크와 아크의 관계가 되도록 변환한 그래프입니다.

아래의 그림처럼 검은색으로 그려진 것이 기본 그래프일 때, Line Graph는 노란색으로 그려진 그래프가 됩니다.

이렇게 Line Graph로 만들고 나면 v4→v2→v3 회전 불가 로직을 단순히 e4→e5 아크의 비용을 ∞ 로 두는 것으로 구현할 수 있습니다.

당연하게도 일반 그래프를 Line Graph 형태로 변환하게 되면 그래프의 크기가 훨씬 커지고 CCH 그래프로 지름길 간선을 추가하게 되면 그 크기는 훨씬 커지게 됩니다.

Line Graph를 위한 CCH 빌드

Line Graph의 아크들을 자세히 보면 논리적으로 맞지 않는 아크들이 있습니다. e3→e1 의 경우 실제로는 (v2→v4) → (v1→v2) 인데, 이것은 존재할 수 없는 아크입니다. 하지만 CCH에서는 그래프가 무향 그래프임을 가정하고 있어서 아크 자체를 삭제할 수는 없기 때문에, 이런 아크들은 ∞ 을 부여하게 되고, 편의상 항상 무한인 아크라고 부릅니다.

이런 항상 무한인 아크들이 존재하기 때문에 CCH에서 추가되는 지름길 아크들도 항상 무한인 경우가 있고, 만약 양방향으로 항상 무한인 경우 아예 간선 자체를 없앨 수도 있습니다.

따라서 좀 더 똑똑하게 Ordering 을 하면 지름길 간선 수도 줄이고, 항상 무한인 아크 수도 늘릴 수 있습니다.

Inertial Flow Cutter 는 네트워크 플로우와 컷 개념을 통해 그래프 파티셔닝을 합니다. 네트워크 플로우란 그래프에서 source와 sink 정점을 정해두고 각 아크마다 허용 가능한 플로우의 capacity 가 정해진 상태에서, source → sink로 파이프에 물을 흘려보내듯이 경로 사이의 모든 아크에 플로우를 보내는 것을 말합니다. 컷이란 그래프에서 일부 아크를 제외하여 그래프를 여러 개로 쪼개는 것을 말합니다. 이 네트워크 플로우와 컷은 아주 밀접한 관계가 있으며, 균형 잡힌 그래프 파티셔닝에서도 유용하게 사용할 수 있습니다.

Line Graph에서 separator를 찾는다는 것은 일반 그래프에서의 minimum balanced cut 을 찾는 것과 같습니다.

이렇게 찾아진 separator(cut)의 순서를 아크의 방향성에 따라 묶어서 정하면 양방향으로 항상 무한인 간선의 수를 늘릴 수 있습니다.

아래 그림처럼 S_l→S_r 방향의 아크(LineGraph의 정점) (5,6), (3,4), (1,2)를 먼저 Ordering 하면, Metric Customization 단계에서 비용을 전처리 할 때 랭크가 더 낮은 곳을 통해서 갈 수 있는지 만을 체크하기 때문에 세 아크(정점) 사이의 간선은 항상 무한인 간선이 됩니다. 해당 아크를 타고 S_l → S_r 로 갈 수는 있지만, S_r → S_l 로 되돌아오는 아크들은 모두 세 아크보다 랭크가 높기 때문에 이용할 수 없기 때문에 (5,6) → (S_r→S_l) → (3,4) 와 같이 가는 방법은 존재할 수 없습니다.

즉, 그래프 파티셔닝에서 separator를 알고 있다는 가정 하에 방향성에 따라 효율적으로 ordering을 하는 것입니다.

카카오에서는 이것을 일반 그래프 기준으로 아크 기반 IFC Ordering 을 한 후, 해당 Ordering에서 separator 들을 역추적하고 위와 같은 방법으로 reordering 하여 항상 무한인 간선을 최대한 늘려서 사용하고 있습니다.

아크 기반 IFC Ordering 이 아니더라도 Line Graph 자체에서 NDMetis와 같은 방법으로 Ordering을 하고 reordering 을 해도 되지만, 아크 기반 IFC Ordering을 하는 것이 가장 성능이 좋았습니다.

수치 측정

Elimination Tree 높이

평균 : 662.43

최대 : 1,158

쿼리 중 relaxing 횟수

평균 : 66,860.65

최대 : 157,563

1:1 쿼리에서 많이 탐색해봤자 2,316 개의 정점만을 방문하고, 방문한 정점들과 인접한 정점들에 대한 relax가 많아봤자 315,126 번만 하는 것을 보면 굉장한 성능 향상이 있다는 것을 알 수 있습니다. 다익스트라 기반 알고리즘을 사용할 경우 50만 개가 넘는 정점을 방문하고, relax를 수백만 번 해도 경로를 못 찾는 경우도 많은데 CCH는 어떤 쿼리에 대해서도 안정성 있게 경로를 찾을 수 있습니다.

전처리 단계별 그래프 크기

단계	정점 수	아크 수
기본 도로 네트워크	5M	13M
Line Graph 변환	13M	60M
CCH Graph (NDMetis 사용)	13M	270M
CCH Graph (IFC 사용)	13M	250M
CCH Graph (IFC 사용 후 항상 무한인 간선 제거)	13M	119M

마치며

결론적으로 CCH는 전처리를 했을 때 늘어나는 간선 수(2배~4배)를 감당할 수 있고, 거리가 멀고 출도착 후보지가 적은 쿼리가 자주 들어오며, 길찾기 옵션 수가 너무 많지 않고, 실시간으로 비용이 업데이트되는 길찾기 서비스에 유용합니다.

카카오맵에서는 도보·자전거 길찾기 서비스가 이 특성에 아주 잘 맞았고, 여러 시행착오 끝에 실 서비스가 가능한 수준으로 개편을 할 수 있었습니다.

이 글에서는 CCH에 대해서만 중점적으로 다뤘지만 실제로는 그것 외에도 메모리 최적화, 알고리즘과 서비스를 분리할 수 있는 코드 구조 설계, CCH에는 적용할 수 없는 비즈니스 로직의 우회적인 적용 등 많은 이슈가 있었습니다. 이런 이슈들을 하나씩 처리하며 많은 수의 객체가 생성될 때는 객체에 여러 필드를 두기보다 필드의 배열 형태로 관리하는 것이 메모리에 유리하다는 것 등을 배우고 코드 구조에 대한 고민, 데이터 빌드 프로세스에 대한 고민을 하고 기존 서비스와 달라지는 결과 테스트 및 수정 등을 해보며 많은 것을 배울 수 있었습니다. 긴 글 읽어주셔서 감사합니다.

참고

- Julian Dibbelt, Ben Strasser and Dorothea Wagner. 2015. Customizable Contraction Hierarchies. Karlsruhe Institute of Technology
- V. Buchhold, D. Wagner, Tim Zeitz, Michael Zündorf. 2020. Customizable Contraction Hierarchies with Turn Costs. Karlsruhe Institute of Technology
- Lars Gottesbüren *, Michael Hamann, Tim Niklas Uhl and Dorothea Wagner. 2019. Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies. Karlsruhe Institute of Technology
- InertialFlowCutter

카카오맵이 빠르게 길을 찾아주는 방법: CCH를 이용한 개편기