노드 900개짜리 그래프 그리기 — 안 죽고, 안 멈추고, 알아볼 수 있게

들어가며

리니지 그래프의 그룹 라벨을 손보는 리팩토링을 했다. 파이프라인 그룹의 정체성을 더 정확하게 나누는 작업이라, 화면에 보이는 그룹(클러스터) 수가 늘었다. 그것뿐이었다. 레이아웃 쪽은 건드리지도 않았다.

배포하고 며칠 뒤부터 제보가 들어왔다.

"그래프가 안 떠요. 근데 새로고침하면 떠요."

1. 레이아웃 라이브러리가 가끔 죽는다, 근데 고칠 수가 없다

스택 트레이스를 따라가 보니 dagre 내부였다. 처음엔 당연히 "업스트림 이슈 파서 고치면 되겠네" 생각했다. 근데 dagre 레포를 열어보고 생각이 바뀌었다. 사실상 유지보수가 멈춘 프로젝트였다.

문제를 정리하면 세 개다.

재현이 안 된다. 같은 입력인데 죽을 때도 있고 안 죽을 때도 있다.
원인이 라이브러리 내부다. compound 그래프(노드를 클러스터로 묶는 모드)에서만 터진다.
고칠 수가 없다. 이슈를 올려도 머지될 곳이 없다.

dagre는 어디서 죽는가

대책을 세우려면 최소한 어느 단계에서 죽는지는 알아야 한다. dagre는 계층형 그래프 레이아웃의 표준인 Sugiyama 방식을 따른다. 크게 세 단계다.

1. rank     — 각 노드를 몇 번째 층(rank)에 둘지 배정   ← ranker 알고리즘 선택 가능
2. order    — 같은 층 안에서 노드 순서를 정해 엣지 교차 최소화
3. position — 실제 x/y 좌표 부여

스택 트레이스가 가리키는 곳은 2단계, order였다. order는 층별로 노드를 정렬하며 교차를 줄이는 반복 휴리스틱인데, compound 모드에서는 여기가 더 복잡해진다. 클러스터의 멤버들이 정렬 중에 흩어지면 안 되니까, dagre는 클러스터 경계를 가상의 border 노드로 삽입해서 멤버들을 그 사이에 가둔 채 정렬한다. 우리가 그래프를 빌드할 때 넣는 이 코드가 그 경계 처리를 트리거한다.

// dagre-layout.worker.ts — buildGraph
const useCompound = !noCompound && input.groups.length > 0
const g = new dagre.graphlib.Graph({ compound: useCompound })

if (useCompound) {
  for (const groupId of input.groups) {
    g.setNode(groupId, { borderType: 'borderRight' })
  }
}
for (const node of input.nodes) {
  g.setNode(node.id, { width: node.width, height: node.height })
  if (node.group && useCompound) {
    g.setParent(node.id, node.group) // 클러스터 멤버십 — order의 경계 처리 대상
  }
}

크래시는 이 border 노드 처리 어딘가에서 나온다. "어딘가"라고 쓴 건 정확한 위치를 끝까지 특정하지 않았기 때문이다. 왜 안 했는지가 다음이다.

원인을 파는 대신, 분포를 쟀다

라이브러리 내부의 확률적 버그를 만났을 때 정석은 디버거로 내부를 파는 거다. 근데 그 끝에 기다리는 게 "머지될 수 없는 패치"라면, 원인 규명은 헛수고가 된다.

그래서 방향을 바꿨다. 왜 죽는지 대신, 언제 얼마나 죽는지를 쟀다. 대형 그래프 mock을 만들어서 클러스터 수와 ranker를 바꿔가며 크래시율을 실측했다.

조건 크래시율 (실측) 클러스터 4개 이하 0% 클러스터 12개 ≈60% 클러스터 존재 + longest-path ranker ≈96% 클러스터 없음 (비-compound) 0%

이 표에서 설계에 필요한 사실이 전부 나온다.

크래시율은 클러스터 수에 비례한다. 그룹 라벨 리팩토링에서 문제가 드러난 이유다 — 버그는 원래 거기 있었고, 우리는 그룹 수를 늘리면서 크래시 확률이 높은 구간으로 더 깊이 들어갔을 뿐이다.
ranker에 따라 극적으로 다르다. rank 배정 결과가 다르면 order가 처리할 층 구성이 달라지니, 1단계의 선택이 2단계의 크래시 확률을 바꾼다.
클러스터가 없으면 안 죽는다. border 노드 처리 자체가 없어지니까. 여기가 최종 방어선의 근거다.

