PathCraft 구축: Go 기반 오픈소스 라우팅 엔진

발행: 5일 전 (2026년 1월 11일 오전 09:43 GMT+9)

11 min read

Source: Dev.to

번역을 진행하려면 실제 기사 내용(텍스트 부분)을 제공해 주시겠어요?
소스 링크는 그대로 유지하고, 제공해 주신 본문을 한국어로 번역해 드리겠습니다.

Introduction

When I started building PathCraft, I had a simple goal: create a routing engine that I could actually understand, extend, and deploy without vendor lock‑in. What began as an experimental side project has evolved into a modular, multimodal routing engine that handles everything from pedestrian navigation to public‑transit routing.

In this post, I’ll share the journey of building PathCraft—architectural decisions, the algorithms powering it, and the lessons learned along the way.

PathCraft란?

PathCraft는 Go 로 작성된 실험적인 도보 및 대중교통 경로 탐색 엔진입니다. 다음과 같은 용도로 설계되었습니다:

재사용 가능한 Go 라이브러리(SDK) 로, 개발자가 애플리케이션에 임베드 가능
CLI 애플리케이션 으로 빠른 경로 질의 수행
HTTP 서버 로, 프로덕션 배포용
임베디드 엔진 으로, 더 큰 시스템에 통합

핵심 철학? 정확성을 최우선, 성능은 그 다음. 많은 경로 엔진이 약간의 성능 향상을 위해 가독성과 유지보수를 희생합니다. PathCraft는 다른 접근 방식을 취합니다.

왜 Go인가?

Reason	Benefit
Performance	컴파일된 특성 덕분에 생산성을 희생하지 않고 거의 네이티브 속도를 제공
Simplicity	최소주의 설계가 PathCraft의 명료성‑우선 철학과 일치
Concurrency	내장된 goroutine과 channel 덕분에 병렬 경로 탐색이 미래에 가능
Single Binary	배포가 쉬움—바이너리만 전달하면 되고 런타임 의존성이 없음
Custom A*	최대 제어와 교육적 가치를 위해 직접 구현
RAPTOR Algorithm	효율적인 대중교통 경로 탐색
OSM Parser	OpenStreetMap 데이터를 읽어 도보 가능한 그래프를 구축
GTFS Parser	대중교통 일정에 대한 General Transit Feed Specification 데이터를 처리
Haversine Calculations	휴리스틱을 위한 지리적 거리 계산

아키텍처

가장 중요한 결정 중 하나는 아키텍처였습니다. 처음에는 헥사고날(포트와 어댑터) 아키텍처를 고려했지만, 최종적으로 모듈형 모놀리쓰 접근 방식을 선택했습니다.

알고리즘 정확성과 빠른 반복에 초점을 맞춘 프로젝트에서는 헥사고날 아키텍처가 불필요한 오버헤드를 초래합니다.
대규모 엔터프라이즈 시스템에 유용한 간접 계층과 추상 경계는 비례하는 이점을 제공하지 못하고 개발 속도를 저하시킬 수 있습니다.

모듈 레이아웃

/internal                → Private core logic
  /graph                → Graph data structures
  /geo                  → Geographic calculations
  /routing              → A*, RAPTOR algorithms
  /osm                  → OpenStreetMap parsing
  /gtfs                 → Transit data parsing

/pkg/pathcraft/engine   → Public API (the only thing users import)
/cmd/pathcraft          → CLI entrypoint
/web                    → Visualization tools

이 구조는 낮은 결합도와 높은 응집도를 유지하면서 시스템을 이해하기 쉽게 만듭니다. 의존성 흐름은 엄격하게 정의되어 있어, 핵심 로직이 인프라스트럭처(HTTP, CLI, 파일 I/O)에 의존하지 않습니다.

워킹 라우터 – A*

PathCraft의 워킹 라우터 핵심은 A* 알고리즘입니다. 작동 방식을 간략히 살펴보면 다음과 같습니다:

A*는 다익스트라 알고리즘(최단 경로 보장)의 장점과 휴리스틱 기반 탐색(빠른 탐색)의 장점을 결합합니다.
각 노드에 대해 다음을 계산합니다

[ f(n) = g(n) + h(n) ]

g(n) – 시작점에서 노드 n까지의 실제 비용
h(n) – n에서 목표까지의 추정 비용(우리의 휴리스틱)
지리적 라우팅에서는 Haversine 공식을 사용해 지구상의 두 지점 사이의 대원 거리를 계산합니다. 이는 허용 가능한 휴리스틱을 제공하는데, 실제 거리를 절대 과대평가하지 않아 최적성을 보장합니다.

알고리즘은 open set을 우선순위 큐로 유지하며, 가장 유망한 노드를 먼저 탐색합니다. Go의 container/heap 패키지가 기본을 제공하고, 사용자 정의 pqItem 구조체가 노드 ID와 우선순위를 추적합니다.

