콘텐츠로 이동
Search

Conflict-free replicated data type

lastmod 2025-12-02created 2023-02-028 edits

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

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

author Zer0 sitemap