여러 사람이 함께 과제를 한다고 생각해 봅시다. 한 사람은 자료를 찾고, 한 사람은 표를 만들고, 다른 사람은 문장을 다듬습니다. 각자 맡은 일이 끝났다고 말해도 과제 전체가 끝난 것은 아닙니다. 표를 본 사람이 “자료가 하나 더 필요하다”며 일을 앞 단계로 돌려보낼 수 있기 때문입니다.

분산 컴퓨터도 비슷합니다. 여러 워커(worker)가 데이터를 나누어 처리하고, 어떤 결과는 다시 앞 단계로 돌아갑니다. 이때 가장 어려운 질문은 의외로 단순합니다.

“지금 잠깐 조용한 것인가, 아니면 정말 모든 계산이 끝난 것인가?”

Timely Dataflow는 이 질문에 답하기 위해 만든 분산 데이터 처리 모델이자 Rust 런타임입니다. 특히 그래프 탐색이나 Datalog처럼 결과가 다시 입력으로 돌아가는 반복 계산을 잘 다룹니다. Datalog는 이미 알고 있는 사실과 규칙을 이용해 새로운 사실을 찾아내는 언어입니다. Naiad 연구에서 출발했으며[1], 같은 프로그램을 노트북의 단일 스레드부터 여러 컴퓨터의 워커까지 확장할 수 있습니다.

이 글은 Timely Dataflow를 처음 접하는 독자를 위한 글입니다. 수식보다 택배 분류센터 비유를 먼저 사용하고, 그 뒤에 실제 용어와 Wirelog 이야기를 연결하겠습니다.

택배 분류센터로 먼저 이해해 보자

큰 택배 분류센터를 떠올려 봅시다. 들어온 상자는 여러 작업대를 거칩니다.

정상적인 상자는 그림의 위에서 아래로 이동합니다. 주소가 잘못 읽힌 상자는 지역별 분류에서 주소 읽기 작업대로 되돌아갑니다. 즉 컨베이어 벨트에 루프가 있습니다.

어느 순간 눈앞의 벨트가 비었다고 해도 오늘 물량이 끝났다고 말할 수는 없습니다.

• 다른 작업대가 상자를 보내는 중일 수 있습니다.
• 작업대 사이의 컨베이어를 이동 중인 상자가 있을 수 있습니다.
• 주소 오류로 되돌아올 상자가 남아 있을 수 있습니다.

“벨트가 비었다”와 “더 올 상자가 없다”는 전혀 다른 말입니다. Timely Dataflow가 추적하는 것은 현재 상자의 수보다 앞으로 상자가 생길 가능성입니다.

이 비유를 실제 용어에 연결하면 다음과 같습니다.

택배 분류센터	Timely Dataflow
작업대	연산자(operator)
작업자 한 명	워커(worker)
컨베이어 벨트	채널(channel)
상자의 작업 차수표	논리 타임스탬프(logical timestamp)
특정 차수 상자를 보낼 수 있는 작업 권한	capability
이 경계보다 오래된 상자는 더 오지 않는다는 표시	frontier

이제 하나씩 살펴봅시다.

1. 데이터플로우는 작업 순서를 그림으로 만든다

보통 프로그램은 “첫 줄을 실행하고, 다음 줄을 실행하라”는 명령 목록입니다. 데이터플로우 프로그램은 조금 다릅니다. 해야 할 일을 작은 연산자로 나누고, 데이터가 이동할 길을 선으로 연결합니다.

Input → Map → Exchange → Join → Output
                    ↑          │
                    └ Feedback ┘

용어가 낯설어 보여도 역할은 단순합니다.

• Map: 들어온 데이터를 다른 형태로 바꿉니다.
• Exchange: 같은 종류의 데이터를 같은 워커로 보냅니다.
• Join: 두 데이터에서 같은 키를 찾아 결합합니다.
• Feedback: 결과를 앞 단계로 되돌려 반복합니다.

