24P by xguru 22일전 | favorite | 댓글 10개

구글 Wave 개발자가 얘기하는 Conflict-free Replicated Data Types 이야기
ㅤ→ CRDT : 실시간 협업도구에서 동시 편집을 지원하는 자료 구조
- Wave는 OT(Operational Transform) 기반 : 모든 변경에 대한 시간순 목록을 저장. 실시간 git-rebase 와 같음
- OT의 문제중 하나는 중앙 집중식 서버/DB가 필요하다는 것
ㅤ→ 구글 닥스(역시 OT기반) 문서에 사람이 몰릴 때 '이 문서는 과부하 되어 편집이 불가능 합니다' 가 나오는 이유가 아마도 이거일듯?
ㅤ→ 문서를 분할하거나 DB 트랜잭션에 재시도 루프를 통해서 회피는 가능 (Serialization문제를 DB로 이관해버림)
ㅤ→ 하지만 완벽하지 않음. Wave는 여러 사람이 동시에 편집했고 잘 동작은 했지만 버그가 많았음. 너무 복잡
- CRDT 의 부상
ㅤ→ Wave가 사용한 알고리즘은 1995년에 발명 된 것. 계속 OT가 잘 동작하도록 연구했지만, CRDT가 더 전도 유망
ㅤ→ CRDT는 다른 접근법을 취해서, 중앙DB없이 실시간 편집이 가능
ㅤ→ 예전에 문제라고 제기했던 속도/용량/기능/복잡도가 모두 개선 됨
ㅤㅤ* 속도 : 요즘의 CRDT (Automerge / RGA or y.js / YATA) 들은 log(n) 수준의 조회 가능
ㅤㅤ* 용량 : Martin 의 Columnar 인코딩은 문서 크기의 1.5~2배 크기 정도로 저장이 가능.
ㅤㅤ* 기능 : 이론적으로는 Rewinding 및 replaying이 가능. 물론 아직 구현한 사람은 없음
ㅤㅤ* 복잡도 : 구현체 크기가 OT보다 CRDT가 크긴 하겠지만 큰 차이 없음
ㅤ→ 위 개선 사항들은 Automerge 에서 곧 제공될 예정

- 실시간 편집에 있어서, 슬프지만 OT 와 관련 작업들은 더이상 필요없을 것
ㅤ→ OT의 모든 기능이 CRDT에 넣을 수 있지만, 반대는 불가능함
ㅤ→ OT의 장점은 중앙 집중식 소프트웨어에 적합하다는 거지만, 분산 알고리즘은 중앙 집중방식에서도 잘 작동함
ㅤ→ WASM에서 실행되는 고품질 CRDT가 JS의 OT 구현보다 빠를 것

- 이제는 가볍고 빠른 CRDT를 만들어야 할 시점.
ㅤ→ 학문적인 부분은 거의 완성되었고, 이제 훌륭한(kick-ass) 구현체가 필요한 시점

xguru 22일전  [-]

글에 링크된 Automerge 개발자 Martin Kleppmann 의 동영상 "CRDTs: The Hard Parts" 가 정말 설명이 좋네요.
초반에 OT랑 CRDT를 잘 비교해서 설명해 줍니다. 뒷 부분은 CRDT 구현에 관한 깊은 얘기구요.
https://www.youtube.com/watch?v=x7drE24geUw

* Automerge : https://github.com/automerge/automerge
JS로 협업 도구를 만들때 사용하는 CRDT 라이브러리

xguru 22일전  [-]

Towards collaboration system: OT 알고리즘에서 CRDT 시스템으로
https://deview.kr/2013/detail.nhn?topicSeq=66

국내 발표중에서는 거의 유일하게 CRDT 얘기를 다룬 내용이네요.

hackerwins 21일전  [-]

이 발표를 하신 현걸님은 본문에서 말하고 있는 RGA를 만드셨어요.
Yorkie도 리스트형 데이터타입을 RGA를 기반으로 구현했습니다.
https://github.com/yorkie-team/yorkie/issues/2

hackerwins 22일전  [-]

Yorkie 프로젝트를 개발하고 있는 홍영택이라고 합니다.
동시편집 앱을 위한 문서저장소 Yorkie도 CRDT를 기반으로 만들고 있어요.

https://github.com/yorkie-team/yorkie

ffdd270 22일전  [-]

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

전문 번역을 했었는데, 올리는 걸 까먹었네요 ;ㅁ; 파파고 베이스로 한번 읽으면서 어색한 부분들만 수정했습니다. 혹여 전체적인 느낌이 어떤지? 읽어보고 싶으신 분들은 위 링크를 확인해주세용~

댓글 창에 올리기에는.. 너무 길어서 ;ㅁ; 노션 링크로 제공해드립니당.

ffdd270 22일전  [-]

생각해보니 Notion도 CRDT를 사용중일 수도 있겠군용!

iolothebard 22일전  [-]

OT를 하면 undo/redo를 날로 먹을 수 있는데... CRDT는 snapshot 밖에 방법이 없는...

xguru 22일전  [-]

Automerge 같은 경우는 라이브러리 자체에서 undo/redo 를 지원해주긴 합니다. 구현하는 사람은 어렵겠지만 라이브러리 쓰는 입장에서는 뭐 ㅎㅎ

xguru 22일전  [-]

OT를 사용하는건 구글 Wave/구글 Docs/MS Office365
CRDT를 사용하는건 Figma/Apple Notes 및 Riak/Redis 등

xguru 22일전  [-]

Figma 의 다중사용자 기술은 어떻게 동작하는가 https://news.hada.io/topic?id=814