동시편집을 구현하는 다양한 기술(OT, CRDT, Delta‐State CRDT, YATA Algorithm)

동시편집

저작 도구라는 주제를 고른 가장 큰 이유는 동시편집이라는 기술적 도전을 하고 싶어서였습니다.

분산 시스템에서 여러 사용자가 동시에 데이터를 수정할 때 데이터의 일관성을 어떻게 유지할 수 있을까요?

이 흥미로운 질문에서 시작하여, 저희는 두 가지 주요 접근 방식인 OT와 CRDT에 대해 알게 되었습니다.

동시 편집을 구현할 수 있는 다양한 방법

OT와 CRDT를 설명하기 이전에 구체적인 예시를 통해 살펴보겠습니다.

사용자 A와 사용자 B가 "honeyflow"라는 문자열을 수정하려고 한다고 가정해보겠습니다.

사용자 A는 "최고"를 붙이고 싶고 사용자 B는 "🍯"을 붙이고 싶어합니다.
순서에 따라 결과는 "honeyflow 최고 🍯" 혹은 "honeyflow 🍯 최고"가 될 수 있습니다.
두 사용자는 "honeyflow 최고 🍯"를 원했습니다. 이런 일을 가능하게 하려면 어떻게 해야 할까요?

OT 방식

OT는 중앙 서버를 통해 동시성을 제어합니다.

서버가 모든 클라이언트의 작업을 관리하며 입력 순서에 따라 적절히 변형하여 처리합니다.

구글 문서나 MS 오피스 365와 같은 서비스들이 이 방식을 채택했습니다.

OT의 동작 방식은 다음과 같습니다:

사용자 A와 B는 "honyfow"라는 글자를 "honeyflow"로 만들고 싶어합니다.
"honyfow"라는 글자에 position을 구합니다.
"hon[e]yfow"를 넣기 위해서는 (0 based index) 기준으로 2:n, 3:y 사이에 'e'를 넣습니다.
"honyf[l]ow"를 넣기 위해서는 4:f, 5:o 사이에 'l'을 넣습니다.
서버에서 이를 통합해서 "honeyflow"가 완성됩니다.
'e'가 먼저 들어가면 'f'와 'o'는 각각 4,5가 아니라 5,6이 되는데, 이때 인덱스 위치를 수정해서 삽입합니다. 이러한 기술을 Operational Transformation(OT)이라고 합니다.

OT의 한계점

중앙 서버 병목 현상
- 모든 작업이 중앙 서버를 거쳐야 하므로, 사용자가 증가할수록 서버 부하가 급증합니다.
- 서버의 처리 지연이 전체 시스템의 응답성에 직접적인 영향을 미칩니다.
네트워크 지연에 취약
- 서버와의 통신이 지연되면 사용자 작업이 즉시 반영되지 않습니다.
- 일시적인 네트워크 단절 시 편집 기능이 제한될 수 있습니다.

CRDT의 장점과 접근 방식

CRDT는 변경사항을 순서와 상관없이 처리하면서도 동일한 최종 상태를 보장합니다.

OT가 인덱스로 이러한 부분을 관리하는 반면, CRDT는 각 개체에 유니크한 값을 부여하여 충돌을 방지합니다.

특히 분산 시스템에서 유용하며, 네트워크 지연이나 일시적인 장애가 있는 환경에서도 일관된 데이터 상태를 유지할 수 있습니다.

대표적인 예시로는 Figma가 있습니다.

Figma의 동시 편집 구현을 참고할 수 있습니다.

CRDT의 종류

State-based CRDT (CvRDT)
- 전체 데이터 상태를 주기적으로 동기화합니다.
- 각 노드가 전체 상태를 저장하고 교환합니다.
- 병합 함수를 통해 최종 상태를 결정합니다.
- 구현이 단순하지만 네트워크 대역폭 사용량이 많습니다.
예시:
- "honeyflow"의 각 문자에 고유한 식별자가 존재합니다.
- 사용자 A와 B가 각각 "honeyflow최고"와 "honeyflow🍯"으로 수정할 때
- 모든 ID를 정렬해서 최종 상태를 결정합니다.
- id1(honeyflow) < id2(최고) < id3(🍯) 순서라면 "honeyflow최고🍯"가 됩니다.
Operation-based CRDT (CmRDT)
- 변경 작업만을 전파하며, 작업들이 교환 법칙을 만족하도록 설계됩니다.
- 각 작업을 타임스탬프와 함께 전파합니다.
- 타임스탬프 순서로 작업을 적용하고 위치는 이전 문자를 기준으로 참조합니다.
- 네트워크 사용량이 적지만 구현이 더 복잡합니다.
- 작업의 인과성 보장이 필요합니다.

Delta-based CRDT

State-based와 Operation-based의 장점을 결합한 하이브리드 방식입니다.
각 문자마다 고유한 상태 정보를 유지합니다.
변경 사항만 델타로 전송하여 네트워크 사용을 최적화합니다.
주기적으로 전체 상태 스냅샷을 생성합니다.
작업의 순서 관계를 유지합니다.

예시 코드:

{
  "Delta 1": {
    "base": "honeyflow",
    "changes": [
      { "type": "insert", "id": "A1", "after": "w", "content": "최" },
      { "type": "insert", "id": "A2", "after": "A1", "content": "고" }
    ]
  },
  "Delta 2": {
    "base": "honeyflow",
    "changes": [
      { "type": "insert", "id": "B1", "after": "w", "content": "🍯" }
    ]
  }
}

Delta State CRDT를 구현하는 다양한 알고리즘

