같은 문서를 동시에 고치면 무슨 일이 생길까 — OT, CRDT, 그리고 제3의 길

두 사람이 같은 문서의 같은 위치를 동시에 수정합니다. 한 사람은 문자를 넣고, 다른 사람은 바로 옆 문자를 지웁니다. 각자의 화면에서는 즉시 잘 반영됐는데 네트워크를 타고 상대의 수정이 도착하자 문장이 달라집니다.

실시간 협업 편집의 어려움은 WebSocket으로 변경사항을 빨리 보내는 데 있지 않습니다. 서로 다른 순서로 변경을 받은 모든 사용자가 결국 같은 결과를 보게 만드는 것이 핵심입니다.

이 문제에 대한 대표적인 답이 OT(Operational Transformation)와 CRDT(Conflict-free Replicated Data Type)입니다. 하지만 실제 제품은 둘 중 하나를 교과서 그대로 선택하지 않습니다. Google Docs는 OT를 대중화했고, Yjs는 CRDT를 실용적인 라이브러리로 만들었습니다. Figma는 중앙 서버를 활용해 CRDT의 일부 규칙만 가져왔고, Notion의 공식 자료는 블록과 트랜잭션 중심의 동기화 파이프라인을 설명합니다.

이 글에서는 알고리즘 이름보다 더 중요한 질문을 따라가 보겠습니다.

누가 변경의 순서를 결정하는가? 그리고 충돌의 최소 단위는 문자인가, 속성인가, 블록인가?

먼저, 무엇을 보장해야 할까

협업 편집기는 보통 세 가지를 동시에 원합니다.

즉각적인 반응 — 키를 누를 때마다 서버 응답을 기다리면 편집할 수 없습니다. 로컬 화면에는 먼저 반영해야 합니다.
수렴(convergence) — 모든 변경이 전달된 뒤에는 모든 사용자가 같은 상태를 봐야 합니다.
의도 보존 — 수렴만 했다고 충분하지 않습니다. 내가 제목에 굵게 표시했는데 전혀 다른 문장에 적용된다면 결과는 같아도 의도는 깨진 것입니다.

첫 번째는 클라이언트 사이드 예측으로 해결할 수 있습니다. 어려운 것은 두 번째와 세 번째입니다. OT와 CRDT의 차이는 이 충돌 해결 규칙을 연산 변환에 둘 것인지, 자료구조 안에 넣을 것인지에서 시작합니다.

OT — 위치가 어긋나면 연산을 바꾼다

OT는 1989년 Ellis와 Gibbs가 실시간 그룹웨어의 동시성 제어 문제를 다루며 제안한 계열의 알고리즘입니다. 핵심은 문서를 스냅샷으로 주고받지 않고 편집을 연산으로 표현하는 것입니다. 원 논문은 동시 실행되는 그룹웨어에서 빠른 응답과 일관성을 함께 다루는 방법을 제시했습니다.

예를 들어 문서가 AB이고 두 사용자가 동시에 A와 B 사이에 문자를 넣었다고 해보겠습니다.

초기 문서: AB

사용자 1: Insert("X", position=1)  → AXB
사용자 2: Insert("Y", position=1)  → AYB

각 연산을 상대 문서에 그대로 적용하면 도착 순서에 따라 AYXB 또는 AXYB가 될 수 있습니다. OT는 두 연산이 같은 기준 문서에서 출발했다는 사실을 이용해 한쪽 위치를 변환합니다. 서버 순서나 사용자 ID 같은 결정 규칙으로 X가 먼저라고 정했다면, Y의 위치를 1에서 2로 옮기는 식입니다.

Transform(Insert Y@1, against Insert X@1)
→ Insert Y@2

최종 문서: AXYB

Google Docs에서 공개한 방식

