개요

---

확장의 방법

• shared-memory architecures, vertical scaling, scaling up
  • 단점
    • 리소스 증가보다 더 크게 비용이 증가함
    • 내결함성이 제한적임
• shared-nothing architecures,, horizontal scaling, scaling out
  • 장점
    • 확장 성능 대비 가격이 더 좋음
    • 내결함성이 비교적 더 좋음

데이터 분산의 종류

• 복제: 동일한 데이터 셋의 복사본을 여러 노드에 유지
• 파티셔닝(샤딩): 데이터 셋을 나누어서 여러 노드에 할당

5장에서는 복제를 다룬다.

복제가 필요한 이유

• 내결함성(가용성) 향상: 시스템의 일부 노드에 장애가 발생해도 지속적으로 동작할 수 있게 함
• 성능 향상
  • 확장성 향상: 서비스 수행 장비를 늘림
  • 지역성 향상: 클라이언트에 지리적으로 가깝게 위치시켜 지연 시간을 줄임

복제가 어려운 이유

데이터 변경 처리.
5장에서는 이 내용을 주로 다룬다.

노드 간 변경을 복제 방법

복제 방법	장점	단점
단일 리더 복제	충돌 해소 우려 없음	가용성이 낮음
다중 리더 복제	결함 노드, 네트워크 중단, 지연 시간 급증이 있는 상황에도 가용성이 놓음	일관성이 보장되기 어려움
리더 없는 복제	(같은 이유로)가용성이 좋음	일관성이 보장되기 어려움

동기식, 비동기식 복제의 트레이드오프

대개 비동기식 쓰는 걸로.

복제 지연(replication lag) 문제

복제 지연과 관련된 개념을 살펴봄

• read-your-writes: 쓰기 후 읽기 일관성
• monotonic read: 단조 읽기
• consistent prefix read: 일관된 순서로 읽기
• 최종적 일관성

동시성 문제

쓰기의 동시성을 판별하는 방법, 충돌을 해결하는 알고리즘을 알아본다.

리더와 팔로워

---

리더 기반 복제

복제본이 저장된 노드를 replica(복제 서버) 라고 한다.
DB 에 대한 모든 쓰기는 replica 에 모두 반영되어야 한다.
가장 일반적인 해결책은 리더 기반 복제(leader-based replication) 이다.

리더기반복제

데이터 쓰기

1. 클라이언트의 쓰기 요청은 리더에게만 전달된다.
2. 리더는 로컬 DB 에 데이터를 쓴다.
3. 리더는 팔로워에게 replication stream 을 발행한다.
4. 팔로워는 로그를 받아서 로컬 DB 에 쓴다.

데이터 읽기

• 클라이언트는 읽기는 임의의 리더나 팔로워로부터 처리된다.

리더 기반 복제는 다음과 같은 여러 DB 서비스들에서 사용하고 있다.

• RDBMS: MySQL, Oracle Data Guard, AlwaysOn Availability Gropus
• NoSQL: MongoDB, ResyncDB, EspressoDB
• MessageQueue: Kafka, RabbitMQ

동기식 복제 vs 비동기식 복제

동기식 복제
리더가 팔로워의 데이터 갱신을 기다리고 클라이언트에게 성공 응답을 보낸다. 위 그림의 Follower1.

비동기식 복제
리더가 팔로워의 데이터 갱신을 기다리지 않고 클라이언트에게 성공 응답을 보낸다. 위 그림의 Follower2.

동기식의 장점

• 팔로워와 리더 간의 데이터 일관성을 보장한다.
• 리더의 순단시 팔로워가 읽기 처리를 대신할 수 있다.

동기식의 단점

• 팔로워가 응답하지 않으면 쓰기가 처리될 수 없다.
• 팔로워의 응답을 받을 때까지 리더가 block 될 수 있다.

동기식의 단점으로 인해, 모든 팔로워를 동기식으로 복제하는 것은 비현실적이다. 현실적으로 동기식 복제를 사용하는 방법은 반동기식(semi-synchronous) 복제 다.

• 하나의 팔로워만 동기식으로 복제하며, 나머지는 비동기식으로 복제한다.
• 동기식 팔로워가 다운되면 다른 팔로워 하나를 동기식으로 전환한다.

보통, 리더 기반 복제는 모두 비동기식 팔로워를 사용한다.
비동기식의 단점

• 쓰기가 리더엔 반영되어서 클라이언트에게 성공 응답이 보내져도, 팔로워에겐 반영되지 못할 수 있으며, 지속성을 보장하지 못한다.

