[DDIA] 05장. 복제

 

들어가기 전에

복제란 네트워크로 연결된 여러 장비에 동일한 데이터의 복사본을 유지한다는 의미다. 복제에서 모든 어려움은 복제된 데이터의 변경 처리에 있으며 이것이 이번 장의 내용이다. 데이터 복제가 필요한 여러 이유가 있다.

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

 

[개념 사전]

단어	의미
최종적 일관성	분산 시스템에서 즉각적인 일관성을 보장하지 않지만, 일정 시간이 지나면 결국 일관된 상태에 도달하는 특성
복제 서버(replica)	데이터베이스의 복사본을 저장하는 각 노드
리더 기반 복제(leader-based replication)(=능동(active)/수동(passive), 마스터(master) 슬레이브(slave) 복제)	리더가 로컬 저장소에 새로운 데이터를 기록할 때마다 데이터 변경을 로그나 스트림으로 팔로워에게 전송하면, 팔로워가 로컬 복사본을 갱신하는 방법
구문 기반 복제(statement-based replication)	리더가 모든 쓰기 요청을 기록하고 쓰기를 실행한 다음 구문 로그를 팔로워에게 전송해 팔로워가 갱신하는 방법
논리적 로그(logical log)	대개 로우 단위로 데이터베이스 테이블에 쓰기를 기술한 레코드 열
변경 데이터 캡처(CDC, change data capture)	데이터베이스의 변경 사항을 감지하고 실시간으로 추출하여 다른 시스템으로 전달하는 기술
읽기 확장(read-scaling) 아키텍처	많은 팔로워를 만들어 팔로워 간 읽기 요청을 분산하여 리더의 부하를 없애고 근처 복제 서버에서 읽기 요청을 처리할 수 있게 구성하는 방법
최종 쓰기 승리(LWW, last write wins)	분산 시스템에서 동일한 데이터에 대한 충돌이 발생할 때, 가장 나중에 기록된 값을 최종적으로 유지하는 충돌 해결 전략
이중 병합 함수(two-way merge function)	연산 순서와 관계없이 동일한 결과를 보장하는 병합 함수
삼중 병합 함수(three-way merge function)	연산의 그룹화 방식이 달라도 결과가 동일한 병합 함수 (Git에서 브랜치 병합 시 공통 조상을 기준으로 병합 연산 수행)
버전 벡터(version vector)	이벤트를 올바르게 정렬하기 위해 복제본당 버전 번호를 부여하여 사용할 때 모든 복제본의 버전 번호 모음
형제 값(동시 값)	여러 작업이 동시에 발생할 때 클라이언트가 동시에 쓴 값을 합쳐 정리하는 값

 

 

새롭게 알게된 점(New)

리더 기반 복제

[1] 동기식 vs. 비동기식

반동기식(semi-synchronous)
현실적으로 데이터베이스에서 동기식 복제를 사용하려면 보통 팔로워 하나는 동기식으로 하고 그 밖에는 비동기식으로 하는 것을 의미한다. 적어도 두 노드에 데이터의 최신 복사본이 있는 것을 보장할 수 있다.

• 보통 리더 기반 복제는 완전히 비동기식으로 구성한다.
• 단점 : 리더가 잘못되고 복구할 수 없으면 팔로워에 아직 복제되지 않은 모든 쓰기는 유실된다.
• 장점 : 모든 팔로워가 잘못되더라도 리더가 쓰기 처리를 계속 할 수 있다.

 

[2] 새로운 팔로워 설정 프로세스

1. 리더의 데이터베이스 스냅샷을 일정 시점에 가져온다.
2. 스냅샷을 새로운 팔로워 노드에 복사한다.
3. 팔로워는 리더에 연결해 스냅샷 이후 발생한 모든 데이터 변경을 요청한다.
4. 팔로워가 스냅샷 이후 데이터 변경의 미처리분(backlog)을 모두 처리했을 때 따라잡았다고 말하며, 이제부터 리더에 발생하는 데이터 변화를 이어 처리할 수 있다.

 

[3] 고가용성 달성 방법

1️⃣ 팔로워에 장애가 일어났을 경우

• 리더로부터 수신한 데이터 변경 로그를 로컬 디스크에 보관한다.
• 보관된 로그에서 결함이 발생하기 전 마지막으로 처리한 트랜잭션 이후의 데이터 변경을 요청할 수 있다.

