junyeokk
Blog
react-internals·2024. 10. 02

Virtual DOM Diffing 알고리즘

UI 라이브러리에서 상태가 바뀔 때마다 화면을 갱신해야 한다. 가장 단순한 방법은 innerHTML로 전체를 다시 그리는 것이다.

javascript
function render(state) {
  container.innerHTML = `
    <ul>
      ${state.items.map(item => `<li>${item}</li>`).join("")}
    </ul>
  `;
}

동작은 하지만 문제가 많다. 기존 DOM 트리를 전부 파괴하고 새로 만들기 때문에 input의 포커스가 날아가고, 체크박스 상태가 초기화되며, CSS transition이 끊기고, 이벤트 리스너를 다시 붙여야 한다. 아이템 하나만 추가됐는데 리스트 전체를 다시 만드는 건 낭비다.

이 문제를 해결하려면 "이전 상태의 UI"와 "다음 상태의 UI"를 비교해서 실제로 바뀐 부분만 DOM에 반영하면 된다. 이게 diffing 알고리즘의 핵심 아이디어다.

왜 Virtual DOM 위에서 diff를 하는가

실제 DOM 노드를 직접 비교하는 건 비현실적이다. DOM 노드는 프로퍼티가 수백 개나 되고, 읽기만 해도 reflow를 유발하는 속성들이 있다. 비교 자체가 비용이 된다.

그래서 DOM의 구조를 가볍게 표현하는 JavaScript 객체, 즉 Virtual DOM을 만들어서 비교한다.

javascript
// Virtual DOM 노드 (VNode)
{
  type: "div",
  props: {
    className: "card",
    children: [
      { type: "h2", props: { children: ["제목"] } },
      { type: "p", props: { children: ["내용"] } }
    ]
  }
}

이 객체는 순수한 JavaScript이므로 비교가 빠르고, 메모리도 적게 쓴다. 상태가 바뀌면 새 VNode 트리를 만들고, 이전 VNode 트리와 비교해서 차이점을 찾고, 그 차이점만 실제 DOM에 반영한다. 이 세 단계가 렌더링 파이프라인이다.

일반적인 트리 diff의 복잡도 문제

두 트리의 최소 편집 거리를 구하는 알고리즘은 O(n³) 시간복잡도를 가진다. 노드가 1,000개면 연산이 10억 번이다. UI를 매 프레임 갱신해야 하는 상황에서 이건 쓸 수 없다.

React가 제안한 해결책은 두 가지 휴리스틱으로 O(n) 복잡도를 달성하는 것이다.

  1. 타입이 다른 노드는 서브트리 전체를 교체한다 — <div>가 <span>으로 바뀌면 내부를 비교하지 않고 통째로 새로 만든다
  2. 같은 레벨의 자식 노드는 key로 매칭한다 — 형제 노드 사이에서만 비교하고, 다른 레벨로 이동한 노드는 추적하지 않는다

이 두 가정 덕분에 트리를 한 번만 순회하면서 diff를 완료할 수 있다. 실제 UI 변경 패턴에서는 이 휴리스틱이 거의 항상 맞기 때문에 실용적이다.

diff 알고리즘 단계별 동작

1단계: 루트 노드 비교

diff의 시작점은 두 VNode의 type을 비교하는 것이다.

javascript
function diff(newVNode, oldVNode, container) {
  // 새 노드가 없으면 기존 DOM 제거
  if (!newVNode) {
    container.innerHTML = "";
    return;
  }

  // 텍스트/숫자 노드 처리
  if (typeof newVNode === "string" || typeof newVNode === "number") {
    if (oldVNode !== newVNode) {
      container.textContent = String(newVNode);
    }
    return;
  }

  // 타입이 다르면 전체 교체
  if (!oldVNode || newVNode.type !== oldVNode.type) {
    const newDom = createDomNode(newVNode);
    container.replaceWith(newDom);
    return;
  }

  // 타입이 같으면 속성 비교 + 자식 비교
  updateProps(container, oldVNode.props, newVNode.props);
  diffChildren(newVNode, oldVNode, container);
}

