cola: 실시간 협업 편집을 위한 텍스트 CRDT 기술

 (nomad.foo)
1P by GN⁺ | ★ favorite | 댓글 1개
  • cola는 Rust로 작성된 실시간 협업 편집용 텍스트 CRDT로, 중앙 조정자 없이 여러 피어가 동시에 수정한 문서를 같은 상태로 수렴시키는 데 초점을 둠
  • 문서 위치를 단순 오프셋이 아닌 ReplicaId.n 형태의 Anchor로 고정해, 동시 편집으로 위치 의미가 흔들리는 문제를 피함
  • 삽입 충돌은 Lamport timestamp와 ReplicaId 정렬로 일관되게 처리하고, 삭제는 실제 제거 대신 tombstone과 version vector로 통합 조건을 관리함
  • 구현 측면에서는 EditRun 기반 RLE와 Vec 인덱스로 표현한 G-tree를 사용해 Rust의 안전한 소유권 모델 안에서 로그 시간 탐색·삽입을 노림
  • 벤치마크에서 cola는 diamond-types, automerge, yrs와 비교됐고, upstream에서는 diamond-types보다 1.4~2배 빠르며 downstream에서도 매우 빠른 성능을 보임

cola가 다루는 협업 편집 문제

  • cola는 Rust로 작성된 텍스트 CRDT이며, 실시간 협업 편집에서 중앙 권한 없이 여러 복제본이 같은 상태로 수렴하도록 설계됨
  • 네트워크 계층에는 모든 편집이 결국 모든 피어에게 도달한다는 최소한의 가정만 둠
    • 편집은 여러 번 전송될 수 있음
    • 편집은 임의 순서로 도착할 수 있음
    • 모든 피어가 결국 모든 편집을 받아야 함
  • 목표는 모든 편집을 받은 뒤 문서 상태가 같아지는 것뿐 아니라, 사용자 관점에서도 결과 문서가 납득 가능한 형태가 되는 것임

오프셋 대신 Anchor로 위치를 고정

  • insert "abc" at offset 8 같은 오프셋 기반 편집은 다른 피어가 앞쪽 영역을 동시에 수정하면 의미가 달라져 복제본이 갈라질 수 있음
  • cola는 문서 위치를 문자 콘텐츠나 오프셋이 아니라 안정적인 식별자로 참조함
    • 각 피어는 삽입하는 문자에 증가하는 번호를 붙임
    • 피어는 고유 식별자인 ReplicaId를 가짐
    • ReplicaId.n 쌍이 문자의 고유 위치 식별자인 Anchor가 됨
  • n 값은 로컬 카운터 증가로 유일성을 보장할 수 있지만, 중앙 서버 없이 ReplicaId의 전역 유일성을 보장하기는 어려움
    • cola는 UUID처럼 충돌 확률이 무시할 수 있을 정도로 큰 랜덤 정수를 사용하는 방식을 전제로 함
  • 삽입은 하나의 Anchor로 위치를 지정하고, 삭제는 시작과 끝 두 Anchor로 범위를 지정함

삽입 충돌을 같은 순서로 정렬

  • 같은 Anchor에 여러 삽입이 들어오면 cola는 Lamport timestamp로 순서를 정함
  • Lamport clock은 다음 규칙으로 갱신됨
    • 로컬에서 텍스트를 삽입할 때 clock을 1 증가시킴
    • 원격 삽입을 받을 때 max(current, remote_timestamp) + 1로 설정함
  • 어떤 삽입 A가 삽입 B를 이미 통합한 환경에서 만들어졌다면, A의 Lamport timestamp는 B보다 커짐
  • 충돌 삽입은 Lamport timestamp 내림차순으로 정렬됨
  • Anchor와 Lamport timestamp가 모두 같은 동시 삽입에는 사용자 관점에서 더 올바른 순서가 없으므로, ReplicaId 오름차순으로 정렬해 피어 간 일관성을 맞춤

