데이터 중심 어플리케이션 설계 - 9장. 일관성과 합의

개인적으로 9장 내용은 많으면서 쉽지 않기도 했고, 실제 라이브러리나 DB의 구현 내용을 살펴보는 것들이라 당장에 써먹을 만한 점들이나 적합한 사례들을 찾으면서 공부할 수 없어서 다소 어렵게 느껴졌다. (책 내용이 다소 미괄적인 것도 한 몫 했다)

---

학습 목표 : 내결함성을 지닌 분산 시스템을 구축하는 데 쓰이는 알고리즘과 프로토콜의 몇 가지 예를 알아보고 결함을 견뎌낼 방법을 찾는다. (분산 시스템에서 제공될 수 있는 보장과 추상화의 범위를 알아보고 합의와 합의 관련 문제를 해결하는 알고리즘을 살핀다.)

일관성 보장

복제 DB는 대부분 최소한 최종적 일관성을 제공.  (= DB에 쓰기를 멈추고 불특정 시간 동안 기다리면 결국 모든 읽기 요청이 같은 값을 반환한다)
→ 불일치는 일시적, 결국 스스로 해소. but 매우 약한 보장.  
→ 최종적 일관성은 시스템에 결함이 있거나 동시성이 높을 때 분명히 드러난다. 

9장에서는 강한 보장을 제공하는 일관성 모델을 살펴본다. 이는 분명한 성능이나 내결함성에 대한 트레이드오프가 존재한다. 

선형성

데이터베이스에 복제본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것.

→ 최신성 보장 

선형성은 원자적 일관성, 강한 일관성, 즉각 일관성, 외부 일관성이라고도 한다. 

↔ 비선형성 시스템의 예

시스템에 선형성을 부여하는 것은 무엇인가?

선형성의 요구사항 : 연산 표시를 모은 선들이 항상 시간순으로 진행되어야 하고 결코 뒤로 가서는 안 된다. 

모든 요청과 응답 시점을 기록하고 그것들이 유효한 순차 순서로 배열되었는지 확인해보면 시스템의 동작이 선형적인지 확인이 가능하다. 

선형성 vs 직렬성

직렬성 

• 모든 트랜잭션이 여러 객체를 읽고 쓸 수 있는 상황에서의 트랜잭션들의 격리 속성
• 트랜잭션들이 어떤 순서에 따라 실행되는 것처럼 동작하도록 보장
• 그 순서가 실제 트랜잭션 실행 순서와 달라도 상관 없다

선형성

• 레지스터(개별 객체)에 실행되는 읽기와 쓰기에 대한 최신성 보장
• 선형성은 연산을 트랜잭션으로 묶지 않아서 충돌 구체화같은 부가적인 수단 없으면 쓰기 스큐를 막지 못한다. 

데이터베이스는 직렬성과 선형성을 모두 제공할 수도 있다 → 엄격한 직렬성 / 강한 단일 복사본 직렬성

• 2단계 잠금이나 실제적인 직렬 실행을 기반으로 한 직렬성 구형은 보통 선형적
• 직렬성 스냅숏 격리는 선형적이지 않다. (일관된 스냅숏 → 스냅숏보다 나중에 실행된 쓰기를 포함하지 않으므로 스냅숏에서 읽으면 선형적이지 않다)

선형성에 기대기

선형성이 유용한 환경은 무엇일까

잠금과 리더 선출

단일 리더 복제를 사용하는 시스템에서는 스플릿 브레인이 발생하지 않도록 보장이 필요.

리더를 선출하는 방법 : 잠금을 사용

• 모든 노드가 시작할 때 잠금 획득을 시도하고 성공한 노드가 리더가 됨
• 이 잠금은 선형적이어야 함. ( = 모든 노드는 어느 노드가 잠금을 소유하는지에 동의해야 한다)
• 아파치 주키퍼, etcd와 같은 코디네이션 서비스가 종종 사용된다. → 합의 알고리즘을 사용해 선형성 연산을 내결함성이 있는 방식으로 구현