ranker 세 종류를 짚고 가면 —

ranker 방식 특성

tight-tree feasible: spanning tree 기반으로 rank를 조밀하게 당김 빠르고 품질 준수. 우리 기본값 (이 선택의 유래는 뒤에서)
network-simplex: 엣지 길이 가중합 최소화를 심플렉스 피벗으로 최적화 품질 최상, 최악 O(N³)
longest-path: 최장 경로 깊이로 단순 배정, 선형 빠르지만 rank가 길게 퍼짐. 클러스터와 만나면 크래시율 ~96%

폴백을 쌓으면 되는 거 아닌가?

맞다. 처음 설계도 그랬다. 기본 ranker로 실패하면 다른 ranker로, 그것도 실패하면 또 다른 ranker로. 폴백은 많을수록 안전하니까.

근데 표를 다시 보자. longest-path는 클러스터 존재 시 크래시율 ≈96%다. 폴백 체인에 longest-path를 넣어두는 건 안전망처럼 보이지만, 첫 단이 죽은 상황 — 클러스터가 많은 상황 — 에서 거의 반드시 같이 죽는 단을 하나 더 끼워 넣는 짓이다.

폴백의 가치는 앞 단과 같은 이유로 죽지 않는다는 보장에서 나온다. 개수는 그다음이다. 앞 단이 죽은 조건에서 뒷 단도 죽는다면 그건 폴백이 아니라 지연이다. 크래시 조건이 "클러스터 수"라는 걸 실측으로 알았으니, 폴백은 클러스터라는 조건 자체를 제거하는 방향이어야 했다. ranker만 갈아 끼우는 걸로는 부족하다.

그래서 longest-path를 체인에서 뺐다.

최후 폴백은 실패할 수 없어야 한다

남은 설계는 이렇다. 각 단은 앞 단보다 뭔가를 포기하고, 그 대가로 실패 조건을 줄인다. 그리고 마지막 단은 실패라는 개념 자체가 없어야 한다.

// dagre-layout.worker.ts
function runLayout(input: LayoutWorkerInput): LayoutWorkerOutput {
  // 최종 폴백은 비-compound — compound 클러스터 수에 비례해 dagre order 단계가 확률적으로
  // 크래시하며(그룹 4개 이하 0%→12개 60% 실측), 클러스터 bounds는 소비부가 멤버 노드로
  // 재계산하므로 compound를 꺼도 그룹 프레임은 유지된다. longest-path는 클러스터 존재 시
  // 실패율(~96%)이 가장 높아 체인에서 제외.
  // dagre 는 layout 시 그래프를 변형하므로 시도마다 새로 빌드한다.
  let g: dagre.graphlib.Graph
  try {
    g = buildGraph(input) // 1단: tight-tree + compound
    dagre.layout(g)
  } catch {
    try {
      g = buildGraph(input, 'network-simplex') // 2단: ranker 교체 + compound
      dagre.layout(g)
    } catch {
      g = buildGraph(input, undefined, true) // 3단: compound 자체를 끈다 → 실측 0%
      dagre.layout(g)
    }
  }
  // ...
}

마지막 줄 주석 하나도 실전 교훈이다. dagre는 layout() 호출 중에 입력 그래프를 변형(mutate)한다. 실패한 그래프 객체를 재사용해 다른 ranker로 재시도하면 이미 반쯤 오염된 상태에서 시작하는 거라, 시도마다 그래프를 새로 빌드해야 한다.

그리고 워커 밖에 한 단이 더 있다. 워커 자체가 죽는 경우(스크립트 로드 실패 같은)를 위한 메인 스레드 최후 방어선 — 비-compound 재시도, 그마저 실패하면 격자 배치다.

// layout.ts — 메인 스레드 최후 방어선
export const layoutAssetGraphFast = (graphData, opts) => {
  try {
    return layoutAssetGraphImpl(graphData, opts, undefined, true) // 비-compound → 실측 0%
  } catch {
    return gridLayoutFallback(graphData)
  }
}

/** dagre 자체가 실패한 그래프의 최후 배치 — 정사각형에 가까운 격자로 나열한다. */
const gridLayoutFallback = (graphData: GraphData): AssetGraphLayout => {
  const ids = Object.keys(graphData.nodes)
  const cols = Math.max(1, Math.ceil(Math.sqrt(ids.length)))
  // i % cols, floor(i / cols) 로 셀 좌표 부여 — 이게 전부다
  // ...
}

