TIL

05장 복제

• 복제가 필요한 이유
  • 지리적으로 사용자와 가깝게 데이터를 유지해 지연 시간을 줄인다.
  • 시스템 일부에 장애가 발생해도 지속적으로 동작할 수 있게 가용성을 높인다.
  • 읽기 질의를 제공하는 장비 수를 확장해 읽기 처리량을 늘린다.
• 복제에서 모든 어려움은 복제된 데이터의 변경 처리에 있다.
• 노드 간 변경 복제를 위한 세 가지 인기 알고리즘이 있다.
  • 단일 리더 (single-leader)
  • 다중 리더 (multi-leader)
  • 리더 없는 (leaderless)

리더와 팔로워

• 복제 서버(replica) : 데이터베이스 복사본을 저장하는 각 노드
• 리더 기반 복제(leader-based replication)
  • 또는 능동/수동, 마스터 슬레이브 복제라고도 한다.
  • 복제 서버 중 하나를 리더(마스터 or 프라이머리)로 지정 후 리더가 먼저 데이터를 기록하게 된다.
  • 다른 복제 서버(팔로워 or 슬레피브)는 리더의 데이터 변경을 복제 로그나 변경 스트림 일부로 전달 받아 복사본을 갱신한다.
  • 쓰기는 리더에게만 허용되고 질의는 팔로워에게 가능하다.
• 이러한 복제 모드는 다양한 데이터베이스에 내장된 기능으로 제공한다.

동기식 대 비동기식 복제

• 동기식 복제
  • 리더는 팔로워가 쓰기를 수신했는지 확인할 때까지 대기한다.
  • 메시지 처리 전까지 상당한 지연이 발생할 수 있다.
  • 장점은 리더와 팔로워가 일관성 있게 최신 데이터 복사본을 가지는 것을 보장한다.
  • 단점은 팔로워가 응답하지 않는다면 쓰기가 처리될 수 없다.
• 비동기식 복제
  • 리더는 팔로워가 수신했는지 기다리지 않는다.
  • 리더에만 쓰기를 성공하면 되기에 지연이 낮다.
  • 팔로워가 응답하지 않더라도 서비스를 지속할 수 있다.
• 보통 리더 기반 복제는 완전 비동기식으로 구성한다.
  • 팔로워에 쓰기가 유실될 수 있어 지속성을 보장하지는 못한다.
  • 그럼에도 비동기식 복제는 많이 사용되는 방식이다.

새로운 팔로워 설정

• 새로운 팔로워를 설정해야할 때가 있다.
  • 복제 서버 수 증설
  • 장애 노드의 대체
• 새로운 팔로워 설정 시 리더의 데이터를 복사하는 방식
  • 전체 데이터베이스를 가능한 잠그지 않고 스냅숏을 가져온다.
  • 스냅숏을 새로운 팔로워 노드에 복사한다.
  • 팔로워는 리더에 연결해 스냅숏 이후의 데이터 변경을 요청한다.
  • 팔로워가 스냅숏 이후 변경의 미처리분을 모두 처리했을 때 따라잡았다고 말하고 이제부터 리더에 발생하는 데이터 변화를 이어 처리 가능하다.

노드 중단 처리

• 팔로워 장애: 따라잡기 복구
  • 팔로워는 리더로부터 수신한 데이터 변경 로그를 보관한다.
  • 팔로워에 장애가 발생하면 마지막으로 처리된 트랜잭션의 변경 로그를 확인해 복구되고 나서 이후 데이터 변경을 모두 리더에게 요청할 수 있다.
  • 변경이 모두 적용되면 리더를 따라잡게 된다.
• 리더 장애: 장애 복구 (fail over)
  • 리더에 장애 발생 시 팔로워 중 하나를 새로운 리더로 승격해야 한다.
  • 클라이언트는 새로운 리더로 연결을 재설정해야하며 팔로워 또한 새로운 리더로부터 데이터 변경을 소비하기 시작해야 한다.
  • 이 같은 장애 복구는 수동 또는 자동으로 진행할 수 있는데 꽤나 까다롭다.

