Diffing 알고리즘, 최소한의 변경점 찾기

단일 노드를 비교하는 데 성공하자, 조던 워크와 팀은 곧바로 가장 까다로운 문제에 부딪혔다. 바로 여러 개의 자식 노드를 가진 목록을 비교하는 것이었다.

그는 새로운 시나리오를 화이트보드에 그렸다. 친구 목록을 렌더링하는 컴포넌트였다.

• 이전 목록(Old List): [ 'Alice', 'Bob', 'Charlie' ]
• 새로운 목록(New List): [ 'Alice', 'David', 'Bob', 'Charlie' ]

이전 버추얼 DOM 트리는 3개의 <li> 자식을, 새로운 트리는 4개의 <li> 자식을 가지고 있었다.

// 이전 VDOM children
[
  { tagName: 'li', children: ['Alice'] },
  { tagName: 'li', children: ['Bob'] },
  { tagName: 'li', children: ['Charlie'] }
]

// 새로운 VDOM children
[
  { tagName: 'li', children: ['Alice'] },
  { tagName: 'li', children: ['David'] },
  { tagName: 'li', children: ['Bob'] },
  { tagName: 'li', children: ['Charlie'] }
]

가장 단순하고 무식한 diff 알고리즘이라면 이렇게 동작할 것이다.

1. 첫 번째 자식: ‘Alice’ vs ‘Alice’. 동일.
2. 두 번째 자식: ‘Bob’ vs ‘David’. 다름! <li>Bob</li>의 텍스트를 ‘David’로 수정한다.
3. 세 번째 자식: ‘Charlie’ vs ‘Bob’. 다름! <li>Charlie</li>의 텍스트를 ‘Bob’으로 수정한다.
4. 네 번째 자식: 이전 목록에는 없음. 새로 추가! <li>Charlie</li>를 새로 생성하여 맨 뒤에 추가한다.

이 결과는 화면상으로는 올바르게 보이지만, 끔찍하게 비효율적이다. 실제로는 ‘David’를 중간에 삽입하기만 하면 되는데, 불필요하게 두 개의 <li>를 수정하고 하나의 <li>를 새로 만드는 낭비를 저지른 것이다.

“이 문제를 해결하지 못하면, 우리의 알고리즘은 반쪽짜리입니다.” 데이빗이 냉정하게 지적했다.

조던은 이 문제를 해결하기 위해, 이전에 어렴풋이 구상했던 두 번째 가정, 바로 key의 도입을 구체화했다.

“개발자가 우리에게 힌트를 주는 겁니다. 어떤 자식이 어떤 자식인지 알려주는 고유한 식별자, key를 제공하도록 하는 거죠.”

그는 코드를 수정했다. 각 <li> 컴포넌트를 렌더링할 때, 고유한 key 속성을 추가하도록 했다.

// key를 사용한 VDOM children
[
  { tagName: 'li', properties: { key: 'user-alice' }, children: ['Alice'] },
  { tagName: 'li', properties: { key: 'user-bob' }, children: ['Bob'] },
  { tagName: 'li', properties: { key: 'user-charlie' }, children: ['Charlie'] }
]

이제 diff 알고리즘은 훨씬 더 영리하게 동작할 수 있었다. 알고리즘은 더 이상 순서에만 의존하지 않고, key를 기준으로 자식들을 비교한다.

1. 알고리즘은 이전 자식 목록의 key들을 해시맵(HashMap)으로 만들어 저장한다: { 'user-alice': (노드), 'user-bob': (노드), ... }. 이 작업은 O(n)으로 매우 빠르다.
2. 새로운 자식 목록을 순회하며 각 노드의 key를 이전 목록의 해시맵에서 찾아본다.
   • key="user-alice": 이전 목록에 존재. 이동 없음.
   • key="user-david": 이전 목록에 없음. 새로운 노드! <li>David</li>를 생성하여 현재 위치에 삽입하라는 명령을 생성한다.
   • key="user-bob": 이전 목록에 존재. 이동 없음.
   • key="user-charlie": 이전 목록에 존재. 이동 없음.

결과는 놀라웠다. 최종적으로 생성된 변경 목록은 단 하나였다.

[ { type: 'INSERT_NODE', parentNode: (ul), newNode: (li David), beforeNode: (li Bob) } ]

불필요한 수정이나 삭제 없이, 오직 <li>David</li>를 <li>Bob</li> 앞에 ‘삽입’하라는 가장 효율적인 단 하나의 명령만을 정확히 찾아낸 것이다.

이 key를 이용한 비교 방식은 조던의 Diffing 알고리즘을 완성하는 마지막 퍼즐 조각이었다. 이로써 그의 라이브러리는 일반적인 트리 비교의 복잡성을 회피하고, 웹 UI 업데이트라는 특정 목적에 놀랍도록 최적화된, 빠르고 효율적인 알고리즘을 갖추게 되었다.

이 알고리즘은 훗날 재조정(Reconciliation)이라는 이름으로 불리며, 조던의 라이브러리가 가진 가장 강력하고 독창적인 무기가 된다. 그는 마침내, 성능이라는 거대한 벽을 넘을 수 있다는 기술적 확신을 얻었다. 이제 남은 것은 동료들의 의심을 잠재우고, 실제로 동작하는 결과물을 보여주는 것뿐이었다.