각 연산자는 데이터가 도착하면 일을 시작합니다. 서로 관계없는 연산자는 동시에 움직일 수 있습니다. 그래서 CPU 코어가 여러 개이거나 컴퓨터가 여러 대일 때 일을 나누기 좋습니다.

Timely의 각 워커는 같은 연산자 그래프를 실행합니다. 워커마다 다른 프로그램을 실행하는 것이 아닙니다. 예를 들어 학생 번호가 짝수인 데이터는 워커 0, 홀수인 데이터는 워커 1이 맡는 식으로 데이터만 나눕니다. 이 재분배를 exchange라고 합니다.

2. 논리 시간: 몇 시인지가 아니라 작업 차수표

Timely의 “시간”은 오후 3시 10분처럼 시계로 재는 시간이 아닙니다. 이 데이터가 어느 작업 차수에 속하는지 나타내는 번호입니다.

예를 들어 매일 들어오는 주문을 처리한다면 다음처럼 번호를 붙일 수 있습니다.

0 = 월요일 주문
1 = 화요일 주문
2 = 수요일 주문

이 번호가 논리 시간입니다. 네트워크가 느려서 화요일 주문이 월요일 주문보다 먼저 도착해도, 시스템은 번호를 보고 올바른 차수를 구분할 수 있습니다.

반복 계산에서는 번호가 한 칸 더 필요합니다. “몇 번째 입력인가”뿐 아니라 “그 입력을 몇 번 반복했는가”도 알아야 하기 때문입니다.

(입력 차수, 반복 횟수)

(7, 0) = 7번째 입력의 최초 계산
(7, 1) = 결과를 한 번 되돌려 계산
(7, 2) = 결과를 두 번 되돌려 계산

Datalog로 친구 관계를 따라가며 “친구의 친구”를 찾는다면 (7, 1)은 한 다리 건너 찾은 결과, (7, 2)는 두 다리 건너 찾은 결과라고 생각할 수 있습니다.

시간이 꼭 한 줄로 늘어서지는 않는다

일반적인 번호는 1 < 2 < 3처럼 한 줄로 정렬됩니다. 하지만 분산 계산에서는 서로 독립적인 두 작업이 동시에 진행될 수 있습니다. 어느 쪽이 먼저라고 정할 필요가 없는 경우도 있습니다.

Timely는 이런 시간을 부분 순서(partial order)로 다룹니다. 말은 어렵지만 뜻은 간단합니다.

관계가 있는 작업끼리는 앞뒤를 비교하고, 관계가 없는 작업은 억지로 줄 세우지 않는다.

덕분에 서로 상관없는 작업은 기다리지 않고 동시에 진행할 수 있습니다.

3. Capability: “이 시간의 데이터를 더 만들 수 있다”는 작업권

다시 택배 분류센터로 돌아가 봅시다. 작업자에게 “7번 차수 상자를 보낼 수 있는 표”가 남아 있다면, 지금 벨트가 비었어도 7번 상자가 나중에 나타날 수 있습니다.

Timely에서는 이 표를 capability라고 부릅니다.

capability는 “이 연산자가 논리 시간 t의 데이터를 출력할 수 있다”는 권한이다.

연산자는 capability를 가지고 있을 때만 그 시간의 메시지를 보낼 수 있습니다. 일이 끝나면 capability를 버립니다. 더 나중 차수의 일만 남았다면 capability를 뒤의 시간으로 옮길 수 있습니다. Timely에서는 이것을 downgrade라고 부릅니다.

전송 중인 메시지도 반드시 계산에 포함해야 합니다. 보내는 워커는 일을 끝냈지만 메시지가 아직 받는 워커에 도착하지 않았을 수 있기 때문입니다.

예를 들어 다음 세 조건을 모두 만족해야 t=4의 일이 끝났다고 말할 수 있습니다.