복제 로그 구현

• 구문 기반 복제
  • 리더가 모든 쓰기 요청(구문(statement))을 기록한 뒤 쓰기 실행 후 구문 로그를 팔로워에 전송
  • 팔로워는 SQL 구문을 파싱하고 실행한다.
  • 구문 기반 복제의 허점
    • NOW나 RAND 같은 비결정적 함수 호출은 복제 서버마다 다른 값을 생성할 수도 있다.
    • 자동증가 칼럼 같이 DB 데이터에 의존한다면 각 복제 서버에서 정확히 같은 순서로 실행되지 않으면 다른 결과가 나올 수 있다.
    • 부수 효과를 가진 구문은 각 복제 서버에서 다른 부수 효과가 발생할 수도 있다.
• 쓰기 전 로그 배송
  • 모든 쓰기를 append-only 바이트 열 로그로 저장하고 팔로워가 이 로그를 처리하면 리더와 정확히 같은 데이터 구조의 복제본을 만들 수 있다.
  • PostgreSQL과 오라클 등에서 사용된다.
  • 쓰기 전 로그 배송의 단점
    • 로그가 제일 저수준의 데이터를 기록하기에 저장소 엔진과 밀접하게 엮인다.
    • 데이터베이스가 저장소 형식을 다른 버전으로 변경한다면 리더와 팔로워의 소프트웨어 버전을 다르게 실행할 수 없다.
    • 만약 복제 프로토콜이 버전 불일치를 허용하지 않는다면 업그레이드 시 다운 타임이 필요하다.
• 논리적(로우 기반) 로그 복제
  • 복제 로그와 저장소 엔진 내부를 분리하기 위해 논리적 로그(logical log)를 사용하는 형식
  • 관계형 데이트베이스용 논리적 로그는 대개 로우 단위의 레코드 열이다.
    • 삽입된 로우의 로그는 모든 칼럼의 새 값을 포함
    • 삭제된 로우의 로그는 로우를 색별하는 정보를 포함
    • 갱신된 로우의 로그는 로우를 식별하는 정보와 모든 칼럼의 새 값을 포함
  • MySQL의 이진 로그가 이 접근 방식을 사용
  • 논리적 로그는 저장소 엔진 버전을 다르게 실행해도 호환 가능하다.
  • 논리적 로그 형식은 외부 애플리케이션이 파싱하기 쉬운 구조이기도 하다.
• 트리거 기반 복제
  • 위 복제 방식들과 달리 유연성이 필요한 경우 트리거를 통해 사용자 정의 코드를 등록할 수 있다.
    • ex) 관계형 데이터베이스에서 사용하는 트리거 or 스토어드 프로시저
  • 사용자 정의 애플리케이션 코드는 데이터가 변경되면 자동으로 실행된다.
    • 데이터 변경을 분리된 테이블에 로깅할 수 있는 기회를 가져 외부 프로세스가 이를 읽을 수도 있다.
  • 트리거 기반 복제는 많은 오버헤드가 발생하지만 유연성 때문에 유용한 경우가 있다.

복제 지연 문제

• 애플리케이션이 비동기 팔로워에서 데이터를 읽을 때 팔로워가 뒤쳐진다면 지난 정보를 볼 수도 있다.
• 물론 이러한 불일치는 일시적인 상태이고 최종적 일관성에 의해 팔로워는 결국 리더와 일치하게 될 것이다.
• 하지만 시스템이 가용량 근처에서 동작하거나 네트워크 문제 발생 시 지연은 수 초에서 수 분으로 증가하며 문제가 발생할 수 있다.

자신이 쓴 내용 읽기

• 복제 지연으로 인해 사용자가 자신이 제출한 데이터를 즉시 볼 수 없다면 데이터가 유실된 것처럼 보일 것이다.
• 쓰기 후 읽기 일관성
  • 사용자가 페이지를 재로딩 했을 때 자신의 모든 갱신을 볼 수 있음을 보장
  • 다른 사용자에 대해선 일정 시간 이후까지 갱신을 보장하지 않을 수도 있다.