협업 텍스트 편집을 위한 CRDT 알고리즘은 RGA, Logoot/LSEQ, Woot, YATA 등 다양하게 존재합니다.

이 중에서 저희는 YATA 알고리즘을 기반으로 한 Yjs 라이브러리를 선택했습니다. 이제 YATA 알고리즘의 동작 방식을 자세히 살펴보겠습니다.

YATA 알고리즘: honeyflow 예시

1. Indexed Sequence CRDT

YATA에서 "honeyflow"라는 텍스트를 어떻게 표현하고 수정하는지 살펴보겠습니다.

ID 구조

type YataID = {
  clientID: number, // Peer의 고유 식별자
  clock: number, // 로컬 카운터
};

// "honeyflow" 각 문자의 ID 예시
const ids = [
  { clientID: 1, clock: 0 }, // 'h'
  { clientID: 1, clock: 1 }, // 'o'
  { clientID: 1, clock: 2 }, // 'n'
  { clientID: 1, clock: 3 }, // 'e'
  { clientID: 1, clock: 4 }, // 'y'
  { clientID: 1, clock: 5 }, // 'f'
  { clientID: 1, clock: 6 }, // 'l'
  { clientID: 1, clock: 7 }, // 'o'
  { clientID: 1, clock: 8 }, // 'w'
];

2. Interleaving 문제 해결

두 사용자가 동시에 "honeyflow" 끝에 "최고"와 "🍯"를 추가하는 상황을 살펴보겠습니다.

type Block = {
  id: YataID,
  leftOrigin: YataID | null, // 왼쪽 참조
  rightOrigin: YataID | null, // 오른쪽 참조
  content: string,
  deleted: boolean,
};

// 사용자 1: "최고" 추가
const block1 = {
  id: { clientID: 1, clock: 9 },
  leftOrigin: { clientID: 1, clock: 8 }, // 'w'의 ID
  rightOrigin: null,
  content: "최고",
  deleted: false,
};

// 사용자 2: "🍯" 추가
const block2 = {
  id: { clientID: 2, clock: 0 },
  leftOrigin: { clientID: 1, clock: 8 }, // 'w'의 ID
  rightOrigin: null,
  content: "🍯",
  deleted: false,
};

3. Block 데이터 구조

"honeyflow"의 전체 구조를 블록으로 표현:

class YataBlock {
  constructor(id, content, leftOrigin, rightOrigin) {
    this.id = id;
    this.content = content;
    this.leftOrigin = leftOrigin;
    this.rightOrigin = rightOrigin;
    this.deleted = false;
  }
}

// "honeyflow" 표현
const honeyflowBlocks = [
  new YataBlock(
    { clientID: 1, clock: 0 },
    "h",
    null,
    { clientID: 1, clock: 1 } // 'o'의 ID
  ),
  new YataBlock(
    { clientID: 1, clock: 1 },
    "o",
    { clientID: 1, clock: 0 }, // 'h'의 ID
    { clientID: 1, clock: 2 } // 'n'의 ID
  ),
  // ... 중간 문자들 ...
  new YataBlock(
    { clientID: 1, clock: 8 },
    "w",
    { clientID: 1, clock: 7 }, // 'o'의 ID
    null
  ),
];

4. 병합(Merging) 프로세스

"honeyflow최고"와 "honeyflow🍯"를 병합하는 과정:

function merge(localBlocks, remoteBlocks) {
  for (const remoteBlock of remoteBlocks) {
    // 1. "최고"와 "🍯"가 모두 'w' 다음에 위치
    if (!hasBlock(localBlocks, remoteBlock.id)) {
      // 2. 둘 다 leftOrigin이 'w'의 ID임을 확인
      const leftExists = hasBlock(localBlocks, remoteBlock.leftOrigin);

      // 3. clientID를 비교하여 순서 결정
      if (leftExists) {
        if (
          remoteBlock.id.clientID <
          localBlocks[localBlocks.length - 1].id.clientID
        ) {
          // "최고🍯" 순서로 정렬
          insertBlock(localBlocks, remoteBlock);
        } else {
          // "🍯최고" 순서로 정렬
          insertBlock(localBlocks, remoteBlock);
        }
      }
    }
  }
}

5. Delta-state 복제

"honeyflow"에서 "honeyflow최고"로 변경 시 전송되는 델타:

type Delta = {
  version: VectorClock,
  blocks: YataBlock[],
};

const delta = {
  version: new Map([[1, 10]]), // 클라이언트 1의 clock이 10
  blocks: [
    new YataBlock(
      { clientID: 1, clock: 9 },
      "최",
      { clientID: 1, clock: 8 }, // 'w'의 ID
      { clientID: 1, clock: 10 } // '고'의 ID
    ),
    new YataBlock(
      { clientID: 1, clock: 10 },
      "고",
      { clientID: 1, clock: 9 }, // '최'의 ID
      null
    ),
  ],
};

최종 결과물

두 변경사항이 모두 적용된 후의 상태:

const finalState = [
  { content: "최", id: { clientID: 1, clock: 9 } },
  { content: "고", id: { clientID: 1, clock: 10 } },
  { content: "🍯", id: { clientID: 2, clock: 0 } },
];

이러한 YATA의 구조를 통해:

문자열의 일관성 유지
삽입 시 충돌 없는 병합
네트워크 지연에도 안정적인 동작
효율적인 동기화

가 가능해집니다.

TEAM

DOCS

DEV-NOTES

> 모든 개발일지 확인하기

Provide feedback

Saved searches

Use saved searches to filter your results more quickly