이동 가능한 트리 CRDT와 Loro의 구현

 (loro.dev)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 협업 소프트웨어에서 계층 구조를 동시에 편집하면 중복 노드, 순환, 삭제된 조상의 하위 노드 이동 같은 트리 충돌이 생기며, Loro는 이를 이동 가능한 트리 CRDT로 구현함
  • Martin Kleppmann 등의 방식은 생성·삭제·이동을 Move t p m c로 통합하고, 삭제를 TRASH 노드로의 이동으로 처리해 동시 하위 노드 이동을 보존함
  • 전역 순서는 Lamport Timestamp와 Peer ID로 만들며, 원격 연산이 기존 순서 중간에 들어오면 undo-do-redo로 순환을 피함
  • Loro는 형제 노드 정렬을 위해 Fractional Index를 결합하고, 같은 위치 동시 삽입으로 인덱스가 겹치면 PeerID, jitter, 인덱스 재설정으로 처리함
  • 벤치마크에서 Loro Movable Tree는 1000개 노드 생성 후 무작위 이동 10000회를 28ms에 수행해 실시간 협업과 과거 버전 checkout에 충분한 성능을 보임

협업 트리에서 생기는 충돌

  • 분산 시스템과 협업 소프트웨어에서 계층 관계를 관리할 때 이동을 삭제와 삽입의 조합으로 모델링하면, 사용자 기대와 충돌 해결 방식이 어긋나기 쉬움
  • 같은 노드가 여러 replica에서 서로 다른 부모로 동시에 이동하면 한 노드가 두 번 삭제되고 두 부모 아래에 다시 생성되어 같은 내용을 가진 중복 노드가 생길 수 있음
  • 이동 가능한 트리의 기본 연산은 생성, 삭제, 이동 세 가지임
  • 동기화 시 주로 문제가 되는 상황은 다음과 같음
    • 같은 노드가 삭제되는 동시에 이동됨
    • 같은 노드가 서로 다른 부모 아래로 이동됨
    • 서로 다른 노드 이동이 합쳐져 순환이 생김
    • 조상 노드가 삭제되는 동안 하위 노드가 이동됨

충돌 유형별 처리 방식

  • 같은 노드의 삭제와 이동이 충돌하면 분산 시스템의 timestamp나 애플리케이션 요구에 따라 한 연산을 적용하고 다른 연산을 무시할 수 있음
  • 같은 노드가 서로 다른 부모 아래로 이동되는 경우에는 애플리케이션에 따라 선택지가 달라짐
    • 노드를 삭제한 뒤 서로 다른 부모 아래에 복사본을 만들고 이후 독립적으로 취급함
    • 한 노드가 두 부모를 가리키게 할 수 있지만, 이는 트리 구조를 깨뜨려 일반적으로 수용하기 어려움
    • 모든 연산을 정렬한 뒤 순서대로 적용하면 모든 peer에서 동일한 결과를 만들 수 있음
  • 서로 다른 노드 이동이 순환을 만들면 이동 가능한 트리의 충돌 해결이 특히 복잡해짐
    • Matthew Weidner는 오류 처리, “time-out” 영역 렌더링, 서버 기반 거부, 위상 정렬 후 순환 생성 연산 건너뛰기, 렌더링 시 특정 edge 숨기기, 이전 부모로 되돌리기 등을 정리함
  • 조상 노드 삭제 중 하위 노드가 이동되는 상황도 놓치기 쉬움
    • 조상의 모든 하위 노드를 즉시 삭제하면 사용자는 자신의 데이터가 손실됐다고 오해할 수 있음

Dropbox와 Figma의 접근

  • Dropbox는 처음에 파일 이동을 원래 위치 삭제 후 새 위치 생성의 두 단계로 처리했음
    • 삭제와 생성 사이에 정전이나 시스템 크래시가 발생하면 데이터 손실 위험이 있었음
    • 현재는 여러 사람이 같은 파일을 동시에 이동하고 저장하려 할 때 충돌을 감지하고, 보통 원본 파일 한 버전을 저장한 뒤 한 사용자의 변경에 대해 “conflicted copy”를 만듦
  • Figma는 트리 구조를 협업 시스템에서 가장 복잡한 부분으로 보고 각 요소에 parent 속성을 둠
    • 중앙 서버가 여러 사용자 업데이트를 감시하고, 어떤 연산이 순환을 만들 수 있으면 해당 연산을 거부함
    • 네트워크 지연 때문에 서버가 거부하기 전에 일시적으로 순환이 생길 수 있음
    • 이 경우 Figma는 순환에 포함된 요소를 임시로 숨기고, 서버가 연산을 공식적으로 거부할 때까지 상태를 보존함
    • 관련 설명은 Figma의 multiplayer technology 글에서 볼 수 있음

