CRDT(Conflict-free Replicated Data Type, 충돌 없는 복제 데이터 타입)는 분산 시스템에서 네트워크 파티션이나 동시 업데이트가 있어도 자동으로 충돌 없이 병합되는 특수 자료구조다. 중앙 코디네이터 없이 강한 최종 일관성을 달성할 수 있다.
일반 분산 업데이트의 문제
Last Write Wins (LWW) 방식의 문제:
노드1: counter = 5 (시간 T1)
노드2: counter = 7 (시간 T2, T2 > T1이지만 네트워크 지연)
병합: counter = 7 (노드1의 증가분 손실!)
CRDT 해결:
G-Counter (증가 전용 카운터):
노드1: [5, 0, 0] (자신의 카운터만 증가)
노드2: [0, 7, 0]
병합: [5, 7, 0] → 합계 = 12 (손실 없음!)
CRDT 유형
상태 기반 CRDT (CvRDT)
python
class GSet:
"""Grow-only Set: 추가만 가능한 집합"""
def __init__(self):
self.set = set()
def add(self, element):
self.set.add(element)
def merge(self, other: 'GSet') -> 'GSet':
# 두 집합의 합집합 → 항상 단조 증가
result = GSet()
result.set = self.set | other.set
return result
def value(self):
return self.set
2P-Set (Two-Phase Set): 삭제 지원
add_set: 추가된 원소
remove_set: 제거된 원소
현재 값 = add_set - remove_set
병합: add_set 합집합, remove_set 합집합
OR-Set (Observed-Remove Set)
동시에 추가/제거가 발생해도 안전하게 처리한다.
원소마다 고유한 태그 부여:
add(x) → (x, unique_tag) 추가
remove(x) → 현재 관찰된 (x, tag) 모두 제거
병합: OR 연산 (태그 기반)
→ "Add wins" 또는 "Remove wins" 정책 선택 가능
실용 CRDT 예시
| 자료구조 | CRDT 버전 | 특징 |
|---|
| Counter | G-Counter, PN-Counter | 증가/감소 |
| Set | G-Set, 2P-Set, OR-Set | 추가/제거 |
| Map | LWW-Map, OR-Map | 키-값 |
| Text | RGA, LOGOOT | 협업 편집 |
| Register | LWW-Register, MV-Register | 단일 값 |
실제 사용
- •Redis Enterprise: CRDTs for multi-region sync
- •Riak: 분산 데이터 자동 병합
- •Google Docs: Operational Transform (OT, CRDT 유사)
- •Apple Notes: 오프라인 편집 후 병합
관련 개념