비동기식의 장점

• 리더의 쓰기가 팔로워와의 상태와는 상관없이 중단되지 않는다.

새로운 팔로워 추가

replica 를 늘리거나 장애 노드의 대체하기 위해 새로운 팔로워를 추가할 수 있어야 한다.
새로운 팔로워는 리더의 데이터 복제본을 가지고 있음을 보장해야 한다.

기존의 노드들은 가용성을 위해 멈추지 않고 계속해서 데이터를 쓰고 있기 때문에, 특정 시점의 복사 작업은 새로운 팔로워의 데이터셋 일관성을 보장하지 못한다.

무중단으로 팔로워를 추가하는 방법
1. 리더의 DB 스냅샷을 일정 시점에 가져와서 팔로워 노드에 복사한다.
2. 팔로워는 리더에 연결하여 스냅숏 이후 발생한 모든 데이터 변경을 요청하여 처리한다.(catch-up)

노드 중단 처리

개별 노드의 장애에 전체 시스템이 동작하게 하여서 가용성을 확보하는 방법에 대해 팔로워 및 리더에게 장애가 발생한 경우로 나누어 알아본다.

팔로워 장애: 따라잡기 복구(catch-up recovery)

1. 각 팔로워는 리더로부터 수신한 데이터 변경 로그를 로컬 디스크에 보관한다.
2. 팔로워가 중단된 이후로 리더로부터 모든 데이터 변경을 요청하여 따라잡는다.(catch-up)

리더 장애: 장애 복구(failover)

리더에게 장애가 발생한 경우, 아래와 같은 처리가 필요하여 까다로운 편이다.

1. 팔로워를 새로운 리더로 승격한다.
2. 클라이언트는 새로운 리더를 위해 설정을 변경해야 한다.
3. 팔로워는 새로운 리더로부터 데이터 변경을 소비하기 시작해야 한다.

위와 같은 리더 장애를 복구하는 과정을 failover 라고 한다.

failover 는 수동 혹은 자동으로 진행하는 방법이 있다.
자동 failover 는 보통 다음의 단계로 구성된다.

1. 리더가 장애인지 판단한다. 대부분의 시스템은 타임아웃으로 판단한다.
2. 새로운 리더를 선택한다. 합의 과정이나 제어 노드에 의해 선택된다.
3. 새로운 리더 사용을 위해 시스템을 재설정한다. 시스템은 이전 리더가 복구된다 하더라도 해당 노드는 팔로워가 되도록 해야 한다.

자동 failover 는 다음과 같은 기술적 어려움이 있다.

1. 비동기식 복제를 사용하는 경우, 이전 리더가 실패한 쓰기를 어떻게 처리할 것인지 문제가 있다. 이전 리더의 복제되지 않은 쓰기를 단순히 폐기하는 방법이 일반적이나, 이 방법은 내구성을 악화시킨다.
2. out-of-date 팔로워가 리더로 승격되는 경우, 이미 쓰여진 키를 덮어쓸 위험이 있다.
3. 스플릿 브레인(split-brain) 현상, 즉, 두 노드가 자신이 리더라고 판단할 위험이 있다. 일부 시스템은 이런 현상이 감지되면, 하나의 노드를 종료하나, 주의 깊게 설계되지 않으면 두 개의 노드가 모두 종료될 위험이 있다.
4. 타임아웃의 적절한 정도를 설정하기 까다롭다. 타임 아웃의 시간이 길수록,failover 는 지연된다. 반대로 너무 짧으면, 불필요한 failover 가 발생할 수 있다.

복제 로그 구현

리더 기반 복제는 내부적으로 다양한 복제 방법을 사용한다. 이에 대해 간단히 살펴보자.

구문 기반 복제(statement-based replication)

리더는 모든 쓰기 요청에 대해 구문(statement) 를 기록하고 쓰기를 실행한다. 그 후, 구문을 팔로워에게 전송한다. RDBMS 는 INSERT, UPDATE, DELETE 구문을 전달한다. 팔로워는 직접 요청을 받은 것처럼 SQL 구문을 파싱하고 처리한다.

구문 기반 복제는 다음의 경우 복제가 깨질 수 있다.

• NOW(), RAND() 와 같은 비결정적 함수를 호출하는 경우, 실행 시점마다 값이 다르다.
• 자동증가 컬럼을 사용하는 경우, 구문의 실행 순서가 모든 노드에서 동일해야한다.
• ? 부수 효과를 가진 구문(트리거, 스토어드 프로시저, 사용자 정의 함수)는 부수 효과가 완벽하게 결정적이지 않으면 각 복제 서버에서 다른 부수 효과가 발생할 수 있다.

