드디어 RGA의 실제 코드를 작성하고 CRDT를 적용 후, 실시간 통신이 되는지 확인해볼 차례입니다.

CRDT RGA로 간단 구현해보기

연산 기반 통신 모습

기존에는 content (string) 과 같은 녀석을 단순히 넘겨주고 그걸 읽어서 화면에 반영했다면,

이제는 서버에 주고받는 녀석들이 CRDT형태의 연산으로 바꿔줘야합니다.

CRDT는 데이터 타입임을 잊지말자!

간단한 CRDT 통신 플로우

클라이언트에 CRDT연산이 일어났을때는 localUpdate 를,

그 연산을 다른 클라이언트가 수신했을때는 remoteUpdate 를 실행 해줘야 합니다.

연산 상태를 필요에 따라 서버에서 상태를 저장 하거나 검증해야합니다.

이부분에서 응용 할 수 있는 부분이

1. redo/undo
2. history
3. 데이터 무결성 검증

등이 있습니다.

redo/undo 가능해..?

하지만 현재는 일정상 남는 시간에 redo/undo를 구현하기로 결정했습니다.

우리팀은 CRDT기능 구현과 기능 개선에 시간을 두기로 했기 때문이죠.

이제

프로토타입 + 우리가 설계한 CRDT 라이브러리인 테스트 환경을 만들어 보았습니다.

CRDT 테스트 환경 세팅

• client의 숫자 id를 세팅해주었습니다.

• server에서 각 클라이언트의 고유한 socket.id 값에 따라 Map을 이용해 매핑하였고. 삭제될 경우 Map에서 삭제 됩니다.

private clientIdCounter: number = 1;
private clientMap: Map<string, number> = new Map(); // socket.id -> clientId

이제 textarea에서 추가되는 요소들을 CRDT화 해줘야 합니다.

---

CRDT 라이브러리 제작

Node로 만든다~

👌 Node화 조건

1. 이중 링크드 리스트를 사용한다.
   1. RGA는 단방향 Linked-List로 삽입하기 이전의 위치만 확인하고 값이 들어간 것을 확인한다.
      1. insert, delete 할때 쉽지않다.
   2. 하지만 좀 더 개선된 버전인 YATA에서는 양방향을 확인하여 데이터 무결성을 검증할 수 있다.
2. 각 노드는 고유한 식별자를 가진다.
   1. uuid가 될 수도 있고 랜덤한 값이 될 수도 있다.
   2. 여기서는 서버에서 부여한 client의 number ID와 논리시계를 사용한다.
3. 논리적 시간과 클라이언트 아이디로 분산 환경에서 순서를 결정한다.
   1. 1시 1분에 A는 0인덱스에 ABC를 입력했다.
   2. 1시 2분에 B는 0인덱스에 123을 입력했다.
   3. 서버에서 입력이 들어왔을때 1시1분 > 1시 2분 으로 시간 순으로 먼저 나누고,
   4. 만약 동일한 시간에 왔을때는 우선순위를 A>B 로 비교하여 A에게 우선순위를 할당한다.

---

먼저 텍스트를 가지는 노드 클래스를 정의합니다.

Node.ts

• 각 노드의 id 같은경우는 clock과 client의 번호로 정한다. clock은 논리적 시간이다.
  • 논리적 시간? 클라이언트와 서버간에 동시에 사용하는 변수를 쓰는 것이다. 클라이언트에서 2라는 시간인데 서버에서 3이면 서버가

    야! 지금 시간 3이야. 그 다음 시간은 4고. 그러니까 너도 4해!

    라며 논리적 시간을 맞춰준다.
    

특이점은 다음 노드를 가리키는 것으로 NodeId를 가지는 것이고, node 들은 다음에 나올 nodeMap이라는 Map 자료구조 안에 Map[nodeId] = Node 형태로 매핑되어 있습니다.

LinkedList.ts

⇒ LinkedList로 명명하고 재사용을 하려고했지만, 추후 명시성을 고려하여 BlockLinkedList 및 TextLinkedList로 나누어 명명하였습니다.

Crdt.ts

• CRDT 전역에 쓰이는 논리시계와 가장 최근에 데이터를 반영한 클라이언트 번호(서버 전파를 위해) 그리고 링크드리스트 정보를 가지고 있습니다.
• CRDT는 하나의 클래스요소로 각 CRDT의 인스턴스 정보를 가지고 있습니다.

아래는 간단한 구조 다이어 그램입니다.

이렇게 다중형태로 동작하도록 구조를 작성했습니다.

이제 간단한 유저 시나리오 동작을 정해서 동작을 구현해보겠습니다.

---

동작 구현

0. 시작

