Chapter 5. Replication(복제)

소개

본 글은 데이터 중심 어플리케이션(마틴 클레프만)으로 스터디하며 해당 책의 내용을 요약 정리한 내용입니다.

https://github.com/ddia-study/ddia-study

GitHub - ddia-study/ddia-study: 데이터 중심 어플리케이션 설계

 

서론

키워드만 간단보기 : https://johngrib.github.io/wiki/d-i-a-05-replication/

우연히 찾은 저자의 유튜브 : https://www.youtube.com/watch?v=uNxl3BFcKSA (quorum 관련 이야기)

복제란 네트워크로 연결된 여러 장비에 동일한 데이터의 복사본을 유지한다는 의미다.

데이터 복제가 필요한 여러 이유

• 지리적으로 사용자와 가깝게 데이터를 유지해 지연 시간을 줄인다.
• 시스템의 일부에 장애가 발생해도 지속적으로 동작할 수 있게 해 가용성을 높인다.
• 읽기 질의를 제공하는 장비의 수를 확장해 읽기 처리량을 늘린다.

복제에서 모든 어려움은 복제된 데이터의 변경 처리에 있다.

 

leader-based replication

복제 서버 중 하나를 leader(master, primary)로 지정한다.

클라이언트가 DB에 쓰기를 할 때 클라이언트는 요청을 리더에게 보내야 한다.

다른 복제 서버는 follwer(read replica, slave, secondary, hot standby)라고 한다.

리더가 로컬 저장소에 새로운 데이터를 기록할 때마다 데이터 변경을 replication log나 change stream의 일부로 팔로워에게 전송한다.

각 팔로워가 리더로부터 로그를 받으면 리더가 처리한 것과 동일한 순서로 모든 쓰기를 적용해 갱신한다.

 

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

동기식 복제의 장점

• 팔로워가 리더와 일관성 있게 최신 데이터 복사본을 가지는 것을 보장
• 갑자기 리더가 작동하지 않아도 데이터는 팔로워에서 계속 사용할 수 있음을 확신

동기식 복제의 단점

• 팔로워가 죽거나 네트워크 문제나 다른 어떤 이유로 인해 동기 팔로워가 응답하지 않는다면 쓰기가 처리되지 않는다.

모든 팔로워가 동기식인 상황은 비현실적이다

현실적으로, DB에서 동기식 복제를 사용하려면 보통 팔로워 하나는 동기식으로 하고 그 밖에는 비동기식으로 하는 것을 의미한다.

 

semi-synchronous : 적어도 두 노드(리더 & 하나의 동기 팔로워)에 데이터의 최신 복사본이 있는 것을 보장한다.

보통 리더 기반 복제는 완전히 비동기식으로 구성한다.

이런 경우 리더가 잘못되고 복구할 수 없으면 팔로워에 아직 복제되지 않은 모든 쓰기는 유실된다.

하지만 완전 비동기식 설정은 모든 팔로워가 잘못되더라도 리더가 쓰기 처리를 계속할 수 있다는 장점이 있다.

 

New Follower

새로운 팔로워가 리더의 데이터 복제본을 정확히 가지고 있는지 어떻게 보장할까?

데이터베이스를 잠가서 디스크의 파일을 일관성 있게 만들 수 있지만 고가용성 목표에 부합하지 않는다.

1. 가능하다면 전체 데이터베이스를 잠그지 않고 리더의 데이터베이스 스냅숏을 일정 시점에 가져온다.
2. 스냅숏을 새로운 팔로워 노드에 복사한다.
3. 팔로워는 리더에 연결해 스냅숏 이후 발생한 모든 데이터 변경을 요청한다. 이것은 스냅숏의 리더의 복제 로그의 정확한 위치와 연관돼야 한다.
4. 팔로워가 스냅숏 이후 데이터 변경의 미처리분(backlog)을 모두 처리했을 때 따라잡았다고 말한다.

 

노드 중단 처리

리더 기반 복제에서 고가용성은 어떻게 달성할 수 있을까?

 

팔로워 장애 : 따라잡기 복구

로그를 이용해 발생한 데이터 변경을 통해 리더를 다 따라잡을 수 있다.

 

리더 장애 : 장애 복구

팔로워 중 하나를 새로운 리더로 승격해야 하고 클라이언트는 새로운 리더로 쓰기를 전송하기 위해 재설정이 필요하며 다른 팔로워는 새로운 리더로부터 데이터 변경을 소비하기 시작해야 한다.

이 과정을 failover라 한다.

 

