CRDT — 충돌 없는 복제 데이터 타입

Conflict-free Replicated Data Type · 여러 복제본이 서로 다른 순서로 수정돼도 병합만 하면 똑같은 값으로 수렴한다

1. 문제: 복제본은 왜 갈라지는가

같은 데이터를 노트북·휴대폰·서버 등 여러 곳에 복사해 두고 각자 오프라인에서 수정한다고 하자. 나중에 다시 연결됐을 때 “누구 버전이 맞는가?”를 정해야 한다. 흔한 해법 세 가지는 모두 아쉽다.

CRDT는 네 번째 길이다. 연산(또는 상태)을 수학적으로 “교환법칙·결합법칙·멱등법칙”이 성립하도록 설계해서, 어떤 순서로 몇 번을 합치든 결과가 하나로 정해지게 만든다.

2. 수렴을 보장하는 세 가지 성질

이런 구조를 수학에서는 준격자(join-semilattice)라 부른다. 상태들 사이에 “≤” 순서를 주고, 병합은 항상 두 상태의 상한(least upper bound)을 취하는 연산이다. 그래서 병합은 값을 절대 되돌리지 않고 “위로만” 간다.

3. 데모 ①: G-Counter (증가 전용 카운터)

좋아요 수, 조회 수처럼 더하기만 하는 값. 트릭은 “하나의 숫자”를 공유하지 않고 노드마다 자기 칸을 따로 갖는 벡터 [A, B]를 쓰는 것이다.

• 노드는 자기 칸만 +1 한다.
• 병합 = 두 벡터를 칸별로 max (merge([3,1],[2,4]) = [3,4]).
• 실제 값 = 모든 칸의 합.

칸별 max는 교환·결합·멱등을 모두 만족한다 → 어떤 순서로 합쳐도 같은 벡터로 수렴. 아래에서 연결을 끊고 양쪽을 마구 눌러 본 뒤 동기화를 눌러 보라.

PN-Counter — 감소도 되게 하려면?

G-Counter는 빼기를 못 한다(max가 값을 되돌릴 수 없으니까). 해결책은 단순하다: 증가용 G-Counter 하나 + 감소용 G-Counter 하나를 두고 값 = 증가합 − 감소합. “빼기”를 “다른 카운터에 더하기”로 바꿔서 다시 단조 증가 구조로 만든 것이다.

4. 데모 ②: OR-Set (추가·삭제 되는 집합)

장바구니, 참여자 목록처럼 원소를 넣고 빼는 집합. 여기서 고전적 충돌이 나온다: A는 “🍎 추가”, B는 동시에 “🍎 삭제” — 병합하면 사과는 있어야 하나 없어야 하나?

OR-Set(Observed-Remove Set)의 규칙: add는 항상 고유 태그를 붙여 원소를 추가하고, remove는 “내가 그때 본 태그들”만 지운다. 그래서 “아직 아무도 못 본 새 add”는 삭제에서 살아남는다 → 동시에 일어난 add와 remove가 부딪히면 add가 이긴다.

시나리오: 연결을 끊고 → A에서 🍎 remove, B에서 🍎 add → 동기화. B가 새로 붙인 태그는 A의 remove가 “본 적이 없으므로” 사과는 살아남는다.

5. 두 갈래: 상태 기반 vs 연산 기반

이 페이지의 데모는 둘 다 상태 기반이다 — “동기화”가 서로의 전체 상태를 교환해 merge한다.

6. 의사코드

# ── G-Counter (상태 기반) ──────────────────────
class GCounter:
    p = {}                      # node_id -> count

    def increment(self, me):
        self.p[me] = self.p.get(me, 0) + 1

    def value(self):
        return sum(self.p.values())

    def merge(self, other):     # 칸별 max — 교환·결합·멱등
        for k in other.p:
            self.p[k] = max(self.p.get(k, 0), other.p[k])

# ── OR-Set (상태 기반) ─────────────────────────
class ORSet:
    adds = set()                # {(elem, unique_tag)}
    tombs = set()               # 제거된 (elem, tag)

    def add(self, e):
        self.adds.add((e, uuid()))          # 매번 새 태그

    def remove(self, e):
        for pair in [x for x in self.adds if x[0] == e]:
            self.tombs.add(pair)            # 지금 본 태그만 매장

    def value(self):
        live = self.adds - self.tombs
        return {e for (e, _) in live}

    def merge(self, other):     # 합집합 ∪ 합집합 — 순서 무관
        self.adds  |= other.adds
        self.tombs |= other.tombs

7. 정리

• CRDT = 병합 규칙을 semilattice로 설계해서 순서·중복·재전송에 흔들리지 않게 만든 자료형.
• 중앙 합의 없이 강한 최종 일관성을 얻는다 → 오프라인 우선 앱, 협업 편집기, 멀티마스터 DB(Redis CRDT, Riak, Automerge/Yjs).
• 대가: 태그·툼스톤 같은 메타데이터가 계속 쌓인다(가비지 컬렉션 필요). 그리고 “의미 있는 병합”이 항상 가능한 건 아니다 — 순서가 본질인 데이터엔 별도 설계(RGA 등)가 필요하다.