격자 배치는 노드를 √N 열로 줄 세우는 산수다. 조건문과 나머지 연산만 있고 그래프 이론이 없다. 알고리즘이 없는 곳에는 알고리즘의 버그도 없다.

예쁘지 않다. 근데 리니지 그래프에서 사용자에게 필요한 최소한은 노드가 화면에 존재하는 거다. 예쁜 배치는 그다음 문제고. 검색하고, 클릭하고, 의존을 따라갈 수만 있으면 최악의 순간은 넘긴다.

클러스터를 껐는데 그룹 테두리는 어떻게 남나?

여기서 잠깐. 3단에서 compound를 꺼버리면 그룹 프레임이 사라져야 정상 아닌가?

하지만 우리 렌더러는 그룹 테두리를 dagre가 계산한 클러스터 bounds로 그리지 않는다. 멤버 노드들의 배치 좌표에서 min/max를 취해 소비부가 재계산한다. dagre 입장에서 클러스터가 없어져도, 노드들이 배치되기만 하면 그룹 프레임은 그대로 그려진다. 강등해도 사용자 눈에 보이는 손실은 "클러스터를 고려한 배치 품질"뿐이고, 그룹이라는 정보 자체는 살아남는다.

폴백 설계의 강등 비용을 결정하는 건 결국 렌더링이 레이아웃 결과에 얼마나 결합돼 있는지다. 그룹 테두리가 dagre의 클러스터 출력에 직접 결합돼 있었다면 3단은 "그룹이 사라지는 단"이 됐을 거고, 이 폴백 구조는 못 만들었을 거다.

실패도 응답이어야 한다

폴백 체인을 만들고 나니 남는 문제가 하나 더 있었다. 워커 안에서 uncaught 예외가 새면 메인 스레드는 영원히 응답을 기다린다. 죽었다는 사실조차 전달이 안 되는 거다.

// dagre-layout.worker.ts
self.onmessage = (e: MessageEvent<LayoutWorkerInput>) => {
  try {
    self.postMessage(runLayout(e.data))
  } catch (err) {
    // 최종 폴백까지 실패해도 uncaught로 새지 않게 명시적 error 메시지로 응답 —
    // 메인 스레드가 fast 경로(비-compound→격자)로 폴백한다.
    self.postMessage({ type: 'error', id: e.data.id, message: String(err) })
  }
}

실패를 예외로 흘리지 않고 { type: 'error' } 응답 타입으로 만들었다. 단과 단 사이를 잇는 건 결국 "앞 단이 죽었다는 사실이 뒷 단에 전달되는 경로"다. 이게 끊기면 다음 단은 영영 호출되지 않는다.

덤으로 하나 더. 수정 후에도 옛 크래시 배치가 화면에 살아남는 제보가 있었다. 레이아웃 결과는 그래프 구조를 해시한 키로 캐시하는데, 이 키에 그룹 배정이 안 들어 있어서 그룹 규칙이 바뀌어도 옛 배치가 히트되고 있었다. 노드 id에 그룹명을 붙여 해시하고, 레이아웃 로직이 바뀔 때마다 LAYOUT_VERSION을 올려 전체 무효화하는 걸로 해소했다. 폴백을 고치고도 캐시가 옛 결과를 돌려주면 아무것도 고쳐지지 않는다..

업스트림에 PR 내는 게 정석 아닌가?

당연히 검토했다. 기각한 선택지 두 개를 남겨둔다.

dagre 포크 수정: order 단계의 확률적 버그를 우리가 고쳐서 포크를 유지하는 방안. 문제의 코드는 교차 최소화 휴리스틱과 compound 경계 처리가 얽힌 지점이라, 고친다는 건 그 코어를 이해하고 계속 책임진다는 뜻이다. 그 비용이 폴백 체인의 비용(가끔 배치 품질 강등)보다 확실히 컸다. 업스트림이 살아 있었다면 계산이 달랐을 거다.
라이브러리 교체(ELK 등): 더 활발한 레이아웃 엔진으로 갈아타는 방안. 크래시 하나 때문에 배치 스타일, 성능 프로파일, 번들 크기를 전부 다시 검증하는 건 이 시점의 문제 크기에 비해 과했다.(근데 바꿨는데도 문제는 똑같긴했다 ㅠㅜ)