이런 한계는 모두 극복 가능하지만, 일반적으로 다른 복제 방법이 선호된다.

쓰기 전 로그(WAL, Write Ahead Log) 전달

모든 쓰기에 대해 WAL 를 작성한다면, WAL 를 복제 로그로 사용할 수 있다.

복제 로그로 WAL 를 이용할 때, WAL 로그의 단점은 저장소 엔진 내부와 결합도가 매우 높은, 물리적 데이터 표현이라는 점이다. 가령, 어떤 디스크 블로에서 어떤 바이트를 변경했는지와 같은 상세 정보를 포함한다. 이는 리더와 팔로워의 데이터베이스 소프트웨어 버전이 다른 경우 복구를 실행할 수 없게 한다.

논리적(로그 기반) 로그 복제

복제 로그를 저장소 엔진 내부와 분리하기 위한 방법 중 하나는 복제와 저장소 엔진을 위해 다른 로그 형식을 사용하는 것이다. 이런 종류의 복제 로그를 저장소 엔진의 물리적 데이터 표현과 구별하기 위해 논리적(Logical log) 라고 부른다.

RDBMS 의 논리적 로그는 대개 로우 단위로 DB 테이블 쓰기를 기술한 레코드열이다. 다음의 특성을 지닌다.

• 삽입된 로우의 로그는 모든 컬럼의 새로운 값을 포함한다.
• 삭제된 로우의 로그는 로우를 식별할 수 있는 정보를 포함한다. 보통 기본키다.
• 갱신된 로우의 로그는 로우를 식별할 수 있는 정보와 변경된 모든 컬럼의 새로운 값을 포함한다.

논리적 로그의 장점

• 논리적 로그는 하위 호환성을 더 쉽게 유지할 수 있다.
• 외부 어플리케이션에서 파싱하기 쉽기 때문에, CDC 로 활용하기도 좋다.

트리거 기반 복제

좀 더 유연한 복제를 제공하는 방식이다.
예를 들어, 다음의 유즈케이스가 있을 수 있다.

• 데이터의 특정 서브셋만 복제
• 데이터베이스를 다른 종류의 데이터베이스로 복제
• 충돌 해소 로직이 필요한 경우

많은 RDBMS 에서 트리거 나 스토어드 프로시저 를 사용한다.
트리거는 데이터 변경에 사용자 정의 애플리케이션 코드를 실행하는 복제 방식이다. 외부 프로세스가 테이블의 데이터 변경을 포착하면 자동으로 사용자 정의 코드를 실행한다.

트리거 기반 복제의 단점

• 다른 복제 방식보다 오버헤드가 많고, 버그나 제항 사항이 더 많이 발생한다.

트리거 기반 복제의 장점

• 유연성

복제 지연 문제

---

리더에서 일어난 쓰기가 팔로워로 복제되기 까지 지연을 복제 지연(Replication Lag) 이라고 한다.

비동기식 복제로 인해, 동일한 읽기 쿼리도 복제 지연에 따라 다른 결과를 반환할 수 있다. 하지만 시간이 흐르면 결국 모든 팔로워는 모든 리더의 모든 쓰기를 복제하게 되어 일관성을 회복하게 되는데, 이를 최종적 일관성 이라고 한다.

이번 절에서는 복제 지연이 발생할 수 있는 세 가지 사례를 제시하고 해결 방법을 간략히 설명한다.

쓰기 후 읽기

리더에게 쓰기 요청을 했으나, 복제 지연으로 인해 읽기 요청은 실패하거나 지난 값을 읽을 수 있다.

이런 상황에서는 쓰기 후 읽기 (read-after-write) 일관성이 필요하다. 이 일관성에서는 자신의 읽기는 자신의 모든 쓰기가 반영돼있음을 보장한다. 단, 다른 이의 쓰기에 대해서는 보장하지 않는다.

쓰기 후 읽기 일관성을 구현하는 방법

