# CRDT 사전: 분산 데이터 구조를 위한 실전 가이드 > Clean Markdown view of GeekNews topic #24731. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=24731](https://news.hada.io/topic?id=24731) - GeekNews Markdown: [https://news.hada.io/topic/24731.md](https://news.hada.io/topic/24731.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2025-12-01T08:34:21+09:00 - Updated: 2025-12-01T08:34:21+09:00 - Original source: [iankduncan.com](https://www.iankduncan.com/engineering/2025-11-27-crdt-dictionary/) - Points: 25 - Comments: 1 ## Summary 여러 복제본이 서로 충돌해도 자연스럽게 한 상태로 모이도록 설계된 것이 **CRDT**입니다. 조정 과정을 생략할 수 있다는 점이 큰 장점인데, 이를 가능하게 하는 기반이 **교환·결합·멱등성**을 만족하는 병합 규칙입니다. 덕분에 OR-Set이나 RGA 같은 구조들이 분산 편집, 협업 애플리케이션, 로컬 우선 저장소 등에서 널리 쓰이고 있습니다. 다만 메타데이터가 끝없이 늘어나는 특성은 해결해야 할 과제로 남아 있고, 그래서 **Delta CRDT**나 다양한 가비지 컬렉션 방식이 적극적으로 연구되고 있습니다. 결국 CRDT는 “모든 상황의 정답”이라기보다, **가용성을 우선하는 시스템이 고민 끝에 선택하게 되는 설계 철학**에 가깝습니다. ## Topic Body - **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는 연산을 전파 ### 주요 CRDT 유형 - **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 개념 - **Causal CRDTs**: 버전 벡터를 사용해 인과 관계를 추적, 더 정확한 충돌 감지 가능 - **Delta CRDTs**: 전체 상태 대신 변경분(델타)만 전송해 네트워크 효율 향상 - **Tree CRDTs**: 계층 구조 데이터(파일 시스템 등) 복제 지원, 부모-자식 관계 유지 필요 - **Observed-Remove Shopping Cart**: OR-Set과 PN-Counter를 결합한 전자상거래 장바구니 예시 ### Garbage Collection 문제 - 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 ### 결론 - CRDT는 **조정 없는 수렴**을 보장하지만, **메타데이터 증가와 복잡성**이 단점 - **가용성 우선 시스템**에서 유용하며, 각 CRDT는 특정 문제 유형에 최적화됨 - 실무에서는 전통적 데이터베이스와 병행해 사용하며, **가비지 컬렉션 전략**이 필수 - “완벽한 CRDT”는 없으며, **응용 요구에 맞는 선택**이 핵심임 ## Comments ### Comment 47007 - Author: neo - Created: 2025-12-01T08:34:22+09:00 - Points: 1 ###### [Hacker News 의견](https://news.ycombinator.com/item?id=46087022) - CRDT의 흥미로운 점 중 하나는, 단순히 여러 **저수준 CRDT를 조합한 라이브러리**가 아니라는 점임 예를 들어 [Automerge](https://automerge.org/)는 자체적으로 완전한 CRDT이며, **수학적 증명**을 통해 동시성 하에서도 일관성을 보장함 Automerge 팀은 Isabelle 같은 정리 증명 도구로 설계를 검증하고, 데이터베이스 세계의 최신 성능 기법을 적용해 빠르고 정확한 구현을 목표로 함 실시간 협업이 필요한 SaaS(예: Notion, Figma)를 만든다면, 복잡한 이론을 몰라도 **협업형 데이터 구조**를 바로 적용할 수 있음 백엔드는 단순한 key-value 스토리지면 충분하고, 프론트엔드는 라이브러리 하나면 됨 - Automerge는 Rust뿐 아니라 Javascript, C에서도 훌륭한 API를 제공함 나도 Redis 기반의 [automerge 라이브러리](https://github.com/michelp/redis-automerge)를 만들어봤는데, pub/sub을 이용해 완전한 **지속 동기화 서버**를 구현할 수 있었음 [Webdis](https://webd.is/)의 websocket 기능을 활용해 여러 브라우저 간 문서 동기화 데모도 빠르게 완성했음 - Automerge는 훌륭하지만 여전히 **학문적 접근**이 강한 느낌임 더 나은 DX와 CRDT 기반 풀스택 DB를 원한다면 [Triplit.dev](https://triplit.dev)를 추천함. 개발 속도는 다소 느려졌지만 기능은 충분히 완성된 상태임 - Automerge가 완전한 CRDT라는 건 놀랍지 않음 개인적으로는 [Loro](https://loro.dev)도 좋아하지만, 여전히 **문서 기반 구조**라서 쿼리 엔진이 부족함. 원하는 데이터를 얻으려면 특정 중첩 항목을 직접 지정해야 함 - Automerge가 **셀프 호스팅을 지원하지 않는 점**은 많은 애플리케이션에서 치명적인 제약임 - CRDT의 기본부터 고급 개념까지 잘 정리된 글이었음 참고로 Riak은 여전히 [OpenRiak](https://github.com/OpenRiak) 형태로 유지되고 있음 - OpenRiak을 처음 알게 되었는데, 예전 동료들이 참여하고 있는 걸 보니 반가움. Basho는 정말 **뛰어난 엔지니어 집단**이었음 - 지난 2년간 직접 CRDT를 개발했지만, 너무 많은 **트레이드오프**가 있다는 걸 깨닫고 결국 ID 기반 OT 프레임워크로 전환했음 이번 화요일에 [Docnode.dev](https://docnode.dev)를 런칭할 예정임. 피드백을 듣고 싶음 앞으로는 P2P가 필요한 상황을 위해 CRDT 모드도 추가할 계획임 - 어떤 트레이드오프가 가장 문제였는지 궁금함 - CRDT나 OT는 사람들이 같은 문단을 동시에 편집할 때를 해결하려는 구조인데, 실제로는 그런 상황이 **거의 발생하지 않음** - 하지만 이런 기능이 없는 시스템은 종종 커서가 같은 문장에 겹쳐서 **콘텐츠 손실**이나 시간 낭비가 생기곤 함 - 이 글에서 말하는 OR-Set은 예전에 Monotone이 2005년부터 사용하던 병합 방식과 유사함 관련 자료는 [MarkMerge 문서](https://tonyg.github.io/revctrl.org/MarkMerge.html)에서 볼 수 있음 - CRDT는 여전히 **직접 구현해야 하는 영역**임 나도 두 달 전, diamond types에서 영감을 받아 시퀀스 기반 CRDT 엔진을 만들었음 AI에게 도움을 요청했지만, 이런 **논리 중심 문제**에는 전혀 도움이 되지 않았음 LLM이 새로운 논리를 이해할 수 있는지 검증하는 **블랙박스 테스트**가 필요하다고 느낌 - Loro 같은 걸 그냥 쓰는 건 어떤지 궁금함 - 글이 훌륭했지만, 용어 사전에는 **색인(index)** 이 꼭 필요하다고 생각함 - CRDT가 결국 **병합 충돌을 DB에서 애플리케이션 로직으로 밀어내는 것** 아닌가 하는 생각이 듦 - CRDT는 DB 내부에 설계될 수도 있음. Riak에서는 바로 그걸 목표로 했음 올바르게 작성되면 어떤 계층에 있든 **자동 병합 해결**이 가능함 - 나도 PostgreSQL에서 CRDT 기법을 적용한 **그래프 DB**를 구상 중임 가장 큰 문제는 UNIQUE/PRIMARY KEY 충돌 처리였음 각 서버에 ID 네임스페이스를 분배하고, 최초 생성이 승리하며 충돌 시 이름을 변경하거나 삭제하는 식으로 해결 가능함 EAV 스키마를 사용하면 SQL에서 **재귀 CTE**로 그래프 탐색을 쉽게 구현할 수 있음 다만 PostgreSQL은 ANY 타입이 없어 속성이 다양한 객체를 표현하기 어렵고, FOREIGN KEY 기능도 직접 구현해야 함 그래도 EAV 구조는 상속 같은 **메타 스키마 설계**에 유리함 PostgreSQL에서 CRDT 타입을 직접 정의할 수 있다면 좋겠지만, 현재는 monoid 연산 제한이 불가능함 결국 비키 컬럼용 CRDT는 애플리케이션 계층에서 처리해야 함 요약하자면, CRDT는 RDBMS 내부에도 구현할 수 있지만, **비즈니스 로직을 어디에 둘지**에 따라 접근 방식이 달라짐