▲

협업 텍스트 편집: CRDT나 OT 없이 구현하기

 (mattweidner.com)
4P by GN⁺ 1일전 | ★ favorite | 댓글 1개
  • 협업 텍스트 편집 문제를 해결하는 새로운 접근법 소개, 복잡한 알고리듬 없이도 실현 가능함
  • 기존 CRDT 및 OT 방식의 복잡성과 제약을 피하고, 간단한 ID 기반 삽입 방식 사용
  • 이 방식은 서버가 '무엇을 어디에 삽입할지'를 직접 지정받아 처리하므로 유연성이 높음
  • 낙관적 로컬 업데이트를 위해 서버 리컨실리에이션 전략을 활용해 상태 동기화 문제 해결
  • 확장성과 이해 용이성을 갖춘 이 방식은 기존 협업 앱 개발에 직접 구현 가능한 대안을 제시함

Collaborative Text Editing without CRDTs or OT

문제 제기

  • 텍스트 협업 편집은 매우 어려운 기능으로, 특히 동시 편집 시 텍스트 인덱스가 뒤틀리는 문제(index rebasing) 가 발생함
  • 기존 방식인 CRDT(충돌 없는 복제 데이터 타입) 과 OT(운영 변환) 는 각각 복잡한 수학적 모델에 기반함
    • CRDT: 각 문자를 ID로 추적하고 트리 기반 정렬
    • OT: 다른 사용자 입력을 반영해 인덱스를 동적으로 재조정
  • 두 방식 모두 라이브러리 의존성이 높고 개발자 맞춤형 커스터마이징이 어려움

새로운 접근 방식

핵심 아이디어

  • 각 문자를 고유한 ID(UUID)로 표시하고, 클라이언트는 서버에 “어떤 ID 뒤에 어떤 문자를 삽입하라”는 명령을 보냄
  • 예: "insert ' the' after f1bdb70a" → f1bdb70a는 삽입 대상 문자 ID
  • 서버는 이를 그대로 해석하여 삽입함으로써 충돌을 회피함

삭제 처리

  • 문자 삭제 시에도 해당 ID는 내부 목록에 남겨 두고 isDeleted 플래그로 처리
  • 실 사용자 텍스트에선 보이지 않지만 참조는 유지되어 향후 조작이 가능

클라이언트 처리와 낙관적 업데이트

  • 사용자는 입력 직후 결과를 볼 수 있어야 하므로, 서버 응답 전 로컬에 반영 (낙관적 업데이트)
  • 서버 리컨실리에이션 전략을 사용하여:
    1. 로컬 미확정 연산을 모두 되돌림
    2. 서버 연산을 적용
    3. 다시 로컬 연산을 재적용하여 최종 동기화 상태 확보

기존 방식과의 차이

  • CRDT는 자동 ID 정렬 알고리듬을 내포하나, 본 방식은 명시적 삽입 위치만 서버에 전달
  • 결과적으로 더 단순하고 명확한 동작 방식 확보

동시 삽입 처리

  • 예: “My name is”에서 두 사용자가 동시에 “ Charlie”와 “ Dave”를 같은 위치에 삽입
    • 서버 수신 순서에 따라 “My name is Dave Charlie”가 됨
  • 이는 자연스러운 처리로 간주되며, 일부 CRDT 방식처럼 문자 단위로 섞이는(interleaving) 현상 없음

유연한 연산 지원

  • 기본적인 insert/delete 외에도 다양한 연산 지원 가능:
    • insert-before
    • 특정 조건 하 삽입 (“color”가 존재할 경우만 “u” 추가)
    • drag & drop 시 위치 재조정 등
  • 이러한 유연성은 정해진 수학적 특성에 얽매이지 않음

리치 텍스트(서식 있는 텍스트) 지원

  • 범위를 ID 기반으로 정의하여 서식 적용 가능 (“ID X부터 ID Y까지 bold” 등)
  • ProseMirror 같은 에디터와 연동 시 간단한 방식으로 충돌 해결 가능
  • 기본 구조는 그대로 유지하면서 리치 텍스트 기능 추가 가능

분산 버전 (Decentralized)

  • 중앙 서버 없이도 Lamport 타임스탬프 기반으로 연산 순서를 정하면 동일 방식으로 작동 가능
  • 이 경우 RGA, Peritext, Fugue 등의 CRDT와 유사한 결과를 보임
  • 트리나 수학적 증명 없이도 CRDT 수준의 일관성 확보 가능

