같은 거래 의존성, 세 가지 병렬 실행 방식
두 거래를 함께 실행했는데 하나는 금방 끝나고 다른 하나는 오래 걸린다고 하자. 먼저 끝난 거래의 결과만 있으면 시작할 수 있는 다음 거래가 있다. 그 거래도 느린 쪽이 끝날 때까지 기다려야 할까?
순차 실행과 같은 원장 결과를 지키는 조건만으로는 답이 정해지지 않는다. 필요한 결과가 준비됐다는 것과, 그 일을 실제 작업자에게 맡기는 것은 다른 결정이기 때문이다.
니고는 거래 사이의 의존 관계를 DAG라는 그래프로 표현하고, 그 그래프를 실행하는 방법으로 WAVE, READY_QUEUE, WORK_FIRST_CONTINUATION을 구현했다. 이름을 외우기 전에, 같은 거래 묶음에서 어떤 기다림을 줄이려는지 살펴보자.
빠른 갈래 뒤에 송금 하나를 더 붙인다
A가 가진 자산 100에서 B에게 20, C에게 10, D에게 5를 보내려 한다. 자산의 소유자와 수량을 담는 기록인 StateCell을 소비하고 새 기록을 만드는 다섯 거래로 나누어 보자. 소유자의 직접 이전이 허용된 자산이며, 모두 A가 서명한 유효한 Direct Cell 거래라고 가정한다. 추가 발행·소각과 수수료 금액은 없고, 다섯 거래를 담을 블록 실행량도 충분하다.
- ① 나누기: A의 100을 소비하고 A 소유의 왼쪽 60과 오른쪽 40을 만든다.
- ② B에게 보내기: 왼쪽 60을 소비해 B의 20과 A의 40을 만든다.
- ③ C에게 보내기: 오른쪽 40을 소비해 C의 10과 A의 30을 만든다.
- ④ D에게 보내기: ②가 남긴 A의 40을 소비해 D의 5와 A의 35를 만든다.
- ⑤ 잔액 합치기: ④의 35와 ③의 30을 소비해 A의 65를 만든다.
최종 상태는 A=65, B=20, C=10, D=5, 합계 100이다. B·C·D에게 보낸 기록은 합치기의 입력이 아니며 각자 남는다. ①의 오른쪽 40과 ②가 남긴 왼쪽 40은 수량만 같고 서로 다른 기록이다. 두 갈래는 수수료를 포함해 다른 변경 대상도 공유하지 않는다고 가정한다.
화살표는 뒤 거래가 앞 거래의 결과를 필요로 한다는 뜻이다. 숫자는 그 사이에서 전달되는 A의 자산 수량이다. B의 20, C의 10, D의 5는 본문에서 설명한 대로 남는다.
후보 순서는 ① → ② → ③ → ④ → ⑤로 정한다. ①이 끝나면 ②와 ③은 함께 계산할 수 있다. ④는 ②의 결과만 필요하고, ⑤는 ③과 ④를 모두 기다려야 한다. 중요한 차이는 ④가 ③보다 뒤에 놓였어도, ③의 계산 결과를 필요로 하지는 않는다는 점이다. 따라서 ③이 진행 중일 때 ④를 계산할 기회가 있다. 최종 거래 반영 순서는 여전히 원래 후보 순서다.
DAG는 반드시 지켜야 할 기다림을 표현한다
그림의 각 점은 거래이고, 화살표는 먼저 처리해야 하는 관계다. 화살표에 방향이 있고 그 방향을 따라가다 출발점으로 돌아오는 고리가 없는 그래프를 DAG, 즉 방향성 비순환 그래프라고 부른다.
니고의 실행 그래프는 정해진 후보 순서에서 앞 거래가 뒤 거래에 미치는 영향을 연결한다. 화살표가 작은 후보 번호에서 큰 번호로만 향하므로, 서로가 서로의 완료를 기다리는 고리가 생기지 않는다. 블록의 합의 구조를 다른 형태의 DAG로 바꾸는 것이 아니라, 한 노드 안에서 거래를 계산하기 위한 계획이다.
화살표는 자산이 이동할 때만 생기지 않는다. 앞 거래가 쓰는 기록을 뒤 거래가 읽는 경우, 앞 거래가 읽은 기록을 뒤 거래가 바꾸는 경우, 두 거래가 같은 기록을 바꾸는 경우에도 원래 순서를 지켜야 한다. 같은 정책을 함께 읽기만 한다면 그 사실만으로 의존 관계가 생기지는 않는다.
이 판단에는 입력과 출력뿐 아니라 자산 정책, 수수료 처리와 존재하지 않는 기록의 조회도 들어간다. 반대로 같은 입력을 두 번 소비하는 요청은 화살표를 붙인다고 둘 다 유효해지지 않는다. DAG는 거래 자체의 유효성 검사를 대신하지 않는다.
그래프가 알려주는 것은 어떤 선행 결과가 준비돼야 하는가까지다. 준비된 거래를 언제 시작하고 어느 작업자에게 맡길지는 실행을 배정하는 스케줄러가 결정한다. 같은 DAG에도 여러 배정 방식이 가능한 이유다.
WAVE: 한 묶음을 끝낸 뒤 다음 묶음으로
먼저 동시에 실행할 수 있는 거래를 단계별로 묶어보자.
이 예제에서는 ① → ②·③ → ④ → ⑤라는 네 묶음이 나온다.
현재 묶음의 계산을 모두 마치고 확인한 결과를 다음 묶음에 전달하는 방식이 WAVE다.
이 방식은 묶음 안에서 볼 기준 상태와 다음 묶음에 넘길 상태의 경계가 분명하다. 니고는 기존의 이 실행 구조를 기준 스케줄러로 두고, 다른 배정 방식도 같은 결과를 내는지 비교할 수 있게 했다.
대신 같은 묶음의 가장 느린 거래를 기다린다. ②가 끝나도 ③이 아직 진행 중이면 다음 묶음인 ④는 시작하지 않는다. ④가 ③의 결과를 필요로 하지 않는다는 사실과 별개로, 묶음 전체의 완료가 다음 단계의 조건이기 때문이다.
차이를 보기 위해 한 번에 두 거래까지 계산할 수 있고, ③은 네 시간 칸, 나머지 거래는 각각 한 칸 걸린다고 가정하자. 금액에서 실행 시간을 계산한 것이 아니라, 배정 원리를 설명하기 위해 정한 값이다. 작업 배정·상태 전달·검증의 추가 시간도 여기서는 생략한다.
WAVE에서는 ①을 0–1, ②를 1–2, ③을 1–5에 계산한다. ④는 ②가 끝난 시점인 2가 아니라 묶음이 끝나는 5부터 시작한다. ④가 5–6, ⑤가 6–7에 실행되므로 전체는 일곱 칸이다.
READY_QUEUE: 필요한 결과가 준비되면 대기열로
④에게 필요한 것은 ②의 결과다. 이 조건이 충족되는 시점에 실행 기회를 주려는 방식이 READY_QUEUE다. 실행할 준비가 된 거래를 크기에 상한이 있는 대기열에 넣고, 여유가 있는 작업자에게 배정한다.
니고는 앞 거래의 계산이 끝났다는 통지만 보고 뒤 거래를 시작하지 않는다. 결과와 실제 상태 접근을 검증하고, 뒤 거래가 사용할 임시 상태에 그 변경을 반영한 다음 남은 선행 거래 수를 줄인다. 모든 선행 결과가 준비된 거래만 실행 대기열에 들어간다. 이 반영은 다음 계산을 위한 임시 상태 전달이며 DB에 확정 저장하는 단계는 아니다.
예제에서는 ②의 결과가 준비되는 시점 2에 ④를 배정할 수 있다. 여유 작업자가 있으므로 ④는 2–3에 끝나고, ③은 계속 5까지 실행한다. ⑤는 두 결과가 모두 필요한 거래이므로 ③이 끝난 뒤인 5–6에 계산한다. 전체는 여섯 칸이다.
⑤에는 선행 거래가 두 개라는 점이 중요하다. ④가 먼저 끝났다는 이유로 시작하면 ③이 만들 A의 30이 없다. 두 결과를 모두 전달받아야 합치기가 준비된다. 대기열은 이 조건을 완화하지 않는다.
READY_QUEUE를 검토한 출발점은 이런 불필요한 묶음 대기를 줄이는 것이었다. 다만 준비된 거래를 찾아 대기열에 넣고 꺼내며, 그 거래가 볼 상태를 만드는 일도 비용이다. 준비됐다는 것은 실행 가능하다는 뜻이며, 작업자가 모두 바쁘면 실제 시작은 늦어질 수 있다.
WORK_FIRST_CONTINUATION: 끝낸 작업자가 다음 일을 이어서
대기열을 사용하면 거래 하나를 끝낼 때마다 다음 일을 등록하고 다시 배정하는 과정이 생긴다. 이번에는 일을 끝낸 작업자가 바로 이어갈 수 있는 후속 거래가 있는지 살펴보자.
WORK_FIRST_CONTINUATION은 새로 준비된 후속 거래 중 하나를 현재 작업자가 이어서 맡는 방식이다. 니고는 그중 후보 순서가 앞선 거래를 우선 이어가고, 함께 준비된 다른 거래는 공유 대기열에 남긴다. 거래마다 실행 작업을 새로 제출하기보다, 정해진 수의 작업이 다음 거래를 계속 처리한다.
예제에서는 ①을 끝낸 작업자가 ②를 이어서 맡고, 다른 작업자가 대기열에서 ③을 가져갈 수 있다. ②를 끝낸 작업자는 준비된 ④를 이어서 처리한다. ④가 끝나도 ⑤는 아직 ③을 기다리므로 곧바로 이어갈 수 없다. 이후 ③을 끝낸 작업자에게서 마지막 조건이 충족되면 ⑤를 이어갈 수 있다.
목표는 거래 사이에 꼭 필요한 기다림을 없애는 것이 아니라 다음 일을 배정받는 비용을 줄이는 것이다. 한 작업자가 한 갈래를 영구히 소유하는 구조도 아니다. 이어갈 일이 없으면 공유 대기열의 다른 일을 찾는다.
아래 그림은 같은 실행 시간을 가정한 세 방식의 계산 구간이다. 각 행은 작업자 번호가 아니라 거래 번호다. 겹친 막대는 동시에 계산할 수 있다는 뜻이다.
시간 칸은 설명용 단위이며 실측값이 아니다. 실제 스레드 배정 기록을 나타내는 그림도 아니다.
이 그림에서 WORK_FIRST가 READY_QUEUE보다 더 짧아지지 않는 것은 자연스럽다. 줄이려는 배정 비용을 애초에 시간에서 빼놓았기 때문이다. 실제 이득을 확인하려면 그 비용까지 포함해 측정해야 한다.
Direct Cell과 Native Program은 어떻게 같은 구조에 들어올까
이 설계를 쓰려면 실행 전에 거래가 읽고 바꿀 상태를 충분히 구체적으로 알 수 있어야 한다. Direct Cell 거래는 소비할 입력과 만들 출력을 드러낸다. 니고의 거래 실행 계층인 Core는 여기에 수수료 기록과 자산 정책 조회를 더해 실제 접근 범위를 분석한다.
Native Program 거래도 필요한 상태와 제안하는 변경을 명시한다. Native Program의 검증 구조에서 설명한 것처럼, 프로그램은 전달받은 상태와 변경안을 검증하고 Core는 그 결과를 실제 전이와 대조한다. 프로그램이 전달받은 범위 밖의 원장 상태를 임의로 조회하거나 변경하지 못하도록 제한된 실행 환경도 전제한다. 병렬 실행을 위해서는 프로그램·정책의 기준까지 확인하고, 프로그램이 실패해 수수료 변경만 남는 경로도 접근 범위에 포함한다.
따라서 같은 Native Program을 호출한다는 이유만으로 모든 거래가 서로 기다리는 것은 아니다. 서로 다른 기록을 바꾸고 공통 정책은 읽기만 한다면 함께 실행할 여지가 있다. 반대로 입력 자산이 달라도 같은 승인 한도나 수수료 기록을 바꾼다면 그 의존 관계를 고려해야 한다.
Core가 거래별 접근 범위를 제공하고, 블록 실행 계층이 DAG를 만들고 계산을 배정한다. Direct Cell 처리 코드나 Native Program 자체가 스레드를 만들거나 스케줄러를 선택하는 구조는 아니다. 업무 로직과 여러 거래의 실행 배치를 분리하는 것이다.
공통 구조에 참여한다는 것과 세 배정 방식을 모두 사용한다는 것은 구분해야 한다. 현재 병렬 경로에서 Direct Cell만으로 구성된 구간은 설정한 세 전략 중 하나를 선택할 수 있다. Native Program이 포함된 구간은 WAVE를 사용한다. 일반 EVM 거래와 시스템 기준을 바꾸는 작업은 순차 처리하는 경계로 두고, 그 앞뒤에서 병렬 구간을 나눈다.
니고는 WAVE를 기준으로 두고 뒤의 두 방식을 Direct Cell 구간의 대안으로 구현·비교했다. 현재 WAVE가 기본 스케줄러이고 두 대안은 실험 전략이다. 병렬 실행 자체도 일반 설정에서는 꺼져 있으며, 이를 활성화하는 설정과 어떤 스케줄러를 쓸지는 별개의 선택이다. 거래 특성에 따라 최적 전략을 자동으로 골라주는 기능이 완성됐다는 뜻은 아니다.
하나의 그래프, 서로 다른 비용
WAVE는 묶음의 경계를 따라 상태를 전달한다. READY_QUEUE는 거래별 의존성이 풀릴 때 실행 기회를 열고, WORK_FIRST_CONTINUATION은 그 기회를 현재 작업자가 이어받아 배정 비용을 줄이려 한다. 세 방식 모두 같은 DAG의 의존 관계를 지켜야 하며, 최종 반영 순서와 검증 조건도 바꾸지 않는다.
예제에서는 ④를 먼저 실행해 전체 계산을 한 칸 줄였다. 하지만 거래 자체가 매우 가볍다면 의존성을 관리하고 상태를 준비하는 비용이 그 이득보다 클 수도 있다. 블록 실행 앞뒤의 검증·저장 등이 더 오래 걸리면 계산 구간의 개선이 전체 시간에는 작게 나타날 수 있다.
이제 다음 질문은 분명해진다. 기다림과 배정 비용을 줄이려던 선택이 실제 측정에서도 효과가 있었을까? 병렬화의 효과는 어디에서 사라졌을까에서는 니고의 측정 기록을 통해 실행 시간과 전체 처리 시간을 나누고, 이미 검증한 결과를 재사용할 때 어떤 방식이 유리해지는지 살펴본다.