DAG

DAG 는 무엇이 무엇보다 먼저인지를 담아 둡니다. 먼저인 쪽에서 나중인 쪽으로 화살표를 그어 두는 방식입니다. 화살표를 아무리 따라가도 떠나온 곳으로 돌아오지 않습니다. 그래서 화살표를 거스르지 않는 순서를 언제나 뽑을 수 있습니다.

상세

아침에 집을 나서는 차례를 떠올려 봅니다. 양말을 신어야 신발을 신을 수 있습니다. 셔츠를 입어야 외투를 걸칠 수 있습니다. 양말과 셔츠 사이에는 그런 조건이 없어서 어느 쪽을 먼저 해도 됩니다.

DAG 는 Directed Acyclic Graph 의 줄임말입니다. 우리말로는 방향 비순환 그래프라고 옮깁니다. 이름을 이루는 낱말부터 하나씩 풉니다.

그래프는 점과 점을 선으로 이어 관계를 담는 자료구조입니다. 점을 노드, 잇는 선을 간선이라고 부릅니다. 할 일 다섯 개를 노드 다섯 개로 둡니다. 앞뒤가 있는 일끼리는 간선으로 잇습니다.

방향 그래프는 간선마다 방향이 붙은 그래프입니다. 간선은 노드 두 개의 순서쌍이라 한쪽 노드에서 다른 쪽 노드로만 따라갑니다. 일방통행 길만 있는 동네 지도와 같습니다. 이 문서는 그 방향을 화살표로 그립니다.

화살표를 따라 노드에서 노드로 이어 가는 길을 경로라고 부릅니다. 같은 노드에서 출발해 같은 노드로 끝나는 경로가 고리입니다. 고리는 간선을 하나 이상 지납니다. 사이클이나 순환이라고도 부릅니다.

DAG 는 방향 그래프 가운데 고리가 하나도 없는 것입니다. 어느 노드에서 출발해 화살표를 따라가도 그 노드로 돌아오는 경로가 없습니다. 아래는 빌드 과정을 DAG 로 담은 것입니다.

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

화살표는 "앞의 일이 끝나야 뒤의 일을 한다" 를 뜻합니다. 테스트는 컴파일과 코드 검사가 둘 다 끝나야 시작합니다. 어느 노드에서 출발해도 화살표를 따라 아래로만 내려갑니다.

화살표를 어느 쪽으로 긋느냐는 약속입니다. 이 그림은 먼저 할 일에서 나중 할 일로 그었습니다. 뒤에서 보는 Git 과 make 는 거꾸로, 나중 것에서 먼저 것으로 긋습니다. 어느 약속이든 고리가 없으면 DAG 입니다.

고리가 없다는 조건

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

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

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

DAG 에서는 이런 막힘이 생기지 않습니다. 노드마다 번호를 매기되 모든 화살표가 작은 번호에서 큰 번호로 가게 매길 수 있습니다. 이렇게 매긴 번호 순서를 위상 순서라고 부릅니다. 앞 빌드 그림이면 내려받기 1, 컴파일 2, 코드 검사 3, 테스트 4, 패키징 5 가 위상 순서 하나입니다.

위상 순서대로 일을 하면 어떤 일도 아직 안 끝난 일을 기다리지 않습니다. 고리가 없다는 조건이 이 순서를 보장합니다. 순서가 필요한 곳에서 DAG 를 쓰는 까닭이 이것입니다.

위상 순서를 뽑는 절차는 위상 정렬이라고 부릅니다. 절차의 비용은 아래 「복잡도」가 다룹니다.

거꾸로, 되풀이는 이 모양에 담기지 않습니다. "조건이 맞을 때까지 앞 단계로 돌아간다" 를 화살표로 그리면 그게 곧 고리입니다. 그래프가 DAG 이기를 그만둡니다.

순서가 정해지지 않는 두 노드

화살표로 이어지지 않은 두 노드는 어느 쪽이 먼저인지 정해지지 않습니다. 첫머리 아침 차례의 양말과 셔츠가 이런 두 일입니다. 앞 빌드 그림에서는 컴파일과 코드 검사가 그렇습니다. 둘 사이에는 화살표도, 화살표를 따라 닿는 경로도 없습니다.