제약 조건과 유일성 보장

유일성 제약 조건을 강제하기 위해서는 선형성이 필요 → 잠금과 유사

ex) 사용자가 서비스에 가입할 때 그들이 선택한 사용자명에 잠금을 획득하는 것.

채널 간 타이밍 의존성

선형성 위반은 시스템에 부가적인 통신 채널이 있기 때문에 발견될 수 있다.  ex) 이미지 크기 변경 모듈 내에서 메시지 큐를 이용하는 방법. 

위 상황에서 파일 저장 시스템이 선형적이면 이 시스템은 잘 동작하지만 선형적이지 않다면 경쟁 조건의 위험이 있다. ∵ 통신 채널이 두 개(파일 저장소, 메시지 큐)이기 때문.

경쟁 조건을 회피하는 방법 중에 가장 단순한 것이 선형성. 부가적인 통신 채널을 제어하면 복잡성이 추가되지만 대안적인 방법을 사용할 수 있다. 

선형성 시스템 구현하기

가장 쉬운 방법 : 실제로 데이터 복사본 하나만 사용 → 내결함성이 없음.

복제의 다양한 방법과 선형성

• 단일 리더 복제 (선형성의 가능성 존재)
  • 리더는 쓰기에 사용되는 데이터의 주 복사본을 갖고 있음. 팔로워는 데이터이 백업 복사본을 보관.
  • 리더나 동기식으로 갱신된 팔로워에서 실행된 읽기는 선형적일 수 있음.
  • 스냅숏 격리를 사용하거나 동시성 버그가 있는 경우 선형적이 아닐 수 있음.
• 합의 알고리즘 (선형적)
  • 단일 리더 복제를 닮음
  • 스플릿 브레인과 복제본이 뒤쳐지는 문제를 막을 수단이 존재
  • 주키퍼와 etcd가 이렇게 동작
• 다중 리더 복제 (비선형적)
  • 여러 노드에서 동시 쓰기 처리 + 쓰여진 내용을 비동기로 다른 노드에 복제
  • 충돌 해소가 필요한 충돌 쓰기를 만들 수 있음. ∵ 단일 복사본만 존재하는 게 아니라서 발생
• 리더 없는 복제 (아마도 비선형적)
  • LWW (최종 쓰기 승리) 방식은 거의 확실히 비선형적 → 시계 스큐 때문에 이벤트의 실제 순서와 일치하리라고 보장할 수 없다.
  • 느슨한 정족수도 선형성의 가능성을 해침
  • 엄격한 정족수도 비선형적으로 동작할 수 있음. 

선형성과 정족수

엄격한 정족수를 사용해도 선형적이지 않은 예시

다이나모 스타일 정족수에서 성능을 버리고 선형성을 선택하는 방법 :

1. 읽기를 실행하는 클라이언트는 결과 반환 전에 읽기 복구를 동기식으로 수행
2. 쓰기를 실행하는 클라이언트는 쓰기 요청 전에 노드들의 정족수로부터 최신 상태를 읽어옴

→ 선형성 읽기, 쓰기 연산만 구현 가능, compare-and-set은 불가 ∴ 다이나모 스타일 복제는 선형성 불가로 판단.

선형성의 비용

단일 리더 복제 사용 시, 팔로워 데이터센터로 접속한 클라이언트의 읽기 / 쓰기 요청은 동기식으로 리더 데이터센터에게 전송. 

이 경우에 데이터센터 사이의 네트워크가 끊기면 팔로워에 접속한 클라이언트들은 DB값을 쓸 수도, 선형성 읽기도 불가하다. → 애플리케이션 중단을 경험

CAP 정리

• 애플리케이션에서 선형성 요구 +  일부 복제 서버가 네트워크가 끊기면 요청 처리 불가. 네트워크가 고쳐질 때까지 기다리거나 오류 반환 → 가용성 없음
• 애플리케이션에서 선형성 요구 X + 네트워크가 끊겨도 독립적으로 요청을 처리할 수 있음. → 가용한 상태를 유지하지만 동작은 선형적이지 않음