삭제는 tombstone과 version vector로 처리

  • 삭제는 시작·끝 오프셋을 Anchor로 바꾼 뒤 다른 피어에게 전파함
  • 두 피어가 같은 영역을 동시에 삭제하면, undo를 고려하지 않는 한 한 번 삭제한 것과 같은 결과가 됨
    • cola는 현재 삭제 undo를 지원하지 않음
  • 삭제 처리에는 세 가지 난점이 있음
    • 삭제된 텍스트를 완전히 제거하면, 아직 도착하지 않은 편집의 Anchor가 그 영역 안에 있을 수 있음
    • 원격 삭제를 너무 일찍 통합하면, 삭제를 만든 피어가 봤던 콘텐츠와 수신 피어의 콘텐츠가 달라 복제본이 갈라질 수 있음
    • 삭제 범위 안에서도 삭제를 만든 피어가 아직 보지 못했던 문자는 삭제하면 안 됨
  • 첫 번째 문제는 tombstone으로 해결함
    • 삭제된 문자는 문서에 남아 있지만 삭제된 것으로 표시됨
    • 이 방식은 메모리 사용량을 늘림
  • 나머지 문제는 삭제 메시지에 version vector를 포함해 해결함
    • 키는 ReplicaId, 값은 삭제를 만든 피어가 당시 본 마지막 문자 timestamp임
    • 수신 피어의 version vector가 삭제 메시지의 version vector 이상일 때까지 삭제 통합을 기다림
    • 삭제 version vector의 timestamp보다 큰 문자는 삭제 대상에서 건너뜀
  • cola에서는 version vector를 version map이라고 부름

Replica와 텍스트 버퍼의 분리

  • 각 피어의 로컬 문서 상태는 cola에서 Replica로 표현됨
  • cola의 CRDT 알고리듬은 실제 문자열 내용을 알 필요가 없음
    • API 함수가 문자열을 인자로 받지 않음
    • cola는 문서 콘텐츠가 아니라 숫자 블록만 다룸
  • 이 설계는 CRDT 메커니즘과 실제 텍스트 버퍼 구현을 분리함

RLE와 EditRun으로 메타데이터를 줄임

  • 문자마다 메타데이터를 붙이면 성능 좋은 구현을 만들기 어려우므로, cola는 연속된 timestamp를 가진 블록을 run-length encoding으로 묶음
  • 예를 들어 Wikipedia의 Manhattan Project 페이지 전체를 붙여넣으면 107,000개 블록이 아니라 하나의 블록으로 표현될 수 있음
  • 커서를 옮기거나 삭제하지 않고 문장을 한 글자씩 입력하는 경우도 키 입력마다 블록을 만들지 않고 하나의 run으로 표현 가능함
  • cola에서 이런 연속 블록은 EditRun이라고 부름
    • 한 번 깨진 EditRun은 문서 생애 동안 고정되며 더 이상 확장되지 않음
    • 아직 깨지지 않은 run은 active 상태임
  • 기존 EditRun 중간에 텍스트를 삽입하면 run을 둘로 나누고 그 사이에 새 텍스트를 넣음
  • 텍스트를 삭제하면 해당 부분을 run에서 분리하고 tombstone으로 표시함
    • 삭제된 run도 같은 방식으로 RLE할 수 있어 tombstone의 메모리 부담을 줄임

링크드 리스트에서 B-tree로

  • 로컬 편집의 upstream 경로는 오프셋 기반 편집을 다른 피어에게 보낼 수 있는 편집으로 바꾸는 과정임
    • 삽입과 삭제 모두 오프셋을 포함하는 run을 찾아 Anchor를 만들어야 함
    • 필요하면 run을 삽입에서는 최대 2개, 삭제에서는 최대 3개로 나눔
  • 링크드 리스트에서는 run 분할은 O(1)이지만, 오프셋을 포함하는 run을 찾으려면 처음부터 스캔해야 해 선형 시간이 걸림
  • 현재 active run과 그 오프셋을 캐시하면 같은 위치에서 반복 편집할 때 빠르지만, 최악의 경우는 여전히 선형임
  • cola는 로그 시간 최악 성능을 위해 B-tree 구조를 고려함
    • run은 B-tree의 leaf로 표현됨
    • inode는 자식들과 자식 길이 합을 저장함
    • tombstone run은 길이 0으로 기여함
    • root의 길이는 문서 전체 길이와 같음
  • B-tree는 탐색과 삽입을 O(log n)에 수행할 수 있어 로컬 편집을 로그 시간으로 처리할 수 있음
  • 다만 원격 편집에서 Anchor -> run 변환을 효율적으로 하려면, Anchor가 들어 있는 leaf를 찾아야 함

