Notion은 CRDT로 동시 편집을 어떻게 처리하는가

AI 요약

Notion의 편집기는 수백 명에서 수천 명이 함께 문서를 작성하는 환경에서 사용되지만, 2025년까지는 같은 블록을 동시에 편집할 때 진정한 의미의 협업 편집을 제공하지 못했습니다. 기존 시스템은 블록을 별도의 데이터베이스 레코드로 저장하고 각 업데이트를 도착 순서대로 반영하는 Last Write Wins(LWW) 방식이었습니다. 예를 들어 Emma가 “Build cool things”로 고치고 Charlie가 “Build things quickly”로 고쳤다면, 서버가 마지막으로 처리한 업데이트만 남고 다른 사용자의 변경 내용은 사라졌습니다. 서로 다른 블록을 동시에 편집할 때는 충돌이 적었지만, 같은 블록의 텍스트를 수정할 때는 변경 손실이 발생했으며 Offline Mode에서는 재접속 전에 다른 사용자가 같은 블록을 수정할 경우 오프라인 작업 전체가 사라질 위험도 있었습니다.

■ RGA 기반 CRDT와 텍스트 병합

Notion은 이 문제를 해결하기 위해 Conflict-free Replicated Data Type(CRDT)을 도입했습니다. CRDT는 여러 클라이언트가 데이터의 로컬 복사본을 유지하면서 동시에 발생한 변경을 결정론적으로 병합하는 자료구조입니다. 모든 사용자의 의도를 항상 완벽하게 보존하는 것은 아니지만, 긴 문서에서 서로 떨어진 위치를 각자 편집하는 경우에는 변경 내용을 잃지 않고 의도를 잘 유지할 수 있습니다.

Notion이 사용하는 CRDT는 Replicated Growable Array(RGA)를 기반으로 합니다. RGA는 삽입된 모든 문자를 노드로 보관하는 트리 자료구조이며, 각 노드에는 고유하고 안정적인 ID가 부여됩니다. Notion은 이 노드를 “text item”, 삽입 위치를 가리키는 ID를 “origin”이라고 부릅니다. 트리는 시작 item과 끝 item으로 초기화되며, 삽입·삭제 연산은 특정 ID를 참조합니다. 삭제된 문자는 즉시 트리에서 제거하지 않고 “tombstone”으로 남깁니다. 아직 전달 중이거나 오프라인 상태에서 생성된 연산이 삭제된 문자의 ID를 참조할 수 있기 때문이며, 해당 노드를 제거하면 연산을 어디에 적용해야 하는지 알 수 없게 됩니다.

ID는 간소화된 session ID와 Lamport clock의 조합으로 만들어집니다. session ID는 클라이언트 세션을 구분하고, Lamport clock은 클라이언트가 알고 있는 가장 높은 논리 시간값을 바탕으로 증가합니다. 두 클라이언트가 같은 Lamport clock 값을 사용할 수는 있지만 session ID까지 같을 수는 없으므로 전체 ID는 고유해집니다. 같은 origin 뒤에 삽입된 item은 더 최근의 논리 timestamp를 우선하고, timestamp가 같으면 session ID를 tie-breaker로 사용해 정렬합니다. 저장 공간을 줄이기 위해 모든 문자를 개별 ID로 저장하지 않고, 같은 세션과 Lamport clock에서 연속으로 삽입된 문자를 하나의 run으로 묶어 run length를 함께 저장합니다.

■ 서식 충돌과 Peritext

Notion 문서는 일반 텍스트가 아니라 굵게 표시하는 bold, 기울임꼴인 italic, 페이지 멘션 같은 rich text 요소를 포함합니다. 따라서 텍스트 삽입 충돌뿐 아니라 서식 annotation의 충돌도 병합해야 합니다. 예를 들어 Charlie가 특정 구간에 bold를 적용하고 Emma가 동시에 같은 구간에 italic을 적용하면, 최종 텍스트에는 두 annotation이 모두 남아야 합니다.

이를 위해 Notion은 Peritext 알고리즘에 기반한 연산을 사용합니다. CRDT 트리는 텍스트 item에 annotation을 추가하거나 제거하는 연산을 저장하고, 트리를 파싱할 때 해당 연산을 적용합니다. annotation의 시작점과 끝점은 item의 경계 바로 앞이나 바로 뒤를 가리키는 anchor point로 표현합니다. 이 방식은 서식이 이후 입력에 이어지는지 여부도 나타낼 수 있습니다. 예를 들어 bold는 extendable annotation이므로 굵은 텍스트 끝에 새로 입력한 내용도 계속 굵게 표시될 수 있습니다. 반면 hyperlink는 extendable하지 않으므로 링크 뒤에 입력한 텍스트까지 자동으로 링크가 이어지지 않도록 끝 anchor를 다르게 지정합니다.

하나의 text item에는 여러 annotation을 연결할 수 있으며, 겹치는 annotation도 지원합니다. annotation이 여러 item에 걸쳐 있더라도 연산 자체는 첫 번째 item에만 저장하고, ID 범위로 나머지 구간을 식별합니다.