이동 가능한 트리 CRDT의 두 접근

  • 중앙집중식 해법 대신 CRDT로 협업 트리 구조를 다룰 수 있음
  • 초기 CRDT 기반 트리 알고리듬은 구현이 어렵고 저장 오버헤드가 컸지만, 최적화와 개선을 거치며 일부 프로덕션 환경에 적합한 트리 동기화 알고리듬이 등장함
  • 대표적인 CRDT 기반 접근은 두 가지임

Kleppmann 방식: 모든 연산을 Move로 통합

  • A highly-available move operation for replicated trees는 트리의 생성·삭제·이동을 하나의 move 연산으로 통합함
  • move 연산은 Move t p m c 네 값으로 정의됨
    • t: Lamport timestamp 같은 고유하고 정렬 가능한 timestamp
    • p: 부모 노드 ID
    • m: 노드와 연결된 metadata
    • c: 자식 노드 ID
  • 트리에 c가 없으면 부모 p 아래에 자식 c를 만드는 생성 연산이 됨
  • 이미 c가 있으면 기존 부모에서 새 부모 p로 옮기는 이동 연산이 됨
  • 삭제는 지정된 TRASH 노드로 이동하는 방식으로 처리함
    • TRASH의 모든 하위 노드는 삭제된 것으로 간주됨
    • 하지만 메모리에는 남겨 동시 편집이 해당 노드를 다른 노드로 이동할 수 있게 함
    • 조상 삭제와 하위 노드 이동이 동시에 발생하는 상황을 처리하기 위한 장치임

순서화와 unsafe operation

  • 삭제도 move 연산으로 정의되므로 “같은 노드 삭제와 이동”은 두 move 연산의 충돌로 바뀜
  • 남는 핵심 문제는 두 가지임
    • 같은 노드를 서로 다른 부모 아래로 이동
    • 서로 다른 노드를 이동해 순환 생성
  • Lamport timestamp와 Peer ID로 모든 연산을 선형 순서로 정렬하면, 같은 노드의 동시 이동도 순서가 있는 두 연산으로 표현됨
  • 트리를 move 연산만으로 모델링하면 동시 편집의 예외적 상황은 순환 생성으로 줄어듦
  • 순환을 만드는 연산은 unsafe operation으로 취급됨
    • 알고리듬은 timestamp 순으로 모든 move 연산을 정렬함
    • 각 연산 적용 전에 순환을 감지함
    • 순환을 만들면 해당 unsafe operation을 무시해 올바른 트리 구조를 유지함

Lamport Timestamp와 원격 연산 적용

  • Lamport Timestamp는 분산 시스템 이벤트의 인과 순서를 판단할 수 있게 함
    • 각 peer는 0에서 시작하는 counter를 가짐
    • 로컬 이벤트가 생기면 counter를 1 증가시키고 그 값을 timestamp로 사용함
    • peer A가 B에게 메시지를 보낼 때 timestamp를 첨부함
    • B는 자신의 논리 시계와 받은 timestamp를 비교해 더 큰 값으로 갱신함
  • 전역 정렬은 먼저 Lamport Timestamp를 비교하고, 값이 같으면 peer의 고유 ID를 tie-breaker로 사용함
  • 원격 업데이트가 기존 정렬된 연산열의 중간에 들어오면 undo-do-redo가 필요함
    • 최근 연산을 되돌림
    • 새 연산을 삽입해 적용함
    • 되돌린 연산을 다시 적용함
  • move 연산을 빠르게 되돌리기 위해 각 move 적용 전에 대상 노드의 old parent를 캐시함
  • unsafe operation은 효과를 무시하더라도 기록은 유지해야 함
    • 연산의 안전성은 동적으로 결정됨
    • 나중에 순환을 유발하던 다른 노드가 먼저 삭제되는 업데이트를 받으면 이전에 unsafe였던 연산이 safe가 될 수 있음
    • undo 과정에서 마지막으로 효과가 있었던 연산의 대상 부모를 찾기 위해 ineffective 표시가 필요함

