DDIA - 복제_다중 리더와 리더 없음

Table of Contents

1. 다중 리더 복제
   1. 다중 리더 복제의 사용 사례
      1. 다중 데이터센터 운영
      2. 오프라인 작업을 하는 클라이언트
   2. 쓰기 충돌 다루기
      1. 동기 대 비동기 충돌 감지
      2. 충돌 회피
      3. 일관된 상태 수렴
      4. 사용자 정의 충돌 해소 로직
      5. 자동 충돌 해소
   3. 다중 리더 복제 토폴리지
2. 리더 없는 복제
   1. 노드가 다운됐을 때 데이터베이스에 쓰기
      1. 읽기 복구와 안티 엔트로피
      2. 읽기와 쓰기를 위한 정족수
   2. 정족수 일관성의 한계
      1. 최신성 모니터링
   3. 느슨한 정족수와 암시된 핸드오프
      1. 다중 데이터센터 운영
   4. 동시 쓰기 감지
      1. 최종 쓰기 승리(동시 쓰기 버리기)
      2. “이전 발생” 관계와 동시성
      3. 이전 발생 관계 파악하기
      4. 동시에 쓴 값 병합
      5. 버전 벡터

다중 리더 복제

리더 기반 복제의 주요한 단점은 리더가 하나만 존재하고 모든 쓰기는 해당 리더를 거쳐야 한다는 것이다.
그래서 리더 기반 복제 모델은 쓰기를 허용하는 노드(리더)를 하나 이상 두는 것으로 자연스럽게 확장된다.
이 방식을 다중 리더 (마스터 마스터, 액티브/액티브 복제) 설정이라 부른다.
이 설정에서 각 리더는 동시에 다른 리더의 팔로워 역활도 한다.

다중 리더 복제의 사용 사례

단일 데이터센터 내에 다중 리더 설정은 복잡도에 비해 이점이 크지 않기에 적절하지 않다.
하지만 몇 가지 상황에서는 합리적인데 관련해서 알아보자.

다중 데이터센터 운영

다중 리더 설정은 각 데이터센터마다 리더가 있을 수 있다.
각 데이터센터 내에는 보통의 리더 팔로워 복제 를 사용한다.
데이터센터 간에는 각 데이터센터의 리더가 다른 데이터센터의 리더에게 변경 사항을 복제한다.
간략화한 구성도는 아래와 같다.

단일 리더 설정 VS 다중 리더 설정 (다중 데이터 센터에서)

1. 성능
   • 단일 리더
     모든 쓰기는 클라이언트에서 인터넷을 통해 리더가 있는 데이터센터로 이동
     지연 시간 증가의 원인
   • 다중 리더
     모든 쓰기는 로컬 데이터센터에서 처리 -> 비동기 방식으로 다른 데이터센터로 복제
     사용자가 인지하는 성능이 더 좋을 수 있다.
2. 데이터센터 중단 내성
   • 단일 리더
     리더의 데이터센터가 고장 나면 장애 복구를 위해 다른 데이터센터에서 한 팔로워를 리더로 승진
   • 다중 리더
     각 데이터센터는 서로 독립적으로 동작
     고장 난 데이터센터가 온라인으로 돌아왔을 때 복제를 따라잡는다.
3. 네트워크 문제 내성
   • 단일 리더
     데이터센터 간 연결의 쓰기는 동기식이기에 데이터센터 간 연결 문제에 매우 민감
   • 다중 리더
     데이터센터 간 연결의 쓰기를 비동기식을 사용하기에 네트워크 문제에 보다 잘 견딤.
     일시적인 네트워크 중단에도 쓰기 처리는 진행되기 때문

다중 리더 복제의 큰 단점

• 쓰기 충돌이 발생할 수 있고, 반드시 해소해야 한다.

다중 리더 복제는 설정상의 실수나 다른 데이터베이스 기능과의 뜻밖의 상호작용이 있다.
예를 들어 자동 증가 키, 트리거, 무결성 제약은 문제가 될 소지가 많다.
이런 이유로 다중 리더 복제는 가능하면 피해야 하는 위험한 영역으로 간주되곤 한다.

오프라인 작업을 하는 클라이언트

다중 리더 복제가 적절한 또 다른 상황은 인터넷 연결이 끊어진 동안 애플리케이션이 계속 동작해야 하는 경우이다.

이 경우 모든 디바이스(클라이언트)에는 리더처럼 동작하는 로컬 데이터베이스가 있다.

특징

