- 협업 편집에서 CRDT가 느리다는 평가는 종종 알고리듬 자체와 구현 방식을 섞어 판단한 결과이며, 자료구조와 메모리 배치만으로 성능이 크게 달라질 수 있음
- Automerge v1.0.0-preview2는 260,000개 편집 추적 처리에 291초와 880MB RAM을 썼고, 같은 작업을 Diamond types native는 56ms와 1.1MB RAM으로 처리함
- Yjs는 트리 대신 평탄 리스트, 위치 캐시, 양방향 연결 리스트, span 저장을 활용해 같은 추적을 0.97초와 3.3MB RAM으로 줄임
- Diamond types는 Rust에서 range tree/B-tree 기반 구조를 사용해 위치 조회·삽입·삭제를
log(n)시간에 처리하고, WebAssembly에서도 Node.js 기준 193ms를 기록함 - 이 벤치마크는 단일 사용자 로컬 편집 재생과 RAM 사용량만 본 것이어서, 실제 선택에는 저장·로드 시간, 네트워크/디스크 크기, binary encoding, 프로토콜, presence, editor binding까지 함께 봐야 함
알고리듬과 구현 성능은 별개임
- 한 학술 비교는 Google Docs 같은 실시간 협업 편집을 여러 CRDT와 OT 알고리듬으로 구현해 벤치마크했고, 일부 알고리듬은 단순 paste 처리에 3초 이상 걸렸음
- 느렸던 방식은 ShareJS와 Google Wave에서 쓰던 알고리듬이었지만, 해당 구현은 1000자 paste를 1000개의 개별 operation으로 쪼개 처리했음
- 이 사례는 동시 편집 동작과 구현 방식을 분리해 봐야 함을 보여줌
- 동작은 동시 편집이 같은 영역에 들어왔을 때 어떤 순서와 규칙으로 병합되는지를 뜻함
- 구현은 프로그래밍 언어, 자료구조, 최적화 수준을 포함함
- 같은 text OT transform 함수도 JavaScript에서는 초당 약 100,000회, C에서는 초당 20M회 실행되어 약 200배 차이가 남
- 느린 구현 하나가 그 시스템의 모든 구현이 느리다는 증거는 아니며, 더 빠른 구현이 가능함
CRDT와 Automerge의 기본 모델
- CRDT는 여러 사용자가 같은 데이터를 동시에 편집하게 해주며, 로컬에서 지연 없이 작업하고 나중에 동기화해 eventual consistency에 도달할 수 있음
- Automerge는 Martin Kleppmann이 만든 협업 편집 라이브러리이며, RGA 알고리듬에 기반함
- Automerge와 Yjs 같은 CRDT는 공유 문서를 문자 리스트로 보고, 각 문자에 고유 ID를 부여함
- 빈 문서에
abc를 입력하면(seph, 0),(seph, 1),(seph, 2)같은 ID가 붙음 - 새 문자는 “어떤 항목 뒤에 삽입되는지”를 함께 기록함
- 빈 문서에
- Automerge/RGA는 각 항목에 sequence number를 추가함
- 새 항목은 지금까지 본 가장 큰 sequence number보다 1 큰 값을 받음
- 자식 항목이 여러 개면 sequence number가 큰 순서로 정렬하고, 같으면 agent ID로 정렬함
- Automerge/RGA의 동작은 세 단계로 볼 수 있음
- 각 항목을 parent에 연결해 트리를 구성함
- 자식이 여러 개인 항목은 sequence number와 ID로 정렬함
- 트리를 depth-first traversal로 평탄화해 최종 리스트나 텍스트 문서를 만듦
Automerge 벤치마크와 병목
- 벤치마크는 automerge-perf의 편집 추적을 사용함
- Martin Kleppmann이 학술 논문을 타이핑한 내용을 문자 단위로 기록한 trace임
- trace에는 260,000개 편집이 있고 최종 문서 크기는 약 100,000자임
- 동시 편집은 포함되지 않음
- 테스트는 로컬에 trace를 적용하는 시간만 측정함
- 환경은 Ryzen 5800x 워크스테이션, Nodejs v16.1, Rust 1.52임
- Automerge v1.0.0-preview2는 이 trace 처리에 291초가 걸렸고, 완료 시점 RAM은 880MB였음
- 키 입력 하나당 약 10KB RAM을 쓴 셈임
- 피크 RAM은 2.6GB였음
- 느린 spike에서는 단일 편집 처리에 1.8초가 걸림
- JavaScript 문자열에 직접 splice하는 baseline은 같은 편집을 0.61초와 0.1MB RAM으로 처리했지만, 협업 편집에 필요한 정보는 모두 버리는 비교용 baseline임
- Automerge가 느린 데에는 몇 가지 구현상 이유가 있음
- 문서가 커질수록 트리 기반 자료구조가 커지고 느려짐
- Immutablejs를 많이 사용해 V8 optimizer와 GC가 최적화하기 어려움
- 삽입된 각 문자를 별도 항목으로 취급해 paste도 많은 항목으로 처리됨
- Automerge 팀은 Rust 구현인 automerge-rs를 WASM으로 쓰는 대체 구현을 작업 중이었음
- 당시 master branch 기준으로 이 테스트의 평균 성능은 빨라지지 않았지만, 메모리 사용량은 절반으로 줄고 성능 변동은 완만해짐
Yjs식 평탄 리스트 구현
- Yjs는 Kevin Jahns가 만든 오픈소스 CRDT 구현이며, 트리 대신 모든 항목을 단일 평탄 리스트에 저장함
- 평탄 리스트 접근은 새 항목을 parent 바로 뒤에서부터 스캔해 삽입 위치를 찾는 방식이며, list CRDT를 리스트로 구현하는 형태임
- 실험용 reference-crdts는 Yjs의 YATA와 Automerge의 RGA를 같은 방식으로 구현함
- 이 접근의 장점은 세 가지임
- 불균형 트리 대신 flat array를 사용해 더 작고 빠름
- 코드가 단순함
- Yjs, Automerge, Sync9 등 여러 list CRDT에 적용할 수 있음
- 이론적으로 같은 위치에 동시 삽입이 많으면 느려질 수 있지만, 실제 편집에서는 대부분 parent 바로 뒤에 삽입함
- reference-crdts 구현은 Automerge보다 약 10배 빨랐고 RAM은 약 30배 적게 사용함
| 테스트 | 처리 시간 | RAM 사용량 |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Plain string edits in JS | 0.61s | 0.1MB |
스캔과 삽입 비용 줄이기
- 평탄 array 구현에는 두 가지 병목이 남음
- 삽입할 위치를 찾기 위해 문서를 스캔해야 함
doc.content.splice(destIdx, 0, newItem)로 array 중간에 삽입할 때 뒤쪽 항목을 이동해야 함
- 삭제된 항목은 다른 삽입이 참조할 수 있어 array에서 제거할 수 없고,
isDeleted같은 표시를 남겨야 함- 현재 문서가 100,000자라도 과거 항목까지 포함해 150,000개 array item이 있을 수 있음
- 문서 위치 50,000에 삽입하려면 삭제 항목을 건너뛰며 대략 75,000개 item을 스캔할 수 있음
- 이런 구조에서는 항목이
n개 있었던 문서에 삽입할 때 약n단계가 필요하고,n개 문자를 삽입하면 O(n²) 가 됨 - Yjs는 사람이 문서를 편집하는 방식에 맞춰 마지막 편집 위치의
(index, position)쌍을 캐시함- 다음 편집은 이전 편집 위치 근처일 가능성이 높아 앞뒤로 짧게 스캔함
- 여러 사용자가 다른 위치를 편집할 때를 위해 캐시된 위치 집합을 저장함
- Yjs는 array 대신 양방향 연결 리스트를 사용해 위치를 찾은 뒤에는 상수 시간에 삽입함
- 또 사람이 문자를 연속으로 입력한다는 점을 이용해
hello를 5개 문자 항목이 아니라 하나의 span으로 저장함- ID와 parent가 순차적으로 이어질 때만 collapse할 수 있음
- 이 데이터셋에서는 array entry 수가 180,000개에서 12,000개로 줄어 14배 감소함
| 테스트 | 처리 시간 | RAM 사용량 |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Rust와 Diamond types의 range tree 접근
- JavaScript 객체는 content, deletion flag, ID, seq, parent 등이 포인터로 흩어진 구조가 되기 쉬워 메모리 단편화와 캐시 miss 비용이 커짐
- Rust는 메모리 배치를 직접 제어할 수 있고, WebAssembly를 통해 웹에서도 사용할 수 있음
- Diamond types는 Rust로 작성한 CRDT 구현이며, Yjs와 거의 같지만 내부적으로 연결 리스트 대신 range tree를 사용함
- 내부 range tree는 약간 수정한 B-tree임
- 일반적인
BTreeMap처럼 key를 저장하는 대신, 내부 노드가 자식에 포함된 문자 수의 합을 저장함 - 문서의 임의 위치 조회, 삽입, 삭제를
log(n)시간에 처리함
- 일반적인
- 260,000개 편집 trace는 이 tree에서 leaf node 3단계 정도로 저장되어, 어떤 item도 대략 3번의 메모리 read로 찾을 수 있음
- remote edit merge를 위해 ID로 B-tree를 찾는 작은 index도 있으며, 해당 codepath는 이 벤치마크에는 포함되지 않음
- leaf node는 32개 entry 블록을 고정 크기 array로 촘촘히 저장함
- 32개 bucket size는 여러 크기로 벤치마크한 결과 잘 동작했지만, 왜 최적인지는 알 수 없다고 밝힘
- Diamond를 diamond-js로 WASM 컴파일해 Node.js에서 호출하면 같은 trace를 193ms에 처리함
- Yjs보다 약 5배 빠름
- JavaScript 문자열 baseline보다 약 3배 빠름
- native Rust 실행은 benchmark에서 56ms를 기록함
- Automerge보다 5000배 이상 빠름
- 초당 4.6M operation을 처리함
- 전체 260,000개 편집 처리 중
malloc호출은 1394회였음
| 테스트 | 처리 시간 | RAM 사용량 |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
| Diamond WASM via Node.js | 0.19s | 알 수 없음 |
| Diamond native | 0.056s | 1.1MB |
Ropey 분리와 tradeoff
- Diamond 구현은 문서 텍스트 내용을 CRDT item 리스트에 직접 넣지 않고 별도 자료구조에 저장함
- 텍스트 내용에는 Rust 라이브러리 Ropey를 사용하며, Ropey도 텍스트 관리를 위해 B-tree를 구현함
- 이 방식에는 공학적 tradeoff가 있음
- Ropey는 텍스트 특화 byte packing을 하므로 RAM 사용량을 줄일 수 있음
- 삽입 시 두 자료구조를 업데이트해야 해 속도가 2배 이상 느려지고 WASM bundle도 60KB에서 120KB로 커짐
- VS Code 같은 editor와 연결하면 editor가 문서 복사본을 유지하므로 CRDT 구조 안에 문서 내용을 저장하지 않아도 될 수 있음
- Ropey만으로 trace를 처리하면 29ms가 걸림
- Diamond native에서 문서 content 업데이트를 끄면 23ms와 0.96MB RAM을 기록함
- Automerge보다 약 14,000배 빠름
- 초당 11M operation을 처리함
- 이 결과는 유용성보다 CRDT metadata 처리 한계를 보기 위한 실험에 가까움
| 테스트 | 처리 시간 | RAM 사용량 | 자료구조 |
|---|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB | naive tree |
| reference-crdts Automerge/Yjs | 31s | 28MB | array |
| Yjs v13.5.5 | 0.97s | 3.3MB | linked list |
| Plain string edits in JS | 0.61s | 0.1MB | 없음 |
| Diamond WASM via Node.js | 0.20s | 알 수 없음 | B-tree |
| Diamond native | 0.056s | 1.1MB | B-tree |
| Ropey Rust baseline | 0.029s | 0.2MB | 없음 |
| Diamond native, no doc content | 0.023s | 0.96MB | B-tree |
실제 라이브러리 선택 기준
- 문서 기반 협업 앱을 지금 만든다면 Yjs를 쓰는 쪽이 유리함
- Yjs는 성능, 낮은 메모리 사용량, 지원 생태계가 좋음
- Kevin Jahns는 Yjs 통합 지원을 유료로 제공하기도 함
- Automerge 팀도 성능을 2021년 최우선 이슈로 두고 있으며, 여러 기법으로 Automerge를 빠르게 만들 계획이 있었음
- Diamond는 매우 빠르지만 Yjs와 Automerge 수준의 기능 parity에는 아직 작업이 많이 남아 있음
- CRDT 라이브러리에는 operation 속도 외에도 binary encoding, network protocol, non-list 자료구조, presence, editor binding 등이 필요함
- 데이터베이스 semantics가 필요하면 CRDT 위에서 잘 된 구현을 알지 못하며, OT 기반 ShareDB를 쓸 수 있음
- Redwood는 P2P editing을 지원하고 full CRDT support를 계획 중인 프로젝트임
측정 방식의 제약
- 이 벤치마크는 로컬 편집 trace 재생 시간과 RAM 사용량만 측정함
- 로컬 사용자 입력은 충분히 빠르면 되며, CRDT가 단일 local edit를 약 1ms 이하로 처리하면 더 빠른 속도는 크게 중요하지 않을 수 있음
- Automerge도 불운한 GC pause를 제외하면 대체로 이 수준을 만족함
- 실제로 더 중요한 지표는 따로 있음
- 문서가 디스크나 네트워크에서 차지하는 byte 수
- 저장과 로드에 걸리는 시간
- 저장된 문서를 데이터베이스 안에서 업데이트하는 시간
- 사용한 trace는 단일 사용자 편집만 포함해, 동시 편집이 많은 pathological case가 남아 있을 수 있음
- 현재 Yjs나 Automerge로 데이터베이스의 단일 객체를 업데이트하려면 일반적으로 전체 문서를 RAM에 로드하고, 변경하고, 전체 문서를 다시 저장해야 해 느릴 수 있음
- Kevin은 Yjs provider를 적절히 조정하면 합리적인 방식으로 구현할 수 있다고 말함
- list CRDT는 삭제된 항목 tombstone 때문에 기본적으로 계속 커지며, pruning은 별도 접근임
- Yjs의 GC 알고리듬과 Antimatter가 예시로 나옴
- pruning은 글에서 다룬 자료구조 최적화와 직교하는 문제임
비교가 완전히 통제된 실험은 아님
- 각 최적화 단계는 여러 변수를 동시에 바꿨기 때문에 속도 향상의 정확한 원인을 분리하지 않음
- Automerge에서 reference-crdts로 넘어갈 때 바뀐 요소는 여러 가지임
- 트리에서 리스트로 핵심 자료구조가 바뀜
- Immutablejs가 제거됨
- Automerge frontend/backend protocol과 여러 Uint8Array 구조가 사라짐
- JavaScript 스타일이 함수형에서 imperative로 바뀜
- reference-crdts에서 Yjs로, Yjs에서 Diamond로 넘어갈 때도 변화가 단일 원인으로 분리되지 않음
- automerge-rs가 이 테스트에서 Automerge보다 빠르지 않았다는 점은 Diamond 성능이 Rust만의 효과는 아니라는 근거지만, 정확한 기여도는 알 수 없음
- RGA와 YATA를 같은 구현 방식으로 비교하는 것도 “동시 병합 동작이 사실상 비슷하며, 동작을 바꿔도 구현 성능이 유지된다”는 전제에 기대고 있음
- reference CRDT implementation에서는 Yjs와 Automerge 동작이 거의 동일한 codepath와 동일한 성능을 보임
- conflict-heavy trace에서는 성능 차이가 있을 수 있지만 실제로는 매우 드문 경우로 봄
- Yjs는 각 item이 언제 삭제됐는지는 저장하지 않고 삭제 여부만 저장함
- Diamond에서 삭제 시점을 저장하면 메모리 사용량이 1.12MB에서 2.34MB로 늘고 약 5% 느려짐
- 이 글의 모든 Diamond benchmark는 Yjs 방식에 맞춘 yjs-style branch를 사용함
벤치마크 코드와 재현 자료
- JS 문자열 baseline, Yjs, Automerge, reference-crdts 테스트 코드는 GitHub gist에 있음
- 대부분 테스트에는 josephg/crdt-benchmarks의
automerge-paper.json.gz가 필요함 - reference-crdts benchmark는 해당 버전의 josephg/reference-crdts에 의존함
- Diamond benchmark는 해당 버전의 josephg/diamond-types에서 실행됨
- 실행 명령은
RUSTFLAGS='-C target-cpu=native' cargo criterion yjs - memory statistics는
cargo run --release --features memusage --example stats로 확인함
- 실행 명령은
- Diamond WASM wrapper는 diamond-js를 사용하고, wasm bundle은
wasm-opt로 최적화함 - 차트는 ObservableHQ에서 만들었음