결국 감수한 트레이드오프는 이거다. 클러스터가 많은 그래프에서 가끔, 클러스터를 고려하지 않은 배치가 나온다. 대신 그래프가 안 뜨는 일은 없다.

이제 그래프는 안 죽는다. 근데 그래서 자신 있게 전체 리니지를 열었더니 —

2. 브라우저가 죽은 게 아니라 멈췄다

자산 900개쯤 되는 전체 리니지 그래프다.

"어? 브라우저가 멈췄는데?"

죽은 게 아니다. 멈췄다. 이 둘은 종류가 다르다. 크래시는 그래도 에러를 남긴다 — 에러 바운더리가 받고, 사용자는 새로고침이라도 한다. 멈춤은 아무것도 남기지 않는다. 클릭도, 스크롤도, 탭 닫기 버튼도 한동안 안 먹는다. 자바스크립트 이벤트 루프가 한 태스크에 잡혀 있는 동안 브라우저는 입력 처리도 페인트도 못 하니까, 탭이 통째로 잡혀 있는 거다..

계측을 붙여서 경로를 확정했다. 범인은 방금 만든 그 폴백 체인이었다. 1단 tight-tree가 확률적으로 크래시하면 2단이 network-simplex로 재시도하는데 — 이 체인이 통째로 메인 스레드에서 돌고 있었다. network-simplex는 rank 배정을 "엣지 길이(랭크 차)의 가중합 최소화" 문제로 놓고 스패닝 트리를 피벗해가며 최적해를 찾는 알고리즘이다. 품질은 최상인데 최악 O(N³)다. 노드 900개에서 이게 터지면 메인 스레드는 초 단위로 잡힌다.

크래시를 막으려고 1장에서 만든 체인이, 크래시가 잦은 대형 그래프에서 하필 가장 비싼 알고리즘을 UI 스레드에 태우고 있었다.

근데 이 병목, 우리가 처음 만난 게 아니다.

우리보다 먼저 이 문제를 만난 팀이 있다

Dagster 팀이 2023년에 쓴 글(Scale DAG Visuals for 10K+ Assets)이 있다. 자산 2,000개 이상 그래프에서 dagre 레이아웃이 수 분씩 걸려 사실상 못 쓰는 상태였다고 한다. 그래서 이들이 뭘 했냐면 — dagre를 Rust로 포팅해서 WASM으로 컴파일했다. 레이아웃이 느리니까 더 빠른 언어로. 자연스러운 발상이다.

결과는, 여전히 느렸다.

그제서야 진짜 병목이 보였다고 한다. 기본 ranker인 network-simplex가 최악 O(N³)이었던 거다. 상수 배 빨라지는 언어 이식으로는 차수가 다른 복잡도를 못 이긴다. Rust 포트는 접고, ranker를 tight-tree로 바꿨더니 시각적으로 거의 같은 그래프가 나오면서 2,000개 기준 수 분 → 약 5초가 됐다고 한다.

근데 그 결론(tight-tree)을 쓰고 있는 우리는 멈췄다. 왜? tight-tree가 크래시하면 폴백이 network-simplex고, 그게 메인 스레드였으니까. Dagster의 교훈은 해피 패스(happy path)를 빠르게 만들어줬지만, 우리의 멈춤은 실패 경로에서 왔다. 그래서 문제를 한 번 더 밀어서 다시 정의했다. '레이아웃이 느리다'에서, '느려도 되는 계산이 멈추면 안 되는 스레드에서 돈다'로. 이렇게 정의하면 해법은 알고리즘 교체가 아니고 계산이 도는 자리를 옮기는 거다.

워커로 보낸다, 전부는 아니고

첫 번째 결정. 레이아웃 계산을 Web Worker로 오프로드한다. 워커 스레드에서는 O(N³)든 뭐든 마음껏 돌아도 된다 — 워커가 몇 초를 계산하든 메인 스레드는 이벤트 루프가 살아 있어서 로딩 상태를 그리고 입력을 받는다.

근데 전부 워커로 보내지는 않는다.

// async-graph-layout.ts
const WORKER_THRESHOLD = 50

if (nodeCount >= WORKER_THRESHOLD && typeof Worker !== 'undefined') {
  try {
    result = await layoutViaWorker(connected, direction)
  } catch {
    result = layoutAssetGraphFast(connected, { direction }) // 1장의 그 최후 방어선
  }
} else {
  result = syncFallback(connected, { direction })
}

