충돌 없는 복제 자료형 (conflict-free replicated data type)
쉽게 풀면
여러 사람이 인터넷 연결 없이 같은 문서를 각자 고친 뒤 나중에 합친다고 생각해 보세요. 보통은 어느 쪽을 살릴지 다투게 되는데, 이 자료형은 합치는 연산 자체가 순서와 중복에 영향받지 않도록 수학적으로 설계되어 있습니다. 그래서 누가 먼저 동기화되든 결국 모두 같은 상태에 도달합니다.
왜 중요한가
실시간 공동 편집기, 오프라인을 지원하는 모바일 앱, 지리적으로 흩어진 분산 데이터베이스의 핵심 기술입니다. 중앙 서버의 합의를 기다리지 않고도 각자 즉시 수정할 수 있어 응답이 빠르고 네트워크가 끊겨도 동작합니다. 최종적 일관성을 수동 충돌 해결 없이 달성하는 원리적 방법을 제시했다는 점에서 이론적 의의도 큽니다.
논문에서는 이렇게 쓰입니다
각자 따로 고친 내용이 자동으로 하나의 결과로 합쳐졌다는 뜻입니다.
조금 더 깊게 보면
상태 기반 방식은 전체 상태를 주고받으며 병합 함수가 결합법칙·교환법칙·멱등성을 만족하는 반격자 구조여야 하고, 연산 기반 방식은 연산만 전파하되 동시 연산이 교환 가능해야 합니다. 대표적 자료형으로 증가만 하는 카운터, 두 집합으로 추가와 삭제를 관리하는 2P-Set, 마지막 쓰기를 채택하는 레지스터, 그리고 텍스트 편집을 위한 순서 있는 시퀀스 자료형이 있습니다. 삭제된 원소의 흔적인 툼스톤이 쌓여 메모리가 증가하는 문제가 실용화의 주요 과제입니다.
주의할 점
합쳐진 결과가 항상 사용자가 의도한 바와 같다는 뜻은 아니며, 보장되는 것은 모든 복제본이 같은 상태가 된다는 수렴성뿐입니다. 합의 알고리즘이 하나의 순서를 강제로 정해 강한 일관성을 얻는 것과 달리, 이 접근은 순서 합의를 아예 포기하는 대신 자료형의 성질로 문제를 해결합니다.