실시간 동시편집 구현 연대기 (2) - CRDT를 직접 구현해보자.

이 글은 아래의 글 부터 이어집니다.

https://0422.tistory.com/332

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

 

 

우리 프론트엔드 팀은 우선은 CRDT 구현에 도전해보기로 했다.

굉장한 기술적 도전이 될것이라 판단했기때문이다.

 

어떻게 구현하지?

구현하기위해서는 필요한 것들부터 알아야한다.

CRDT, 즉, 클라이언트 측에서 원활하게 상호 병합을 문제없이 하기위해서는 어떤 조건을 만족해야할까?

 

1. A 사용자에서 병합하나, B 사용자에서 병합하나 그 결과가 완벽하게 동일해야한다.
2. 여러 사용자가 사용할 수 있으므로, 여러개의 병합 상황과 서로 시간대가 다른 메시지가 있어도 동일하게 병합되어야한다.
   • 예를 들어, A라는 사용자가 B, C,D와 통신하여 메시지를 병합하는 경우를 살펴보자.
     • C와 D가 동시에 메시지를 보낸다.
     • A는 D의 메시지가 먼저 도착했고, B는 C의 메시지가 먼저 도착했다.
     • 이후, A는 C의 메시지를 받았고, B는 D의 메시지를 받았다.
     • 그럼에도 A와 B의 메시지 상태는 동일해야한다.(동일하게 병합되어야한다.)

그렇다면 이것을 어떻게 구현할 수 있을까?

우리는 여타 다른 CRDT처럼 글자만의 유일한 ID와 글자의 순서를 유지하는 형태로 구현해보고자 했다.

하지만, 유일한 ID와 순서를 유지하는 방법이 여러가지가 있었고, 여기서 많은 고민을 했다.

식별자를 어떤식으로 부여해야 유일할지가 고민이었고, 또한, 순서와 식별자를 통합으로 관리할지, 따로 관리할지 역시 고민거리였다.

 

유일한 ID와 글자 순서를 보장하기위한 시도

1. 유사배열과 유리수 인덱스

처음에는 배열형태로 구현할까 했었다. 다만, 정말 배열은 아니고, 유리수 키값에 대해 글자 값을 갖는 형태이다.

이렇게 하면 좋은점이 유리수 대소에 의해 인덱스가 고정되므로, 인덱스는 유일한 ID이자 순서를 제어할 수 있는 방법이된다.

 

하지만, 이 방식에는 두가지 정도의 문제가 존재했다.

1. OT방식을 CRDT에 적용시켰을때 나타나는 문제처럼, index로 관리하게되면 삽입/삭제시 인덱스가 밀리거나 제거되어 문제가 발생할 수 밖에 없다.
2. 유리수를 어떻게 지정할것인가? 

index이자 key	0	1
글자	A	C

 

위와같이 'AC'라는 문자열이있는데 B를 넣는다고하면 어떻게 id를 부여해햐 유일한 값이될까?

단순히 0과 1의 중간값인 0.5를 부여했다가는 사용자가 많아지는 경우 0.5라는 키를 가진 글자가 통신에 참여한 사용자 수만큼 늘어날 수 있게 된다.

 

따라서 이런 방식으로는 불가능하다 판단했다.

 

 

2. 배열 + 유일한 ID값 (인덱스+ 시간값 보정 + 클라이언트 소켓 id)을 통한 순서제어

글자의 순서를 제어해야하기때문에, 최대한 배열형태를 유지하고싶었다.

왜냐하면, 순서를 보장하기위해 연결리스트로 구현하게되면 요소를 찾거나, 특정 위치에 있는 요소를 찾기 위해 기본적으로 순회를 포함하게 되기 때문이었다.

 

 

그래서 배열의 형태를 유지하되, 인덱스의 한계를 극복하고자, 인덱스를 시간값과 web RTC signaling서버에 사용되는 socket id를 사용해서 보정하여 순서를 제어하게 만들었다.

token하나의 타입을 아래와 같이 정의했다.

interface CRDTToken {
  index: number; //index
  letter: string; //글자
  time: number;  //글자가 생성된 시간을 담을 프로퍼티
  id: string; //socket ID
}

 