• 어떤 연산자도 t=4 capability를 들고 있지 않습니다.
• 워커 사이를 이동 중인 t=4 메시지가 없습니다.
• 더 이른 시간이 경로를 따라 t=4 메시지를 만들 가능성도 없습니다.

capability는 복잡한 분산 계산을 위한 작업권 장부인 셈입니다.

4. Frontier: “여기 이전은 끝났다”는 경계선

각 작업권과 전송 중 메시지를 모두 합치면, 시스템은 앞으로 도착할 수 있는 가장 이른 시간을 알 수 있습니다. 이 경계가 frontier입니다.

시간이 단순한 숫자라면 이해하기 쉽습니다.

frontier = {5}

이는 5 이상의 데이터는 앞으로 올 수 있지만, 0, 1, 2, 3, 4 데이터는 더 오지 않는다는 뜻입니다. 따라서 4까지의 집계 결과는 확정해서 내보낼 수 있습니다.

frontier는 “마지막으로 처리한 번호”와 다릅니다. 핵심은 과거에 무엇을 봤는지가 아니라, 미래에 무엇이 더 올 수 있는지입니다.

경계가 여러 개일 수도 있다

부분 순서 시간에서는 서로 비교할 수 없는 작업이 여러 개 남을 수 있습니다. 이때 frontier도 한 숫자가 아니라 여러 좌표의 집합이 됩니다.

frontier = {(5, 0), (4, 3)}

여기서 좌표는 (입력 차수, 반복 횟수)입니다.

시간	뜻
(5, 0)	5번째 입력을 처음 계산하는 중
(4, 3)	4번째 입력을 세 번 반복해 계산하는 중

두 시간을 비교할 때는 두 숫자가 모두 같거나 커야 “같거나 그 이후”라고 말합니다. 두 숫자 중 하나라도 작으면 이후라고 할 수 없습니다. 그런데 (5, 0)은 입력 차수는 더 크지만 반복 횟수는 더 작습니다. (4, 3)은 반복 횟수는 더 크지만 입력 차수는 더 작습니다. 따라서 어느 쪽도 다른 쪽의 이후가 아니며, 둘의 앞뒤를 정할 수 없습니다.

그래서 frontier에는 두 좌표가 함께 남습니다. 시스템은 “5번째 입력의 첫 계산”과 “4번째 입력의 세 번째 반복”이라는 두 종류의 작업이 모두 더 올 수 있다고 보는 것입니다.

이처럼 서로 앞뒤를 정할 수 없는 최소 시간들의 집합을 antichain이라고 부릅니다. 이름보다 “앞으로 올 수 있는 작업이 여러 방향에 남아 있어 경계도 여러 개다”라고 이해하면 충분합니다.

조금 더 깊이 보기: frontier가 나타내는 미래의 어느 갈래에서도 t 시각의 데이터가 더 올 수 없다면, t의 계산은 끝난 것입니다. Timely API에서는 이를 frontier.less_equal(t) == false로 확인합니다.

5. 그래프의 위치도 함께 봐야 한다

같은 t=4 상자라도 접수대에 있을 때와 트럭 바로 앞에 있을 때는 남은 일이 다릅니다. 접수대의 상자는 여러 작업대를 더 거쳐야 하지만, 트럭 앞의 상자는 곧 센터를 떠납니다.

그래서 Timely는 시간만 보지 않고 (그래프의 위치, 논리 시간)을 함께 봅니다. 이것을 pointstamp라고 합니다.

또 데이터가 어떤 길을 지날 때 시간이 어떻게 변하는지도 기록합니다. 이것을 path summary라고 합니다.

(epoch=7, iter=2) --한 번 되돌아감--> (epoch=7, iter=3)

직선 길에서는 시간이 그대로이고, feedback 길을 지나면 반복 횟수가 하나 증가합니다. 이 정보가 있으면 시스템은 현재 남은 작업 하나가 미래에 어디에서 어떤 시간의 데이터를 만들 수 있는지 계산할 수 있습니다.

이름은 어렵지만 핵심은 단순합니다.