undo-do-redo 예시

  • 새 연산이 로컬에 없는 연산에 의존하면 중간 버전 업데이트가 아직 빠진 상태이므로, 임시 캐시한 뒤 누락 업데이트를 받은 후 적용해야 함
  • 새 opId가 기존 모든 연산보다 크면 바로 적용 가능함
    • safe이면 대상 노드의 현재 부모를 old parent로 기록하고 move를 적용함
    • unsafe이면 ineffective로 표시하고 효과를 무시함
  • 새 opId가 기존 순서 중간에 들어가면 이후 연산을 하나씩 꺼내 되돌리고, 새 연산을 적용한 뒤 되돌린 연산을 순서대로 다시 적용함
  • 예시 흐름에서는 Peer1이 로컬에서 C를 B 아래로 옮긴 뒤, Peer0이 B를 C 아래로 옮긴 연산을 받음
    • Lamport timestamp 순서에서 0:3이 1:3보다 앞서므로 1:3을 먼저 undo해 C를 old parent A로 되돌림
    • 이후 0:3으로 B를 C 아래로 이동함
    • 다시 1:3을 redo해 C를 B 아래로 옮기려 하지만 순환이 감지되어 적용되지 않음
    • 트리 상태는 바뀌지 않고 undo-do-redo 과정이 완료됨

Evan Wallace 방식: 과거 부모 추적

  • Evan Wallace의 CRDT: Mutable Tree Hierarchy는 각 노드가 모든 과거 부모 노드를 추적하게 함
  • 각 기록된 부모에는 counter가 붙음
    • 새 부모의 count 값은 해당 노드의 모든 과거 부모 count보다 1 큼
    • 가장 높은 count를 가진 부모가 현재 부모가 됨
  • 동기화 시 부모 기록도 함께 동기화됨
  • 순환이 발생하면 휴리스틱 알고리듬이 순환을 일으킨 노드를 가장 가까운 과거 부모 중 순환을 만들지 않고 root에 연결된 부모로 다시 붙임
  • 이 과정을 순환 노드가 모두 트리에 다시 붙을 때까지 반복해 replica 간 트리 구조를 동기화함
  • 이 방식은 비싼 undo-do-redo 절차가 필요 없지만, 원격 move를 받을 때마다 모든 노드가 root에 연결됐는지 확인하고 순환 노드를 다시 붙여야 하므로 노드가 많을 때 성능이 나빠질 수 있음
  • 성능 비교용 benchmark가 별도로 만들어짐

Loro의 Movable Tree 구현

  • Loro는 Martin Kleppmann 등의 A highly-available move operation for replicated trees 알고리듬을 구현함
  • 이 알고리듬은 대부분의 실제 시나리오에서 높은 성능을 냄
  • 핵심인 undo-do-redo 과정은 Loro에서 Eg-walker(Event Graph Walker)가 원격 업데이트를 적용하는 방식과 매우 유사함
  • 이동 가능한 트리만으로는 형제 노드의 순서 문제를 해결하지 못함
    • outline notes나 그래픽 디자인 소프트웨어의 layer 관리에서는 자식 노드 정렬이 필요함
    • 사용자는 노드 순서를 조정하고 이를 다른 협업자나 기기와 동기화해야 함
  • Loro는 Fractional Index 알고리듬을 통합해 이동 가능한 트리의 자식 노드를 정렬 가능하게 함

Fractional Index와 동시 삽입 충돌

  • Fractional Index는 각 객체에 정렬 가능한 값을 부여함
    • 두 객체 사이에 새 삽입이 일어나면 새 객체의 Fractional Index는 왼쪽과 오른쪽 값 사이가 됨
    • 관련 설명은 Figma blog와 Evan blog에서 볼 수 있음
  • 분산 환경에서 여러 peer가 같은 위치에 새 노드를 삽입하면 서로 다른 내용의 노드에 같은 Fractional Index가 할당될 수 있음
  • Loro는 동일한 Fractional Index를 유지하고, 같은 인덱스끼리의 상대 순서는 각 peer의 고유 ID인 PeerID로 결정함
  • 같은 Fractional Index가 양쪽에 있으면 그 사이에 새 Fractional Index를 만들 수 없음
  • Loro는 이 문제를 두 방식으로 처리함
    • 생성되는 Fractional Index에 일정량의 jitter를 추가해 동일 인덱스 발생 가능성을 크게 줄임
    • 예를 들어 0과 1 사이의 값이 원래 0.5라면, random jitter로 0.52712, 0.58312, 0.52834 같은 값이 될 수 있음
    • 0.7@A와 0.7@B 사이에 삽입해야 하는 경우, 0.7과 1 사이에서 새 노드와 0.7@B 노드에 각각 새 Fractional Index를 부여하는 방식으로 재설정할 수 있음