2️⃣ 리더에 장애가 일어났을 경우

장애 복구(failover) 과정
→ 팔로워 중 하나를 새로운 리더로 승격한다.
→ 클라이언트는 새로운 리더로 쓰기를 전송하기 위해 재설정한다.
→ 다른 팔로워는 새로운 리더로부터 데이터 변경 소비하기 시작한다.

• 새로운 리더는 이전 리더가 실패하기 전에 이전 리더의 쓰기를 일부 수신하지 못할 수 있다.
  • 일반적인 해결책 : 이전 리더의 복제되지 않은 쓰기를 단순히 폐기하자. (이 방법은 내구성에 대한 클라이언트의 기대를 저버리게 된다.)
• 쓰기를 폐기하는 방법은 데이터베이스 외부의 다른 저장소 시스템이 데이터베이스 내용에 맞춰 조정돼야 한다면 위험하다.
• 스플릿 브레인(split brain) : 두 노드가 모두 자신이 리더라고 믿는 현상 (데이터가 유실되거나 오염되게 됨)

 

[4] 복제 로그 구현

종류	WAL Shipping	논리적(로우 기반) 로그 복제	트리거 기반 복제
특징	1️⃣ 저장소 엔진과 밀접한 연관성 ⭕️ WAL는 어떤 디스크 블록에서 어떤 바이트를 변경 했는지와 같은 상세 정보를 포함하므로 복제가 저장소 엔진과 밀접하게 엮인다. 2️⃣ 중단 시간 필요  복제 프로토콜이 버전의 불일치를 허용하지 않으므로 업그레이드할 때 중단 시간이 필요하다.	1️⃣ 저장소 엔진과 밀접한 연관성 ❌ 하위 호환성을 더 쉽게 유지할 수 있으며, 리더와 팔로워에서 다른 버전의 데이터베이스 혹은 다른 저장소 엔진을 실행할 수 있다. 2️⃣ 외부 애플리케이션의 파싱 용이성 확보 오프라인 분석이나 사용자 정의 색인과 캐시 구축을 위해 데이터 웨어하우스 같은 외부 시스템에 데이터베이스의 내용을 전송하고자 할 때 유용하다.	1️⃣ 유연성 확보  데이터베이스 서브셋만 복제, 다른 종류의 데이터베이스로 복제, 충돌 해소 로직이 필요할 때 복제를 애플리케이션 층으로 옮겨 실행할 수 있다. 2️⃣ 많은 오버헤드, 버그 발생  다른 복제 방식보다 많은 오버헤드, 버그나 제한 사항이 더 많이 발생한다.

 

트리거 기반 복제에 사용되는 기술

• 오라클의 골든게이트(GoldenGate) : 데이터베이스 로그를 읽어 애플리케이션이 데이터를 변경할 수 있게 한다.
• 트리거 기반 : ORACLE 데이터버스(Databus), PostgreSQL 부카르도(Bucarde)

 

[5] 복제 지연이 있을 때 발생할 수 있는 세 가지 사례와 해결 방법

🧐 문제 1. 사용자가 쓰기를 수행한 직후 데이터를 본다면 새로운 데이터는 아직 복제 서버에 반영되지 않아 제출된 데이터가 유실된 것처럼 보인다.

• 해결 방법
  • 쓰기 후 읽기 일관성 : 사용자가 페이지를 재로딩 했을 때 항상 자신이 제출한 모든 갱신을 볼 수 있음을 보장하며 다른 사용자에 대해서는 보장하지 않는다.
• 프로세스
  • 사용자가 수정한 내용을 읽을 때는 리더에서 읽는다.
  • 마지막 갱신 후 1분 동안은 리더에서 모든 읽기를 수행한다.
  • 복제 서버가 아직 최신 내용이 아닌 경우 다른 복제 서버가 읽기를 처리하거나 복제 서버가 따라잡을 때까지 질의를 대기시킨다.

 

🔉 디바이스 간(cross-device) 쓰기 후 일관성
- 마지막 갱신 타임스탬프와 같은 메타데이터는 중앙집중식으로 관리한다.
- 사용자 디바이스의 요청을 동일한 데이터센터로 라우팅해야 한다. (데스크톱 컴퓨터는 홈 광대역 연결, 모바일 디바이스는 셀룰러 데이터 네트워크를 이용한다면 네트워크 라우팅이 완전히 다름)

 

 

 

