Skip to content

Conflict-free replicated data type

분산 컴퓨팅에서 충돌 없는 복제 데이터 유형은 네트워크의 여러 컴퓨터에 걸쳐 복제되는 데이터 구조로 다음과 같은 기능이 있습니다. 애플리케이션은 다른 복제본과 조정하지 않고 모든 복제본을 독립적으로 동시에 업데이트할 수 있습니다.

Libraries

Softwares

실전 가이드

CRDT(Conflict-free Replicated Data Type, 충돌 없는 복제 데이터 타입) 는 네트워크 분할이나 동시 수정 상황에서도 조정 없이 일관된 데이터 병합을 가능하게 하는 분산 데이터 구조임

  • 데이터 병합이 교환법칙·결합법칙·멱등성을 만족하면, 모든 복제본이 결국 동일한 상태로 수렴함
  • 대표적인 형태로 G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot 등이 있으며, 각기 다른 추가·삭제·재추가·순서 유지 요구를 처리함
  • Delta CRDT는 전체 상태 대신 변경분만 전송해 효율을 높이고, Garbage Collection은 메타데이터 누적 문제를 해결하기 위한 핵심 과제임
  • CRDT는 완벽한 해법이 아니지만, 가용성이 즉시 일관성보다 중요한 시스템에서 강력한 선택지로 평가됨

CRDT의 기본 개념

  • CRDT는 분산 환경에서 동시 수정이 발생해도 조정 없이 병합 가능한 데이터 구조
    • 병합 연산이 교환적(commutative) , 결합적(associative) , 멱등(idempotent) 이면 모든 복제본이 동일한 상태로 수렴
  • Lattice(격자) 개념을 기반으로, 상태가 항상 “위쪽”으로만 이동하도록 설계
    • 예: G-Counter는 각 복제본의 카운트를 max로 병합해 손실 없는 합산 보장
  • CRDT는 State-based(CvRDT) 와 Operation-based(CmRDT) 두 가지 접근이 있음
    • CvRDT는 전체 상태를 병합, CmRDT는 연산을 전파

주요 CRDT 유형

  • G-Counter: 증가만 가능한 카운터, 각 복제본의 값 합산
  • PN-Counter: 증가용·감소용 G-Counter를 결합해 양방향 카운트 지원
  • G-Set: 추가만 가능한 집합
  • 2P-Set: 추가·삭제 가능하지만 재추가 불가
  • LWW-Element-Set: 타임스탬프 기반으로 최근 연산이 승리
  • OR-Set: 고유 태그를 사용해 동시 추가 시 데이터 손실 없이 병합, add-wins 동작
  • LWW-Register / MV-Register: 단일 값 저장용, LWW는 단일 승자, MV는 동시값 모두 유지
  • OR-Map: 키별로 OR-Set을 결합한 맵 구조
  • RGA / WOOT / Logoot / LSEQ: 순서가 있는 시퀀스 데이터용 CRDT
    • RGA는 트리 기반, WOOT은 양방향 참조 기반, Logoot/LSEQ는 위치 식별자 기반

고급 CRDT 개념

  • Causal CRDTs: 버전 벡터를 사용해 인과 관계를 추적, 더 정확한 충돌 감지 가능
  • Delta CRDTs: 전체 상태 대신 변경분(델타)만 전송해 네트워크 효율 향상
  • Tree CRDTs: 계층 구조 데이터(파일 시스템 등) 복제 지원, 부모-자식 관계 유지 필요
  • Observed-Remove Shopping Cart: OR-Set과 PN-Counter를 결합한 전자상거래 장바구니 예시

Garbage Collection 문제

  • CRDT는 수렴을 위해 메타데이터를 계속 누적하므로 무한 성장 문제 발생
    • 예: OR-Set의 태그, RGA의 tombstone
  • 시간 기반 만료, 합의 기반 삭제, 버전 벡터 기반 인과 추적, 메타데이터 상한 설정, 체크포인트/리베이스 등 다양한 전략 존재
  • 각 방식은 안전성(좀비 복원 방지) 과 공간 효율성 사이의 절충 필요

성능 및 선택 가이드

  • CRDT 유형별 공간·시간 복잡도는 복제본 수, 요소 수, 태그 수 등에 따라 달라짐
    • G/PN-Counter는 복제본 수에 비례, OR-Set은 태그 수에 비례, RGA는 tombstone 누적
  • Delta CRDT는 병합 성능을 크게 개선
  • 선택 기준:
    • 추가만 필요 → G-Counter, G-Set
    • 삭제 필요, 재추가 불필요 → 2P-Set
    • LWW 허용 → LWW-Set/Register
    • 동시 수정 보존 → OR-Set, MV-Register
    • 순서 유지 필요 → RGA, Logoot
    • 중첩 구조 → OR-Map

결론

  • CRDT는 조정 없는 수렴을 보장하지만, 메타데이터 증가와 복잡성이 단점
  • 가용성 우선 시스템에서 유용하며, 각 CRDT는 특정 문제 유형에 최적화됨
  • 실무에서는 전통적 데이터베이스와 병행해 사용하며, 가비지 컬렉션 전략이 필수
  • “완벽한 CRDT”는 없으며, 응용 요구에 맞는 선택이 핵심임

See also

Favorite site

Articles