∴ 선형성이 필요 없는 애플리케이션은 네트워크 문제에 더 강함. → CAP 정리

CAP = 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 선택하라.

CAP는 오직 하나의 일관성 모델(= 선형성)과 한 종류의 결함 (=네트워크 분단)만을 고려하는 역사적인 관심사이고, 현대에서 시스템을 설계할 때는 실용적인 가치가 없음.

선형성과 네트워크 지연

다중코어 CPU의 RAM에서도 선형성을 보장하지 않는다. → 메모리와 캐시에 저장하기 위해서 여러 데이터 복사본이 생성. 선형성을 제거한 이유는 내결함성이 아니라 성능 때문

선형성은 느리고, 지연 시간에 민감한 시스템에서는 이를 선택할 수 없다. 

순서화 보장

순서화, 선형성, 합의 사이에는 깊은 연결 관계가 존재

순서화와 인과성

순서화가 인과성을 보존하는 데 도움이 된다. 인과성은 이벤트에 순서를 부과.

인과적으로 일관적인(causally consistent) 시스템 : 시스템이 인과성에 의해 부과된 순서를 지킨다 (ex. 스냅숏 격리 : 인과적 일관성 제공. 데이터의 어떤 조각을 읽었다면 그보다 인과적으로 먼저 발생한 어떤 데이터도 볼 수 있어야 한다.)

인과적 순서가 전체 순서는 아니다

전체 순서(total order) : 두 요소가 있으면 항상 어떤 것이 더 크고 작은지 말할 수 있게 한다. 

비교 불가한 것도 존재 : 부분적으로 순서가 정해지는 것. 

• 선형성 : 전체 순서를 정할 수 있다. 
• 인과성 : 부분 순서를 정의. (동시에 실행됐다면 비교할 수 없다)

위의 정의에 따르면 선형성 데이터스토어에는 동시적 연산이 없다. (하나의 타임라인, 모든 연산은 그 타임라인을 따라서 전체 순서가 정해짐)

동시성은 타임라인이 갈라졌다 다시 합쳐지는 것을 의미. 

선형성은 인과적 일관성보다 강하다

선형성은 인과성을 내포한다. ↔ 선형성은 성능을 많이 떨어뜨린다. 

대부분의 경우에 선형성이 요구되어지는 것처럼 보여지는 것은 인과적 일관성을 요구하는 것임.

∴ 절충이 가능 (선형성은 인과성을 보존하는 유일한 방법이 아님). 인과성을 보존하면서 성능을 높은 데이터베이스를 연구 중

인과적 의존성 담기

비선형성 시스템이 인과적 일관성을 유지하는 방법에 대한 아이디어

1. 어떤 연산이 다른 연산보다 먼저 실행됐는지 알아야 한다. (부분 순서)
   • 전체 DB를 대상으로 같은 키에 대한 동시 쓰기를 검출 → 버전 벡터
   • DB는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야 함
     • 이전 연산의 버전 번호를 DB로 돌려줌

일련번호 순서화

모든 인과적 의존성을 추적하는 것은 오버헤드가 크다

• 일련번호, 타임스탬프 등을 써서 이벤트의 순서를 정할 수 있다 → 전체 순서 제공 (인과성에 일관적인 전체 순서대로 일련번호를 생성 가능)
• 동시 연산은 순서가 제멋대로일 수 있음. 

비인과적 일련번호 생성기

다중리더 or 리더 없는 데이터베이스에서 연산에 사용할 일련번호를 생성하는 방법

• 각 노드가 자신만의 독립적인 일련번호 집합을 생성
• 각 연산에 일 기준 시계에서 얻은 타임스탬프를 붙임 (LWW 충돌 해소 방법에서 사용)
• 일련번호 블록을 미리 할다. 

→ 생성된 일련번호가 인과성에 일관적이지 않음. 

인과성에 일관적이지 않은 예시

