[CS] CRDT

CRDT(Conflict-free Replicated Data Type) 는 분산 시스템에서 데이터 복제를 처리하기 위한 구조다.
 
1. 주요 특징
- 충돌 없는 병합
  > 각 노드에서 독립적으로 데이터를 수정한 후, 병합 시 충돌 없이 자동으로 일관된 상태 보장
- 최종 일관성
  > 네트워크 분리 또는 지연 상황에서도, 모든 노드는 결국 동일한 상태로 수렴
- 병합 및 독립 수정 허용
  > 여러 노드에서 병렬로 데이터를 수정할 수 있으며, 수정된 데이터는 병합 시 자동으로 조화
 
2. 종류 (데이터 병합 방식에 따라 나뉨)
- 2.1. State-Based CRDT
  > 각 노드는 데이터의 전체 상태를 주기적으로 다른 노드와 동기화
  > 병합 연산자는 결합 연산자를 사용하며, 연산의 순서와 상관없이 동일한 결과 획득
- 2.2. Operation-Based CRDT
  > 데이터의 상태가 아닌 각 연산을 다른 노드에 전파
  > 전파된 연산은 수신 노드에서 재적용되어 최종 일관성 보장
 
3. 예시
- 3.1. G-Counter(Grow-only Counter)
  > 오직 증가만 가능한 카운터
  > 각 노드에서 숫자를 독립적으로 증가시킨 후, 병합 시 각 노드의 값을 더함
- 3.2. LWW-Register(Last-Write-Wins Register)
  > 마지막에 기록된 값이 승리하는 데이터 타입
  > 타임스탬프를 기반으로 병합 시 최신 값 유지
- 3.3. RGA(Replicated Growable Array)
  > 분산 환경에서 리스트 관리
  > 실시간 협업 문서 편집기에 사용
 
4. 사용 사례
- 분산 데이터베이스, 실시간 협업 애플리케이션, 오프라인 동기화 시스템