그리고 CRDTToken 배열을 가지고 있을 CRDT객체를 만들어주었다.

삽입되는 경우만 고려하여 코드를 가져왔다.

export default class CRDT {
  private CRDTTokens: CRDTToken[]; //글자배열
  private id: string; // 소켓 id

  constructor(id: string) {
    this.CRDTTokens = [];
    this.id = id;
  }
  
  localInsert(selectionStart: number, letter: string, time: number): CRDTRemoteToken {
  // selectionStart는 삽입될 위치다.
    const result = { index: selectionStart, letter, time, id: this.id };
    this.CRDTTokens.splice(selectionStart - 1, 0, result);

    console.log(this.CRDTTokens);

  }


  remoteInsert(remoteToken: CRDTToken) {
  // webRTC를 통해 받은 remoteToken을 삽입시키고, index, time, id를 통해 보정한다.
    this.CRDTTokens.splice(remoteToken.index - 1, 0, remoteToken);
    this.CRDTTokens.sort((a, b) => {
      if (a.index !== b.index) return a.index - b.index; // index 기준으로 오름차순 정렬
      else if (a.time !== b.time) return b.time - a.time; // time 기준으로 오름차순 정렬
      else return a.id.localeCompare(b.id); // id 기준으로 오름차순 정렬
    });

    console.log(this.CRDTTokens);
  }
  
  ...
  
  toString() {
    return this.CRDTTokens.reduce((text, token) => text + token.letter, '');
  }
 }

 

문제발생

이렇게 작성한 코드를 바탕으로 print(1234)상태에서 <test>를 중간에 끼워넣어 print<test>(1234)로 만드는경우 해당 부분을 받는 클라이언트에서 글자가 깨지는 문제가 발생했다.

해당 원인을 살펴보자.

이는 <test>의 index가 (1234)의 index와 동일하기 때문이다.

 

입력전 (1234)의 상태

시간은 Date.now지만, 편의상 자연수로 표기했다.

index	5	6	7	8	9	10
time	1	2	3	4	5	6
letter	(	1	2	3	4	)

 

이상태에서 <test>를 추가해보자.

 

입력되는 <test>의 상태

역시 시간을 자연수로 표기했다.

index	5	6	7	8	9	10
time	6	7	8	9	10	11
letter	<	t	e	s	t	>

 

이제 병합될때 정렬되는 형태를 확인해보자.

index정렬 -> index가 같으면 time으로 정렬 -> time이 같으면 id로 정렬(생략)

이되면 이런식으로 작동하게된다.

index	5	5	6	6	7	7	8	8	9	9	10	10
time	1	6	2	7	3	8	4	9	5	10	6	11
letter	(	<	1	t	2	e	3	s	4	t	>	)

 

결국은 기존의 index때문에 글자가 밀리게 되는 것이다.

기존의 index를 변경(새롭게 인덱스를 부여)하지 않는 이상, 이 순서 문제를 해결할 수 가 없었다.

인덱스를 새롭게 부여하는경우 삽입하는데 O(N), 받은 후 정렬하는데 O(NlogN), 글자보정하는데에 O(N)으로 연산이 많이 필요해지게된다.

 

또한 현재 index가 정말 순서를 보장하기보다는 id로써의 역할이 강해져버려서 다른 방식을 생각하게 되었다.

 

연결리스트로 순서관리 + 유일한 ID값(시간 + socketID) 

어떻게 배열을 사용하지 않고 순서를 보장할까 고민하다 결국 연결리스트를 도입하기로 결정했다.

연결리스트로 구현하게되면 index가 필요하지 않게 된다.

"Hello" 라는 문자열이 있는 경우, H->e->l->l->o의 형태로 저장이 되고, 중간에 삽입이 되는 경우 노드의 포인터만 조정해주기 때문이다.

 

삽입시 로직

1. insert(cursorPositon, letter)의 형태와 같이 입력하는 커서 위치에 글자를 입력받는다.
2. 연결리스트를 순회하며 해당 위치에 있는 요소 앞에 있는 요소를 찾아낸다.
3. 새로운 요소를 만들고, 해당요소의 다음 요소로 기존 요소를 붙여준다.