인코딩 크기와 jitter 설정

  • Loro는 drifting-in-space의 Vec<u8> 기반 Fractional Index 구현을 사용함
  • 이 구현은 base 256임
    • 기본값에서 앞으로 또는 뒤로 128개 값을 계속 삽입해야 Fractional Index의 byte 크기가 1 증가함
  • 최악의 저장 오버헤드는 매번 새 값을 번갈아 삽입하는 경우에 발생함
    • 예를 들어 ab에서 a와 b 사이에 c를 넣고, 다시 c와 b 사이에 d, c와 d 사이에 e를 넣는 식임
    • 이런 경우 새 연산 하나가 추가 byte를 필요로 할 수 있지만 매우 드문 상황임
  • Loro는 원래 구현에 간단한 jitter 해법을 추가함
    • Fractional Index에 jitter 값 길이만큼 random bytes를 append함
    • JavaScript에서는 doc.setFractionalIndexJitter(number)에 양수를 넣어 jitter를 활성화할 수 있음
    • 인코딩 크기는 약간 늘어나며, 각 Fractional Index마다 jitter bytes가 추가됨
  • 같은 위치에서 Fractional Index를 만들 때 99% 확률로 충돌을 피하기 위한 jitter와 최대 동시 편집 수 n의 관계는 다음과 같음
jitter 최대 동시 편집 수
1 3
2 37
3 582
  • 정렬된 많은 Fractional Index에는 공통 prefix가 많아짐
  • Loro는 인코딩 시 이전 값과 같은 prefix bit 수와 남은 bytes만 저장하는 prefix 최적화로 전체 인코딩 크기를 줄임

관련 작업과 선택 이유

  • Fractional Index 외에도 트리의 sibling 노드를 순서화할 수 있는 movable list CRDT가 있음
  • Martin Kleppmann의 Moving Elements in List CRDTs는 Loro의 Movable List에 사용됨
  • Fractional Index 해법은 구현이 더 단순함
  • 트리 노드를 모델링할 때 자식 노드에 stable position representation을 제공하지 않으면 전체 트리 구조가 지나치게 복잡해짐
  • Fractional Index에는 interleaving 문제가 있음
    • Figma layer item이나 multi-level bookmark처럼 상대 순서만 필요하고 엄격한 순차 의미론이 필요 없는 경우에는 수용 가능함

벤치마크 결과

  • Loro는 Movable Tree 구현에 대해 무작위 노드 이동, 과거 버전 전환, 매우 깊은 트리 구조의 극단 조건 성능을 벤치마크함
  • 실시간 협업과 원활한 과거 버전 checkout을 지원할 수 있는 수준의 결과가 나옴
  • 테스트 환경은 M2 Max CPU이며, 벤치 코드는 tree.rs에 있음
작업 시간 설정
무작위 이동 10000회 28ms 먼저 1000개 노드 생성
서로 다른 버전으로 1000회 전환 153ms 먼저 1000개 노드 생성 후 1000회 이동
깊이 300 트리에서 서로 다른 버전으로 1000회 전환 701ms 새 노드가 이전 노드의 자식

사용 예와 데모

  • loro-crdt의 LoroTree는 노드 생성, 위치 지정 생성, 이동, root로 이동, 다른 노드 앞뒤로 이동, 부모 내 index 조회, Fractional Index 조회, 노드의 data map 접근을 제공함
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";

let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
  • Loro로 여러 peer 간 데이터 동기화를 시뮬레이션하는 Todo 앱 데모가 만들어짐
    • Movable Tree는 subtask 관계를 표현함
    • Map은 task의 여러 속성을 표현함
    • Text는 task title을 표현함
    • 생성, 이동, 수정, 삭제 외에도 Loro 기반 버전 전환이 구현됨
    • scrollbar를 드래그해 수행된 모든 과거 버전 사이를 전환할 수 있음