이렇게 어떤 쌍에는 앞뒤가 있고 모든 쌍에 꼭 있지는 않은 순서를 부분 순서라고 부릅니다. 집합의 「부분집합이다」 관계가 흔한 예입니다. {a, b} 와 {a, c, d} 는 둘 다 {a, b, c, d} 의 부분집합입니다. 하지만 둘 중 어느 쪽도 다른 쪽의 부분집합이 아닙니다.

DAG 의 화살표가 그리는 것이 이 부분 순서입니다. 그래서 위상 순서는 하나가 아닐 수 있습니다. 앞 그림에서 컴파일 2, 코드 검사 3 으로 매겨도 되고 코드 검사 2, 컴파일 3 으로 매겨도 됩니다.

순서가 정해지지 않은 두 일은 서로를 기다리지 않습니다. 함께 돌려도 화살표를 거스르지 않습니다. 빌드 도구가 작업 여럿을 동시에 띄울 수 있는 근거가 여기에 있습니다.

트리와 갈리는 대목

트리도 고리가 없는 그래프입니다. 그래프 이론의 트리는 모든 노드가 이어져 있고 고리가 없는 그래프입니다. 간선에 방향이 없습니다.

트리에는 맨 위 노드가 하나 있습니다. 그것을 뿌리라고 부릅니다. 트리의 간선에 뿌리에서 아래쪽으로 화살표를 달면 DAG 가 됩니다.

반대는 성립하지 않습니다. 트리에서는 한 노드에 이르는 길이 하나뿐입니다. DAG 에서는 갈라졌던 경로가 다시 한 노드로 모일 수 있습니다. 화살표 여럿이 같은 노드로 들어오는 것입니다.

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

가운데 줄이 DAG 입니다. 트리처럼 순서가 언제나 나오면서, 갈라졌다 합쳐지는 모양까지 담습니다.

복잡도

DAG 는 노드와 간선을 한 번씩만 훑으면 위상 순서를 뽑습니다. 그래프에 고리가 있는지도 같은 훑기 안에서 드러납니다. 담는 공간은 메모리에 어떤 모양으로 담느냐에 따라 갈립니다. 비싼 연산은 간선을 넣는 쪽입니다. 고리가 안 생기는지 확인하려면 그래프를 다 훑어야 할 수 있습니다.

재 보는 대상은 앞 빌드 그림입니다. 이 절에서 V 는 노드 수, E 는 간선 수입니다.

O(…) 는 빅오 표기법입니다. 입력이 커질 때 비용이 무엇에 비례해 늘어나는지를 적습니다. O(V+E) 는 노드 수와 간선 수를 더한 만큼에 비례한다는 뜻입니다.

메모리에 DAG 를 담는 방법은 둘입니다. 인접 리스트는 노드마다 목록을 하나씩 둡니다. 노드 i 의 목록에는 i 에서 화살표가 나가는 노드를 적습니다. 인접 행렬은 V × V 칸의 표를 둡니다. i 에서 j 로 화살표가 있으면 (i, j) 칸이 1, 없으면 0 입니다.

앞 빌드 그림을 인접 리스트로 담으면 이런 모양입니다.

flowchart TD
    subgraph 배열["노드 배열 · 칸 다섯"]
        H1["의존성 내려받기"]
        H2["컴파일"]
        H3["코드 검사"]
        H4["테스트"]
        H5["패키징"]
    end
    H1 --> L1["컴파일"]
    H1 --> L2["코드 검사"]
    H2 --> L3["테스트"]
    H3 --> L4["테스트"]
    H4 --> L5["패키징"]

앞의 그림들에서 화살표는 일의 앞뒤를 뜻했습니다. 이 그림의 화살표는 다릅니다. 배열의 칸에서 그 칸에 매달린 목록 칸으로 이어진다는 것만 나타냅니다.

목록 칸에 적힌 이름은 배열의 같은 이름 칸을 가리킵니다. 그래서 같은 이름이 그림에 여러 번 나옵니다. 테스트는 배열 칸 하나와 목록 칸 둘로 세 번 나옵니다.

패키징 칸에는 매달린 목록이 없습니다. 나가는 화살표가 없기 때문입니다.