커서 위치 2에 e를 추가하는 상황이라고 해보자. (숫자는 순서를 표기하기위해 임의로 표기했다.)

 

1. 2번 위치의 앞요소인 'H'를 가져온다.
2. 'e'를 하나의 node로 만든다. (time과 socket ID를 추가한다.)
3. 'H'요소의 다음요소로 'e'요소를 붙이고, 'H'요소의 기존 다음요소를 'e'의 다음 요소로 만든다.

삭제시 로직 역시, 요소를 가져와서 포인터를 조정해가는과정 이므로 생략하겠다.

 

실제 코드를 보자.

import { Node } from './Node';

export default class CRDT {
  id: string;
  head: Node | null;
  length: number;
  #cursorPosition: Node | null;

  constructor(id: string) {
    this.id = id; // socket id
    this.head = null;
    this.length = 0;
  }

  insert(letter: string, index: number, wordLength = 1) {
    const newNode = new Node(this.id, letter, Date.now());
    newNode.nextNode = this.searchNodeByIndex(index);  //새 요소의 다음 요소로 붙이기

    if (index - 1 <= 0) { //현재 위치가 0인경우 head를 교체하거나 붙임
      this.head = new Node(this.id, '', 0); 
      this.head.nextNode = newNode;
    } else {
      this.searchNodeByIndex(index - 1)!.nextNode = newNode;  //이전요소의 다음요소로 새요소 붙이기
    }
    this.length++;
  }
  ...
   searchNodeByIndex(index: number): Node | null { //요소찾기
    let current = this.head;
    let count = 0;

    while (current !== null) {
      if (count === index) return current;

      count++;
      current = current.nextNode;
    }

    return null;
  }
  }

 

병합시키기

드디어 대망의 병합이다.

어떻게 병합을 할지 고민하다 P2P연결에서 주고받는 데이터를 변경하는 형태로 구현하기로 결정했다.

 

기존의 배열형태에서는 remote 클라이언트에서 글자가 추가된 경우에 그 글자요소만 전송하고, 글자를 특정 인덱스에 집어넣는 형태로 구현되어있었다.

이때 사용하는 특정 인덱스가 문제다. 특정 인덱스이기 때문에 인덱스가밀리고, 글자가 깨지는 원인이된다.

또한, 우리는 이제 연결리스트이므로 특정 인덱스가 없다. 

 

이 문제를 해결하기위해 P2P에서 주고받는 데이터를 특정 글자 요소와 인덱스에서 전체 연결리스트 요소로 변경했다.

 

이렇게 했을때 좋은점은 크게 두가지이다.

1. 요소가 그냥 추가되거나, 삭제되는 경우, 받은 연결리스트로 교체하면 따로 병합을 진행시키기 않아도 된다는점
2. 덕분에 복사/붙여넣기로 입력, 삭제하는 경우, 동일한 로직을 적용시킬 수 있음

하나씩 살펴보자.

요소가 추가되거나, 삭제되는경우의 병합 (길이가 다른 경우)

아래의 상황을 살펴보자.

Hello에서 ello로 변경되어야 하는상태다.

 

이렇게 수신되는 경우 굳이 ello와 Hello를 비교해보지 않아도 된다.

연결리스트의 길이만 비교한후에 head의 next포인터만 변경해주면 되는 것이다.

 

반대의 경우도(삽입되는 경우) 마찬가지이다.

충돌이 일어나는 경우 (길이가 같은 경우)

하지만, 길이가 같은경우에는 비교해야할 필요가 있다.

이런 경우, 두개의 연결리스트를 동시에 순회하며, 3가지 요소를 확인하고, 병합된 요소를 새로운 연결리스트로 만들어주었다. 

기존의 연결리스트를 활용하기에는, 동일한 위치의 요소를 확인할 수 없기 때문이었다. (병합해서 하나의 길이가 늘어나면 정확한 위치가 아니게됨)

 