• 리더 기반 복제 시스템에서 쓰기 후 읽기 일관성 보장 방법들
  • 사용자가 수정한 내용은 무조건 리더에서 읽기를 보장
    • ex) 소셜 네트워크에서 사용자 프로필(자신의 데이터) 질의는 무조건 리더에서 하도록 규칙 지정
  • 마지막 갱신 시각 기준 1분 동안은 리더에서 모든 읽기를 수행
    • 애플리케이션 내 대부분 내용을 사용자가 편집 가능하다면 생각할 수 있는 방안
    • 또한 복제 지연을 모니터링하여 리더보다 1분 이상 늦은 모든 팔로워에 대한 질의를 금지할 수 있다.
  • 클라이언트가 가장 최근 쓰기의 타임프탬프를 기억하고 복제 서버가 아직 최신 내용이 아닌 경우에는 다른 복제 서버가 읽기를 처리하거나 따라잡을 때까지 질의를 대기시킬 수 있다.
• 동일 사용자가 여러 디바이스로 접근할 때 디바이스 간 쓰기 후 일관성을 제공해야 한다면 고려할 점이 늘어난다.
  • 사용자의 마지막 갱신 타임스탬프를 기억하려면 다른 디바이스의 갱신 시각은 알 수 없기에 이 메타데이터는 중앙집중식으로 관리해야 한다.
  • 복제 서버가 여러 데이터센터 간 분산돼 있다면 사용자 디바이스의 요청을 동일 데이터센터로 라우팅해야 한다.

단조 읽기

• 비동기식 팔로워 환경에선 시간이 거꾸로 흐르는 현상을 볼 수도 있다.
  • 서로 다른 복제 서버에서 여러 읽기를 수행할 때 첫 번째 질의보다 두 번째 질의에서 더 과거의 데이터를 불러올 수도 있다.
• 단조 읽기 (monotonic read)
  • 시간이 거꾸로 흐르는 현상이 발생하지 않게 보장하는 방법
  • 강한 일관성보다는 덜하지만 최종적 일관성보다는 더 강한 보장이다.
  • 데이터를 읽을 때 이전 값을 볼 수도 있지만 여러 번 반복해 읽어도 시간이 되돌아가는 현상은 적어도 방지한다.
• 단조 읽기를 달성하는 한 방법은 읽기가 항상 동일한 복제 서버에서 수행되게끔 하는 것이다.

일관된 순서로 읽기

• 세 번째 복제 지연 이상 현상으로 ‘인과성 위반’이 있다.
  • ex) A와 B의 채팅 대화를 재 3자인 C가 관찰할 때 B가 질문하기도 전에 A의 대답이 먼저 채팅창에 보이는 현상이 발생할 수도 있다.
  • 파티셔닝(샤딩된) 데이터베이스에서 서로 다른 파티션은 독립적으로 동작하기 때문에 발생하는 문제로 쓰기의 전역 순서가 없다.
• 인과성 위반을 방지하려면 ‘일관된 순서로 읽기(Consistent Prefix Read)’가 필요하다.
  • 일련의 쓰기가 특정 순서로 발생한다면 모든 사용자는 같은 순서로 쓰여진 내용을 보게 됨을 보장
  • 한 가지 해결책으로는 인과성이 있는 데이터는 동일 파티션에 기록되게끔 하는 방법이 있지만 일부 애플리케이션에선 효율적이지 않다.

복제 지연을 위한 해결책

• 복제는 비동기식으로 동작하지만 사용자에겐 동기식으로 동작하는 척 하는 것이 문제 해결 방안이다.
• 트랜잭션은 애플리케이션이 더 단순해지기 위헤 데이터베이스가 제공하는 강력한 보장이다.
• 하지만 분산 환경에서 트랜잭션은 성능과 가용성 측면에서 너무 비싸고 확장성이 없다.
• 때문에 최종적 일관성을 사용해야 한다는 주장이 있고 일부 사실이지만 지나치게 단순화된 대답이다.

다중 리더 복제