자동 장애 복구 과정

1. 리더가 장애인지 판단한다.
2. 새로운 리더를 선택한다. (election)
3. 새로운 리더 사용을 위해 시스템을 설정한다.

 

장애 복구 과정에서 잘못될 수 있는 것들

• 비동기식 복제를 사용한다면 새로운 리더는 이전 리더가 실패하기 전에 이전 리더의 쓰기를 일부 수신하지 못할 수 있다.
• 쓰기를 폐기하는 방법은 DB 외부의 다른 저장소 시스템이 DB 내용에 맞춰 조정돼야 한다면 특히 위험하다. out-of-date 팔로워가 리더로 승격된 경우가 있었고, 잘못된 사용자에게 개인 데이터가 공개된 깃헙의 케이스가 있었다.
• 스플릿 브레인 : 두 노드가 모두 자신이 리더라고 믿을 수 있다.
• 불필요한 장애 복구 (정상인 시스템)

 

복제 로그 구현

구문 기반 복제

리더는 모든 쓰기 요청(statement)을 기록하고 쓰기를 실행한 다음 구문 로그를 팔로워에게 전송한다.

이 접근법은 합리적인 것 같지만 복제가 깨질 수 있다.

• NOW(), RAND() 같은 비결정적 함수를 호출하는 모든 구문은 각 복제 서버마다 다른 값을 생성할 가능성이 있다.
• 자동증가 칼럼을 사용하는 구문이나 데이터베이스에 있는 데이터에 의존하는 구문은 각 복제 서버에서 정확히 같은 순서로 실행돼야 한다.
• side effect를 가진 구문(trigger, SP)은 부수 효과가 완벽하게 결정적이지 않으면 각 복제 서버에서 다른 side effect가 발생할 수 있다.

 

쓰기 전 로그 배송

모든 쓰기는 로그에 기록한다.

완전히 동일한 로그를 사용해 다른 노드에서 복제 서버를 구축할 수 있다.

팔로워가 이 로그를 처리하면 리더에서 있는 것과 정확히 동일한 데이터 구조의 복제본이 만들어진다. (Postgresql, Oracle)

가장 큰 단점은 로그가 제일 저수준의 데이터를 기술한다는 점이다. 어떤 디스크 블록에서 어떤 바이트를 변경했는지와 같은 상세 정보를 포함하고 있기 때문에, 복제가 저장소 엔진과 밀접하게 엮인다.

 

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

복제 로그를 저장소 엔진 내부와 분리하기 위한 방안 중 하나는, 복제와 저장소 엔진을 위해 다른 로그 형식을 사용하는 것이다.

이런 종류의 복제 로그를 logical log라고 한다.

RDB용 논리적 로그는 대개 로우 단위로 데이터베이스 테이블에 쓰기를 기술한 레코드 열이다.

• 삽입된 로우의 로그는 모든 칼럼의 새로운 값을 포함한다.
• 삭제된 로우의 로그는 로우를 고유하게 식별하는 데 필요한 정보를 포함한다.
• 갱신된 로우의 로그는 로우를 고유하게 식별하는 데 필요한 정보와 모든 칼럼의 새로운 값을 포함한다.

 

장점

• 하위호환성 유지가 쉽다
• 다른 버전의 소프트웨어나 저장소 엔진에서 실행할 수 있다
• 외부 시스템에 데이터베이스의 내용을 전송하고자 할 때 유용하다. (change data capture)

 

트리거 기반 복제

트리거는 사용자 정의 애플리케이션 코드를 등록할 수 있게 한다.

이 애플리케이션 코드는 DBS에서 데이터가 변경되면 자동으로 실행된다.

트리거는 데이터 변경을 분리된 테이블에 로깅할 수 있는 기회를 가진다.

이 테이블로부터 데이터 변경을 외부 프로세스가 읽을 수 있다.

트리거 기반 복제에는 다른 복제 방식보다 많은 오버헤드가 있다.

 

복제 지연 문제

리더 기반 복제는 모든 쓰기가 단일 노드를 거쳐야 하지만 읽기 전용 질의는 어떤 복제 서버에서도 가능하다.

read-scaling 아키텍처에서는 간단히 팔로워를 더 추가함으로써 읽기 전용 요청을 처리하기 위한 용량을 늘릴 수 있다.

애플리케이션이 비동기 팔로워에서 데이터를 읽을 때 팔로워가 뒤쳐진다면 지난 정보를 볼 수도 있다. 하지만 이런 불일치는 일시적인 상태에 불과한다.