1. 글자가 같은지 확인한다.
2. 다른경우 time이 빠른 요소를 앞에 붙이고, time이 느린 요소를 뒤에 붙인다.
3. time마저 같은경우 socket ID의 대소를 비교하여 앞뒤를 정렬한다.

이 세가지 요소를 고려함으로써 어느 클라이언트에서 요소들을 비교하던 동일한 방식으로 병합시킬 수 있게 된다.

 

아래와 같이 "Hello"와 "Cello"를 비교해야하는 경우를 확인해보자.

'H'와 'C'를 비교한다.

둘의 글자가 다르므로, 둘의 시간을 비교한다.

'H'는 51초에 생성되었고, 'C'는 52초에 생성되었으므로 'H'를 먼저 붙이고 'C'를 붙인다.

이후에 오는 요소들은 동일하므로, 요소를 붙여준다.

 

이와같은 방법으로 충돌을 해결할 수 있었다.

실제 코드를 보자.

  merge(recievedLinkedList: CRDT) {
    if (recievedLinkedList.length === this.length) { //길이가 같은 경우 병합처리
      this.merging(recievedLinkedList);
    } else { //다르면 head교체
      this.head = recievedLinkedList.head;
      this.length = recievedLinkedList.length;
    }
  }

 

병합 로직도 살펴보자. (실험 상태였어서 코드가 매우 더럽다)

  merge(recievedLinkedList: CRDT) {
    if (recievedLinkedList.length === this.length) {
      this.merging(recievedLinkedList);
    } else {
      this.head = recievedLinkedList.head;
      this.length = recievedLinkedList.length;
    }
  }

  private merging(recievedLinkedList: CRDT) {
    const newCRDT = new CRDT(this.id);

    let localPointer = this.head?.nextNode;
    let remotePointer = recievedLinkedList.head?.nextNode;
    let counter = 1;

    while (localPointer && remotePointer) {
      if (
        localPointer.letter === remotePointer.letter &&
        localPointer.identifier.id === remotePointer.identifier.id &&
        localPointer.identifier.time === remotePointer.identifier.time
      ) {
        newCRDT.insert(localPointer.letter, counter++);
      } else {
        if (localPointer.identifier.time < remotePointer.identifier.time) {
          newCRDT.insert(localPointer.letter, counter++);
          newCRDT.insert(remotePointer.letter, counter++);
        } else if (localPointer.identifier.time > remotePointer.identifier.time) {
          newCRDT.insert(remotePointer.letter, counter++);
          newCRDT.insert(localPointer.letter, counter++);
        } else {
          if (localPointer.identifier.id < remotePointer.identifier.id) {
            newCRDT.insert(localPointer.letter, counter++);
            newCRDT.insert(remotePointer.letter, counter++);
          } else {
            newCRDT.insert(remotePointer.letter, counter++);
            newCRDT.insert(localPointer.letter, counter++);
          }
        }
      }

      localPointer = localPointer.nextNode;
      remotePointer = remotePointer.nextNode;
    }

    this.head = newCRDT.head;
    this.length = newCRDT.length;
  }

 

커서 이동 문제

글자는 이제 잘 병합이 되는데... 커서가 밀리는 현상이 발생했다.

asdf| 와 같이 마지막에 커서가 있고, 앞에 "vvvv"를 추가하는경우 vvvv|asdf 처럼 커서가 밀리게되는것이다.

이 문제를 해결하기 위해 병합할때에 커서 포지션을 조정해주는 형태를 택했다.

커서를 가장 최근에 입력한 요소 뒤로 고정시키는 것이다.

 

그러려먼 가장 최근에 입력한 요소를 기록해두면된다.

crdt클래스에 node 타입의 cursorPositon을 추가해주었고, 입력/삭제, 그리고 병합시에 조정해주는 로직을 추가했다.

export default class CRDT {
  id: string;
  head: Node | null;
  length: number;
  #cursorPosition: Node | null;

  constructor(id: string) {
    ...
    this.#cursorPosition = this.head;
  }

  insert(letter: string, index: number, wordLength = 1) {
    ...
    this.#cursorPosition = newNode;
  }
  ...
  }

 