• 모든 디바이스 상에서 복제 서버 간 다중 리더 복제를 비동기 방식으로 수행하는 프로세스가 존재
• 복제 지연은 사용자가 인터넷이 가능해진 시점에 따라 몇 시간에서 몇일 이상 소요

아키텍처 관점에서 이 설정은 근본적으로 데이터센터 간 다중 리더 복제와 동일하다.

쓰기 충돌 다루기

다중 리더 복제에서 제일 큰 문제는 쓰기 충돌이 발생한다는 점이다.

쓰기 충돌에 대한 간단한 예제를 아래 그림으로 확인하자.

동기 대 비동기 충돌 감지

다중 리더 설정은 복제를 비동기식으로 동작한다고 했다.

비동기 충돌 감지

• 동시에 발생한 쓰기는 모두 성공
• 충돌은 이후 특정 시점에서 비동기로만 감지
• 이 시점에 사용자에게 충돌 해소 요청은 너무 늦을 수도 있다.

동기 충돌 감지

• 이론적으로 가능
• 다중 리더 복제의 주요 장점을 상실
  각 복제 서버가 독립적으로 쓰기를 허용
• 단일 리더 복제를 사용하는 편이 좋음
  다중 리더 복제의 주요 장점을 상실하기 때문

충돌 회피

충돌을 처리하는 제일 간단한 전략
특정 레코드의 모든 쓰기가 동일한 리더를 거치도록 애플리케이션이 보장한다면 충돌은 발생하지 않는다란 개념이다.

한 가지 예
특정 사용자의 요청을 동일한 데이터센터로 항상 라우팅한다.
그래서 해당 데이터센터 내 리더를 사용해 읽기와 쓰기를 하게끔 보장하는 것이다.
한 사용자 관점에서 보면 구성은 기본적으로 단일 리더이다.

하지만 여러가지 이유(특정 데이터센터 장애 등)로 지정된 리더를 변경하고 싶을 수도 있다.
이런 상황에서 충돌 회피가 실패한다.
그러면 다른 리더에서 동시 기록 가능성을 대처 해야 한다.

일관된 상태 수렴

다중 리더 설정에서는 쓰기 순서가 정해지지 않아 최종 값이 무엇인지 명확 하지 않다.
어떤 순서도 다른 순서보다 “더 정확”하지 않다.
이런 순서와 관련된 내용은 "이전 발생" 관계와 동시성 에서 살펴본다.

단순하게 각 복제 서버가 쓰기를 본 순서대로 적용한다면 데이터베이스는 결국 일관성 없는 상태가 된다.

모든 복제 계획은 모든 복제 서버가 최종적으로 동일하다는 사실을 보장해야 한다.
따라서 데이터베이스는 수렴 (convergent) 방식으로 충돌을 해소해야 한다.
수렴 방식 : 모든 변경이 복제돼 모든 서버에 동일한 최종 값이 전달되게 해야 한다

수렴 충돌 해소를 달성하는 방법

• 각 쓰기에 고유 ID를 부여, 가장 높은 ID를 가진 쓰기를 선택
  가장 높은 ID(winner)를 선택하고, 다른 쓰기는 버린다.
  TimeStamp를 사용하면 최종 쓰기 승리(last write wins, LWW)라 부른다.
  대중적이지만 데이터 유실 위험이 존재
• 각 복제 서버에 고유 ID를 부여, 가장 높은 ID의 복제 서버에서 생긴 쓰기를 우선 적용
  위와 유사하지만 대상이 복제 서버이고 위는 각 쓰기
  데이터 유실 위험 존재
• 어떻게든 값을 병합
• 명시적 데이터 구조에 충돌을 기록해 모든 정보를 보존
  충돌을 해소하는 애플리케이션 코드가 필요

사용자 정의 충돌 해소 로직

충돌을 해소하는 가장 적합한 방법은 애플리케이션에 따라 다르다.
따라서 대부분의 다중 리더 복제 도구는 애플리케이션 코드를 사용해 충돌 해소 로직을 수행한다.

사용자 정의 충돌 해소 로직은 쓰기나 읽기 수행 중 실행될 수 있다.

1. 쓰기 수행 중
   복제된 변경 사항 로그에서 데이터베이스 시스템이 충돌을 감지하자마자 충돌 핸들러를 호출
   백그라운드 프로세스에서 빠르게 실행돼야 함