• 리더가 하나만 존재한다면 이 리더에 장애 발생 시 쓰기를 할 수 없게 된다.
• 다중 리더 설정
  • 쓰기를 허용하는 노드를 하나 이상 두는 것
  • 쓰기 처리를 하는 각 노드는 데이터 변경을 다른 모든 노드에 전달해야 한다.
• 단일 데이터센터 내 다중 리더 설정은 복잡도에 비해 이점이 크지 않지만 몇 가지 상황에선 합리적이다.

사용 사례 1 - 다중 데이터센터 운영

• 다중 데이터센터인 경우 각 데이터센터마다 리더가 있을 수 있다.
  • 다중 데이터센터의 경우 지리적으로 떨어진 곳에 위치하기에, 리더가 하나라면 지리적으로 멀리 떨어진 데이터센터를 거쳐야 쓰기를 수행하게 된다.
• 다중 데이터센터 복제 방식
  • 각 데이터센터 내에선 보통의 리더 팔로워 복제 사용
  • 데이터 센터 간에는 각 리더가 다른 데이터센터의 리더에게 변경 사항을 복제
• 다중 데이터센터에서 다중 리더 설정이 가지는 이점
  • 모든 쓰기는 로컬 데이터센터에서 처리한 다음 비동기로 다른 데이터센터에 복제한다.
    • 단일 리더 설정이었다면 모든 쓰기가 인터넷을 통해 리더가 있는 데이터센터로 이동해야 하는데 이는 지연을 상당히 발생시킨다.
  • 각 데이터 센터는 다른 데이터센터와 독립적으로 동작하기에 중단 내성이 높다.
    • 고장난 데이터센터가 온라인으로 돌아왔을 때 복제를 따라잡으면 된다.
  • 비동기 복제를 사용하는 다중 리더 설정에선 네트워크 문제에 보다 잘 견딘다.
    • 일시적인 중단에도 쓰기 처리는 진행되기 때문
    • 단일 리더였다면 쓰기가 동기식이기에 데이터센터 내 연결 문제에 매우 민감하다.
• 일부 데이터베이스는 기본적으로 다중 리더 설정을 제공한다.
  • MySQL의 텅스텐 리플리케이터(Tungsten Replicator)
  • PostgreSQL의 BDR
  • 오라클의 골든게이트
• 다중 리더 복제의 단점
  • 동일한 데이터를 다른 두 데이터센터에서 동시에 변경할 수 있는 쓰기 충돌을 반드시 해소해야 한다.
  • 많은 데이터베이스에 새로 추가된 기능이기에 미묘한 설정상 실수나 뜻밖의 상호작용이 있을 수 있다.

사용 사례 2 - 오프라인 작업을 하는 클라이언트

• 인터넷 연결이 끊어진 동안 애플리케이션이 계속 동작해야 한다면 다중 리더 복제가 적절하다.
• 오프라인에서 동작하려면 모든 디바이스에는 리더처럼 동작하는 로컬 데이터베이스가 있어야 한다.
  • 모든 디바이스 상에서 서버 간 다중 리더 복제를 비동기 방식으로 수행해야한다.
  • 아키텍처 관점에서 이 설정은 근본적으로 다중 리더 복제와 비슷하다.

사용 사례 3 - 협업 편집

• 실시간 협업 편집 애플리케이션
  • 동시에 여러 사람이 문서를 편집 가능한 애플리케이션
• 협업 편집은 오프라인 편집 사용 사례와 공통점이 많다.
  • 한 사용자의 변경 내용을 즉시 로컬 복제 서버에 적용 후 다른 사용자와 비동기 방식으로 복제한다.
• 편집에 충돌이 없음을 보장하려면 편집 전에 문서의 잠금을 획득해야 한다.
  • 리더에서 트랜잭션을 사용하는 단일 리더 복제와 동일
  • 더 빠른 협업을 위해 변경 단위를 매우 작게 해서 잠금을 피할 수도 있다.

쓰기 충돌 다루기

