▲

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

 (loro.dev)
2P by neo 2달전 | favorite | 댓글 1개

  • Movable tree CRDTs and Loro's implementation

  • 배경

    • 분산 시스템과 협업 소프트웨어에서 계층적 관계를 관리하는 것은 복잡함
    • 데이터 구조에서 삭제와 삽입을 결합하여 이동을 모델링할 때 충돌 해결과 사용자 기대 충족이 어려움
    • 예를 들어, 동일한 노드를 다른 부모로 동시에 이동하면 동일한 내용의 중복 노드가 생성될 수 있음

  • 이동 가능한 트리의 충돌

    • 이동 가능한 트리의 주요 작업: 생성, 삭제, 이동
    • 동시 작업 동기화 시 발생할 수 있는 충돌:
      • 동일한 노드가 삭제되고 이동됨
      • 동일한 노드가 다른 노드 아래로 이동됨
      • 다른 노드가 이동되어 순환이 발생함
      • 조상 노드가 삭제되는 동안 자손 노드가 이동됨
  • 동일한 노드의 삭제와 이동
    • 상대적으로 해결이 쉬움
    • 분산 시스템의 타임스탬프나 애플리케이션의 특정 요구 사항에 따라 하나의 작업을 적용하고 다른 작업을 무시함
  • 동일한 노드를 다른 부모 아래로 이동
    • 동시 이동 작업 병합은 더 복잡함
    • 애플리케이션에 따라 다양한 접근 방식 채택 가능:
      • 노드를 삭제하고 다른 부모 노드 아래에 복사본 생성
      • 노드가 두 부모에게 연결되도록 허용 (일반적으로 허용되지 않음)
      • 모든 작업을 정렬하고 순차적으로 적용
  • 다른 노드의 이동으로 인한 순환 발생
    • 동시 이동 작업으로 인한 순환 해결은 복잡함
    • 여러 해결책:
      • 오류 발생
      • 순환 노드를 특별한 "타임아웃" 영역에 렌더링
      • 서버에서 이동 작업 처리
      • 위상 정렬 사용
      • 순환을 일으키는 엣지를 숨김
  • 조상 노드 삭제와 자손 노드 이동
    • 조상 노드 삭제 시 자손 노드 이동은 쉽게 간과될 수 있음
    • 모든 자손 노드를 직접 삭제하면 데이터 손실로 오해할 수 있음

  • 인기 있는 애플리케이션의 충돌 처리 방법

    • Dropbox: 파일 이동을 삭제 후 생성으로 처리했으나 데이터 손실 위험 있음
    • Figma: 중앙 서버가 순환을 감지하고 작업을 거부하여 일관성 유지

  • 이동 가능한 트리 CRDTs

    • 중앙 집중식 솔루션 대신 CRDTs 사용
    • 초기 CRDT 기반 알고리즘은 구현이 어렵고 저장 오버헤드가 큼
    • 지속적인 최적화로 일부 CRDT 기반 트리 동기화 알고리즘이 생산 환경에 적합해짐

  • 복제된 트리를 위한 고가용성 이동 작업

    • 트리의 세 가지 작업(생성, 삭제, 이동)을 이동 작업으로 통합
    • 이동 작업은 Move t p m c로 정의됨
    • 노드 삭제는 TRASH 노드로 이동하여 처리
  • 전역적으로 정렬된 논리적 타임스탬프
    • Lamport 타임스탬프 사용하여 분산 시스템에서 이벤트의 인과 순서 결정
    • 작은 숫자가 더 이른 이벤트를 의미함
  • 원격 작업 적용
    • 작업의 안전성은 적용 시 트리 상태에 따라 다름
    • 원격 업데이트를 처리할 때 최근 작업을 되돌리고 새로운 작업을 삽입한 후 되돌린 작업을 다시 적용

  • CRDT: 가변 트리 계층 구조

    • 각 노드가 모든 역사적 부모 노드를 추적하고 카운터를 부여
    • 동기화 시 순환이 발생하면 가장 가까운 역사적 부모 노드에 다시 연결

  • Loro에서의 이동 가능한 트리 CRDTs 구현

    • Martin Kleppmann의 알고리즘을 구현하여 높은 성능 제공
    • Fractional Index 알고리즘을 통합하여 자식 노드 정렬 가능

  • 자식 노드 정렬에서의 잠재적 충돌

    • 동일한 위치에 여러 노드를 삽입할 때 동일한 Fractional Index가 할당될 수 있음
    • PeerID를 사용하여 동일한 Fractional Index의 상대적 순서 판단

  • 구현 및 인코딩 크기

    • Fractional Index는 노드 순서를 제공
    • 인코딩 크기는 최악의 경우 추가 바이트가 필요하지만 드문 상황임

  • 관련 작업

    • Fractional Index 외에도 이동 가능한 목록 CRDT가 있음
    • Fractional Index는 구현이 간단하고 상대적 순서만 필요할 때 유용함

  • 벤치마크

    • Loro의 이동 가능한 트리 구현 성능 벤치마크 수행
    • 실시간 협업과 원활한 역사적 버전 체크아웃 지원 가능

  • 요약

    • 이동 가능한 트리 CRDTs 구현의 어려움과 두 가지 혁신적인 알고리즘 소개
    • Loro는 Martin Kleppmann의 알고리즘과 Fractional Index를 통합하여 다양한 애플리케이션 시나리오를 충족

  • GN⁺의 정리

    • 이동 가능한 트리 CRDTs는 분산 시스템에서 계층적 데이터 구조를 관리하는 데 중요한 역할을 함
    • Loro는 높은 성능과 효율적인 충돌 해결을 제공하여 실시간 협업 애플리케이션에 적합함
    • Fractional Index를 사용하여 자식 노드 정렬 문제를 해결함
    • 유사한 기능을 가진 다른 프로젝트로는 Figma와 Dropbox가 있음
