분산 시스템에서 같은 데이터에 여러 노드가 동시에 쓰면 어떻게 될까?

Amazon Dynamo는 2007년에 발표된 분산 key-value 저장소다. “항상 쓰기 가능(Always Writeable)“이라는 원칙 아래, 장애나 네트워크 파티션 상황에서도 쓰기를 거부하지 않는다. 대신 서로 다른 노드에 서로 다른 값이 써질 수 있고, 나중에 이 충돌을 해결해야 한다.

이 글에서는 Dynamo가 충돌을 감지하는 방법(벡터 클럭)과 해결하는 방법(클라이언트 중재)을 다룬다.

먼저 생각해볼 것

장바구니에 두 명의 사용자가 동시에 아이템을 추가한다고 해보자. 한 명은 사과를, 다른 한 명은 오렌지를 넣는다. 이 두 변경 사항을 어떻게 처리해야 할까?

하나만 남기고 다른 하나를 버려야 할까? 아니면 둘 다 살려야 할까? 그리고 그 판단은 누가 해야 할까?

이것이 분산 시스템에서의 동시 쓰기(concurrent write) 문제다. Dynamo는 이를 벡터 클럭으로 감지하고, 애플리케이션에게 해결을 맡긴다.

벡터 클럭이란

분산 시스템에서 이벤트의 인과 관계(causality)를 추적하는 메커니즘이다.

각 노드가 자신만의 논리적 카운터를 유지하고, 이벤트가 발생할 때마다 카운터를 증가시킨다. 노드가 3개(A, B, C)일 때 벡터 클럭은 [A:0, B:0, C:0] 형태다.

서버는 이 벡터 클럭을 비교해서 판단한다.

  • 이게 단순한 연속 업데이트인지 (한 쪽이 다른 쪽의 후속)
  • 아니면 병렬 업데이트인지 (동시에 일어난 충돌)

비교 규칙

두 벡터 클럭 A, B가 있을 때:

조건결과처리
A의 모든 카운터 <= B의 카운터A는 과거 버전자동 삭제 가능
그 외 (어떤 건 A가 크고 어떤 건 B가 큼)충돌중재 필요

예를 들어보자.

V1: [A:2, B:1, C:0]
V2: [A:2, B:2, C:0]

V1의 모든 카운터가 V2 이하다. V1은 과거 버전이므로 자동으로 정리된다.

V1: [A:2, B:1, C:0]
V2: [A:1, B:0, C:1]

A 카운터는 V1이 크고, C 카운터는 V2가 크다. 어느 쪽이 “나중"인지 판단할 수 없으므로 충돌이다.

Dynamo 장바구니 예제

Dynamo는 데이터를 N개 노드에 복제한다. 예를 들어 N=3이면 키 하나의 데이터가 3개 노드에 저장된다. 이 노드 목록을 선호 목록(Preference List)이라 한다. 평소에는 이 3개 노드가 동기화되지만, 네트워크가 끊기면 각자 다른 값을 가질 수 있다.

네트워크 파티션이 발생한 상황을 보자.

네트워크 파티션 발생:

  노드 A, B (연결됨)     노드 C (고립)

초기 장바구니는 비어 있다.

A쪽에서 사용자1:    add apple   → {apple}
C쪽에서 사용자2:    add orange  → {orange}

이제 서로 다른 두 버전이 존재한다.

V1 = {apple}
V2 = {orange}

Dynamo에서는 둘 다 저장한다. add 동작은 비즈니스적으로 절대 누락되면 안 되기 때문이다.

이후 읽기를 시도하면 여러 버전이 함께 반환된다.

get(cart#123) →
[
  {apple},   context1,
  {orange},  context2
]

중재(Reconciliation)

누가 합치는가? 클라이언트(애플리케이션)가 한다.

장바구니라면 합집합(union)이 자연스럽다.

{apple} ∪ {orange} → {apple, orange}

병합한 결과를 다시 put하면 된다. 이때 벡터 클럭은 두 버전을 모두 포함하도록 갱신된다.

신택틱 중재 vs 시맨틱 중재

신택틱 중재 (자동 정리)

인과 관계가 명확한 경우다.

V1: [A:1]
V2: [A:2]

V2가 V1을 포함한다. V1은 자동으로 삭제된다. 애플리케이션이 개입할 필요가 없다.

시맨틱 중재 (의미 기반 병합)

인과 관계가 없는 경우다.

V1: [A:2, C:0]
V2: [A:0, C:1]

비교 불가능하므로 충돌이다. 애플리케이션이 비즈니스 로직에 따라 직접 병합해야 한다.

remove가 위험한 이유

초기: {apple}

A: add banana   → {apple, banana}
C: remove apple → {}

네트워크 복구 후 병합하면?
→ {banana} 또는 {apple, banana}?

정답이 명확하지 않다. 논문에서도 “remove된 아이템이 다시 나타날 수 있다"고 언급한다.

Dynamo의 합집합 기반 병합에서는 add는 절대 누락되지 않지만, remove는 되살아날 수 있다. 이것은 “항상 쓰기 가능(Always Writeable)“이라는 설계 철학이 낳은 의도된 트레이드오프다.

W+R > N의 의미

Dynamo에서는 서비스마다 N, R, W 파라미터를 조정할 수 있다.

  • N — 데이터를 복제할 노드 수
  • W — 쓰기 성공에 필요한 최소 응답 노드 수
  • R — 읽기 성공에 필요한 최소 응답 노드 수

이 값들의 관계가 일관성과 가용성의 균형을 결정한다.

R + W > N이면 읽기 노드 집합과 쓰기 노드 집합이 반드시 겹친다.

N=3, W=2, R=2

쓰기 시: 노드 A, B에 저장 (2개)
읽기 시: 노드 B, C에서 읽음 (2개)

→ B가 겹침 → 최신 값을 읽을 수 있음

W=1, R=1로 설정하면 어떻게 될까?

N=3, W=1, R=1

1 + 1 = 2 < 3
→ 읽기와 쓰기 노드가 안 겹칠 수 있음
→ 가용성은 최대 (아무 노드 1개만 살아있어도 OK)
→ 일관성은 최저 (stale 데이터를 읽을 확률이 높음)

일반적으로 (3, 2, 2) 설정을 사용한다. N은 내구성을, W와 R의 조합은 가용성과 일관성 사이의 트레이드오프를 결정한다.

설정W+R vs N일관성가용성용도
N=3, R=2, W=24 > 3강함보통일반적 사용
N=3, R=1, W=N4 > 3강함쓰기 낮음읽기 위주 (상품 카탈로그)
N=3, R=1, W=12 < 3약함최대가용성 극대화

참고자료