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

동시편집

저희는 실시간 편집이 가능한 플랫폼 프로젝트로 동시 편집이 핵심 기능 중 하나입니다.

이러한 기능을 구현하기 위해 저희는 다양한 알고리즘을 고민해보았습니다.

동시 편집을 어떻게 하면 구현할 수 있을까요 ?

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

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를 구현하는 다양한 알고리즘

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

이 중에서 저희는 YATA 알고리즘을 기반으로 한 Yjs 라이브러리를 선택했습니다.

Yjs를 구성하는 YATA 알고리즘의 동작 방식을 자세히 살펴보겠습니다.

Indexed Sequence CRDT

YATA는 Indexed Sequence CRDT 입니다.

Indexed Sequence CRDT는 insert/delete 연산을 임의의 순서로 정의할 수 있는 데이터 구조를 의미합니다.
이러한 구조는 순서 정보를 유지하면서 여러 클라이언트의 동시 작업 처리를 위해 고안된 방식입니다.

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'
];

Sequence Number LSeq: 두 이웃의 ID를 기준으로 새로운 ID를 생성합니다. RGA: 전역적으로 증가하는 카운터 사용합니다. YATA: 각 피어가 독립적으로 카운터를 유지하며 증감합니다. Replica ID Sequence Number만으로는 중복을 방지할 수 없으므로, 피어의 고유 ID와 결합해 고유성을 보장합니다.

2. Interleaving 문제 해결

Interleaving은 여러 피어가 같은 인덱스에 삽입 연산을 수행할 때, 요소가 섞이는 문제입니다.
예: 원래 문서: honey ! A: honey flow🐝 , B: honey flow🍯 동기화 후: honey flow🐝flow🍯, honey flow🍯flow🐝f

문제 원인

각 삽입 연산 간의 의존성을 나타낼 충분한 메타데이터가 없어서 발생합니다.

해결책

RGA:

이전 요소의 ID(predecessor)를 연산에 포함해 삽입 순서를 추적합니다.
그러나 시작 부분 삽입(prepends) 등에서 여전히 한계가 있습니다.

YATA:

이전 요소(predecessor)와 다음 요소(successor) 정보를 함께 사용합니다.
이를 left/right origins로 정의해 더 강력한 순서 추적 가능합니다.

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
  ),
];

YATA는 delta-state CRDT로, 데이터를 배열 형태로 관리하며 각 블록(block)이 요소를 나타냅니다.

연산

삽입 (Insert)

삽입 위치를 계산 → 좌/우 이웃의 ID 확인 → 새 블록 생성 후 삽입.

삭제 (Delete)

삭제된 블록은 tombstone 처리(값을 None으로 설정).

병합 (Merge)

좌/우 origins를 이용해 충돌을 해결하고, 새 블록을 적절한 위치에 삽입.

삽입 순서 결정

좌/우 origins를 기준으로 삽입 가능한 경계를 설정.
동시에 삽입된 요소의 순서는 피어 ID를 비교해 결정.

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);
        }
      }
    }
  }
}

병합 시 각 블록의 좌/우 origins를 기준으로 충돌 해결합니다.
누락된 블록은 병합하지 않습니다.
병합 순서를 정할 때, 피어 ID가 높은 블록을 뒤쪽에 배치합니다.

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 } },
];

위 예시는 honeyflow 최고 🍯 에 대한 예시입니다.

Vector Clock: 각 피어에서 가장 높은 Sequence Number를 추적.
Delta 생성: Vector Clock 기준으로 변경된 블록과 tombstone된 블록의 ID만 포함.
Delta 병합: Delta의 새 블록과 tombstone 데이터를 기존 배열에 병합

참고

Insertion: ID, 내용(content), 위치(position) 속성을 가지며, 편집 내용이 어떤 위치에 추가되어야 하는지 정의함.
Deletion: 특정 Insertion의 ID를 숨김 처리하며, 편집 기록 자체는 삭제되지 않음.
Edit은 절대 삭제되지 않음: 삭제되지 않는 기록을 통해 어떤 아이템이 어디에 있어야 하는지 항상 확신할 수 있음.
Tombstone: 성능 최적화를 위해 Insertion이 축약(truncated)되며, 완전히 삭제된 경우 ID와 위치만 유지하는 마커로 사용됨.
Update: 실제로는 Deletion + Insertion으로 처리되며, 기존 값을 삭제하고 새로운 값을 삽입하는 방식으로 구현됨.

참고 링크: (yjs fundamental)[https://medium.com/dovetail-engineering/yjs-fundamentals-part-1-theory-232a450dad7b]

이러한 YATA의 구조를 통해:

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

가 가능해집니다.

TEAM

DOCS

DEV-NOTES

> 모든 개발일지 확인하기

Provide feedback

Saved searches

Use saved searches to filter your results more quickly