2011년 3월, INRIA 소속 연구자 Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski는 연구보고서 RR-7687을 통해 “Conflict-free Replicated Data Types”라는 이름의 자료구조 계열을 처음으로 공식 정의했습니다. 이 논문은 결합법칙·교환법칙·멱등법칙이라는 세 가지 대수적 성질만 만족하면, 여러 복제본이 서로 통신을 조율하지 않고도 결국 똑같은 상태로 수렴한다는 것을 수학적으로 증명했어요. Syncthing처럼 서버 없이 여러 기기가 파일을 동기화하는 도구를 쓰다 보면 한 번쯤 궁금해지는 지점이 있습니다. 중앙 서버 없이도 여러 복제본이 어떻게 결국 같은 데이터로 수렴할 수 있을까요?
CRDT는 무엇을 해결하려는 자료구조인가
CRDT는 네트워크가 끊기거나 지연되는 환경에서도 각 복제본이 즉시 쓰기를 받아들이면서, 나중에 그 갱신 내역이 어떤 순서로 합쳐지든 항상 동일한 최종 상태로 수렴하도록 설계된 자료구조예요. 논문은 이 성질을 “Strong Eventual Consistency(SEC, 강한 최종적 일관성)“라는 이름으로 공식화하는데, 같은 갱신 내역을 전달받은 두 복제본은 반드시 동등한 상태(state equivalence)에 도달해야 한다는 조건입니다. 기존의 낙관적 복제 시스템들은 충돌이 나중에 발견되면 롤백하고 합의(consensus) 절차를 거쳐 재조정하는 방식이 많았는데, 논문 서론에서는 이런 방식의 대표적 실패 사례로 아마존 쇼핑카트의 동시성 이상 현상을 직접 언급해요. CRDT는 애초에 “충돌이 발생할 수 없는” 자료구조를 설계해서 이 롤백 과정 자체를 없애버리자는 제안이고, 그래서 이름에도 “Conflict-free(충돌 없는)“라는 표현이 들어가 있어요.
CvRDT: 상태 전체를 주고받아 병합하는 방식
CvRDT(Convergent Replicated Data Type)는 각 복제본이 로컬 상태를 통째로 상대방에게 보내고, 받은 쪽이 자신의 상태와 병합(merge)하는 상태 기반(state-based) 방식이에요. 논문은 이 병합이 항상 안전하게 수렴하려면 상태 공간이 “단조 준격자(monotonic semilattice)“를 이뤄야 한다고 정의합니다. 상태들 사이에 최소상한(least upper bound, LUB)을 구하는 연산 ⊔가 존재해서, 두 복제본의 상태를 병합하면 항상 두 상태를 모두 포함하는 최소상한 상태로 합쳐지고, 갱신을 거칠 때마다 상태가 단조적으로만 증가한다는 조건이에요. 예를 들어 각 복제본이 자기 몫만 증가시키는 카운터(G-Counter)는 병합할 때 항목별로 더 큰 값만 취하면 되므로 이 조건을 자연스럽게 만족해요. 증가와 감소를 모두 지원하는 PN-Counter, 원소 추가만 가능한 G-Set, 추가와 삭제를 함께 지원하는 OR-Set 같은 구체적 자료구조들이 논문에서 이 방식으로 설계돼요.
CmRDT: 연산만 전파하는 방식
CmRDT(Commutative Replicated Data Type)는 상태 전체 대신 개별 연산(operation)만 다른 복제본에 전파하고, 각 복제본이 그 연산을 자신의 로컬 상태에 적용하는 연산 기반(operation-based) 방식이에요. 이 방식이 수렴하려면 병렬로 실행된(concurrent) 연산들끼리 순서를 바꿔 적용해도 결과가 같아야 한다는 교환법칙(commutativity)만 만족하면 되는데, 대신 논문은 “신뢰할 수 있는 인과 순서 방송(causally-ordered broadcast)” 프로토콜이 밑단에 있다고 가정해요. 즉 인과관계가 있는 연산들(happened-before 관계)은 모든 복제본에서 반드시 같은 순서로 도착해야 하고, 동시에 일어난 연산들만 임의의 순서로 도착해도 괜찮다는 전제예요. 논문 3.2절은 흥미롭게도 CvRDT와 CmRDT가 표현력 면에서 동등하다는 것도 증명하는데, 임의의 CvRDT는 CmRDT로 에뮬레이션할 수 있고 그 반대도 가능하다는 정리(Theorem 3, Theorem 4)를 실어요. 결국 상태를 통째로 보낼지 연산만 보낼지는 구현 방식의 선택이지, 수렴을 보장하는 근본 원리는 같다는 뜻이에요.
수렴을 보장하는 세 가지 대수적 조건
CRDT가 조율 없이도 항상 같은 상태로 수렴하는 이유는 결합법칙, 교환법칙, 멱등법칙이라는 세 가지 성질을 만족하도록 자료구조와 연산을 설계했기 때문이에요. 결합법칙(associativity)은 연산을 어떤 순서로 묶어 적용하든 결과가 같다는 성질이고, 교환법칙(commutativity)은 연산의 적용 순서 자체를 바꿔도 결과가 같다는 성질이며, 멱등법칙(idempotence)은 같은 연산이나 상태를 중복으로 적용해도 결과가 변하지 않는다는 성질이에요. 네트워크가 메시지를 중복 전달하거나(멱등법칙이 이를 방어), 서로 다른 복제본에 갱신이 서로 다른 순서로 도착하거나(교환법칙·결합법칙이 이를 방어) 하는 실제 분산 환경의 골칫거리들이, 이 세 성질만 만족하면 수학적으로 문제가 되지 않는다는 게 논문의 핵심 통찰이에요. 다만 논문 3.3절은 이 수렴 조건이 “직관적으로 옳은” 병합 결과를 보장하는 건 아니라는 점도 분명히 짚어요. 예를 들어 같은 원소를 한쪽에서는 추가하고 다른 쪽에서는 삭제하는 동시 연산이 있을 때, 추가가 이기게 할지 삭제가 이기게 할지는 응용에 따라 다르게 정의할 수 있는 설계 선택의 문제이지, CRDT라는 성질 자체가 자동으로 “옳은” 답을 정해주지는 않아요.
실제로 CRDT를 쓰는 시스템들
CRDT는 논문 발표 이후 실제 프로덕션 시스템에 여럿 채택됐는데, 대표적으로 Riak이 2012년경 카운터·집합·맵 같은 데이터 타입을 CRDT 기반으로 구현하면서 초기 상용 사례로 꼽혀요. Redis Enterprise도 지역 간(geo-distributed) 복제 기능에 CRDT 기반 데이터 타입을 적용해서, 여러 리전에서 동시에 쓰기가 들어와도 중앙 조율 없이 값이 수렴하도록 지원해요. 실시간 협업 편집 라이브러리인 Yjs와 Automerge 역시 CRDT를 기반으로 여러 사용자가 동시에 같은 문서를 편집해도 브라우저 간에 서버 개입 없이 내용을 병합하는 데 쓰이고 있어요. 조금 결이 다른 사례로는 Matrix 프로토콜의 이벤트 그래프(Matrix Event Graph)가 있는데, Matrix 진영이 스스로 “이건 CRDT다”라고 공식 표방하는 건 아니지만, 외부 학계 분석(KIT 소속 Florian Jacob 등)에서 이 이벤트 그래프의 상태 해석(state resolution) 방식을 연산 기반 CRDT로 모델링할 수 있다고 분석한 연구가 나와 있어요. 즉 CRDT는 특정 라이브러리 하나가 아니라, 이미 여러 분산 시스템의 핵심 설계 원리로 자리 잡은 개념이라는 게 확인돼요.
Syncthing은 CRDT를 쓰고 있을까
정확히 말하면 Syncthing은 CRDT를 쓰지 않고, 훨씬 단순한 최종 수정 우선(Last-Write-Wins) 방식으로 파일 충돌을 처리해요. Syncthing 공식 문서를 확인해보면, 두 기기에서 같은 파일이 동시에 수정돼 내용이 실제로 달라졌을 때는 더 오래된 수정 시각을 가진 파일을 충돌 파일로 표시해서 .sync-conflict-<날짜>-<시각> 접미사를 붙여 별도로 보존하고, 수정 시각까지 같으면 기기 ID 값이 더 큰 쪽의 파일을 충돌 파일로 취급해요. 이건 CRDT 논문이 말하는 준격자 기반 병합이나 교환법칙을 만족하는 연산 전파와는 다른 접근이에요. CRDT라면 두 변경 내역을 자료구조 차원에서 병합해 하나의 수렴된 상태를 만들어내지만, Syncthing은 파일 콘텐츠 자체를 병합하지 않고 “어느 쪽을 원본으로 남길지”만 타임스탬프로 결정한 뒤, 진 쪽은 지우지 않고 별도 파일로 남겨서 사용자가 직접 병합하도록 넘겨요(위 문서에서 확인한 대로 삭제와 수정이 충돌하면 수정이 항상 이기도록 하는 예외 규칙도 있어요). 다시 말해 Syncthing이 CRDT 논문의 수학적 병합 이론을 그대로 구현한 건 아니고, “조율 없이도 각자 로컬에서 즉시 쓰기를 받아들인다”는 철학적 지향점만 CRDT와 같은 방향을 바라보고 있는 셈이에요. 그래서 파일처럼 이진 콘텐츠를 다루는 도구에서는 CRDT식 자동 병합보다 “충돌 파일을 남기고 사람이 판단”하는 방식이 여전히 현실적인 절충안으로 쓰이고 있다는 걸 확인할 수 있어요.
결론
CRDT 논문이 던진 질문은 결국 “서버의 조율 없이도 데이터가 항상 같은 곳으로 수렴할 수 있는가”였고, 답은 결합법칙·교환법칙·멱등법칙을 만족하는 자료구조를 쓴다면 그렇다는 것이었어요. Riak, Redis Enterprise, Yjs·Automerge처럼 이 이론을 그대로 구현에 반영한 시스템이 있는가 하면, Syncthing처럼 철학은 공유하되 실제 구현은 훨씬 단순한 타임스탬프 기반 방식을 택한 시스템도 있다는 걸 확인했어요. 홈랩에서 rsync나 콘텐츠 정의 청킹 같은 동기화·백업 기법을 비교하다 보면, 결국 어떤 도구든 “충돌을 어떻게 정의하고 누가 해결하는가”라는 같은 질문으로 돌아오게 되는데, 여러 동기화·백업 도구의 트레이드오프를 한 번에 비교하고 싶다면 동기화·백업 도구 비교 글도 참고할 만해요.
참고 자료
- Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M. (2011). Conflict-free Replicated Data Types. INRIA Research Report RR-7687. HAL Archive
- Syncthing 공식 문서 – Understanding Synchronization
자주 묻는 질문
Q1. CRDT는 정확히 무엇의 약자인가요?
CRDT는 Conflict-free Replicated Data Type의 약자로, 여러 복제본이 서버 조율 없이 각자 갱신되더라도 수학적으로 항상 같은 최종 상태로 수렴하도록 설계된 자료구조예요.
Q2. CRDT 논문은 누가 언제 발표했나요?
Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski가 2011년 INRIA(프랑스 국립 정보통신연구소) 연구보고서(RR-7687)로 발표했고, 같은 해 SSS 2011 학회에서도 발표됐어요.
Q3. CvRDT와 CmRDT는 어떻게 다른가요?
CvRDT는 전체 상태를 통째로 주고받아 병합(merge)하는 상태 기반 방식이고, CmRDT는 개별 연산만 전파해서 각 복제본이 그 연산을 적용하는 연산 기반 방식이에요.
Q4. Syncthing은 CRDT를 사용해서 파일 충돌을 해결하나요?
아니요, Syncthing 공식 문서 기준으로 파일 충돌은 수정 시각과 기기 ID를 비교하는 단순한 최종 수정 우선(LWW) 방식으로 처리되고, CRDT나 버전 벡터 같은 정교한 병합 메커니즘은 쓰지 않아요.
Q5. CRDT는 실제로 어떤 제품에 쓰이고 있나요?
Redis Enterprise의 지역 간 복제, Riak의 데이터 타입, Yjs·Automerge 같은 실시간 협업 편집 라이브러리가 CRDT를 프로덕션에 적용한 대표 사례예요.
Q6. CRDT를 쓰면 항상 서버 없이도 완벽하게 동작하나요?
아니요, 수렴은 보장되지만 자료구조 설계에 따라 메모리·네트워크 오버헤드가 커질 수 있고, 사용자가 기대하는 '직관적인 병합 결과'와 수학적으로 수렴된 결과가 항상 일치하지는 않아요.
관련 글