같은 시간표를 가진 일이라도 지금 어디에 있느냐에 따라 남은 일이 다르다.

6. 루프가 있는데도 끝을 찾는 과정

다음 Datalog 규칙은 그래프에서 갈 수 있는 모든 길을 찾습니다.

path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y), edge(Y, Z).

코드를 읽는 방법부터 풀어 봅시다.

• edge는 처음부터 알고 있는 직접 연결입니다.
• path는 규칙으로 새로 찾아낼 수 있는 모든 경로입니다.
• :-는 “오른쪽 조건이 참이면 왼쪽도 참이다”라는 뜻입니다.
• X, Y, Z 같은 대문자는 여러 값이 들어갈 수 있는 변수입니다.

첫 번째 줄은 “직접 연결되어 있으면 갈 수 있다”는 뜻입니다. 두 번째 줄은 “X에서 Y까지 갈 수 있고 Y에서 Z로 직접 연결되어 있으면 X에서 Z까지 갈 수 있다”는 뜻입니다.

예를 들어 a → b, b → c가 있다면 a → c도 찾아냅니다. 새로 찾은 path가 다시 두 번째 규칙의 입력으로 들어가므로 루프가 생깁니다.

Timely식으로 계산 과정을 풀어 쓰면 다음과 같습니다.

1. (입력 4, 반복 0)에 직접 연결된 길을 넣습니다.
2. 첫 결과를 이용해 한 단계 더 먼 길을 찾습니다.
3. 새 결과는 (입력 4, 반복 1)로 루프를 돕니다.
4. 더 먼 길이 나오면 반복 2, 반복 3으로 계속 갑니다.
5. 모든 워커가 해당 반복의 capability를 버리고, 이동 중인 메시지도 없어집니다.
6. frontier가 앞으로 이동하며 “입력 4의 이 반복은 끝났다”고 알려 줍니다.
7. 더 새로 찾을 길이 없으면 계산이 고정점(fixed point)에 도달합니다.

여기서 중요한 구분이 있습니다. Timely가 path를 찾는 조인 알고리즘 자체를 제공하는 것은 아닙니다. Timely는 데이터가 워커와 루프를 따라 움직이게 하고 언제 일이 끝났는지 알려 줍니다. 실제 조인과 변경분 계산은 Differential Dataflow 같은 상위 계층이 담당합니다.

Timely와 Differential은 어떻게 다른가

둘은 자주 함께 언급되지만 같은 프로그램은 아닙니다. 대학교에 비유하면 역할이 더 분명해집니다.

구성 요소	대학 비유	실제 역할
Timely Dataflow	강의실, 시간표, 출석 확인	워커, 데이터 이동, 논리 시간, 반복, 완료 판단
Differential Dataflow	수정된 과제 부분만 다시 채점하는 방법	입력 변화에 영향받은 결과만 다시 계산
Datalog 엔진	과제 문제와 풀이 규칙	사실과 규칙을 읽고 새로운 사실을 도출

Timely는 계산이 움직이는 무대와 시계입니다. Differential Dataflow는 그 무대에서 “바뀐 것만 다시 계산하는 방법”을 제공합니다. Datalog 엔진은 사람이 작성한 논리 규칙을 실행 계획으로 바꿉니다.

따라서 Timely Dataflow를 하나의 증분 알고리즘이라고만 부르면 정확하지 않습니다. 순환하는 병렬 계산을 표현하고, 그 진행 상태를 추적하는 계산 모델과 런타임에 가깝습니다.

실제 Rust 코드는 어떤 모습인가

아래 코드는 공식 저장소 예제를 줄인 것입니다. 코드를 읽지 않아도 다음 절로 넘어갈 수 있습니다.

use timely::dataflow::{InputHandle, ProbeHandle};
use timely::dataflow::operators::{Exchange, Input, Inspect, Probe};