Google이 2010년에 공개한 Docs 설명에서는 편집을 InsertText, DeleteText, ApplyStyle 같은 변경으로 표현합니다. 한 편집자의 변경이 서버를 거쳐 다른 편집자에게 도착하면, 수신자는 그 변경을 자신의 로컬 문서 상태에 맞게 변환합니다. 예를 들어 범위 10–20에 굵게 표시하는 연산과 위치 15에 세 글자를 넣는 연산이 겹치면 스타일 범위는 10–23으로 늘어납니다. Google Docs의 OT 설명

대표적인 클라이언트·서버 OT 흐름은 다음과 같습니다.

클라이언트
  1. 로컬 연산을 즉시 적용
  2. 연산과 기준 revision을 서버로 전송
  3. 아직 승인되지 않은 로컬 연산을 보관

서버
  4. 변경 순서를 직렬화
  5. 기준 revision 이후의 연산과 변환
  6. 승인(ACK)과 변환된 연산을 전파

클라이언트
  7. 서버 변경과 대기 중인 로컬 변경을 다시 정렬

여기서 중앙 서버는 OT의 수학적 필수 조건은 아닙니다. 다만 서버가 전역 순서를 정하는 구조는 상태 공간을 크게 줄여줍니다. Google Wave의 공개 프로토콜도 서버가 연산을 변환하고 저장하는 구조를 사용했습니다. Google Wave federation architecture

OT의 어려움은 변환 함수에 있습니다. Insert와 Delete뿐 아니라 스타일, 범위, 표, 임베드, 실행 취소까지 추가되면 연산 쌍마다 올바른 변환 규칙이 필요합니다. 구현이 잘못되면 특정 도착 순서에서만 문서가 갈라지는 버그가 생깁니다. 반대로 중앙 서버가 있고 변경 타입이 제한적이라면, OT는 작은 메타데이터로 정교한 텍스트 편집을 제공하는 현실적인 선택입니다. CodeMirror 역시 중앙 서버가 변경 순서를 정하는 비교적 단순한 OT 모델을 선택했습니다. CodeMirror 협업 편집 설계

CRDT — 위치 대신 정체성을 저장한다

CRDT는 충돌이 발생할 때마다 연산을 변환하는 대신, 서로 다른 순서로 업데이트를 받아도 같은 결과가 나오도록 자료구조를 설계합니다. Shapiro 등의 2011년 논문은 이를 Strong Eventual Consistency 관점에서 정식화했습니다. 같은 업데이트 집합을 받은 복제본은 별도 합의 없이 같은 상태에 도달합니다. CRDT 원 논문

CRDT는 크게 두 방식으로 설명할 수 있습니다.

State-based CRDT: 복제본의 전체 상태를 병합합니다. 상태는 단조롭게 증가하는 semilattice를 이루고, merge는 두 상태의 least upper bound를 구합니다.
Operation-based CRDT: 변경 연산을 전달합니다. 동시에 발생한 연산이 가환하도록 만들고, 필요한 경우 인과적 순서를 보장합니다.

텍스트 CRDT에서 중요한 전환은 문자를 배열의 숫자 위치로만 보지 않는 것입니다. 각 삽입 요소에 고유 ID를 붙이고, “5번 위치에 삽입” 대신 “ID가 A인 요소 뒤에 삽입”처럼 표현합니다.

초기 상태: A(id:1) → B(id:2)

사용자 1: X(id:client1, clock:7)를 A 뒤에 삽입
사용자 2: Y(id:client2, clock:4)를 A 뒤에 삽입

결정적 ID 정렬 규칙 적용
→ 모든 복제본이 A → X → Y → B로 수렴

Yjs는 실제로 무엇을 저장할까

Yjs는 텍스트와 배열을 다루는 list CRDT입니다. 삽입된 항목에 (clientID, clock) 형태의 고유 ID를 부여하고, 앞뒤 항목의 ID를 origin, originRight로 기억합니다. 여러 사용자가 같은 위치에 동시에 삽입해도 모든 피어가 동일한 순서를 선택할 수 있습니다. 연속 타이핑은 문자마다 JavaScript 객체를 만드는 대신 하나의 Item으로 묶어 저장합니다. Yjs 내부 구조 문서

