실시간 협업 편집, 생각보다 훨씬 어렵다

Google Docs는 수백만 명의 사용자를 대상으로 실시간 협업 편집을 처리합니다. 겉보기에는 아무것도 아닌 것처럼 보입니다. 타이핑하면 커서가 움직이고, 함께 편집하는 사람의 변경 내용이 즉시 나타나죠. 하지만 이 단순함은 착시입니다. 내부를 들여다보면 협업 편집은 분산 시스템에서 가장 어려운 문제 중 하나이고, 이를 해결하는 두 가지 주요 접근법인 Operational Transformation(OT)과 CRDT는 직접 만들어 보기 전까지는 드러나지 않는 트레이드오프를 각각 가지고 있습니다.

CRDT(Conflict-free Replicated Data Types)의 장점은 꽤 매력적으로 들립니다. 충돌 없이 자동으로 병합되는 자료구조, 중앙 서버가 필요 없는 구조, 그리고 수학적으로 보장되는 최종 일관성 말이죠. 하지만 여러 팀이 CRDT를 골라 협업 에디터를 만든 뒤 알게 된 현실은 훨씬 지저분합니다. 이론은 아름답습니다. 엔지니어링은 잔인하죠.

문제: 동시 편집

근본적인 문제는 이렇습니다. 두 사용자가 같은 문서를 동시에 편집하고, 그 사이에 네트워크 지연이 있습니다. 사용자 A가 5번 위치에 'Hello'를 삽입합니다. 아직 A의 편집을 보지 못한 사용자 B는 5번 위치의 글자를 삭제합니다. 최종 문서는 어떻게 되어야 할까요?

이 질문에는 모호함이 있습니다. B의 삭제는 A가 삽입하기 전 5번 위치의 글자에 적용되어야 할까요, 아니면 삽입한 후의 5번 위치에 적용되어야 할까요? 전자라면 원래 글자가 지워지고 'Hello'가 남습니다. 후자라면 'Hello'의 'H'가 지워집니다. 두 해석 모두 합리적입니다. 시스템은 하나를 골라야 하고, 모든 클라이언트가 같은 결과로 수렴하도록 보장해야 합니다. 결과가 갈라지면 두 사용자가 서로 다른 문서를 보게 되는데, 이는 용서할 수 없는 실패 모드입니다.

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation(OT)

오래된 방식인 OT(1989년)는 연산끼리 서로 변환하는 방식으로 이 문제를 풉니다. A가 B의 '10번 위치 삭제' 연산을 받으면, A의 시스템은 A가 이미 적용했지만 B는 아직 보지 못한 연산이 무엇인지 확인합니다. 그리고 B의 연산을 그 변경분에 맞게 변환합니다. A가 10번 위치에 5글자를 삽입했다면, B의 삭제는 이제 15번 위치에 적용되어야 합니다(원래 대상 글자가 오른쪽으로 밀렸으니까요).

이 방식은 실제로 잘 작동하며, Google Docs도 이를 사용합니다. 문제는 변환 함수입니다. 삽입과 삭제만 있는 텍스트 에디터에서도 모든 연산 쌍이 서로 어떻게 변환되는지 정의해야 하고, 연산 종류가 두 개뿐이어도 변환 케이스는 네 가지나 됩니다. 서식, 표, 이미지, 목록, 댓글을 더하면 경우의 수가 조합적으로 폭발합니다. 각 케이스는 모두 정확해야 하며, 사소한 버그 하나가 문서 불일치를 일으키는데 이는 재현과 디버깅이 거의 불가능합니다.

OT는 전통적으로 연산의 전체 순서를 정하기 위해 중앙 서버도 필요로 합니다. 서버가 없으면 동시 연산이 클라이언트마다 다른 순서로 변환되어 서로 다른 결과를 낳을 수 있습니다. Google은 Docs를 위해 중앙 서버를 감당할 수 있지만, P2P 애플리케이션에서는 OT를 쉽게 쓸 수 없습니다.

CRDT: 이론적 약속

