Incremental - 증분 계산을 위한 라이브러리

 (github.com/janestreet)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Incremental은 입력이 바뀔 때 복잡한 계산을 효율적으로 갱신할 수 있도록 지원하는 라이브러리임
  • Umut Acar 등의 자기 조정 계산(self-adjusting computation) 연구에서 영감을 받음
  • 스프레드시트와 같은 대규모 계산이 데이터 변경에 효율적으로 반응하도록 구성할 수 있음
  • GUI 애플리케이션의 뷰에 새로운 데이터를 효율적으로 반영할 수 있음
  • 필터링이나 매핑의 역변환처럼 파생 데이터가 원본 데이터와 계속 동기화되도록 보장할 수 있음

활용 분야

  • 변경되는 입력에 대응해 복잡한 계산을 효율적으로 갱신함
  • 스프레드시트 형태의 대규모 계산이 데이터 변화에 반응하도록 구성할 수 있음
  • GUI 뷰에 새로운 데이터를 효율적으로 통합할 수 있음
  • 원본에서 계산된 파생 데이터를 지속적으로 동기화함
    • 데이터 필터링
    • 매핑의 역변환

설계 배경과 문서

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이런 반응형 프로그래밍은 요즘 JavaScript UI 프레임워크에서 시그널(signals) 이라는 이름으로 널리 쓰이며, 표준화 제안도 진행 중임
    Vue, SolidJS, Svelte, Ember, Angular가 사용하고 React에는 MobX와 Jotai 같은 구현이 있음. 변경 전파와 방향성 비순환 그래프(DAG) 평가 알고리즘도 여러 가지이며, SolidJS 2는 Incremental과 비슷한 높이 기반 알고리즘을 사용하는 것으로 알고 있음
    나는 노드를 Int32Array 아레나에 할당하고 연결 리스트로 이어서 의존성 간선 수에 비례하는 GC 부하를 피하는 구현을 실험 중임
    Rust에도 여러 구현이 있으며 UI 프레임워크로는 Leptos, rust-analyzer가 사용하는 범용 증분 계산 시스템으로는 Salsa가 있음. 이를 의존성을 자동 추적하는 빌드 시스템으로 볼 수도 있는데, tup은 빌드 작업을 계측해 어떤 파일을 읽는지 감지하고 의존 관계를 설정함. 작성자의 글과 고전인 Build Systems à la Carte도 읽어볼 만함

    • 빠르게 비워낼 수 있는 가벼운 의존성 그래프를 만들 수 있음. 시그널이 어떻게 바뀌었는지까지 기술할 필요 없이 바뀌었을 가능성만 표시하고, 변경 시 의존 대상을 비운 뒤 새 데이터를 요청할 때 다시 등록하면 됨. 이 과정에서 더는 관심 없는 변경을 일부 구독자가 통지받을 수는 있음
      다만 증분 계산과 함수형 반응형 프로그래밍(FRP) 은 실제로 서로 다른 영역임. 증분 계산은 델타에 작동하는 함수를 명시적으로 유도하지만, FRP는 손상된 부분을 찾아 복구하는 방식만 사용할 수도 있음
    • 또 다른 주요 예로 JetBrains Noria가 있음. Noria의 핵심은 UI 프레임워크가 아니라 증분 계산 플랫폼이지만, 현재는 JetBrains Air IDE의 GUI 렌더링 최적화에 활용됨
    • 복잡한 객체의 갱신 처리에는 상당한 차이가 있어 보이며, 스케줄링도 다를 가능성이 큼

  • Incremental 라이브러리는 원본 데이터가 바뀔 때 계산 그래프를 부분적으로 재구체화하는 문제를 해결하려는 것으로 보임. 잘 설계된 빌드 시스템과 비슷하며 함수형 프로그래밍에서도 흔히 쓰이는 유용한 접근임
    증분 계산 분야에는 Differential Dataflow, 인접 기술인 Timely Dataflow, DBSP도 있음. Feldera는 DBSP 기반이고 Materialize는 Differential Dataflow 관계자들이 이끌고 있음
    나는 금융 데이터와 워크로드에 특화된 별도 접근법인 modolap을 개발하고 있음. 해결해야 할 크고 중요한 문제가 많음. 관련해서 Signals and Threads의 빌드 시스템 에피소드도 참고할 만함

    • modolap의 주요 버튼을 누르자 아무 설명 없이 2,000달러 Stripe 결제로 이동하는 건 꽤 대담함
    • openivm은 광범위한 집계 연산을 증분 연산으로 구현한 SQL-to-SQL 컴파일러이며, 구체화된 뷰를 자동 유지하는 DuckDB 확장도 제공함

  • Goldman도 약 30년 전 금융상품 가격 산정에 같은 접근법을 사용했음. 그곳에서 약 13년 근무하는 동안 Node Purpling에 관한 긴 논의를 기억함
    컴퓨터과학은 발전했고 내가 보기에는 이것이 그래프 접근법은 아니지만, 미분 같은 계산은 비용이 크므로 실행 횟수를 이론적 최솟값에 최대한 가깝게 줄여야 함. 관련 HN 토론도 있음

    • 이로 인해 비공식적으로 bank python이라 불리는 환경이 생겼으며, 이 글이 잘 다룸
      전용 사내 IDE를 보는 순간 화가 나 퇴사하지 않는다고 해도 신입이 적응하는 데 유난히 오래 걸리고, 몇 달이 지나도 근본적으로 다른 요소를 계속 배워야 한다는 대목이 문제를 가장 잘 묘사함. 나도 작업 내용을 완전히 이해하는 데 약 2년 반이 걸렸음
      다시 교육해야 한다는 사실을 깨닫기 전까지 현대적인 교육도 거의 없었음. 가장 나쁜 점은 UI를 만들기 위한 코딩이었고, 신규 프로젝트에는 사용 승인이 나지 않았음

  • 가장 좋아하는 기술 발표 중 하나는 Seven Implementations of Incremental임: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

  • 몇 년 전 데이터플로 프로그래밍에 큰 관심이 있었고, 많은 이가 여러 방향에서 이 문제에 접근했던 것 같음. 이 라이브러리를 보자 곧바로 Clojure의 Javelin이 떠올랐음

  • 흥미롭다면 Incremental 위에 구축된 UI 라이브러리 Bonsai도 볼 만함
    React 같은 라이브러리는 가상 DOM으로 불필요한 작업을 효율적으로 건너뛰지만, 가상 DOM 자체를 만드는 데도 시간이 듦. Bonsai는 가상 DOM까지 증분화하며 작업하기도 재미있음
    나는 지금은 유지보수되지 않는 Revery를 대상으로 데스크톱 UI 라이브러리를 만들었지만, 상당히 오래된 Bonsai 버전을 사용함

  • 이것이 입력에 새 값을 발행하고 계산을 거쳐 새 결과를 구독자에게 전달하는 옵저버블 패턴과 어떻게 다른지 완전히 이해하지 못했음
    변경 감지와 값이 그대로일 때 전파를 중단하는 최적화가 있겠지만 옵저버블도 가능함. stabilize로 재계산 전에 변경을 일괄 처리하는 부분도 흥미롭지만 역시 옵저버블로 구현 가능함
    핵심 차이가 내부 조사로 계산 그래프를 자동 구성하는 데 있는지, 더 근본적인 요소가 있는지 궁금함

    • 옵저버블 패턴을 어떻게 정의하느냐에 따라 달라짐. 여기서 근본적인 요소는 지연 평가와 그래프 노드 사이의 약한 연결임. 노드 값은 관찰할 때만 구체화되며 실행 중 그래프 구조 변경도 유연하게 처리함
      일부 노드만 관찰할 때 전체 그래프를 구체화할 필요가 없음. 계산을 언제든 중단해 그래프를 부분적으로만 갱신된 상태로 남겨두고 입력을 추가 변경한 뒤, 관심 있는 노드의 구체화를 계속할 수도 있으며 알고리즘이 모든 변경을 정리해 줌
      증분 계산은 본질적으로 이런 특성을 포괄하는 용어이며, 같은 시스템을 관찰자와 구독자 모델로 구성할 수도 있음. 고전적인 Excel 스프레드시트가 좋은 예이며, Salsa 알고리즘 설명도 참고할 만함
    • 대략 옵저버블은 대상을 구독하고 값을 듣는 방식이고, Incremental은 계산과 상태의 DAG 전반에 걸친 캐시에 가까움. 필요한 부분만 다시 계산해 최적화할 수 있음
      Ron Minsky의 발표가 매우 좋음
    • 이 글이 증분·스트리밍 시스템의 지형을 파악하는 데 도움 됨
    • 나도 비슷하게 생각했음. 처음 보면 의존성 추적을 갖춘 반응형 프로그래밍과 매우 가까워 보임. 진짜 장점이 API 사용성인지, 일반적인 옵저버블 구현으로는 현실적으로 어려운 내부 최적화인지 궁금함
    • 근본적으로 그래프가 맞지만, 거대하고 동적으로 변하는 그래프에서 변경을 정확하고 효율적으로 계산하는 방식임
      수백 개의 중간 노드로 갈라졌다가 길이가 서로 다른 경로를 거쳐 다시 합쳐지는 다이아몬드형 하위 그래프를 생각해 볼 수 있음. 일부 경로에 min(A, B)가 있고 최댓값 쪽만 바뀌는 경우도 있음
      단순한 옵저버 방식은 계산량이 잠재적으로 지수적으로 폭증하고 동시성 문제도 일으킬 가능성이 큼. 이 라이브러리는 그래프 구조를 동적으로 변경해도 최적에 가까우면서 정확함. 옵저버 등으로도 같은 결과를 낼 수 있지만, 성능 절벽을 피하면서 올바르게 구현하기가 훨씬 어려움

  • Jane Street 프로젝트의 장점은 연구나 틈새 시스템에 있던 발상을 개발자가 실제로 쓸 수 있는 형태로 포장한다는 데 있음. 라이브러리를 도입하지 않더라도 설계 문서는 대체로 읽을 가치가 큼

  • Electric Clojure는 클라이언트·서버 경계를 넘는 증분 렌더링을 제공함. 가장 비슷한 것은 SolidJS라고 보지만, SolidJS는 프런트엔드에만 해당함

  • 예전에 비슷한 것을 만들면서 선례를 거의 찾지 못했음. 사용 목적이 사라져 프로젝트를 종료했지만 다시 살펴보고 싶으며, npm에 data-rambler라는 이름으로 남아 있음
    구상은 JavaScript 런타임에 적재할 수 있는 도메인 특화 언어(DSL) 에 데이터 스트림을 공급하는 방식이었음. 모듈이 데이터를 여러 출력 스트림으로 변환하고, 이를 별도 보고서 라이브러리에 전달해 템플릿 기반 동적 보고서를 생성함
    첫 버전부터 상당히 강력했지만, 복잡성을 줄이기 위해 JavaScript다운 문법으로 개선할 큰 계획도 있었음

답변달기