삭제도 단순한 배열 삭제와 다릅니다. 다른 복제본이 아직 그 요소를 참조할 수 있으므로 삭제 여부를 별도로 전파합니다. Yjs는 항목에 삭제 플래그를 표시하고 delete set을 동기화하며, garbage collection이 활성화된 경우 삭제된 콘텐츠를 더 가벼운 구조로 바꿀 수 있습니다.

CRDT의 장점은 서버가 잠시 없거나 여러 복제본이 오래 분기돼도 병합할 수 있다는 점입니다. 오프라인 우선, P2P, local-first 제품과 잘 맞습니다. 그러나 “conflict-free”는 사용자 관점의 충돌이 사라진다는 뜻이 아닙니다. 수렴 규칙이 자료구조에 미리 들어 있다는 뜻에 가깝습니다. 두 사용자가 같은 문장을 서로 다른 의도로 고치면 결과가 결정적으로 합쳐져도 사람에게 자연스럽지 않을 수 있습니다.

또한 고유 ID, 삭제 정보, 인과성 메타데이터, 스키마 진화, 권한 검사, undo/redo를 함께 설계해야 합니다. 직접 CRDT를 구현하기보다 Yjs나 Automerge처럼 검증된 구현을 먼저 검토해야 하는 이유입니다.

Figma — CRDT에서 영감을 얻고 중앙 서버를 활용하다

텍스트 편집기와 디자인 툴은 충돌의 모양이 다릅니다. 문서는 글자 위치가 중요하지만, 디자인 파일은 객체의 위치·색상·이름 같은 속성으로 구성됩니다.

Figma가 2019년에 공개한 멀티플레이어 아키텍처는 문서를 다음과 같은 2단계 맵으로 설명합니다.

Map<ObjectID, Map<Property, Value>>

rectangle-42:
  x: 120
  y: 80
  fill: "#C7FF4A"

한 사용자가 x를 바꾸고 다른 사용자가 fill을 바꾸면 두 변경은 충돌하지 않습니다. 같은 객체의 같은 속성을 동시에 바꿨을 때만 서버에 마지막으로 도착한 값이 이깁니다. CRDT의 LWW register와 비슷하지만 타임스탬프 대신 중앙 서버가 순서를 정합니다.

Figma는 이를 “true CRDT”라고 부르지 않습니다. 서버라는 중앙 권위자가 있으므로 완전한 탈중앙 합의를 위해 필요한 메모리와 성능 비용을 줄였다고 설명합니다. 클라이언트는 승인되지 않은 자신의 변경을 우선 표시해 즉각적인 조작감을 만들고, 서버 응답으로 최종 상태를 확정합니다. 객체 순서에는 0과 1 사이 값을 계속 나눠 쓰는 fractional indexing을 사용합니다. Figma 멀티플레이어 공식 설명

여기서 배울 점은 “CRDT를 썼는가”가 아닙니다. 데이터 모델을 속성 단위로 나누자 대부분의 편집이 애초에 충돌하지 않게 됐다는 점입니다.

Notion — 공개된 것은 블록과 트랜잭션 파이프라인이다

Notion을 CRDT 사례로 소개하는 글이 많지만, 공개된 공식 자료만으로는 현재 텍스트 병합 알고리즘을 OT 또는 CRDT라고 단정할 수 없습니다. Notion이 2021년에 공개한 내용은 블록 데이터 모델과 변경 저장·전파 경로입니다.

Notion에서는 텍스트, 이미지, 데이터베이스 행, 페이지까지 모두 블록입니다. 각 블록은 ID, type, properties, 자식 블록 ID 배열인 content, 권한 상속에 사용하는 parent를 가집니다.

사용자 동작은 하나 이상의 레코드를 바꾸는 operation이 되고, 관련 operation들은 transaction으로 묶입니다. 클라이언트는 먼저 로컬 상태에 transaction을 적용한 뒤 IndexedDB나 SQLite의 TransactionQueue에 저장합니다. 서버의 /saveTransactions는 변경 전후 상태를 만들고 권한과 데이터 정합성을 검사한 다음 transaction 전체를 커밋하거나 거부합니다.

