[CRDT 구현 여정기 - 1] CRDT를 사용하고 구현방식을 정해보자

hyonun·2024년 12월 29일

Nocta - CRDT구현

목록 보기

1/5

2024년 10월, 네이버 부스트캠프 9기를 진행하며
실시간 저작도구를 만드는 그룹프로젝트에 참여하였습니다.
우리 팀의 이름은 Glassmo로, 글래스모피즘이라는 디자인 컨셉에서 착안해 왔습니다.
자세한 내용은 Notion에서 확인 가능합니다!

우리팀의 목표

저희 Glassmo팀은 저작도구를 만들어보기로 모인 팀이였습니다.

저작도구란, Front-End 개발자에겐 커다란 도전과도 같은 주제인데요.

도전을 해보고자 모인 4명이였기에, 라이브러리의 도움없이 저작도구의 기능들을 직접 구현해보자 마음먹었습니다.
1주차 글래스모 팀원들 표정

1주차 글래스모 팀원들 표정

하지만 어떤 레퍼런스없이, 라이브러리없이 구현해야 한다는 말은 특정 기술의 이론을 익혀 이를 코드화를 하고 동작까지 확인해야하는 정말 많은 과정들이 숨어있었습니다.

그래서 어느정도 기술적 도전을 하다가, 우리는 6주 라는 제한이 있으니 불가능하다 판단되면 그때 라이브러리를 써보자! 로 정했고 우리는 그 기간을 1~2주차로 정했습니다.

이때 저희 글래스모팀은 퍼즐방식으로 개발을 해보았습니다.

💡퍼즐방식?

구현을 위주로 프로토타입을 제작한다.
4명 각자 정해진 파트를 맡아서 진행한다.
이후 병합하는 과정에서 서로가 익힌 기술을 소개하며 기술공유를 진행한다.
퍼즐 방식을 도입한 이유는
각자 맡은 파트가 존재하여 OwnerShip 부여 가능
기술 공유 시 팀원들의 이해도를 일치시키기 위한 효과적인 커뮤니케이션 환경을 조성할 수 있습니다

라는 장점이 있다고 생각하여 도입했습니다.

그렇게 1주차는 프로젝트 기획 및 프로토타입 개발, 2주차는 각자 맡은 프로토타입 개발 병합에 나섰습니다.

이렇게 2주차까지는 우리가 현실적으로 구현할 수 있는 목표인지 가늠해 보기로 했습니다.

🔥 부담을 가지지 말자, 도저히 안되겠으면 과감하게 라이브러리를 사용!

그래서 이번 칼럼은 저에게 주어진 CRDT를 구현하는 과정에 대해 이야기 해보려고 합니다.

CRDT란 뭐지?

저희는 notion like app 을 목표로 하였기에 실시간 편집기능이 중요했습니다.

이를 위해서 실시간 편집 기능에 사용되는 방법들을 조사해 보았고, 크게 OT와 CRDT 두개로 줄일 수 있었습니다.

자세한 사항은 여기서!

CRDT(Conflict-free Replicated Data Type)

선, 문자와 같은 기본 요소의 순서를 구현하는 것을 시퀀스 CRDT로 사용되고 있는 것을 알았으며 그 중, 우리는 연산기반 CRDT를 사용하는 것이 효율적이라 판단하여 활용하게 되었습니다.

출처: https://fireheal.tistory.com/118,
https://www.bartoszsypytkowski.com/operation-based-crdts-arrays-1/

연산기반 CRDT의 장점은, 서버의 부하가 적고 사용자에게 빠른 동기화를 가져줄 수 있습니다만,

구현이 어렵다.
메모리 처리비용이 많이 증가하다

라는 문제를 가지고 있습니다.

구체적으로, 어떤점이 구현이 어려운지 확인해보겠습니다.

1. 툼스톤(TombStone)

이 연산기반 CRDT의 특징중에 TombStone 이라는 개념이 있습니다.

각 노드에 isDeleted를 포함하여 확인하기 때문에 tombstone 이라고 하는 더미 node들이 잔뜩 남게 됩니다.

실제로는 노드를 삭제하지 않지만, 삭제 flag를 표시하고 반영하지 않는 형태입니다.

그렇기에 이 TombStone을 관리하는 로직이 필요합니다.

2. 인덱스

인덱스에서도 고려해야할 부분이 있는데요.

0 1 2 3 4
a b c d e

0 인덱스와 1 인덱스 사이에 문자 인덱스를 만든다고하면,0.5 이런식으로 중간지점에 오도록 인덱스를 만드는 것을 추천합니다.

0 0.5 1 2 3 ..
a  f  b c d ..

0과 1사이에 랜덤하게 숫자를 생성하면 안되나?

그 이유는 추후 0.9 1 인덱스 사이에는 0.95 가 들어가고, 1 과 0.95 사이에는 0.975 가 들어가고 … 점점 이렇게 인덱스의 확장성이 떨어지는 문제가 생기게 됩니다.

0.9 0.95 0.975 0.9725 0.93625 ....   1
 a    b    c      d     e      ..   g

만약 a와 g 사이에 문자가 1000자이상 들어가게 된다면.. 그 인덱스의 길이는..어마어마 해지는 상황이 되는 것이죠!

