[내용 정리]
1. 일관성 보장과 선형성
1.1. 서론
•
내결함성
◦
분산 시스템에서 가장 중요한 요소
◦
결함이 있더라도, 서비스가 올바르게 동작해야함
•
내결함성을 지닌 분산 시스템 구축이 필요
◦
알고리즘, 프로토콜
•
구축 방법
◦
범용 추상화를 구현하고 애플리케이션에서 이 보장에 의존
▪
예) 트랜잭션 - 이슈가 발생하더라도 트랜잭션 추상화로 내결함성 보장
◦
추상화
▪
합의 - 모든 노드가 어떤 것에 동의하게 만드는 것
▪
합의 알고리즘
1.1.1. 일관성 보장과 선형성
•
최종적 일관성
◦
복제 데이터베이스에서 쓰기를 멈추고, 특정 시간 동안 기다리면 결국 모든 읽기 요청은 같은 값을 반환한다.
◦
최종적으로는 일관된 값을 반환한다.
◦
모든 복제본이 같은 값으로 수렴되기를 기대함
•
최종적 일관성은 약한 보장
◦
언제 복제본이 수렴될지 모름
•
강한 일관성 모델
1.1.2. 선형성
•
정의
◦
시스템에 데이터 복사본은 하나만 있고, 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것 처럼 보이게 만드는 것
◦
읽힌 값은 항상 최근에 갱신한 값
◦
뒤처진 캐시나 복제본에서 나오지 않았음을 보장
◦
최신성 보장
•
Alias
◦
원자적 일관성, 강한 일관성, 즉각 일관성, 외부 일관성
•
비선형적 시스템 예시
1.2. 시스템에 선형성을 부여하는 것은 무엇인가?
•
선형성 기본 아이디어
◦
시스템이 데이터 복사본이 하나뿐인 것처럼 보이게 만드는 것
•
레지스터
◦
데이터베이스의 개별 객체
▪
키-값 저장소의 키 하나, 데이터베이스의 로우 하나, 문서 데이터베이스의 문서 하나
•
레지스터 예제 1
◦
연산 종류
▪
read(x) ⇒ v :클라이언트가 레지스터 x 값을 읽기를 요청했고, 값 v를 반환했다는 것을 의미
▪
wirte(x, v) ⇒ r : 클라이언트가 레지스터 x 의 값을 v로 설정하라고 요청했고, 데이터베이스가 응답 r(성공/실패)를 반환했다는 것을 의미
◦
상황
▪
x의 처음 값은 0이고, 클라이언트 C 가 1로 설정하는 쓰기 요청 실행
▪
요청이 실행되는 동안 클라이언트 A, B는 최신 값을 읽기 위해 반복적으로 데이터베이스 폴링
▪
A, B는 자신의 읽기 요청에 어떤 응답을 받을 수 있을까?
•
클라이언트 A의 첫번째 읽기 연산은 쓰기 연산 시작 전에 완료되므로 0을 반환하는것이 명백
•
클라이언트 A의 마지막 읽기는 쓰기가 완료된 후 시작하므로 명핵히 새로운 값 1을 반환해야함
•
쓰기 연산과 시간이 겹치는 읽기 연산은 0 또는 1을 반환한다. 시점을 명확히 알 수 없다. 쓰기 연산과 읽기 연산이 동시에 실행된다.
•
레지스터 예제 2
◦
시스템을 선형적으로 만들기 위해 제약 조건 추가
◦
x값이 원자적으로 0에서 1로 바뀌는 (쓰기 연산의 시작과 끝사이) 어떤 시점이 있어야한다고 상상.
◦
따라서, 한 클라이언트의 읽기가 새로운 값 1을 반환하면 이후 모든 읽기 또한 새로운 값을 반환해야함 (쓰기 연산이 아직 완료되지 않았더라도)
◦
예)
▪
클라이언트 A가 새로운 값 1을 읽은 다음에는 B는 반드시 1을 읽어야함
•
레지스터 예제 3
◦
연산 종류
▪
cas(x, v[old], v[new]) ⇒ r :클라이언트가 원자적 compare and set 연산을 요청함.
◦
연산이 실행되었다고 생각하는 시점이 수직선으로 표시됨
◦
표시들이 모여 순차열을 이루며, 그 결과는 레지스터에 실행된 읽기와 쓰기의 유효한 순차열이 돼야한다.
◦
선형성의 요구사항
▪
연산 표시를 모은 선들이 항상 시간 순으로 진행되어야하며, 결코 뒤로 가서는 안됨 → 최신성 보장
▪
새로운 값이 쓰여지거나 읽히면, 이후 실행되는 모든 읽기는 값이 다시 쓰여질 때까지 쓰여진 값을 읽게 됨
•
선형성 vs 직렬성
◦
선형성
▪
레지스터(개별 객체)에 실행되는 읽기와 쓰기에 대한 최신성 보장
▪
연산을 트랜잭션으로 묶지 않음. 충돌 구체화 등을 사용하지 않을 경우 쓰기 스큐와 같은 문제 못막음
◦
직렬성
▪
모든 트랜잭션이 여러 객체를 읽고 쓸 수 있는 상황에서의 트랜잭션의 격리 속성
1.3. 선형성에 기대기
•
선형성이 중요한 요구사항이 되는 영역
1.3.1. 잠금과 리더 선출
•
스플릿 브레인 방지 필요 → 분산 잠금을 활용하여 리더 선출
•
코디네이션 서비스 사용
◦
아파치 주키퍼, etcd
◦
합의 알고리즘을 상요해 선형성 연산을 내결함성 있는 방식으로 구현
◦
선형성 저장소 서비스
1.3.2. 제약 조건과 유일성 보장
•
제약조건 강제시 선형성 필요함
•
잠금(사용자명에 잠금). 원자적 Compare And Set과 유사
•
예시) 은행 계좌 잔고, 재고 수준, 좌석 점유
◦
모든 노드가 동의하는 하나의 최신 값이 있기를 요구함
1.3.3. 채널간 타이밍 의존성
•
파일 저장소와 메시지 큐
◦
파일 저장 서비스가 성형적일 경우 시스템은 잘 동작
◦
선형적이지 않을 경우, 경쟁 조건의 위험 존재
▪
부가적인 통신 채널 제어 필요
1.4. 선형성 시스템 구현하기
•
선형성
◦
데이터 복사본이 하나만 있는 것처럼 동작하고, 그 데이터에 실행되는 모든 연산은 원자적
•
복제방법과 선형성
◦
단일 리더 복제 (선형적이 될 가능성 있음)
▪
설계,(스냅샷 격리) ,동시성 버그 등으로 선형적이지 않을 수도 있음
◦
합의 알고리즘 (선형적)
▪
스플릿 브레인과 복제본이 뒤처지는 문제를 막는 수단을 포함 → 선형적
◦
다중 리더 복제 (비선형적)
▪
비동기로 내용을 복제하므로 비선형적
◦
리더 없는 복제 (아마도 비선형적)
▪
정족수 읽기와 쓰기(w + r > n)은 정속수의 정확한 설정 / 엄격한 일관성을 어떻게 정의하냐에 따라 다를 수 있음
▪
일 기준 시계 기반의 최종 쓰기 승리는 비선형적
▪
느슨한 정족수도 비선형적
1.4.1. 선형성과 정족수
리더 없는 시스템은 선형성을 제공하지 않음
•
엄격한 정족수를 사용하지만 비선형적인 실행이 발생할 수 도 있음
◦
네트워크 지연으로 인한 경쟁 조건 발생
◦
w+ r < n 이더라도 선형적이지 않을 수 있음
•
성능 저하 비용을 지불하여 다이나모 스타일 정족수를 선형적으로 만드는 것도 가능 (358)
◦
읽기 클라이언트 - 결과를 반환하기 전에 읽기 복구를 동기적으로 수행
◦
쓰기 클라이언트 - 쓰기 요청을 보내기 전에 노드들의 정족수로부터 최신 상태 읽기
1.5. 선형성의 비용
•
다중 리더 복제에서의 다중 데이터 센터
◦
다중 데이터 센터 복제에 좋은 옵션
◦
데이터 센터 간 네트워크 연결 끊킴에도 정상 동작 가능
▪
큐에 쌓아뒀다가 동기식으로 데이터 전송
•
단일 리더 복제에서의 다중 데이터 센터
◦
모든 쓰기와 선형성 읽기는 리더로 보내져야야함
◦
데이터 센터간 네트워크 연결 끊킬시 비선형적
1.5.1. CAP 정리
•
선형성 비용의 트레이드 오프
◦
선형성 → 가용성 없음
▪
다른 복제 서버와 연결이 끊키면 일부 복제 서버는 연결이 끊긴 동안 요청 처리 불가 네트워크 문제 해결때까지 오류 반환.
◦
가용성 → 선형성 없음
▪
독립적으로 요청 처리 가능.
•
CAP 정리
◦
일관성 (Consistency)
◦
가용성 (Availability)
◦
분단 내성 (Partition tolerance)
•
네트워크 결함 발생 시, 선형성과 완전한 가용성 중 하나를 선택해야함.
•
CAP는 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 선택하라는 의미
1.5.2. 선형성과 네트워크 지연
•
선형성을 보장하지 않는 이유(제거한 이유)는 내결함성이 아니라 성능 때문
◦
선형성은 느림
◦
지연 시간에 민감한 시스템은 트레이드 오프(완화된 일관성 모델)가 중요함.
2. 순서화 보장
•
순서화, 선형성, 합의 등에는 깊은 연관 관계가 존재
2.1. 순서화와 인과성
•
순서화는 인과성을 보존하는데 도움을 줌
•
인과성 예시
◦
인과적 의존성
◦
이전 발생
◦
인과성에 일관적
◦
쓰기 스큐
•
인과성은 이벤트에 순서를 부과
◦
결과가 나타나기전에 원인이 발생
•
인과적으로 일관된 시스템
◦
인과성에 의해 부과된 순서를 지키는 시스템
◦
예) 스냅샷 격리
2.1.1. 인과적 순서는 전체 순서는 아니다
•
전체 순서와 부분 순서
◦
전체 순서
▪
어떤 두 요소를 비교할 수있게 함.
▪
예) 자연수. 전체 순서 정할 수 있음
◦
부분 순서
▪
수학적 집합
•
{a, b} > {b, c} 비교 불가
•
부분적으로 순서가 정해진다
•
데이터베이스 일관성 모델
◦
선형성
▪
선형성 시스템에서는 연산의 전체 순서를 정할 수 있음
◦
인과성
▪
두 연산이 동시에 실행될 경우, 비교 불가
•
인과적 관계가 있으면 순서가 있지만, 동시 실행시 비교 불가
▪
인과성이 전체 순서가 아닌 부분 순서를 정의함
•
선형성 데이터스토어에는 동시적 연산이 없음
◦
하나의 타임 라인이 있고, 모든 연산은 그 타임 라인에 따라 전체 순서가 정해져야함
◦
타임라인에 따라 단일 데이터 복사본에 연산을 실행하여 모든 요청이 원자적으로 처리되도록 보장
2.1.2. 선형성은 인과적 일관성보다 강하다
•
인과적 순서와 선형성 사이의 관계
◦
선형성은 인과성을 내포한다
◦
어떠 시스템이든지 선형적이라면 인과성을 올바르게 유지함
•
단, 선형성이 높으면 성능과 가용성이 낮을 수 있음
•
선형성만이 인과성을 보존하는 유일한 방법은 아님
◦
성능 손해를 유발하지 않고 인과적 일관성을 만족 시킬 수 있음
•
선형성이 중요한게 아니라 인과적 일관성이 중요
2.1.3. 인과적 의존성 담기
•
비선형 시스템이 인과적 일관성을 유지할 수 있는지에 대한 아이디어
◦
인과성 유지를 위해서는 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 함 (부분 순서)
◦
동시에 실행되는 연산은 어떤 순서로든 처리될 수 있지만 한 연산이 다른 연산보다 먼저 실행됐다면 모든 복제 서버는 그 순서로 처리돼야 함
◦
복제 서버가 연산을 처리할 때 인과적으로 앞서는 모든 연산이 이미 처리됐다고 보장할 수 있어야 함
•
인과적 의존성을 결정하려면 시스템에 있는 노드에 관한 지식을 기술한 방법이 필요
◦
어떤 연산이 다른 연산보다 먼저 실행됐는지 결정 필요
•
데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야함
2.2. 일련번호 순서화
•
인과성은 중요한 이론적 개념이나, 모든 인과적 의존성을 추적하는 것은 실용적이지 않음
◦
읽은 데이터를 모두 명시적으로 추적하는 것은 오버헤드가 큼
•
대안
◦
일련번호, 타임스탬프(논리적 시계) 활용
•
특징
◦
크기가 작음
◦
전체 순서 제공
◦
인과성에 일관적인 전체 순서대로 일련번호 생성 가능
•
예) 단일 리더 복제 - 복제 로그
◦
리더는 연산마다 카운터를 증가시킴
◦
복제 로그의 연산에 단조 증가 일련번호 할당
◦
팔로워가 복제 로그에 나오는 순서대로 쓰기를 적용하면 팔로워는 언제나 인과성이 일관적
2.2.1. 비인과적 일련번호 생성기
•
단일 리더가 없는 경우 (다중 리더, 리더 없는 데이터베이스, 데이터 베이스 파티셔닝)
◦
일련번호 생성이 힘듬. 여러가지 옵션
◦
여러가지 옵션이 존재
◦
그러나, 생성된 일련번호가 인과성에 일관적이지 않음 (비일관성)
•
옵션
◦
각 노드마다 고유의 일련번호 집합 생성 → 노드마다 초당 연산수가 다를 수 있음
◦
각 연산에 일 기준 시계(물리적 시계)에서 얻은 타임스탬프 붙임 → 시계 스큐에 종속적 (인과적으로 나중에 실행된 연산이 더 낮은 타임스태프 배정)
◦
일련번호 블록 미리 할당 → 어떤 블록으로 받을지 모름. 인과성 없음
2.2.2. 램포트 타임스탬프
•
인과성에 일관적인 일련번호 생성하는 방법
◦
램포트 타임스탬프
•
핵심 아이디어
◦
모든 노드와 모든 클라이언트가 지금까지 본 카운터 값중 최대값을 추적하고, 모든 요청에 그 최대값 포함
◦
노드가 자신의 카운터 값보다 큰 최대 카운터를 가진 요청이나 응답을 받으면 바로 자신의 카운터를 그 최대값으로 증가
•
특징
◦
타임스탬프 데이터 포맷
▪
(카운터, 노드ID)
◦
각 노드는 처리한 연산 개수를 카운터로 유지
◦
전체 순서화 제공
▪
두 타임스탬프가 있으면 카운터가 큰 것이 타임스탬프가 큼
▪
카운터 값이 같으면 노드 ID가 큰것이 타임스탬프가 큼
•
예시
2.2.3. 타임스탬프 순서화로 충분하지 않다
•
램포트 타임스탬프가 인과성에 일관적인 연산의 전체 순서를 정의하나, 분산 시스템의 다양한 문제 해결에 충분치 않음
•
사용자명에 대한 유일성 제약 조건 등을 구현하려면 연산의 전체 순서가 있는 것으로 충분하지 않음
•
언제 그 순서가 확정되는지도 알아야함 (언제 전체 순서가 확정되는지 알아야 함)
◦
예) 성공/실패 여부를 당장 결정해야하는 경우
▪
다른 어떤 노드도 동시에 더 낮은 타임스탬프를 가지고 동일한 사용자명으로 계정 생성중이아니라고 확신하려면 다른 모든 노드가 무엇을 하고 있는지 확인 필요
•
연산의 전체 순서는 모든 연산을 모은 후에 드러남
•
언제 전체 순서가 확정되는지 알아야한다는 아이디어 → 전체 순서 브로드캐스트
2.3. 전체 순서 브로드캐스트
2.3.1. 전체 순서 브로드캐스트
•
분산 시스템에서 모든 노드의 연산 전체 순서를 동일하도록 합의하기 까다로움
•
단일 리더 복제
◦
연산의 전체 순서 정하기 쉬움
•
문제
◦
처리량이 단일 리더가 처리할 수 있는 수준을 넘어설 때, 시스템을 어떻게 확장할 것인가?
◦
리더가 장애가 났을 때, 장애를 어떻게 복구할 것인가? → 전체 순서 브로드캐스트
•
전체 순서 브로드캐스트 / 원자적 브로드캐스트
◦
노드 사이에 메세지를 교환하는 프로토콜
◦
안전성 속성 만족 필요
▪
신뢰성 있는 전달
•
어떠한 메세지도 손실되지 않는다. 메세지가 한 노드에 전달되면 모든 노드에도 전달된다.
▪
전체 순서가 정해진 전달
•
메세지는 모든 노드에 같은 순서로 전달된다.
•
노드나 네트워크에 결함이 있더라도 신뢰성과 순서화 속성이 항상 만족됨을 보장해야함
◦
네트워크가 끊킨 경우 메세지 전달 불가하나, 알고리즘이 지속적인 재시도 진행
◦
네트워크 복구시, 메세지가 올바른 순서에 따라 전달 될 수 있게 함
2.3.2. 전체 순서 브로드캐스트 사용하기
•
주키퍼, etcd 는 전체 순서 브로드캐스트를 실제 구현
•
전체 순서 브로드캐스트는 데이터베이스 복제에 딱 필요한 것
•
상태 기계 복제
◦
모든 메세지가 데이터베이스에 쓰기를 나타내고, 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태 유지
•
직렬성 트랜잭션 구현에도 사용될 수 있음
◦
스토어 프로시저
▪
모든 노드가 메세지들을 같은 순서로 처리
▪
데이터베이스 파티션과 복제본은 서로 일관적인 상태 유지
•
전체 순서 브로드캐스트의 특징
◦
메세지가 전달되는 시점에 그 순서가 고정된다는 것
◦
로그를 만드는 방법중 하나 (복제로그, 트랜잭션 로그, 쓰기전 로그)
◦
펜싱토큰을 제공하는 잠금 서비스 구현에도 유용
▪
잠금을 획득하는 모든 요청은 메세지로 로그에 추가되고, 모든 메세지들은 로그에 나타난 순서대로 일련번호가 붙음
2.3.3. 전체 순서 브로드캐스트를 사용해 선형성 저장소 구현하기
•
선형성시스템과 전체 순서 브로드 캐스트
◦
둘다, 전체 순서가 있음
•
전체 순서 브로드캐스트는 비동기식
◦
메세지를 고정된 순서로 신뢰성 있게 전달되게 보장
◦
언제 메시지가 전달 될 지는 보장되지 않음(비동기식) → 어떤 수신자는 다른 것들보다 뒤처질 수 있음
•
선형성은 최신성 보장
◦
읽기가 최근 쓰여진 값을 보는게 보장
•
전체 순서 브로드캐스트 구현이 있다면 이를 기반으로 선형성 저장소 만들 수 있음
◦
예) 유저 계정의 유저명 유일성 보장 - 사용 가능한 모든 사용자명마다 원자적 compare-and-set 연산이 구현된 선형성 저장소
▪
모든 레지스터는 초기에 null 값을 가짐
▪
사용자가 사용자명을 생성하길 원할 때 해당 사용자명에 해당하는 레지스터에 compare-and-set 연산을 실행해 이전 값이 null이라는 조건 하에 연산 수행
◦
전체 순서 브로드캐스트를 추가 전용 로그를 사용해 선형성 compare-and-set 연산 구현
1.
메세지를 로그에 추가해서 점유하기 원하는 사용자명을 시험적으로 가리킴
2.
로그를 읽고, 추가한 메세지가 되돌아오기를 기다림
3.
원하는 사용자명을 점유하려고 하는 메세지가 있는지 확인. 자신의 메세지라면 성공. 아니라면 어보트
•
로그 항목은 모든 노드에 같은 순서로 전달되므로, 여러개의 쓰기가 동시 실행시 모든 노드가 어떤 쓰기가 먼저 실행된 것인지 동의함
•
충돌하는 쓰기 중 첫번째 것을 승자로 택하고, 나머지를 어보트 → 모든 노드는 쓰기가 커밋/어보트 되는지에 동의함
•
위 절차는 선형성 쓰기는 보장하나 선형성 읽기는 보장하지 않음
◦
로그로부터 비동기로 갱신되는 저장소를 읽으면 오래된 값이 읽힐 수 있음
2.3.4. 선형성 저장소를 사용해 전체 순서 브로드캐스트 구현하기
•
정수를 저장하고 원자적 increment-and-get 연산이 지원되는 선형성 레지스터가 있다고 가정
•
전체 순서 브로드캐스트를 통해 보내고 싶은 모든 메시지에 대해 선형성 정수로 increment-and-get 연산을 수행하고, 레지스터로 얻은 값을 일련번호로 메시지에 붙임
•
그 후, 메세지를 모든 노드에 보낼 수 있고 수신자는 일련번호 순서대로 메세지를 전달
•
전체 순서 브로드캐스트와 타임스탬프의 순서화의 차이
◦
선형성 레지스터를 증가시켜 얻은 숫자들은 틈이 없는 순열을 형성함
◦
따라서, 어떤 노드가 메세지 4를 전달하고 일련번호 6인 메세지를 받았다면 메세지 6을 전달하기전에 메세지 5를 기다려야함
◦
램포드 타임스탬프는 그렇지 않음
•
선형성 compare-and-set(또는 increment-and-get) 레지스터와 전체 순서 브로드캐스트는 둘다 합의와 동등하다고 증명할 수 있음
3. 분산 트랜잭션과 합의
3.1. 합의
•
합의의 목적
◦
여러 노드들이 뭔가에 동의하게 만드는 것
•
합의 예시
◦
리더 선출
◦
원자적 커밋
▪
여러 노드 / 파티션에 걸친 트랜잭션. 어떤 노드는 성공 하고 어떤 노드는 실패하는 경우
•
FLP 결과 (합의 불가능성)
◦
어떤 노드가 죽을 위험에 있다면 항상 합의에 이를 수 있는 알고리즘은 없다는 것을 증명
•
2PC 알고리즘 (2단계 커밋)
3.2. 원자적 커밋과 2단계 커밋 (2PC)
3.2.1. 단일 노드에서 분산 원자적 커밋으로
•
단일 노드
◦
트랜잭션 커밋은 데이터가 디스크에 지속성 있게 쓰여지는 순서에 결정적으로 의존함
◦
데이터가 먼저고 (쓰기전 로그 등) 커밋 레코드가 그다음임
◦
커밋 레코드 쓰기가 마치는 시점에 커밋 / 어보트 결정
◦
커밋을 원자적으로 만들어 주는 것은 단일 장치 (특정한 하나의 노드에 부착된 하나의 특정 디스크 드라이브의 컨트롤러)
•
다중 노드
◦
원자성 보장이 어려움
◦
어떤 노드는 커밋하고 어떤 노드는 어보트 → 일관성 저해
3.2.2. 2단계 커밋 소개
•
정의
◦
여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋 되거나, 모든 노드가 어보트되도록 보장하는 알고리즘
•
코디네이터 (트랜잭션 관리자)
◦
단일 노드 트랜잭션에 존재하지 않는 새로운 컴포넌트
◦
형태
▪
애플리케이션 프로세스 내 라이브러리 형태 (자바 EE 컨테이너)
▪
분리된 프로세스, 서비스 (JOTM, BTM, MSDTC, 나라야나)
•
플로우
◦
데이터베이스 노드: 참여자 (participant)
◦
애플리케이션이 커밋할 준비가 되면, 코디네이터가 1단계 시작
◦
각 노드에 준비 요청을 보내서 커밋할 수 있는지르 물어봄. 그 후 코디네이터가 응답을 추적
▪
모든 참여자가 커밋할 준비가 됨 → 코디네이터는 2단계 커밋 요청을 보내고, 커밋이 실제로 일어남
▪
참여자 중 누구라도 아니오를 응답 → 코디네이터는 2단계에서 모든 노드에 어보트 요청을 보냄
◦
예시
3.2.3. 약속에 관한 시스템
2단계 커밋 프로세스 상세 설명
1.
애플리케이션은 분산 트랜잭션을 시작하기 원할때 코디네이터에게 트랜잭션 ID를 요청. 트랜잭션 ID는 전역으로 유일
2.
애플리케이션은 각 참여자에서 단일 노드 트랜잭션을 시작하고, 단일 노드 트랜잭션에 전역으로 유일한 트랜잭션 ID를 붙임
•
모든 읽기와 쓰기는 단일 노드 트랜잭션 중 하나로 실행됨
•
이 단계에서 잘못되면 코디네이터나 참여자가 어보트 가능
3.
애플리케이션이 커밋할 준비가 되면, 코디네이터는 모든 참여자에게 전역 트랜잭션 ID로 태깅된 준비 요청을 보낸다. 요청 중 실패하거나 타임아웃이 될 경우, 코디네이터는 참여자 모두에게 어보트 요청
4.
참여자가 준비 요청을 받으면, 트랜잭션을 커밋할 수 있는지 확인
•
트랜잭션 데이터를 쓰는 것(죽거나, 전원 장애, 디스크 공간 부족)과 충돌, 제약 조건 위반 등 확인
•
코디네이터에게 “네” 라고 응답함으로써 노드에 요청이 있으면 트랜잭션을 오류 없이 커밋할 것이라고 약속
•
어보트 권리를 포기하지만 실제 커밋은 진행 X
5.
코디네이터가 모든 준비 요청에 대해 응답을 받았을 때, 커밋/어보트 최종 결정
•
커밋 포인트
◦
코디네이터가 추후 죽는 경우에 어떻게 결정했는지를 알 수있도록 그 결정을 디스크에 있는 트랜잭션 로그에 기록
6.
코디네이터 결정이 디스크에 쓰여지면 모든 참여자에게 커밋이나 어보트 요청이 전송됨. 요청 실패/타임 아웃 시 코디네이터는 성공할때까지 영원히 재시도
•
2PC의 원자성 보장
◦
코디네이터가 한번 결정하면, 그 결정은 변경할 수 있음.
3.2.4. 코디네이터 장애
•
참여자가 준비 요청을 받고 “네”에 투표를 한 경우, 일방적으로 어보트 불가
•
코디네이터가 죽거나, 위 시점에서 네트워크 장에시, 참여자는 대기할 수 밖에 없음
◦
트랜잭션 상태: 의심스럽다 (in doubt), 불확실하다 (uncertain)
•
2PC가 완료할 수 있는 유일한 방법
◦
코디네이터가 복구되기를 기다리는 것
◦
코디네이터가 참여자들에게 커밋/어보트 요청 전 디스크에 트랜잭션 로그에 자신의 결정을 기록하는 이유
◦
복구 될때, 트랜잭션 로그를 읽어 의심스러운 트랜잭션 상태를 결정함
◦
코디네이터 로그에 커밋 레코드가 없는 트랜잭션은 어보트 됨
•
예시
3.2.5. 3단계 커밋
•
2단계 커밋의 한계
◦
블로킹 원자적 커밋 프로토콜
◦
코디네이터가 복구하기를 기다리느라 멈출 수 있음
•
3단계 커밋
◦
2단계 커밋의 대안
◦
지연에 제한 있는 네트워크와 응답시간에 제한이 있는 노드를 가정
◦
기약 없는 네트워크 지연과 프로세스 중단이 있는 대부분의 실용 시스템에서 3PC는 원자성 보장 불가
•
논 블로킹 원자적 커밋
◦
완벽한 장개 감지기. 노드가 죽었는지 아닌지 구별 할 수 있는 신뢰성 있는 매커니즘 필요
◦
기약 없는 지연이 있는 네트워크에서 타임아웃은 신뢰성 있는 장애 감지기가 아님 → 2PC가 실제로 계속 쓰이는 이유
3.3. 현실의 분산 트랜잭션
•
2PC
◦
(pros) 안정성 보장
◦
(cons) 운영의 문제. 성능 저하
•
분산 트랜잭션
◦
성능 손해를 위반함
•
분산 트랜잭션의 종류
◦
데이터베이스 내부 분산 트랜잭션
▪
데이터베이스 노드 사이의 내부 트랜잭션
▪
다른 시스템과 호환될 필요가 없으므로 아무 프로토콜이나 쓸 수있고 특정 기술에 특화된 최적화 사용 가능
◦
이종 분산 트랜잭션
▪
서로 다른 벤더의 데이터베이스 / 비데이터베이스(브로커) 간의 분산 트랜잭션
▪
이번 챕터에서 우리가 살펴볼 트랜잭션
3.3.1. 정확히 한번 메세지 처리
•
메시지 큐와 데이터베이스를 함께 쓰는 경우
•
메세지 전달
◦
메세지 처리하는 트랜잭션이 커밋 성공시에만 처리된것으로 확인 받을 수 있음
◦
메세지 확인과 데이터베이스 쓰기를 단일 트랜잭션에서 원자적으로 커밋
•
한계
◦
트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능
◦
예시
▪
메시지 처리 부수효과: 이메일 전송 (2단계 커밋 지원 X)
▪
메세지 처리 실패 후 재시도 시, 이메일 2번 전송 가능
3.3.2. XA 트랜잭션
•
X/Open XA (eXtended Architecture)
◦
이종 기술에 걸친 2단계 커밋 구현 표준
◦
트랜잭션 코디네이터와 연결되는 인터페이스를 제공하는 C로 된 API
•
XA는 애플리케이션이 네트워크 드라이브나 클라이언트 라이브러리를 사용해 참여자 데이터베이스나 메시징 서비스와 통신한다고 가정
◦
트라이버가 XA를 지원한다는 것 = 연산이 분산 트랜잭션의 일부가 돼야 하는지 알아내기 위해 XA API를 호출한다는 뜻
◦
드라이버는 데이터베이스 서버로 필요한 정보를 보냄.
◦
드라이버는 코디네이터가 참여자에게 준비, 커밋,. 어보트를 요청할 수 있는 콜백 제공
•
트랜잭션 코디네이터는 XA API를 구현
◦
현실에서는 독립된 서비스가 아니라 프로스세스에 로딩되는 단순한 라이브러리
◦
트랜잭션 참여자를 추적, 참여자들에게 (드라이버로 가는 콜백을 통해) 준비 요청을 보낸후, 응답 수집, 각 트랜잭션에 대한 커밋/어보트 결정을 추적하기 위해 로컬 디스크 로그 사용
•
애플리케이션 프로세스가 죽거나 애플리케이션이 실행중인 장비가 죽으면 코디네이터도 함께 사랒림
◦
코디네이터 로그는 애플리케이션 서버 로컬 디스크에 존재
3.3.3. 의심스러운 상태에 있는 동안 잠금을 유지하는 문제
•
트랜잭션이 의심스로운 상태에 빠지는 것에 신경쓰는 이유?
◦
잠금 이슈
•
데이터베이스는 트랜잭션 커밋/어보트 전까지 잠금 해제 불가
•
2단계 커밋 트랜잭션은 의심스러운 상태 내내 잠금 홀딩 됨 → 해소될때까지 성능 이슈
3.3.4. 코디네이터 장애에서 복구하기
•
코디네이터 죽고 재시작 시, 의심스러운 트랜잭션 해소 필요
•
현실에서는 고아 (의심스러운) 트랜잭션 발생 가능
◦
트랜잭선 로그 손실, 오염
◦
트랜잭션 자동 해소가 안됨
•
방법
◦
관리자 수동 커밋/롤백 결정
•
경험적 결정
◦
참여자가 코디네이터로부터 확정적 결정을 얻지 않고 으심스러운 트랜잭션을 어보트하거나 커밋할지를 일방적으로 결정
◦
2단계 커밋 약속 체계를 위반하므로 원자성을 깰 수 있음
3.3.5. 분산 트랜잭션의 제약
•
XA 트랜잭션
◦
여러 데이터 시스템이 일관성을 유지하게 하는 문제를 해결하나, 운영상의 문제도 있음
◦
트랜잭션 코디네이터 자체가 (트랜잭션 결과를 저장할 수 있는) 일종의 데이터베이스 여야함
◦
다른 중요한 데이터베이스와 동일하게 신경써서 접근해야함
•
이슈 예시
◦
코디네이터 - 단일 장비 실행시 SPOF 가 됨
◦
여러 서버 사이드 애플리케이션은 모든 영속적인 상태를 DB에 저장하고 상태 비저장 모드로 개발됨
▪
애플리케이션 서버 추가 / 제거 이점이 있음
▪
코디네이터가 애플리케이션 일부가 되면, 서버는 더이상 상태 비저장이 아님
◦
XA는 광범위한 시스템과 호환돼야 하므로 최소 공통 분모가 될 필요가 있음
▪
여러 시스템에 걸친 교착 상태 감지 불가
▪
SSI와 함께 동작하지 않음 (지원하려면 여러 시스템에 걸친 충돌 식별 프로토콜 필요)
◦
분산 트랜잭션은 장애를 증폭시키는 경향이 있음. 내결함성 시스템 구축에 위배
▪
2PC 성공적으로 커밋하려면 모든 참여자가 응답 필요
▪
일부가 고장나면 트랜잭션도 실패
▪
cf) 데이터베이스 내부 트랜잭션는 제한이 크지 않음. 분산 버전 SSI 사용 가능
3.4. 내결함성을 지닌 합의
3.4.1. 합의문제의 형식화와 형식적 모델
•
합의 문제의 형식화
◦
하나 또는 그 이상의 노드들이 값을 제안할 수 있음
◦
합의 알고리즘이 그 값 중 하나를 결정함
•
합의 알고리즘 속성 (형식적 모델)
◦
균일한 동의: 어떤 두 노드도 다르게 결정하지 않는다. (모두 같은 결과로 저장)
◦
무결성: 어떤 노드도 두번 결정하지 않는다. (한번 결정 시, 변경 불가)
◦
유효성: 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것 (뻔한 해결책 배제)
◦
종료: 죽지 않은 모든 노드는 결국 어떤 값을 결정 (내결함성)
3.4.2. 합의 알고리즘과 전체 순서 브로드캐스트
•
내결함성을 지닌 합의 알고리즘
◦
뷰스템프 복제, 팍소스, 라프트, 잽
◦
합의 알고리즘의 형식적 모델(동의, 무결성, 유효성, 종료)을 직접 사용하지 않음
◦
값의 순차열에 대해 결정하여 전체 순서 브로드캐스트 알고리즘을 만듬
•
전체 순서 브로드캐스트
◦
모든 노드에게 메세지가 정확히 한번, 같은 순서로 전달 돼야 함
◦
합의를 여러번 반복하는 것과 동일 (각 합의 결정 = 하나의 메세지 전달)
•
속성
◦
합의의 동의 속성 → 모든 노드는 같은 메세지를 같은 순서로 전달하도록 결정
◦
무결정 속성 → 메세지 중복 X
◦
유효성 속성 → 메세지는 오염되지 않고 조작되지 않음
◦
종료 속성 → 메세지 손실 X
3.4.3. 단일 리더 복제와 합의
단일 리더 복제는 합의를 어떻게 하나?
•
수동으로 리더 선택
◦
독재자 방식의 합의 알고리즘
◦
사람의 개입이 필요 하므로 합의의 종료 속성 만족 X
•
자동 리더 선출 및 장애 복구
◦
내결함성을 지닌 전체 순서 브로드캐스트와 유사. 합의 해결과도 비슷
◦
문제점
▪
스플릿 브레인 문제
▪
모든 노드들이 누가 리더인지 동의해야함
▪
리더를 선출하려면 합의가 필요
3.4.4. 에포크 번호 붙이기와 정족수
•
합의 알고리즘
◦
앞서 설명한 합의 프로토콜들은 리더를 사용하나, 리더가 유일함을 보장하지 않음
◦
그들은 더 약한 보장을 함
•
프로토콜 - 에포크 번호를 정의하고 각 에포크 내에서 리더가 유일하다고 보장
◦
팍소스 - 투표 번호
◦
뷰스템프 복제 - 뷰 번호
◦
라프트 - 텀 번호
•
리더 선출 투표
◦
선출은 에포크 번호를 증가 시킴 → 에포크 번호는 전체 순서가 있고 단조 증가
◦
두가지 다른 에포크에 있는 두가지 다른 리더 충돌 시, 에포크 번호가 높은 리더가 이김
•
노드의 정속수 투표
◦
리더 결정 허용 시 충돌되는 결정을 할지도 모르는 에포크가 높은 다른 리더가 있는지 확인 필요
◦
리더는 내리려고 하는 모든 결정에 대해 제안된 값을 다른 노드에게 보내서, 노드의 정족수가 그 제안을 찬성한다고 응답하기를 기다려야함
◦
정족수는 전형적으로 노드 과반수로 구성
◦
노드는 에포크 번호가 더 높은 리더를 알지 못할 때만 제안에 찬성하는 투표를 함
•
두번의 투표
1.
리더 선출을 위한 투표
2.
리더의 제안에 투표
◦
두번의 투표 하는 정족수가 겹쳐야함
◦
제안에 대한 투표가 성공한다면, 그것에 투표한 노드중 최소 하나는 가장 최근에 리더 선출에도 참여했어야 함
◦
제안에 대한 투표를 할 때, 에포크 번호가 더 큰 것이 있다고 밝혀 지지 않았다면, 현재 리더는 에포크 번호가 더 높은 리더 선출이 발생하지 않았다고 결론을 내릴 수 있음 → 리더십 유지 가능
•
투표과정이 2PC와 유사해보임
◦
차이점
▪
2PC에서 코디네이터는 선출되지 않는다는 것
▪
2PC는 모든 참여자로부터 “네” 투표가 필요하지만 내결함성을 지닌 합의 알고리즘은 노드의 과반수로부터 투푤르 받으면 된다는 점
▪
합의 알고리즘은 안전성 속성을 항상 만족
•
새로운 리더가 선출된 후 노드를 일관적인 상태로 만들어주는 복구 과정을 정의
•
합의 알고리즘의 정확성과 내결함성 핵심
3.4.5. 합의의 제약
•
합의 알고리즘
◦
불확실한 시스템에 구체적인 안전성 속성 (동의, 무결성, 유효성, 종료)을 가져옴
◦
내결함성 유지 (종료 속성, 노드의 과반수가 동작하고 통신할 수있는 한 진행 가능)
◦
전체 순서 브로드캐스트를 제공
◦
내결함성 있는 방식으로 선형성 원자적 연산 구현
•
합의 알고리즘의 제약
◦
제안이 결정되기전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제
▪
비동기식 복제 설정 시, 커밋된 데이터는 장애 복구 시 잠재적으로 손실 가능
◦
합의 시스템은 항상 엄격한 과반수가 동작하길 요구
▪
노드 1대가 장애를 견디려면 최소한 3대의 노드 필요
▪
노드 2대가 … 최소한 5대 노드 필요
◦
대부분의 합의 알고리즘은 투표에 참여하는 노드 집합이 고정되어 있다고 가정
▪
콜러스터에 노드 단순히 추가 / 제거 불가
▪
합의 알고리즘의 동적 멤버십 확장은 이해하기 어려움
◦
합의 시스템은 장애 노드 감지를 위해 타임아웃에 의존
▪
네트워크 문제 → 장애 발생 오판단 → 리더 선출에 많은 시간 소요 → 성능 저하
◦
네트워크 문제에 민감
3.5. 멤버십과 코디네이션 서비스
3.5.1. 주키퍼와 etcd
•
메모리 안에 들어올 수 있는 작은 양의 데이터를 보관하록 설계
◦
(지속성을 위해 디스크에 쓰긴함)
•
이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제
◦
전체 순서 브로드캐스트는 데이터베이스 복제에 필요한 것
•
개별 메세지가 데이터베이스에 쓰기를 나타낸다면, 같은 쓰기를 같은 순서로 적용함으로써 복제본들은 일관성을 유지
•
주키퍼
◦
구글의 처비(Chubby) 잠금 서비스를 모델로 삼아 다양한 기능 집합 구현
◦
선형성 원자적 연산
▪
원자적 compare-and-set 연산을 사용해 잠금 구현
◦
연산의 전체 순서화
▪
펜싱 토큰
◦
장애 감지
▪
단명 노드
◦
변경 알림
3.5.2. 작업을 노드에 할당하기
•
주키퍼/처비 모델이 잘 동작하는 예
1.
여러개의 프로세스나 서비스가 있고, 그 중 하나가 리더나 주 구성요소로 선택돼야 할 때
•
리더에 장애가 나면 다른 노드중 하나가 넘겨받아야함
2.
파티셔닝된 자원이 있고, 어떤 파티션을 어느 노드에 할당해야할지 결정하는 경우
•
매우 많은 노드에서 과반수 투표는 비효율적
◦
주키퍼는 고정된 수의 노드에서 실행되고, 이 노드들 사이에서 과반수 투표를 수행하면서 많아질 수 있는 클라이언트를 지원
◦
노드들을 코디네이트하는 작업(합의, 연산 순서화, 장애 감지)의 일부를 외부 서비스에 위탁하는 방법 제공
3.5.3. 서비스 찾기
•
특정 서비스에 연결하려면 어떤 IP 주소로 접속해야하는지 알아내는 용도로 사용됨
•
합의가 필요하지 않음
◦
DNS - 서비스 이름으로 IP 주소를 찾는 전통적인 방법
▪
좋은 성능과 가용성 달성을 위해 다층 캐시 사용
▪
DNS에서 읽는 것은 선형적이지 않고, 질의 결과가 조금 뒤쳐지더라도 문제되지 않음
▪
DNS는 신뢰성 있게 사용 가능하고 네트워크 끊킴에 견고하다는게 더중요
3.5.4. 멤버십 서비스
•
클러스터에서 어떤 노드가 현재 활성화된 살아있는 멤버인지 결정
•
장애감지와 합의를 연결 → 어떤 노드가 살아있고 죽었는지 동의할 수 있음
•
합의는 어떤 노드가 현재 멤버십을 구성하는지 동의하는데 매우 유용
4. 정리
•
일관성 모델
◦
선형성 모델
▪
복제된 데이터가 오직 하나의 복사본만 있는것처럼 보이게 하고, 데이터에 대한 모든 연산을 원자적으로 만드는 것
▪
이해하기 쉬우나, 느림
▪
전체 순서
◦
인과성 모델
▪
선형성 모델에 비해 더 약한 일관성 모델 제공
▪
부분 순서
•
인과적 순서를 담아내더라도 어떤것은 이 방법으로 구현할 수 없음
◦
타임스탬프 순서화로는 충분하지 않음
◦
예) 유일한 사용자 명
▪
한 노드가 등록을 받아들이려면, 다른 노드가 동시에 동일한 사용자명으로 등록하는 과정에 있지 않다는 것을 알아야함 → 합의로 이어짐
•
합의
◦
결정된 것에 모든 노드가 동의하고 결정을 되돌릴 수없는 방식으로 무언가를 결정하는 것
◦
광범위한 문제가 합의로 환원될 수 있음
▪
선형성 comapre-and-set 레지스터
▪
원자적 트랜잭션 커밋
▪
전체 순서 브로드캐스트
▪
잠금과 임차권
▪
멤버십/코디네이터 서비스
▪
유일성 제약 조건
◦
위 문제들을 결정할 수 있는 능력을 한 노드에만 준다면 간단
▪
그러나, 단일 리더 장애 발생 시, 내결함성 크게 저하
▪
해결 방법
1.
리더가 복구될때 까지 대기. (종료 속성을 만족하지 않으므로 합의 완전히 해결 X)
•
XA 트랜잭션 코디네이터 방식
2.
수동으로 새로운 노드 선택 후 장애 복구
3.
자동으로 새 리더 선택 알고리즘
◦
코디네이션 서비스
▪
합의, 장애감지, 멤버십 서비스를 위탁하는 중요한 역할 수행
[스터디]
Harry
일관성 모델의 종류에 대해 비교 설명하시오
CAP 정리란?
램포트 타임스탬프란?
전체 순서 브로드캐스트란?
2단계 커밋이란?
Matthew
선형성이란 무엇이며 어떠한 구현 원칙을 가지고 있나요?
선형성과 인과성을 순서의 측면에서 비교 설명하세요
비선형성 시스템에서 인과성을 유지하기 위한 방법은 대략적으로 어떤 것이 있으며 어떠한 문제가 있나요?