• 다중 리더 복제에서 제일 큰 문제는 쓰기 충돌이 발생한다는 점이다.
• 동기 대 비동기 충돌 감지
  • 이론적으로 충돌 감지는 동기식으로 만들 수 있지만 다중 리더 복제의 주요 장점(각 복제 서버가 독립적으로 쓰기를 허용)을 잃는다.
  • 동기식 충돌 감지를 하려면 단일 리더 복제만 사용해야 할 수도 있다.
    • 첫 번째 쓰기가 완료될 때까지 두 번째 쓰기를 차단
    • 단일 리더 데이터베이스에선 순차적인 쓰기를 적용 가능
• 충돌 회피
  • 특정 레코드의 모든 쓰기가 동일 리더를 거치도록 보장한다면 충돌은 발생하지 않는다.
  • 특정 사용자의 요청을 동일한 데이터센터로 항상 라우팅하여 읽고 쓰도록 보장
  • 때때로 한 데이터센터가 고장나 다른 데이터센터로 라우팅해야 하는 경우 충돌 회피가 실패한다.
• 일관된 상태 수렴(convergent)
  • 모든 복제 계획은 모든 복제 서버가 최종적으로는 동일하다는 사실을 보장해야 하며 모든 변경이 복제 서버에 동일 최종 값이 전달되어야 한다.
  • 최종 쓰기 승리 - 각 쓰기에 고유 ID를 부여하고 가장 높은 ID를 가진 쓰기를 골라 모든 복제 서버에 적용 후 다른 쓰기는 버린다.
  • 각 복제 서버에 고유 ID를 부여하고 높은 숫자의 복제 서버에서 생긴 쓰기를 우선적으로 적용되게 하는 방법도 있다.
    • 최종 쓰기 승리 방법과 마찬가지로 데이터 유실 위험이 있다.
  • 명시적 데이터 구조에 충돌을 기록해 모든 정보를 보존하여 나중에 충돌을 해소하는 애플리케이션 코드를 작성하는 방법도 있다.
• 사용자 정의 충돌 해소 로직
  • 대부분의 다중 리더 복제 도구는 애플리케이션 코드로 충돌 해소 로직을 작성한다.
  • 충돌 해소는 보통 전체 트랜잭션이 아닌 개별 로우나 문서 수준에서 적용된다.

다중 리더 복제 토폴리지

• 복제 토폴로지 - 쓰기를 한 노드에서 다른 노드로 전달하는 통신 경로를 설명
  • 리더가 둘 이상이라면 다양한 토폴로지가 가능
• 전체 연결 (all-to-all)
  • 모든 리더가 각자의 쓰기를 다른 모든 리더에게 전송
• 원형 토폴로지 (circular topology)
  • 각 노드가 하나의 노드로부터 쓰기를 받고, 하나의 노드에만 쓰기를 전달
• 별 모양 토폴로지
  • 지정된 루트 노드 하나가 다른 모든 노드에게 쓰기를 전달
• 원형과 별 모양 토폴로지의 단점
  • 쓰기가 모든 복제 서버에 도달하려면 여러 노드를 거쳐야 한다.
  • 한 노드에 장애가 발생하면 해당 노드가 복구될 때까지 통신을 할 수 없다.
• 전체 연결 토폴로지의 단점
  • 일부 네트워크 연결이 다른 연결보다 빠르다면 일부 복제 메시지가 다른 메시지를 추월할 수 있다.
  • 추월 문제는 인과성 문제를 초래할 수 있다.
  • 쓰기를 올바르게 정렬하기 위해 버전 백터(version vector) 기법을 사용할 수도 있지만 다중 리더 복제 시스템에서 충돌 감지는 제대로 구현되지 않았다.

리더 없는 복제

• 일부 데이터 저장소는 리더 개념을 버리고 모든 복제 서버가 쓰기를 받을 수 있게 허용하는 접근 방식을 사용한다.
  • ex) 다이나모(Dynamo), 카산드라, 볼드모트 등
  • 다이나모로부터 파생된 스타일이기에 다이나모 스타일의 데이터베이스라 부른다.

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

• 리더 없는 복제에선 클라이언트가 여러 복제 서버에 요청을 병렬로 전송한다.
• 리더 없는 설정에선 복제 서버 중 하나애 장애가 발생해도 복구가 필요하지 않는다.
  • 사용 가능한 다른 복제 서버에 쓰기를 전송하면 되기 때문
