[CRDT] CRDT 기본 원리 정리

CRDT 원리를 담은 동영상

위 영상을 기반으로 핵심 내용들만 정리한 내용입니다.

 

동시편집이란?

동시 편집은 동시에 시작한 작업이 원하는 화면에서 같은 화면으로 종료시키고자하는 방식입니다.

즉, 여러 유저들 간 수정 내역들을 통합하고 병합하여 최종적으로 같은 화면을 보게 만들어야합니다.

- 최종적으로 같은 화면으로 수렴되는 성질을 convergence property(수렴 속성)이라 합니다. 이는 consensus(합의)와 비슷하지만 다릅니다.

 

익숙한 병합도구로 git이 있습니다. 하지만, git은 같은 줄을 편집하여 충돌이 생긴 경우 수동으로 편집해야합니다.

가장 유명한 도구로는 google docs가 있습니다.

 

Google Docs

 

구글 독스는 로컬 복사본과 서버를 이용하여 OT(Operational Transformation) 방식의 동시 편집을 수행합니다. 간단한 과정은 다음과 같습니다.

 

1. 사용자의 입력으로 데이터가 수정되면, 로컬 복사본에 이를 반영하고 수정사항을 서버로 전달합니다.

2. 서버는 이런 입력들을 취합하고 수정 사항들을 병합하고 다시 로컬로 전송합니다.

3. 서버로부터 응답이 오면, 이에 맞게 로컬 복사본과 문서에 내용을 반영합니다.

 

이 방법은 아쉽게도 몇 가지 문제가 있습니다.

- 중앙 서버가 반드시 필요하며, 해당 네트워크가 없다면 동시 편집이 불가능합니다.

- 중앙 서버에 전송하고 받는 과정에서 네트워크 자원이 낭비됩니다.

- 서버에서 (상대적으로) 많은 연산을 필요로 합니다.

 

이런 OT 방식의 단점을 극복하고자 CRDT(Conflict-free Replicated Data Type) 알고리즘이 새롭게 개발되었습니다.

 

OT & CRDT의 핵심 원리

본격적으로 두 알고리즘을 알아보겠습니다. 두 알고리즘의 핵심 원리는 동일합니다.

차이는 OT는 중앙 서버에서 이 로직을 수행하고, CRDT는 각 로컬에서 이 로직을 수행한다는 점입니다.

통합하는 과정

 

두 유저가 있을 때, "Hello!"로 시작한다 하겠습니다.

 

1. 각 유저는 동시에 수정을 진행합니다.

- Red : Hello World!

- Blue : Hello! :-)

 

2. 각 위치에서의 수정사항을 공유하여 삽입합니다.

 

간단한 원리지만, 무수히 많은 예외처리가 필요합니다.

대표적으로 "World"가 마지막에 삽입되었다면 어떻게 될까요?

"Hello! World" 일 때, 

"Hello! World :-)" , "Hello! :-) World", "Hello! W:-)orld" 등등 뭐가 옳은 결과일까요?

동일 위치에서 삽입이 일어났을 때,

1. 다음과 같이 같은 위치에서 삽입이 일어났을 때, 삽입이 일어난 위치와 유저의 번호 등을 조합하여 id를 만들어냅니다.

2. id를 기반으로 텍스트를 로컬에서 먼저 편집합니다.

3. 이후, 동시간대에 편집 내용을 받아옵니다.

4. 이 때, 편집 내용의 id를 기반으로 들어가야할 위치를 정합니다. (위의 경우, 본인보다 id가 작은 것을 만날 때까지 순회하는 것이 규칙입니다.)

 

OT vs CRDT

마지막으로, OT와 CRDT의 차이를 정리하겠습니다.

OT는 중앙 서버에서 병합을 수행하고, CRDT는 각 로컬에서  병합을 수행합니다.

 

OT는 단순하고 정확하지만, 중앙 서버가 반드시 존재해야하며 중앙 서버가 모든 연산을 수행해야합니다. 이는 유저 수나 작업이 많은 환경에서 큰 부담이 될 수도 있습니다. 또한, 반드시 중앙 서버를 거쳐야하기 때문에 네트워크 자원 손실 등이 발생할 수 있습니다.

 

CRDT는 로컬에서 이런 병합을 수행합니다. 중앙 서버가 없어도 되기 때문에 로컬 P2P 서버, 오프라인 모드 등에서도 사용할 수 있으며, 네트워크 자원 손실이 없습니다. 또한, 각 연산을 로컬에서 수행하기에 상대적으로 부담이 적습니다. 하지만, OT에 비해서 알고리즘과 데이터 구조 설계가 복잡합니다.