충돌 없는 복제 데이터 타입(CRDT) 사전: 분산 데이터 구조를 위한 실전 가이드

1 week ago 6

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는 연산을 전파

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는 수렴을 위해 메타데이터를 계속 누적하므로 무한 성장 문제 발생
- 예: 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