또, 이걸 실제 코드에서의 index로 변환시켜주는 메서드도 필요했다.

병합하는 경우, index를 찾아서 입력창의 커서를 이동시켜주어야하기때문이다.

  getIndexByNode(node: Node) {
    let current = this.head;
    let count = 0;

    while (current !== null) {
      if (
        current.letter === node.letter &&
        current.identifier.id === node.identifier.id &&
        current.identifier.time === node.identifier.time
      )
        return count;

      count++;
      current = current.nextNode;
    }

    return null;
  }
  
  get cursorPosition(): number | null {
    if (!this.#cursorPosition) return null;

    return this.getIndexByNode(this.#cursorPosition); //해당 요소의 index를 찾아온다.
  }

 

삭제되는 경우 고려

그런데 문제가, 로컬에서 마지막으로 입력한 문자가 삭제되는 경우가 있을 수 있다는 점이었다.

'asdf'를 입력해서 adsf| 인 상태인데 remote에서 f를 삭제하면 어떻게 해야하는가...?

이런경우에는 커서가 s로 갈 수 있도록 했다.

이에 cursorPosition 을 set해주는 setter가 필요하다.

  set cursorPosition(index: number) {
    const prevNode = this.searchNodeByIndex(index);

    this.#cursorPosition = prevNode;
  }

 

 

병합시 커서 조정해주기

아래와 같이 RTC Connection의 Data channel에서 메시지를 받는경우, 커서를 조정해주었다.

 const handleRecieveCodeMessage = (event: MessageEvent<string>) => {
    const remoteCRDT = JSON.parse(event.data);

    const prevCursorPosition = crdt.current.cursorPosition as number; //마지막에 입력한 요소
    const prevCursorCandidateNode = crdt.current.searchNodeByIndex(prevCursorPosition - 1); //삭제되는 경우 고려
    crdt.current.merge(remoteCRDT);

    if (crdt.current.cursorPosition) { //로컬에서 마지막으로 입력한 요소가 삭제되지 않음
      setCursorPosition(crdt.current.cursorPosition);
    } else { //로컬에서 마지막으로 입력한 요소가 삭제된 경우
        const cursorPosition = crdt.current.getIndexByNode(prevCursorCandidateNode);
        crdt.current.cursorPosition = cursorPosition; 
        setCursorPosition(cursorPosition); //text입력하는 cursor 조정
      }
    }

    setPlainCode(crdt.current.toString());
  };

 

이렇게 CRDT를 구현할 수 있었다!!!

 

한계와 대응

한계 - 고려하지 못한 실시간

그러나, 간간히 글자가 깨지는 문제가 발생했다.

혹은, 중간에 글자가 깨졌다가 100ms내외로 복구되는 현상이 계속해서 발생했다.

해당 문제를 디버그하려고 노력했고, 많은 시간을 투자했으나 정확하게 어떤 문제인지 확인할 수 없었다.

 

대응 - 라이브러리 도입

우리는 프로젝트를 진행하고있다. 정해진 기한안에 기능을 완성해야하는것이다.

따라서 우리 팀은 프로젝트의 기능을 완성하는것이 우선이라 판단했고, 라이브러리를 적용하여 온전한 기능을 제공할 수 있도록 방향성을 잡게되었다.

 

라이브러리 도입에 대한 고민

라이브러리도 여러가지가 있었다.

원래도 라이브러리 도입을 백업용으로 생각은 하고있었다. 사실 crdt를 완벽하게 구현하려면 논문정도의 지식이 필요하기 때문이다....

yjs, automerge중에 고민을 하고 있었는데, 커서 문제를 해결하는 과정에서, 라이브러리를 사용한다면 yjs를 사용해보자고 합의하게되었다.

yjs는 정확하게 우리와 동일한 커서 문제를 고민했다.

공유중인 데이터에서 자신의 위치를 데이터를 기준으로 변환시키는 고민을 했던 것이다. (relativePosition -> absolutePosition)

따라서 우리팀은 최종적으로는 Yjs를 도입해 CRDT 기능을 완성시켰다.

다음 게시글에서는 어떻게 Yjs를 적용시켰는지 더 살펴보자.