🧐 문제 2. 사용자가 새로운 데이터를 조회했음에도 다음 질의에서는 이전 데이터를 조회한다.

• 해결 방법
  • 단조 읽기(monotonic read) : 이전에 새로운 데이터를 읽은 후에는 예전 데이터를 읽지 않는다.
• 프로세스
  • 각 사용자의 읽기가 항상 동일한 복제 서버에서 수행되게끔 하는 것이다.
  • 임의 선택보다는 사용자 ID의 해시를 기반으로 복제 서버를 선택한다.
  • 복제 서버가 고장 나면 사용자 질의를 다른 복제 서버로 재라우팅해야 한다.

 

🧐 문제 3. 사용자가 데이터베이스에서 읽을 때 예전 상태의 일부와 새로운 상태의 일부를 함께 볼 수 있다.

• 해결 방법
  • 일관된 순서로 읽기(Consistent Prefix Read) : 일련의 쓰기가 특정 순서로 발생한다면 이 쓰기를 읽는 모든 사용자는 같은 순서로 쓰여진 내용을 보게 됨을 보장한다. (서로 다른 파티션이 독립적으로 동작해 쓰기의 전역 순서가 없어 발생하는 것!)
• 프로세스
  • 서로 인과성이 있는 쓰기가 동일한 파티션에 기록되게끔 한다. (일부 애플리케이션에서 효율적이지 않음)

 

다중 리더 복제

리더가 하나만 존재하고 모든 쓰기는 해당 리더를 거쳐야 할 때, 모종의 이유로 리더에 연결할 수 없다면 문제가 발생한다. 이 문제를 해결하기 위해 쓰기를 허용하는 노드를 하나 이상 두고 각 노드는 데이터 변경을 다른 모든 노드에 전달한다.

• 동일한 데이터를 다른 두 개의 데이터센터에서 동시에 변경하려고 한다면 쓰기 충돌이 발생한다.
• 새로 추가된 기능이기 때문에 자동 증가 키, 트리거, 무결성 제약 등의 기능들이 불안정하다.

[1] 실시간 협업 편집 애플리케이션 (e.g. Google Docs)

• 변경 내용을 즉시 로컬 복제 서버에 적용하고 동일한 문서를 편집하는 다른 사용자와 서버에 비동기 방식으로 복제한다.
• 빠른 협업을 위해 변경 단위를 단일 키 입력과 같이 매우 작게 해서 잠금을 피할 수 있다.

[2] 쓰기 충돌

• 충돌 회피 : 특정 레코드의 모든 쓰기가 동일한 리더를 거치도록 보장한다.
• 일관된 상태 수렴 : 모든 변경이 복제돼 모든 복제 서버에 동일한 최종 값이 전달되게 한다.
• 충돌 해소 로직 작성 : 대부분의 다중 리더 복제 도구를 애플리케이션 코드를 사용해 충돌 해소 로직을 작성한다.
  • 충돌 해소는 보통 전체 트랜잭션이 아니라 개별 로우나 문서 수준에서 적용된다.

 

🔉 충돌을 자동으로 해소하는 흥미로운 연구 내용
- 충돌 없는 복제 데이터타입(CRDT, conflict-free replicated datatype) : Set, Map, 정렬 목록, 카운터 등을 위한 데이터 구조의 집합으로 동시에 여러 사용자가 편집할 수 있고 합리적인 방법으로 충돌을 자동 해소한다.
- 병합 가능한 영속 데이터 구조(mergeable persistent data structure) : Git 버전 제어 시스템과 유사하게 명시적으로 히스토리를 추적하고 삼중 병합 함수(three-way merge fuction)을 사용한다.
- 운영 변환(operational transformation) : 협업 편집 애플리케이션의 충돌 해소 알고리즘이다. 특히 텍스트 문서를 구성하는 문자 목록과 같은 정렬된 항목 목록의 동시 편집을 위해 설계됐다.

 

 

[3] 복제 토폴로지

 

종류	원형	별	전체 연결(all-to-all)
방법	각 노드가 하나의 노드로부터 쓰기를 받고, 이 쓰기를 다른 한 노드에 전달(MySQL의 기본 제공 토폴로지)	지정된 루트 노드 하나가 다른 모든 노드에 쓰기 전달	모든 리더가 각자의 쓰기를 다른 모든 리더에게 전송

 