1. client와 server가 연결되면, 서버에서 clientid를 만들고 연결된 client에 id를 할당해준다.
2. client는 할당 받은 id로 client local에서 CRDT를 생성한다.
3. server는 몽고DB에 저장된 CRDT상태를 serialize(직렬화)하여 client에 전송한다.
4. client는 수신 받은 직렬화된 CRDT로 LinkedList로 역직렬화를 한 뒤, client의 local에 저장한다.

1. 텍스트 입력

1. 유저가 contentEditable="true” 인 상태의 요소에 입력을 한다.
2. handleInput 함수가 실행되며 변경 전, 변경 후값을 비교하여 변경이 일어난 index번호와 삭제연산인지, 삽입연산인지 판단한다.
   1. 삽입연산
      1. 클라이언트 로컬의 CRDT에 로컬삽입연산을 해준다.
      2. 로컬삽입연산이 끝나면, 서버에 삽입연산을 전파한다.
      3. 서버는 서버의 CRDT에 삽입연산을 진행한 뒤, 업데이트된 CRDT를 몽고DB에 저장한다.
      4. 그리고 서버는 나머지 클라이언트에게 삽입 연산을 전파한다.
      5. 현재 로컬의 CRDT를 기반으로 content를 업데이트 한다.
   2. 삭제연산
      1. 클라이언트 로컬의 CRDT에 로컬삭제연산을 해준다.
      2. 로컬삭제연산이 끝나면, 서버에 삭제연산을 전파한다.
      3. 서버는 서버의 CRDT에 삭제연산을 진행한 뒤, 업데이트된 CRDT를 몽고DB에 저장한다.
      4. 그리고 서버는 나머지 클라이언트에게 삭제 연산을 전파한다.
      5. 현재 로컬의 CRDT를 기반으로 content를 업데이트 한다.

2. 변경 수신

1. 다른 클라이언트가 값을 입력했다.
2. 서버로부터 연산이 수신된다.
   1. 삽입연산
      1. 로컬 CRDT에 원격삽입 연산을 진행한다.
      2. 현재 로컬 CRDT를 기반으로 content 를 업데이트 한다.
   2. 삭제연산
      1. 로컬 CRDT에 원격삭제 연산을 진행한다.
      2. 현재 로컬 CRDT를 기반으로 content 를 업데이트 한다.

위처럼 간단한 동작 시나리오를 설정해 주었습니다. handleInput 을 활용하여 간단한 삽입연산을 확인해 보겠습니다.

const currentContent = block.crdt.read();
const caretPosition = getAbsoluteCaretPosition(element);

• 현재 컨텐츠와 캐럿 포지션을 구합니다.

if (newContent.length > currentContent.length) {
...
} else if (newContent.length < currentContent.length) {
...

위와 같은 방식을 통해 삭제, 삽입연산을 판단하고 이에 맞게 remoteInsert, remoteDelete등을 실행합니다.

---

예외처리가 필요한 시나리오들

사용자의 copy&paste
글자를 블럭채로 옮기기
여러글자를 지워버리기
브라우저 내부 기능으로 특수효과 적용

사용자의 copy&paste

각 유저의 key입력에 따라 paste될때 paste되는 문자열들을 CRDT에 사용하는 node 화 하여 반영해야한다. 이럴때 한번에 여러개의 글자를 묶어서 (링크드리스트로) target 인덱스에 넣는 방법이 필요할 것 같다.

글자를 블럭채로 옮기기

블럭을 하나의 CRDT화 해서 순번을 바꾸는 형식으로 처리한다.

여러글자를 지워버리기

현재 전부 선택됐을때 배열에 넣어서 순차적으로 선택된 부분을 localDelete와 remoteDelete가 될 수 있도록 처리한다.
또는 한번에 삭제하는 알고리즘을 작성한다. (처음과 끝부분을 linkedList로 이어버려서 삭제 처리)

브라우저 내부 기능으로 특수효과 적용

 e.preventDefault();

등을 통해 브라우저 기능을 지우고, 우리들의 기능으로 사용하도록 전부 커스텀한다.

또는 브라우저기본기능을 이용가능하게 한 상태에서 우리 기능을 그위에 커스텀해서 올린다. (이경우 디버그 봐야할 것들이 많아진다.)

---

테스트 영상

아직은 삽입연산만 된다.

하지만 한계단을 올라갔다~!! (야호~)

🕵️‍♀️ 문제

삭제연산하면 인덱스-1에러 등등 잔뜩 나는게 함정입니다..

아마 현재 삭제위치를 잘 판단하지 못하는 듯합니다.

낙관적 업데이트로 클라이언트와 로컬의 CRDT상태를 일치시키는것이 쉽지않은 듯합니다.

하지만 차근차근 삽입, 삭제, 예외처리를 차근차근 잡아간다면 가능할 것으로 보입니다..!!

다음에는 삭제연산과 CRDT를 안정적으로 적용하고, 리팩토링과 api등을 확실히 정할 예정입니다.