내용 정리
1. 서론
복제란, 네트워크로 연결된 여러 장비에 동일한 데이터이 복사본을 유지한다는 의미이다.
•
데이터 복제가 필요한 이유
◦
지연 시간 감소
▪
지리적으로 사용자와 가깝게 데이터 유지
◦
가용성 증가
▪
시스템 일부 장애가 발생해도 지속적으로 동작 가능
◦
읽기 처리량 증가
▪
읽기 질의 제공하는 장비의 수 확장
•
복제 알고리즘
◦
단일 리더 복제 (single-leader)
◦
다중 리더 복제 (multi-leader)
◦
리더 없는 복제 (leaderless)
•
복제시 고려해야할 트레이드 오프
◦
동기식 복제 vs 비동기식 복제
◦
잘못된 복제본 처리 방식
•
최종적 일관성
◦
쓰기 읽기 (read-your-writes)
◦
단조 읽기 (monotonic read)
2. 리더와 팔로워 (단일 리더기반 복제)
•
복제 서버
◦
DB의 복사본을 저장하는 각 노드
2.1. 리더 기반 복제 (leader-based-replication)
•
복제 서버가 동일한 데이터를 유지하기 위한 일반적인 방법
•
능동/수동, 마스터/슬레이브 복제 라고도 함
•
서버 종류
◦
리더 (마스터, 프라이머리)
◦
팔로워(리드 레플리카, 슬레이브, 2차, 핫대기)
•
프로세스
1.
DB 쓰기 시, 클라이어트는 요청을 리더로 보냄
2.
리더는 먼저 로컬 저장소에 DB 쓰기 진행
3.
복제 로그 또는 변경 스트림의 일부로 팔로워에 데이터 전송
4.
팔로워 로그 수신 후 순차적으로 모든 쓰기를 적용하여 DB 로컬 복사본을 갱신
•
특징
◦
읽기는 리더 또는 팔로워에 질의 가능
◦
쓰기는 리더에게만 허용
•
예시
2.2. 동기식 대 비동기식 복제
•
동기식 복제
◦
개념
▪
리더는 팔로워가 쓰기를 수신했는지 확인 해줄 때 까지 대기
▪
확인 후 사용자에게 성공을 보고하고 다른 클라이언트에게 해당 쓰기를 보여줌
◦
장점
▪
팔로워 & 리더 일관성 있게 최신 데이터 복사본 보장
◦
단점
▪
네트워크 이슈등으로 동기 팔로워 응답 X 인 경우 쓰기 처리 불가
▪
리더 - 모든 쓰기 차단 후 동기 복제 서버가 다시 사용할 수 있을 때까지 대기 필요
•
비동기식 복제
◦
장점
▪
복제가 매우 빠름
▪
모든 팔로워가 잘못되더라도 리더가 쓰기 처리를 계속 진행할 수 있음
◦
단점
▪
데이터 복사의 소요 시간 보장 불가 (데이터 동기화가 안된 상황이 발생할 수도 있음)
•
반동기식 복제
◦
동기식 + 비동기식 복제
◦
적어도 두 노드(리더 + 하나의 동기 팔로워)에 데이터 최신 복사본이 있는것을 보장
•
리더 기반 복제
◦
완전 비동기식으로 구성
◦
리더가 잘못되고 복구 할 수 없는 경우, 팔로워에 복제되지 않은 쓰기는 모두 유실됨
▪
쓰기가 클라이언트에 확인된 경우에도 지속성 보장 불가를 의미
◦
모든 팔로워가 잘못되더라도 리더가 쓰기 처리를 계속 할 수 있음
•
예시
◦
팔로워 1 - 동기식
◦
팔로워 2 - 비동기식
2.3. 새로운 팔로워 설정
때때로 복제 서버 수를 늘리거나, 장애 노드의 대체를 위해 새로운 팔로워 설정이 필요하다. 새로운 팔로워가 리더의 데이터 복제본을 정확히 가지고 있는지 어떻게 보장할까?
1.
전체 DB를 잠그지 않고 리더의 DB 스냅샷을 일정 시점에 갖고옴
2.
스냅샷을 새로운 팔로워 노드에 복사
3.
팔로워는 리더에 연결해 스냅샷 이후 발생한 모든 데이터 변경 요청
•
스냅샷이 리더의 복제 로그의 정확한 위치와 연관되어야 함
•
복제로그의 정확한 위치 예시
◦
PostgreSQL - 로그 일련번호 (log sequence number)
◦
MySQL - 이진로그 좌표 (binlog coordinate)
4.
팔로워가 스냅샷 이후 데이터 변경의 미처리분(backlog)를 모두 처리했을 때 따라잡았다고 말함. 이후 리더에 발생하는 데이터 변화에 이어 처리 가능
2.4. 노드 중단 처리
•
팔로워 장애: 따라잡기 복구
◦
각 팔로워는 리더로부터 수신한 데이터 변경 로그를 로컬 디스크에 보관
▪
팔로워가 죽어 재시작하거나, 리더와 팔로워 사이 네트워크 일시 중단 시, 팔로워는 쉽게 복구 가능
◦
복구 프로세스
1.
보관된 로그에서 결함이 발생하기 전 처리한 마지막 트랜잭션 파악
2.
팔로워는 리더와 연결해 연결이 끊어진 동안 발생한 데이터 변경 요청
3.
변경 적용 완료 이후, 리더를 다 따라잡게 되고, 이전과 같이 변경 스트림 수신
•
리더 장애: 장애 복구
◦
장애 복구(failover)
▪
팔로워 중 하나를 새로운 리더로 승격
▪
클라이언트는 새로운 리더로 쓰기를 전송하기 위한 재설정 필요
▪
다른 팔로워는 새로운 리더로부터 데이터 변경을 소비하기 시작해야함
◦
장애 복구 방법
▪
수동
▪
자동
◦
자동 장애 복구 프로세스
1.
리더가 장애인지 판단
•
타임아웃 사용
2.
새로운 리더 선택
•
선출 과정(리더가 나머지 복제 서버의 대다수에 의해 선택)
•
이전에 선출된 제어노드(controller node)에 의해 임명
•
보통 이전 리더의 최신 데이터 변경 사항을 가진 복제서버가 가장 적합한 후보
3.
새로운 리더를 사용을 위해 시스템 재설정
•
클라이언트가 샐운 쓰기 요청을 새로운 리더로 보냄
•
이전 리더가 복구한 경우, 이전 리더가 팔로워가 되도록 시스템 인식 필요
◦
장애 복구 과정에서 발생할 수 있는 이슈들
▪
비동기 복제 시, 이전 리더의 복제되지 않은 쓰기 이슈 (단순 폐기)
▪
스플릿 브레인(split brain)
•
두 노드가 모두 자신이 리더라고 믿는 상황
•
쓰기 충돌 해소 과정 거치지 않으면 데이터 유실 및 오염 발생 가능
▪
리더 죽었다고 판단하는 적절 타임 아웃 설정 어려움
•
짧은 타임 아웃 - 불필요한 장애 복구
2.5. 리더 기반 복제 동작 매커니즘
•
구문 기반 복제
◦
프로세스
▪
모든 쓰기 요청(구문, statement) 기록 후 쓰기가 실행한 다음 구문을 팔로워에게 전송
▪
관계형 DB는 모든 INSERT, UPDATE, DELETE 구문을 팔로워로 전달
▪
팔로워는 클라이언트에서 직접 받은 것처럼 SQL 구문 파싱 후 실행
◦
문제점
▪
비결정적 함수를 호출하는 구문은 값이 다르게 생성될 수 있음
•
현재 날짜와 시간을 얻기 위한 NOW() , 임의의 숫자를 얻기 위한 RAND()
▪
각 복제 서버에서 정확하게 같은 순서로 실행되지 않을 경우, 효과가 달라 질 수 있음
•
자동 증가 컬럼 사용 구문
•
DB의 특정 데이터 의존 (UPDATE …. WHERE < some condition )
▪
부수효과를 가진 구문은 부수효과가 완벽하게 결정적이지 않으면 다른 부수효과 발생 시킬 수도 있음
•
쓰기전 로그 배송
◦
로그란?
▪
로그 : 모든 쓰기를 포함하는 추가 전용 바이트 열
▪
예시
•
로그 구조화 저장소 엔진 - 로그 세그먼트
•
B 트리 - 쓰기전 로그
◦
프로세스
▪
완전한 동일한 로그를 사용해 다른 노드에서 복제 서버 구축 가능
▪
리더: 팔로워에게 네트워크로 로그 전송
◦
문제점
▪
로그가 제일 저수준의 데이터를 기술한다는 점
•
어떤 디스크 블록에서 어떤 바이트를 변경했는지 등 상세 정보 포함
•
복제가 저장소 엔진과 밀접하게 엮임 (예. DB가 저장소 형식을 다른버전으로 변경시, 이슈 발생)
•
WAL 배송(shipping)과 같이 복제 프로토콜이 버전 불일치를 허용하지 않으면 업그레이드 시 중단 시간 필요
▪
팔로워가 리더보다 새 소프트웨어 버전을 사용하게끔 복제 프로토콜 허용 시
•
팔로워가 먼저 업그레이드 진행 → 무중단 데이터베이스 소프트웨어 업그레이드 수행 가능
•
장애 복구 수행 → 업그레이드된 노드 중 하나를 새로운 노드로 선정
•
논리적(로우기반) 로그 복제
◦
정의
▪
복제와 저장소 엔진을 위해 다른 로그 형식 사용
▪
논리적 로그(logical log)
•
저장소 엔진의 물리적 데이터 표현과 구별
•
로우 단위로 DB 테이블에 쓰기를 기술한 관련 레코드열
▪
예시
•
삽입된 로우 로그
◦
모든 컬럼의 새로운 값 포함
•
삭제된 로우 로그
◦
고유하게 식별하는데 필요한 정보 포함 (기본키)
•
갱신된 로우의 로그
◦
고유하게 식별한는데 필요한 정보 + 모든 컬럼의 새로운 값 포함
•
여러 로우 수정하는 트랜잭션
◦
여러 로그 레코드 생성 후 트랜잭션이 커밋되었음을 레코드로 표시 (MySQL binlog)
◦
특징
▪
저장소 엔진 내부와 분리 → 하위 호환성 유지 용이
▪
리더와 팔로워에서 다른 버전의 데이터 소프트웨어나 다른 저장소 엔진 실행 가능
▪
변경 데이터 캡쳐 (change data capture) -CDC
•
외부 애플리케이션 파싱 용이
•
외부 시스템에 데이터베이스 내용을 전송하고자 할 때 유용
•
트리거 기반 복제
◦
정의
▪
애플리케이션 코드를 통한 복제
▪
유연성이 필요한 상황에 사용
•
데이터 서브셋만 복제
▪
데이터베이스를 다른 종류의 데이터베이스로 복제
▪
충돌 해소 로직
◦
예시
▪
오라클 골든 게이트, 트리거. 스토어 프로시저
◦
트리거
▪
사용자 정의 애플리케이션 코드를 등록 할 수 있게 함
▪
DB 시스템에서 데이터 변경(쓰기 트랜잭션) 시, 자동 실행
▪
데이터 변경을 분리된 테이블에 로깅 가능
▪
이 테이블로부터 데이터 변경을 외부 프로세스가 읽을 수 있음
▪
외부 프로세스는 필요한 애플리케이션 로직을 적용해 다른시스템으로 변경 복제
2.6. 복제 지연 문제 (리더 기반의 비동기식 복제)
•
읽기 확장 아키텍쳐 (read-scaling)
◦
리더 기반 복제에서 읽기 전용 질의는 어떤 복제 서버에서도 가능
◦
읽기 요청 비율이 높은 패턴에서 활용 가능
◦
팔로워 추가 → 읽기 전용 요청 처리 증가
◦
비동기식 복제에서만 동작
▪
동기식: 단일 노드 장애 또는 네트워크 중단으로 전체 시스템 쓰기가 불가능해짐
•
최종적 일관성
◦
비동기 팔로워에서 복제 지연 발생 가능
◦
그러나 불일치는 일시적인 상태에 불과함
◦
언젠가는 따라잡게되고 리더와 일치하게 됨
•
복제 지연 문제 대응 방법
◦
자신의 쓰기 후 읽기 지연 → 쓰기 후 읽기 일관성
◦
시간 역전 현상 → 단조 읽기
◦
인과성 위반 → 일관된 순서로 읽기
2.7. 복제 지연 발생 이상 현상
•
쓰기 후 읽기 일관성 (read-after-write)
◦
개념
▪
사용자가 쓰기 후, 읽기를 다른 복제 서버에서 진행 시 지연이 발생할 수 있음
◦
구현 기법
▪
사용자가 수정한 내용을 읽을때는 리더에서 읽음
•
예) 소셜 네트워크에서 사용자 프로필 정보
▪
리더에서 읽을지 말지를 결정하기 위한 다른 기준 필요
•
애플리케이션 내 대부분의 내용을 사용자가 편집 할 수 있는 경우, 대부분 리더에서 읽음 → 읽기 확장 이점 무효화
•
예)
◦
마지막 갱신 시간 기준으로 1분동안 리더에서 모든 읽기 수행
◦
팔로워에서 복제 지연을 모니터링 → 1분 이상 늦은 모든 팔로워에 대한 질의 금지
▪
논리적 타임스탬프 / 실제 시스템 시간
•
클라이언트에서 가장 최근 쓰기의 타임스탬프 기억
•
복제 서버가 아직 최신 내용이 아닌 경우 → 다른 복제 서버가 읽기 처리 혹은 질의 대기
▪
다중 데이터센터 분산시
•
리더가 제공해야하는 모든 요청은 리더가 포함된 데이터센터로 라우팅
예시
◦
cf) 디바이스간 쓰기 후 읽기 일관성
▪
사용자의 마지막 갱신 타임스탬프 기억하는 접근 방식이 어려움
•
메터 데이터를 중앙 집중식으로 관리
▪
복제 서버가 여러 데이터 센터간에 분리된 경우
•
다른 디바이스 연결이 동일한 데이터 센터로 라우팅 된다는 보장이 없음
◦
DESKTOP - LAN 광대역 연결
◦
MOBILE - 셀룰러 네트워크
◦
디바이스간 네트워크 라우팅이 상이함
•
리더에서 읽어야 할 필요가 있는 접근법이면 사용자 디바이스 요청을 동일한 데이터센터로 라우팅 해야함
•
단조 읽기
◦
개념 및 특징
▪
사용자의 시간이 거꾸로 흐르는 현상 (시간 역전 현상)을 방지
•
리더로부터의 데이터 동기화가 다 되지 않은 상태에서, 클라이언트가 동기화가 된 팔로워로부터 읽기를 시도 한 후, 동기화가 되지 않은 팔로워로부터 같은 데이터에 대해 읽기를 시도하는 경우
▪
강한 일관성보다는 덜한 보장이지만 최종적 일관성 보다 더 강한 보장
▪
새로운 데이터를 읽은 후에는 예전 데이터를 읽지 않음
◦
프로세스
▪
각 사용자의 읽기가 항상 동일한 복제 서버에서 수행되게끔 함
▪
예시) 사용자 ID의 해시 기반으로 복제 서버를 선택
◦
예시
•
일관된 순서로 읽기
◦
개념 및 특징
▪
인과성 위반 우려 대응
▪
일련의 쓰기가 특정 순서로 발생 시, 이 쓰기를 읽는 모든 사용자는 같은 순서로 쓰여진 내용을 보게 됨을 보장
▪
파티셔닝(샤딩) 데이터베이스에서 발생 가능한 문제
◦
프로세스
▪
서로 인과성이 있는 쓰기는 동일한 파티션에 기록되게 하는 방법
▪
인과성을 명시적으로 유지하기 위한 알고리즘 사용
◦
예시
3. 다중 리더 기반 복제
•
단일 리더 기반 복제의 문제점
◦
리더에 이슈가 발생시 쓰기 불가
•
다중 리더 설정 (마스터 마스터, 액티브/액티브 복제)
◦
쓰기를 허용하는 노드를 하나 이상 두는 것
◦
각 리더는 동시에 다른 리더의 팔로워
3.1. 다중 리더 복제의 사용 사례
•
다중 데이터센터 운영
◦
장점
▪
성능
•
모드 쓰기는 로컬 데이터 센터에 처리 후 비동기 방식으로 복제
•
사용자가 인지하는 성능 좋음
▪
데이터센터 중단 내성
•
데이터센터간 독립성 보장
•
온라인으로 돌아왔을 때 복제 따라잡음
▪
네트워크 문제 내성
•
일시적인 네트워크 중단에도 쓰기 처리 가능
◦
단점
▪
쓰기 충돌 문제 발생 가능 (동일한 데이터를 다른 두개의 센터에서 동시 변경)
▪
Auto Increment, 트리거, 무결성 제약
◦
예시
•
오프라인 작업을 하는 클라이언트
◦
오프라인 상태에서도 애플리케이션 동작 보장
▪
여러 기기에서 오프라인 상태에서 진행한 쓰기 작업을 다중으로 처리할 수 있음
•
협업 편집
◦
실시간 협업 편집 애플리케이션
▪
여러사람이 동시에 편집 가능한 애플리케이션
◦
한 사용자가 문서 편집 할 때 변경 내용을 즉시 로컬 복제 서버에 적용
◦
동일한 문서를 편집하는 다른사용자와 서버에 비동기 방식으로 복제
3.2. 쓰기 충돌
•
다중 리더 복제의 대표적인 문제 → 충돌 해소 필요
◦
예시
•
동기대 비동기 충돌 감지
◦
단일 리더
▪
첫번째 쓰기 완료될 때가지 두번째 쓰기 차단 및 대기 또는 재시도 요청
◦
다중 리더
▪
두 쓰기 모두 성공, 충돌은 이후 특정 시점에서 비동기로만 감지
◦
충돌 감지를 동기식으로 만들 수 있으나 다중 리더 복제의 장점을 잃음
•
충돌 회피
◦
특정 레코드의 모든 쓰기가 동일한리더를 거치도록 애플리케이션에서 보장
•
일관된 상태 수렴
◦
다중 리더 설정에서는 쓰기 순서가 정해지지 않아 최종값 명확하지 않음
◦
모든 복제 서버가 최종적으로 동일하다는 사실을 보장해야 함
◦
데이터베이스는 수렴(convergent) 방식으로 충돌을 해소해야함
▪
모든 변경이 복제돼 모든 복제 서버에 동일한 최종값이 전달되게 해야 함
◦
수렴 충돌 해소 방식
▪
최종 쓰기 승리(LWW, Last Write Wins)
•
각 쓰기에 고유 ID를 부여하고 가장 높은 ID를 가진 쓰기를 고름
◦
고유 ID 예시 - 타임스탬프, UUID, 키와 값의 해시값, 긴 임의 숫자
•
대중적이나 데이터 유실 위험 있음
▪
각 복제서버에 고유 ID 부여 후 높은 숫자의 복제 서버에 생긴 쓰기가 항상 우선적으로 적용
•
데이터 유실 위험 존재
▪
어떻게든 값 병합
•
예) 사전 순서로 정렬 후 연결
▪
명시적으로 데이터 구조에 충돌을 기록해 모든 정보 보존
•
충돌 해소 애플리케이션 코드 작성
•
사용자 정의 충돌 해소 로직
◦
쓰기 수행 중 실행
▪
시스템 충돌을 감지 하자마자 충돌 핸들러 호출
▪
사용자에게 충돌 내용 표시 X
▪
백그라운드에서 빠르게 실행
◦
읽기 수행 중 실행
▪
출동 감지 → 모든 충돌 쓰기 저장
▪
다음 데이터를 읽을 때 여러 버전의 데이터가 애플리케이션에 반환
▪
애플리케이션은 충돌 내용을 보여주거나 자동으로 해소
▪
충돌 해소된 결과가 데이터베이스에 기록
•
자동 충돌 해소
◦
충돌 없는 복제 데이터 방식 (CRDT, Conflict-free Replicated Data Type)
▪
set, map, 정렬목록, 카운터 등을 위한 데이터 구조 집합
▪
동시에 여러 사용자가 편집 가능한 합리적인 방법
◦
병합 가능한 영속 데이터 구조
▪
Git 버전과 유사하게 명시적으로 히스토리 추적
▪
삼중 병합 함수 사용
◦
운영 변환
▪
협업 편집 애플리케이션의 충돌 해소 알고리즘
3.3. 다중 리더 복제 토폴로지
•
복제 토폴로지
◦
쓰기를 한 노드에서 다른 노드로 전달하는 통신 경로
•
종류
◦
전체 연결 (all-to-all)
▪
모든 리더가 각자의 쓰기를 다른 모든 리더에게 전송
◦
원형 (circular)
▪
MySQL의 기본 방식
▪
각 노드가 하나의 노드로부터 쓰기를 받음
▪
이 쓰기(자신의 쓰기도 추가)를 다른 한 노드에 전달함
◦
별 (star)
▪
지정된 루트 노드 하나가 다른 모든 노드에 쓰기를 전달
▪
트리로 일반화 가능
◦
예시
•
원형 & 별 모양 토폴로지
◦
특징
▪
쓰기가 모든 복제 서버에 도달하기 위해 여러 노드에 거쳐야 함
▪
노드들은 다른 노드로 받은 데이터 변경 사항을 전달해야함
▪
무한 복제 루프 방지를 위해 고유 식별자 사용
◦
문제점
▪
하나의 노드 장애가 다른 노드 간의 복제 메세지 흐름에 방해를 줄 수 있음
▪
메세지가 여러 경로를 따라 이동시, 단일 장애점 (single point of failure) 회피 가능
•
전체 연결 토폴로지
◦
일관된 순서로 읽기 (인과성 문제) 발생 가능
▪
네트워크 이슈로 인해 일부 복제 서버에 쓰기가 잘못된 순서로 올 수 있음
▪
버전 벡터 기법 사용
▪
많은 다중 리더 복제 시스템에서 충돌 감지 기법이 제대로 구현되어 있지 않음
•
PostgreSQL - 쓰기의 인과적 순서 제공 X
•
MySQL 텅스텐 리플리케이터 - 충돌을 감지하기 위한 시도 X
4. 리더 없는 복제
•
단일 리더 & 다중 리더 복제 방식
◦
클라이언트가 쓰기 요청을한 노드(리더)에 전송
◦
데이터베이스 시스템이 쓰기를 다른 복제 서버에 복사 처리
◦
리더는 쓰기를 처리하는 순서를 정하고 팔로워는 동일한 순서의 리더의 쓰기 적용
•
리더 없는 복제
◦
리더의 개념 제거
◦
모든 복제 서버가 클라이언트로부터 쓰기를 직접 받을 수 있도록 허용
◦
예시
▪
아마존 - 다이나모 시스템
4.1. 노드가 다운되었을 때 데이터베이스에 쓰기
•
리더 기반 복제
◦
쓰기 처리를 위해 장애 복구 실행 필요
•
리더 없는 복제
◦
장애 복구 불필요
◦
복제 서버 중 하나의 쓰기를 놓친 사실을 단순 무시
◦
읽기 요청 병렬로 여러 노드에 전송
▪
클라이언트에서 복제가 실패된 노드에서 데이터 조회시 오래된 값을 읽을 수 있는 이슈 해결 가능
▪
한노드에서 최신값, 다른 노드에서 오랜된 값 → 버전 숫자를 사용해 어떤 값이 최신인지 결정
◦
예시
•
읽기 복구와 안티 엔트로피
◦
최종적으로 모든 데이터가 모든 복제 서버에 복사 된 것을 보장해야함
◦
사용 불가능한 노드가 온라인 상태가 된 후 누락된 쓰기를 어떻게 따라 잡을 것인지?
◦
읽기 복구
▪
클라이언트가 여러 노드에서 병렬로 읽기를 수행하여 오랜된 응답을 인지
▪
해당 복제 서버에 새로운 값 기록
◦
안티 엔트로피 처리
▪
백그라운드 프로세스를 두고 복제 서버간 데이터 차이를 지속적으로 탐색
▪
누락된 데이터를 복사
▪
특정 순서로 쓰기를 복사하므로 데이터 복사까지 지연 발생
4.2. 읽기와 쓰기를 위한 정족수
•
쓰기 성공 허용 범위 설정의 문제 해결 방식
•
정족수 읽기와 쓰기
◦
r과 w를 따르는 읽기와 쓰기
◦
유효한 읽기와 쓰기를 위해 필요한 최소 투표수: r & w
•
개념
◦
n: 복제 서버의 개수
◦
w: 쓰기 성공이 요구되는 노드 의 수
◦
r: 질의를 해야하는 최소 노드 의 수
◦
w+ r > n일 경우 최신 값을 얻을 것을 기대
▪
n = 3, w = 2, r = 2
•
다이나모 스타일 데이터베이스에서는 n, w, r 파라미터 설정가능
◦
n을 홀수로 설정(3 또는 5)
◦
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개 노드보다 사용가능한 노드가 적다면 쓰기나 읽기는 에러 반환
4.3. 정족수 일관성의 한계
•
w + r > n
◦
일반적으로 모든 읽기는 키의 최신 값을 반환할 것을 기대함
◦
읽은 노드 중 에는 최신값을 가진 노드가 최소한 하나는 있을 것
•
r과 w의 값으로 노드의 과반수 (n/2 초과)를 선택
◦
n/2 노드 장애가 허용해도 w + r > n이 보장되기 때문
•
정족수가 다수 일 필요는 없음
•
w와 r이 작을수록 오랜된 값이 확률이 높음
◦
최신 값을 가진 노드가 읽을 노드에 포함되지 않을 가능성이 있음
•
w+ r > n이 오래된 값을 반환하는 엣지 케이스
◦
느슨한 정족수
▪
w개의 쓰기는 r개의 읽기와 다른 노드에서 수행될 수 있음
▪
r개의 노드와 w개의 노드가 겹치는 것이 보장 X
◦
두개의 쓰기가 동시 발생
▪
순서를 모름
▪
동시 쓰기 병합 필요
◦
쓰기와 읽기 동시 발생
▪
쓰기가 일부 복제 서버에만 반영
◦
쓰기가 일부에만 성공하여 전체 성공 서버가 w 복제 서버 보다 적다면 데이터 롤백하지 않음
◦
새 값을 전달하는 노드 고장
▪
예전 값을 가진 다른 복제 서버에서 해당 데이터 복원
▪
새로운 값을 저장한 복제 서버 수가 w 보다 낮아져 정족수 조건 깨짐
◦
모든 과정이 올바르게 동작해도 시점 문제 발생 가능
4.4. 느슨한 정족수와 암시된 핸드오프
•
느슨한 정족수
◦
일단 쓰기를 받아들이고, 값이 보통 저장되는 n개 노드에 속하지는 않지만 연결할 수 있는 노드에 기록
◦
쓰기와 읽기는 여전히 w와 r의 성공 응답이 필요
◦
값을 위해 지정된 n개의 홈 노드에 없는 노드가 포함될 수 있음
•
암시된 핸드 오프
◦
네트워크 장애 상황 해제시, 한 노드가 다른 노드를 위해 일시적으로 수용한 모든 쓰기를 해당 홈 노드로 전송
•
특징
◦
쓰기 가용성을 높이는데 유용
◦
모든 w개의 노드를 사용할 수 있는 동안 데이터베이스는 쓰기 받아들일 수 있음
▪
w + r > n 인 경우에도 키의 최신 값을 읽는다고 보장 X
▪
최신값이 일시적으로 n 이외의 노드에 기록될 수 있음
◦
단지 지속성에 대한 보장으로 데이터가 w 노드 어딘가에 저장된다는 의미
◦
암시된 핸드오프가 완료 될 때까지는 r 노드의 읽기가 저장된 데이터를 본다는 보장이 없음
4.5. 동시 쓰기 감지
•
여러 클라이언트가 동시에 같은 키 쓰는것을 허용 → 엄격한 정족수 사용하더라도 충돌 발생
◦
다중 리더 복제의 쓰기 충돌과 유사
•
부분적인 장애로 인해 이벤트가 다른 노드에 다른 순서로 도착할 수도 있음
◦
예시
4.6. 최종 쓰기 승리 (동시 쓰기 버리기)
•
각 복제본이 가진 예전 값을 버리고 가장 최신값으로 덮어쓰는 방법
•
최신 이라는 개념은 모호할 수 있음
◦
이벤트 순서가 정해지지 않았음
•
최종 쓰기 (LWW) 충돌 해소 알고리즘
◦
쓰기에 타임스탬프를 붙여 제일 큰 타임 스탬프 선택
◦
최종 수렴 달성이 목표나, 지속성을 희생 시킴
▪
동일한 키에 여러번 동시 쓰기가 있다면 클라이언트에 모두 성공 보고
▪
쓰기중 하나만 남고 다른 쓰기는 무시됨
◦
손실 데이터 허용하지 않을 경우 부적합
◦
LWW로 데이터베이스를 안전하게 사용하는 유일한 방법
▪
키를 한번만 쓰고 이후에 불변값으로 다루는 것
▪
같은 키를 동시에 갱산하는 상황 방지
▪
카산드라 - UUID로 모든 쓰기 작업에 고유키 부여
4.7. 이전 발생 관계와 동시성
•
작업의 인과성 (casually dependant)
◦
생성(A 작업) → 업데이트:INCR (B 작업)
▪
B는 A에 인과성이 있다고 볼 수 있음
▪
A는 B의 이전 발생(happens-before)
•
인과성이 없는 경우 → 동시 작업
•
이전 발생 관계 결정 알고리즘
◦
서버가 모든 키에 대한 버전 번호 유지하고 키를 기록할 때마다 버전 번호 증가시킨다. 기록한 값은 새로운 버전 번호를 가지고 저장된다.
◦
클라이언트가 키를 읽을 때는 서버는 최신 버전뿐만 아니라 덮어쓰지 않은 모든 값을 반환한다. 클라이언트는 쓰기전에 키를 읽어야한다.
◦
클라이언트가 키를 기록할 때는 이전 읽기의 번호를 포함해야하고, 이전 읽기에서 받은 모든 값을 합쳐야 한다
◦
서버가 특정 버전 번호를 가진 쓰기를 받을 때 해당 버전 이하 모든 값을 덮어 쓸 수 있다. 하지만 이보다 높은 버전 번호의 모든 값을 유지해야 한다.
예시
•
동시에 쓴 값 병합
◦
위 알고리즘을 위해 클라이언트에서 추가 작업 필요
▪
동시에 쓴 값 (형제값)을 합쳐 정리향함
◦
형제값 병합은 다중리더 복제의 충돌 해소 문제와 본질적으로 같음
▪
최종 쓰기 승리
▪
애플리케이션 코드
◦
형제값 병합의 가장 합리적인 접근 방식
▪
합집합 취하기 (장바구니 예제)
◦
툼스톤
▪
제거도 할 수있게 하려면 제거되었음을 나타내기 위해 해당 버전 번호에 표시를 남겨둬야 함
▪
이런 삭제 표시를 의미함
•
버전 벡터
◦
다중 복제본이 존재할 경우, 모든 복제본의 버전 번호의 모음
◦
키당 버전 번호 뿐만 아니라 복제 번호도 필요함
◦
하나의 복제본을 읽은 다음, 다른 복제본에 다시 쓰는 방법으로 안전함을 보장
5. 정리
5.1. 복제의 용도
•
고가용성
•
연결이 끊긴 작업 동작
•
지연 시간 감소
•
확장성 증가
5.2. 복제 접근 방식
•
단일 리더 복제
◦
이해하기 쉽고 충돌 해소 우려 없음
•
다중 리더 복제
◦
결함 노드, 네트워크 중단, 지연시간 급증에 장점
◦
설명하기 어렵고 일관성 보장안됨
•
리더 없는 복제
◦
결함 노드, 네트워크 중단, 지연시간 급증에 장점
◦
설명하기 어렵고 일관성 보장안됨
5.3. 복제 방식
•
동기
•
비동기
◦
시스템이 원활히 동작할 때는 빠름
◦
복제 지연이 증가하고 서버 장애 발생 시, 이슈 발생할 수 있음
5.4. 복제 지연 발생 이상 현상
•
쓰기 후 읽기 일관성
◦
사용자는 자신이 제출한 데이터를 항상 볼수 있어야 함
•
단조 읽기
◦
사용자가 어떤 시점에 데이터를 본 후에는 예전 시점의 데이터는 나중에 볼 수 없음
•
일관된 순서로 읽기
◦
사용자는 인과성이 있는상태의 데이터를 봐야한다.
5.5. 쓰기 충돌
•
다중 리더 복제와 리더 없는 복제 접근 방식의 동시성 문제
•
쓰기 충돌 해결 알고리즘
◦
LLW
◦
이전 발생 관계 결정 알고리즘
스터디
1. 질문만들기
Harry
수렴 충돌 해소 방식을 설명하시오
이전 발생 관계 결정 알고리즘이란?
복제 지연 발생 이상 현상에 대해 서술하시오
Matthew
복제 방식 3가지의 특정 혹은 장단점을 설명하시오
고가용성, 툼스톤이란 무엇인가?
복제 동기 / 비동기식 방법의 특징을 설명하시오
2. 책 같이 살펴보기
•
(p168)서로 인과성이 있는 쓰기는 동일한 파티션에 기록되게 하는 방법
◦
파티션은 테이블에 종속적인 개념. 인과성이 있는 쓰기는 테이블에 종속적이지 않더라도 발생할 수 있지 않나?
▪
예)A 테이블, B 테이블
▪
이걸, 동일한 파티션에 기록되게 한다는게 어떤의미일까
•
(p183) 쓰기가 일부에만 성공하여 전체 성공 서버가 w 복제 서버 보다 적다면 데이터 롤백하지 않음
◦
쓰기를 보장해야하는 노드의 개수가 w인데, 그중 일부만 성공한다는게 어떤의미인지?