데이터베이스에 쓰기를 멈추고 잠시 동안 기다리면 팔로우는 따라잡게 된다. 이런 효과를 최종적 일관성이라 한다.

 

자신이 쓴 내용 읽기

새로운 데이터가 제출되면 리더에게 전송해야 하지만 사용자가 데이터를 볼 때는 팔로워에서 읽을 수 있다.

이것은 데이터를 자주 읽지만 가끔 쓰는 경우에 특히 적합하다.

쓰기 후 읽기 일관성(자신의 쓰기 읽기 일관성)이 필요하다.

리더 기반 복제 시스템에서 쓰기 후 읽기 일관성을 어떻게 구현할까?

• 사용자가 수정한 내용을 읽을 때는 leader에서 읽는다. 그밖에는 팔로워에서 읽는다.
• 애플리케이션 내 대부분의 내용을 사용자가 편집할 가능성이 있다면, 이 접근 방식은 대부분 leader에서 읽기 때문에 효율적이지 않다. leader에서 읽을지 말지를 결정하기 위해 다른 기준을 사용해야 한다.
• 클라이언트는 가장 최근 쓰기의 타임스탬프를 기억할 수 있다. 그러면 시스템은 사용자 읽기를 위한 복제 서버가 최소한 해당 타임스탬프까지 갱신을 반영하게 할 수 있다. 복제 서버가 아직 최신 내용이 아닌 경우에는 다른 복제 서버가 읽기를 처리하거나 복제 서버가 따라잡을 때까지 질의를 대기시킬 수 있다.
• 복제 서버가 여러 데이터센터에 분산됐다면 복잡도가 증가한다. 리더가 제공해야 하는 모든 요청은 리더가 포함된 데이터센터로 라우팅 돼야 한다.

 

단조 읽기

사용자가 시간이 거꾸로 흐르는 현상을 목격할 수 있다.

사용자가 각기 다른 복제 서버에서 여러 읽기를 수행할 때, 비동기적 쓰기 이슈로 인해 발생

monotonic read는 이런 종류의 이상 현상이 발생하지 않음을 보장한다.

강한 일관성보다는 덜한 보장이지만 최종적 일관성보다는 더 강한 보장이다.

즉, 이전에 새로운 데이터를 읽은 후에는 예전 데이터를 읽지 않는다.

각 사용자의 읽기가 항상 동일한 복제 서버에서 수행되게끔 하는 것이다.

 

일관된 순서로 읽기

인과성 위반이 일어나는 경우를 방지하기 위해 Consistent Prefix Read 같은 보장이 필요하다.

일관된 순서로 읽기는 일련의 쓰기가 특정 순서로 발생한다면 이 쓰기를 읽는 모든 사용자는 같은 순서로 쓰여진 내용을 보게 됨을 보장한다.

 

복제 지연을 위한 해결책

애플리케이션 개발자가 이런 미묘한 복제 문제를 걱정하지 않고 "올바른 작업 수행"을 위해 항상 데이터베이스를 신뢰할 수 있다면 훨씬 좋다. 이것이 트랜잭션이 있는 이유다.

 

다중 리더 복제

리더가 하나만 존재하고 모든 쓰기는 해당 리더를 거쳐야 한다.

어떤 이유로 리더에 연결할 수 없다면 쓰기를 할 수 없다.

따라서 쓰기를 허용하는 노드를 하나 이상 두는 것으로 자연스럽게 확장된다.

이를 다중 리더 설정이라고 한다.(master master, active/active)

 

예시

- 다중 데이터 센터

• 모든 쓰기는 로컬 데이터센터에서 처리한 다음 비동기 방식으로 다른 데이터 센터에 복제된다.
• 각 데이터센터는 다른 데이터센터와 독립적으로 동작한다.

Auto Increment Key, Trigger, 무결성 등 문제가 될 가능성이 높아서 다중 리더 복제는 가능하면 피해야 하는 영역으로 간주되기도 한다.

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

- 협업 편집

 

쓰기 충돌 다루기

동기 vs 비동기 충돌 감지

단일 리더 DB : 첫 번째 쓰기 완료까지 두 번째 쓰기 차단 or 두 번째 쓰기 중단 후 재시도

다중 리더에서는 동기식으로 하면 이점을 잃음

 

충돌 회피

특정 레코드의 모든 쓰기가 동일한 리더를 거치도록 애플리케이션이 보장한다면 충돌이 발생하지 않는다.

 

일관된 상태 수렴