배열의 칸은 노드 수만큼입니다. 목록에 매달린 칸은 간선 수만큼입니다. 아래 표의 「왜」 칸이 이 모양에서 나옵니다. 표에 적은 「노드를 한 번씩 꺼내고 간선을 한 번씩 지웁니다」는 아래 「위상 정렬 한 번의 비용」이 풉니다.

간선이 가능한 수보다 훨씬 적은 그래프를 희소 그래프라고 부릅니다. 이때 두 표현이 크게 갈립니다. 노드 1,000 개에 간선 3,000 개인 DAG 라면 행렬은 1,000,000 칸입니다. 리스트는 목록 1,000 개에 칸 3,000 개입니다.

위상 정렬 한 번의 비용

위상 정렬이 왜 O(V+E) 인지는 절차를 보면 드러납니다. 한 노드로 들어오는 화살표 수를 그 노드의 진입 차수라고 부릅니다. 절차는 진입 차수가 0 인 노드, 곧 기다릴 것이 없는 노드를 꺼내는 일의 되풀이입니다.

1. 진입 차수가 0 인 노드를 꺼내 위상 순서 끝에 붙입니다
2. 그 노드에서 나가는 화살표를 지웁니다. 화살표가 가리키던 노드의 진입 차수가 하나씩 줄어듭니다
3. 남은 노드가 없을 때까지 되풀이합니다

앞 빌드 그림에 돌리면 이렇습니다. 한 바퀴에 진입 차수가 0 인 노드를 모두 꺼냈습니다.

노드 다섯이 한 번씩 꺼내졌습니다. 화살표 다섯이 한 번씩 지워졌습니다. 이것이 O(V+E) 의 V 와 E 입니다. 2 바퀴에 둘이 함께 나온 것이 앞 「상세」의 순서가 정해지지 않는 두 노드입니다.

고리 확인은 따로 비용이 붙지 않습니다. 노드가 남았는데 진입 차수가 0 인 노드가 하나도 없으면 남은 노드 가운데 고리가 적어도 하나 있다는 뜻입니다. 앞의 「문서 만들기」 그림이 첫 바퀴부터 여기에 걸립니다.

위상 순서는 몇 가지까지 나올 수 있을까요. 화살표가 하나도 없으면 모든 줄 세우기가 위상 순서입니다. 노드 V 개를 줄 세우는 가짓수 V! 이 그대로 위상 순서의 수입니다. 노드 10 개면 3,628,800 가지입니다.

화살표가 늘면 그 수가 줄거나 그대로입니다. 한 줄로 이어지면 하나만 남습니다.

간선 하나를 넣을 때

간선을 넣는 것 자체는 O(1) 입니다. 그런데 DAG 를 지키려면 넣기 전에 확인이 필요합니다. 새 간선 u→v 가 고리를 만드는 경우는 하나입니다. v 에서 화살표를 따라 u 에 닿는 경로가 이미 있을 때입니다.

그래서 v 에서 출발해 닿는 노드를 모두 따라가 봅니다. 그중에 u 가 있으면 넣지 않습니다. 이 따라가기가 최악에는 노드와 간선을 다 지나 O(V+E) 입니다.

최악은 v 에서 닿는 노드가 많은데 u 는 그중에 없을 때 옵니다. 넣어도 되는 간선인데 다 훑고 나서야 그걸 압니다. 간선을 하나씩 자주 넣는 그래프에서 이 확인이 비용을 지배합니다.

일반 그래프보다 싸지는 계산

이 소절은 고리가 없다는 조건이 어떤 계산을 싸게 만드는지 봅니다. 견줄 상대는 고리가 있는 방향 그래프입니다. 재 보는 것은 한 노드에서 다른 노드까지 가는 경로의 길이입니다.

고리가 있는 그래프에서는 노드를 어떤 순서로 보아도 한 번에 끝낸다는 보장이 없습니다. 어떤 노드의 길이를 정해 놓아도 나중에 본 노드에서 더 짧은 길이 나오면 그 값을 다시 고쳐야 합니다. 고친 값은 그 노드가 가리키던 노드들로 다시 번집니다. 그래서 같은 노드를 여러 번 다시 봅니다.