정리

  • 이동 가능한 트리 CRDT 구현은 동시 이동, 삭제, 순환, 조상 삭제와 하위 이동의 조합 때문에 어려움
  • Loro는 Kleppmann 등의 고가용 move 연산 알고리듬으로 트리 계층 이동을 구현함
  • 자식 노드 간 이동과 정렬은 drifting-in-space의 Fractional Index 구현을 통합해 처리함
  • 이 조합은 다양한 협업 애플리케이션 시나리오의 요구를 충족할 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 작업/노트용 새 멀티플레이어 편집기 [1]를 만들고 있으며, 텍스트와 아웃라이너 연산을 모두 지원함
    겉으로는 평평한 텍스트 문서처럼 동작하지만, 아웃라이너 기능 때문에 내부적으로는 큰 트리가 됨. 변경 동기화에는 고가용 이동 연산과 비슷한 방식을 씀. 트리를 바꾸는 연산은 insmov 하나뿐이고, 클라이언트가 온라인이면 변경 집합 C를 서버와 동기화함. 서버에 원격 변경이 있으면 마지막 동기화 이후의 모든 변경 R을 전역 선형 순서로 돌려주고, 로컬 변경 C의 insmov를 되돌린 뒤 R과 아직 동기화하지 않은 새 변경을 다시 적용함
    분수 인덱스는 쓰지 않고, insmov 튜플에 부모 P뿐 아니라 이전 형제 guid A도 포함. 모든 트리 연산은 결국 서버가 정한 전역 선형 순서대로 적용되므로, 정렬은 insmov 연산 자체로 처리됨. 대부분은 되돌리기가 필요 없고, 서버에 내가 모르는 insmov 변경이 있는 동시에 내가 새 insmov를 보내는 경우에만 올바른 순서 재생이 필요함. 긴 비행 뒤 와이파이에 다시 연결할 때는 생길 수 있지만, 온라인 상태에서 WebSocket으로 실시간 푸시를 받는 경우에는 덜 흔하고, 텍스트 업데이트 같은 비-insmov 연산에는 필요 없음
    [1] https://thymer.com

    • 이 방식은 서버의 전역 선형 순서를 논리적 타임스탬프로 쓰는 RGA 리스트 CRDT [1]와 동등해 보임
      예를 들면 Lamport 타임스탬프 대신 서버 순서를 쓰는 형태임
      [1] https://inria.hal.science/inria-00555588/
    • 어제 우연히 오래된 스레드[0]를 읽다가 Thymer에 대한 글을 보고 흥미가 생겼음
      HN에서 Thymer를 검색해 보니 2009년의 Show HN[1]이 나왔고, Thymer는 지난 15년 동안 비공개 베타였던 것처럼 보임
      0. https://news.ycombinator.com/item?id=40786425
      1. https://news.ycombinator.com/item?id=518803
    • 어떤 리치 텍스트를 쓰고 있는지 궁금함

  • 이 글을 꼭 읽어봐야겠음. 프리랜서 클라이언트 작업에서 React Table Library [0]를 오픈소스로 공개했고, 트리 연산에 초점을 맞췄음
    그들은 10만 개 노드 규모의 폴더/파일 트리 구조를 다루며, 폴더와 파일 이동, 복제, 최상위 및 중첩 수준의 지연 로딩 등을 같은 테이블 구조 안에서 처리함. 프로젝트를 끝내고 나니 Google Drive가 왜 같은 계층 수준에서만 표시와 수정을 허용하는지 알 것 같았음. 많은 노드가 있는 중첩 뷰에서 이를 구현하려면 고려해야 할 제약이 너무 많음
    [0] https://react-table-library.com/

    • 좋아 보이는데, 언제 완전히 헤드리스가 될지 궁금함

  • 조언을 구하고 싶음. 멀티플레이어 앱은 아니지만, 프런트엔드에 사용자 프로필로 쓰는 크고 상호 연결된 비정규화 트리들이 있음
    타일형 레이아웃처럼 사용자가 타일을 추가/삭제/크기 변경하고, 각 타일 슬롯에 여러 컴포넌트를 추가하며, 그 컴포넌트들도 각자 프로필을 갖는 구조를 생각하면 됨. 서로 다른 타일 배열을 가진 여러 레이아웃이 존재할 수 있고, 개별 타일이 전역 상태의 다른 조각을 참조하거나 공유하는 복잡성도 있음
    일반 REST로 안전하게 업데이트하기가 어려움. 같은 사용자가 탭 두 개를 열고 탭 1에서 업데이트한 뒤 탭 2에서 또 업데이트해 전체 프로필이 무효 상태가 되지 않도록 보장해야 하기 때문임. 전반적으로 순서도 중요함. 클라이언트에는 제대로 적용된 업데이트를 서버에서 건너뛰면 깨질 수 있음
    아주 단순한 해결책으로, 특정 상태 조각을 완전히 덮어쓸 수 있는 최소 데이터를 보내고 큐 뒤에 넣는 방식을 썼음. 보통은 괜찮지만 실제 변경은 몇 바이트뿐인데 50KB를 보내는 식으로 낭비가 생길 때가 있음
    일반적으로 CRDT가 필요한 이유들은 없지만, 단일 사용자라도 상태 관리가 훨씬 쉬워질 것 같음. 우선 사용자의 브라우저 탭 간 동기화가 되고, 더 중요하게는 프런트엔드 상태를 단순히 변경하면 CRDT가 서버와 적절히 조율해 줄 것이라고 믿을 수 있음. 더는 직접 처리하지 않아도 됨. 이게 말이 되는지, 아니면 멀티플레이어와 로컬 우선이 필요 없는 상황에서 Yjs 같은 것을 붙이는 오버헤드가 가치 없는지 궁금함

    • 애플리케이션이 여러 탭을 적극적으로 쓴다면 YJS 같은 것을 쓰는 게 말이 될 수 있음. 그런 유형의 문제를 해결하는 데 매우 효과적이기 때문임
      다만 프로필 편집이 단일 사용자 전용이라면 CRDT 도입은 과한 것 같음. 겉보기에는 탭 두 개를 열어둔 시나리오가 가장 큰 버그 원천이므로, BroadcastChannel로 업데이트 이벤트를 다른 모든 탭에 알리는 방법을 쓸 수 있음
    • 이 사용 사례에는 CRDT가 맞아 보임
      서버 상태 일부를 덮어쓰는 REST 호출로 공유 상태를 유지하는 방식은 실제로 취약하고, 평평한 데이터 레코드의 필드를 덮어쓰는 정도에만 적합함. 또한 서버-클라이언트 상태 조율을 항상 신중히 고려해야 하고, 정상 흐름이 아닌 경로에서는 쉽게 동기화가 어긋남
      말한 것처럼 업데이트가 합쳐지는 방식을 명시하는 CRDT를 만들면 인지 부담이 크게 줄어들 것임

  • Google Docs나 Zoho Writer 같은 서식 있는 텍스트 콘텐츠에서는 목록 항목을 아래로 옮기거나 새 열을 추가하는 작업, 테이블/목록 연산이 본질적으로 트리 조작 연산임
    이런 경우의 동시 충돌은 맥락별 특수 처리가 없으면 수렴시키기 어렵기로 악명 높음 [1]. 이 구현이 그런 사용 사례에도 일반화된 해법을 제공하는지 궁금함
    아마 리프 노드, 즉 텍스트 블록에는 리스트나 문자열 CRDT를 쓰고, 구조 노드인 목록과 테이블에는 이 트리 CRDT를 조합할 수 있을 것 같음. 하지만 그러면 모든 연산에 2차원 주소 (parent-id, index_offset_into_that_parent)를 덧붙여야 함
    [1] https://github.com/inkandswitch/peritext/issues/27

    • 늘 그렇게 상상해 왔음. 리치 텍스트는 평문에 두 가지가 추가된 것임: 굵게 표시된 구간 같은 주석 범위, 그리고 테이블이나 임베디드 이미지 같은 비문자 요소
      텍스트 CRDT는 근본적으로 문자 데이터를 담는 리스트 CRDT일 뿐임. 따라서 임베디드 요소는 문자열의 다른 항목처럼 크기 1인 특수 항목, 즉 임베디드 자식 노드로 쉽게 모델링할 수 있음. 올바른 접근을 쓰면 필요에 따라 트리 안에서 서로 다른 CRDT를 섞어 쓸 수 있음. 예를 들어 리치 텍스트 안에 테이블이 있고, 그 셀 중 하나에 이미지가 있는 식임
      모든 연산에 parent-crdt-id 필드를 붙이는 건 아쉽지만 피하기 어려워 보임. 다행히 실제 사용 사례 대부분에서는 연속된 연산들이 같은 부모 CRDT를 공유하는 경우가 매우 흔할 것 같고, 그래서 이런 ID 필드는 런 렝스 인코딩으로 잘 압축될 것 같음
    • 구현상 여러 종류의 CRDT를 실제로 조합할 수 있음. Loro 내부 구현에서는 각 연산이 부모 ID를 저장해야 함
      다만 Seph가 말한 것처럼 같은 부모 아래의 연속 연산은 효과적으로 압축할 수 있어서, 이런 부모 ID의 상각 오버헤드는 보통 크지 않음

  • 이미지의 픽셀이나 3D 모델처럼 데이터 밀도가 높은 애플리케이션에 실용적인 CRDT가 있었는지 궁금함

    • 협업 애플리케이션에서는 먼저 사용자가 수행할 편집에 대한 개념적 틀과, 그런 편집이 비동기로 일어날 때 사용자의 의도와 결과 문서의 일관성을 가장 잘 보존하는 방법부터 잡아야 함
      문서의 구체적 표현이 데이터 집약적이더라도, 사용자의 개별 편집과 연산을 인코딩하는 방식은 여전히 작을 수 있음
      Photoshop 같은 이미지 편집기를 만든다고 해보면, 채널당 16비트 색 깊이의 비압축 1억 200만 화소 이미지, 예를 들어 Fujifilm GFX100 사진은 TIFF로 약 610MB임. 각 픽셀을 별도의 마지막 쓰기 승리 레지스터로 표현하면 오버헤드가 크지만, 그런 표현은 사용자의 의도를 보존하는 데 실제로 맞지 않음. 사용자가 할 편집은 "이미지 대비를 15% 올리기"나 "브러시 Q와 색상 #000으로 스플라인 [(0,0), (1500, 1500)] 칠하기" 같은 것임. 각 픽셀을 Lamport 타임스탬프로 동기화하면 사용자 1의 대비 변경이 사용자 2가 칠한 픽셀을 제외한 모든 픽셀에 적용되어, 덧칠된 픽셀이 어색하게 보일 수 있음
      대신 사용자 의도를 편집 연산 목록으로 표현하는 편이 나음. 이는 102MB짜리 픽셀 격자 전체보다 훨씬 작음. CRDT 자료구조는 그런 사용자 의도를 동기화하기 위한 가능한 기술적 메커니즘 중 하나지만, 구조는 출력의 구체적 데이터 배치가 아니라 사용자 의도의 의미론에 맞춰 골라야 함
      그래도 "add new layer named bgbelow layerfgwith pixelsdata:(10mb of pixels) at (1500, 1500)"처럼 대량 데이터를 포함하는 편집 연산은 생길 수 있음. 하지만 이런 편집 명령의 동기화 오버헤드는 매우 낮고, 크기는 O(1)이지 편집 명령 안의 픽셀 수에 비례하는 O(pixels)가 아님
    • 완전히 같지는 않지만, Figma는 동시 편집을 지원하고 CRDT와 비슷한 접근을 쓰는 것으로 알고 있음 (https://www.figma.com/blog/how-figmas-multiplayer-technology...)
    • 이미지 편집에는 모든 충돌 편집을 마지막 작성자 승리 방식으로 쉽게 해결할 수 있어서 CRDT가 꼭 필요할지 모르겠음
      3D 모델은 다른 문제이고, 협업 3D 모델링 도구가 시장에 있는지는 본 적이 없음. 적극적으로 찾아본 건 아님
    • 성능 좋은 픽셀 기반 CRDT가 어떤 모습일 수 있는지 큰 CRDT 글에서 스케치한 적이 있음: http://archagon.net/blog/2018/03/24/data-laced-with-history/...
      직접 만들어 보지는 않았고, 실제로 실용적일지도 확신은 없음. 그래도 최소한 문서의 전체 이력은 보존할 수 있음
    • 본 멋진 예시는 래스터 그래픽용 비파괴 편집기인 Modyfi임
      Yjs로 데이터를 표현하지만 원시 픽셀을 저장하는 대신 변환의 전체 이력을 저장함
      https://digest.browsertech.com/archive/browsertech-digest-ho...

  • 글을 GPT로 검사했는지 궁금함. 첫 문단에서 ChatGPT 말투가 강하게 느껴짐

    • 그렇진 않아 보임. 이런 문법 오류는 ChatGPT답지 않음:
      This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.
답변달기