▲

CRDT 사전: 분산 데이터 구조를 위한 실전 가이드

 (iankduncan.com)
17P by GN⁺ 1일전 | ★ favorite | 댓글 1개
  • 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”는 없으며, 응용 요구에 맞는 선택이 핵심임
▲
GN⁺ 1일전  [-]
Hacker News 의견

  • CRDT의 흥미로운 점 중 하나는, 단순히 여러 저수준 CRDT를 조합한 라이브러리가 아니라는 점임
    예를 들어 Automerge는 자체적으로 완전한 CRDT이며, 수학적 증명을 통해 동시성 하에서도 일관성을 보장함
    Automerge 팀은 Isabelle 같은 정리 증명 도구로 설계를 검증하고, 데이터베이스 세계의 최신 성능 기법을 적용해 빠르고 정확한 구현을 목표로 함
    실시간 협업이 필요한 SaaS(예: Notion, Figma)를 만든다면, 복잡한 이론을 몰라도 협업형 데이터 구조를 바로 적용할 수 있음
    백엔드는 단순한 key-value 스토리지면 충분하고, 프론트엔드는 라이브러리 하나면 됨

    • Automerge는 Rust뿐 아니라 Javascript, C에서도 훌륭한 API를 제공함
      나도 Redis 기반의 automerge 라이브러리를 만들어봤는데, pub/sub을 이용해 완전한 지속 동기화 서버를 구현할 수 있었음
      Webdis의 websocket 기능을 활용해 여러 브라우저 간 문서 동기화 데모도 빠르게 완성했음
    • Automerge는 훌륭하지만 여전히 학문적 접근이 강한 느낌임
      더 나은 DX와 CRDT 기반 풀스택 DB를 원한다면 Triplit.dev를 추천함. 개발 속도는 다소 느려졌지만 기능은 충분히 완성된 상태임
    • Automerge가 완전한 CRDT라는 건 놀랍지 않음
      개인적으로는 Loro도 좋아하지만, 여전히 문서 기반 구조라서 쿼리 엔진이 부족함. 원하는 데이터를 얻으려면 특정 중첩 항목을 직접 지정해야 함
    • Automerge가 셀프 호스팅을 지원하지 않는 점은 많은 애플리케이션에서 치명적인 제약임

  • CRDT의 기본부터 고급 개념까지 잘 정리된 글이었음
    참고로 Riak은 여전히 OpenRiak 형태로 유지되고 있음

    • OpenRiak을 처음 알게 되었는데, 예전 동료들이 참여하고 있는 걸 보니 반가움. Basho는 정말 뛰어난 엔지니어 집단이었음

  • 지난 2년간 직접 CRDT를 개발했지만, 너무 많은 트레이드오프가 있다는 걸 깨닫고 결국 ID 기반 OT 프레임워크로 전환했음
    이번 화요일에 Docnode.dev를 런칭할 예정임. 피드백을 듣고 싶음
    앞으로는 P2P가 필요한 상황을 위해 CRDT 모드도 추가할 계획임

    • 어떤 트레이드오프가 가장 문제였는지 궁금함

  • CRDT나 OT는 사람들이 같은 문단을 동시에 편집할 때를 해결하려는 구조인데, 실제로는 그런 상황이 거의 발생하지 않음

    • 하지만 이런 기능이 없는 시스템은 종종 커서가 같은 문장에 겹쳐서 콘텐츠 손실이나 시간 낭비가 생기곤 함

  • 이 글에서 말하는 OR-Set은 예전에 Monotone이 2005년부터 사용하던 병합 방식과 유사함
    관련 자료는 MarkMerge 문서에서 볼 수 있음

  • 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 내부에도 구현할 수 있지만, 비즈니스 로직을 어디에 둘지에 따라 접근 방식이 달라짐
답변달기