Transit Router – RAPTOR

대중교통을 위해 RAPTOR(Round‑Based Public Transit Optimized Router) 알고리즘을 구현했습니다. 전통적인 그래프 기반 접근 방식과 달리 RAPTOR는 시간표 데이터를 직접 사용합니다.

라운드 – 각 라운드는 하나의 추가 대중교통 구간(환승)을 나타냅니다
노선 스캔 – 표시된 각 정류장에 대해 해당 정류장을 운행하는 모든 노선을 스캔합니다
환승 처리 – 노선 스캔 후, 도보 경로 환승을 처리합니다
파레토 최적성 – 도착 시간과 환승 횟수 두 가지를 모두 추적합니다

왜 RAPTOR인가?

장점	설명
속도	대중교통에 대해 그래프 기반 접근 방식보다 일반적으로 더 빠릅니다
단순성	우아하고 이해하기 쉽습니다
유연성	제약 조건(최대 환승 횟수, 도보 거리 등)을 쉽게 추가할 수 있습니다

공개 API

/pkg/pathcraft/engine에 있는 Engine 구조체는 공개 API 역할을 하며, 외부 사용자가 가져와야 하는 유일한 패키지입니다.

type Engine struct {
    graph     *graph.Graph
    gtfsIndex *gtfs.StopTimeIndex
}

// Core methods
func (e *Engine) Route(req RouteRequest) (RouteResult, error)
func (e *Engine) LoadOSM(path string) error
func (e *Engine) LoadGTFS(stopTimesPath, tripsPath string) error

엔진은 조정 역할을 할 뿐이며, 실제 계산을 수행하지 않습니다. 이러한 분리를 통해 HTTP/CLI와 관련된 내용이 알고리즘에 섞이는 것을 방지합니다.

GTFS 시간 형식 처리

24:00:00을 초과하는 GTFS 시간을 다루는 것이 까다로운 도전이었습니다. 이는 자정을 넘는 서비스를 나타냅니다. 예를 들어, 25:30:00에 출발하는 여행은 다음 날 오전 1:30을 의미합니다.

우리는 /internal/time에 커스텀 time 패키지를 구축하여 이 엣지 케이스를 투명하게 처리하고, 나머지 코드베이스는 깔끔하게 유지했습니다.

Development Principles

Pure Functions – 라우팅 알고리즘은 순수 함수이다. 동일한 그래프와 쿼리를 주면 언제나 같은 결과를 반환한다(숨겨진 상태, 무작위성, 부수 효과가 없음).
Comprehensive Tests – 모든 라우팅 알고리즘은 특히 엣지 케이스에 대해 철저한 테스트를 갖추어야 한다. 라우팅 로직의 버그는 미묘하고 발견하기 어려울 수 있다.
Interface Discipline – 구체적인 필요가 있을 때만 인터페이스를 도입하고, 가상의 미래 요구사항을 근거로 만들지 않는다.
Self‑Documenting Code – 코드는 무엇을 하는지 스스로 설명해야 하며, 주석은 왜 특정 결정을 내렸는지에만 사용한다.

OSM 파싱 및 그래프 구성

(원본 내용이 여기서 잘렸으며, 다음은 다음 섹션을 나타내는 간단한 자리표시자입니다.)

OSM 파싱은 원시 OpenStreetMap 데이터를 보행 가능한 그래프로 변환하며, 노드 중복 제거, 엣지 생성 및 속성 추출(예: footway 태그, 표면 유형)을 처리합니다. 생성된 그래프는 A* 라우터에 직접 전달되어 빠르고 정확한 보행자 경로 탐색을 가능하게 합니다.

빠른 시작

A* 보행 라우팅
CLI 인터페이스
GeoJSON 내보내기
/route 및 /health 엔드포인트를 갖춘 HTTP 서버 모드
GTFS 수집
RAPTOR 알고리즘 구현
기본 지도 시각화
도보 + 대중교통 통합
시간 의존 라우팅
성능 벤치마킹
더 빠른 쿼리를 위한 그래프 축소
캐싱 전략
WASM/JavaScript 바인딩
gRPC API
플러그인 시스템

첫 번째 PathCraft 버전은 놀라울 정도로 단순했습니다. 이는 의도된 것이었습니다 – 무언가 작동하게 만든 뒤 개선해 나가세요.

좋은 Makefile, 일관된 포맷팅, 자동화된 테스트는 큰 이익을 가져옵니다. 도구에 한 시간을 투자하면 나중에 디버깅에 며칠을 절약할 수 있습니다.

문서 작성을 통해 설계를 깊이 고민하게 됩니다. 간단히 설명할 수 없다면, 아마도 충분히 이해하지 못한 것입니다.