CRDT, YJS
필요성
한 문서를 여러 사람이 편집하는 상황을 생각 A, B가 동시에 어떤 문장을 수정함 시간 순서대로 A 수정 -> B 수정의 결과가 B 수정 -> A 수정의 결과와 같다면 베스트! 그러나 누군가는 수정하고, 누군가는 삭제하면다면 복잡하게됨 CRDT는 “시간의 순서를 따지지 않고, 모든 변경이 언젠가 서로 합쳐져도 같은 결과로 수렴하도록 만드는 일” -> 순서를 비교하지 않고 의미로 병합
기존 방식
순서대로 하나씩 적용하면, 충돌이 안 생긴다
CRDT의 접근
각 사용자가 로컬에서 자유롭게 수정하더라도, 나중에 수학적으로 합치면 같은 의미로 복원되게 만들자. 변경(operations) 자체가 다음 두 성질을 가지게 설계됨
- Commutative (가환) - 순서 바뀌어도 결과 동일
- Idempotent (멱등) - 같은 연상을 여러 번 적용해도 결과 동일 이 두가지가 있으면 누가 먼저냐 상관없이 결국 동일한 상태로 수렴(converge) 함 -> Strong Eventual Consistency (SEC) 라고 부름
쉬운 예: Counter CRDT
예시
- A가 +1, B가 +2
- A와 B가 동시에 일하고, 나중에 합쳐도 뎔과는 1 + 2 = 3 -> 순서 상관없음, Commutative, CRDT의 가장 기본 형태
문서 편집 (Text CRDT)는 문자 삽입(insert) / 삭제 (delete) 연산 -> 어디에 어떤 글자를 넣었는지 관계를 저장해야 의미를 보존할 수 있음 -> CRDT에서는 position이 아닌 relation으로 표현함
List or Sequence CRDT
- 문자들 사이 관계로 표현된 리스트 구조
| 종류 | 설명 | 예시 |
|---|---|---|
| Counter CRDT | 숫자 덧셈/뺄셈이 충돌 없이 합쳐짐 | like/dislike 수, 투표 수 등 |
| Register CRDT | 마지막 값만 유지 | 상태 토글 (ON/OFF 등) |
| Set CRDT | 원소 추가/삭제 충돌 없이 합침 | 참여자 목록 |
| Map CRDT | key-value 쌍으로 구성된 객체 | JSON-like 구조 |
| List / Sequence CRDT | 순서가 중요한 값의 리스트 | ✨ 문서/텍스트 편집기 |
| Graph CRDT | 관계가 있는 데이터 (실험적) | 노드 연결, 소셜 그래프 등 |
Text CRDT 작동 방식
- 각 문자는 앞/뒤 어떤 문자를 기준으로 삽입됐는가
- 두 사용자가 동시에 삽입해도, “어디 뒤에 왔다”만 알면 충돌없이 정렬 가
CRDT의 문제
- 문서가 길어질수록 메모리 사용량 증가, 가비지 컬렉션 문제, 동기화 성능 저하 이슈 발생
- Yjs의 해결방식 -> YATA (Yet Another Transformation Approach) 라는 방식 사
- 모든 삽입/삭제를 하나의 트랜잭션 로그처럼 저장하되, 필요할 때 효율적으로 병합하고, GC는 나중에 정리하자.
Yjs
- “문서 상태”를 Y.Doc 안에 저장하고, 변경을 작고 이식성 좋은 이진 업데이트(update)로 만듦
- 업데이트는 어떤 순서로 도착해도 수렴함
구성 요소
- Y.Doc: 협업 문서의 루트 (세션). CRDT 상태를 담는 컨테이너
- Shared Types: Y.Text, Y.Array, Y.Map, Y.Xml* … 실제로 편집하는 자료구조,
- Update(이진 패치): 변경 사항의 최소 단위 (typed array). 네트워크로 주고 받음.
- Transaction: 여러 변경을 하나로 묶어 이벤트/성능 최적화. (doc.transact(…))
- Provider(전송/동기화 계층): y-websocket, y-webrtc 등. 업데이트를 브로드캐스트/수신
- Awareness(프레즌스): 사용자 이름, 커서 위치, 선택 영역과 같은 “일시적 상태” 동기화.
- Persistence: y-indexeddb 등 로컬 저장. 오프라인/재접속 회복
- UndoManager: 협업 친화적인 undo/redo 스 핵심: 편집 = Shared Type 변경 -> Doc가 update 생성 -> Provider가 전송/수신 -> 수신 Doc이 update 적용 -> 결국 모두 같은 상태로 수렴.
동시 삽입이 오면
- 각 삽입에 전역적으로 비교 가능한 ID (사이트 ID + 논리 시간 등)을 붙여 총순서 규칙으로 정렬 -> 항상 가튼 규칙으로 정렬됨
- 삭제는 “그 문자를 tombstone 표시”로 관리했다가, 안전해지면 GC로 정리 -> 대형 문서 성능도 좋음