DAG

DAG 는 일과 일 사이의 앞뒤 순서를 담아 두고, 무엇부터 해야 하는지를 정해 주는 그래프입니다. 화살표를 아무리 따라가도 떠나온 곳으로 다시 돌아오지 않습니다. 돌아오는 길이 없어서 순서가 언제나 하나는 나옵니다.

쉽고 빠른 이해

DAG 는 일 사이의 앞뒤 순서를 담는 그래프입니다. 빌드에서 "컴파일이 끝나야 테스트를 돌린다" 같은 조건을 여기에 적어 둡니다.

순서를 목록 하나로 적으면 나란히 해도 되는 일까지 줄을 세우게 됩니다. 어떤 일이 어떤 일을 기다리는지만 적어 두면 나머지 순서는 기계가 알아서 풉니다.

도는 모양은 셋입니다.

1. 일마다 점을 하나씩 둡니다
2. "이것이 끝나야 저것을 한다" 를 화살표로 잇습니다
3. 화살표를 거스르지 않는 순서를 뽑아 그대로 실행합니다

대가가 있습니다. 화살표가 한 바퀴 돌아 제자리로 오면 순서를 못 뽑습니다. 그런 고리가 생겼는지 늘 확인해야 하고, 찾으면 멈추는 수밖에 없습니다.

상세

아침에 집을 나서는 차례를 떠올려 봅니다. 양말을 신어야 신발을 신을 수 있고, 셔츠를 입어야 외투를 걸칠 수 있습니다. 반대로 양말과 셔츠 사이에는 그런 조건이 없어서 어느 쪽을 먼저 해도 됩니다. DAG 는 이렇게 "무엇 다음에 무엇" 만 적어 두고 나머지는 열어 두는 방식입니다.

DAG 는 Directed Acyclic Graph 의 줄임말이고, 우리말로는 방향 비순환 그래프라고 옮깁니다. 그래프는 점과 점을 선으로 이어 관계를 적는 자료구조입니다. 점을 노드, 잇는 선을 간선이라고 부릅니다.

이름의 앞 낱말인 방향은 간선마다 화살표가 붙는다는 뜻입니다. 화살표는 한쪽으로만 흐릅니다. 이런 그래프를 방향 그래프라고 부릅니다.

뒤 낱말인 비순환은 그 화살표를 계속 따라가도 출발한 노드로 돌아오는 길이 없다는 뜻입니다. 돌아오는 길을 고리라고 부릅니다. 순환이라고도 합니다.

아래는 빌드 과정을 DAG 로 적은 것입니다.

flowchart TD
    A["의존성 내려받기"] --> B["컴파일"]
    A --> C["코드 검사"]
    B --> D["테스트"]
    C --> D
    D --> E["패키징"]

테스트는 컴파일과 코드 검사가 둘 다 끝나야 시작합니다. 컴파일과 코드 검사 사이에는 화살표가 없습니다. 둘은 서로를 기다리지 않아도 됩니다.

고리가 없다는 조건

이 소절은 비순환이라는 조건이 무엇을 지켜 주는지 봅니다. 견줄 상대는 고리가 있는 그래프입니다.

flowchart TD
    F["문서 만들기"] --> G["번호 매기기"]
    G --> H["목차 뽑기"]
    H --> F

셋 모두 앞선 일이 끝나기를 기다립니다. 무엇부터 해야 하느냐고 물으면 답이 없습니다. 어느 것을 골라도 아직 안 끝난 일을 기다리고 있기 때문입니다.

고리가 하나라도 있으면 순서를 못 뽑습니다. 빌드 도구가 서로를 필요로 하는 모듈을 만났을 때 오류를 내고 멈추는 것이 이 때문입니다. 그래서 비순환은 장식이 아니라 이 모양의 쓸모를 만드는 조건입니다.

순서를 뽑는 절차

화살표를 거스르지 않는 한 줄 순서를 뽑는 절차를 위상 정렬이라고 부릅니다. 앞선 일이 뒤에 오지 않도록 노드를 한 줄로 늘어놓는 것입니다.

절차는 이렇습니다. 들어오는 화살표가 하나도 없는 노드를 찾아 먼저 내보냅니다. 그 노드와 거기서 나가는 화살표를 지웁니다. 남은 그래프에서 같은 일을 되풀이합니다.

들어오는 화살표가 없는 노드를 하나도 못 찾았는데 노드가 남아 있다면, 남은 부분에 고리가 있는 것입니다. 위상 정렬은 순서를 뽑는 절차이면서 고리를 찾는 절차이기도 합니다.