CRDT는 근본적으로 다른 접근을 취합니다. 연산을 변환하는 대신, 어떤 병합 순서로 처리하든 같은 결과가 나오는 자료구조를 사용합니다. 이는 수학적 보장입니다. 자료구조가 유효한 CRDT라면 수렴은 자동으로 보장됩니다. 변환 함수도, 중앙 서버도, 순서 의존성도 필요 없습니다.

텍스트 편집에서 핵심 CRDT 변종은 RGA(Replicated Growable Array)와 비슷한 시퀀스 CRDT들입니다. 편집이 일어날 때마다 위치가 바뀌는 대신, 각 글자에 전역적으로 정렬된 고유 식별자를 부여합니다. 삽입은 기존 식별자 사이에 새 식별자를 만들고, 삭제는 식별자를 톰스톤(tombstone) 처리합니다. 완전히 제거하지는 않습니다. 이에 대해서는 나중에 자세히 다루겠습니다.

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

CRDT: 실제 현실

충돌 없음, 탈중앙화, 수학적으로 보장된 수렴이라는 CRDT의 약속은 실제로 존재합니다. 하지만 엔지니어링 과제는 상당히 큽니다.

톰스톤이 쌓입니다. CRDT에서 글자를 삭제해도 자료구조에서 실제로 제거할 수 없습니다. 아직 그 삭제를 보지 못한 다른 레플리카가 자신의 편집 위치를 올바르게 잡으려면 그 ID가 필요하기 때문입니다. 그래서 삭제된 글자는 보이지 않지만 여전히 존재하는 톰스톤으로 표시됩니다. 많이 편집된 문서에는 편집 이력에서 나온 톰스톤이 수천 개씩 쌓입니다. 1000글자짜리 문서에 톰스톤이 5만 개 있을 수도 있습니다. 이는 메모리를 부풀리고 연산을 느리게 만듭니다.

메타데이터 오버헤드가 막대합니다. 글자마다 고유 ID(사용자 식별자 + 논리 타임스탬프), 인접 ID에 대한 포인터, 톰스톤 플래그가 필요합니다. 글자당 메타데이터는 50~100바이트에 이를 수 있습니다. 100KB 문서라면 CRDT 표현은 5~10MB가 될 수도 있습니다. 이는 동기화에서 중요한데, 전체 CRDT 상태를 네트워크로 보내는 비용이 크기 때문입니다.

이력이 길어질수록 성능이 떨어집니다. 시퀀스 CRDT의 연산은 O(1)이 아닙니다. 글자를 삽입하려면 ID로 정렬된 시퀀스에서 올바른 위치를 찾아야 하고, 이는 톰스톤을 포함한 전체 ID 수에 따라 달라집니다. 편집 이력이 긴 문서에서는 이 속도 저하가 실제로 느껴질 정도가 됩니다.

의도 보존이 어렵습니다. CRDT는 수렴, 즉 모든 레플리카가 같은 상태에 도달함을 보장합니다. 하지만 그것이 올바른 상태인지는 보장하지 않습니다. 두 사용자가 같은 단어를 동시에 편집하면 CRDT는 그들의 글자를 결정적으로 뒤섞습니다. 결과는 수렴하지만 말이 안 될 수도 있습니다. OT는 한 사용자의 편집을 온전히 유지하고 다른 쪽 편집을 그 주변에 적용하도록 설계할 수 있습니다. CRDT는 기계적으로 병합합니다.

Yjs와 실용적인 중간 지점

Yjs는 JavaScript에서 가장 인기 있는 CRDT 라이브러리이며, 많은 웹 애플리케이션의 협업 기능을 뒷받침합니다. 잘 설계되어 있고, 압축된 바이너리 인코딩으로 메타데이터 오버헤드를 줄이고, 모든 클라이언트가 온라인일 때는 톰스톤 가비지 컬렉션도 동작하는 등 이론적인 CRDT 문제 상당수를 실용적인 최적화로 다룹니다.

하지만 Yjs가 마법은 아닙니다. Yjs를 도입한 팀들은 CRDT 라이브러리가 수렴 문제는 해결해도 협업 문제는 해결하지 못한다는 것을 알게 됩니다. 여전히 다음이 필요합니다. 피어 탐색을 위한 시그널링 서버, 오프라인 변경을 위한 영속성 계층, 고수준 연산의 충돌 해결(두 사용자가 같은 섹션의 구조를 바꾸면 어떻게 할 것인가?), 프레즌스 추적(커서, 선택 영역), 다른 사용자의 편집을 존중하는 실행 취소/다시 실행, 그리고 권한 관리입니다.