분기가 명확하다.

  • 새 노드가 null/undefined: 기존 DOM을 비운다
  • 텍스트 노드: 값이 다를 때만 textContent를 갱신한다
  • 타입이 다른 엘리먼트: 서브트리를 비교하지 않고 새 DOM으로 교체한다
  • 타입이 같은 엘리먼트: 속성만 업데이트하고, 자식 노드를 재귀적으로 비교한다

타입이 다를 때 서브트리를 버리는 게 과격해 보일 수 있다. <div>에서 <section>으로 바뀌면 내부 구조가 같더라도 전부 새로 만든다. 하지만 실제로 타입이 바뀌면 내부 구조도 대부분 바뀌기 때문에 비교를 건너뛰는 편이 효율적이다.

2단계: 속성(Props) 업데이트

같은 타입의 노드라면 DOM 요소를 재사용하고 속성만 갱신한다.

javascript
function updateProps(domElement, oldProps, newProps) {
  // 1. 제거된 속성 처리
  Object.keys(oldProps).forEach(key => {
    if (key !== "children" && !(key in newProps)) {
      if (key in domElement) {
        domElement[key] = null;       // DOM 프로퍼티 초기화
      } else {
        domElement.removeAttribute(key); // HTML 어트리뷰트 제거
      }
    }
  });

  // 2. 추가/변경된 속성 처리
  Object.keys(newProps).forEach(key => {
    if (key !== "children" && oldProps[key] !== newProps[key]) {
      if (key in domElement) {
        domElement[key] = newProps[key];       // DOM 프로퍼티로 설정
      } else {
        domElement.setAttribute(key, String(newProps[key])); // 어트리뷰트로 설정
      }
    }
  });
}

여기서 주목할 점은 DOM 프로퍼티와 HTML 어트리뷰트를 구분한다는 것이다. checked, value, disabled 같은 속성은 setAttribute로 설정하면 제대로 동작하지 않는 경우가 있다. 예를 들어 input.setAttribute("checked", "") 은 체크박스의 현재 상태를 바꾸지 않는다. input.checked = true처럼 DOM 프로퍼티로 직접 설정해야 한다.

이 구분이 중요한 이유는 HTML 어트리뷰트가 초기값을 나타내고, DOM 프로퍼티가 현재 상태를 나타내기 때문이다. 둘은 항상 동기화되지 않는다.

3단계: 자식 노드 비교 (Children Diffing)

가장 복잡한 부분이다. 자식 노드 배열 두 개를 비교해서 어떤 노드를 추가하고, 어떤 노드를 제거하고, 어떤 노드를 이동할지 결정해야 한다.

단순하게 인덱스 기반으로 비교하면 문제가 생긴다.

이전: [A, B, C, D] 다음: [B, C, D, A]

인덱스 0끼리 비교하면 A→B, 1끼리 비교하면 B→C… 결국 4개 노드를 모두 업데이트한다. 하지만 실제로는 A를 맨 뒤로 옮기기만 하면 된다. 이걸 해결하는 게 key 기반 매칭이다.

javascript
이전: [A, B, C, D]
다음: [B, C, D, A]

이 알고리즘의 핵심은 lastIndex 변수다. 이걸 이해하면 전체 로직이 보인다.

lastIndex 이동 판단 원리

새 자식 리스트를 앞에서부터 순회하면서, 각 노드가 이전 리스트에서 몇 번째에 있었는지를 확인한다. lastIndex는 "지금까지 만난 이전 인덱스 중 최댓값"이다.

규칙: 이전 인덱스가 lastIndex보다 작으면 이동이 필요하다.

왜 이 규칙이 동작하는지 예시로 보자.

이전: [A(0), B(1), C(2), D(3)] (괄호 안은 인덱스) 다음: [B, C, D, A]
새 리스트 순회이전 인덱스lastIndex이동?
B10 → 1❌ (1 ≥ 0)
C21 → 2❌ (2 ≥ 1)
D32 → 3❌ (3 ≥ 2)
A03✅ (0 < 3)

