- 중앙 서버 기반 협업 앱에서 텍스트를 배열 인덱스로 편집하면 동시 편집 때 위치가 밀리므로, 각 문자에 전역 고유 ID를 붙이고 “특정 ID 뒤에 삽입”하는 방식으로 서버 상태를 갱신함
- 실제 서비스에서 쓰이는 CRDT와 OT는 강력하지만, 총순서 알고리듬이나 연산 변환 규칙이 복잡해 앱 요구에 맞춰 내부 동작을 바꾸기 어려움
- 제안 방식은 클라이언트와 서버가
Array<{ id: ID; char?: string; isDeleted: boolean }> 형태의 ID 목록을 유지하고, 삭제된 문자도 tombstone처럼 남겨 이후 삽입 위치 참조가 깨지지 않게 함
- 낙관적 로컬 업데이트는 서버 조정(server reconciliation) 으로 처리하며, 원격 연산을 받을 때 대기 중인 로컬 연산을 되돌린 뒤 원격 연산과 미승인 로컬 연산을 순서대로 다시 적용함
- 동시 삽입 순서, 리치 텍스트 포맷, 분산형 변형,
Articulated 라이브러리까지 다루며, 서버가 앱별 의미에 맞춰 삽입·삭제를 넘어선 유연한 연산을 정의할 수 있음
인덱스 기반 편집이 동시 편집에서 깨지는 이유
- 협업 텍스트 편집에서 클라이언트는 사용자가 입력한 연산을 서버로 보내고, 서버는 자신의 권위 있는 상태를 갱신해야 함
- 텍스트를 문자 배열로 보고
index 17에 " the" 삽입 같은 연산을 보내면, 서버 도착 전 다른 사용자의 삽입 때문에 같은 인덱스가 다른 위치를 가리킬 수 있음
- 예를 들어 Alice가 앞쪽에
" gray"를 삽입하면 Bob의 index 17은 더 이상 원래 위치가 아님
- 서버는 Bob의 연산을
index 22로 리베이스해야 함
- 핵심은 클라이언트가 어떤 연산을 서버에 보내고, 서버가 이를 어떻게 해석해야 텍스트를 “명백히 올바른” 방식으로 갱신할 수 있느냐임
- 이 인덱스 리베이스 문제는 Google Docs 같은 실시간 협업 앱뿐 아니라, 리스트 항목을 삽입하는 웹 폼이나 인라인 댓글·편집 기록을 다루는 단일 스레드 로컬 앱에서도 나타날 수 있음
CRDT와 OT가 실무에서 부담스러운 지점
- 기존 해법은 크게 CRDT와 OT로 나뉨
- CRDT는 각 문자에 불변 ID 또는 “position”을 부여하고, 특수한 트리 순회 같은 수학적 총순서로 ID를 정렬함
- OT는 동시 편집을 고려해 연산 자체를 변환하며, 예시에서는
index 17 삽입을 index 22 삽입으로 바꿈
- 두 접근은 이미 실제 서비스에서 사용됨
- Google Docs는 OT를 사용함
- Yjs CRDT 라이브러리는 여러 앱에서 활용됨
- 부담은 개념적 복잡성에서 생김
- 텍스트 편집 CRDT의 총순서는 학술 논문에 정의된 미묘한 알고리듬인 경우가 많음
- OT 알고리듬은 대수적 “변환 속성”을 만족해야 하며, 경우의 수가 제곱으로 늘고 형식 검증 없이는 결함이 잦음
- 복잡한 알고리듬은 구현도 복잡하게 만들고, 보통 전문가가 만든 라이브러리를 네트워크 블랙박스처럼 사용하게 됨
- 라이브러리가 예상하지 못한 기능이 필요할 때 단일체적 구조가 발목을 잡음
- 큰 문서의 필요한 부분만 메모리에 올리고 나머지는 디스크에 두기
- 문단별 편집 권한이나 특정 포맷 사용 권한 같은 하위 문서 권한을 서버에서 강제하기
- Google Docs 스타일의 제안 변경을 본문 안이나 옆에 표시하기
- Replicache 같은 키-값 저장소와 동기화하기 쉬운 표현으로 텍스트 저장하기
- 삽입·삭제 외에 텍스트 이동, 문서 트리 조작, 문단 분할·병합 같은 연산 지원하기
문자 ID와 “insert after” 방식
- 기본 아이디어는 배열 인덱스 대신 각 문자에 전역 고유 ID를 붙이는 것임
- 핵심 자료구조는
Array<{ id: ID; char: string }> 형태임
- 클라이언트는
index 17에 삽입 대신 f1bdb70a 뒤에 " the" 삽입 같은 연산을 서버에 보냄
- 서버는 대상 ID를 찾아 그 바로 뒤에 새 문자를 넣음
- 새 문자들의 ID도 클라이언트가 함께 지정해야 함
- 예:
f1bdb70a 뒤에 " the"를 ids [...]로 삽입
- 클라이언트가 ID를 생성하면 서버 응답을 받기 전에 후속
insert after 연산에서 새 ID를 참조할 수 있음
- 삭제된 문자를 완전히 제거하면 삽입 위치를 잃을 수 있음
- Bob이
26085702 뒤에 삽입하려는 동안 다른 사용자가 26085702 문자를 삭제하면, 서버는 어디에 삽입해야 할지 알 수 없음
- 서버는 삭제된 ID도 내부 목록에 유지해야 함
- 보정된 상태 표현은 다음과 같음
Array<{ id: ID; char?: string; isDeleted: boolean }>
- 사용자에게 보이는 텍스트는 삭제되지 않은 항목만 이어 붙여 만들 수 있음
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')
삽입과 삭제 처리
- 문자 입력 시 클라이언트와 서버의 동작은 단순함
- 클라이언트는 삽입 지점 바로 앞 문자의 ID인
before를 찾음
- 새 문자에 대해 UUID 같은 전역 고유 ID
id를 생성함
- 서버에
before 뒤에 char를 id로 삽입하라는 연산을 보냄
- 서버는 삭제된 항목까지 포함해
before를 찾고, 그 항목 바로 뒤에 { id, char, isDeleted: false }를 삽입함
- 문자 삭제도 ID 기반으로 처리함
- 클라이언트는 삭제할 문자의
id를 찾음
- 서버에 해당 ID의 항목을 삭제하라는 연산을 보냄
- 서버는 해당 항목을 찾아 아직 삭제되지 않았다면
entry.isDeleted = true로 설정함
- 이 방식은 CRDT나 OT 논문을 따라가지 않고도 서버로 보내는 편집 연산의 위치 문제를 직접 해결함
- 단순 배열 구현은 문자마다 UUID를 저장해야 하므로 비효율적일 수 있으며, 최적화는
Articulated에서 다룸
낙관적 업데이트와 서버 조정
- Google Docs 스타일의 협업 편집에서는 사용자가 서버 응답을 기다리지 않고 자신의 입력 결과를 즉시 봐야 함
- 어려운 지점은 클라이언트에 아직 서버가 승인하지 않은 대기 중인 로컬 연산이 있는 상태에서, 그와 동시인 원격 연산을 서버로부터 받을 때임
- 이 경우 CRDT가 꼭 필요한 것은 아니며, 서버 조정(server reconciliation) 으로 처리할 수 있음
- 대기 중인 모든 로컬 연산을 되돌려 클라이언트 상태를 이전 서버 상태 관점으로 되감음
- 원격 연산을 적용해 클라이언트를 서버 상태에 맞춤
- 아직 승인되지 않은 로컬 연산을 다시 적용함
- 더 단순한 전략으로는 대기 중인 로컬 연산이 있을 때 원격 연산 처리를 금지하는 Wait for Ack가 있음
- Bob의 클라이언트는 자신의 메시지가 처리된 서버 상태를 받을 때까지 첫 서버 메시지를 무시할 수 있음
- Bob이 계속 입력하거나 네트워크 지연이 크면 지연이 무한히 길어질 수 있어 서버 조정보다 덜 실시간적임
CRDT와 달라지는 부분
- 제안 방식은 문자마다 ID를 붙이고
isDeleted 표시를 사용한다는 점에서 CRDT와 일부 특징을 공유함
- 차이는 순서를 다루는 방식에 있음
- 이 방식에서는 클라이언트가
X를 Y 뒤에 삽입하라고 서버에 말하고, 서버는 그대로 하거나 개발자가 정의한 다른 방식으로 처리함
- 텍스트 편집 CRDT에서는 ID가 복잡한 알고리듬에 의해 정렬됨
- 여러 텍스트 편집 CRDT 사이의 차이를 만드는 핵심도 이 ID 정렬 알고리듬이며, 이 접근은 그 부분을 피함
동시 삽입이 만드는 결과
- 같은 위치에 여러 사용자가 동시에 입력하면 서버가 연산을 받은 순서의 역순으로 결과가 배치됨
- 예를 들어 텍스트가
"My name is"이고 Charlie가 " Charlie", Dave가 " Dave"를 동시에 입력한다고 가정함
- Charlie의 연산이 먼저 도착하면 서버는
"My name is Charlie"를 만듦
- Dave의 연산도 같은
is의 s ID 뒤에 삽입하므로 결과는 "My name is Dave Charlie"가 됨
- 같은 대상 ID 뒤에 대한
insert after 연산은 동시성이 없더라도 서버 수신 순서의 역순이 됨
- 그래도 왼쪽에서 오른쪽으로 입력한 단어들은 문자 단위로 뒤섞이지 않음
- Dave가 각 문자를 별도 연산으로 보내도
a는 D 뒤, v는 a 뒤에 삽입됨
- 서버 상태는
"My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie"처럼 변함
- 오른쪽에서 왼쪽으로 입력하는 경우에는 Charlie와 Dave의 연산이 교차 순서로 서버에 도착하면 결과 텍스트도 교차될 수 있음
- 실제로는 두 사용자가 동시에 온라인이고 서로의 진행 중 편집을 무시할 때 발생할 수 있음
서버가 더 유연한 연산을 정의할 수 있음
- 서버 조정을 사용하면 서버는 클라이언트 연산을 사실상 원하는 방식으로 처리할 수 있고, 클라이언트는 결국 같은 상태에 도달함
- 이는 엄격한 대수 규칙을 만족하는 연산만 허용하는 CRDT·OT와 대비됨
- 같은 위치의 동시 삽입에 대해 서버는 여러 방식으로 대응할 수 있음
- 해당 연산을 무시해 no-op으로 처리
- ID는 내부 목록에 추가하되 즉시 삭제 표시해, 이후 Dave의 연산이 이전 ID를 참조할 수 있게 함
- 텍스트를 삽입하되 두 단어에 검토용 특수 포맷을 적용
- Dave의 편집을 본문 옆에 표시되는 “제안”으로 변환
- LLM에 텍스트를 어떻게 고칠지 물어봄
- 클라이언트는 사용자 의도를 더 잘 담는 연산을 보낼 수도 있음
insert before는 문단 위에 제목을 만들 때 이전 문단 끝의 동시 삽입 중간에 제목이 들어가는 것을 피하는 데 쓸 수 있음
fix typo 연산은 ID X를 가진 color의 o 뒤에 u를 삽입하되, 주변 단어가 여전히 color일 때만 같은 조건을 담을 수 있음
- 서버는 삽입 위치 자체가 서버 도착 후 달라지는 연산도 정의할 수 있음
- 같은 위치의 동시 삽입을 알파벳순으로 재정렬할 수 있음
- 드래그앤드롭용
move 연산을 추가하면, 이동된 텍스트 내부의 insert after를 원래 위치가 아니라 이동된 텍스트 내부에 적용할 수 있음
리치 텍스트 포맷 처리
- 리치 텍스트에서는 굵게, 글자 크기, 하이퍼링크 같은 인라인 포맷을 다룸
- 범위 포맷도 인덱스 대신 문자 ID로 표현할 수 있음
- 예:
ID X부터 ID Y까지 bold 적용
ID X inclusive부터 ID Y exclusive까지로 정의하면 범위 끝의 동시 삽입도 굵게 처리할 수 있음
- ProseMirror 같은 리치 텍스트 편집기와 함께 쓰면 서버는 ID X와 Y의 현재 배열 인덱스를 찾아, 로컬 ProseMirror 상태에 해당 범위를 굵게 처리하라고 지시할 수 있음
- ProseMirror는 이후 해당 범위 안에 삽입되는 텍스트에도 굵게를 유지할 수 있음
- 단 서버가
bold set to false 같은 삽입 연산에 따라 다르게 처리할 수도 있음
- 협업 리치 텍스트의 의미론을 이해하려면 Peritext essay가 참고 자료가 됨
분산형 변형과 CRDT와의 연결
- 지금까지는 중앙 서버가 연산의 총순서를 서버 수신 순서로 정하고, 권위 있는 상태를 갱신한다고 가정함
- 중앙 서버가 없거나 서버가 선택적인 앱에서는 연산에 대한 최종적 총순서를 분산 방식으로 부여할 수 있음
- 이 경우 문자별 ID와
insert after 연산은 분산형 “비서버” 조정에서도 동작함
- 기술적으로는 이 결과가 텍스트 편집 CRDT가 됨
- 분산형이고, 최종 일관성을 갖는 협업 텍스트 편집 알고리듬이기 때문임
- 어떤 순서 방식을 쓰느냐에 따라 기존 CRDT와 연결됨
- Lamport timestamp로 연산을 정렬하면 결과 목록 순서는 RGA / Causal Trees와 동등함
- Lamport timestamp와 포맷 연산을 함께 쓰면 동작은 Peritext와 상당히 비슷함
- 깊이 우선 위상 정렬을 사용하면 결과 목록 순서는 Fugue와 동등함
- 이 동등성 주장에 대한 자세한 증명은 작성되어 있지 않음
Articulated: 구현 보조 라이브러리
- 실제 구현에서는 텍스트 자체를 ProseMirror 상태 같은 다른 곳에 저장하고, 이 접근에는 다음 형태의 ID 목록만 필요할 수 있음
Array<{ id: ID; isDeleted: boolean }>
- 이 목록에서 자주 필요한 작업은 네 가지임
- ID와 현재 배열 인덱스 사이 변환
- 지정한 ID 뒤에 새 ID 삽입
- ID를 삭제 표시
- 저장을 위해 상태를 직렬화하고 복원
- 단순 배열은 이 작업들에 적합하지 않음
- 작업 1~3은 선형 시간이 걸림
- 문자마다 객체와 UUID를 저장하므로 메모리와 저장 공간이 큼
- Articulated는 이 배열과 같은 기능을 제공하는 작은 npm 라이브러리임
- 핵심 자료구조
IdList는 인기 있는 텍스트 편집 CRDT 라이브러리와 비슷한 최적화를 사용함
- ID는
{ bunchId, counter } 형태이며, bunchId는 여러 ID가 공유할 수 있는 UUID임
- 왼쪽에서 오른쪽으로 삽입하는 일반적인 경우처럼 같은 bunch의 ID가 나란히 있으면 메모리와 직렬화 상태에서 하나의 객체로 저장함
- 핵심 자료구조는 배열이 아니라 B+Tree라서 메서드 호출 시간이
log 또는 log^2임
IdList는 영속 자료구조(persistent data structure) 이기도 함
- 클라이언트는 서버에서 마지막으로 받은 상태와 낙관적 상태를 싸게 함께 저장할 수 있음
- 원격 연산을 받을 때 서버의 마지막 상태로 롤백하기 쉬움
- 추가 자료로 docs, 초기 demos, 300 SLOC 미만의 단순 구현인 IdListSimple이 제공됨
IdListSimple은 최적화와 영속성을 생략했지만 기능적으로 동일하며, fuzz tests로 검증됨