2. 읽기 수행 중
   충돌을 감지하면 모든 충돌 쓰기를 저장
   데이터를 읽을 때 여러 버전의 데이터를 에플리케이션에 반환
   그리고 애플리케이션은 사용자에게 충돌 내용을 보여주거나 자동으로 충돌을 해소 후 결과를 데이터베이스에 기록

충돌 해소는 보통 전체 트랜잭션이 아니라 개별 로우나 문서 수준에서 적용된다.

자동 충돌 해소

1. 충돌 없는 복제 데이터타입(Conflict-free replicated datatype, CRDT)
   셋, 맵, 정렬 목록, 카운터 등을 위한 데이터 구조의 집합으로 동시에 여러 사용자가 편집할 수 있고 합리적인 방법으로 충돌을 자동 해소
   이중 병합(two-way merge) 사용
   리악 2.0에서 일부 구현
   CRDT vs OT 참고
2. 병합 가능한 영속 데이터 구조(mergeable persistent data structure)
   깃 버전 제어 시스템과 유사하게 명시적으로 히스토리를 추적하고 삼중 병합 함수(three-way merge function)를 사용
3. 운영 변환(operational transformation)
   협업 편집 애플리케이션의 충돌 해소 알고리즘
   CRDT vs OT 참고

다중 리더 복제 토폴리지

복제 토폴로지 : 쓰기를 한 노드에서 다른 노드로 전달하는 통신 경로를 설명

원형 토폴로지(Circular topology)와 별 모양 토폴로지(Star topology)

• 모든 복제 서버에 도달하기 전에 여러 노드를 거쳐야 함
• 무한 복제 로프를 방지하기 위한 각 노드 별 고유 식별자 사용
  복제 로그에서 각 쓰기는 지나온 모든 노드의 식별자가 태깅
  자신의 식별자가 태깅된 경우, 데이터 변경 사항을 무시
• 하나의 노드에 장애가 발생하면 다른 노드 간 복제 메시지 흐름에 방해를 줌
  장애 노드를 회피하게끔 재설정 가능하지만 보통 수동으로 수행해야 함

전체 연결 토폴로지(All-to-all topology)

• 가장 일반적인 토폴로지
• 빽빽하게 연결되어 내결함성이 더 좋음
• 네트워크 연결 간 속도 차이로 일부 복제 메시지가 다른 메시지를 “추월”할 수 있음

리더 없는 복제

모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있게 허용하는 접근 방식이다.

리더 없는 복제는 아마존이 내부 다이나모(Dynamo) 시스템에서 사용한 후 다시 유행했다.
다이나모에서 영감을 얻은 리더 없는 복제 모델의 오픈 소스 데이터스토어를 다이나모 스타일 이라 하며, 리악, 카산드라, 볼드모트가 존재한다.

전송 방식

• 클라이언트가 여러 복제 서버에 직접 전송 방식
• 코디네이터 노드가 중간에서 복제 서버에 전송하는 방식
  특정 순서로 쓰기를 수행하지는 않음

노드가 다운됐을 때 데이터베이스에 쓰기

여러 복제 서버 중 하나를 사용할 수 없어도 장애 복구가 필요하지 않다.

복제 서버 3이 다운된 동안 발생한 모든 쓰기는 해당 노드에서 누락됐다.
결과적으로 클라이언트가 복제 서버 3에서 데이터를 읽는다면 오래된(outdated) 값을 얻을 수 있다.

이 문제를 해결하기 위해서 읽기 요청을 병렬로 여러 노드에 전송 한다.
이때 받은 여러 요청의 결과 중 버전 숫자를 사용해서 어떤 값이 최신 내용인지 결정한다.

읽기 복구와 안티 엔트로피

위의 그림에서 복제서버 3이 누락된 쓰기를 따라잡는 방법이 여러가지 있다.
그 중 두 가지 메커니즘이 주로 사용된다.

1. 읽기 복구
   클라이언트는 복제 서버 3의 값이 오래된 값이라는 사실을 버전 값을 사용해 알게 된다.
   그리고 클라이언트는 해당 복제 서버에 새로운 값을 다시 기록한다.
2. 안티 엔트로피 처리
   백그라운드 프로세스를 두고 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 하나의 복제 서버에서 다른 서버로 복제한다.
   특정 순서로 쓰기를 복사하기 때문에 데이터가 복사되기까지 상당한 지연이 있을 수 있다.

읽기와 쓰기를 위한 정족수

정족수란 몇 개의 서버로 부터 읽기 요청과 쓰기 요청을 어느 범위까지 허용할지에 대한 내용이다.