워커는 공짜가 아니다. postMessage는 structured clone으로 입력 전체를 복사하고(그래서 워커 입력을 노드 id·크기·엣지만 담은 평탄한 객체로 따로 빌드한다), 결과가 비동기로 오니 로딩 상태도 한 프레임 생긴다. 노드 50개짜리 그래프는 메인 스레드에서 밀리초 단위로 끝나는데 굳이 직렬화 왕복을 태울 이유가 없다. 50은 이 왕복 비용과 계산 비용이 교차하는 지점의 경험적 경계다.

워커 프로토콜에서 챙긴 디테일 두 개.

요청 상관관계(correlation): 워커 응답은 e.data.id === input.id로 매칭한다. 이 id가 그냥 일련번호가 아니라 그래프 구조의 해시라서, 뒤늦게 도착한 이전 그래프의 응답이 현재 그래프에 잘못 적용되는 경합을 구조적으로 막는다.
기동 지연 숨기기: explorer 마운트 시점에 preloadLayoutWorker()로 워커를 미리 띄운다. 첫 대형 레이아웃 요청 때 워커 스크립트 다운로드·기동을 기다리지 않는다.

하나 더 있다. dagre에 넣기 전에 고아 노드(엣지가 하나도 없는 노드)를 미리 분리해서 본체 배치에서 제외하고, 배치가 끝난 뒤 별도 스택으로 붙인다. 계층형 레이아웃은 엣지 관계로 층을 만드는 알고리즘이라 고아 노드는 어차피 의미 있는 위치가 없는데, N에는 똑같이 기여한다. 입력에서 빼는 게 맞다.

메인 스레드에서 O(N³)를 금지한다

두 번째 결정. 워커 오프로드만으로는 부족하다. 워커도 죽는다 — 스크립트 로드 실패, 미지원 환경. 그때 예전 코드는 "워커가 못 하면 메인 스레드가 대신 (전체 체인을) 돈다"였고, 그게 바로 멈춤의 경로였다.

그래서 규칙을 하나 박았다. network-simplex를 포함한 크래시 폴백 체인은 워커 안에서만 돈다. 메인 스레드는 fast 경로만 허용한다. 1장 끝에 나온 layoutAssetGraphFast — 기본 ranker를 비-compound로만 시도하고 실패 시 격자 — 가 바로 그 fast 경로다.

fast 경로가 폴백 체인 없이 단 두 단인 근거는 1장의 실측 표에 이미 있다. 비-compound면 크래시율 0%다. 크래시 조건(클러스터)이 없는 경로에는 크래시 폴백도 필요 없고, network-simplex로 재시도할 일 자체가 없다.

그럼 워커 안에는 왜 O(N³)를 남겨뒀나? 어차피 비-compound가 0%라면 워커도 fast 경로만 쓰면 될 텐데 — 워커에서는 트레이드오프가 다르다. 워커의 network-simplex 재시도는 "compound 품질을 살릴 마지막 기회"고, 몇 초가 걸려도 UI는 멀쩡하다. 메인 스레드에서 같은 재시도는 "브라우저 몇 초 정지" 정도다.

묻지 않고 접는다

계산을 워커로 옮기고 최악 경로를 막았는데도, 900개 노드를 다 그리는 것 자체가 무겁다. 레이아웃이 끝나도 DOM/SVG 개체 900개와 엣지 path 1,007개를 초기 렌더가 전부 생성해야 한다. 레이아웃이 다가 아니고, 렌더 볼륨이 남는다.

그래서 세 번째 결정. 노드 300개를 넘는 그래프는 사용자에게 묻지 않고 그룹을 전부 접은 상태로 시작한다.

AS-IS (전부 펼침) TO-BE (기본 접힘) 초기 렌더 개체 900 300 엣지 path 1,007 403

"사용자 선택권은?"이라는 반론이 바로 나올 텐데, 그래서 이 자동화에는 그나마 양보한 조건 두 개가 붙어 있다.