• 사용자가 수정한 내용을 읽을 때는 리더에서 읽는다. 그 밖에서는 팔로워에서 읽는다. 프로필 읽기를 예시로 들자면, 프로필 정보에 대해 자신의 프로필 읽기는 리더에서, 다른 사람에 대한 프로필 정보는 팔로워에서 읽을 수 있겠다.
• 자신의 마지막 쓰기 이후, 1분간 리더에서만 읽고 그 이후엔 확장성의 이점을 누리기 위해 팔로워로부터 읽기를 허용한다. 복제 지연을 모니터링 하여 1분 이후에도 지연된 팔로워에 대한 읽기를 제한할 수 있다.
• 클라이언트 사이드에서 가장 최신의 쓰기 타임스탬프를 기억하고, 읽기 쿼리에 해당 타임스탬프를 요청 바디에 포함시킨다. 팔로워가 해당 타임스탬프까지 반영이 된 상태라면 응답을 하고, 아니라면 대기하거나 다른 팔로워로 요청을 핸드오프 한다.

동일한 사용자가 여러 디바이스(데스크톱, 모바일)로 서비스를 접근하는 경우, 디바이스 간 쓰기 후 읽기 일관성(cross-device read-after-wrtie consitency) 가 필요하다.

이 경우, 추가적으로 다음의 상황들을 고려해야 한다.

• 사용자의 마지막 갱신 타임스탬프를 중앙집중식으로 관리해서 다른 디바이스에서 해당 메타를 알 수 있어야 한다.
• 디바이스 간 라우팅이 다를 수 있다. 리더에서만 읽어야 한다면, 다른 디바이스의 요청이 같은 리더로 라우팅될 수 있어야 한다.

단조 읽기

같은 사용자의 동일한 읽기 요청이 각기 다른 팔로워에게 라우팅 되었을 때, 시간이 거꾸로 흐르는 현상을 목격할 수 있다.

즉, 앞선 읽기에선 보였던 값이, 뒤이은 읽기에선 보이지 않을 수 있는 것이다.

단조 읽기(monotonic read) 란, 이렇게 시간이 거꾸로 흐르는 이상 현상이 발생하지 않는 것을 보장하는 일관성을 의미한다.

단조 읽기는 강한 일관성 보다는 덜하지만 최종적 일관성보다는 더 강한 일관성 보장이다.

단조 읽기를 달성하는 방법

• 각 사용자의 읽기가 항상 동일한 팔로워에서 수행되게끔 한다. 예를 들어, 라운드 로빈 라우팅이 아닌 ID 해싱 기반 라우팅을 사용해볼 수 있다. 하지만 복제 서버가 고장난 경우, 다른 복제 서버로 라우팅 할 수 있어야 한다.

일관된 순서로 읽기

일관된 순서로 읽기(consistent prefix read) 는 일련의 쓰기의 순서가 모든 사용자의 읽기에서 동일함을 보장한다.

주로 파티셔닝된 DB 에서 일관된 순서로 읽기가 깨지는 문제가 발생하고 한다. 많은 분산 DB 에서 파티션은 각각 독립적으로 동작하므로 전역적인 쓰기 순서가 보장되지 않기 때문이다.

일관된 순서로 읽기를 달성하는 방법

• 서로 인관성이 있는 쓰기가 동일한 파티션에 기록되게끔 하는 방법. 인과성을 명시적으로 유지하기 위한 알고리즘 또한 있다.

다중 리더 복제

---

지금 까지는 단일 리더를 사용한 복제 아키텍처만을 고려했음.

단일 리더 기반 복제의 주요한 단점

• 리더에 연결할 수 없다면 DB 에 쓰기를 할 수 없다!

쓰기 처리를 여러 노드로 확장하는 것을 다중 리더(Multi-Leader) 방식이라고 부른다. 이 방식에서 리더는 리더인 동시의 팔로워이다.

다중 리더 복제의 유즈 케이스

다중 데이터센터 운영

다중 데이터센터 운영시, 아래와 같이 데이터센터마다 리더가 있는 아키텍처를 고려해볼 수 있다.

다중 데이터센터 운영시 단일 리더 대비 다중 리더의 장점

항목	단일 리더	다중 리더
성능	리더가 존재하는 데이터 센터로 쓰기 요청이 전달되어야 하기 때문에, 쓰기 지연 발생	가까운 데이터 센터에서 쓰기 요청이 처리되기 때문에 성능이 더 좋음
데이터센터 중단 내성	리더가 있는 데이터센터가 고장 나면, 장애 복구를 위해 다른 데이터 센터의 팔로워를 리더로 승진시켜야 한다.	각 데이터 센터는 독립적으로 동작하기에, 고장난 데이터 센터가 온라인으로 돌아왔을 때, 복제를 따라잡는다.
네트워크 문제 내성 ?	데이터센터 내에서의 쓰기는 동기식이기 때문에, 데이터 센터 내 연결 문제에 매우 민감하다.	데이터 센터 내에서도 비동기식이기 때문에 네트워크 중단에도 쓰기 처리는 진행되어 네트워크 문제에 보다 잘 견디다.

