▲

GN⁺: 더 빠른 CRDTs (2021)

 (josephg.com)
3P by neo 3달전 | favorite | 댓글 1개

5000배 빠른 CRDT: 최적화의 모험

서론

  • 몇 년 전, 프랑스 연구자들이 실시간 협업 편집 알고리즘을 비교한 논문을 발표했음
  • 여러 알고리즘을 구현하고 성능을 벤치마킹했음
  • 일부 알고리즘은 간단한 붙여넣기 작업에 3초 이상 걸렸음
  • 문제의 알고리즘은 ShareJS에서 사용한 알고리즘이었음

문제의 원인

  • 논문에서 큰 텍스트를 붙여넣을 때 1000개의 개별 작업으로 나누어 처리했음
  • 이는 알고리즘 자체의 문제가 아니라 구현의 문제였음

CRDT의 매력

  • CRDT(Conflict-Free Replicated Data Types)는 여러 사용자가 동시에 데이터를 편집할 수 있게 해줌
  • 로컬에서 지연 없이 작업할 수 있으며, 동기화 시 자동으로 일관성을 유지함
  • 중앙 서버 없이도 작동 가능함

Automerge의 문제점

  • Automerge는 협업 편집을 위한 라이브러리로, RGA 알고리즘을 기반으로 함
  • 각 문서의 문자를 고유 ID로 관리하고, 삽입 시 부모 항목을 지정함
  • 성능 문제로 인해 260,000개의 편집 작업을 처리하는 데 5분이 걸림
  • 메모리 사용량도 매우 높음

성능 최적화

  • Automerge의 성능 문제는 복잡한 트리 기반 데이터 구조와 Immutablejs 사용 때문임
  • Yjs는 단일 평면 리스트를 사용하여 성능을 크게 향상시킴
  • Yjs는 삽입 위치를 찾기 위해 캐시를 사용하고, 양방향 연결 리스트를 사용하여 삽입을 효율적으로 처리함
  • Yjs는 30배 더 빠르고 메모리 사용량도 적음

Rust로의 전환

  • Rust는 메모리 레이아웃을 제어할 수 있어 성능을 더욱 향상시킬 수 있음
  • Diamond types라는 새로운 CRDT 구현을 통해 Yjs보다 5배 빠른 성능을 달성함
  • Rust로 구현된 Diamond는 260,000개의 편집 작업을 56밀리초 만에 처리함

결론

  • 최적화된 데이터 구조와 효율적인 메모리 관리로 CRDT의 성능을 크게 향상시킬 수 있음
  • Rust와 같은 저수준 언어를 사용하면 더욱 빠른 성능을 달성할 수 있음

GN⁺의 정리

  • CRDT는 협업 편집의 미래로, 중앙 서버 없이도 일관성을 유지할 수 있는 강력한 도구임
  • Automerge의 성능 문제는 복잡한 데이터 구조와 비효율적인 메모리 사용 때문이었음
  • Yjs와 Diamond types는 단순하고 효율적인 데이터 구조를 사용하여 성능을 크게 향상시킴
  • Rust와 같은 저수준 언어를 사용하면 더욱 빠른 성능을 달성할 수 있음
  • 협업 편집 도구를 개발할 때 Yjs와 Diamond types를 고려해볼 만함
▲
neo 3달전  [-]
Hacker News 의견

  • 32개의 엔트리가 가장 효율적인 이유는 캐시 라인이 64바이트이기 때문임

    • 2바이트 정수를 사용할 경우, 32개의 엔트리가 정확히 하나의 캐시 라인에 맞아 메인 메모리 전송을 줄일 수 있음

  • CRDTs를 사용하는 실제 애플리케이션 중 좋은 경험을 제공하는 예시를 찾기 어려움

    • Notion은 두 사람이 동시에 노트를 작성할 때 Google Docs에 비해 사용성이 떨어짐

  • CRDTs는 강력하지만, 역사적인 작업(또는 요소)을 남기는 단점이 있음

    • 압축을 사용해도 여전히 단점으로 작용해 채택에 대한 우려가 있음
    • 그럼에도 불구하고 파일 기반 저장소 제공자(Dropbox, Syncthing 등)에서 충돌 없는 알고리즘을 구현할 가능성에 대해 흥미를 느낌

  • 현재 GitHub Readme 인용:

    • 블로그 게시물 이후 성능이 10-80배 향상됨

  • 이 기사는 내용이 어려워도 잘 쓰여져 있어 읽는 것을 멈출 수 없었음

  • 계층 구조를 사용한 것을 보고 중첩 집합을 대신 사용했는지 궁금함

    • 읽기 작업에서의 이득이 삽입 작업에서의 손실을 상쇄할 수 있을지에 대한 아이디어 없음

  • 몇 년 전에 이 게시물을 우연히 발견했음

    • 최근 몇 년 동안 가장 재미있었던 게시물 중 하나임

  • WASM이 네이티브 실행보다 4배 느린 이유에 대해 궁금함

    • 모든 문자열 작업이 WASM 메모리로 복사되고 결과가 계산된 후 다시 JS로 복사되어야 하기 때문이라고 생각했음
    • 이 맥락을 잘못 이해한 것인지 궁금함

  • Automerge의 Rust 구현이 완료되었으므로 업데이트된 벤치마크를 보는 것이 흥미로울 것임

답변달기