• 다운되었던 복제 서버에선 오래된 데이터가 있을 수 있는데 이 또한 문제되지 않는다.
  • 읽기 요청도 여러 서버에 병렬로 요청하여 제일 최신값을 버전을 이용해 판별하고 사용한다.
• 다이나모 스타일에서 다운되었던 노드가 누락된 쓰기를 반영하는 메커니즘
  • 읽기 복구
    • 클라이언트가 여러 노드에서 병렬로 읽기를 수행
    • 버전을 이용해 오래된 값을 반환한 노드를 인식하고 해당 노드에 새로운 값을 다시 기록
  • 안티 엔트로피 처리
    • 백그라운드 프로세스를 통해 복제 서버 간 데이터 차이를 찾아 지속적으로 누락된 데이터를 복제한다.
    • 리더 기반 복제의 복제 로그와 달리 특정 순서로 쓰기를 복사하기에 상당한 지연이 있을 수 있다.
• 읽기와 쓰기를 위한 정족수
  • 장애 내성이 있다고는 하지만 복제 서버들 중 일정 수 이상은 쓰기를 받아들여야 성공한 것으로 간주한다.
  • w + r > n이면 읽을 때 최신 값을 얻을 것으로 기대하는데 이런 r과 w를 따르는 읽기와 쓰기를 정족수 읽기와 쓰기라고 부른다.
    • n: 복제 서버 수, w: 쓰기에 성공해야 하는 노드 수, r: 읽기 시 최소한 질의해야 하는 노드 수
  • 다이나모 스타일 데이터베이스에서 n, w, r은 대개 설정 가능하다.
    • 일반적으로 n을 홀수 (보통 3 or 5), w = r = (n + 1) / 2로 설정한다.

정족수 일관성의 한계

• w + r > n을 만족한다면 일반적으로 모든 읽기는 최신 값을 반환할 것을 기대한다.
  • w와 r이 작을수록 오래된 값을 읽을 확률이 높다.
  • 보통 r, w 값으로 노드의 과반수를 선택하는데 n/2 노드 장애까지 허용해도 w + r > n이 보장되기 때문
• 하지만 w + r > n인 경우에도 오래된 값을 반환하는 엣지 케이스가 있다.
  • w개 쓰기가 성공하지만 r개 읽기가 최신값이 쓰여진 w개와 겹치지 않는 경우
  • 쓰기 충돌이 발생하면 쓰기가 유실될 수 있다.
  • 쓰기와 읽기가 동시에 발생하면 읽기가 최신 값을 반환하는지 여부가 분명하지 않다.
  • 쓰기가 일부 복제 서버엔 성공, 다른 복제 서버에서 실패해 w개보다 성공 서버가 적다면 쓰기에 성공한 복제 서버는 롤백하지 않는다.
  • 새 값을 전달하는 노드 장애 시 예전 값을 가진 복제 서버로부터 데이터를 복구 받으면 새 값이 유실되어 정족수 조건이 깨진다.
  • 모든 과정이 올바르게 동작해도 시점 문제로 엣지 케이스가 발생할 수 있다. (선형성과 정족수)
• 다이나모 스타일 데이터베이스는 최종적 일관성을 허용하는 사용 사례에 최적화되어 있다.
  • w와 r로 오래된 값을 읽는 확률을 조정할 순 있지만 절대적이진 않다.
• 애플리케이션이 오래된 값 읽기를 허용하더라도 복제 상태에 대해 모니터링하는 일은 중요하다.
  • 리더 기반 복제와 달리 리더 없는 복제 시스템에선 쓰기 순서를 고정할 수 없어 모니터링이 더 어렵다.

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

• 노드가 n개 이상인 대규모 클러스터에서 네트워크 장애 시 트레이드 오프에 직면한다.
  • w나 r 노드 정족수를 만족하지 않는 모든 요청에 오류를 반환
  • 일단 쓰기를 받아들이고 값이 보통 저장되는 n개 노드에 속하지는 않지만 연결할 수 있는 노드에 기록
