실시간 동시편집 구현 연대기 (1) - CRDT와 OT

들어가며

네이버 부스트캠프에서 진행중인 그룹프로젝트로

algoitni라는 알고리즘을 동료, 친구들과 화상, 음성, 채팅을 공유하며 코드를 함께 작성할 수 있는 서비스를 만들고 있다.

https://algoitni.site/

😺 AlgoITNi

 

 

 

실시간 동시편집

이번 프로젝트에서 가장 어려운 문제는 코드를 함께 작성할 수 있는 이었다. (사실 쉬운게 없었다...)

하나의 문서에 대해 실시간으로 여러 유저의 편집이 각자의 편집화면에 바로 반영되는 것을 실시간 공동편집이라한다.

 

 

다행히도 시중에는 이런 기능을 제공하는 프로그램들이 꽤 있다.

Google Docs, Notion이 그렇다.

이들은 어떻게 구현했을까?

 

OT와 CRDT 알아보기

실시간 동시편집을 구현하는데에는 크게 두가지 기술을 적용시킬 수 있다.

OT (Operational Transformation)

OT는 입력한 순서에 따라 서버가 중간 개입자로써 병합시켜서 각각의 클라이언트에 전달하는 방식이다.

즉, 서버가 모든걸 다해서 클라이언트는 자기정보를 주고, 서버로 부터 받기만 하면 된다.

 

예를들어, 

문서에 HELLO라는 문자열이 있고,

1	2	3	4	5
H	E	L	L	O

 

A가 H를 지우는데, B가 E앞에 C를 입력했다면, 결과 문자열은 CELLO가 된다.

이 과정을 순서대로 살펴보자.

 

1. A가 H를 지운다. (1번 인덱스를 지워!) -> 서버는 E부터 인덱스를 수정한다.

1	2	3	4
E	L	L	O

 

2. B가 E앞에(원래는 2번) C를입력한다.  -> 서버는 1번 인덱스 앞에 C를 붙인다.

1	2	3	4	5
C	E	L	L	O

 

결과물 CELLO가된다!

 

이처럼 그냥 시간 순서대로 병합시키는 형태가 OT이다.

서버에서 인덱스를 보정시켜서 적용시키는 것이다.

즉, 서버에서 이전에서 한 병합행동에 의해(Operational) 다음 행동이 변한다. (Transformation)

 

단점

이 방법은 매우 직관적이나 그만한 단점이 존재한다.

서버 한 곳에서 병합이 일어나기 때문이다. 즉, 중앙집중이기 때문에 간단하나, 사용자가 많아지만 서버의 부하가 커지는 문제를 낳게된다.

 

CRDT (Conflict-free replicated data type)

CRDT는 중앙서버가 필요없는 P2P간의 병합방식이다. OT의 문제점인 과부화 문제를 해결할 수 있게 된다.

하지만 동시에, 중앙서버가 없어지면서 어려운 문제로 변하기 시작한다.

 

중앙서버가 없는 상태에서 OT처럼 병합하면 어떤 문제가 발생할 수 있는지, 아까와 동일한 예시로 확인해보자.

 

문서에 HELLO라는 문자열이 있고,

1	2	3	4	5
H	E	L	L	O

 

A가 H를 지우는데, B가 E앞에 C를 입력한다.

이 과정을 순서대로 살펴보자.

 

1. A가 H를 지운다. (1번 인덱스를 지워!)

1	2	3	4
E	L	L	O

 

2. B가 E앞에(2번인덱스) C를입력한다.  

1	2	3	4	5
E	C	L	L	O

 

결과물은 ECLLO가된다! (박살이났다!)

 

정말 박살이 난 모습을 볼 수 있다. 이는 클라이언트마다, index 상태가 다르기때문이다.

어떻게 하면 이런 문제를 해결할 수 있을까?

 

유니크한 값과 순서

문자가 추가되면 인덱스가 변한다. CRDT는 이 문제를 피하기 위해 각 글자에 유니크한 값을 부여한다.

그리고 이 유니크한 값들의 순서에 따라 병합한다.

 

간단하게 예를 들면 이런식이다. 동일한 예시를 통해 CRDT의 작동방식을 이해해보자.

 

HELLO가 있다고 하면 각 글자에 유일한 id값을 부여하여 이렇게 만든다.

1	2	3	4	5
H	E	L	L	O

 

1. A가 H를 지운다. (1번 글자를 지워!)

2	3	4	5
E	L	L	O

 

2. B가 E앞에(2번이라는 id값을가진 글자) C를입력한다.  이때 C는, 지워진 H와는 다른 1.5라는 id값을 갖게 된다.

1.5	2	3	4	5
C	E	L	L	O

 

결과물은 CELLO가된다!

 

 

CRDT의 단점

물론 CRDT방식도 단점이 있다. 단점은 아래와 같다.

 

1. OT보다 많은 메모리를 사용하며, 이걸 실시간 통신으로 주고받아야한다.
   • 모든 글자가 그냥 글자가 아니라, id값을 가지며, 이 순서 역시 보장해야하므로 객체형태가 된다. 이것이 많아지면 많아질수록  메모리가 많이 필요하게된다.
2. P2P통신이 구성되어있어야한다.
   • 클라이언트간의 P2P통신은 흔한 환경은 아니다.
3. 실시간성이 모호해지고, 동기화 결과가 섞여버려 의도하지 않은 결과물이 나올 수 있다.
   • 이부분에 대해서는 유명한 그림이 있다.

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

 

우리의 선택

우리 서비스는 이미 Web RTC를 사용한 P2P환경이 구축되어있는 상황이고, 서버가 안그래도 매우 많은 상황이라, 더이상 서버를 늘리는 것은 어렵다고 판단했다.

따라서 CRDT로 구현하는 것을 택했다.

 

다음 게시글에서는 우리가 직접 CRDT를 구현한 방식과 겪었던 문제들에 대해 기술해 볼 것이다.