Coordination avoidance

합의 없이도 일관성을 얻을 수 있어. **조정 회피(coordination avoidance)**가 핵심 아이디어야. Total order broadcast는 합의가 필요하니까 확장성 병목이 되고 가용성도 제한되거든. 더 약한 일관성 모델로도 충분히 쓸 만한 시스템을 만들 수 있다는 게 이 장의 요지지.

먼저 브로드캐스트 프로토콜의 스펙트럼을 알아야 해. Best-effort broadcast는 송신자가 안 죽으면 모든 정상 프로세스에 전달되지만, 중간에 죽으면 일부만 받아. Reliable broadcast는 송신자가 죽어도 결국 다 전달돼 — eager 방식은 모든 프로세스가 재전송해서 N² 메시지가 필요하고. Gossip broadcast는 랜덤 부분집합에만 전달하는데 확률적이지만 대규모에서 훨씬 효율적이야. 가장 비싼 건 Total order broadcast — reliable에 더해 모든 프로세스가 같은 순서로 메시지를 받아야 하니까 합의가 필수지.

Total order 없이 복제하면 레플리카가 **발산(diverge)**해. 여기서 핵심 아이디어가 나와 — 충돌의 결정론적 결과를 정의하면 합의 없이도 수렴할 수 있어. 이게 **CRDT(Conflict-free Replicated Data Type)**야. 조건은 가능한 상태가 **반격자(semilattice)**를 형성하고, merge 연산이 교환적, 결합적, 멱등적이어야 해. LWW Register는 타임스탬프 큰 쪽이 이기고, G-Counter는 프로세스별 카운터 배열의 합산으로 전체 카운트를 구하고, G-Set은 합집합으로 merge하지. 이건 강한 최종 일관성(strong eventual consistency) — 같은 업데이트를 받은 레플리카는 즉시 같은 상태야.

실제 적용은 Dynamo-style 데이터 스토어에서 볼 수 있어. Cassandra, Riak 같은 리더 없는(leaderless) 시스템이지. 일관된 해싱으로 데이터를 노드에 배치하고, 벡터 클럭으로 충돌을 감지하고, Read repair와 Anti-entropy로 수렴시켜. Sloppy quorum + hinted handoff로 파티션 시에도 가용성을 유지하고.

이론적 기초도 있어. CALM 정리(Consistency As Logical Monotonicity) — 논리적으로 단조적인(monotonic) 프로그램, 즉 정보를 추가만 하고 철회하지 않는 프로그램은 조정 없이 최종 일관성을 보장할 수 있어. 반대로 임계값 확인 같은 비단조적 연산은 조정이 필요하지. 어떤 애플리케이션이 최종 일관성에서 안전한지 판단하는 이론적 틀이야.

최종 일관성보다 강하지만 linearizability보다 약한 중간점도 있어 — **인과적 일관성(causal consistency)**이야. 인과적으로 관련된 연산은 모든 노드에서 올바른 순서로 보이고, 동시적 연산은 노드마다 순서가 달라도 돼. 벡터 클럭으로 인과 관계를 추적하지.

결국 강한 일관성과 최종 일관성 중 뭘 고를지는 애플리케이션에 따라 다르다는 거야. 방문 카운터는 최종 일관성이면 충분하지만, 금융 거래는 linearizability가 필요해. 현실에서는 하이브리드 접근법을 많이 쓰지.

---

정리

7장 읽고 기억할 거 세 가지:

1. CRDT는 merge 연산의 수학적 속성(교환, 결합, 멱등)으로 합의 없이도 레플리카가 수렴하게 해 — 강한 최종 일관성이야
2. CALM 정리 — 단조적 프로그램은 조정 없이 최종 일관성이 안전해. 비단조적 연산이 있을 때만 조정이 필요하지
3. 인과적 일관성은 linearizability와 eventual consistency 사이의 실용적 중간점이야 — 인과 관련 연산만 순서를 보장하고 동시 연산은 자유롭게 둬