Topological Sort 기반 DAG에 Skip Set을 도입한 런타임 분기 제어 설계

Building a DAG Orchestrator That Rewrites Its Own Execution Plan

Kingsley Onoh2026년 4월 18일8분advanced

AI 요약

Context

기존 Linear DAG 모델의 Topological Sort 구조로는 조건부 분기(Branching) 처리가 불가능한 한계 발생. BPMN이나 Airflow 방식의 그래프 구조 변경은 Path Explosion으로 인한 설계 복잡도 증가와 파서의 검증 로직 중복 문제를 초래함.

Technical Solution

Topological Sort 결과인 Flat List를 유지하며 런타임에 실행 여부를 결정하는 Mutable Skip Set 도입
Condition Step 실행 시 Jinja2 표현식을 평가하여 선택되지 않은 Branch의 Step ID들을 Skip Set에 추가하는 구조
State Machine에 'skipped' 상태를 정의하여 실행 순서 변경 없이 해당 Step을 즉시 건너뛰는 메커니즘 구현
Dependency Resolver 수정으로 모든 선행 Step이 'completed' 또는 'skipped' 상태일 때만 실행 가능하도록 조건 완화
Jinja2의 텍스트 반환 특성을 처리하기 위해 _FALSY_VALUES Frozenset을 정의한 Truthiness 평가 로직 적용

실천 포인트

1. 분기 로직 도입 시 그래프 구조 자체를 변경하기보다 상태 기반의 스킵 메커니즘 검토

2. 조건부 실행 환경에서 선행 작업의 '실패'와 '건너뜀'을 명확히 구분하여 하위 작업의 블로킹 여부 결정

3. 템플릿 엔진 사용 시 반환 타입의 불일치(String vs Boolean)를 해결할 전역 Truthiness 기준 수립

태그

#Jinja2 #DAG #Orchestration #State Machine #Topological Sort

원문 읽기