G-tree: Vec 인덱스로 표현한 B-tree

  • 일반 B-tree leaf에 대한 포인터만으로는 top-down 삽입 과정에서 leaf까지 어떻게 내려갈지 알기 어려움
  • bottom-up 연산에는 각 노드의 부모 포인터가 필요하며, Rust의 안전한 소유권 모델에서는 Rc<RefCell<_>> 같은 구조가 필요해 느리고 복잡해질 수 있음
  • cola는 모든 노드를 Vec 같은 동적 배열에 저장하고, 노드 간 참조를 포인터가 아니라 인덱스로 표현함
    • 벡터가 모든 노드를 소유함
    • 각 노드는 부모 인덱스를 저장할 수 있음
    • unsafe 코드 없이 양방향 탐색이 가능함
  • 이 구조는 노드 인덱스가 변하지 않는다는 가정에 의존함
    • 새 노드는 벡터 끝에 append됨
    • cola는 run을 제거하지 않고 tombstone으로 표시하므로 인덱스 무효화 문제가 생기지 않음
  • 이런 grow-only tree-in-a-vector 구조를 cola에서는 G-tree라고 부름
  • G-tree Rust 코드는 B-tree의 부모-자식 구조를 유지하면서 메모리 표현만 바꾼 형태임

G-tree가 만드는 성능 특성

  • G-tree는 B-tree처럼 top-down 탐색과 삽입을 로그 시간에 수행함
  • leaf의 벡터 인덱스인 LeafIdx를 안정적인 leaf 식별자로 사용할 수 있음
  • 현재 active run을 포인터가 아니라 LeafIdx로 캐시할 수 있음
    • 같은 커서 위치에서 반복 편집하면 active run을 확장하고 조상 길이만 root까지 갱신함
    • 트리 순회와 새 할당 없이 몇 번의 정수 비교와 2~4번의 정수 덧셈으로 처리될 수 있음
  • cola의 G-tree는 branching factor 32를 사용하며, inode 평균 점유율은 약 20개 자식임
    • 4레벨만으로 보통 약 160k개의 서로 다른 EditRun을 저장할 수 있음
    • automerge-paper 편집 trace 처리 후 cola의 G-tree는 약 15k개의 EditRun을 가짐
    • 해당 trace는 260k개 편집을 포함하며 며칠에 걸쳐 기록됨
  • G-tree는 노드가 이미 선형 메모리에 저장되어 있어 직렬화와 역직렬화도 단순함

Anchor를 LeafIdx로 변환

  • 원격 편집 downstream 경로는 insert 2.3..7 at 1.2, delete between 3.4 and 2.2 같은 Anchor 기반 편집을 로컬 문서 오프셋 편집으로 바꾸는 과정임
  • G-tree는 위아래로 탐색할 수 있으므로, 어떤 Anchor가 들어 있는 run의 LeafIdx를 알면 해당 오프셋을 계산할 수 있음
  • 핵심은 Anchor -> LeafIdx 변환임
  • 단순한 설계는 보조 G-tree나 B-tree를 두고, leaf에 ReplicaId, temporal range, main G-tree의 LeafIdx를 저장하는 방식임
    • leaf는 ReplicaId와 temporal range 순서로 완전 정렬됨
    • Anchor를 기준으로 트리를 내려가 원하는 LeafIdx를 찾을 수 있음
    • 검색과 삽입은 모두 O(log n)임
  • 실제 cola 소스 코드는 이 보조 G-tree 방식을 그대로 쓰지는 않음
    • 실제 구현은 검색과 삽입이 O(log f)임
    • f는 Anchor가 들어 있는 EditRun이 시간 동안 쪼개진 fragment 수임
    • f는 항상 n 이하이고 보통 훨씬 작음