다중 리더 단점

• 동일한 데이터에 대한 다른 데이터센터에서의 동시 쓰기는 충돌이 발생할 수 있다. 충돌 해소 처리가 반드시 필요하다.
• 자동 증가 키, 트리거, 무결성 제약 등 문제가 될 소지가 많다. 이런 이유로 되도록이면 다중 리더 복제는 피해야할 위험한 영역으로 간주되곤 한다.

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

인터넷 연결이 끊어진 동안 어플리케이션이 계속 동작해야 하는 경우

가령, 다양한 디바이스에서 접근 가능한 캘린더 앱의 오프라인에서도 읽기/ 쓰기 요청이 가능해야 한다.
오프라인 상태에서의 작업이 온라인 상태가 됐을 대 다른 디바이스와 동기화돼야 한다.

모든 디바이스 로컬에서 리더처럼 동작하는 로컬 DB 가 있다.
또한 다른 디바이스의 리더와 복제를 비동기 방식으로 수행하는 프로세스(동기화)가 있다. 복제 지연은 온라인 상태로부터 몇 시간에서 며칠 이상이 소요될 수도 있다.

이 유즈 케이스는 근본적으로 데이터센터 간 다중 리더 복제와 동일하다.

CouchDB 는 이런 종류의 동작 모드를 위해 설계되었다.

협업 편집

구글 독스와 같은 실시간 협업 편집 애플리케이션의 경우

한 사용자가 문서를 편집할 때 변경 내용이 즉시 로컬 복제 서버에 적용하고 나서, 동일한 문서를 편집하는 다른 사용자와 서버에 비동기 방식으로 복제한다.

충돌 문제가 발생할 수 있으며 이를 해결할 수 있어야 한다.

쓰기 충돌 처리하기

다중 리더 복제에서 비동기식 복제를 사용하는 경우 충돌이 발생할 수 있다.

충돌을 처리하는 방법을 살펴본다.

충돌 회피

제일 간단한 전략.

특정 레코드에 대한 모든 쓰기가 동일한 리더를 거치도록 보장하면 된다. 충돌 처리는 어려운 것이기 때문에, 충돌 회피는 자주 권장되는 방법이다.

예를 들어, 특정 사용자의 데이터(가령, 특정 사용자의 구글 닥스 문서)를 편집할 수 있는 애플리케이션에서 다른 사용자의 쓰기 요청이 동일한 데이터센터 내의 동일한 리더로 라우팅되도록 한다면 보장할 수 있다.

이러한 전략은 데이터 센터가 고장 나서 트래픽을 다른 데이터 센터로 다시 라우팅 해야하는 경우, 충돌 회피에 실패하게 된다. 이런 경우, 다른 리더에서 충돌을 해소할 수 있어야 한다.

일관된 상태 수렴

수렴(convergent) 방식으로 충돌을 해소하는 방법이다.
다른 리더에서 쓰기가 모두 성공했다고 할지라도, 최종적으로는 일관된 상태로 수렴해야 한다는 것이다.

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

• 각 쓰기 마다 comparable 한 ID 를 설정하고, 가장 높은 순위의 ID(winner)의 쓰기를 적용하고 나머진 버린다. 타임스탬프를 사용하는 경우를 LWW(last wirte wins) 이라고 한다. 대중적인 방법이지만, 데이터 유실의 위험이 있다.
• 각 리더에 우선 순위가 있는 고유한 ID 를 부여하고, 높은 순위의 ID 의 리더의 쓰기를 적용하고 나머진 버린다. 마찬가지로, 데이터 유실의 위험이 있다.
• 값을 버리지 않고 병합한다. 가령 쓰기1: "B", 가령 쓰기2: "C" 였다면, "B/C" 와 같은 형태로 병합하여 나타낸다.
• 명시적 데이터 구조에 충돌을 기록해 모든 정보를 보존하고, 나중에 충돌을 해소하는 애플리케이션 코드를 작성한다.

사용자 정의 충돌 해소 로직

애플리케이션마다 적합한 충돌 해소 로직을 개발자가 직접 작성하는 것이다.

충돌 해소 로직이 적용되는 시점은 크게 두 가지가 있다.