일반화해서 보자면 아래와 같다.
n : 복제 서버(클러스터에 n개 이상의 노드가 있을 수 있음)
w : 모든 쓰기는 최소 w개의 노드에서 성공
r : 모든 읽기는 최소 r개의 노드에서 질의
w + r > n이면 읽을 때 최신 값을 얻은 것으로 기대한다.

다이나모 스타일 데이터베이스에서는 n, w, r 파라미터는 대개 설정 가능하다.

정족수 일관성의 한계

w + r > n인 경우에 오래된 값을 반환하는 에지 케이스가 존재한다.

• 느슨한 정족수를 사용한다면 w개의 쓰기는 r개의 읽기와 다른 노드에서 수행될 수 있다.
  r개의 노드와 w개의 노드가 겹치는 것을 보장하지 않음
  느슨한 정족수 : 정족수를 만족하지 않더라도 쓰기를 받아들이고 홈 노드에 속하지 않지만 연결할 수 있는 노드로써 기록
• 두 개의 쓰기가 동시에 발생하면 어떤 쓰기가 먼저 일어났는지 분명하지 않음
  해결책으로 동시 쓰기를 합치는 방법(“쓰기 충돌 다루기” 참고)
  승자를 타임스탬프 기반으로 결정한다면 시계 스큐(clock skew)로 인해 쓰기가 유실될 수 있음
• 쓰기가 읽기와 동시에 발생하면 읽기가 최신 값을 반환하는지 불분명
  쓰기가 일부 복제 서버에만 반영될 수 있기 때문
• 쓰기가 w보다 적은 서버에서 성공하더라도 성공한 복제 서버에서는 롤백하지 않음
  이어지는 읽기에 해당 쓰기 값이 반환될 수도 있고 아닐 수도 있다.
• 새 값을 가진 노드가 고장나면, 이전 값을 가진 노드가 이전 값을 전파하여 복원되는 경우
  새로운 값을 저장한 복제 서버 수가 w보다 낮아져 정족수 조건이 깨질 수 있음
• 모든 과정이 올바르게 동작해도 시점 문제로 에지 케이스가 존재할 수 있음

즉, 매개변수 w와 r로 오래된 값을 읽는 확률을 조정할 수 있지만 절대적으로 보장할 수는 없다.
“복제 지연 문제”에서 설명한 보장을 대개 받을 수 없기에 관련된 이상 현상이 발생할 수 있다.

견고한 보장은 일반적으로 트랜잭션이나 합의가 필요하다.

최신성 모니터링

운영 관점에서 데이터베이스가 최신 결과를 반환하는지 여부를 모니터링하는 일은 중요하다.

복제 형식에 따른 분류

1. 리더 기반 복제
   데이터베이스는 일반적으로 복제 지연에 대한 지표를 노출하며 이 지표는 모니터링 시스템에 제공된다.
   현재 위치에서 팔로워의 현재 위치를 빼면 복제 지연량을 측정할 수 있다.
2. 리더 없는 복제
   쓰기가 적용된 순서를 고정할 수 없어서 모니터링이 조금 더 어려움
   데이터베이스가 읽기 복구만 사용한다면 자주 읽히지 않는 값이 얼마나 오래된 것인지에 대한 제한이 없다.

최종적 일관성은 의도적으로 모호한 보장이지만 운용성을 위해서는 “최종적”을 정량화할 수 있어야 한다.

느슨한 정족수와 암시된 핸드오프

적절히 설정된 정족수가 있는 데이터베이스는 장애 복구 없이 개별 노드 장애를 용인한다.
요청은 w나 r개 노드가 응답할 때 반환할 수 있어 개별 노드의 응답이 느려지는 것도 허용 가능하다.

리더 없는 복제가 매력적인 경우

• 높은 가용성과 낮은 지연 시간이 필요한 경우
• 오래된 값 읽기를 허용하는 경우

노드가 n개 이상인 대규모 클러스터에서 클라이언트는 네트워크 장애 상황에서 정족수 구성에 들어가지 않는 데이터베이스 노드에 연결될 가능성이 있다.
이 경우 데이터베이스 설계자는 트레이드오프에 직면한다.

1. w나 r 노드 정족수를 만족하지 않는 모든 요청에 오류를 반환
2. 일단 쓰기를 받아들이고 값이 보통 저장되는 “홈” 노드에 속하지 않지만 연결할 수 있는 노드에 기록