// asset-graph-explorer.tsx
// 대형 그래프 기본 접힘 — 저장된 사용자 선택이 없을 때 1회만.
// 저장은 하지 않는다: 사용자가 직접 펼치기/접기를 만지면 그때부터 영속화된다.
const defaultCollapseAppliedRef = useRef(false)
useEffect(() => {
  if (defaultCollapseAppliedRef.current || allGroups.length === 0) return
  defaultCollapseAppliedRef.current = true
  if (nodeCount > LARGE_GRAPH_COLLAPSE_THRESHOLD && !hasStoredCollapsedGroups()) {
    setCollapsedGroups(allGroups)
  }
}, [nodeCount, allGroups])

첫째, 저장된 사용자 선택이 있으면 자동화가 물러난다. 예전에 직접 펼쳐놓은 사람의 화면을 멋대로 접지 않는다.
둘째, 자동 접힘 자체는 저장하지 않는다. 저장이 시작되는 순간은 사용자가 처음으로 직접 접기/펼치기를 만진 순간이다. 자동화는 첫인상 한 번만 결정하고, 그 뒤의 주인은 사용자다.

접는 게 싸니까 접는 거다

이 결정이 성립하는 전제가 하나 있다. 접기가 싸야 한다. 접을 때마다 dagre가 다시 돌면 그 접힘은 그 자체로 성능 문제다.

우리 접기는 제자리 접기다. 레이아웃은 항상 "전체 그래프" 기준으로 한 번만 계산하고, 접기/펼치기는 렌더 계층에서만 표현한다 — 멤버 노드 숨김, 그룹 프록시 노드 치환, 엣지 재라우팅(숨은 노드의 엣지를 프록시 노드 경계 앵커로 다시 붙이고, 같은 그룹 쌍의 중복 엣지는 dedupe). dagre 재실행이 없으니 접고 펼쳐도 다른 노드가 1px도 움직이지 않고, 레이아웃 캐시 키도 접힘 조합과 무관해진다.

캐시 얘기가 나온 김에. 레이아웃 결과는 그래프 구조 해시를 키로 IndexedDB에 LRU 50개까지 캐시한다(localStorage의 10MB 한계를 피해 IndexedDB로 간 것도 Dagster 팀이 같은 글에서 idb-lru-cache로 먼저 간 길이다). 같은 그래프를 다시 열면 워커도 안 돈다. 1장에서 "캐시 키에 그룹 정보가 없어서 옛 배치가 살아남았다"고 했던 그 캐시다. 강력한 만큼, 키 설계를 틀리면 버그도 오래 산다..

웹워커는 오버엔지니어링 아닌가?

대부분의 화면에서는 그렇다. 폼 제출하고 목록 그리는 화면에 워커를 넣는 건 낭비다.

이 구조가 수지가 맞으려면 —

계산이 메인 스레드를 체감 가능하게(수백 ms 이상) 잡는다
입력·출력이 구조적 데이터라 structured clone 직렬화가 싸다
같은 입력이 반복돼 캐시가 먹힌다

그래프 레이아웃은 셋 다 해당한다. 셋 중 하나라도 빠지면 동기 계산 + 로딩 스피너가 더 정직한 답일 수 있다.

이제 그래프는 안 죽고, 안 멈춘다. 그래서 다시 900노드 전체 리니지를 열었다. 잘 열린다. 빠르다. 그리고..

3. 다 그렸더니 아무것도 안 보였다

"근데 이걸로 뭘 알 수 있지?"

엣지 1,000개가 서로를 가로지르는 화면은 이미 그래프라고 부르기 어렵다. 그래프 시각화 쪽에서 헤어볼이라고 부르는 바로 그 상태다. 노드 사이의 관계를 보여주려고 그린 선들이, 정작 많아지는 순간 관계를 가장 먼저 지워버린다. 어떤 선이 어디서 와서 어디로 가는지 눈으로 따라갈 수가 없다.

여기서 문제의 종류가 바뀐다. 1·2장은 '그리는 비용'과 싸웠다 — 죽거나, 멈추거나. 3장은 다 그려내는 데 성공하고도 남는 '읽는 비용'과 싸운다. 이쯤 되면 성능 이슈라기보다 정보 설계 이슈다.

엣지는 50개만 그린다

첫 번째 결정. 뷰포트와 교차하는 엣지 중 50개만 그린다.

컬링은 2단계 파이프라인이다. 먼저 O(E) 필터로 뷰포트 밖 엣지를 걸러내고, 살아남은 게 50개를 넘을 때만 O(E log E) 정렬로 상위 50개를 고른다.

// viewport-culling.ts
const MAX_VISIBLE_EDGES = 50