• 쓰기 수행 중: 다른 리더의 복제 로그에서 충돌을 감지하자마자 충돌 해소 로직을 호출한다.
• 읽기 수행 중: 충돌을 감지하면 모든 충돌 쓰기를 저장한다. 다음 읽기에서 여러 버전의 데이터가 애플리케이션에 반환되고, 이 때, 읽기 요청자에게 충돌된 데이터를 보여주거나, 자동으로 충돌을 해소하여 보여줄 수 있다.

자동 충돌에 관한 연구

• 충돌 없는 복제 데이터 타입(CRDT, Conflict-free Replicated Data Type): Riak 2.0, FastDB 에서 구현됐다.
• 병합 가능한 영속 데이터 구조(mergeable persistent data structure): git 과 유사하게 명시적으로 히스토리를 추적하고 삼중 병합 함수(three-way merge function)를 사용한다. CRDT 는 이중 병합 함수를 사용한다.
• 운영 변환(operation transformation)은 구글 독스와 같은 협업 편집 애플리케이션의 충돌 해소 알고리즘이다.

다중 리더 복제 토폴로지

복제 토폴로지는 노드 간 쓰기 통신 경로를 설명한다.

전체 연결(all-to-all)

• 가장 일반적인 토폴로지
• 모든 리더가 다른 모든 리더에게 쓰기를 전달

원형 토폴로지(circular topology)

• MySQL 이 쓰는 방식
• 각 노드는 하나의 노드로부터 쓰기 전달을 받고, 이 쓰기를 자신이 전달할 하나의 노드에게 전달한다.

별 모양 토폴로지

• 지정된 루트 노드 하나가 다른 모든 노드에 쓰기를 전달한다.
• 별 모양 토폴로지는 트리 형태로 일반화할 수도 있다.

원형과 별모양은 하나의 쓰기가 여러 노드를 거쳐야 전체 서버에 전파된다. 무한 복제 루프를 방지하기 위해, 복제 로그에 쓰기를 거친 노드의 식별자가 저장된다.

원형과 별모양의 문제점은 하나의 노드에서 장애가 발생하면 전체 서버에 복제가 중단(single point of failure)될 수 있다. 장애 노드 발생시 해당 노드를 회피하도록 재설정이 필요하다. 이는 주로 수동 재설정으로 이루어진다. 연결이 더 빽빽할 수록, 토폴로지의 내결함성이 좋아진다.

전체 연결 토폴로지의 문제점은 일관된 순서로 읽기가 깨질 수 있다는 것이다. 즉, 리더 노드마다 네트워크 속도의 차이로 인해, 쓰기의 순서가 보장되지 않을 수 있다.

이를 해결하기 위해, 버전 벡터(version vector) 라는 기법을 사용하곤 한다. 그러나, PostgresSQL, MySQL 등 많은 다중 리더 복제 시스템에선 이런 충돌 감지 기법이 제대로 구현되어 있지 않다.

다중 리더 복제를 사용하는 경우, 스택 후보가 충돌 감지에 대한 믿을 만한 보장을 제공하는지 확인하는 것이 권장된다.

리더 없는 복제

---

리더 없는 복제(leaderless Replication) 이란 일부 DB 시스템은 리더 없이 모든 복제 서버에 쓰기가 가능한 것을 말한다.
Dynamo 에서 사용하여 Dynamo 스타일이라고도 불린다. Riak, Cassandra 등에서 사용된다.

leaderless 복제 일부 구현에서는 클라이언트가 복제 서버로 직접 쓰기 호출을 하지 않고, 코디네이터 노드를 통해서 전달한다. 코디네이터 노드는 특정 순서로 쓰기를 수행하지 않는다. 이런 차이는 DB 사용 방식에 중대한 영향을 미친다.

노드가 다운됐을 때 DB 에 쓰기

리더가 있을 때, 리더가 다운된 경우 리더에 대한 장애 복구가 필요하다.
리더가 없는 경우가 장애 복구가 필요하지 않다.

클라이언트는 모든 복제 서버로 쓰기 요청을 보내고, 하나의 노드에서 실패하고 두 개의 노드에서 성공했다면, 쓰기가 성공한 것으로 판단한다. 성공했다고 판단하면 특정 노드에서 실패한 쓰기에 대해선 단순히 무시한다.

쓰기가 실패한 노드에선 오래된(outdated) 데이터가 읽어질 수 있다. 2개의 노드에 대해 읽기 요청을 보내고, 버전을 비교하여 최신값을 선택한다.

읽기 복구와 안티 엔트로피