DAG 에서는 위상 순서가 이 되돌아감을 없앱니다. 어떤 노드를 볼 때면 그 노드로 들어오는 화살표의 출발점이 위상 순서상 이미 다 계산돼 있습니다. 그래서 노드마다 한 번만 계산하면 됩니다.

위상 순서대로 노드를 한 번씩 보며 나가는 간선을 한 번씩만 처리하면 끝납니다. 비용은 위상 정렬과 같은 O(V+E) 입니다.

한 출발점에서 다른 노드까지의 최단 경로가 이렇게 풀립니다. 노드나 간선마다 걸리는 시간이 붙어 있을 때 가장 오래 걸리는 경로도 같은 방식으로 풉니다. 이 가장 긴 경로를 임계 경로라고 부릅니다. 전체 일이 끝나는 데 걸리는 시간을 정하는 경로입니다.

앞 빌드 그림에 시간을 붙여 봅니다. 내려받기 2 분, 컴파일 5 분, 코드 검사 3 분, 테스트 4 분, 패키징 1 분이라고 둡니다. 위상 순서대로 "가장 늦게 끝나는 앞 일 + 자기 시간" 을 적어 내려갑니다.

이 표는 들어오는 쪽에서 모아 보는 셈입니다. 노드와 간선을 한 번씩만 보는 것은 앞의 셈과 같습니다.

임계 경로는 내려받기 → 컴파일 → 테스트 → 패키징, 12 분입니다. 코드 검사는 2 분 늦어져도 전체 시각이 안 바뀝니다. 아래 그림에서 굵은 화살표가 임계 경로입니다.

flowchart TD
    A["의존성 내려받기 · 2분 · 끝 2"] ==> B["컴파일 · 5분 · 끝 7"]
    A --> C["코드 검사 · 3분 · 끝 5"]
    B ==> D["테스트 · 4분 · 끝 11"]
    C --> D
    D ==> E["패키징 · 1분 · 끝 12"]

예시