timely::execute_from_args(std::env::args(), |worker| {
    let mut input = InputHandle::new();
    let mut probe = ProbeHandle::new();

    worker.dataflow(|scope| {
        scope.input_from(&mut input)
             .container::<Vec<_>>()
             .exchange(|x| *x)
             .inspect(|x| println!("{x}"))
             .probe_with(&mut probe);
    });

    for round in 0..10 {
        input.send(round);
        input.advance_to(round + 1);

        while probe.less_than(input.time()) {
            worker.step();
        }
    }
}).unwrap();

중요한 줄은 세 곳입니다.

• exchange: 데이터를 담당 워커로 보냅니다.
• advance_to(round + 1): “이전 차수의 새 입력은 더 넣지 않겠다”고 약속합니다.
• probe.less_than(...): 이전 차수의 일이 남았는지 확인합니다.

입력만 보내고 advance_to를 호출하지 않으면 시스템은 과거 데이터가 더 들어올 수 있다고 생각합니다. 작업자가 오래된 작업권을 계속 들고 있는 것과 같습니다. 그래서 frontier도 움직이지 않습니다.

강점: 어떤 점이 좋은가

반복 계산을 자연스럽게 표현한다

그래프 탐색, PageRank, 재귀 질의처럼 결과가 다시 입력으로 돌아가는 계산이 모델 안에 들어 있습니다. 반복을 별도의 배치 작업으로 억지로 나눌 필요가 없습니다.

모든 워커를 매번 멈추게 하지 않는다

Timely는 모든 워커가 매 단계마다 일제히 멈추는 전역 장벽을 기본으로 강제하지 않습니다. 각 워커는 데이터와 진행 정보를 교환하며 가능한 일을 계속합니다. 필요한 곳에서만 probe로 기다릴 수 있습니다.

독립적인 일은 동시에 진행한다

부분 순서 시간 덕분에 관계없는 작업을 억지로 한 줄에 세우지 않습니다. 이는 병렬 처리의 여지를 늘립니다.

작은 컴퓨터에서 클러스터까지 같은 모델을 쓴다

같은 데이터플로우를 단일 스레드, 여러 스레드, 여러 프로세스에서 실행할 수 있습니다. 연구용 알고리즘이나 새로운 데이터 엔진을 만들 때 특히 유용합니다.

Differential Dataflow의 좋은 토대가 된다

바뀐 부분만 다시 계산하려면 어느 시간의 데이터가 더 이상 바뀌지 않는지 알아야 합니다. Timely의 frontier가 바로 이 완료 정보를 제공합니다.

약점: 왜 모두가 Timely를 쓰지는 않을까

배우기 어렵다

논리 시간, capability, frontier, 부분 순서 같은 개념을 함께 이해해야 합니다. 단순한 로그 변환 작업이라면 이런 복잡성이 필요하지 않을 수 있습니다.

완성된 데이터 플랫폼은 아니다

Timely는 계산 런타임입니다. SQL 편집기, 다양한 데이터베이스 커넥터, 운영 대시보드, 자동 복구를 모두 제공하는 제품이 아닙니다. 실서비스 플랫폼을 만들려면 저장, 체크포인트, 모니터링 같은 기능을 별도로 설계해야 합니다.

자유도가 높은 만큼 실수할 곳도 많다

capability를 실수로 오래 보관하면 frontier가 멈춥니다. 잘못된 exchange 기준은 특정 워커에 데이터가 몰리는 현상을 만들 수 있습니다. 워커를 늘린다고 자동으로 빨라지는 것도 아닙니다.

네트워크와 메모리 비용이 든다

조인이나 집계를 하려면 같은 키의 데이터를 같은 담당 워커에 모아야 할 때가 있습니다. 이처럼 데이터를 워커 사이에서 다시 나누어 보내는 일을 셔플(shuffle)이라고 합니다. 서로 다른 컴퓨터에 있는 워커끼리 셔플하면 네트워크를 사용합니다. 또 시스템은 어디까지 계산이 끝났는지 판단하기 위한 진행 정보도 워커끼리 주고받습니다. 그래서 데이터가 아주 적으면 실제 계산보다 이런 준비와 통신에 시간이 더 들 수 있습니다.