1️⃣ 원형과 별 모양 토폴로지의 특징

• 무한 복제 루프를 방지하기 위해 각 쓰기에 쓰기가 완료된 노드의 고유 식별자가 태깅된다.
• 하나의 노드에 장애가 발생하면, 해당 노드가 복구될 때까지 다른 노드도 통신할 수 없다.

2️⃣ 전체 연결 토폴로지의 특징

• 내결함성 : 단일 장애점(single point of failure)을 피해 메시지가 여러 경로를 따라 이동할 수 있어 하나의 노드에 장애가 발생해도 통신이 가능하다.
• 네트워크 혼잡으로 일부 네트워크 연결이 다른 연결보다 빠르면 복제 메시지의 순서가 뒤바뀌어서 전달이 이루어질 수 있다.

 

🔉 다중 리더 복제 시스템에서의 충돌 감지 기법은 제대로 구현되지 않았다?
PostgreSQL의 BDR(Bi-Directional Replication, 양방향 복제를 지원하는 복제 솔루션)은 쓰기의 인과적 순서를 제공하지 않으며, MySQL의 텅스텐 리플리케이터(Tungsten Replication, 복제 솔루션)는 충돌을 감지하기 위한 시도조차 하지 않는다. 다중 리더 복제 시스템을 사용하려면 이런 문제를 인지하고 문서를 주의 깊게 읽은 다음 데이터베이스를 철저하게 테스트해 실제로 믿을 만한 보장을 제공하는지 확인하는 편이 좋다.

 

 

리더 없는 복제

일부 데이터 저장소 시스템은 리더의 개념을 버리고 모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있게 허용하는 접근 방식을 사용하기도 한다. 이런 종류의 데이터베이스를 다이나모 스타일이라 한다.

• 클라이언트가 여러 복제 서버에 쓰기를 직접 전송하거나 코디네이터 노드(coordinator node)가 클라이언트를 대신해 이를 수행하기도 한다.
• 코디네이터 노드는 특정 순서로 쓰기를 수행하지 않는다.

 

[1] 누락된 쓰기를 해결하는 두 가지 메커니즘

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

• 읽기 복구 : 클라이언트가 여러 노드에서 병렬로 읽기를 수행하여 오래된 응답을 감지하고 새로운 값을 다시 기록한다.
• 안티 엔트로피 처리 : 백그라운드 프로세스를 두고 복제 서버 간 데이터 차이를 지속적으로 찾아 누락된 데이터를 복사한다.

 

[2] 정족수

1️⃣ 정족수 읽기와 쓰기

n개의 복제 서버가 있을 때

• 모든 쓰기는 w개의 노드에서 성공해야 쓰기가 확정된다.
• 모든 읽기는 최소한 r개의 노드에 질의해야 한다.
• w + r > n이면 읽을 때 쓰기와 읽기 노드가 겹치므로 최신 값을 얻을 것으로 기대한다.

• r과 w를 따르는 읽기와 쓰기를 정족수 읽기와 쓰기라고 부른다.
• 다이나모 스타일 데이터베이스에서 n, w, r 파라미터는 대개 설정 가능하다.
  • 일반적인 선택 : n = 홀수(보통 3이나 5), w = r = (n + 1) / 2 (반올림)
    • r과 w의 값으로 노드의 과반수(n/2 초과)를 선택하는 이유는 n/2 노드 장애까지 허용해도 w +r > n이 보장되기 때문이다. (하지만 셋 중 적어도 하나의 노드만 겹쳐도 됨!)
  • 쓰기가 적고 읽기가 많을 때 선택 : w = n, r = 1 (읽기 속도 UP, 하나의 노드 장애 시 모든 쓰기 실패)

 

2️⃣ 일관성 한계

w + r > n인 경우에도 오래된 값을 반환하는 에지 케이스