뽑히는 답은 하나가 아닐 수 있습니다. 앞 그림에서는 컴파일과 코드 검사 중 어느 쪽을 먼저 적어도 화살표를 거스르지 않습니다. 화살표로 묶이지 않은 두 일은 어느 쪽을 먼저 해도 되고 함께 해도 됩니다. 빌드 도구가 여러 작업을 동시에 띄울 수 있는 근거가 여기에 있습니다.

비용은 노드와 간선을 한 번씩 훑는 만큼입니다. 노드 수를 V, 간선 수를 E 라고 적으면 O(V+E) 로 씁니다. 고리를 찾는 일이 같은 절차 안에서 끝나므로 비용이 따로 붙지 않습니다.

트리와 갈리는 대목

트리도 화살표를 따라가면 되돌아오지 않는 모양입니다. 그래서 트리는 전부 DAG 입니다. 반대는 성립하지 않습니다.

갈리는 대목은 한 노드로 들어오는 화살표 수입니다. 트리에서 한 노드는 부모를 하나만 갖습니다. DAG 에서는 여러 노드가 같은 노드를 가리킬 수 있습니다.

앞 그림의 테스트가 그렇습니다. 컴파일과 코드 검사 둘에서 화살표를 받습니다. 여럿이 기다리던 일이 한 곳에서 합쳐지는 모양은 트리로는 적을 수 없습니다.

셋을 나란히 놓으면 이렇습니다.

가운데 줄이 DAG 가 서 있는 칸입니다. 트리만큼 순서가 잘 정해지면서, 갈라졌다 합쳐지는 모양까지 적을 수 있습니다.

어디에서 만나나

DAG 는 순서 있는 일을 다루는 곳마다 나옵니다. 노드와 화살표가 가리키는 것만 다르고 모양은 같습니다.

표에 나오는 오케스트레이터는 여러 작업을 정해진 차례대로 돌려 주는 도구를 말합니다.

표의 셋째 줄을 조금 더 봅니다. Git의 커밋 이력이 DAG 입니다. 병합 커밋은 앞 커밋을 둘 가리킵니다. 부모가 둘이므로 트리가 아닙니다.

Airflow 같은 오케스트레이터에서는 이 낱말이 한 겹 더 쓰입니다. 거기서 DAG 는 돌릴 파이프라인 하나를 통째로 가리키는 이름이기도 합니다. "DAG 를 하나 만든다" 는 말은 작업 사이의 순서를 적는다는 뜻이면서, 돌아갈 워크플로 하나를 정의한다는 뜻입니다.

담기지 않는 것

DAG 는 순서만 적습니다. 각 일이 얼마나 걸리는지, 실패하면 어떻게 하는지는 이 모양에 들어 있지 않습니다. 그런 것은 그래프를 돌리는 쪽이 따로 들고 있어야 합니다.

되풀이도 그대로는 못 담습니다. "조건이 맞을 때까지 앞으로 돌아간다" 는 곧 고리라서, DAG 이기를 그만두게 됩니다. 되풀이가 본론이면 고리를 허용하는 상태 머신 쪽 표현으로 갑니다.

그래도 담아야 하면 한 바퀴를 한 벌씩 펼쳐 노드를 새로 만듭니다. 몇 바퀴 돌지 미리 알 때만 쓸 수 있는 방법입니다.

관련 항목

DAG 를 이루는 구성 요소

노드 · 간선 · 방향 그래프 · 경로 · 진입 차수 · 루트 노드

DAG 위에서 도는 알고리즘

위상 정렬 · 깊이 우선 탐색 · 너비 우선 탐색 · 고리 검출 · 임계 경로 · 이행적 축소

DAG 와 견주는 다른 그래프 모양

그래프 · 트리 · 순환 그래프 · 이진 트리 · 머클 트리 · 머클 DAG · 상태 머신

DAG 로 순서를 정하는 작업 단위

태스크 · 워크플로 · 파이프라인 · 업스트림 의존성 · 태스크 의존 관계 · 오퍼레이터

DAG 를 만들어 돌리는 도구

Airflow · Gradle · Make · Bazel · Spark · Git · 오케스트레이션

DAG 조건을 어겼을 때 나는 오류

순환 의존 · 순환 참조 · 데드락 · 무한 루프

DAG 를 메모리에 담는 표현

인접 리스트 · 인접 행렬 · 의존성 그래프 · 빌드 그래프