[동시편집] CRDT vs OT
OT 방식은 2006년 이전부터 사용하던 동시편집 기술입니다.
Google Docs나 Microsoft는 여전히 이 기술을 사용하고 있습니다.
기본 원리는 사용자의 작업을 변환하여, 다른 사용자의 작업과 충돌하지 않도록 조정합니다.
위의 그림과 같이 동시에 편집을 하게 될 때
서버에 편집 요청을 보냅니다.
서버는 요청에 대해 통합하는 역할을 하게 되는데, 이때 바뀐 인덱스의 위치를 고려합니다.
이런 동작 원리로 인해 중앙 서버가 필요하며, 서버를 통해 모든 변환을 조정합니다.
OT방식은 빠른 응답성으로 공동 편집에 사용되었지만,
히스토리를 재정렬하고 오퍼레이션을 변환해야 하므로 downstream의 처리 속도가 특히 분산 환경에서 매우 느리다는 단점이 있습니다.
(O(N^2k), N: 오퍼레이션의 수, k: 리플리카 수).
CRDT 방식은 2006년 이후부터 사용하던 동시편집 기술입니다.
Automerge / RGA or y.js / YATA 등 다양한 CRDT 라이브러리가 존재합니다.
기본 원리는 데이터 타입 자체가 충돌을 자동으로 해결하도록 설계되어 있습니다.
중앙 서버 없이도 피어 투 피어(P2P) 방식으로 작동할 수 있다는 장점이 있습니다.
데이터 타입의 설계가 중요하지만, 일단 구현되면 사용하기 쉽습니다.
교환 법칙(commutative)의 오퍼레이션을 사용해서 downstream 실행시 리플리카의 일관성을 위해서 오퍼레이션을 별도로 변환하거나 정렬할 필요가 없습니다.
하지만 보통 CRDT 유형의 알고리즘은 upstream 처리시에 고유한 identifier를 생성하거나 조회되어야 하므로 upstream 처리가 느린 경향이 있습니다.
저희 팀은 서버의 부하를 막고 OT에 비해 비교적 쉬운 CRDT 방식으로 동시편집을 구현하기로 하였습니다.