// 1단계: AABB(축 정렬 바운딩 박스) 교차 판정 — 엣지의 양 끝점으로 만든 사각형이
// 뷰포트(+패딩 50px)와 겹치는지만 본다. 실제 선분 교차보다 후한 근사다.
function doesEdgeIntersectViewport(edge: EdgeWithEnds, vp: ViewportRect, padding = 50): boolean {
  const minX = Math.min(edge.from.x, edge.to.x)
  const maxX = Math.max(edge.from.x, edge.to.x)
  const minY = Math.min(edge.from.y, edge.to.y)
  const maxY = Math.max(edge.from.y, edge.to.y)
  return !(
    maxX < vp.left - padding ||
    minX > vp.right + padding ||
    maxY < vp.top - padding ||
    minY > vp.bottom + padding
  )
}

// 2단계: 초과분만 점수 정렬로 컷
export function getVisibleEdges<E extends EdgeWithEnds>(
  edges: E[],
  viewport: ViewportRect,
  maxEdges = MAX_VISIBLE_EDGES,
): E[] {
  const intersecting = edges.filter((e) => doesEdgeIntersectViewport(e, viewport))
  if (intersecting.length <= maxEdges) return intersecting
  return intersecting
    .map((edge) => ({ edge, score: edgeVisibilityScore(edge, viewport) }))
    .sort((a, b) => b.score - a.score)
    .slice(0, maxEdges)
    .map((item) => item.edge)
}

1단계의 AABB 판정은 의도적으로 후하게 가져간다. 대각선 엣지의 바운딩 박스는 실제 선분보다 크니까, 화면 모서리를 스치지도 않는 엣지가 살아남을 수 있다(false positive). 반대는 없다 — 실제로 보이는 엣지가 잘리는 일(false negative)은 이 근사에서 발생하지 않는다. 컬링에서 후한 쪽 오차는 렌더 몇 개 낭비지만, 박한 쪽 오차는 눈앞에서 선이 사라지는 버그다. 근사를 고를 때 오차의 방향부터 정해야 한다.

그럼 2단계의 점수 함수는 얼마나 정교하냐면 —

function edgeVisibilityScore(edge: EdgeWithEnds, vp: ViewportRect): number {
  const fromIn = isPointInViewport(edge.from, vp) ? 1 : 0
  const toIn = isPointInViewport(edge.to, vp) ? 1 : 0
  return fromIn + toIn
}

이게 전부다. 양 끝이 다 보이면 2점, 한쪽만 보이면 1점, 화면을 스치기만 하면 0점.

(물론... 더 정교한 걸 설계하려 했다. 엣지 길이, 뷰포트 중심과의 거리, 선택 상태 가중치.. 근데 만들고 보니 점수의 절대값은 아무 데도 쓰이지 않았다. 버릴 엣지를 고르는 문제에서 쓰이는 건 순서뿐이다...AI야.. 다 필요하다며)

중요한 건, 이 캡이 뷰포트의 순수 함수라는 거다. 확대해서 교차 엣지가 50개 아래로 내려가면 intersecting.length <= maxEdges 분기로 빠져 전부 그려진다. 축소하면 다시 걸린다. 숨김을 어딘가에 저장하지 않으니 무효화할 상태도 없다.

줌 0.15 밑에서는 노드도 안 그린다

두 번째 결정은 같은 원칙의 노드 버전 — 흔히 semantic zoom 또는 LOD(level of detail)라 부르는 것의 최소 구현이다.

// viewport-culling.ts
export const GROUPS_ONLY_SCALE = 0.15

export function shouldRenderNode(nodeId, groupId, collapsedGroups, scale): boolean {
  if (scale < GROUPS_ONLY_SCALE && groupId && collapsedGroups.has(groupId)) {
    return false
  }
  return true
}

줌 배율이 0.15 밑으로 내려가면 — 전체 그래프를 조감하는 수준이면 — 접힌 그룹 안의 개별 노드는 그리지 않는다. 그 축척에서 노드 하나는 어차피 몇 픽셀짜리 점이다. 읽히지 않는 것을 그리는 비용은 전부 낭비고, 그 축척에서 사용자가 실제로 읽는 단위는 그룹이다.

지도 제작이 이 문제를 먼저 정착시켰다. cartographic generalization — 축척이 작아지면 골목은 사라지고 도시는 점이 되는 것 (이야.. 대규모 시스템 설계 기초 2편이 이렇게 쓰이네)