• 각 노드의 초당 연산수가 달라, 홀수 연산과 짝수 연산이 존재하면 어떤 게 인과적으로 먼저인지 알 수 없음. 
• 시게 스큐에 종속적
• 인과적으로 나중에 실행되는 연산이 블록 구간이 더 낮은 번호를 할당 받을 수 있음. 

램포트 타임스탬프

위 세 가지 방법 대신 인과성에 일관적일 일련번호를 생성하는 방법

(카운터, 노드ID)의 쌍으로 구성. 

• 카운터 : 각 노드가 처리한 연산 개수
• 노드ID : 각 노드별 고유 식별자

카운터 같더라도 노드ID를 포함시켜서 각 타임스탬프가 유일하게 구성된다. 

→ 전체 순서화를 제공. 두 타임스탬프가 있으면 카운터가 큰 것이 타임스탬프가 크고, 카운터 값이 같으면 노드ID가 큰 것이 타임스탬프가 크다.

짝수/홀수 카운터와 동일한 원리.
모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다.
노드가 자신의 카운터 값보다 큰 최대 카운터를 가진 요청이나 응답을 받으면 바로 자신의 카운터를 그 최댓값으로 증가시킨다. 

버전 벡터와의 차이

목적에서의 차이

• 버전 벡터 : 두 연산이 동시적인지 또는 어떤 연산이 다른 연산에 인과적으로 의존하는지 구별 가능
• 렘포트 타임스탬프 : 전체 순서화를 강제. 두 연산이 동시적인지 또는 인과적으로 의존성이 있는지를 알 수 없다. 버전벡터보다 크기가 더 작다

타임스탬프 순서화로는 충분하지 않다

램포트 타임스탬프

• 사후에 충돌에 성공하는 쪽을 결정하는 데는 효과적. ex) 동일 사용자명을 등록하려는 두 요청 → 시스템에서 사용자명 생성 연산을 모두 모으면 비교 가능. 
• 요청을 받은 후 당장 결정해야 할 때는 부족한 정보
• 연산의 전체 순서가 모든 연산을 모은 후에야 드러난다는 단점

→ 전체 순서 브로드캐스트 : 언제 전체 순서가 확정되는지 알아야 한다는 아이디어

전체 순서 브로드캐스트

전체 순서 브로드캐스트, 원자적 브로드캐스트라고도 함. 

안전성 속성 보장 필요 

• 신뢰성 있는 전달 : 어떤 메시지도 손실되지 않고 메시지가 한 노드에 전달되면 모든 노드에도 전달된다.
• 전체 순서가 정해진 전달 : 메시지는 모든 노드에 같은 순서로 전달된다.

노드나 네트워크에 결함이 있더라도 신뢰성과 순서화 속성이 항상 만족되도록 보장해야 한다. 

전체 순서 브로드캐스트 사용하기

상태 기계 복제 (state machine replication) : 모든 메시지가 DB에 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태를 유지한다는 원리

전체 순서 브로드캐스트의 특징

• 메시지가 전달되는 시점에 그 순서가 고정된다.
• 로그를 만드는 방법 중 하나이다. 
  • 메시지 전달은 로그에 추가하는 것과 비슷. 모든 노드는 로그를 읽어서 순서가 동일한 메시지를 볼 수 있다. 
• 펜싱 토큰을 제공하는 잠금 서비스 구현에도 사용 (잠금 획득 요청이 로그에 추가되고 모든 메시지는 로그에 나타난 순서대로 일련번호가 붙음 → 단조 증가)

전체 순서 브로드캐스트를 사용해 선형성 저장소 구현하기

전체 브로드캐스트 : 비동기식. 고정된 순서로 신뢰성 있게 전달되도록 보장되지만 언제 메시지가 전달될지는 보장되지 않음. 
선형성 : 최신성 보장 (읽기가 최근에 쓰여진 값을 보는 게 보장)

추가 전용 로그를 사용해 선형성 compare-and-set 연산 구현하기