공식 README에는 메시지를 복사하는 비용과 Rust의 소유권 규칙에 맞춰 데이터를 다루는 방식을 개선한 과거 논의가 연결되어 있습니다. 하지만 README가 가리키는 복사 최적화 이슈는 이미 닫혔습니다. 따라서 메시지 복사가 현재 버전을 느리게 만드는 주된 원인이라고 단정할 수는 없습니다.

생태계가 상대적으로 작다

Flink나 Spark에 비해 바로 연결할 수 있는 데이터 소스와 운영 사례가 적습니다. 일반적인 ETL이나 SQL 스트리밍이 목적이라면 더 높은 수준의 도구가 편할 수 있습니다.

어떤 문제에 어울리는가

문제	적합도	이유
계속 변하는 큰 그래프 분석	높음	병렬 처리와 반복이 모두 필요함
재귀 질의·증분 뷰 엔진 만들기	높음	시간과 완료 정보를 세밀하게 제어 가능
새로운 저지연 데이터 엔진 연구	높음	낮은 수준의 연산자까지 직접 구현 가능
단순한 로그 변환·ETL	낮음	개념과 운영 비용이 지나치게 큼
SQL·대시보드·커넥터가 즉시 필요한 서비스	낮음	완성형 플랫폼이 아님
자동 복구와 데이터 내구성이 가장 중요한 서비스	별도 설계 필요	저장과 체크포인트는 계산 모델 밖의 문제

Wirelog는 왜 이 아이디어를 선택했는가

먼저 오해하기 쉬운 부분부터 분명히 하겠습니다.

Wirelog는 Rust timely 크레이트를 가져다 쓰지 않습니다. Timely-Differential의 핵심 아이디어를 순수 C11로 다시 구현합니다.

Wirelog는 Datalog 엔진입니다. 다음과 같은 규칙을 실행한다고 생각하면 됩니다.

path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y), edge(Y, Z).

문제는 데이터가 계속 바뀐다는 것입니다. 간선 하나가 추가될 때마다 모든 path를 처음부터 다시 계산하면 낭비가 큽니다. 반대로 간선이 삭제되면 그 간선을 이용해 찾았던 결과를 정확히 취소해야 합니다.

Timely-Differential의 아이디어는 이 문제와 잘 맞습니다.

1. 추가와 삭제를 숫자로 표현한다

먼저 같은 결과가 여러 방법으로 만들어지는 상황을 생각해 봅시다.

a → b → c
a → d → c

a에서 c로 가는 길은 두 개입니다. b → c가 삭제되어도 d를 지나는 길이 남아 있으므로 a → c는 여전히 참입니다. 단순히 결과를 “있음/없음”으로만 저장하면 어느 길이 남았는지 판단하기 어렵습니다.

그래서 변경 내역을 숫자로 적는 장부를 사용합니다. 데이터 추가는 +1, 삭제는 -1입니다.

edge("a", "b")  +1   추가
edge("a", "b")  -1   삭제

두 길에서 같은 결과가 나오면 장부의 값은 2가 됩니다. 한 길이 사라져 -1이 적용되어도 1이 남으므로 결과는 여전히 유효합니다. 이렇게 각 데이터에 양수나 음수 장부 값을 붙이는 모델을 Z-set이라고 합니다.

Wirelog도 사용자가 직접 넣고 빼는 기본 사실에 이 산술을 적용합니다. 구현 문서에서는 기본 사실을 EDB, 규칙으로 새로 얻은 결과를 IDB라고 부릅니다. 장부 값은 multiplicity, 즉 “몇 번 존재하는가”를 나타내는 수로 저장합니다.