DAG 는 버전 관리와 빌드 도구 안에 실물로 들어 있습니다. 성격이 다른 두 곳을 봅니다. Git 이 커밋 이력을 담는 방식과 GNU(GNU's Not Unix) make 가 빌드 규칙을 담는 방식입니다.

Git 커밋 이력

Git 은 커밋 하나를 커밋 객체 하나로 저장합니다. 커밋 객체에는 그 시점의 파일 전체를 가리키는 트리 ID, 부모 커밋 ID, 작성자와 시각, 메시지가 들어 있습니다. 이 트리는 그 커밋 시점의 최상위 디렉토리를 담은 Git 객체의 이름입니다. 앞 「상세」에서 본 그래프 모양의 트리와는 다른 것입니다.

부모는 바로 앞 커밋입니다. 저장된 커밋 하나는 이렇게 생겼습니다.

tree 1b61de420a21a2f1aaef93e38ecd0e45e8bc9f0a
parent 4ccb6d7b8869a86aae2e84c56523f8705b50c647
author Maya <maya@example.com> 1759173425 -0400
committer Maya <maya@example.com> 1759173425 -0400

Add README

parent 줄이 이 커밋에서 부모로 나가는 화살표입니다. 저장소의 첫 커밋은 부모가 0 개입니다. 보통 커밋은 1 개입니다. 병합 커밋은 2 개 이상입니다.

커밋 객체들이 이렇게 서로를 가리켜 DAG 를 이룹니다. 부모를 가리키니 방향이 있습니다. 새 커밋을 만들 때 부모로 적는 것은 이미 저장돼 있는 커밋입니다. 그래서 부모를 따라가도 떠나온 커밋으로 돌아오는 고리가 없습니다.

아래는 두 갈래를 병합한 이력을 git log --graph 로 본 출력입니다.

$ git log --pretty=format:'%h %s' --graph
* 734713b Fix refs handling, add gc auto, update tests
* d921970 Merge commit 'phedders/rdocs'
|\
| * 35cfb2b Some rdoc changes
* | 1c002dd Add some blame and merge stuff
|/
* 1c36188 Ignore *.gem
* 9b29157 Add open3_detach to gemspec file list

d921970 이 병합 커밋입니다. 이 커밋을 git show 로 열면 Merge: 1c002dd... 35cfb2b... 줄에 부모 둘이 찍힙니다.

첫째 부모는 병합할 때 있던 브랜치 쪽, 둘째 부모는 병합해 들어온 브랜치 쪽입니다. d921970^2 가 둘째 부모를 가리킵니다.

flowchart TD
    C6["734713b"] --> C5["d921970 · 병합 커밋"]
    C5 --> C4["1c002dd"]
    C5 --> C3["35cfb2b"]
    C4 --> C2["1c36188"]
    C3 --> C2
    C2 --> C1["9b29157"]

화살표는 Git 이 저장한 방향대로 새 커밋에서 부모 쪽으로 그렸습니다. 앞 빌드 그림과는 방향 약속이 반대입니다.

d921970 에서 화살표 두 개가 나갑니다. 1c36188 로는 화살표 두 개가 들어옵니다. 갈라졌다 다시 만나는 이 모양 때문에 커밋 이력은 트리가 아니라 DAG 입니다.

GNU make 규칙

GNU make 의 Makefile 은 규칙의 모음입니다. 규칙 하나는 목표 : 선행 조건 꼴입니다.

목표는 대개 만들어 낼 파일입니다. 선행 조건은 그 목표를 만드는 데 들어가는 파일입니다. 아래는 make 매뉴얼의 예제로, 실행 파일 edit 를 만드는 Makefile 입니다.

edit : main.o kbd.o command.o display.o \
       insert.o search.o files.o utils.o
        cc -o edit main.o kbd.o command.o display.o \
                   insert.o search.o files.o utils.o

main.o : main.c defs.h
        cc -c main.c
kbd.o : kbd.c defs.h command.h
        cc -c kbd.c
command.o : command.c defs.h command.h
        cc -c command.c
display.o : display.c defs.h buffer.h
        cc -c display.c
insert.o : insert.c defs.h buffer.h
        cc -c insert.c
search.o : search.c defs.h buffer.h
        cc -c search.c
files.o : files.c defs.h buffer.h command.h
        cc -c files.c
utils.o : utils.c defs.h
        cc -c utils.c

매뉴얼 예제에서 파일을 지우는 clean 규칙만 뺐습니다. 노드는 파일입니다. 화살표는 목표에서 선행 조건으로 갑니다. 규칙 한 줄이 그대로 인접 리스트의 목록 한 줄입니다.

edit 는 오브젝트 파일 여덟 개를 선행 조건으로 갖습니다. .o 파일은 저마다 .c 파일 하나와 헤더 파일 몇 개를 갖습니다. .o 파일 하나하나는 그 자체로 목표입니다. 동시에 edit 의 선행 조건입니다.

flowchart TD
    E["edit"] --> M["main.o"]
    E --> K["kbd.o"]
    E --> CO["command.o"]
    E --> F["files.o"]
    E --> R["나머지 .o 넷"]
    M --> MC["main.c"]
    M --> D["defs.h"]
    K --> KC["kbd.c"]
    K --> D
    K --> CH["command.h"]
    CO --> CC["command.c"]
    CO --> D
    CO --> CH
    F --> FC["files.c"]
    F --> D
    F --> BH["buffer.h"]
    F --> CH
    R --> D

.o 여덟 개 중 넷을 펼치고 나머지 넷은 한 노드로 접었습니다. 접은 노드에서는 여덟 개가 공통으로 갖는 defs.h 로만 화살표를 그었습니다.

모든 .c 파일이 defs.h 를 포함하므로, 접지 않은 그래프에서 defs.h 로는 .o 여덟 개 전부에서 화살표가 들어옵니다. command.h 로는 kbd.o · command.o · files.o 세 곳에서 들어옵니다. 같은 파일이 여러 목표의 선행 조건으로 다시 나오는 이 모양이 트리가 아닌 DAG 입니다.

make 는 화살표를 거꾸로 따라 일합니다. 선행 조건이 바뀌면 그 목표를 다시 만듭니다. 선행 조건 자신도 만들어 내는 파일이면 그것부터 갱신합니다.

defs.h 를 고치면 그것을 선행 조건으로 갖는 .o 여덟 개가 모두 다시 컴파일됩니다. 그 다음에 edit 가 다시 링크됩니다.

규칙을 잘못 적어 고리가 생기면 make 는 이런 메시지를 냅니다.

Circular xxx <- yyy dependency dropped.

목표 xxx 의 선행 조건 yyy 를 따라 내려갔더니 그중 하나가 다시 xxx 를 필요로 했다는 뜻입니다. make 는 의존 그래프에서 고리를 찾아냈습니다. 그 의존 하나를 버렸다는 것도 함께 알립니다.

경계

워크플로 도구 Airflow 의 Dag 는 이 DAG 인가. 아닙니다. Airflow 의 Dag 는 워크플로 하나를 돌리는 데 필요한 것을 모두 묶은 객체입니다. 이 표제어의 DAG 는 그 안에서 작업 사이의 앞뒤만 담은 모양입니다.

Airflow 의 Dag 에는 이런 것이 들어갑니다. 언제 돌릴지 정하는 일정, 워커에서 도는 작업 단위인 태스크, 태스크 사이의 의존, 워크플로가 끝났을 때 할 일을 정하는 콜백입니다. 그밖에 재시도 횟수와 시간 제한 같은 운영 값도 들어갑니다. 이 가운데 고리 없는 그래프에 해당하는 것은 태스크와 그 사이의 의존입니다.

flowchart TD
    subgraph Dag["Airflow 의 Dag · 워크플로 하나"]
        S["일정"]
        CB["콜백"]
        RT["재시도 · 시간 제한"]
        subgraph 모양["태스크 사이의 의존 · 이 표제어의 DAG"]
            T1["first_task"] --> T2["second_task"]
            T1 --> T3["third_task"]
            T4["fourth_task"] --> T3
        end
    end

안쪽 상자의 화살표는 Airflow 코드 두 줄에서 나옵니다. first_task >> [second_task, third_task] 는 first_task 가 끝나야 나머지 둘을 돌린다는 뜻입니다. third_task << fourth_task 는 fourth_task 가 third_task 보다 먼저라는 뜻입니다. 이렇게 선언한 의존이 Dag 의 구조를 이룹니다.

판정의 근거는 Airflow 자신의 정의입니다. Airflow 는 이 낱말이 수학의 directed acyclic graph 에서 왔지만 Airflow 안에서는 그 자료구조를 훨씬 넘어서는 뜻이 됐다고 밝힙니다. 그래서 대문자 줄임말 DAG 대신 Dag 로 적기로 했습니다. 표기를 갈라 둔 것 자체가 둘이 같은 것이 아니라는 표시입니다.

다만 안쪽 상자는 이 표제어의 조건을 지켜야 합니다. 태스크 의존에 고리가 있으면 실행 순서를 못 뽑기 때문입니다. Airflow 2.10.5 에는 Dag 정의에 고리가 있을 때 내는 예외 AirflowDagCycleException 이 있습니다.

일정·콜백·재시도는 이 모양 밖에 얹힌 것입니다. 모양 자체는 이 표제어의 DAG 입니다.

사용처

DAG 는 "무엇이 무엇을 기다리나" 를 담아야 하는 곳마다 쓰입니다. 도메인이 달라도 노드와 화살표가 가리키는 것만 바뀝니다.

Git·make 는 앞 「예시」가, Airflow 는 앞 「경계」가 다뤘습니다. 나머지 넷을 봅니다.

Apache Spark

Spark 는 데이터 처리 엔진입니다. 잡 하나를 DAG 로 봅니다. 노드는 RDD 나 DataFrame 이라는 데이터 묶음입니다. 간선은 그 데이터에 거는 연산입니다.

담는 것은 「어떤 데이터가 어떤 연산을 거쳐 다음 데이터가 됐나」의 앞뒤입니다. 그래서 이 모양이 그대로 맞습니다. 웹 UI(User Interface)가 잡마다, 그리고 잡을 쪼갠 스테이지마다 이 DAG 를 그려 보여 줍니다.

그 그림은 노드 여럿을 연산 범위별로 한 상자에 묶습니다. 이름표는 그 상자에 붙는 범위 이름입니다. 노드 하나하나는 그대로 데이터입니다.

Terraform

Terraform 은 인프라 리소스를 설정으로 적어 만들고 바꾸는 도구입니다. 계획을 세우거나 상태를 새로 읽을 때 먼저 의존 그래프를 만듭니다. 한 리소스가 다른 리소스의 속성을 참조하면 그 둘 사이에 간선이 생깁니다. depends_on 으로 직접 적은 의존도 간선이 됩니다.

그래프를 만든 뒤 고리가 없는지, 뿌리가 하나인지 확인합니다. 그 다음 그래프를 걸으며 리소스를 만듭니다. 한 노드는 그 노드가 기다리는 노드들이 다 끝나는 즉시 처리됩니다. 그래서 서로 기다리지 않는 리소스는 나란히 만들어집니다.

동시에 처리하는 노드는 기본 10 개까지입니다. 이 수는 -parallelism 옵션으로 바꿉니다.

IPFS 의 머클 DAG

IPFS 는 내용으로 데이터를 찾는 분산 파일 시스템입니다. 데이터를 머클 DAG 로 담습니다. 노드마다 식별자가 있습니다. 식별자는 그 노드의 내용과 자식 식별자 목록을 SHA256(Secure Hash Algorithm 256-bit) 같은 암호 해시 함수에 넣은 결과입니다.

자식의 식별자를 알아야 부모를 만들 수 있습니다. 그래서 머클 DAG 는 자식이 없는 잎부터 쌓아 올립니다. 노드 셋을 사슬로 이으면 식별자가 이렇게 매겨집니다.

flowchart TD
    A["A · 식별자 = Hash(B)"] --> B["B · 식별자 = Hash(C)"]
    B --> C["C · 식별자 = Hash(빈 내용)"]

고리를 만들려면 C 가 A 를 가리켜야 합니다. 그러려면 C 를 만들 때 A 의 식별자를 이미 알아야 합니다. 그런데 A 의 식별자는 B 를, B 의 식별자는 C 를 해시한 값입니다. C 가 먼저 있어야 A 가 정해집니다.

해시 함수는 결과에서 입력을 거꾸로 만들어 내기 어려운 함수입니다. 그래서 고리를 만들기가 사실상 불가능할 만큼 어렵습니다. 해시 함수에 약점이 발견되지 않는 한 그렇습니다.

머클 트리와 다른 대목도 있습니다. 머클 트리는 머클 DAG 와 비슷하게 해시로 노드를 잇는 트리입니다. 다만 잎의 깊이를 고르게 맞추는 균형 조건이 붙습니다.

머클 DAG 에는 그 조건이 없습니다. 모든 노드가 내용을 실을 수 있습니다. 한 노드가 부모를 여럿 가질 수 있어 갈라진 가지가 다시 만날 수 있습니다.

Bazel

Bazel 은 빌드 도구입니다. 대상 A 를 빌드하거나 실행하는 데 대상 B 가 필요하면 A 가 B 에 의존한다고 봅니다. 이 의존 관계가 대상들 위에 DAG 를 이룹니다.

이 DAG 를 의존 그래프라고 부릅니다. 담는 것은 「빌드나 실행에 필요하다」의 앞뒤입니다. 그래서 이 모양이 그대로 맞습니다.

의존 그래프에서 경로 길이 1 로 닿는 대상이 직접 의존입니다. 길이와 상관없이 닿는 대상은 모두 이행적 의존입니다. Bazel 은 이 그래프를 만들어 훑으며 빌드합니다. 요청한 대상이 의존하는 산출물이 전부 최신으로 확인되면 빌드가 끝난 것으로 봅니다.

관련 항목

DAG 를 이루는 구성 요소

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

DAG 를 정의하는 그래프 개념

고리 · 사이클 · 위상 순서 · 부분 순서 · 도달 가능성

DAG 위에서 도는 알고리즘

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

DAG 를 메모리에 담는 표현

인접 리스트 · 인접 행렬 · 희소 그래프 · 밀집 그래프

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

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

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

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

DAG 를 안에 두고 돌아가는 제품

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

DAG 의 꼴을 띠는 의존 그래프

의존성 그래프 · 빌드 그래프 · 액션 그래프 · 커밋 그래프

DAG 의 노드와 화살표가 되는 제품 속 객체

커밋 · 커밋 객체 · 병합 커밋 · 부모 커밋 · Makefile · 선행 조건 · 빌드 대상

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

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