1. 사용 가능한(점유 가능한) 모든 사용자명에 레지스터는 초기에 널(null) 값을 가진다. 
2. 메시지를 로그에 추가해서 점유하기 원하는 사용자명을 시험적으로 가리킨다
3. 로그를 읽고, 추가한 메시지가 돌아오기를 기다린다. 
4. 원하는 사용자명을 점유하려고 하는 메시지가 있는지 확인. 원하는 사용자명에 해당하는 첫 번째 메시지가 자신의 메시지라면 성공. 
   사용자명 획득을 커밋하고 클라이언트에게 확인 응답을 보낸다. 첫 번째 메시지가 자신의 메시지가 아니라면 연산을 abort 시킨다.

→ 선형성 쓰기를 보장하지만 선형성 읽기를 보장하진 않는다. 로그로부터 비동기로 갱신되는 저장소라면 오래된 값이 읽힐 수 있다. = 순차적 일관성, 타임라인 일관성

선형성 저장소를 사용해 전체 순서 브로드캐스트 구현하기

정수를 정장하고 원자적 increment-and-geet 연산이 지원되는 선형성 레지스터를 가정. 

1. 전체 순서 브로드캐스트를 통해 보내고 싶은 모든 메시지에 대해 선형성 정수로 increment-and-get 연산을 수행하고 레지스터에서 얻은 값을 일련번호로 메시지에 붙인다.
2. 메시지를 모든 노드에 보낼 수 있고 (손실되면 재전송) 수신자들은 일련번호 순서대로 메시지를 전달한다. 

선형성 레지스터를 증가시켜서 얻은 숫자들은 틈이 없다. ex) 어떤 노드가 메시지 4를 전달하고 일련번호가 6일 메시지를 받았다면 메시지 6을 전달하기 전에 5를 기다려야 한다. ↔ 램포트 타임스탬프

네트워크 연결이 끊기고 노드 장애가 날 때 선형성 정수 값을 복구하는 것이 관건 → 합의 알고리즘

분산 트랜잭션과 합의

합의 : 여러 노드들이 뭔가에 동의하게 만드는 것.

합의 불가능성

• FLP 결과 = 노드가 죽을 위험이 있다면 항상 합의에 이를 수 있는 알고리즘은 없다. 
• FLP는 비동기를 가정 → 타임아웃 허용이나 죽은 노드 식별 방법이 있다면 합의가 가능하다.

원자적 커밋과 2단계 커밋(2PC)

트랜잭션의 결과는 커밋이나 어보트. → 원자성을 보장
특히 다중 객체 트랜잭션과 보조 색인을 유지하는 경우에 중요

단일 노드에서 분산 원자적 커밋으로

한 노드에서 커밋을 원자적으로 만들어주는 것은 단일 장치 (해당 노드에 부착된 하나이 특정 디스크 드라이브의 컨트롤러)

but 파티셔닝된 DB에서 다중 객체 트랜잭션을 쓰거나 하는 경우엔 모든 노드에 커밋 요청을 보내고 각 노드에서 독립적으로 트랜잭션을 커밋하는 것만으로는 부족
(∵ 어떤 노드는 커밋되고 다른 노드는 롤백되어 원자성을 잃을 수 있음 → 다른 노드에서 롤백된 것을 알아도 이미 커밋된 데이터를 취소할 수 없다)
→ 다른 모든 노드도 커밋될 것이라고 확신할 때만 커밋이 되어야 한다. 

• 커밋된 데이터는 소급적으로 어보트 될 수 없다 (커밋 후 읽기 격리의 기반) 
• 다만 이후 보상 트랜잭션으로 덮는 것은 가능하다. 

2단계 커밋 소개

2단계 커밋 : 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하기 위해 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘

2PC는 코디네이터(= 트랜잭션 관리자)를 사용

• 트랜잭션을 요청하는 애플리케이션 프로세스 내에서 라이브러리 형태로 구현되지만 분리된 프로세스나 서비스가 될 수도 있다. 
• ex) 나라야나, JOTM, BTM, MSDTC 등

2PC 트랜잭션 진행 방법