하지만 0.5로 중간값으로 오게 하는것도 덜 발생하게 할 뿐 CRDT의 근본적 문제를 해결할 수 없습니다.

이를 보완하기 위한 알고리즘

으로.. 다양한 알고리즘들이 거론되었습니다.

RGA
YATA
Logwoot

등등이 존재하지만, 각자 역시 단점을 가지고 있습니다.

우리는 이 알고리즘중 비교적 구현난이도가 쉬운 RGA를 사용하기로 했습니다.

RGA와 YATA 톺아보기

RGA 구조

RGA는 기본적으로 단방향 LinkedList로 이루어져있습니다.

0->1->2
A->B->C 

head: A노드

A노드 :
- 현재 정보
  - 'A'
- 다음 노드
  - B노드

여기에 논리적 시간 개념을 도입해서 CRDT의 입력 연속성을 지키고 고유한 id를 형성하도록 만들었습니다.

논리적 시간이란?

A(1분) : 지금은 1분입니다. 다음은 2분이에요.
B(4분) : 지금 4분이야. A야. 그러니 다음은 5분이겠지? 너도 지금 시계 맞춰놓으렴.
A(5분) : 넵!

위 방식으로 각자 +1씩 증가하는 counter clock 을 가집니다. 그리고 A와 B가 가지고 있는 시계를 동기화를 시킵니다.

0->1->2
A->B->C 

head: A노드

A노드 :
- ID
  - clock : 1
- 현재 정보
  - 'A'
- 다음 노드
  - B노드

하지만 정말 우연으로 동시에 입력을 한다면 어떻게 될까요?

1. A유저가 clock 1 인덱스로 'a'를 입력했습니다.
2. B유저가 clock 1 인덱스 'b'를 입력했습니다.

그러면 ab 가 되어야 할까요 ba 가 되어야할 까요?

이 만일의 사태에서의 예외처리를 위해 client number 를 도입했습니다.

서버에서 websocket연결이 될때마다 순서대로 클라이언트에게 번호를 부여하는 것이죠.

그래서 번호가 작은 client가 먼저 입력되도록 나름의 룰을 만들어 두었습니다.

A유저가 먼저 접속했다면, ab, B유저가 먼저 접속했다면 ba가 되는 것이겠죠.

이를 위해 client 번호를 추가하여

0->1->2
A->B->C 

head: A노드

A노드 :
- ID
  - clock : 1
  - client : 1
- 현재 정보
  - 'A'
- 다음 노드
  - B노드

id로는 clock과 client를 고유값으로 가지고, 현재 정보와 다음 노드를 가지는 하나의 글자 노드가 완성되었습니다.

양방향 링크드 리스트로 확장

하지만 단방향 LinkedList의 경우 이전에 있는 노드를 알기 힘듭니다.

그도 그럴 것이 자신 이전 노드의 정보를 가지고 있지 않아서, 매번 while 문을 통해 찾아야 하기 때문이죠.

그래서 다음노드값 뿐만 아니라 이전노드값도 저장하도록 확장하였습니다.

이를 통해 쉽게 삽입, 삭제를 진행할 수 있죠.

최종 모습

0->1->2
A->B->C 

head: A노드

B노드 :
- ID
  - clock : 2
  - client : 1
- 현재 정보
  - 'B'
- 다음 노드
  - C노드
- 이전노드
  - A노드

이렇게 노드를 정의하고 난 다음은, CRDT 동작에 필요한 메소드만 만들면 해결이였습니다.

insertByIndex : index값이 주어지면 그부분에 삽입 연산
insertById : id(clock, client number)주어지면 그 노드에 삽입연산
findByIndex : index값이 주어지면 그 노드 반환
deleteNode : id(clock, client number)주어지면 그 노드 삭제 
spread : head부터 시작해서 링크드리스트 글자들 배열로 반환...
...

이렇게 어느정도 필요한 메소드들을 선언해두고 CRDT동작을 확인하였습니다.

갑자기 닥쳐온 수많은 문제들..

좋아 이제 다된것같은데.. 엥 이 버그들은 대체 뭐지..?

하지만 바로 저희 동작대로 동작하지 않았습니다.

버그

- 글자를 입력했는데 캐럿이 움직이지 않는다.
- 한글입력이 제대로 반영되지 않는다.
- 복사 붙여넣기 할때 제대로 되지 않는다.
- 커맨드 입력(컨트롤 A, 쉬프트 누르고 화살표이동)이 되지않는다
...

가장 중요한 caret부분이 제대로 동작하지 않았습니다.

Caret 이란? 키보드를 입력하려고할때 현재 입력되는 위치가 어디인지 알려주는 | 녀석.

각 입력, 삭제마다 caret을 하나하나 관리해줘야 한다는 사실에 저희들은 절망했고, 도전했습니다.

const selection = window.getSelection();

각 입력, 삭제마다 캐럿의 위치를 브라우저에서 제공하는 API를 통해 getSelection 으로 가져오고 매번 업데이트를 해줬습니다.

다른 사람이 입력할때는 캐럿을 어떻게?
→ 이부분은 추후 CRDT칼럼에서 좀더 깊게 다루겠습니다.

그렇게 단순한 입력동작은 되니 NestJS와 Websocket와의 연동을 테스트해보게 되었습니다..!

hyonun

비전공자 + 반도체 경력2년의 IT 개발자 도전기~

다음 포스트