실시간 편집 알아보기

Optimistic Replication

공동 편집에는 응답성이 매우 중요합니다.

그리고 네트워크 지연이나 문서의 락에 영향을 받지 않아야 합니다.

 

모든 유저는 자신의 디바이스에 편집하려고 하는 문서의 복제본을 가지고, 이를 Optimistic Replication이라고 부릅니다.

 

사용자의 편집 operator의 반영 순서는 다음과 같습니다.

1. 로컬 복제본 -> 원격 복제본
2. upstream 실행: local operation 실행
3. downstream 실행: 다른 사용자가 전송한 원격 operation 처리

 

OT (Operation Transformation)

OT는 2006년까지 사용되던 기술로 Google Docs, Ms Office 등에서 사용합니다.

 

동작 원리

왼쪽 친구는 3번째 인덱스에 l을 추가했고

오른쪽 친구는 4번째 인덱스에 !를 추가했습니다.

 

친구들의 Operation을 서버가 받아서 통합하는 과정을 거칩니다.

 

이 과정에서 다음과 같은 상황이 발생할 수 있습니다.

4번째 index에 !를 추가해야 하는데 3번째 인덱스테 l이 들어가는 바람에 인덱스들의 순서가 변경되었습니다.

원래대로 4번째 인덱스에 !를 추가하면 될까요?

 

안됩니다!

원하는 결과를 얻으려면 !는 5번째 인덱스에 추가되어야 합니다.

 

이렇게 Opertaion을 적절하게 Transform해주는 방식을 OT(Operation Transform)방식이라고 부릅니다.

 

문제점

하지만 이런 OT에게는 문제점이 있습니다.

 

바로 중앙 서버가 존재해야 한다는 것인데요.

서버에 너무 많은 사용자가, operation이 몰린다면 과부하가 발생할 수 있습니다.

 

이러한 OT의 대안으로 CRDT가 등장하게 됩니다.

 

CRDT (Conflict-free-Replicated Data Types)

CRDT는 2006년 이후부터 현재까지 사용되고 있습니다.

 

동작 원리

어떠한 변경 사항이 생겼을 때

순서와 상관없이 변경 사항이 동일하다면 같은 상태입니다.

OT와 비교해서 OT는 인덱스로 계산하는 반면 CRDT는 각 개체가 유니크한 값입니다.

 

문제점

하지만 위의 사진 처럼 글자들이 독립적으로 랜덤한 Identifier를 가지게 되는데,

이 Identifier에 의해 Operation들이 merge됩니다.

 

따라서 두 분기를 merge한다면 기대하는 값을 얻기 어려울 수 있습니다.

 

CRDT를 보완하는 알고리즘

 

만약 같은 인덱스에 대해 동시 입력이 발생한다면 어떻게 처리해야 할까요?

 

이때 Logical Clock이라는 개념이 등장합니다.

 

분산 시스템에서 각 노드의 시계를 정확하게 똑같이 동기화 하는건 어려운 문제입니다.

Logical Clock은 clock counter를 이용해 이벤트간의 인과 관계를 따집니다.

 

더 자세한 이야기는 아래 링크를 참고해주세요.

https://www.geeksforgeeks.org/lamports-logical-clock/

Lamport's logical clock - GeeksforGeeks

 

• RGA
  • Linked List와 Logical Clock을 합친 방법입니다.
• RGATreeSplit
  • RGA를 text로 사용했을 때 성능 개선 포인트가 존재합니다.
  • 로컬 실행 복잡도와 공간 복잡도를 개선한 버전입니다.
    • 로컬 실행 시간: Linked List 대신에 Tree 도입
    • 공간 복잡도: 각 요소에 문자가 아닌 문자열을 보관
• TreeDoc
  • 비균형 이진 탐색 트리으로 이진 탐색이 가능합니다.
  • 만약 계속에서 문서의 끝에 텍스트를 입력하게 된다면 균형이 깨져 많은 비용이 발생합니다.

 

참고

https://channel.io/ko/blog/crdt_vs_ot

CRDT vs OT

https://hackerwins.github.io/2019-04-16/co-editor

Google Docs 같은 실시간 협업 에디터를 만드는 방법

https://bartoszsypytkowski.com/the-state-of-a-state-based-crdts/

An introduction to state-based CRDTs