리더 없는 복제에서도 최종적 일관성이 달성되려면, 노드가 복구됐을 때 최신 데이터에 대한 복제가 이루어져야한다.(catch-up)

리더 없는 복제의 catch-up엔, 주로 두 가지 메커니즘이 사용된다.

• 읽기 복구: 클라이언트가 out-dated 된 값을 읽었을 때, 해당 노드가 out-dated 된 것을 감지할 수 있다. 클라이언트 사이드에서 뒤쳐진 노드에게 최신 버전의 값 업데이트 요청을 보낸다. 읽기가 자주 일어나는 상황에서 적합하다.
• 안티 엔트로피 처리: 지속적으로 노드를 최신화시키는 백그라운드 프로세스를 띄운다.

위 두 개의 방법 중 읽기 복구만 이용하면, 읽기 복구를 실행하는 어플리케이션이 읽지 않는 데이터에 대해선 최신화를 보장할 순 없다.

읽기와 쓰기를 위한 정족수

n개의 노드가 있고, 모든 쓰기는 w개의 노드에서 성공해야 확정되고, 모든 읽기는 최소한 r개의 노드에 질의를 한다고 하자.
이 때, w + r > n 이면 읽기는 반드시 최신값을 얻을 것으로 기대한다. w + r > n 을 만족하면, n 개의 노드 중 적어도 한 개의 노드에 대해선 최신값 쓰기와 읽기가 모두 성공하기 때문이다. w + r > n 을 정족수 조건 이라고 부르겠다.

보통 n을 홀수로 하고, w = r = (n + 1)/2 로 설정한다.
읽기가 많고 쓰기가 적은 유즈 케이스에선, w = n, r = 1 로 설정할 수 있다. 하지만, 이 경우 한 개의 노드라도 고장나면 쓰기에 실패한다.

정족수 일관성의 한계

정족수 조건을 만족해도 오래된 값을 반환하는 에지 케이스가 있다.

• 느슨한 정족수를 사용한다면 쓰기 노드와 읽기 노드가 겹치는 것을 보장하지 않는다.
• 쓰기 충돌을 해결하기 위해 LWW 방식을 사용하는 경우, clock skew 로 인해 쓰기가 유실될 수 있다.
• 쓰기와 읽기가 동시에 발생했을 때, 쓰기는 일부 복제 서버에만 반영된 상태일 수 있다.
• 쓰기가 w 보다 적은 노드에서만 이루어져서 쓰기가 실패했지만, 쓰기가 이루어진 노드가 롤백하지 않은 경우.
• 시점 문제로 에지 케이스가 있을 수 있다. 이는 331p "선형성과 정족수" 에서 살펴본다.

결국, 최종적 일관성이 달성된 상태에선 정족수 조건이 항상 최신값을 읽는 것을 보장하지만, 최종적 일관성이 달성되지 않거나 위와 같은 에지 케이스에선 정족수 조건이 절대적으로 최신값 읽기를 보장하진 못한다.