팬은 GPU에게, 판정은 React에게

세 번째 결정은 위 두 판정이 "언제" 다시 도는지에 대한 거다.

컬링 판정은 뷰포트의 함수라서, 화면을 끌면 판정이 바뀐다. 순진하게 구현하면 팬 중 매 프레임 setState → React 커밋 → 자식 재렌더 → 컬링 재판정이 돈다. 근데 240px쯤 끌어봐야 판정 결과는 거의 안 바뀐다 — 뷰포트 가장자리의 엣지 몇 개가 들고 날 뿐이다. 판정 결과가 안 바뀌는데 판정 비용만 매 프레임 내는 구조다.

// svg-viewport.tsx
/**
 * 팬-재렌더 분리: 팬/줌 중에는 React state 를 건드리지 않고
 * DOM transform 만 직접 갱신한다(GPU 합성만 발생). React 커밋(=자식 재렌더,
 * 컬링 재판정)은 제스처가 멈추거나 이 거리(화면 px)만큼 이동했을 때만 수행.
 * 컬링 뷰포트는 같은 거리만큼 패딩해 커밋 사이에 노드가 비어 보이지 않게 한다.
 */
const CULL_COMMIT_PX = 240
const WHEEL_COMMIT_DELAY_MS = 120

팬 중에는 60fps로 스로틀된 핸들러가 DOM 엘리먼트의 style.transform = matrix(...)만 직접 갱신한다. willChange: 'transform'이 걸린 레이어라 브라우저는 레이아웃·페인트 없이 컴포지터에서 기존 레이어를 옮기기만 하고, React는 아무것도 모른다. 누적 이동량이 240px를 넘거나 제스처가 끝나면 그때 한 번 커밋해서 컬링을 다시 판정한다.

// svg-viewport.tsx — onMove (팬 핸들러 발췌)
applyLive({ x: liveRef.current.x + delta.x, y: liveRef.current.y + delta.y }) // transform만
sinceCommit += Math.abs(delta.x) + Math.abs(delta.y)
if (sinceCommit > CULL_COMMIT_PX) {
  sinceCommit = 0
  commitLive() // 여기서만 React가 깨어난다
}

커밋 트리거의 축이 제스처마다 다르다. 팬은 거리 기반(240px 누적)이고, 휠 줌은 시간 기반(120ms 디바운스)이다. 팬은 이동량이 판정 변화량에 비례하니 거리가 맞고, 휠은 틱이 불규칙하게 쏟아지니 "멈춘 뒤"가 맞다. 디바운스를 걸 때 시간 축이 기본값이 되기 쉬운데, 신호의 성질에 따라 축을 골라야 한다.
커밋 사이의 빈 화면은 패딩으로 막는다. 커밋 없이 끌 수 있는 최대 거리가 240px이니, 컬링 뷰포트를 SVG 좌표 기준으로 그만큼 사방 확장해서 미리 그려둔다(padViewport(getViewport(), CULL_COMMIT_PX / scale) — 화면 px를 SVG 좌표로 환산하려고 scale로 나눈다).

엣지를 숨기면 안된는거 아닌가?

맞다, 그래서 이 화면의 목적을 다시 물어야 한다. 리니지 그래프는 엣지를 세는 화면이 아니라 따라가는 화면이다. 사용자의 실제 동선은 "이 모델의 상류가 어디지"를 확대해 들어가며 따라가는 것이지, 축소 화면에서 선 1,000개를 훑는 게 아니다. 따라가는 동선에서는 확대하는 순간 교차 엣지 수가 캡 밑으로 내려가 전부 그려진다. 캡이 깎는 건 어차피 읽을 수 없던 축소 화면의 헤어볼뿐이다.

물론 이 논리에도 문제점은 있다, 축소 화면에서 "멀리 떨어진 두 클러스터가 연결돼 있는가"를 확인하고 싶은 사용자에게는, 그 한 가닥이 캡에 잘리면 진짜 정보 손실이다.(이건 다음 리니지 개선으로...)

참고 자료:

Scale DAG Visuals for 10K+ Assets — Dagster Blog (2023): Rust/WASM 포팅 시도와 포기, network-simplex → tight-tree 전환, 뷰포트 기반 엣지 컬링, IndexedDB 레이아웃 캐시
A Technique for Drawing Directed Graphs — Gansner, Koutsofios, North, Vo (GKNV), IEEE TSE 1993