Jane Street Incremental: 증분 계산을 위한 라이브러리

Incremental은 계산 그래프의 의존성을 추적하여 재계산을 최소화합니다

Jane Street의 Incremental은 소스 데이터가 변경될 때 계산 그래프를 부분적으로 하이드레이션(hydrating)하는 문제를 해결하기 위해 설계된 라이브러리입니다. 입력값이 변경될 때 전체 계산 파이프라인을 다시 실행하는 대신, Incremental은 계산 간의 의존성을 추적하고 변경 사항의 영향을 받는 특정 노드만 업데이트합니다. 이 접근 방식은 계산 오버헤드를 이론적 최소치로 줄여주어, 복잡하고 상호 의존적인 데이터 변환에 매우 효율적입니다.

핵심 개념 및 구현

Incremental은 데이터 입력과 출력 사이의 관계를 방향성 비순환 그래프(DAG)로 취급하여 계산을 위한 빌드 시스템처럼 작동합니다.

의존성 추적 및 전파

• 자동 그래프 구축: 라이브러리는 실행 중에 의존성을 조사하여 계산 그래프를 자동으로 구축합니다.
• 변경 사항 전파: 소스 값이 업데이트되면 라이브러리는 해당 변경 사항을 그래프를 통해 전파합니다. 이 패턴의 일부 구현체는 평가 순서를 결정하고 중복 업데이트를 방지하기 위해 높이 기반 알고리즘을 사용합니다.
• 배칭(Batching): stabilize 명령을 사용하면 개발자가 여러 변경 사항을 하나로 묶을 수 있으며, 이를 통해 일련의 업데이트가 완료된 후 계산 그래프가 단 한 번만 재평가되도록 보장합니다.

Observable 패턴과의 비교

입력이 리스너에게 값을 게시하는 Observable 패턴과 유사하지만, Incremental은 변경 감지 최적화와 노드가 재계산되는 횟수를 최소화하는 데 집중합니다. 입력값이 변경되었음에도 계산된 값이 변경되지 않은 경우 전파를 중단함으로써 단순한 푸시 기반 시스템의 함정을 피합니다.

산업 분야 적용 및 생태계

증분 계산은 금융 모델링부터 현대적인 사용자 인터페이스에 이르기까지 다양한 분야에서 사용되는 기초적인 패턴입니다.

금융 워크로드 및 고성능 컴퓨팅

증분 계산은 금융 분야에서 오랜 역사를 가지고 있습니다. 예를 들어, Goldman Sachs와 같은 기업의 상품 가격 결정 시스템은 수십 년 전부터 값비싼 미분 계산을 최소화하기 위해 유사한 그래프 기반 접근 방식을 활용해 왔습니다. 현대적인 반복 버전으로는 Differential Dataflow, Timely Dataflow, 그리고 (Feldera에서 사용하는) DBSP와 같은 시스템이 있으며, 이들은 대규모 금융 데이터 워크로드에 최적화되어 있습니다.

UI 프레임워크 및 "Signals"

JavaScript 생태계에서 이 패턴은 현재 "Signals"로 대중화되어 있습니다. Vue, SolidJS, Svelte, Ember, and Angular와 같은 프레임워크는 세밀한 반응성을 달성하기 위해 시그널을 사용합니다.

• SolidJS는 특히 Incremental에서 사용되는 것과 유사한 높이 기반 DAG 평가 알고리즘을을 사용합니다.
• Jane Street에서 개발한 UI 라이브러리인 Bonsai는 Incremental을 기반으로 직접 구축되었습니다. 이는 VDOM을 그 자체로 증분적으로 만들어 트리 구축에 소요되는 시간을 줄임으로써 (React가 사용하는) Virtual DOM 접근 방식을 개선합니다.

컴파일러 및 빌드 시스템

증분 계산은 현대적인 빌드 시스템과 컴파일러의 핵심입니다. 예를 들어, Salsa는 rust-analyzer에서 사용되는 증분 계산 프레임워크로, IDE가 변경된 코드 부분만 재분석하도록 보장합니다.

기술적 트레이드오프 및 고려 사항

언어 선택: OCaml

Incremental은 OCaml로 작성되어, 복잡한 의존성 그래프에서 정확성을 보장하는 강력한 타입 시스템 보증을 제공합니다. 일부에서는 C++와 비교하여 OCaml의 성능을 질문하기도 하지만, 다른 이들은 OCaml의 속도가 Java와 비슷하거나 인터프리터 언어보다 훨씬 빨라 고성능 계산 그래프에 적합하다고 언급합니다.

동적 vs. 정적 그래프

증분 계산 시스템의 과제제는 동적성(dynamism)을 처리하는 것입니다. 즉, 런타임에 노드가 추가되거나 제거되는 경우(예: UI 윈도우가 나타나거나 사라지는 경우)를 말합니다. 고정 크기 그래프(예: 스프레드시트)는 간단하지만, 동적 그래프는 캐싱 문제나 확장성 병목 현상을 피하기 위해 더 정밀한 메모리 관리와 추적이 필요합니다.

대안적 접근 방식

일부 개발자들은 대안으로 **Merkle Trees (hash trees)**를 제안합니다. 계산 노드에 의존성 해시와 솔트(salt)를 태깅함으로써, 시스템은 해시를 비교하는 것만으로 결과가 재계산될 필요가 있는지 식별할 수 있으며, 이때 ID를 사용하여 캐시에서 결과를 인덱싱합니다.