다중 리더 설정에서는 쓰기 순서가 정해지지 않아 최종 값이 무엇인지 명확하지 않다.

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

따라서 DB는 수렴(convergent) 방식으로 충돌을 해소해야 한다.

이는 모든 변경이 복제돼 모든 복제 서버에 동일한 최종 값이 전달되게 해야 한다는 의미다.

• 각 쓰기에 고유 ID를 부여하고 가장 높은 ID를 가진 쓰기를 고른다. (Last write wins, LWW)
• 각 복제 서버에 고유 ID를 부여하고 높은 숫자의 복제 서버에서 생긴 쓰기가 낮은 숫자의 복제 서버에서 생긴 쓰기보다 항상 우선적으로 적용되게 한다.
• 어떻게든 값을 병합한다. (사전 순 정렬 후 연결)
• 명시적으로 데이터 구조에 충돌을 기록해 모든 정보를 보존한다. 나중에 애플리케이션에서 충돌을 해소한다.

 

사용자 정의 충돌 해소 로직

• 쓰기 수행 중 : 복제된 변경 사항 로그에서 DBS가 충돌을 감지하자마자 충돌 핸들러를 호출한다.
• 읽기 수행 중 : 충돌을 감지하면 모든 충돌 쓰기를 저장한다. 다음 번 데이터를 읽을 때 이런 여러 버전의 데이터가 애플리케이션에 반환된다.

자동 충돌 해소

• CRDT
• Mergeable persistent data structure
• operational transformation

Geek News : https://news.hada.io/topic?id=2962
채널톡 : https://channel.io/ko/blog/crdt_vs_ot

제가 틀렸었어요. CRDT가 미래입니다. | GeekNews

CRDT vs OT - 채널톡

 

다중 리더 복제 토폴로지

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

• 원형 토폴로지
• 별 모양 토폴로지
• 전체 연결 토폴로지

 

리더 없는 복제

• 리더의 개념을 버리고 모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있게 허용하는 접근 방식
• 코디네이터 노드(coordinator node)가 클라이언트를 대신해 여러 복제 서버에 쓰기

리더 없는 복제는 아마존이 내부 Dynamo 시스템에서 사용한 후 다시 데이터베이스용 아키텍처로 유행했다. (Dynamo Style)

Dynamo Style : https://en.wikipedia.org/wiki/Dynamo_(storage_system)

Dynamo (storage system) - Wikipedia

 

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

리더 없는 설정에서는 장애 복구가 필요하지 않다.

다운된 노드가 온라인 상태가 되면 클라이언트가 해당 노드에서 데이터를 읽을 때 응답으로 outdated 값을 얻을 수 있다.

이 문제를 해결하기 위해 클라이언트가 DB에서 읽을 때 하나의 복제 서버로 요청을 보내지 않고 읽기 요청을 병렬로 여러 노드에 전송한다.

이렇게 전송 받은 데이터 중 버전 숫자를 사용해 어떤 값이 최신 내용인지 결정한다.

 

읽기 복구와 안티 엔트로피

사용 불가능한 노드가 온라인 상태가 된 후 누락된 쓰기를 어떻게 따라잡아야 할까?

• 읽기 복구 : 클라이언트가 여러 노드에서 병렬로 읽기를 수행하면 오래된 응답을 감지할 수 있다.
• 안티 엔트로피 처리 : 백그라운드 프로세스를 두고 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 하나의 복제 서버에서 다른 서버로 복사한다. 특정 순서로 쓰기를 복사하기 때문에 상당한 지연이 있을 수 있다.

 

읽기와 쓰기를 위한 정족수

n개의 복제 서버가 있을 때 모든 쓰기는 w개의 노드에서 성공해야 쓰기가 확정되고 모든 읽기는 최소한 r개의 노드에 질의해야 한다.

w + r > n이면 읽을 때 최신 값을 얻을 것으로 기대한다.

최소한 r개의 노드 중 하나에서 최신 값을 읽을 수 있기 때문이다.

이런 r과 w를 따르는 읽기와 쓰기를 정족수 읽기와 쓰기라고 부르며, 유효한 읽기와 쓰기를 위해 필요한 최소 투표수를 r과 w로 생각할 수 있다.

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

n은 홀수, w = r = (n + 1) / 2 (반올림)

w + r > n이면 다음과 같이 사용 불가능한 노드를 용인한다.

