들어가며
크래프톤 정글 9기 최종 프로젝트에서 실시간 캔버스 협업 기능을 구현하게 되었습니다. 모든 사용자가 동일한
데이터를 일관되게 동기화할 수 있어야 했고, 이 과정에서 Yjs가 문제를 효과적으로 해결해줄 수 있는 도구임을
알게 되었습니다.
이를 계기로, Yjs가 어떤 원리에 기반해 실시간 동기화를 가능하게 하는지 깊이 있게 학습해보고자 했습니다.
CRDT
"CRDT(Conflict-free replicated data type)는 분산 컴퓨팅에서 네트워크의 여러 컴퓨터에 걸쳐 복제되는 데이터 구조이고 아래와 같은 장점을 가지고 있다."
분산 시스템에서는 여러 복제본(replica)에서 동시에 업데이트가 발생할 경우, 데이터 일관성 문제가 발생할 수 있습니다. 일반적으로 이러한 문제를 해결하려면, 일부 업데이트를 삭제하거나 조정하는 방식으로 충돌을 수동으로 해결해야 합니다.
하지만 CRDT는 모든 업데이트를 수용하면서도, 나중에 충돌 없이 자동으로 일관된 상태로 수렴할 수 있도록 설계된 데이터 구조입니다.
CRDT의 종류
Operation-based CRDT (Op-based, CmRDT)
- 데이터를 수정하면, 변경된 내용(연산)만 다른 노드에 전파합니다.
- 모든 노드는 그 연산을 같은 순서로 적용해야 데이터가 일관되게 유지됩니다.
예를 들어, +1, +1, -1 같은 연산 순서가 바뀌면 최종 결과가 달라질 수 있기 때문에, 메시지 순서(인과 관계) 를 지켜야 합니다.
State-based CRDT (CvRDT)
- 변경할 때마다 다른 노드에 전체 데이터 상태를 전송합니다.
- 받은 쪽은 이 상태를 기존 상태와 병합 함수(merge)를 통해 합칩니다.
- 연산 순서나 타이밍이 달라도, 결과는 항상 동일 합니다.
예를 들어, A의 카운터 상태가 5, B의 상태가 7이면, 병합 함수가 둘 중 더 큰 값 7을 선택하여 일관성 있게 유지됩니다.
CRDT 심화 분석
Google Docs
Google Docs와 같은 실시간 협업 툴은 여러 사용자가 동시에 문서를 수정해도 충돌 없이 병합할 수 있어야 합니다. 이를 가능하게 하는 기술이 바로 OT(Operational Transformation, 연산 변환) 입니다.
OT는 변경 내용을 연산(Operation) 으로 전파하고, 다른 사용자의 변경과 충돌하지 않도록 변환(transform) 하여 적용하는 방식입니다. 이 방식은 중앙 서버가 각 클라이언트의 연산을 조정함으로써, 일관된 결과를 유지합니다.
OT의 동작 방식 간단 예시
OT에서의 연산 변환 예시
위 그림은 OT(Operation Transformation)의 대표적인 사례를 보여줍니다.
두 명의 사용자가 동시에 동일한 문자열 "HELO"를 수정하고 있습니다.
- 사용자 A 는 3번 인덱스에
"L"을 삽입하려고 했습니다. - 사용자 B 는 4번 인덱스에
"!"를 삽입하려 했습니다.
하지만 두 사용자의 편집은 서로 영향을 주기 때문에, 각 연산은 상대편의 작업을 고려해 변환(transform) 되어야 합니다.
- 서버는 사용자 A의
"L"삽입 연산을 먼저 적용합니다. - 이어서 사용자 B의
"!"삽입 연산을 원래 인덱스 4 에서 인덱스 5 로 위치를 조정하여 처리합니다.
이처럼, OT에서는 동시 발생한 연산의 순서를 조정하고 위치를 변환하는 작업이 필수적입니다.
이를 통해 각 사용자의 문서가 동일한 최종 결과를 갖게 됩니다.
하지만 OT 방식은 다음과 같은 문제점이 있습니다.
- 모든 연산을 중앙 서버가 조정해야 하므로, 서버 부하가 매우 큽니다.
- 사용자 수가 많아지거나 텍스트 변경이 빈번해질 경우, 서버 과부화로 인해 실시간성이 떨어질 수 있습니다.
- 네트워크 지연, 순서 오류 등이 발생할 경우 연산 적용 실패 가능성도 존재합니다.
이러한 이유로, 최근에는 OT보다 CRDT 방식을 선호하는 추세입니다.
CRDT는 어떻게 충돌 없이 병합할까?
CRDT에서의 연산 변환 예시
앞서 OT에서는 모든 연산을 서버가 받아 순서대로 처리해야만 일관성을 유지할 수 있었습니다. 하지만 CRDT는 다릅니다.
CRDT는 각 데이터 조각(문자 등)에 고유한 식별자(ID)를 부여합니다. 예를 들어, 아래 그림에서는 "H", "E", "L", "O" 각각에 0.2, 0.4, 0.6, 0.8이라는 값이 부여되어 있죠.
이런 식으로 데이터 간의 상대적 위치 만 알 수 있으면, 그 사이에 새로운 값을 삽입할 때도 충돌 없이 고유한 위치를 만들 수 있습니다.
텍스트 편입 삽입 이후 이상현상
CRDT는 대부분의 경우 충돌 없이 데이터를 병합할 수 있지만, 모든 상황이 완벽하게 해결되는 것은 아닙니다.
특히 두 명 이상의 사용자가 동시에 같은 위치를 수정하거나, 범위를 이동하는 복잡한 작업이 겹치는 경우, 다음과 같은 문제가 발생할 수 있습니다.
- Interleaving Anomlies (문자열 섞임 문제)
아래 그림처럼 두 사용자가 동시에 문장을 수정했을 때, 입력된 텍스트가 서로 엇갈려(interleaved) 병합되는 현상이 발생할 수 있습니다.
CRDT에서의 텍스트 편입 삽입 이후 이상현상
이러한 문제는 1글자 단위의 피드백이 아닌 이상 자연스럽게 해결되지 않으며,
이를 방지하기 위해 문자열의 삽입 위치를 조정하는 알고리즘이 함께 사용됩니다.
CRDT에서도 삽입 위치를 결정하기 위해 정렬 가능한 고유 식별자(타임스탬프, 우선순위 등)를 사용합니다.
동시에 같은 위치에 삽입이 발생하면, 우선순위에 따라 어떤 연산이 ‘이긴다’고 판단해 병합합니다.
하지만 이 과정에서 다른 사용자의 의도가 일부 무시될 수 있는 한계도 존재합니다.
- 이동(Move) 연산의 여러움
사용자가 "soy milk"를 한 줄 위로 이동하고 싶었지만, "milk"만 이동되고 "soy"는 원래 위치에 남아 있는 결과가 나올 수 있습니다.
이는 CRDT가 범위 단위의 이동 중 발생한 중간 상태 변경을 완전하게 추적하거나 병합하기 어려운 구조이기 때문입니다.
현재까지도 이 문제는 완전히 해결되지 않은 분야이며, 연구가 계속되고 있습니다.
마치며
CRDT는 분산 시스템에서 데이터 일관성을 유지하기 위한 대표적인 방법으로,
연산 기반 CRDT(Op-based) 와 상태 기반 CRDT(State-based) 로 나뉘며,
독립적인 업데이트, 자동 충돌 해결, 강한 최종 일관성(Strong Eventual Consistency) 을 보장합니다.
이러한 특성 덕분에 CRDT는 Google Docs와 같은 실시간 협업 툴에서도 사용되고 있으며,
여러 복제본 간에 동시 업데이트를 허용하면서도 충돌 없이 자동으로 일관성을 복원할 수 있습니다.
하지만 모든 기술이 그렇듯, CRDT 역시 완벽하지는 않습니다.
interleaving 문제, 트리 구조의 병합, 이동 연산 처리 등 해결되지 않은 기술적 과제들이 존재하며,
이를 극복하기 위한 다양한 연구와 개선이 현재도 활발히 진행되고 있습니다.
이번 글을 통해 CRDT의 개념과 구조를 이해하고,
데이터 동기화 문제를 해결하기 위한 접근 방식으로서의 가능성과 한계를 함께 살펴볼 수 있었습니다.
다음 글에서는 실제 프로젝트에서 사용한 Yjs가
CRDT를 어떻게 구현하고 활용하는지, 그리고 실시간 협업 기능을 어떻게 제공하는지 구체적으로 알아보겠습니다.