보조 라이브러리: Articulated

  • Array<{ id, isDeleted }> 형태를 효율적으로 다루기 위한 라이브러리
  • UUID 대신 { bunchId, counter } 구조 사용하여 메모리 최적화
  • B+Tree 기반 구조로 빠른 ID 탐색 및 삽입 지원
  • 지속 가능한(persistent) 데이터 구조로 서버 리컨실리에이션과 궁합이 좋음

결론

  • 이 방식은 CRDT/OT에 비해 이해하기 쉽고 직접 구현이 가능함
  • 다양한 편집 기능과 권한, 제약, 서식 등을 자유롭게 적용할 수 있어 현실적인 협업 에디터 구현에 유리함
  • Articulated 라이브러리는 이러한 접근을 실용화하는 데 도움이 되는 도구로 제공됨
▲
GN⁺ 1일전  [-]
Hacker News 의견

  • 이 알고리듬이 꽤 멋져보임. 각 문자에 전역 고유 ID(예: UUID)를 붙여서 언제든지 일관적으로 참조 가능하게 만드는 방식 설명, 클라이언트는 특정 ID 뒤에 문자를 삽입한다고 서버에 알리고, 서버는 해당 위치에 삽입 처리, 삭제는 화면에서만 가리고 내부적으로는 위치 참조 목적을 위해 계속 보존, 이 방식이 텍스트 편집 뿐 아니라 게임 월드 동기화 등 다른 분야에도 활용 가능성 상상

    • 이건 본질적으로 단순화된 CRDT인듯 함, 타이브레이킹 및 중앙 서버 사용 방식이 Google Wave 시절 구조와 유사함
    • 설명된 내용이 CRDT 아니냐는 의문 제기
    • 사실 그렇게 새로울 것 없다는 반응, 분산 시스템을 직렬화할 때 중앙 프로세스를 이용하는 건 전통적인 방식이며, 네트워크 분할(CAP 등)이나 단일 실패점 등의 이슈는 여전히 존재, 성능 논의가 기사에 있는지 궁금하다는 첨언
    • ctrl+a, ctrl+x, ctrl+v와 같은 대량 선택/복사/붙여넣기 동작에 행운을 빈다는 농담

  • CRDT와의 차별점을 중앙 서버가 순서 정렬 등 동기화 역할을 하며 실제 데이터 구조에 미리 정해진 순서를 부여하지 않아도 되는 점에서 찾을 수 있다는 관점 공유, 클라이언트와 서버 간 통신만 존재하므로 서버가 클라이언트의 로컬 연산을 모두 처리한 후 원격 업데이트를 보낼 수 있음

  • dict/map 같은 다른 데이터 구조나 임의 타입의 배열에 대한 얘기가 없는 것이 놀랍다는 의견, 실제로 앱에서는 순수한 텍스트 협업 편집보다 다양한 협업 데이터 구조가 더 많이 필요, 데이터 검증이나 부분 로딩, 상위 레벨 연산 등 흥미로운 예시가 있으나 Yjs 등에서 해당 기능이 없는 이유가 CRDT 자체 때문보다는 이런 기능 자체가 원래 구현이 어려워서라 판단

    • 여러 데이터 구조 얘기에 깊이 동의, "원자적" 객체 배열을 만들 때 객체의 프로퍼티 변경이 불가능하면 문자열 대신 타입만 바꾸면 되고, 객체 내부 변경은 트리 탐색/저장 문제라 약간 더 복잡할 뿐임을 언급, 또한 헬퍼 라이브러리 사용자 쪽에서 자체적인 '의미 모델' 로직을 훅처럼 연결해서 잘못된 상태(예: 하나의 todo가 isDone: true이면서 state: inProgress인 경우)를 방지할 수 있기를 기대, 링크된 글에서 언급된 리치 텍스트 포매팅과 비슷한 맥락

    • CRDT는 충돌 발생 시 일관된 방법으로 한 쪽을 선택하여 병합하는데, 문제는 그 결과 데이터 유실이나 유효하지 않은 데이터가 나올 수 있다는 점, git merge 충돌을 무조건 한쪽만 골라서 해결한다고 생각하면 대부분 잘못된 결과나 컴파일 오류가 나오는 상황, 자동화된 해결만으로는 데이터의 원본성과 의미가 제대로 보전되지 않을 수 있다는 지적, 그래서 CRDT가 아직 널리 쓰이지 못하는 이유라고 생각

  • 이런 접근 방식에 대한 설명 글 재밌게 읽었고, 본인도 예전부터 같은 방식을 써봤으며 학계에서 거의 언급되지 않는 점 신기, 본인은 이걸 decentralize된 환경에서 CRDT로 구현해서 결합/불변/교환 가능성 등 속성을 유지할 수 있었다고 말함

    • CRDT의 대안으로 개발했다면 실제로 얻은 이득이 무엇이었는지 궁금하다는 질문

  • 중앙 서버가 없을 때만 복잡한 CRDT/OT가 정말로 필요한 것이냐는 본문 메시지 요약 시도

    • 중앙 서버가 없어도, 분산된 방식에서 연산의 전체 순서를 합의 및 적용할 방법이 있으면 CRDT/OT의 복잡성을 피할 수 있다는 의견, 링크된 글 소개, 물론 이 또한 CRDT의 한 형태이긴 하나(일반화 형태), undo/replay 구현이 만만치 않으며 전통적 CRDT/OT 구조가 더 복잡하다고 느껴질 때 대안으로 고려할 만 함 강조

    • OT(Operational Transformation)는 중앙 서버를 필요로 한다는 언급

  • 본질적으로도 CRDT에 해당, 다만 문서에 적용되는 연산 순서를 중앙 서버가 정해준다는 점, 구글 Docs와 Zoho Writer도 OT+중앙 서버 방식임, 제시된 접근법은 CRDT 스타일이나 사실상 중앙 서버 기반 서비스에서는 더 실용적임을 인정

  • Automerge 같은 CRDT와의 주요 차이가 서버 조정 방식에 있다는 의견, Automerge는 시퀀스 번호와 에이전트 ID 정의된 순서로 동시 삽입을 정렬하지만 본 접근법은 서버가 도착하는 순서대로 처리, 참조한 기사 속 설명 인용: “여러 fancy한 알고리듬이 필요 없으니 단순화”, 많은 서비스는 어차피 중앙 서버를 쓸 테니 이 방식이 실용적으로 보이긴 하지만 서버 조정 시 로컬 편집 취소/재연이 필요하기 때문에 실제로 얼마나 더 단순한지는 확신하기 힘듦

    • “rewind/replay” 도 fancy한 접근이라고 느끼며, Persistent B+Tree도 그렇게 단순하진 않다는 코멘트

    • Automerge도 결국 내부적으로는 전체 순서를 만들 수 있지만 실제로는 전통적인 CRDT(RGA 등) 방식으로 텍스트 연산 처리, undo/replay가 간단치 않아서 그렇다는 설명

  • 최적화되지 않은 CRDT라는 느낌, max set size=1로 셋팅하고 막 쓰는 수준 아니냐는 농담

    • 오히려 이렇게 복잡성과정을 줄이는 건 실제 발생하는 동작에 가까워서 단순해서 끌린다는 피드백, 최적화되어 있지 않아도 매력이 있음

  • 서버 리콘실리이션을 쓴다면 클라이언트 쪽에서 병합 문제가 어려워질 위험, 서버 업데이트가 순차적으로 오면서 에디터 UX를 어떻게 부드럽게 유지할 수 있는지 질문, 예를 들어 삽입 요청이 실패하면 재시도 하는지, 그사이에 다른 업데이트가 왔다면 어떻게 해야 하는지 등, 제안된 방안으론 편집 내역을 되감기 후 재적용 또는 대기하며 큐 플러시, 프론트엔드 관점에선 명시되지 않은 UI/UX 엣지케이스가 상당수 존재할 것 같고 이런 이유로 CRDT가 오히려 단순할 수 있음, 특히 네트워크 연결이 불안정한 환경(예: 지하철)에서 사용자 경험이 어떤지 궁금

    • ProseMirror와 최신 CodeMirror는 문서 변경을 step 단위로 관리하고 각 단계별로 위치 정보(position map)를 갱신하여버퍼의 단계를 문서에 적용할 수 있게 데이터 구조화를 한다는 설명, 실제 협업 편집에서 실용적으로 잘 동작함을 강조하며, 참고 자료 링크 공유

  • 누군가 LLM(예: 4b 모델 등)을 활용해 딱히 복잡한 CRDT나 OT를 쓰지 않고도 간단한 케이스 외의 병합 충돌을 해결해보면 어떨까 하는 제안, 에너지 효율은 떨어질 수 있으나 의외로 잘 동작할 수도 있음

    • 예시처럼 "My name is"에 대해 "is" 뒤에 "Charlie"와 "Dave"를 각각 삽입하는 충돌의 경우 LLM이 어떻게 병합할지 의문
답변달기