1. 트랜잭션의 참여자(각 노드들)로부터 준비 요청을 보내서 커밋할 수 있는지 물어본다.
2. 코디네이터가 참여자들의 응답을 추적한다
   1. 모든 참여자가 '네'라고 응답했다면 코디네이터는 2단계에서 커밋 요청을 보내고 실제 커밋이 발생
   2. 하나라도 '아니오'로 응답했다면 2단계에서 모두 어보트 요청

약속에 관한 시스템

2PC가 원자성을 보장하는 두 가지 방법

• 참여자는 '네'에 투표할 때 나중에 분명히 커밋할 수 있을 것이라고 약속한다.
• 코디네이터가 한 번 결정하면 그 결정은 변경할 수 없다. (커밋 요청이 실패하면 재시도를 몇 번 하든지 상관없이 그 결정을 강제해야 한다. 참여자가 죽은 경우에도 복구될 때 커밋될 수 있도록 해야 한다)

단일 노드 원자적 커밋은 위의 두 가지를 하나로 묶어 트랜잭션 로그에 커밋 레코드를 쓴다. 

코디네이터 장애

준비 요청을 보내기 전에 장애가 났다면 참여자는 안전하게 트랜잭션을 어보트할 수 있으나 준비 요청을 받고 '네'에 투표한 상황에서 장애가 났다면 참여자는 회신을 계속해서 기다려야 한다. 

이 상태에 있는 참여자의 트랜잭션을 의심스럽다, 불확실하다 고 표현한다.

위 상황에서 이론상으로 참여자들끼리 통신해서 각 참여자가 어떻게 투표했는지 확인 후 어떤 것에 동의를 할 수는 있지만, 2PC 프로토콜의 일부는 아니다.

따라서 참여자들은 코디네이터가 복구되기를 기다려야 하고, 코디네이터는 참여자들에게 커밋 or 어보트 요청을 보내기 전 디스크의 트랜잭션 로그에 자신의 결정을 써야 한다. 

복구 시 트랜잭션 로그를 읽어서 모든 의심스러운 트랜잭션의 상태를 결정 + 커밋 레코드가 없는 트랜잭션 어보트

3단계 커밋

2PC : 코디네이터가 복구되기를 기다리느라 멈출 수 있음 → 블로킹 원자적 커밋 프로토콜

노드에 장애가 나도 멈추지 않도록 → 원자적 커밋 프로토콜을 논블로킹하게.. 대안은 3단계 커밋(3PC)

but 3PC는 지연에 제한이 있는 네트워크와 응답 시간에 제한이 있는 노드를 가정 ∴ 현실에서 원자성 보장 X

논블로킹 원자적 커밋

• 완벽한 장애 감지기가 필요 (어떤 노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메커니즘이 필요) 
• 타임아웃은 신뢰성 있는 장애 감지지가 아니다. 아무 노드도 안 죽고 네트워크 문제로 발생하는 지연이어도 타임아웃이 발생해 노드 장애로 판단하기 때문
• 따라서 코디네이터 장애와 관련된 문제가 있어도 2PC를 쓰는 것.

현실의 분산 트랜잭션

2PC 분산 트랜잭션에 대한 엇갈린 평가

• (+) 중요한 안전성 보장을 제공한다
• (-) 운영상의 문제를 일으키고 성능을 떨어뜨린다. 제공할 수 있는 것보다 더 약속하고 있다. 

두 가지 종류의 분산 트랜잭션

• 데이터베이스 내부 분산 트랜잭션
  • 데이터베이스 노드 사이에 내부 트랜잭션. 트랜잭션에 참여하는 모든 노드는 동일한 DB SW를 실행한다.
• 이종 분산 트랜잭션
  • 이종 트랜잭션의 참여자들은 둘 혹은 그 이상의 다른 기술. 서로 다른 벤더의 DB나 비데이터베이스 시스템(ex. 메시지 브로커)일 수 있다. → 시스템 내부가 다르더라도 원자적 커밋을 보장해야 한다. 