다만 현재 Wirelog는 규칙으로 얻은 결과를 정렬한 뒤 중복을 제거합니다. 파생 결과의 장부 값까지 공개 기능으로 보장하는 단계는 아닙니다. Z-set의 일반 이론과 현재 Wirelog가 실제로 보장하는 범위는 구분해야 합니다.

2. 새로 바뀐 부분을 표시한다

도서관이 새 책 한 권을 받을 때 전체 서가 목록을 다시 만드는 대신, 새 책을 기존 색인에 추가하는 모습을 생각하면 됩니다. Wirelog도 새 사실이 들어오면 관련된 규칙에 변경분(delta)을 전달합니다.

이를 위해 검색용 색인과 변경 목록을 합친 자료구조를 사용합니다. Timely-Differential 계열에서는 이런 색인을 arrangement라고 부릅니다. Wirelog 문서의 differential arrangement도 같은 역할을 가리킵니다.

3. 외부 변경과 내부 반복을 함께 센다

Wirelog는 시간을 대략 다음처럼 기록합니다.

(사용자 변경 차수, 재귀 반복 횟수, 워커 번호)

• 변경 차수: 사용자가 몇 번째로 사실을 추가했는가
• 반복 횟수: 그 변경을 규칙에 몇 번 전파했는가
• 워커 번호: 어느 병렬 작업자가 처리했는가

이 좌표가 있으면 어떤 결과가 어느 변경의 몇 번째 반복에서 나왔는지 추적할 수 있습니다.

원래 Timely는 더 일반적인 부분 순서 시간을 지원합니다. 현재 Wirelog는 자신의 Datalog 실행 방식에 맞춰 먼저 사용자 변경 차수를 비교하고, 같으면 반복 횟수를 비교합니다. 사전에서 단어를 앞 글자부터 비교하는 것과 비슷해 이를 사전식 비교라고 합니다. 즉 아이디어를 그대로 복사한 것이 아니라 문제에 맞게 단순화한 구현입니다.

4. 끝난 반복을 건너뛴다

Wirelog의 frontier는 이전 실행이 어디까지 수렴했는지 기억합니다. 새 입력과 관계없는 규칙은 이미 끝난 반복을 다시 실행하지 않을 수 있습니다.

여러 워커가 동작할 때는 가장 느린 워커의 진행 지점을 기준으로 삼습니다. 그래야 한 워커가 아직 처리하지 않은 일을 실수로 끝났다고 판단하지 않습니다.

현재 한계: 삭제는 아직 전체 재평가로 돌아간다

여기서 “Differential 아이디어를 채택했다”와 “모든 변경을 완전히 증분 처리한다”를 구분해야 합니다.

현재 Wirelog는 추가된 사실을 변경분으로 전파합니다. 하지만 사실이 삭제되면 정확성을 지키기 위해 영향받은 계층의 고정점을 전체 재평가하고 이전 결과와 차이를 구합니다. 즉 삭제까지 완전히 증분 처리하는 단계는 아닙니다.

이 한계가 있어도 Z-set, 변경분 색인, 논리 시간, frontier는 앞으로 더 정교한 철회 처리와 병렬 실행을 구현할 수 있는 공통 토대가 됩니다.

왜 Rust 구현을 그대로 사용하지 않았을까

Timely와 Wirelog는 목표가 다릅니다.

Timely는 Rust로 작성한 범용 분산 데이터플로우 런타임입니다. Wirelog는 작은 장치나 다른 프로그램 안에도 넣을 수 있는 C11 Datalog 라이브러리를 지향합니다. 메모리 사용을 예측하기 쉽고, 다른 언어에서 C 함수를 부르기 쉬우며, 같은 종류의 값을 나란히 저장해 CPU가 한꺼번에 처리하기 좋은 구조를 원합니다. 미래에는 계산 부분을 FPGA나 GPU로 교체하는 것도 목표입니다.

그래서 Wirelog는 다음과 같이 선택했습니다.