B, C, D는 이전 리스트에서도 이 순서대로 있었으므로 이동할 필요가 없다. A만 원래 위치(0)가 lastIndex(3)보다 앞이므로, 상대적 순서가 깨졌다는 뜻이다. A만 이동하면 된다.

다른 예시도 보자.

이전: [A(0), B(1), C(2)] 다음: [C, A, B]
새 리스트 순회이전 인덱스lastIndex이동?
C20 → 2❌ (2 ≥ 0)
A02✅ (0 < 2)
B12✅ (1 < 2)

C는 그대로, A와 B가 이동한다. 총 2번 이동이다.

이 방식의 한계도 있다. 만약 리스트의 마지막 원소가 맨 앞으로 오면?

이전: [A(0), B(1), C(2), D(3)] 다음: [D, A, B, C]
새 리스트 순회이전 인덱스lastIndex이동?
D30 → 3❌
A03✅
B13✅
C23✅

최적으로는 D 하나만 맨 앞으로 옮기면 되는데, 이 알고리즘은 A, B, C 세 개를 이동한다. D가 첫 번째로 처리되면서 lastIndex가 3으로 크게 잡히기 때문이다.

이건 O(n) 알고리즘의 트레이드오프다. 최적의 이동 횟수를 보장하지는 않지만, 대부분의 실제 UI 변경 패턴에서는 충분히 효율적이다. Vue 3는 이 문제를 LIS(Longest Increasing Subsequence) 알고리즘으로 개선한다.

노드 제거 처리

새 리스트에서 사라진 노드는 DOM에서 제거해야 한다. 이전 자식 리스트를 순회하면서, key가 새 리스트에 존재하지 않으면 해당 DOM 노드를 removeChild로 삭제한다.

이전: [A, B, C, D] 다음: [A, C] → B, D를 DOM에서 제거

이때 주의할 점은 key가 없는 노드의 처리다. key가 없으면 이전/새 노드 간 매칭이 불가능하므로 인덱스 기반으로 비교하게 된다. 이 경우 불필요한 업데이트가 발생할 수 있다.

전체 흐름 정리

상태가 바뀌었을 때 렌더링이 일어나는 전체 과정이다.

상태 변경 ↓ 새 VNode 트리 생성 (createElement 호출) ↓ diff(newVNode, oldVNode, domNode) ├── 타입 비교 → 다르면 교체 ├── 같으면 → updateProps() └── diffChildren() ├── key 맵 생성 ├── 새 리스트 순회 → 매칭/이동/생성 └── 이전 리스트 순회 → 미매칭 노드 제거 ↓ 실제 DOM에 최소한의 변경만 반영

이 파이프라인 덕분에 개발자는 "현재 상태에 대한 UI가 어떤 모습이어야 하는지"만 선언하면 된다. 이전 상태와의 차이를 계산하고 DOM을 효율적으로 갱신하는 건 diff 알고리즘이 알아서 처리한다. 이게 선언적 UI 프로그래밍의 핵심이다.

React의 실제 diff와의 차이

위에서 설명한 알고리즘은 개념을 이해하기 위한 단순화된 버전이다. React의 실제 reconciler는 훨씬 더 복잡하다.

  • Fiber 아키텍처: React 16+에서는 VNode 트리 대신 Fiber 트리를 사용한다. 각 Fiber 노드가 linked list로 연결되어 있어서 diff 작업을 여러 프레임에 걸쳐 나눠서 처리할 수 있다 (시분할 렌더링)
  • 더블 버퍼링: current 트리와 workInProgress 트리 두 개를 유지하면서, diff가 끝나면 포인터만 교체한다
  • Lane 모델: 업데이트에 우선순위를 부여해서 사용자 인터랙션(클릭, 타이핑)이 백그라운드 데이터 페칭보다 먼저 처리되도록 한다

하지만 근본적인 아이디어 — 두 트리를 비교해서 차이만 반영한다 — 는 동일하다. 단순한 diff 구현으로 시작해서 점차 최적화를 쌓아올린 것이다.

관련 문서