정확히 한 번 메시지 처리

메시지 확인 & 데이터베이스 쓰기를 단일 트랜잭션에서 원자적으로 커밋 → 메시지 처리하는 데이터베이스 트랜잭션이 커밋에 성공했을 때만 처리한 것으로 확인할 수 있음.
분산 시스템에서도 결과적으로 정확히 한번만 메시지가 처리되도록 보장 가능 (재시도는 있을지라도)

단, 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 (↔ ex. 이메일 서버가 2단계 커밋을 지원하지 않으면 재시도할 때 두 번씩 전송됨)

XA 트랜잭션

XA(eXtended Architecture) : 트랜잭션 코디네이터와 연결되는 인터페이스를 제공하는 C API. (Java는 JTA(Java Transaction API)를 통해 구현되고 JTA는 데이터베이스용 드라이버(JDBC)나 메시지 브로커용 드라이버(JMS)에서 지원된다)

XA의 특징

• 네트워크 드라이버나 클라이언트 라이브러리를 사용한 참여자 DB나 메시징 서비스와 통신을 가정
• 트랜잭션 코디네이터가 XA API를 구현
  • 트랜잭션의 참여자를 추적
  • 준비 요청을 보낸 후 그들의 응답을 수집
  • 각 트랜잭션에 대한 커밋.어보트 결정을 추적하기 위해 로컬 디스크에 있는 로그 사용
• 애플리케이션이 죽으면 코디네이터도 함께 사라짐 → 서버 재시작 되면 코디네이터 라이브러리가 로그를 읽어 각 트랜잭션의 커밋/어보트 결과를 복구 → 그 후 코디네이터는 DB 드라이버의 XA 콜백을 사용해 참여자에게 커밋/롤백을 요청
• 모든 통신이 클라이언트 라이브러리를 거치므로 데이터베이스 서버가 직접 코디네이터에 연결할 수는 없다.

의심스러운 상태에 있는 동안 잠금을 유지하는 문제

의심스러운 상태 (커밋/롤백 결정을 기다리는 상태)에서는 로우 단위의 잠금을 걸기 때문에 결정에 대한 통신이 안 오면 무기한으로 해당 자원을 사용할 수 없다. 
특히 2PL (2단계 잠금)을 사용하면 읽은 로우에도 잠금이 된다. 

코디네이터 장애에서 복구하기

이상 ) 코디네이터가 장애에서 재시작되면 로그로부터 그 전의 상태를 깨끗하게 복구하고 의심스러운 트랜잭션을 해소
현실 ) 고아가 된 의심스러운 트랜잭션을 파악하지 못하고 해당 트랜잭션은 영원히 잠금을 유지하는 불상사가 발생할 수 있음. (DB 재부팅도 소용이 없다 - 2PC의 올바른 구현은 원자성 보장을 위해 재시작 시에도 잠금을 유지)

→ XA 구현 중에 경험적 결정 (heurisitic decision) : 참여자가 코디네이터로부터 확정적 결정을 얻지 않고 의심스러운 트랜잭션에 대한 결정을 일방적으로 진행

분산 트랜잭션의 제약

• 코디네이터가 복제되지 않고 단일 장비에서만 실행되면 전체 시스템의 단일 장애점이 된다. (여러 코디네이터에서 고가용성을 제공하지 않음)
• 코디네이터가 애플리케이션 서버의 일부가 되면 해당 로그가 지속적인 시스템 상태의 중대한 부분이 된다. (상태 비저장 모드로 개발하는 것이 중요한 서버 애플리케이션에 흠이 됨)
• XA는 광범위한 데이터 시스템과 호환되어야 하므로 최소 공통 분모가 될 필요가 있다. 
• 장애를 증폭시키는 경향이 있다. 2PC가 성공적으로 트랜잭션을 커밋하려면 모든 참여자가 응답해야 한다. 결과적으로 시스템의 어느 한 부분이라도 고장나면 트랜잭션도 실패한다. 

내결함성을 지닌 합의

합의의 핵심 아이디어