Timely-Differential에서 가져온 생각	Wirelog 방식으로 바꾼 부분
논리 시간	(변경 차수, 반복 횟수, 워커)
+1, -1 변경 장부	C11 구조체에 저장한 존재 횟수
이전 결과를 재사용하는 색인	열 단위 저장소와 변경 목록
frontier에 의한 완료 판단	규칙·계층·워커별 완료 지점
병렬 실행 구조	여러 계산 경로와 교체 가능한 실행부

장점은 계산 모델을 활용하면서 Wirelog의 작은 배포 크기와 C 환경을 지킬 수 있다는 것입니다. 단점은 원래 Rust 구현의 정확성을 자동으로 물려받지 못한다는 점입니다. Wirelog가 Z-set, frontier, 철회, 워커 진행 상태에 관한 테스트를 별도로 많이 두는 이유입니다.

결국 왜 선택했는가

단순히 “빠르다고 알려진 기술”이어서가 아닙니다. Timely-Differential은 계속 변하는 재귀 계산을 설명할 공통 언어를 제공합니다.

• +1, -1은 무엇이 추가되고 삭제됐는지 말해 줍니다.
• (epoch, iteration)은 외부 변경과 내부 반복을 연결합니다.
• 변경분 색인은 이전 계산을 다음 변경에서 재사용하게 합니다.
• frontier는 어디까지 안전하게 끝났는지 말해 줍니다.
• worker progress는 병렬 실행에서도 성급한 완료 판단을 막습니다.

정적인 Datalog 파일을 한 번 계산하고 끝낸다면, 직전 반복에서 새로 나온 사실만 다음 반복에 사용하는 고전적인 방법으로 충분할 수 있습니다. 이 방법을 세미나이브 평가라고 합니다. 하지만 Wirelog가 풀려는 문제는 사실이 계속 추가되고 삭제되는 동안 재귀 결과를 유지하는 것입니다. 이 문제에는 시간, 변경, 완료를 함께 다루는 Timely-Differential의 관점이 잘 맞습니다.

마치며

Timely Dataflow의 핵심은 데이터를 무조건 빨리 보내는 것이 아닙니다.

아직 생길 수 있는 일과 이제 절대 생기지 않을 일을 구분하는 것.

논리 시간은 데이터의 작업 차수를 나타냅니다. capability는 특정 시간의 데이터를 더 만들 수 있는 권한입니다. frontier는 그 권한과 전송 중 메시지를 모두 확인해 “여기 이전은 끝났다”고 알려 주는 경계입니다.

이 장부가 있기 때문에 여러 워커가 제각각 움직이고 결과가 루프를 돌아도 계산의 끝을 찾을 수 있습니다. Differential Dataflow는 이 토대 위에서 바뀐 부분을 재사용하고, Wirelog는 핵심 아이디어를 C11 Datalog 엔진에 맞게 옮기고 있습니다.

처음에는 용어가 많아 보이지만, 택배 분류센터의 질문 하나로 돌아가면 됩니다.

“지금 상자가 안 보이는 것인가, 아니면 더 올 수 있는 상자가 정말 없는가?”

Timely Dataflow는 두 상황을 구분하는 시스템입니다.

---

더 읽을 자료

• Timely Dataflow GitHub 저장소
• Timely Dataflow 공식 책: Core Concepts
• Timely Dataflow 공식 책: Progress Tracking
• Timely Dataflow 공식 책: Iteration
• Naiad: A Timely Dataflow System
• Wirelog GitHub 저장소

관련 글

• Datalog의 증분 계산
• Timely Dataflow를 위한 전송 프로토콜은 왜 새로 필요한가
• WITH RECURSIVE로는 답답했던 질문들: 내 노트 그래프에 Datalog 얹기

참고 문헌

1. D. G. Murray, F. McSherry, R. Isaacs, M. Isard, P. Barham, and M. Abadi, “Naiad: A Timely Dataflow System,” in Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP ’13), ACM, 2013, pp. 439–455. Available at: https://sigops.org/s/conferences/sosp/2013/papers/p439-murray.pdf