• 느슨한 정족수를 사용한다면 w개의 쓰기는 r개의 읽기와 다른 노드에서 수행될 수 있으므로 r개의 노드와 w개의 노드가 겹치는 것을 보장하지 않는다.
• 두 개의 쓰기가 동시에 발생하면 어떤 쓰기가 먼저 일어났는지 분명하지 않다.
• 쓰기와 읽기가 동시에 발생하면 쓰기는 일부 복제 서버에만 반영될 수 있다.
• 쓰기가 일부 복제 서버에서는 성공하고 다른 복제 서버에서 실패해 전체에서 성공한 서버가 w 복제 서버보다 적다면 성공한 복제 서버에서는 롤백하지 않는다.
• 새 값을 전달하는 노드가 고장나면 예전 값을 가진 다른 복제 서버에서 해당 데이터가 복원되고 새로운 값을 저장한 복제 서버 수가 w보다 낮아져 정족수 조건이 깨진다.

 

🔉느슨한 정족수와 암시된 핸드오프
노드가 n개 이상일 때, 클라이언트는 네트워크 장애 상황에서 정족수 구성에 들어가지 않는 데이터베이스 노드(이하 E노드)에 연결될 가능성이 있다. 이때 일단 쓰기를 받아들이고 연결할 수 있는 E노드에 기록하는 것이 느슨한 정족수이다. 이후 네트워크 장애 상황이 해제되면 일시적으로 수용한 모든 쓰기가 지정된 노드에 전송되는 방식을 암시된 핸드오프라고 한다.

 

 

[3] 동시 쓰기 감지

다이나모 스타일 데이터베이스는 여러 클라이언트가 동시에 같은 키에 쓰는 것을 허용하기 때문에 엄격한 정족수를 사용하더라도 충돌이 발생한다.

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

• 최종 쓰기 승리
  • 쓰기에 타임스탬프를 붙여 예전 타임스탬프를 가진 쓰기는 무시, 제일 큰 타임스탬프를 선택하는 방법이다.
  • 손실 데이터를 허용하지 않는다면 충돌 해소에 적합하지 않다.
• 이전 발생 관계 파악
  • 쓰기에 이전 읽기의 버전 번호를 포함하여 이전 상태를 알게 한다.
  • 버전 번호를 포함하지 않은 쓰기는 다른 쓰기와 동시에 수행된 것이므로 아무것도 덮어쓰지 않는다.
• 동시에 쓴 값 병합
  • 애플리케이션 코드로 동시 쓰기의 최종 상태를 결정한다.
• 버전 벡터
  • 모든 복제본의 버전 번호 모음을 사용해 덮어 쓰기와 동시 쓰기를 구분한다.

 

🔉 동시성
- 동시성을 정의하기 위해 정확한 시각은 중요하지 않다. 두 작업이 발생한 물리적인 시각보다 각 작업이 서로 알지 못하면 단순히 두 작업은 동시에 수행됐다 말한다.
- 이전 발생(happends-before)은 동시성의 의미를 정의하는 핵심이다.

 

 

어려웠거나 이해하지 못한 부분(Difficulty)

• [리더없는 복제] 정족수 - n, w, r 파라미터의 생소함

 

추가 내용(Amendment)

참고 자료 <가상 면접 사례로 배우는 대규모 시스템 설계 기초> 6장 키-값 저장소 설계

 

응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정

🧐 W, R, N의 값은 어떻게 정해야 하는 걸까?

• R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템
• W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
• W + R > N : 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
• W + R ≤ N : 강한 일관성이 보장되지 않음

 

일관성 모델(consistency model)

키-값 저장소를 설계할 때 고려해야 할 중요한 요소로, 데이터의 알관성의 수준을 결정한다.

• 강한 일관성(strong consistency) : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 다시 말해서 클라이언트는 절대로 낡은(out-of-date) 데이터를 보지 못한다.
• 약한 일관성(weak consistency) : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
• 최종 일관성(eventual consistency) : 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모둔 사본에 반영(즉, 동기화)되는 모델이다. (다이나모 또는 카산드라 같은 저장소가 사용)

 

일시적 장애 처리

• 느슨한 정족수(sloppy quorum) 접근법
  • 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. 이때 장애 상태인 서버는 무시한다.
  • 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서(hint)를 남긴다. 따라서 이런 장애 처리 방안을 단서 후 임시 위탁(hinted handoff) 기법이라 부른다.

 

🔉해시 링(Hash Ring)
분산 시스템에서 데이터 또는 요청을 특정 노드에 할당할 때 사용하는 원형 형태의 해시 공간이다. 해시 링에는 각 서버와 데이터가 각 해시값에 따라 저장되는데 데이터는 시계 방향으로 가장 가까운 서버에 데이터를 저장한다.