CRDT를 이해하기 위해 Martin Kleppmann 교수님의 CRDTs: The Hard Parts을 요약했습니다.

CRDT

위키에서는 CRDT를 다음과 같이 설명하고 있습니다.

CRDT(Conflict-free replicated data type)는 분산 컴퓨팅에서 네트워크의 여러 컴퓨터에 걸쳐 복제되는 데이터 구조이고 아래와 같은 장점을 가지고 있다.

독립적 업데이트: 응용 프로그램은 다른 복제본과의 조정 없이 각 복제본을 독립적으로, 동시에 업데이트할 수 있습니다.
자동 일관성 해결: 데이터 구조에 내장된 알고리즘이 일관성 문제를 자동으로 해결합니다.
강한 최종 일관성: 복제본들이 시간이 지나면서 서로 다른 상태를 가질 수 있지만, 결국에는 모든 복제본이 같은 상태로 수렴합니다.

분산 시스템에서는 여러 복제본에 동시에 업데이트가 발생할 때 일관성 문제를 일으킬 수 있습니다. 일반적으로, 이러한 문제를 해결하기 위해서는 업데이트의 일부를 삭제하거나 조정해야 할 수 있는데, CRDT는 이러한 문제를 해결하기 위해 모든 업데이트를 허용하고 나중에 자동으로 일관성을 복원할 수 있는 데이터 구조입니다.

CRDT의 두 가지 접근 방식

연산 기반 CRDT (Operation-based CRDT, CmRDT):
- 상태를 전파하는 대신, 업데이트 작업만 전송합니다. 예를 들어, 정수 값을 증가시키는 연산만을 전송합니다.
- 연산은 교환 가능(순서와 상관없이 결과가 동일)하지만, 중복 전송이나 순서 보장에 대한 보장이 필요합니다.
상태 기반 CRDT (State-based CRDT, CvRDT):
- 전체 상태를 전송하고, 수신한 상태를 병합하는 방식입니다. 병합 함수는 교환 가능, 결합 가능, 그리고 항등성이 있어야 합니다.
- 최근에 적용된 변경 사항만 전송하는 델타 상태 CRDT도 있습니다.

CRDTs: The Hard Parts

Google Docs

클라이언트가 데이터를 주고 받기 전에는 로컬 환경에 본인만의 인덱스를 갖고 편집을 합니다. 클라이언트에서 편집이 이뤄지면 서버로 정보를 보내는데, 편집되는 순서대로 서버에서 인덱스를 재조정하여 다시 클라이언트에게 데이터를 반환합니다. 이때, 각각의 클라이언트에 삽입되는 인덱스는 다릅니다. (이미지 참고)

하지만 OT방식은 서버를 통해 정보를 처리하기 때문에 두 장치간의 로컬 통신을 할 수 없는 문제가 발생합니다. (물리적으로 가까워도 멀리 존재하는 서버에 연결해야 하기 때문에 비효율적입니다)

그리고 OT는 인덱스 기반으로 동작하기 때문에 간단하게 정의될 수 있지만 인덱스 충돌이나 레이턴시에도 제약이 걸리게 됩니다.

OT를 대체하기 위해서

인덱스를 사용하지 않고
중앙 집중 서버가 존재하지 않는

**CRDT(Conflict-Free-Replicated Data Types)**를 사용하게 됐습니다.

CRDT는 두 글자를 머지했을 때, 인덱스가 아닌 유니크한 key를 통해

convergence를 달성하기 위해 서로 다른 두 클라이언트가 순서를 다르게 작업해도 같은 상태를 볼 수 있어야 합니다.

텍스트 편입 삽입 이후 이상현상 (Interleaving anomalies in text editing)

CRDT는 유니크한 키 값을 통해 충돌이 일어나지 않습니다. (하지만, 편집 시점을 알아야 하기에 0~1과 같은 유니크 숫자값을 쓰고 정렬해서 다시 보여줍니다)

하지만, 2명 이상의 유저가 동시에 편집을 하게 됐을 때에 1글자 단위 피드백이 이뤄지지 않는 이상 위의 이미지와 같이 병합하는 과정에서 이상하게 병합이 되게 됩니다.

interleaving anomalies 현상을 해결하기 위해 문자열을 조정하는 알고리즘들이 사용됩니다.

Martin Kelppmann 교수님께서 작성하신 논문인 Interleaving anomalies in collaborative text editors에서는 RGA(Replicated Growable Array)를 사용해 문자열을 조정하는데, 문자 삽입시 timestamp를 추가해 순서를 결정해 해결합니다.

Moving (reordering) list items

이렇게 두 개의 복제본이 있을 때, 하나의 복제본이 승리 해야만 하나의 최종 위치를 결정할 수 있습니다.

마찬가지로, CRDT에서는 정렬할 수 있는 고유한 식별자를(타임스탬프나 우선순위) 통해 최종적으로 하나의 식별자를 선택합니다.