• 안전성 속성 : 내결함성을 포기한다면 쉽게 만족할 수도 있음 
  • 균일한 동의 : 어떤 두 노드도 다르게 결정하지 않는다
  • 무결성 : 어떤 노드도 두 번 결정하지 않는다
  • 유효성 : 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다
• 활동성 속성
  • 종료 : 죽지 않은 모든 노드는 결국 어떤 값을 결정한다
    어떤 노드들에 장애가 나더라도 다른 노드들은 여전히 결정을 내려야 한다. 죽은 것이 복구되기를 기다리지 않는다.

합의 알고리즘과 전체 순서 브로드캐스트

유명한, 내결함성을 지닌 합의 알고리즘들은 합의의 핵심 아이디어 를 만족하면서 하나의 값을 제안하고 결정하지 않는다. 대신 값의 순차열에 대해 결정해서 전체 순서 브로드캐스트 알고리즘을 만든다. 

전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일. (각 회마다 노드들은 다음에 보내기 원하는 메시지를 제안하고 전체 순서 상에서 전달될 다음 메시지를 결정)

• 동의 : 모든 노드는 같은 메시지를 같은 순서로 전달하도록 결정
• 무결성 : 메시지 중복 x
• 유효성 : 메시지는 오염되지 않고 난데없이 조작되지 않음
• 종료 : 메시지 손실 x

단일 리더 복제와 합의

단일 리더 복제에서 리더 선택 방법

• 독재자 방법 : 노드가 죽으면 시스템은 운영자가 수동으로 다른 노드를 리더로 설정할 때까지 쓰기를 멈춤 → 종료 속성 만족 x
• 자동 리더 선출 방법 : 전체 순서 브로드캐스트에 가까워짐. but 스플릿 브레인 문제가 존재
  • 스플릿 브레인 문제를 해결하기 위해서는 합의가 필요함 ∴ 리더를 선출하기 위해 리더가 필요한 상황

에포크 번호 붙이기와 정족수

합의 프로토콜은 유일무이한 리더를 보장하지는 않고, 에포크 번호를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장

두 개의 다른 에포크에 있는 리더 사이에 충돌이 있으면 에포크 번호가 높은 리더가 이긴다. ∴ 리더는 결정 허용 전에 에포크 번호가 더 높은 다른 리더가 없는지 먼저 확인해야 함

정족수 투표 2가지 → 노드는 에포크 번호가 더 높은 다른 리더를 알지 못할 때만 제안에 찬성하는 투표를 한다.

1. 리더를 선출하기 위한 투표
2. 리더의 제안에 투표하기 위한 투표

이 두 번의 투표를 하는 정족수 중에 하나라도 겹쳐야 한다. 제안에 대한 투표를 할 때 에포크 번호가 더 큰 것이 있다고 밝혀지지 않았다면 현재 리더는 에포크 번호가 더 높은 리더 선출이 발생하지 않았다고 결론. → 리더로서 안전하게 제안된 값을 결정할 수 있음

합의의 제약

• 노드가 제안에 투표하는 과정 = 동기식 복제
• 엄격한 과반수가 동작하기를 요구 → 노드 한 대의 장애를 견디려면 최소 3대의 노드 / 2대의 장애를 위해서는 5대의 노드가 필요
• 투표에 참여하는 노드 집합이 고정되어 있어 동적 멤버십 확장을 하려면 정적 멤버십 확장보다 훨씬 복잡하다
• 장애 노드 감지를 위해 타임아웃에 의존한다 (잘못된 장애 판단 가능 + 연쇄 작용으로 성능 저하 발생 가능)
• 신뢰성 없는 네트워크에 민감하다

멤버십 서비스

멤버십 서비스 : 클러스터에서 어떤 노드가 현재 활성화된 살아 있는 멤버인지 결정.

노드의 장애를 신뢰성 있게 판단하는 것은 불가능하지만 합의와 연결하면 노드의 생사에 동의를 이룰 수 있다.  → 잘못된 판단일지라도 상당히 유용