■ 블록 분할을 처리하는 text slice

Notion에서 사용자가 블록 중간에서 Enter를 누르면 새로운 블록이 만들어지고 기존 텍스트가 두 블록으로 나뉩니다. 이때 Emma가 “Build things” 뒤에서 블록을 분할하는 동시에 Charlie가 원래 블록에 공백과 “quickly”를 추가할 수 있습니다. 분할이 먼저 적용된다면 Charlie의 입력은 그가 편집 당시 참조한 원래 블록이 아니라 새로 만들어진 블록에 들어가야 합니다. 동시 편집으로 인해 연산이 가리키는 origin이 더 이상 같은 데이터베이스 레코드에 존재하지 않을 수 있기 때문입니다.

Notion은 이를 위해 “text slice”라는 개념을 도입했습니다. 블록의 텍스트 item은 text slice에 속하며, 모든 블록은 빈 text slice로 시작합니다. 블록이 분할되면 하나의 text slice가 둘로 나뉘고, 두 번째 slice가 새 블록으로 이동합니다. 같은 블록에 속한 text slice는 “text slice tree”라는 트리로 조직되며, 이 트리를 재구성하면 해당 블록의 텍스트를 얻을 수 있습니다. 하나의 text slice tree에는 서로 다른 블록에서 시작된 slice가 함께 포함될 수도 있습니다.

각 slice는 최초 slice에서 파생된 모든 slice를 묶는 “text instance”에도 속합니다. slice가 분할되거나 다른 블록으로 이동해도 같은 text instance를 유지하므로, text instance를 연산이 참조할 수 있는 안정적인 식별자로 사용할 수 있습니다. Notion은 text instance와 그 일부 slice를 포함하는 블록 사이의 매핑을 유지하고, 특정 text instance에 대한 연산이 도착하면 관련 블록을 조회해 대상 slice를 찾습니다. Emma의 분할 이후에는 instance A의 slice가 Block A와 Block B에 모두 존재하므로 Charlie의 연산은 Block A를 참조하면서도 text instance ID를 통해 두 블록에서 실제 대상을 찾을 수 있습니다.

■ search label과 조회 비용 개선

이 설계는 하나의 text instance에 속한 slice가 많은 블록으로 나뉘면 여러 블록을 모두 읽어야 한다는 한계가 있습니다. 예를 들어 한 블록을 99번 분할하면 같은 text instance의 slice를 포함하는 블록이 100개가 됩니다. 특정 slice에 문자를 삽입하려면 매핑이 반환한 100개 블록을 가져와 각 text slice tree를 순회해야 합니다.

Notion은 이 문제를 줄이기 위해 각 text slice에 “search label”을 부여했습니다. 처음에는 빈 label이며, slice가 분할될 때 왼쪽 조각에는 L, 오른쪽 조각에는 R을 이어 붙입니다. “things”가 다시 “thing”과 “s”로 나뉘면 각각 RL과 RR 같은 label을 갖습니다. text instance와 block의 매핑에 이 label을 포함하면, 연산이 제공한 label로 시작하는 slice를 가진 블록만 조회할 수 있습니다. Charlie의 입력이 R label을 포함하고 있을 때 검색 조건을 정확히 R로 한정하지 않고 R로 시작하는 label을 찾는 이유는 대상 slice가 동시에 다시 분할될 수 있기 때문입니다. 대상이 RR로 바뀌었더라도 기존 연산의 R label로 찾을 수 있어야 합니다.

실제 구현에서 Notion은 LRL 같은 label 문자열을 그대로 저장하거나 Postgres에서 `label LIKE 'LR%'`로 검색하지 않습니다. 저장 효율을 높이는 compact encoding을 사용하며, 원문은 이 방식이 저장 효율을 5배 개선한다고 설명합니다. Notion은 이 블록 분할 처리 방식이 텍스트 조각을 독립적인 노드로 모델링하는 다른 편집 시스템에도 활용될 수 있다고 언급합니다. 다만 ProseMirror와 Yjs에서는 분할을 첫 번째 블록의 삭제와 두 번째 블록의 삽입으로 모델링하기 때문에, 동시 입력이 원래 노드에 남을 수 있으며 Notion의 방식은 분할 이후에도 의도한 위치를 보존하도록 설계됐다고 설명합니다.

■ 운영 배포와 확장

Notion은 이 CRDT 시스템을 2025년 7월 운영 환경에 배포했습니다. 회사의 설명에 따르면 이 시스템은 세계에서 가장 큰 CRDT 배포 사례 중 하나이며, 매분 수백만 건의 CRDT 연산을 처리합니다. 새 데이터 모델은 실시간 동시 편집뿐 아니라 Offline Mode와 agent collaboration도 지원하는 기반이 됩니다. Notion은 향후 협업자의 presence를 개선하거나, 여러 제안을 하나의 묶음으로 처리해 함께 게시하고 승인할 수 있는 기능에도 이 기반을 활용할 계획이라고 밝혔습니다.

원문: Notion / 번역·요약: Trawling