2번을 느슨한 정족수 라고 한다.
쓰기와 읽기는 여전히 w와 r의 성공 응답이 필요하지만 값을 위해 지정된 n개의 “홈” 노드에 없는 노드가 포함될 수 있다.

네트워크 장애 상황이 해제 되면 한 노드가 다른 노드를 위해 일시적으로 수용한 모든 쓰기를 해당 “홈” 노드로 전송한다.
이것을 암시적 핸드오프 라고 한다.

느슨한 정족수는 쓰기 가용성 및 지속성을 높이는 데 특히 유용하다.
이는 모든 일반적인 다이나모 구현에서 선택 사항이다.

다중 데이터센터 운영

리더 없는 복제도 동시 쓰기 충돌, 네트워크 중단, 지연 시간 급증을 허용하기에 다중 데이터센터 운영에 적합하다.

카산드라와 볼드모트는 일반적인 리더 없는 모델에 다중 데이터센터 지원을 구현했다.

• n개의 복제 서버 수에는 모든 데이터센터의 노드가 포함
• 각 데이터센터마다 n개의 복제 서버 중 몇 개를 보유할지를 지정
• 클라이언트의 각 쓰기는 데이터센터 상관없이 모든 복제 서버에 전송
• 데이터센터 간 연결의 지연과 중단에 영향을 받지 않음
  클라이언트는 보통 로컬 데이터센터 안에서 정족수 노드의 확인 응답을 기다리기 때문
  보통 쓰기는 비동기로 처리

리악의 경우

• n은 하나의 데이터센터 안에 있는 복제 서버 수
• 데이터센터 간 복제는 백그라운드에서 비동기
  방식은 다중 리더 복제와 유사

동시 쓰기 감지

다이나모 스타일 데이터베이스는 여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용한다.
그래서 엄격한 정족수를 사용하더라도 충돌이 발생한다.
이런 상황은 다중 리더 복제의 “쓰기 충돌 다루기”와 유사하다.
또한 읽기 복구나 암시된 핸드오프 중에도 발생할 수 있다.

문제는 이벤트가 다른 노드에 다른 순서로 도착할 수 있다는 것 이다.
이는 다양한 네트워크 지연과 부분적인 장애 때문이다.

다른 순서로 쓰기 이벤트가 도착하거나 순간적인 노드 장애로 인해 노드간의 데이터가 서로 달라진 상황을 아래 그림에서 확인할 수 있다.

최종적인 일관성을 달성하기 위해 애플리케이션 개발자는 데이터베이스 내부에서 충돌을 어떻게 다루는지 잘 알아야 한다.

최종 쓰기 승리(동시 쓰기 버리기)

“예전” 값을 버리고 가장 “최신” 값으로 덮어쓰는 방법이다.
어떤 쓰기가 “최신”인지 명확하게 결정할 수 있는 한 모든 쓰기는 최종적으로 모든 복제 서버에 복사되므로 복제본은 최종적으로 동일한 값으로 수렴한다.

여기에서 “최신”은 확실하게 구분하기 힘든 경우가 많다.
이렇게 “최신”이 확실하지 않다면 이벤트의 순서를 정할 수 없기에 동시 쓰기라 해야 한다.

비록 쓰기는 자연적인 순서가 없지만 임의로 순서를 정할 수 있다.
예를 들어 쓰기에 타임스탬프를 붙여서 최종 쓰기 승리(LWW)라 부르는 충돌 해소 알고리즘을 사용할 수도 있다.

LWW는 최종적 수렴 달성이 목표이지만 지속성을 희생한다.
결국 여러 쓰기 중 최신의 쓰기가 남고 그외의 쓰기는 버리기 때문이다.
손실 데이터를 허용하지 않는다면 LWW는 충돌 해소에 적합하지 않다.
보통 캐싱과 같이 손실된 쓰기를 허용하는 경우가 있다.

LWW로 데이터베이스를 안전하게 사용하는 유일한 방법은 키를 한번 만 사용하는 것이다.(이후 불변)
이 방법은 같은 키를 동시에 갱신하는 상황을 방지한다.

“이전 발생” 관계와 동시성

두 가지 작업이 동시에 수행됐는지 여부에 대해 어떻게 결정되는지 알아보자.

몇 가지 예를 살펴보자.

1. 두 개의 쓰기에 순서가 존재하는 경우(클라이언트 시점)
   A(1 입력) -> B(A++)인 경우
   B는 A에 인과성이 있다.(causally dependent)