또한, 이렇게 range에서의 이동이 일어날 때에, 이동 중에 발생한 변경사항을 CRDT에서는 처리하지 못합니다. (아직 미해결 문제라고 합니다)

이용자는 soy milk가 1행으로 이동하길 원하지만, milk만 1행으로 이동하고, soy m은 3열에 머무르게 됩니다.

따라서, 사용자는 기대한 결과를 얻을 수 없습니다.

관련된 정보는 Moving Elements in List CRDTs 논문에서 확인할 수 있습니다.

Moving subtrees of a tree

이렇게 하나의 트리에서 B와 C에 subtree를 생성하면 a, b, c, d와 같은 가능성이 생깁니다. (사실 a, b는 생성되지 않습니다. a는 복제를 만들지 않기 때문, b는 트리구조가 아니게 되기 때문입니다)

마찬가지로 타임스탬프와 같이 우선순위를 통해 해당 문제를 해결할 수 있습니다.

이렇게 두 개의 작업도, a, b는 순환이나 복제를 만들기 때문에 허용되지 않고 c, d와 같이 우선순위로 문제를 해결합니다. (뭐든 우선순위로 해결하고 있지만, 다른 사용자의 의도가 무시되는 문제가 있습니다)

timestamp 기반으로 undo와 redo를 통해 작업 순서를 정해 일관성을 유지합니다.

CRDT에서는 로컬에서 동작하기 때문에 변경사항을 먼저 적용하고 다른 복제본과 동기화 합니다. (로컬 작업의 즉시성을 반영하면서 원격작업과 병합시에 하나의 결과로 수렴합니다.

트리구조를 가진 데이터를 핸들링할 때에는 (파일 시스템 등) 트리의 규칙을(하나의 부모를 갖는다, 순환을 포함하지 않는다) 지켜서 연산들의 순서를 바꿔도 같은 결과를 얻을 수 있게 합니다.

이외로 로그나 메타 데이터 핸들링에 대해서 A highly-available move operation for replicated trees 논문에 자세히 설명돼있습니다.

Reducing metadata overhead of CRDT

CRDT에서는 인덱스 대신 사용하는 유니크 key값과 클라이언트를 구분할 수 있는 uuid, 그리고 유저가 편집한 데이터까지 여러 meta 데이터를 포함하고 있습니다. 실제로 편집에 필요한 데이터 외에도 많은 데이터를 보내기 때문에 이를 줄여야 합니다.

https://github.com/automerge/automerge

automerge에서는 변경사항만 보내고, 바이너리로 인코딩한 다음에 최소한의 메타데이터를 포함하여 데이터를 압축합니다. 문서가 커지더라도 매번 전체 상태가 아닌 변경 사항만 주고받고 누적된 변경 사항들은 효율적으로 압축되어 저장합니다.

편집 히스토리를 효과적으로 저장하기 위해 아래의 방식을 사용합니다.

모든 삽입 작업의 집합을 저장합니다
- 문자가 삭제된 경우, 그것을 표시합니다.
- 이는 삭제 연산을 별도로 저장하지 않고, 삽입된 문자에 삭제 표시를 하는 방식입니다.
각 작업에는 Lamport 타임스탬프 같은 ID가 있습니다
- 이는 카운터와 노드 ID/액터 ID의 쌍으로 구성됩니다.
- 이를 통해 작업의 순서와 출처를 추적할 수 있습니다.
각 삽입은 이전 작업(predecessor)의 ID를 참조합니다:
- 이는 RGA(Replicated Growable Array) 방식과 유사합니다.
- 이를 통해 삽입 위치를 정확히 추적할 수 있습니다.
작업들은 문서 순서대로 저장됩니다:
- 이는 문서의 최종 상태를 쉽게 재구성할 수 있게 해줍니다.

마치며

CRDT는 분산 시스템에서 데이터 일관성을 유지하기 위한 방법으로, 연산 기반 CRDT와 상태 기반 CRDT로 나뉘어집니다. CRDT는 독립적 업데이트, 자동 일관성 해결, 강한 최종 일관성을 제공하며, Google Docs와 같은 협업 툴에서 사용되고 있습니다. CRDT를 사용하면 여러 복제본 간의 동시 업데이트를 허용하고, 나중에 자동으로 일관성을 복원할 수 있습니다. 하지만 CRDT에는 여러 어려운 문제들이 존재하며, 이를 해결하기 위한 다양한 연구들이 진행되고 있습니다.

이렇게 CRDT에 대해 알아보았습니다. 효과적으로 데이터를 동기화하고 일관성을 유지하기 위해 이러한 데이터 구조를 사용해 문제를 해결하고 있다는 것을 배울 수 있었습니다. 특히 Klevvmann 교수님의 강의를 통해 CRDT의 어려운 부분들을 이해할 수 있었고, 이를 통해 분산 시스템에서 데이터 일관성을 유지하는 방법에 대해 더 깊이 이해할 수 있었습니다.

이제 Yorkie에서는 실제로 CRDT가 어떻게 사용되는지 다음 글에서 알아보겠습니다.