특히, 비동기식 복제를 사용하는 경우 [복제 지연 문제](# 복제 지연 문제)로 인해 최신값이 읽히지 않는 이상 현상이 발생할 수 있다. 견고한 보장은 일반적으로 트랜잭션이나 합의가 필요하다. 이는 7장, 9장에서 살펴본다.

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

Sloppy Quorums and Hinted Handoff
n 을 초과하는 노드로 구성된 클러스터에서, 특정 키 처리를 담당하는 정족수 n 개의 노드가 있다고 하자. 이 n 개 중 일부 노드들이 다운되거나 네트워크 연결이 소실된 상황에선 정족수를 구성하는 노드들에 데이터를 쓸 수가 없다.

정족수를 구성하는 노드 중 일부가 장애 상황일 때, 정족수 구성 외의 노드에 쓰기 처리를 위임하는 것을 느슨한 정족수 라고 한다.

장애 상황의 노드들이 복구가 되었을 때, 쓰기를 이 노드들에 다시 복제하는데 이를 암시된 핸드오프(hinted handoff) 라고 한다.

느슨한 정족수는 쓰기 가용성을 높이는데 효과적이다.

하지만, 정족수 조건이 만족된다고 해도, 일시적으로 최신값이 n 이외의 노드에 기록될 수 있기 때문에 r 노드가 최신값을 읽는 것을 보장하지 않는다.

동시 쓰기 감지

리더 없는 복제에선, 여러 클라이언트가 동일 키에 대해 동시에 쓰는 것을 허용하기 때문에 엄격한 정족수를 사용하더라도 충돌이 발생한다. 읽기 복구나 암시된 핸드오프 상황에서도 충돌이 발생할 수 있다.

충돌이 발생한 경우, 실제로 어떤 값이 최신값인지 판단하기 어렵다. 아래 그림에서 Client A, B 가 동시에 쓰기를 했으나, 각 노드까지 반영되는 것이 모두 다르기 때문에, A가 최신값이 되는 경우도 있고 그 반대의 경우도 존재할 수 있다.(양자 역학?)

리더 없는 복제에서 쓰기 충돌을 해소하는 방법에 대해 알아본다.

LWW

타임스탬프가 우세한 경우의 쓰기를 취한다. 단, loser 의 쓰기는 유실될 수 있다.
타임스탬프가 동일한 경우는 로직을 작성하기에 따라 동작을 결정할 수 있다. 가령, 노드ID 에 우선 순위를 주거나, 도착한 순서로 우선 순위를 추가할 수 있다.

이전 발생 관계와 동시성

두 작업이 동시에 수행됐다를 어떻게 판별하는가?
작업 B가 다른 작업 A를 알고 있고 기반으로 한다면, 작업 B는 작업 A 보다 이전에 발생(happens-before)했다고 한다. B는 A에 인과성이 있다(causally dependent)고 한다.
두 작업이 서로 인과성이 없는 경우, 동시에 발생했다고 한다.

아래 그림은 동시에 발생하지 않은 경우

아래 그림은 동시에 발생한 경우

쓰기를 요청한 시각이 동시성을 결정하진 않는다. 요청의 시각이 다르더라도 서로 인과관계만 없다면 동시에 쓴 것으로 본다.

이전 발생 관계 결정 알고리즘

capturing the happens-beofre relationship

클라이언트가 자신이 알고 있는 버전을 쓰기 요청과 함께 보낸다.
알고있는 버전까지는 인과관계가 존재하는 것이며, 그 이후의 최신 버전과는 동시 쓰기가 아닌 것이다.

서버 데이터와 클라라이언트가 가지고 있는 데이터가 서로 다를 수 있으나, 손실된 쓰기는 없다.

구체적으로 다음과 같이 알고리즘이 동작한다.

• 서버는 모든 키에 대하 각각 버전을 유지하고, 키가 업데이트 될 때마다, 버전을 증가시킨다.
• 클라이언트가 키를 읽을 때, 서버는 최신 버전 뿐만 아니라 덮어쓰지 않은 모든 값을 반환한다.
• 클라이언트의 쓰기는 이전 읽기의 버전을 포함해야 한다. 이전 읽기에서 받은 모든 값을 함께 합쳐야(merge) 한다.
• 서버가 특정 버전을 쓰기를 받을 때, 해당 버전 이하 모든 값을 덮어쓰되(merge 쓰기가 보장되어야 함), 이보다 높은 버전의 모든 값은 동시 쓰기이므로 유지 한다. 위 그림에서 값마다 버전이 따로 존재한다.
• 버전을 포함하지 않은 쓰기는 동시에 쓰여지지 않은 것이므로 아무것도 덮어쓰지 않는다.

동시에 쓴 값 병합

이 알고리즘은 클라이언트단에서 동시값(형제(sibling)값)을 병합해야하는 추가적인 작업이 필요하다.
형제값을 병합하는 것은 버전을 기반으로 한 LWW 방식이므로 데이터 유실이 발생할 수 있다는 단점이 있다.

클라이언트가 형제값을 병합하는 합리적인 방법은 합집합을 구하는 것이다.
하지만, 값을 삭제하는 경우, 형제값에선 여전히 해당값이 존재할 수 있다.
이를 방지하기 위해선 단순히 병합한 집합에서 해당 값을 삭제하여 set 하는 것이 아니라, 해당 값을 삭제하겠다는 표시를 남겨야한다. 이를 툼스톤 이라고 한다.

복잡하고 오류가 발생 쉽다. Riak 에선 형제 병합을 지원하는 CRDT 라는 데이터 타입을 지원한다.

버전 벡터

아래 그림에선, 단일 복제본을 사용했다.

리더가 없는 다중 노드 아키텍처에서의 알고리즘은 키당 버전뿐만 아니라 노드당 버전 번호도 사용해야 한다.

모든 노드의 버전 모음을 버전 벡터(version vector) 라고 한다.

클라이언트가 값을 읽을 때, 서버는 버전 벡터를 함께 보낸다.
클라이언트는 받은 버전 벡터를 이후 쓰기에 함께 보낸다.(인과 관계)