• w < n이면 노드 하나를 사용할 수 없어도 여전히 쓰기를 처리할 수 있다.
• r < n이면 노드 하나를 사용할 수 없어도 여전히 읽기를 처리할 수 있다.
• n = 3, w = 2, r = 2이면 사용 불가능한 노드 하나를 용인한다.
• n = 5, w = 3, r = 3이면 사용 불가능한 노드 둘을 용인한다.
• 일반적으로 읽기와 쓰기는 항상 모든 n개의 복제 서버에 병렬로 전송한다.

 

정족수 일관성의 한계

정족수가 읽기 시 최근에 쓴 값을 반환하게끔 보장하지만 실제로는 그렇게 간단하지 않다.

매개변수 w와 r로 오래된 값을 읽는 확률을 조정할 수 있지만 이를 절대적으로 보장할 수는 없다.

 

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

적절히 설정된 정족수가 있는 데이터베이스는 장애 복구 없이 개별 노드 장애를 용인한다.

하지만 지금까지 설명한 대로 정족수는 내결함성이 없다. 네트워크 중단으로 다수의 데이터베이스 노드와 클라이언트는 쉽게 연결이 끊어질 수 있다.

노드가 n개 이상인 대규모 클러스터에서 클라이언트는 네트워크 장애 상황에서 일부 데이터베이스 노드(특정 값을 위한 정족수 구성에 들어가지 않는 노드)에 연결될 가능성이 있다.

• w나 r 노드 정족수를 만족하지 않는 모든 요청에 오류를 반환하는 편이 좋을까?
• 아니면 일단 쓰기를 받아들이고 값이 보통 저장되는 n개 노드에 속하지는 않지만 연결할 수 있는 노드에 기록할까? (느슨한 정족수)

쓰기와 읽기는 여전히 w와 r의 성공 응답이 필요하지만 값을 위해 지정된 n개의 "홈" 노드에 없는 노드가 포함될 수 있다.

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

느슨한 정족수는 쓰기 가용성을 높이는 데 특히 유용하다

 

다중 데이터 센터 운영

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

 

동시 쓰기 감지

여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용하기 때문에 충돌이 발생한다.

최종적 일관성을 달성하기 위해 복제본들은 동일한 값이 돼야 한다.

 

최종 쓰기 승리(LWW)

각 복제본이 가진 "예전" 값을 버리고 가장 "최신" 값으로 덮어쓰는 방법이 있다.

쓰기에 타임스탬프를 붙여 가장 "최신"이라는 의미로 제일 큰 타임스탬프를 선택하고 예전 타임스탬프를 가진 쓰기는 무시한다. (LWW)

손실 데이터를 허용하지 않는다면 LWW가 충돌 해소에 적합하지 않다.

 

"이전 발생" 관계와 동시성

작업 B가 작업 A에 대해서 알거나 A에 의존적이거나 어떤 방식으로든 A를 기반으로 한다면 작업 A는 작업 B의 happens-before이다.

작업이 다른 작업보다 먼저 발생하지 않으면 동시 작업이라고 말한다.

작업이 동시에 발생한 것을 어떻게 알 수 있을까?

 

happens-before 파악하기

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

쓰기가 이전 읽기의 버전 번호를 포함하면 쓰기가 수행되지 이전 상태를 알 수 있다.
버전 번호를 포함하지 않은 쓰기는 다른 쓰기와 동시에 수행된 것이므로 아무것도 덮어쓰지 않는다.

 

동시 값 병합

여러 작업이 동시에 발생하면 클라이언트는 동시에 쓴 값을 합쳐 정리해야 한다.

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

형제를 병합할 때 삭제한 아이템이 합집합에서 재등장할 수 있기 때문에, 해당 버전 번호에 표시를 남겨둔다. (툼스톤)

애플리케이션 코드에서 형제 병합은 복잡하고 오류가 발생하기 쉽다.

자동 병합을 수행할 수 있게 데이터 구조를 설계하려는 노력이 있다. (CRDT)

 

버전 벡터

다중 복제본의 동시 쓰기를 받아들이기 위해 복제본당 버전 번호도 사용한다.

모든 복제본의 버전 번호 모음을 version vector라고 부른다.

버전 벡터는 값을 읽을 때 데이터베이스 복제본에서 클라이언트로 보내고, 값이 기록될 때 데이터베이스로 다시 전송한다.

이 버전 벡터를 통해 데이터베이스는 덮어쓰기와 동시 쓰기를 구분할 수 있다.

리악에서 사용하는 dotted version vector : https://github.com/ricardobcl/Dotted-Version-Vectors

GitHub - ricardobcl/Dotted-Version-Vectors: Logical Clocks for Eventually Consistent Systems