Yjs로 협업 에디터를 만든 뒤 CRDT 방식이 필요 없는 복잡성을 더한다고 결론 내린 팀도 있습니다. 대부분의 애플리케이션처럼 중앙 서버가 있다면 OT나, 충돌 감지를 곁들인 마지막 쓰기 우선(last-write-wins) 같은 더 단순한 방법이 더 실용적일 수 있습니다. CRDT는 오프라인 우선 애플리케이션, 로컬 우선 소프트웨어, 중앙 권한을 가정할 수 없는 시스템처럼 진정한 P2P 시나리오에서 빛을 발합니다.

대부분의 애플리케이션이 해야 할 일

협업 편집을 애플리케이션에 추가하려는 경우를 위한 실용적인 판단 기준은 다음과 같습니다.

• 중앙 서버가 있고 문서가 작다면: OT를 쓰세요. Google의 방식이 잘 작동합니다. Node.js에서는 ShareDB 같은 라이브러리가 OT를 구현해 두었습니다. 중앙 서버는 순서 정하기, 영속성, 충돌 해결, 권한 관리를 모두 단순하게 만들어 줍니다.
• 오프라인 지원이나 P2P가 필요하다면: CRDT(Yjs 또는 Automerge)를 쓰세요. 진정한 오프라인 편집과 P2P 동기화를 올바르게 처리할 수 있는 방식은 CRDT뿐입니다. 탈중앙화의 대가로 메타데이터 오버헤드와 톰스톤 누적을 감수하세요.
• 협업자들이 같은 섹션을 동시에 거의 편집하지 않는다면: 둘 중 어느 것도 필요 없을 수 있습니다. 섹션당 편집자 한 명만 허용하는 단순 잠금이나, 좋은 충돌 UI를 갖춘 마지막 쓰기 우선 방식이면 OT나 CRDT의 복잡성 없이도 실제 협업 패턴 상당수를 감당할 수 있습니다.
• Google Docs 경쟁 제품을 만들고 있다면: 분산 시스템 엔지니어 팀과 여러 해의 개발 기간이 필요합니다. 주말 프로젝트가 아닙니다. 협업 편집의 겉보기 단순함 뒤에는 엄청난 복잡성이 숨어 있습니다.

솔직한 평가

협업 편집은 난이도가 직관적이지 않은 문제 중 하나입니다. 행복한 경로, 즉 두 사용자가 겹치지 않는 편집을 하는 경우는 거의 모든 방식으로 잘 작동합니다. 어려운 경우들, 즉 같은 영역에 대한 동시 편집, 나중에 동기화되는 오프라인 편집, 표나 중첩 목록, 임베디드 객체 같은 복잡한 문서 구조는 OT와 CRDT 사이의 트레이드오프를 깊이 이해해야 합니다.

어느 한쪽이 확실히 낫지는 않습니다. OT는 서버가 있으면 단순하고, 서버가 없으면 어렵습니다. CRDT는 서버 없이 동작하지만 메타데이터 오버헤드와 톰스톤 누적을 감당해야 합니다. 두 방식 모두 핵심 알고리즘 이상의 세심한 엔지니어링이 필요하며, 그 엔지니어링(프레즌스, 영속성, 권한, 실행 취소)은 종종 수렴 문제 자체보다 어렵습니다.

업계는 서서히 실용적인 하이브리드로 수렴하고 있습니다. 데이터 모델에는 CRDT를 쓰고(자동 병합 보장), 조정 작업(프레즌스, 권한, 가비지 컬렉션)에는 서버를 씁니다. 이렇게 하면 두 세계의 장점을 얻습니다. 수학적 수렴과 실용적인 인프라입니다. 하지만 두 세계의 복잡성도 함께 떠안게 되며, 그래서 35년간의 연구 끝에도 협업 편집은 여전히 어려운 문제로 남아 있습니다.