2. 두 개의 쓰기가 동시에 수행된 경우(클라이언트 시점)
   각 클라이언트가 작업을 시작할 때 다른 클라이언트가 동일한 키에 대한 작업을 수행했는지 알지 못한다.
   따라서 작업 간에 인과성이 없다.

작업 A가 다른 작업 B 보다 이전 발생(happens-before)라고 말하는 경우는 아래와 같다.

• 작업 B가 작업 A에 대해서 아는 경우
• 작업 B가 작업 A에 의존 하는 경우
• 작업 B가 작업 A를 기반으로 작업 하는 경우

즉, 한 작업이 다른 작업 이전에 발생했는지가 동시성을 의미를 정의하는 핵심이다.
한 작업이 다른 작업보다 먼저 발생(happens-before)하지 않으면 단순히 동시 작업 이라 말한다.

두 작업이 동시성인지 아닌지 알 수 있는 알고리즘이 필요하다.
한 작업이 다른 작업 전에 발생했다면 나중 작업은 이전 작업을 덮어쓸 수 있다.
하지만 작업이 동시에 발생하면 충돌을 해소해야 한다.

이전 발생 관계 파악하기

두 작업이 동시성인지 아닌지 여부를 결정하는 알고리즘을 살펴보자.
여기서는 상황을 단순하게 만들기 위해 하나의 복제본을 가진 데이터베이스에서 시작한다.

위의 그림의 작업 간 데이터플로를 아래에서 도표로 보여준다.
화살표는 어떤 작업이 다른 작업 이전에 발생했는지와 나중 작업이 이전 작업에 수행된 작업을 알거나 의존했다는 사실이다.

서버는 버전 번호를 보고 두 작업이 동시에 수행됐는지 여부를 결정할 수 있다.
값 자체가 데이터 구조인 셈이다.
해당 알고리즘은 다음과 같이 동작한다.

• 서버가 모든 키에 대한 버전 번호를 유지, 키를 기록할 때마다 버전 번호를 증가
• 클라이언트가 키를 읽을 때 서버는 최신 버전과 덮어쓰지 않은 모든 값을 반환
  클라이언트는 쓰기 전에 키를 읽어야 한다.
• 클라이언트가 키를 기록할 때 이전 읽기 버전 번호를 포함
  또한 이전 읽기에서 받은 모든 값을 합쳐야 한다.
• 서버가 특정 버전 번호를 가진 쓰기를 받을 때 해당 버전 이하 모든 값을 덮어쓸 수 있다.
  하지만 높은 버전 번호의 모든 값은 유지

동시에 쓴 값 병합

해당 알고리즘은 어떤 데이터도 자동으로 삭제되지 않음을 보장한다.
하지만 클라이언트가 추가적으로 작업을 해줘야 한다.
여러 작업이 동시에 발생하면 클라이언트는 동시에 쓴 값을 합쳐 정리해야 한다.
리악은 이런 동시 값을 형제(sibling) 값이라 한다.

형제 값 병합은 다중 리더 복제에서 충돌을 해소하는 문제와 본질적으로 같다.

위의 장바구니 예제에서 형제를 병합하는 합리적인 접근 방식은 합집합을 취하는 것이다.
하지만 상품을 제거도 할 수 있게 하려면 합집합으로는 올바른 결과를 얻을 수 없다.
단순히 삭제하는 것으로는 상품을 제거할 수 없다.
제거된 상품이 다시 나타날 수 있다.
이를 위해서 툼스톤 이라는 방법을 사용한다.
형제를 병합할 때, 상품이 제거됐음을 나타내는 표시를 해당 버전에 남기는 것이다.

애플리케이션 코드에서 형제 병합은 복잡하고 오류가 발생하기 쉽다.
이런 것을 자동으로 수행하기 위한 몇 가지 노력이 있다.
예를 들어서 리악은 CRDT라는 방법을 사용한다.

버전 벡터

장바구니 예제는 단일 복제본을 사용했다.
다중 복제본인 경우 살펴보자.

장바구니 예제는 의존성 파악을 위해 단일 버전을 사용했다.
다중 복제본인 경우 키당 버전 번호 뿐만 아니라 복제본당 버전 번호 도 사용해야 한다.

모든 복제본의 버전 번호 모음을 버전 벡터(version vector) 라고 부른다.
이를 변경한 몇 가지 방법 중 도티드 버전 벡터(dotted version vector) 란 것도 있다.

버전 벡터를 사용하면 데이터베이스는 덮어쓰기와 동시 쓰기를 구분할 수 있다.
참고 : version vector