현재 완성도와 남은 작업

  • cola의 설계는 수렴, 의도 보존, 성능을 목표로 하는 기반을 갖춤
  • 프로덕션 준비를 위해서는 undo/redo 지원과 몇 가지 추가 작업이 남아 있음

Rust CRDT 벤치마크

  • cola는 Rust 기반 CRDT 3개와 비교됨
  • 벤치마크는 실제 character-by-character 편집 trace를 처리하는 시간을 측정함
    • Rust 벤치마킹 라이브러리 criterion을 사용함
    • upstream과 downstream 양방향을 모두 측정함
    • 벤치마크 코드는 crdt-benches에 있음
  • 그래프는 cola 성능의 100배를 기준선으로 두며, cola보다 100배 이상 느린 측정값은 표시하지 않음
  • 실행 환경은 2018 MacBook Pro, 2.2GHz 6-Core Intel Core i7임
    • 다른 머신에서는 수치가 달라질 수 있지만 상대 성능은 비슷할 것으로 봄

벤치마크 결과

  • upstream 방향에서는 yrs와 automerge가 기준선을 넘음
  • upstream에서 cola는 diamond-types보다 1.4~2배 빠름
  • downstream 방향에서는 diamond-types가 모든 trace에서 crash해 측정값을 얻지 못함
    • 라이브러리를 잘못 사용한 것이라면 결과를 업데이트하겠다는 단서가 붙음
  • downstream에서 cola는 이전보다 약 2배 느림
    • 원격 편집 통합이 일반적으로 로컬 편집 생성보다 비싸기 때문에 예상된 결과임
  • cola는 양방향 모두에서 빠른 rope 라이브러리들과 비슷하거나 더 빠른 수준으로 동작하며, 현재 가장 빠른 텍스트 CRDT 구현으로 평가됨

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • G-tree는 여전히 부모 포인터가 추가된 B-tree라고 봄
    배열에 저장된다는 건 표현 방식의 문제일 뿐 구조를 근본적으로 바꾸지는 않음
    여전히 포인터를 저장하지만, 바이트 단위가 아니라 노드 크기 단위이고 주소 공간 시작이 아니라 첫 배열 원소 기준의 상대 위치일 뿐임
    예를 들어 명시적 참조 없이 배열에 저장된 완전 이진 트리도, 인덱스 x의 자식이 2x + 1과 2x + 2에 있는 암시적 표현일 뿐 여전히 이진 트리라고 부름

    • 그래도 표현 방식을 이야기하는 건 유용함
      특히 절대 참조보다 상대적이고 자체 관리되는 참조 쪽으로 유도하는 언어에서는 더 그렇다
      흥미롭게 본 트리 표현 방식 중 하나는 노드를 깊이 우선 탐색 순서로 평평한 배열에 저장하는 것임
      읽기 전용이고 독자가 어차피 깊이 우선으로 순회하려는 경우 꽤 효율적일 수 있음
      S-expression과 HTML이 떠오름

  • API에서 놓친 게 아니라면, 이건 굵게·기울임 같은 서식 범위를 지원하지 않는 듯함
    내가 알기로 리치 텍스트 CRDT 알고리즘에서는 아직 Peritext가 최첨단임 https://www.inkandswitch.com/peritext/
    이 프로젝트가 Peritext 알고리즘의 리치 텍스트 기능까지 가져가면 좋겠음

    • CRDT 분야를 조금 관심 있게 보는 입장에서, 더 범용적인 구조화 데이터 CRDT를 만들 수 있을지 늘 궁금했음
      사용자가 의미적으로 유효한 상태를 설명하는 모델이나 스키마를 정의하는 방식임
      예를 들어 JSON을 그냥 병합하면 문법적으로는 유효하지만 의미상 말이 안 되는 상태가 될 수 있음
      Peritext 알고리즘이 굵게·기울임·밑줄은 더해지는 연산이고 하이라이트 색상은 그렇지 않다는 걸 아는 것처럼, 사용자가 스키마에서 state: notStarted와 completionDate: 2023-09-04가 양립할 수 없다고 선언할 수 있으면 좋겠다는 생각임
    • 질문: 글에서는 Cola가 알 수 없는 자료형에 대해 충돌 없는 편집만 다룬다고 하며, 사실상 문자 스트림과 위치만 다룬다고 함
      그렇다면 HTML처럼 서식 자체를 텍스트 안에 표현할 수 있지 않을까?
      다른 리치 텍스트 표현을 잘 아는 건 아니라서 확신은 없음
      추가로, 위에 링크된 Peritext 문서를 보니 바로 이런 RTF 고유의 어려움을 다루고 있었고 꽤 흥미롭게 읽었음

  • Automerge나 Y.js/Yrs와 비교했을 때 성능이나 기능 차이가 있나?

    • 글의 “세 번째 부분”이 “Rust로 구현된 다른 CRDT 3개인 diamond-types, automerge, yrs와 cola를 벤치마크했다”로 시작함
      이 cola 라이브러리는 연산 속도 면에서는 꽤 유리해 보임
      메모리 사용량도 궁금함

  • Ian Piumarta의 같은 이름 작업과 헷갈리면 안 됨
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • 또는 한때 MergeTree(LSM)의 대안으로 여겨졌지만 지금은 쓰이지 않는 Cache Oblivious Lookahead Arrays도 있음 https://github.com/giannitedesco/cola
    • coda.io라는 Notion 클론 스타일 앱도 있음

  • 잘 만든 작업이지만 공정한 벤치마크처럼 보이지는 않음
    연산을 계산해 저장하지도 않고 실제 텍스트도 저장하지 않음
    여기에 델타 업데이트를 지원하는 텍스트 CRDT를 만들려면 사용자가 별도 구조에 OpID => Text를 저장해야 하는데, 이 비용이 싸지 않음

  • slotmap 크레이트(https://docs.rs/slotmap/latest/slotmap/)를 쓰면 인덱스 이동이나 “인덱스”가 다른 값을 가리킬 걱정 없이 삭제를 지원할 수 있음
    slotmap에서는 이를 키라고 부르고, 키에 버전 번호도 함께 들어 있음

    • CRDT 맥락에서도 동작할까?
      순서 정하기가 어렵고 버전은 로컬에서만 의미가 있을 수 있어서 궁금함

  • Etherpad와 Word가 감당하지 못했던 프로젝트에 이걸 한번 써볼까 함

  • 연결된 모든 클라이언트가 모든 편집을 받는다고 가정한다면, 오프셋과 삽입/삭제/치환 명령 앞에 기존 텍스트 상태의 예상 해시를 넣으면 안 되나?
    그러면 편집이 적절한 상태에만 적용된다는 걸 거의 보장할 수 있고, 이후 변경은 “적용될 것으로 기대되는 데이터 상태의 해시”를 키로 삼는 딕셔너리에 누적할 수 있음
    물론 같은 데이터에서 해시 연산을 중복 계산해야 해서 비용은 크겠지만, 이해하고 구현하기는 매우 단순함

    • 그 방식이면 비동기 편집은 절대 적용되지 않음
      내가 문서에 로컬 편집을 하고, 당신이 원격 편집을 하면, 당신의 “예상 상태” 해시는 앞으로도 내 문서 상태와 절대 맞지 않음
      나는 이미 로컬 변경을 해버렸기 때문임
      CRDT가 수렴을 보장하려면 모든 클라이언트가 모든 편집을 받아야 하는 건 맞지만, 업데이트를 특정 순서로 적용하지 않아도 된다는 성질이 현실의 분산 사용 사례에서는 중요함

  • 브라우저에서 폼 공동 편집을 쉽게 켜는 방법이 있는지 궁금함
    두 사람이 같은 페이지나 폼을 열면, 상대가 현재 어떤 입력 필드를 편집 중인지 보이고, 텍스트 입력 필드에는 텍스트 CRDT가 쓰이는 식이면 좋겠음
    Yjs로 비슷하게 구현해 보려 했지만 꽤 어려웠고 잘 동작하지 않았음

    • Yjs가 왜 안 맞았는지 궁금함
      그 용도에는 딱 좋아 보이는데 말임
답변달기