키 입력·블록 이동
  → 로컬 operation 적용
  → TransactionQueue
  → /saveTransactions
  → 권한·정합성 검증
  → 데이터베이스 커밋
  → MessageStore 알림
  → 다른 클라이언트가 최신 record 동기화

변경이 저장되면 MessageStore가 WebSocket으로 구독 중인 클라이언트에 새 레코드 버전을 알립니다. 클라이언트는 로컬 버전이 오래됐다면 syncRecordValues로 최신 데이터를 가져옵니다. Notion 블록 데이터 모델과 동기화 과정

이 자료에서 확실히 말할 수 있는 것은 Notion이 블록·레코드·트랜잭션을 중심으로 로컬 선반영과 서버 검증을 구성했다는 사실입니다. 동일한 문단을 두 사용자가 동시에 편집할 때 어떤 문자 병합 알고리즘을 쓰는지는 이 글에 공개돼 있지 않습니다. “Notion은 CRDT다” 또는 “Notion은 단순 LWW다”라고 단정하는 순간 공개 자료보다 한 발 더 나가게 됩니다.

OT와 CRDT 중 무엇을 선택해야 할까

정답은 알고리즘의 인기보다 제품의 요구사항에서 나옵니다.

중앙 서버가 항상 있고 긴 텍스트를 정교하게 합쳐야 한다

서버가 전역 순서를 정하는 OT 또는 서버 기반 rebase 모델이 잘 맞습니다. 연산 종류를 제한하고 검증된 구현을 사용하면 메타데이터가 작고 텍스트 편집 의도를 세밀하게 보존할 수 있습니다.

오프라인에서 오래 편집하거나 P2P 병합이 필요하다

CRDT가 강합니다. 네트워크가 끊긴 동안 각 복제본이 독립적으로 바뀌어도 나중에 병합할 수 있습니다. 대신 메타데이터, 스키마 변경, 권한과 히스토리 정책까지 함께 설계해야 합니다.

문서가 텍스트보다 객체와 블록에 가깝다

OT와 CRDT를 고르기 전에 충돌 단위를 다시 정의해야 합니다. 객체의 속성 단위 LWW, 블록 단위 transaction, 서버 검증만으로 문제의 상당 부분이 사라질 수 있습니다. Figma와 Notion의 공개 아키텍처가 보여주는 방향입니다.

실제로는 다음 질문이 결정에 더 도움이 됩니다.

서버가 최종 순서를 정해도 되는가?
사용자는 오프라인에서 얼마나 오래 편집하는가?
충돌의 최소 단위는 문자, 리치텍스트 범위, 속성, 블록 중 무엇인가?
사용자의 의도를 어디까지 보존해야 하는가?
undo/redo는 다른 사람의 변경을 덮어써도 되는가?
권한이 다른 사용자의 변경을 어느 단계에서 거부할 것인가?
삭제된 요소와 히스토리를 언제 정리할 것인가?

결국 중요한 것은 충돌의 단위다

OT는 충돌한 연산을 현재 문맥에 맞게 변환합니다. CRDT는 복제본이 독립적으로 변경돼도 수렴하도록 데이터에 정체성과 병합 규칙을 넣습니다. Figma는 중앙 서버가 있다는 전제 아래 객체 속성 단위로 문제를 단순화했고, Notion은 블록과 트랜잭션을 중심으로 변경을 저장하고 전파하는 구조를 공개했습니다.

네 접근법의 공통점은 로컬에서 먼저 반영하고 나중에 확정한다는 것입니다. 사용자가 느끼는 “실시간”은 네트워크가 무한히 빠르기 때문이 아니라, 시스템이 불확실한 상태를 잠시 품고도 나중에 정합성을 회복할 수 있기 때문에 만들어집니다.

좋은 협업 시스템은 충돌을 없애는 시스템이 아니라, 제품의 데이터 모델에 맞는 크기로 충돌을 제한하는 시스템이다.