• 후자를 ‘느슨한 정족수’라 부른다.
  • 쓰기, 읽기는 여전히 w와 r의 성공 응답이 필요
  • 하지만 값을 위해 지정된 n개의 “홈” 노드에 없는 노드가 포함될 수 있다.
• 암시된 핸드오프
  • 네트워크 장애 상황이 해제되면 노드가 일시적으로 수용한 모든 쓰기를 “홈” 노드로 전송하는 방식
• 느슨한 정족수는 쓰기 가용성을 높이는 데 특히 유용하다.
  • 암시된 핸드오프가 완료될 때까지 r 노드의 읽기가 최신 데이터를 본다는 보장은 없다.
• 리더 없는 복제는 동시 쓰기 충돌, 네트워크 중단, 지연 시간 급증을 허용하기에 다중 데이터센터 운영에 적합하다.

동시 쓰기 감지

• 다이나모 스타일에선 정족수를 사용해도 충돌이 발생한다.
  • 여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용하기 때문
  • 다양한 네트워크 지연과 장애로 인해 여러 노드에 이벤트가 다른 순서로 도달할 수도 있다.
• 최종 쓰기 승리 (LWW)
  • 쓰기에 타임스탬프를 붙이고 예전 쓰기를 최신 쓰기로 덮어쓰기 하는 방식
  • LWW는 지속성을 희생하는데 여러 동시 쓰기가 있다면 하나 말고 다른 쓰기는 조용히 무시된다.
  • 손실 데이터를 허용하지 않는다면 적합하지 않다.
  • 모든 쓰기에 UUID 등으로 고유한 키를 부여해서 불변 값으로 다루는 방식을 사용해 해결할 순 있다.
• “이전 발생” 관계와 동시성
  • 한 작업이 다른 작업 이전에 발생했는지가 동시성의 의미를 정의하는 핵심이다.
  • 두 작업이 동시성인지 아닌지 알 수 있는 알고리즘이 필요
• 이전 발생 관계 파악하는 알고리즘
  • 서버가 모든 키에 대한 버전 번호를 유지하고 키를 기록할 때마다 버전 정보를 증가시킨다.
  • 클라이언트가 키를 읽을 때 서버는 최신 버전 뿐 아니라 덮어쓰지 않은 모든 값을 반환
    • 클라이언트는 쓰기 전에 키를 읽어야 함
  • 클라이언트가 키를 기록할 때 이전 읽기의 버전 번호를 포함해야 하고, 이전 읽기에서 받은 모든 값을 합쳐야 한다.
  • 서버가 특정 버전 번호를 가진 쓰기를 받을 때 해당 버전 이하 모든 값을 덮어쓸 수 있다.
    • 높은 버전 번호의 모든 값은 유지해야 한다.
• 동시에 쓴 값 병합
  • 위 알고리즘은 클라이언트가 동시에 쓴 값을 합쳐 정리해야하는 데 이러한 동시 값을 형제(sibling) 값이라 한다.
  • 형제를 병합하는 합리적인 접근 방식은 합집합을 취하는 것이다.
    • 최종 쓰기 승리처럼 유실되는 값을 만들지 않는다.
  • 하지만 데이터를 추가하는 쓰기 이외에 제거도 할 수 있으려면 합집합으로는 부족하다.
  • 툼스톤 - 형제를 병합할 때 데이터가 제거 됐음을 나타내기 위한 표시로 해당 버전 번호에 남긴다.
• 버전 백터
  • 다중 복제본의 경우 키당 버전 번호뿐 아니라 복제본당 버전 번호도 사용해야 한다.
  • 각 복제본은 쓰기 처리 시 자체 버전 번호를 증가시키고 각기 다른 복제본의 버전 번호도 계속 추적한다.
  • 모든 복제본의 버전 번호 모음을 버전 벡터라 부른다.
  • 버전 백터 구조는 한 복제본을 읽고 다른 복제본에 다시 이어 쓰는 작업이 안전함을 보장하기에 형제가 올바르게 병합되는 한 데이터 손실은 없다.