CRDT (Conflict-free Replicated Data Type)

CRDT (Conflict-free Replicated Data Type)

분산 시스템에서 동시 업데이트 충돌 시 별도 합의 없이 자동으로 병합 가능한 데이터 구조

수학적 특성: 결합법칙(Associative), 교환법칙(Commutative), 멱등성(Idempotent) → 순서/중복 무관하게 동일 결과

유형

• •상태 기반 (CvRDT): 전체 상태를 교환, merge 함수로 병합 (대역폭↑)
• •연산 기반 (CmRDT): 연산(operation)만 전파, 인과 순서 전달 필요 (대역폭↓)

주요 CRDT

• •G-Counter: 증가만 가능한 카운터 (노드별 로컬 카운터, 합산으로 전체 값)
• •PN-Counter: 증가/감소 가능 (G-Counter 2개: P-증가, N-감소)
• •LWW-Register: 최후 기록 승리 (타임스탬프 기반 충돌 해결)
• •OR-Set (Observed-Remove Set): 추가/삭제, 태그 기반 충돌 해결

적용사례: 실시간 협업 편집, 분산 캐시, Active-Active 복제, 오프라인-온라인 동기화

비교: CRDT(자동 병합/최종 일관성) vs OT(Operational Transformation/변환 기반/중앙 서버) vs 합의 알고리즘(강한 일관성/높은 비용)

연관: Active-Active, CAP, Eventual Consistency, 분산 시스템