CRDT
동시 편집 기술
네이버 부스트캠프 그룹 프로젝트에서 코드를 공동 편집 할 수 있는 기술이 필요했다.
이 글에서는 공동 편집 기술이 무엇이며 왜 우리 팀이 CRDT 방식을 선택했는지에 관하여 이야기 할 것이다.
공동 편집 기술
공동 편집 기술은 서로 다른 사람이 같은 공간에서 동시에 편집할 수 있도록 해주는 기술이다.
공동 편집이 적용된 대표적인 예시로는 노션과 피그마가 있다.
그렇다면 CRDT 이외의 다른 공동 편집 기술에는 어떤 것이 있을까?
그리고 왜 CRDT를 사용하게 되었을까?
OT
(1989 ~ 2006)
CRDT 이전에 사용했던 기술이며 Google Docs, MS Office 등에서 사용되었다.
OT 방식의 핵심은 "서버가 병합을 수행"하는 것이다.
현재 문자의 상태가 HELO라고 해보자.
A 사용자는 HELO에서 3번째 인덱스에 L을 입력하고
B 사용자는 HELO에서 4번째 인덱스에 !를 입력한다.
그렇다면 두 사용자는 각각 HELLO와 HELO!라는 문자열을 갖게 된다.
이렇게 수정한 두 문자열을 서버로 전송되며 서버는 두 문자열을 병합한다.
만약, 서버가 A 사용자의 입력을 먼저 수행한다면
- HELO (처음)
- HELLO (A 사용자의 입력: 3번 인덱스에 L을 입력)
- HELL!O (B 사용자의 입력: 4번 인덱스에 !를 입력)
위와 같은 결과가 나오게 될 것이다.
이를 해결하기 위해서는 2번을 수행하고 난 뒤 3번 작업의 동작을 변형해야 한다.
(위의 예시 3번에서 5번 인덱스에 !를 입력)
이것이 Operation Transformation 즉, OT 기술이다.
다시 한 번 정리하면 OT의 순서는 다음과 같다.
- 각 사용자는 각자 변경사항을 서버로 전송
- 서버는 1번의 결과를 순차적으로 병합
- 결과를 각 사용자에게 반환
| H | E | L | L | O | ! |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 |
문제점
이러한 OT 방식의 단점은 서버를 사용하기 때문에 과부하에 취약하다는 것이다.
또한, 당연하게도 중앙 집중식 서버가 반드시 있어야 한다는 문제점이 있다.
CRDT
(2006 ~)
OT 방식 이후에 나오게 된 공동 편집 기술이다.
OT와의 가장 큰 차이점은 다음과 같다.
- P2P
- 교환법칙
그렇다면 OT는 교환법칙이 성립하지 않는가?
정답은 "그렇다"이다.
앞서 봤듯이 OT 방식은 순서대로 병합을 하며 이전 동작에 따라 다음 동작의 변환(transform)이 되기 때문이다.
따라서, 앞 동작이 다음 동작에 영향을 미친다고 할 수 있으며 각 연산의 순서에 따라 결과가 달라질 수 있다.
CRDT는 교환법칙이 성립한다.
각 동작의 순서와 상관없이 변경 사항만 같으면 같은 상태이다.
OT 방식에서 발생한 문제점은 각 글자의 인덱스를 부여했다는 것이다.
배열과 같은 인덱스를 사용하게 되면 각 입력에 따라 인덱스가 변한다는 문제점이 발생했던 것이다.
CRDT는 이를 해결하기 위해 각 개체(글자)를 유니크한 값으로 간주한다.
아까 봤던 예시를 CRDT 버전으로 다시 보자.
HELO라는 문자열은 OT 방식과 같이 각각 0, 1, 2, 3 인덱스를 갖는다고 가정하자.
(CRDT에서 인덱스를 부여하는 방식은 그때그때 다를 수 있다)
이때,
A 사용자는 L과 O 사이에 L을 입력하고
B 사용자는 O 뒤에 !를 입력한다.
기존 OT 방식이었다면 L뒤에 L이 삽입되며 그 뒤에 있는 O의 인덱스를 변화시켰을 것이다.
하지만, CRDT에서는 2번 인덱스의 L과 3번 인덱스의 O 사이에 2.5번 인덱스를 갖는 L을 삽입한다.
또한, 마지막에 추가된 !의 경우에는 4라는 인덱스를 새롭게 부여할 수 있을 것이다.
결과적으로 아래와 같은 값을 갖게 될 것이다.
| H | E | L | L | O | ! |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 2.5 | 3 | 4 |
위에서 봤던 OT방식과 다르게 기존에 존재하던 글자들의 인덱스는 변하지 않았다.
이렇듯 각 글자를 유니크하게 간주했기 때문에 충돌이 일어나지 않는다.
3번 인덱스에 새로운 글자가 추가된다고 인덱스가 변하지 않는다는 것이다.
또한, 각 글자는 유니크하기 때문에 어떠한 순서로 병합을 하더라도 같은 결과가 나오게 된다.
이러한 특징을 이용하여 클라이언트에서 직접 병합을 수행하더라도 같은 결과를 만들어 낼 수 있기 때문에 (단, 같은 CRDT 알고리즘을 사용해야 할 것) 중앙 서버가 필요하지 않다.
문제점
물론 CRDT에도 문제점이 있다.
A는 L과 O 사이에 K를 삽입하고
B는 L과 O 사이에 P를 삽입한다.
위의 경우, 삽입에 대해 양 옆의 index의 중간 값을 사용하도록 했다면 K와 P는 둘 다 2.5라는 인덱스를 갖게 될 것이다.
서로 다른 글자가 같은 인덱스를 갖기 때문에 충돌이 났다고 표현하며 충돌이 발생하게 되면 의도하지 않은 문자열로 병합이 되는 경우가 발생한다.
이를 해결하기 위한 다양한 알고리즘들이 있다.
결론
우리 그룹은 CRDT 방식을 사용하기로 했다.
WebRTC를 구현하는 과정에서 이미 P2P 통신을 연결해뒀고, WebRTC의 데이터 채널을 이용한다면 영상, 음성 이외의 다른 데이터도 주고받을 수 있었기 때문이다.
이미 서버를 여러대 사용중인 상태에서 또 다른 서버를 추가하는 것도 부담이 되었고 최근 사용되는 공동 편집 기술이 CRDT를 기반으로 만들어져있기 때문이다.
[참고자료]
