Krabby를 위한 동시성, 비동기성, 배칭, 증분 컴파일을 갖춘 쿼리 시스템의 설계.
올해 초부터 나는 Krabby를 위한 쿼리 시스템을 천천히 설계해 왔다. 가만히 앉아 매우 열심히 생각한 지 다섯 달이 걸렸지만, 이제는 설계를 명확히 파악했다고 믿는다. Krabby에 왜 쿼리 시스템이 필요한지(한동안 필요 없다고 생각했기 때문에), 내가 원했던 특별한 기능은 무엇인지, 그리고 모든 것이 어떻게 맞물리는지를 설명하겠다.
Krabby에 대한 나의 최초 구상은, 작업이 자신의 출력을 그것을 필요로 하는 이후 작업으로 “밀어 넣는” 푸시 기반 아키텍처였다. 이것이 “풀 기반” 쿼리 시스템보다 오버헤드가 낮을 것이라고 생각했다. 특히 컴파일 초기 단계에서는 작업 간 의존성을 미리 알 수 있으므로 실현 가능해 보였다. 컴파일러는 같은 종류의 독립적인 작업을 쉽게 병렬화할 수 있는 방식으로 많이 실행할 수 있었다.
이는 내 이름 해결 알고리즘의 설계에 큰 영향을 미쳤다. 대상 크레이트의 src/ 폴더에서 Rust 소스 파일을 (종종 선제적으로) 파싱하고, 그 결과를 Rust 항목의 전역 데이터베이스에 주입하려 했다. 이 데이터베이스는 아직 발견되지 않은 항목에 대한 보류 중인 참조도 저장하며, 해당 항목이 추가되면 참조를 해결한다.
한동안 이 설계가 꽤 마음에 들었지만, 지난 12월 구현의 세부 사항을 파고들면서 설계에 중요한 결함이 있음을 깨달았다.
전역 데이터베이스가 보류 중인 참조를 추적하므로, 이는 사실상 특수화된 쿼리 시스템이었다. 나는 그 복잡성을 피하지 못했다.
게으른 방식이므로 CPU 캐시를 잘 활용하지 못한다. 항목은 첫 사용보다 훨씬 일찍 추가되어 캐시에 삽입될 수 있다. 항목이 처음 필요할 때 조회하는 즉시 방식은 캐시 활용을 개선할 것이다.
불균형한 의존성 그래프(직렬로 처리해야 하는 긴 작업 사슬을 포함하는 그래프)를 효율적으로 다루지 못한다. 이 아키텍처는 의존되는 정도가 큰 작업을 식별할 수 없고, 실행 시점도 제어하지 않는다. 그런 작업은 컴파일 매우 늦게 실행되어, 다른 모든 일이 끝난 뒤 하나의 CPU가 계속 일하게 만들 수 있다. 반대로 풀 기반 접근법은 수요 주도 우선순위화 요소를 추가한다.
풀 기반 접근법은 서로 다른 목표(예: cargo check, cargo build, 또는 특정 Rust 항목 식별)를 쉽게 대상으로 삼을 수 있다. 이는 LSP에서 Krabby를 사용할 수 있게 하는 데 매우 중요하다. 여기서는 사용자가 시작한 동작(예: foo()의 모든 참조 찾기)을 관련 없는 작업을 최소화하며 가능한 한 빨리 평가해야 한다.
이로 인해 내 이름 해결 구현 작업은 완전히 멈췄다. 2026년 아주 시작부터 쿼리 시스템을 설계하기 시작했고, housekeeping을 작성하느라 샌 두 달을 제외하면 그것이 내 주된 관심사였다. 말해 두겠다. 쿼리 시스템 설계는 엄청난 작업이다!!
나는 코드베이스가 근본적으로 역사적인 설계 선택에 의해 제한된다는 사실에 늘 슬퍼한다. 프로그램의 아키텍처 방식은 그것을 특수화하고, 쉽게 벗어날 수 없는 경로에 놓는다. 나는 수년 전의 결정이 그 가능성을 전혀 고려하지 않았다는 이유로 기능과 최적화가 막히는 모습을 계속 본다. 원래 세상은 그런 법이지만, 나는 그것이 가슴 아프다.
모든 프로젝트에서, 특히 Krabby에서는 가능한 한 철저히 설계 공간을 탐색하려 한다. 다섯 걸음, 어쩌면 열 걸음 앞을 내다보려 한다. 내가 예견할 수 있는 모든 가능성을 우아하게 허용하도록 설계하려 한다. 물론 이는 틀릴 수 있지만, 시도했다는 사실에서 위안을 얻는다. 그것이 내가 7천 단어짜리 블로그 글을 쓰는 변명이다.
다음은 Krabby의 쿼리 시스템을 위해 생각한 흥미로운 기능 목록이다. 주로 rustc의 쿼리 시스템 및 salsa와 다른 점에 집중한다. 이 기능들을 모두 즉시 구현하려는 것은 아니지만, 설계에 그 요구 사항을 통합하려고 노력했다.
이것은 독특한 기능은 아니지만 설계에 가장 큰 영향을 준다고 생각한다. rustc의 프런트엔드는 이미 동시성을 지원한다(오랫동안 개발되어 왔지만, 이제 CI의 일부로 테스트된다). Krabby에서는 병렬성을 훨씬 더 적극적으로 받아들이고, 첫날부터 요구 사항으로 취급하여 나머지 설계를 형성하게 하고 싶다.
housekeeping 크레이트는 동시성을 향한 중요한 단계였다. 스레드 간에 공유되는 리소스를 해제하는 안전한 방법, 즉 고성능 동시 자료 구조를 구축하는 데 필수적인 재료를 제공한다. 이런 구현은 다른 것도 있지만, housekeeping은 추가 기능과, 내가 바라건대, 더 나은 성능을 제공한다. 언젠가 그 설계를 글로 정리할 계획이다.
비동기성: 작업은 일시 정지하고 재개할 수 있어야 한다. 이것만으로 여러 기능이 열리므로 하위 목록을 둘 만하다.
작업이 다른 스레드에서 실행 중인 무언가에 의존한다면, 일시 정지하여 현재 스레드에서 다른 작업이 실행되게 하고, 의존 작업이 완료되면 재개할 수 있다. salsa는 비동기 작업을 지원하지 않으며, 이런 상황에서는 현재 스레드를 차단해 처리한다.
작업은 동시에 여러 다른 작업에 의존할 수 있고, 모두 완료된 뒤에만 재개할 수 있다. 이는 두 번째 종류의 배칭이다. 작업은 동시에 여러 쿼리를 만들고, 그중 하나라도 즉시 계산할 수 없으면 일시 정지할 수 있다. 이는 async 함수의 구조적 동시성과 유사하다. 여러 퓨처가 하나씩 .await되는 대신 동시에 완료되기를 기다린다.
비동기 I/O 작업을 구현할 수 있다. Krabby는 Cargo를 통합하므로, 핵심 비동기 I/O 작업은 네트워크에서 리소스를 가져오는 일이다. 이를 통해 Krabby는 쿼리로 Cargo의 기능을 완전히 구현할 수 있다.
시스템 호출을 배치하고 오버헤드를 줄이는 Linux 하위 시스템인 io_uring의 사용이 열린다(종종 엄청난 폭으로!). 다소 놀랍게도 Rust 컴파일에서 I/O는 때때로 병목이 될 수 있다. 증분 컴파일 상태를 저장할 때, 그리고 이전 컴파일 이후 변경 사항을 식별하기 위해 소스 파일을 불러올 때 발생한다.
Rust의 실제 async 메커니즘으로 이를 구현하지는 않을 것이다. 성능에 관한 우려가 있기 때문이다. 몇몇 구체적인 작업 종류와 그 비동기 상태가 어떤 모습일지를 생각해 보았고, async를 사용해도 상용구가 크게 줄지는 않는다고 결론지었다. 수동 구현은 메모리와 실행 시간 오버헤드가 더 적을 것이다.
배칭은 Krabby에서 자주 탐색하려는 원칙이다. 즉각적이고 작은 이점(예: 코드 캐시 활용 개선)은 있을 것이나, 진짜 가치는 먼 미래에 올 것이다. Rust 컴파일러의 특정 작업을 명시적으로 배치 처리하는 방식으로 작성할 수 있고, 그것이 예측하지 못한 최적화를 열 수 있는 실질적인 가능성이 있다고 생각한다.
지금 수치를 갖고 있지는 않고 곧 수집할 계획이지만, 컴파일러에서 어디에나 나타나는 해시 테이블 조회는 배칭으로 크게 최적화할 수 있다. 거의 전적으로 메모리 바운드이므로, 지연 시간은 처리량보다 훨씬 나쁘다. 실행은 느리지만 CPU 리소스를 지나치게 많이 차지하지는 않는다. 현대 CPU는 이미 ILP에 매우 뛰어나며 해시 테이블 조회를 위한 메모리 가져오기가 진행되는 동안 다른 작업을 수행할 수 있다. 명시적 배칭이 실행 시간을 추가로 20-40% 개선할 수 있다고 생각한다.
배칭이 열어 줄 다른 최적화는 당연히 SIMD다. SIMD 기반 렉서를 실제 환경에서 찾을 수는 있겠지만, AST 낮추기나 타입 검사처럼 더 복잡한 컴파일 단계에 SIMD를 탐색한 경우는 본 적이 없다. 무언가 나올지는 모르지만 이런 길은 탐색할 가치가 있으며, 배칭이 이를 가치 있게 만들 가장 좋은 기회라고 믿는다.
“잠깐, 작업을 분배할 다중 스레드 큐가 필요하고, 거기에 우선순위화도 지원하게 하고 싶다고? 그걸 어디서 구할 건데??” 친애하는 독자여, 알고 보니 작년에 Krabby의 푸시 기반 아키텍처를 위해 이미 하나를 작성했다! 그리고 빠르다! 곧 보겠지만 작업 큐는 다른 여러 기능의 구현도 돕는다.
cargo CLI 구현, Cargo.toml 파싱, 의존성 자체 해결을 통해 Cargo 지원을 내장할 것이다. 여전히 rustc처럼 사용하거나 자신의 빌드 시스템에 패치할 수 있다. 이것은 쿼리 시스템의 기능은 아니지만 광범위한 결과를 낳으므로 언급할 만하다.나는 cargo build와 cargo check가 불필요하게 크레이트를 다시 빌드하고 아주 오랫동안 단일 CPU를 쓰는 경우를 자주 만난다. 단순한 예로, rustc 작업 중 rustc_ast에서 사용되지 않는 코드를 제거했더니 _다른 48개 크레이트_가 90초 넘게 다시 빌드되었다. 여기에는 여러 문제가 있다:
* Cargo는 `rustc`를 매우 단순하게 이해한다. 크레이트의 소스 파일([체크섬 사용 추적 이슈](https://github.com/rust-lang/cargo/issues/14136) 참고) 또는 의존성의 수정 시간이 바뀌면 Cargo는 `rustc`를 다시 호출한다. `rustc`의 모든 호출이 다른 출력을 낸다고 가정하는 듯하므로, 그 출력에 의존하는 모든 크레이트도 다시 빌드한다. `touch compiler/rustc_ast/src/lib.rs`를 실행해 파일의 내용은 바꾸지 않고 mtime만 바꾼 뒤 다시 컴파일해도, 단순한 아무 작업 없음이어야 하는데 48개 크레이트를 다시 빌드하고 15초가 걸렸다.
* `rustc`는 쿼리 시스템을 사용하여 작업 반복을 피하지만, 컴파일 후반 단계에서만 그렇다. 파싱, 이름 해결, 매크로 확장은 오늘날 쿼리 시스템의 일부가 아니다. `rustc`의 모든 호출은 이 단계들을 완전히 반복하게 한다.
* `rustc`는 크레이트의 의존성이 시작 전 컴파일되기를 요구한다. 겉으로는 합리적이지만 병렬성을 심각하게 방해하며 기능적으로 필수도 아니다. 서로 의존하는 크레이트의 긴 사슬에서는, 가장 안쪽 크레이트의 변경이 사슬 전체를 직렬로 다시 빌드하게 한다. `rustc`는 이미 이를 상각하려 한다. 코드 생성을 나머지 컴파일과 분리하여, 각 크레이트의 컴파일 전반부가 그 의존성의 코드 생성과 병렬로 일어나게 한다. 문제를 완전히 해결하려면 세밀한 접근이 필요하다.
Krabby에서는 이 문제들을 피할 수 있다고 믿는다. Krabby는 의존성 그래프의 모든 크레이트를 동시에 컴파일하며, 한 크레이트가 다른 크레이트에 의존하더라도 둘을 병렬로 컴파일하기 시작할 수 있다. Krabby의 의존성 그래프는 크레이트가 아니라 Rust 항목 단위로 표현되므로, Krabby의 병목을 만들려면 서로 의존하는 Rust 항목의 긴 사슬이 필요하다. 그리고 Krabby는 그러한 많은 경우를 우회할 것이다. 예를 들어 함수 호출 foo()는 foo의 구현이 아니라 시그니처만으로 타입 검사할 수 있다. 따라서 서로 호출하는 함수가 20개라면 Krabby는 20개 함수 시그니처를 모두 해결하고, 이어서 20개 함수 호출을 병렬로 모두 처리할 수 있다. 최종 사용자에게 단일 CPU 병목의 답답함을 대부분 없앨 수 있다고 생각한다.
Cargo 통합은 오버헤드를 더하기도 빼기도 한다. Krabby는 모든 데이터 조각(예: Rust 항목)이 어느 크레이트에서 왔는지 추적해야 하는 반면, rustc는 보통 컴파일 중인 크레이트만 생각하면 된다. 반면 Krabby는 의존성 크레이트 사이에서 데이터를 디스크 파일에 쓰고 읽는 대신 메모리를 통해 전달할 수 있다. 병목 완화와 관계없이, Cargo 통합은 컴파일을 상당히 빠르게 하리라 확신한다.
이는 단순해 들리지만 정말 야심 찬 변화이며 매우 기대된다. rustc의 증분 캐시는 가장 최근 컴파일 중 사용한 정보만 보관한다. 가장 최근 컴파일에서 쓰이지 않은 이전 컴파일의 데이터는 제거된다. 따라서 이전 추가를 되돌리거나 Git 커밋 사이를 오가는 단순한 변경도 쉽게 rustc를 혼란스럽게 하여 불필요한 작업을 다시 하게 만든다. 게다가 rustc는 이전 컴파일의 모든 정보가 증분 캐시에 있어야 한다. target 폴더의 크기를 제한할 수 없다(Cargo를 쓰면 문제가 훨씬 심해진다).
Krabby에서는 쿼리 데이터를 간단한 키-값 캐시에 저장하고, 캐시 축출 정책(예: LRU)을 구성할 수 있게 할 계획이다. 예를 들어 “이 함수 타입 검사” 쿼리는 함수 내용으로 키가 정해진다. 사용자에게 보이는 많은 이점을 열 것이라 생각한다:
* 캐시 최대 크기를 구성할 수 있다. 예를 들어 `target` 폴더를 1GiB로 제한할 수 있다. Krabby가 원하는 모든 데이터를 거기에 넣을 수 없다면 데이터를 더 자주 재계산해야겠지만 드물 것이고 경고를 줄 수 있다. 50GB `target` 폴더 폭발을 피하기에는 가치 있는 절충이다. 중요하고 계산 비용이 큰 데이터를 우선시하도록 캐시 축출 정책을 조정할 수 있다.
* Cargo 기능 플래그를 바꿔도 캐시 대부분을 재사용할 수 있다. 오늘날 Cargo는 대상 크레이트와 기능 플래그를 키로 하여 `target`에 여러 증분 캐시를 저장한다. Cargo에서 다른 기능 플래그 집합을 컴파일하면 전체 재빌드가 일어나지만, Krabby에서는 그렇지 않을 것이다.
* 이에 따라, 서로 다른 기능 플래그로 해당 크레이트를 컴파일하더라도 속도 향상을 제공하는 일반적인 크레이트용 시스템 전역 캐시를 둘 수 있다. 이는 내장 `sccache`와 비슷하다. 자주 쓰이는 크레이트를 추적하고 이 캐시에 저장하는 것을 우선시할 수 있다.
* Krabby는 공유 캐시로 서로 다른 커밋에 있는 같은 코드베이스의 여러 체크아웃을 컴파일할 수 있다. 큰 코드베이스의 서로 다른 버전을 동시에 살펴볼 때(예: 버그 이분 탐색이나 벤치마킹) 믿을 수 없을 만큼 유용할 수 있다.
스트리밍 쿼리: Krabby는 때때로 데이터 컬렉션을 계산해야 한다. IDE의 “모든 참조 찾기” 명령, 글롭 임포트(즉, use foo::*), Cargo의 --workspace 옵션을 생각해 보라. 이 모든 경우에 컴파일러는 컬렉션 안의 모든 항목(모든 사용처, 모든 임포트 항목, 모든 Cargo 패키지)을 식별해야 한다. 어떤 항목은 빨리 발견되지만 다른 항목은 시간이 아주 오래 걸릴 수 있다. 다른 크레이트에 있는 참조, 자체 글롭 임포트를 포함하는 모듈로부터의 글롭 임포트, 또는 crates/** 같은 파일 시스템 글롭으로 식별되는 Cargo 패키지가 있을 수 있다. 스트리밍 쿼리는 모든 항목이 완전히 발견될 때까지 기다리는 대신, 항목을 발견되는 대로 반환하는 발상이다. 이는 지연 시간을 낮추고 작업을 줄이며 병렬성을 개선할 수 있다.
컴파일러 개발 가속: rustc 작업 중 나는 종종 tests/ui 테스트 모음을 실행한다. 이는 20,000개가 넘는 독립 Rust 파일을 컴파일하고 컴파일러의 출력(거의 항상 특정 오류 메시지)을 확인한다. 내 노트북에는 훌륭한 하드웨어가 있지만, tests/ui를 실행하는 컴파일러 빌드는 시간이 걸린다(160초에 21,532개 테스트, 초당 133개 테스트, 스레드당 초당 8개 테스트). 더 잘할 수 있다고 생각한다!
내 변경이 이 테스트 대부분과 관련 없었다는 것을 안다. 컴파일러의 쿼리 시스템은 이를 검증하는 데 도움이 될 수 있다. 컴파일러의 어느 부분, 따라서 어느 쿼리 구현이 바뀌었는지 감지할 수 있다면, 증분 캐시를 사용해 해당 쿼리만 다시 실행하고, 출력이 바뀌지 않았다면 빠르게 끝낼 수 있다.
몇 시간 동안 이를 생각해 보았는데, 안전하고 올바르게 구현하기가 정말 어렵다. 완전한 비증분 테스트가 이를 뒷받침해야 하며, 최선의 경우 주간 CI 실행으로 해야 한다. 하지만 가능해 보인다… 각 종류의 쿼리 코드를 별도 공유 라이브러리로 컴파일하고, 좋은 시작점으로 단순한 “이 파일이 바뀌었는가?” 메커니즘에 의존할 수 있다. 빌드 시간도 빨라질 것이라 생각한다.
이 모든 기능을 하나의 일관된 설계로 묶는 일은 정말 까다로웠다. 특히 동시성, 비동기성, 배칭은 미묘한 방식으로 서로 상호작용한다. 결합된 복잡성은 각 부분의 합보다 훨씬 크다. 하지만 내 설계가 모든 것을 고려한다고 생각한다(그러길 바란다!).
몇 가지 중요한 용어를 정의하자. 쿼리 시스템은 “이 크레이트의 Rust 에디션”이나 “foo!()의 확장” 같은 데이터 단위를 계산한다. 쿼리는 데이터 단위에 대한 요청이다. 같은 데이터는 여러 번 쿼리될 수 있다. 작업은 요청된 데이터를 계산한다. 어떤 데이터가 쿼리되면 이를 계산하는 작업이 실행된다. 실행 중 작업은 더 많은 데이터를 쿼리할 수 있다. 쿼리 시스템의 정의적 속성은 메모이제이션이다. 데이터가 여러 번 쿼리되어도 한 번만 계산되어야 한다.
쿼리 시스템은 cargo build 같은 최상위 작업으로 초기화된다. 가능한 한 빨리 작업을 완료하려 한다. 우리의 목표는 지연 시간, 즉 작업 시작과 끝 사이 시간을 최소화하는 것이다. 적극적으로 병렬화하고 작업을 재사용하여 이를 달성할 수 있다.
쿼리 시스템의 작업량은 작업과 쿼리의 그래프 또는 함수 호출 스택으로 볼 수 있다. 파일 하나 src/main.rs를 가진 Cargo 패키지 foo를 생각해 보자:
fn main() {
foo();
}
fn foo() {}
제안한 설계에 따라 foo를 컴파일할 때 관련될 작업의 단순화된 그래프다. 강조된 간선은 가능한 임계 경로를 나타낸다.
벌써 꽤 복잡하다! 구체적인 구현 요구에 상당히 가깝게 모델링하려 했다. 앞서 말한 기능 일부를 볼 수 있다. Cargo는 Krabby 내부에서 처리되고, 파싱 같은 초기 단계는 쿼리 시스템의 일부이며, 함수 호출은 피호출자의 본문이 아닌 시그니처만 필요로 한다.
이 그래프의 맥락에서 쿼리 시스템의 일은 작업을 가능한 한 효율적으로 실행하는 것이다. 유한한 수의 CPU가 주어졌을 때, 시간에 따라 그 CPU들에서 실행할 작업을 예약해야 한다. 이 예약 결정이 컴파일 종료 시점과 전체 지연 시간을 결정한다.
가능한 최선의 지연 시간(무한하고 완벽한 병렬성을 가정)은 서로 의존하는 가장 긴 작업 사슬, 즉 임계 경로로 제한된다. 임계 경로는 각 작업이 걸리는 시간을 고려해야 한다. 그래프에서는 가능한 임계 경로 하나를 굵은 빨간색으로 강조했다. 쿼리 시스템은 임계 경로를 식별하고 그 실행을 우선시하려 노력해야 한다.
이 그래프는 상당히 철저해 보일 수 있지만 많은 것을 놓친다. 특히 “foo() 찾기” 같은 작업이 왜 실행되었는지는 식별하지 않는다. 이는 이후 작업인 “main() 본문 이름 해결”에 필요했는데, 이후 작업이 실행되기 전에 어떻게 필요함을 알았을까? 이후 작업은 쿼리 시스템에 “foo() 찾기”가 필요하다고 알려야 했다. 그래프에 표시된 것보다 먼저 실행을 시작했음이 틀림없다. 다른 시각화인 호출 스택을 시도해 보자:
cargo build
Cargo.toml 불러오기
foo 컴파일
main() 찾기
src/main.rs 파싱main() 시그니처 이름 해결main() 코드 생성
main() 본문 타입 검사
main() 시그니처 타입 검사
main() 본문 이름 해결
foo() 찾기
src/main.rs 파싱foo() 시그니처 이름 해결foo() 시그니처 타입 검사
foo() 코드 생성
foo() 본문 타입 검사
foo() 본문 이름 해결foo() 시그니처 타입 검사같은 작업과 쿼리에 대한 호출 스택이다.
이는 매우 유용한 것을 보여 준다. 작업의 시작과 끝 경계다. “foo 컴파일” 같은 작업은 아주 이르게 시작하여 아주 늦게 끝나며, 많은 다른 작업을 포괄한다. 이전 그래프에 암시된 인과성을 강조한다. 작업은 다른 작업에 의존하지 않고도 그 작업에 의해 발생할 수 있다. “src/main.rs 파싱” 작업은 “Cargo.toml 불러오기” 작업에 의존하지 않는다. 하지만 후자의 결과 때문에만 호출되었다.
이 호출 스택은 조금 최적화할 수 있다. “main() 코드 생성”은 “main() 본문 타입 검사”가 완료된 뒤 “foo() 코드 생성”을 요청하지만, foo()가 더 일찍 필요하다는 점을 알아낼 수 있다. “main() 코드 생성”은 “main() 타입 검사”와 동시에 “main() 본문 이름 해결”을 직접 호출하고, 거기에서 foo()의 필요를 확인할 수 있다.
이 호출 스택 관점은 그래프보다 엄격히 우월하지는 않다. “src/main.rs 파싱” 작업을 여러 번 보여 준다. 병렬성을 가린다. 어떤 작업을 병렬로 실행할 수 있는지가 덜 분명하다. 두 시각화 모두 도움이 된다고 생각한다. 서로 다른 맥락에서 강점이 있다.
지금까지 이 절은 꽤 일반적이었다. Krabby 설계의 세부 사항으로 들어가자. 다음 절들은 시스템을 일관된 전체로 설명하도록 구성했으며, 각 절은 서로 다른 주제를 다룬다. 논문을 읽듯이 개요를 얻기 위해 각 절을 훑어보기를 권한다.
작업은 데이터 단위를 계산한다. 작업은 쿼리 시스템이 알고 있는 클래스의 인스턴스다. 클래스는 작업 구현의 구체적인 이름이며, 구체적인 Rust 타입 및 연관 코드다. 작업 메타데이터는 쿼리 시스템이 작업에 관해 관리하는 정보다.
작업에는 생명 주기가 있다. 작업은 쿼리되기 전 작업 큐에 들어갈 수 있다. 결국 작업 큐 또는 다른 작업의 쿼리 때문에 시작된다. 완료되기를 기다려야 하는 보류 중인 쿼리가 있다면 차단 상태가 된다. 보류 중인 쿼리가 모두 완료되면 재개된다. 결국 완료된다.
작업 구현은 구체적인 Rust 타입을 중심으로 한다. 이 타입은 작업의 생명 주기 전체(큐에 들어가거나 쿼리되는 시점부터 완료될 때까지)에 걸친 상태를 보유한다. 타입에는 여러 속성이 있다:
OnceLock과 유사한 컨테이너다. 작업의 메타데이터도 보유한다.슬롯은 쿼리 시스템 대신 사용자가 할당하고 관리할 수 있다. 이는 특히 Rust 경로를 항목으로 매핑하는 동시 “데이터베이스”를 작성하려는 이름 해결에 유용하다. 네임스페이스 간 선언 찾기와 글롭 임포트 해결 등 유용한 추가 연산을 제공하도록 데이터베이스를 구성할 것이다. 데이터베이스 안에서 직접 슬롯을 할당할 수 있다.
Future::poll()과 매우 유사하다. 작업 상태에 대한 참조와 쿼리 시스템 핸들을 받아 작업을 진전시키려 한다.다른 데이터에 대한 쿼리를 시작할 수 있다. 아무것도 반환할 필요가 없다. 쿼리 시스템은 작업이 만드는 모든 쿼리를 기록하고, 작업이 보류 중인 쿼리에 차단되었는지를 자동으로 판단할 수 있다. 아무것에도 차단되지 않았다면 완료되었으며, 미리 정해진 슬롯에 출력을 썼음이 틀림없다.
폴 함수는 손으로 구현하도록 의도되었다. 가능한 한 많은 데이터를 동시에 쿼리할 수 있고, 또 그래야 한다! 내가 알기로 대부분의 폴 함수는 단순한 패턴을 따른다:
* 알려진 모든 쿼리를 실행한다(이전 폴에서 보류된 것도 포함).
* 결과를 작업 상태에 누적한다.
* 이로 인해 새 쿼리가 생길 수 있다. 이들도 반복하여 실행한다.
* 모든 쿼리가 성공적으로 해결되었다면:
* 상태를 후처리하고 출력을 슬롯에 쓴다.
우선순위: 임시 휴리스틱으로 결정되며, 작업 큐에서 작업을 언제 시작할지 제어한다. 우선순위는 작업의 임계 경로 길이를 반영해야 한다(임계 경로에서 더 앞에 나타나는 작업은 더 높은 우선순위를 가져야 한다). 예를 들어 “크레이트 컴파일” 작업은 일반적으로 “함수 타입 검사” 작업보다 높은 우선순위를 가져야 한다. 대상 크레이트는 컴파일에 많은 시간이 필요할 수 있기 때문이다. 우선순위는 시간이 지나며 바뀔 수 있고, 이전 컴파일 세션의 통계를 활용할 수 있다.
배치 폴 함수: 작업 상태 목록에 폴 함수를 하나씩 호출하는 것과 동등하지만, 더 효율적일 가능성이 있다. 일반적인 제어 흐름(각 작업 상태에 대해 같은 단계 순서를 하나씩 따르는 방식)을 전치하여, 시퀀스의 각 단계마다 모든 작업 상태를 하나씩 처리할 수 있다. 이는 저수준 성능 개선을 제공할 수 있으며, (자동)벡터화 사용을 열 수도 있다.
쿼리 시스템은 생명 주기 전반에 걸쳐 작업에 관한 서로 다른 정보를 기록한다. 이 정보 대부분은 작업 슬롯에 저장된다.
작업 시작 전에는 어떤 정보도 저장되지 않는다.
작업이 시작되면 슬롯에 그렇게 표시된다. 표시된 뒤에는 다시 시작할 수 없으며, 이로써 작업이 메모이제이션된다. 작업이 다른 작업의 쿼리 때문에 시작되었다면, 그 연결은 여기서 명시적으로 기록되지 않고 실행 중인 스레드가 기록한다.
시작된 뒤 작업이 쿼리되면, 쿼리는 작업 슬롯에 기록된다. 이는 아주 드물어야 한다.
작업이 하나 이상의 차단된(보류 상태가 아닌) 쿼리를 기다린다면, 작업 슬롯은 차단된 쿼리 카운터와 작업 재개 수단을 수용한다. 쿼리가 끝날 때마다 카운터를 줄이고, 0에 도달하면 모든 차단된 쿼리가 완료되었으며 작업이 재개된다.
증분 컴파일을 위해 작업이 내보낸 쿼리 목록(순서대로)을 기록한다. 이 정보는 작업 슬롯에 저장되지 않으며, 증분 컴파일이 활성화된 경우에만 기록한다.
작업 클래스는 상태를 가진다. 클래스 핸들로 표현되며, 이를 통해 작업이 생산한 데이터를 쿼리할 수 있다. 클래스 핸들은 참조 카운팅되고 더 많은 쿼리가 나타날 수 있는 동안 유지된다. 드롭되면 연결된 모든 데이터도 드롭할 수 있다. 따라서 컴파일 중간에 상당한 데이터 덩어리를 해제할 수 있다.
좋은 예시이자 내가 가장 염두에 두는 사례는 이름 해결이다. 다음은 함수 본문에 대한 이름 해결 작업의 단순화된 아이디어다:
// AST를 HIR로 변환
struct NameResFnBody {
slot: Arc<Slot<FnBodyHir>>,
// 해결되지 않은 참조를 포함하는 HIR
hir: FnBodyHirBuilder,
// 포함 모듈의 스코프
scope: Arc<NameResScope>,
}
impl Task for NameResFnBody {
fn poll(&mut self, handle: &mut QuerySystemHandle) {
// `uref`는 예를 들어 `foo`, `util::block_on`
// `uref.base()`는 `foo`, `util`
for uref in self.hir.unresolved_refs() {
// `path`는 예를 들어 `takeaway{crate#123}::util`
let path = self.scope.get(uref.base());
if let Ready(decl) = handle.lookup_decl(path) {
// 매크로 확장을 유발하고 새 참조를 드러낼 수 있음
self.hir.insert(uref.user(), decl);
}
// 쿼리가 차단되어도 계속 진행
}
if !handle.blocked() {
// 모든 쿼리가 완료되었고, 함수가 해결됨.
self.slot.write(hir.finished());
}
}
fn priority(&self) -> u32 {
400 // 동적일 수도 있음
}
}
쿼리는 어떤 데이터에 대한 요청이다. 쿼리는 작업(소스)이 시작하고, 요청한 데이터는 다른 작업(대상)이 계산하므로, 위 실행 그래프에서 보았듯이 작업 간 연결로 볼 수 있다.
작업처럼 쿼리에도 생명 주기가 있다. 먼저 시작된다. 요청한 데이터가 이미 계산되었다면(즉 대상 작업이 완료되었다면), 즉시 완료로 표시된다. 그렇지 않으면 보류 상태다. 대상 작업은 아직 시작되지 않았거나, 드물게 이미 실행 중이다. 소스 작업을 담당하는 작업자 스레드는 기본 작업 슬롯을 잠그고 대상 작업을 시작하여 쿼리를 시작하려 한다. 대상 작업이 이미 실행 중이면 시작에 실패하고 쿼리는 차단된다. 차단된 쿼리는 대상 작업의 메타데이터에 등록되어, 완료 시 소스 작업을 재개할 수 있다.
쿼리는 순환을 형성할 수 있다. 한 쿼리 집합이 서로 의존하면 모두 무한히 차단된다. 순환이 언제나 오류인 것은 아니다. 이름 해결 중에는 무해하게 발생할 수 있고(예: 순환 임포트 해결 중), 트레이트 해결에서는 중요한 고려 사항이다. 쿼리 순환은 관련 작업 중 하나에 자신이 순환의 일부라고 보고하여 끊어야 한다. 작업은 이를 처리하는 방법을 선택할 수 있다. 멈추고 오류를 만들거나, 다른 인수로 순환 쿼리를 다시 시도할 수 있다. 순환 안의 작업 중 어느 것을 선택할지는 임의적이며, 결과는 그 선택에 의존해서는 안 된다. 순환은 복잡하고 직관적이지 않은 방식으로 중첩되고 얽힐 수 있음에 유의하라.
스트리밍 쿼리를 특별히 지원한다. 이는 결과가 컬렉션(순서 있는 Vec 또는 순서 없는 HashMap/HashSet)인 쿼리다. 결과를 점진적으로 반환할 수 있으며, 시간이 지나며 컬렉션에 추가한다. 작업이 그런 쿼리에 의존하면, 모든 결과가 아직 준비되지 않았더라도 지금까지 수집된 데이터를 관찰할 수 있다. 쿼리에 차단되지만, 새 데이터가 추가될 때마다 그리고 쿼리가 완료될 때 재개된다.
작업은 고정된 수의 작업자 스레드에서 실행된다. 작업자 스레드는 실행을 담당하는 진행 중 작업 집합과, 새 작업을 얻을 수 있는 작업 큐에 대한 참조를 보유한다.
작업자 스레드는 배치로 작업을 실행하려 한다. 새 작업과 기존 작업을 클래스별로 구성하고, 한 번에 한 클래스의 사용 가능한 모든 작업을 실행한다. 작업 구현이 정의한 배치 폴 함수를 사용한다. 알려진 각 작업 클래스(또는 최근 사용한 클래스)에 대해 보류 집합, 즉 시작하거나 재개할 준비가 된 그 클래스 작업의 집합을 유지한다. 이 집합들은 임의 순서로 선택해 실행한다. 집합에 작업이 아주 적으면, 먼저 작업 큐에서 정확히 그 클래스의 작업을 더 불러올 수 있다.
작업이 실행 중 아직 계산되지 않은 데이터를 쿼리하면, 작업은 로컬에 보관되고 요청된 작업이 시작된다. 요청 작업은 해당 클래스의 보류 집합에 추가되어 배치 처리될 수 있다. 원래 작업은 이들의 부모로 간주된다. 새로 시작한 작업도 보관될 수 있어 보관된 작업의 계층이 생긴다.
작업자 스레드는 로컬 작업이 실행되는 이유를 추적한다. 작업 큐에서 가져왔기 때문에 실행될 수도 있고, 다른 로컬 작업이 쿼리했기 때문에 실행될 수도 있다(이 경우 그 부모 작업의 식별자를 저장한다). 로컬 작업이 완료되면, 그 작업을 기다리는 쿼리(부모가 있다면 부모와, 작업 메타데이터에 추적된 다른 작업)를 차단 해제하여 일부 작업을 재개할 수 있다.
Krabby에는 메모리 내 캐시와 디스크 캐시가 있다. 둘 다 키와 값의 쌍을 저장한다. 키로 값을 조회하고 새 키-값 쌍을 삽입할 수 있다. 두 캐시는 키와 값에 대해 서로 다른 개념을 사용한다. 메모리 내 캐시는 컴파일에 필수이며 작업 메타데이터와 출력 슬롯을 포함한다. 디스크 캐시는 증분 컴파일에만 쓰이며 작업 실행을 더 자세히 기록한다.
메모리 내 캐시는 클래스별 데이터와 클래스 간 데이터를 보유한다. 각 작업 클래스에 대해 작업 슬롯 데이터베이스를 보유한다. 이는 완료된 작업, 진행 중 작업, 큐에 들어간 작업을 포괄한다. 쿼리가 내보내지면 해당 슬롯을 여기서 조회하고, 아직 없으면 추가한다.
디스크 캐시는 이를 확장하여 이전 컴파일 세션의 값을 재사용하게 한다. 조회 비용이 더 크므로, 메모리 내 캐시를 확인한 뒤 특정한, 더 비용이 큰 작업 클래스에만 사용한다. 경우에 따라 데이터는 필요하기 전에 불러올 수 있다. 작업 기록을 저장한다.
작업 기록은 작업을 증분 방식으로 다시 실행할 수 있게 한다. 실행 중 작업은 쿼리를 내보냈다. 작업 기록은 작업의 키와 결과, 그리고 내보낸 쿼리의 키와 결과를 발생 순서대로 저장한다. 그 쿼리들을 다시 호출해 작업을 재생할 수 있다. 모든 결과가 저장된 값과 일치하면, 저장된 결과는 최신 작업 출력과 일치한다. 같은 키에 대해 여러 작업 기록을 캐시할 수 있고, 이들은 같은 초기 쿼리를 공유할 수 있다.
디스크 캐시의 데이터는 정준화된다. 식별자 ID처럼 작업에 관련 없는 데이터는 외부 배열로 옮기고 그 배열의 인덱스로 대체할 수 있다. 이 인덱스들은 작업 기록 전체에서 일관되게 사용되므로 작업 키와 결과 사이에서 대응한다. 외부 배열은 캐시 키에 포함되지 않으므로, 다른 식별자 ID를 가진 쿼리도 같은 캐시 항목을 사용할 수 있다.
큰 값(예: HIR 자료 구조)은 디스크 캐시에 여러 번 나타난다. 그런 큰 값일 수 있는 쿼리의 출력은 의존 작업이 참조하고, 다른 쿼리의 입력으로도 사용될 수 있다. 효율을 위해 이 값들은 인터닝된다. 디스크 캐시 전체에 걸쳐 중복 제거되고 작은 숫자 ID로 식별된다. 이는 증분 컴파일과 관련 있다.
캐시는 축출 정책과 최대 크기로 구성할 수 있다. 이는 target 폴더의 크기를 제한하기 위해 디스크 캐시에서 가장 중요하다. 축출 정책 이론을 살펴보지는 않았지만, 간단한 LRU로 시작해 시간에 따라 구현을 조정할 수 있으리라 생각한다. 메모리 압박 상황에서는 메모리 내 캐시에 최대 크기를 적용하는 것도 유용하다.
일부 작업은 불순하다. I/O를 수행하며 결과는 컴파일마다 달라질 수 있다. 가장 중요한 작업은 디스크에서 Rust 소스 파일을 읽는다. 이 작업들은 쿼리를 내보내지 않으며 쿼리 트리의 잎이다. 증분 컴파일의 시작점이다.
rustc와 salsa는 증분 컴파일에 빨강-초록 알고리즘을 사용한다. 이전 컴파일을 기준으로 작동하며 더 오래된 컴파일의 데이터는 고려하거나 저장하지 않는다. 결과가 이전 컴파일과 같으면 작업은 “초록”, 바뀌었으면 “빨강”으로 간주된다. 디스크 캐시는 이전 컴파일의 작업 기록을 보유한다. 작업은 위에서 아래 또는 아래에서 위로 다시 실행되며, 결국 불순한 잎의 재계산으로 이어진다. 작업 결과가 바뀌지 않았다면 초록으로 표시된다. 작업의 모든 입력(그 작업이 내보낸 쿼리의 결과)이 초록이면 그 작업도 초록으로 표시된다. 작업 입력 중 하나라도 빨강이면 재계산된다. 결과가 바뀌지 않았다면 여전히 초록으로 표시된다.
Krabby는 가능한 곳에서 더 오래된 컴파일의 데이터를 재사용하도록 빨강-초록 알고리즘을 확장한다. 바로 이전 컴파일은 계속 특별히 처리한다. 하지만 작업을 재계산해야 할 때(즉 입력이 빨강일 때), Krabby는 먼저 일치하는 작업 기록이 있는지 디스크 캐시를 확인한다. 캐시 제한을 만족하기 위해 이전 컴파일의 데이터가 없어도 되며, 이 경우 영향받은 작업은 초록으로 표시될 수 없다. 하지만 해당 작업의 데이터는 더 오래된 컴파일에 있을 수 있고, 그 작업의 의존 작업 데이터는 여전히 캐시되어 있을 수 있다.
일부 경우 Krabby는 이 알고리즘에서 벗어나는 휴리스틱을 적용할 수 있다. 자주 쓰이는 작업을 선제적으로 확인하거나 배칭을 지원하기 위해, 일부 작업이 필요하다고 알려지기 전에 다시 실행하도록 선택할 수 있다.
Krabby는 순환을 감지하기 위해 세 알고리즘을 사용한다. 빠르지만 거짓 음성을 보고하는 스레드별 즉시 알고리즘, 드물게 실행되지만 거짓 양성을 보고하는 스레드 간 지연 알고리즘, 특정 작업의 순환을 확인할 수 있는 느린 알고리즘이다. 즉시 알고리즘은 순환 감지를 위한 전통적인 알고리즘이다(현재 스레드의 쿼리 스택을 확인한다). 지연 알고리즘은 교착 상태 감지기와 유사하며 흥미로운 도달 가능성 개념에 의존한다. 느린 알고리즘은 특정 작업 주변의 의존성 그래프를 순회해 순환을 모호함 없이 식별한다.
작업이 계산 중인 데이터에 대한 쿼리를 내보내면, 쿼리와 작업은 차단된다. 대상 작업은 동시성 때문에 다른 스레드에서 실행 중일 수 있고, 배칭 때문에 같은 스레드에서 실행 중일 수 있으며, 또는 순환이 형성 중일 수 있다. 마지막 경우 대상 작업도 해당 쿼리에 차단되어 교착 상태를 형성한다. 순환에 관련된 작업은 영원히 차단된다.
차단된 작업은 하나 이상의 쿼리에 차단되어 있다. Krabby는 작업을 진전시킬 수 있는지를 측정한다. 작업은 1) 실행 중이거나, 2) 차단되었지만 이제 재개할 준비가 되었거나, 3) 지금 차단되어 있지만 의존성 중 하나를 진전시킬 수 있다면 진전시킬 수 있다. 이는 의도적으로 약한 정의다. 교착 상태에 걸린 일부 작업이 이 방식으로 잘못 분류될 수 있다.
작업이 두 쿼리에 차단되었다고 하자. 하나는 순환/교착 상태를 만들고, 다른 하나는 실행 중이다. 위 정의에 따르면 Krabby는 이 작업을 진전시킬 수 있다고 가정한다. 하지만 두 번째 의존성이 실행을 마치면 작업은 순환을 일으키는 쿼리에만 차단된다. Krabby는 더는 진전시킬 수 없음을 인식한다. 교착 상태 작업이 잘못 분류되더라도 일시적으로만 그럴 것이다.
따라서 Krabby는 각 작업자 스레드의 로컬 재개 준비 작업으로부터 확실히 진전시킬 수 있는 모든 작업을 주기적으로 수집한다. 그 작업들에 의존하는 차단 작업을 조회하고, 재귀적으로 진전 가능 표시를 한다. 표시되지 않는 차단 작업은 순환의 일부다. 하지만… 작업자 스레드에서 수집하는 동안 테어링과 유사한 경쟁 조건 때문에 일부 작업이 잘못 분류될 수 있다.
마지막 단계는 교착 상태일 가능성이 높은 작업을 선택하고, 의존성을 재귀적으로 탐색하여 확인하는 것이다. 순환이 식별되면 작업의 차단을 해제하고, 재개될 때 작업에 순환을 보고한다.
몇 가지 최적화가 있다. 사용자가 순환이 발생할 수 없다고 믿는 특정 작업 클래스에서는 순환 감지를 건너뛴다. 지연 알고리즘은 충분히 오래된 차단 작업만 고려한다(예: 500마이크로초 넘게 차단된 경우). 앞으로 이를 조정할 더 많은 방법을 찾게 되리라 기대한다.
이 아이디어들은 7개월 넘게 내 머릿속을 맴돌았고, 여전히 머리가 조금 아프다. 그래도 구현할 때가 무르익었다고 생각한다! Barcelona에서 열리는 EuroRust 2026에서 내 쿼리 시스템을 발표할 예정이며, 그때 salsa를 사용한 것과 krabby-query를 사용한 것, 두 가지 쿼리 기반 Cargo 구현을 선보일 것이다. 현재 salsa 구현을 작업하면서 필요한 구체적 쿼리를 잘 파악하고 있고, 곧 krabby-query 구현을 시작할 예정이다. 정말 기대된다!!!
무언가가 불명확하게 느껴지거나, 어떤 것의 세부 사항을 더 듣고 싶거나, 그저 Krabby 개발 소식을 계속 따라가고 싶다면 우리 Zulip에 참여하라!