▲
neo 2달전  [-]
Hacker News 의견

  • 새로운 멀티플레이어 편집기를 개발 중임

    • 텍스트와 아웃라이너 작업을 지원함
    • 문서는 큰 트리 구조로 변환됨
    • insmov(이동 또는 삽입) 작업을 사용하여 동기화함
    • 서버가 변경 사항을 보내면 클라이언트는 이를 다시 적용함
    • 대부분의 경우 작업을 되돌릴 필요가 없음
    • 실시간 업데이트 시 문제가 거의 발생하지 않음

  • React Table Library를 오픈 소스로 제공함

    • 폴더/파일 트리 구조를 처리함
    • 폴더/파일 이동, 복제, 지연 로딩 등을 지원함
    • Google Drive가 동일한 계층 수준에서만 표시 및 수정하는 이유를 이해하게 됨

  • 조언을 구함

    • 큰 비정규화된 트리를 프론트엔드에서 사용 중임
    • 사용자 프로필을 타일 레이아웃으로 관리함
    • 안전한 업데이트를 위해 최소한의 데이터를 전송함
    • CRDT를 사용하면 상태 관리가 훨씬 쉬워질 것 같음
    • 브라우저 탭 간 동기화가 가능해짐

  • Google Docs/Zoho Writer와 같은 형식화된 텍스트 콘텐츠 작업 시 트리 조작이 필요함

    • 동시 충돌 문제 해결이 어려움
    • 리스트 CRDT와 트리 CRDT를 결합할 수 있을 것 같음
    • 모든 작업에 2차원 주소를 추가해야 함

  • 이미지(픽셀) 및 3D 모델과 같은 데이터 밀집 응용 프로그램에 대한 실용적인 CRDT가 있는지 궁금함

  • 첫 번째 단락이 ChatGPT의 목소리를 닮았다고 생각함

답변달기