[1주차, 2장] 커밋 프로토콜

이 문서는 [월간-CS][24년 5월] 핵심 이론부터 프로그래밍 실습까지, 분산컴퓨팅을 위해서 작성된 문서입니다. 이 문서에는 그 어떤 저작권이 없으며, 편하게 참고 및 사용하셔도 됩니다.

“학습 목표” 분석하기

도서 “분산 컴퓨팅 2장 학습 목표”에서는 중계자의 도입으로 분산 컴퓨팅의 문제를 해결하는 방법을 설명하고 있습니다.

서로 떨어져 있는(분산된) 프로세스(실행 중인 프로그램)들의 거래를 중계자를 통해서 안전하게 이행하고 종결하는 방법을 알아보자

"계좌 이체 문제” 소개

동일한 네트워크에 연결된 은행 S, K가 있다.
또한 두 사람 Alice와 Bob은 각각 은행 S와 K를 사용하고 있다. 두 사람 모두 10,000원의 돈을 가지고 있을 때, Alice가 Bob에게 1,000원을 이체한다면 어떻게 거래의 완결성을 보장할 수 있을까?

1장 분산 컴퓨팅이란 무엇인가? #두 장군 이야기에서 알 수 있듯이, K은행에 있는 Bob의 계좌에 계좌 이체 내역이 반영되기 전에 S은행의 Alice 계좌만 차감을 한다면 문제가 복잡해질 것이다.

1. Alice 계좌 차감 이후, Bob 계좌 증가 반영 되지 않음

   → 거래 상 문제 발생

2. Alice 계좌 차감 이후, Bob 계좌 증가 반영

   → 거래 완결

혹은 그 외의 다양한 상황에서도 문제가 복잡해집니다.
따라서 분산 컴퓨팅 시스템에서는 두 가지 기본 요건을 가지게 됩니다.

“안정성과 라이브니스” 소개

1. 안정성(Safety)

   1. 정의 : 잘못된 결과가 일어나서는 안된다는 원칙

   2. 예시 : Alice의 잔고만 줄어들거나, Alice의 잔고 변화 없이 Bob의 잔고만 늘어나는 결과를 허용하지 않음

2. 라이브니스(Liveness)

   1. 정의 : 원하는 결과가 반드시 어느 시점에 실현되어야 하는 원칙

   2. 예시 : Alice의 잔고가 줄어드는 것과 함께 Bob의 잔고도 올바르게 늘어나는 결과가 언젠가는 발생해야함

안정성과 라이브니스 동시 충족 문제

지금까지 알아본 방식을 양자 합의 방식이라고 부른다.
두 장군의 이야기나 계좌 이체 문제 모두 상대방이 메세지를 확인했는 지를 고민할수록 합의 성공률은 0에 수렴하게 된다.

안정성(Safety)을 극한으로 추구하게 될 경우, Alice와 Bob은 계속 합의 과정을 반복하게 되면서 이체를 완료할 수 없게 될 것이다. 즉, 라이브니스(Liveness)를 충족할 수 없다.

이러한 문제는 아래의 환경적 요인이 개선되기 전에 해결될 수 없다.

• 네트워크의 비동기적 문제가 완전하게 해결되거나

• SF 영화처럼 Alice가 Bob에게 순간 이동할 수 있게 되는 등

부동산 거래 문제

현재 Alice는 자신의 집을 팔고 더 좋은 동네의 집을 사 이사가고 싶어한다. 즉, Alice는 2건의 거래 당사자가 될 것이다.
(설명의 편의를 위해 Alice 집을 1,000원으로 표기한다.)

• 구매 계약

  • 거래액 : 1,000원

  • 계약금 : 100원 (10%)

  • 특약 : 일주일 안에 잔금을 치르지 않으면, Alice는 계약금 100원을 돌려 받지 못한다.

• 판매 계약

  • 거래액 : 1,000원

  • 계약금 : 100원 (10%)

  • 특약

    • 일주일 안에 잔금을 받지 않으면, Alice는 계약금 100원을 상대방에게 돌려줘야 한다.

    • Alice가 계약을 파기할 경우, Alice는 계약금 100원의 2배인 200원을 상대방에게 돌려줘야 한다.

이런 경우 Alice는 어떤 거래도 100% 완료될 것이라고 확약(Commit) 할 수 없고 서로 메세지를 주고 받는 식으로는 합의(Consensus)에 이르지도 못한다.

따라서 이러한 복잡한 거래 상황을 담당할 중계자의 존재가 필요할 것이다.

“2단계 커밋 프로토콜” 소개

앞선 예시들(두 장군, 계좌 이체, 부동산 거래)과 같이,
분산 컴퓨팅 참여 프로세스들 간의 거래 행위를 트랜잭션(Transaction)이라고 부른다.

앞선 예시들에서는 안정성(Safety)과 라이브니스(Liveness)를 동시에 추구하다가 교착 상태(Deadlock)에 빠지는 것을 알아보았다.

따라서 트랜잭션이 안전하게 수행되기 위해서는 원자성(Atomicity)을 가져야 한다.

트랜잭션의 원자성이란?

트랜잭션에 참여하는 컴퓨팅 주체들이 모두 해야 할 일을 하거나, 아예 시작도 하지 않는 것

즉, Alice가 바로 잔고를 갱신하는 것이 확약(Commit)되지 않는다면, Bob도 자신의 잔고를 갱신하는 것에 확약하지 않는다.
그 반대의 경우 Alice가 확약하면, Bob도 확약해야 한다.

원자성을 보장하면서 트랜잭션이 수행되기 위해서는 아래의 2가지가 필요하다.

• 트랜잭션 코디네이터(TC, Transaction Coordinator)

• 2단계 커밋 프로토콜(2-Phase Commit Protocol)

스트로우맨 프로토콜

가장 간단한 해결방법으로는 스트로우맨 프로토콜(Straw Man Protocol)이 있다.

1. Alice 컴퓨터는 트랜잭션 코디네이터(TC)를 통해 요청을 보낸다.

2. 트랜잭션 코디네티어(TC)가 거래 당사자 은행 S와 K에게 각각 Alice, Bob 계좌 잔금의 변동을 요청한다.

하지만 이 방법도 결국 두 은행 간의 계좌 정보 변경 여부를 완벽하게 처리할 수 없다. 즉, 장애 감내성(Fault-Tolerant)이 높지 않다.

즉 아래와 같이 다양한 장애 상황에서 장애(Fault)가 발생할 수 있고 이에 따라서 안정성 및 라이브니스가 불충족된다.

스트로우맨 프로토콜에서는 이러한 문제들은 스스로 해결되지 않는다.

1. Alice의 잔고가 1,000원보다 적을 경우

   → TC는 요청을 동시에 처리하므로, Bob의 잔고가 1,000원 늘어난다.

2. Bob의 계좌가 존재하지 않을 경우

   → TC는 요청을 동시에 처리하므로, Alice의 계좌 잔고만 1,000원 감소한다.

3. 은행 S(Alice)의 시스템이 정전될 경우

   → “요청을 잘 전달했습니다” 메세지가 Alice에게 전달되지 않을 수 있다.

4. 네트워크 상 문제가 있는 경우

   → 모든 시스템이 멀쩡해도, Alice에게 출금만 이루어지거나 Bob에게 입금만 이루어 질 수 있다.

5. TC가 중단된 경우

   → 역시나 Alice, Bob 중 한 쪽에만 거래가 완료될 수 있다.

원자적 커밋 프로토콜

스트로우맨 프로토콜에서 준비(Prepare) 및 확약(Commit) 단계를 추가하여 원자적 커밋 프로토콜(Atomic Commit Protocol)을 만들 수 있다.

1. 준비 단계

   

2. 확약 단계

   

만약 확약 단계에서 두 은행 S, K 중 하나라도 NO라고 회신하면 거래는 모든 거래는 합의되지 않는다. 즉, 취소된다.

안정성 보장을 위한 조치

스트로우맨 프로토콜에 비해 원자적 커밋 프로토콜은 아래와 같이 안정성이 강화되었습니다.

• 은행 S, K가 준비되지 않은 상태에서는 거래가 진행되지 않는다.

• 은행 S, K에 실제 계좌가 없는 경우에는 거래가 진행되지 않는다.

• 은행 S, K의 실제 계좌가 있더라도 잔고가 없으면 거래가 진행되지 않는다.

하지만 확약(OK) 이후에 발생하는 아래 상황들에는 안정성이 보장되지 않습니다.

• 은행 S, K가 OK 이후에 마비되었다.

• 트랜잭션 코디네이터가 마비되었다.

• 네트워크 장애가 발생하여 요청이 완료되지 않고 있다.

이런 문제들로 인해서 누군가가 돈을 잃거나 공돈을 얻는 상황이 발생할 수 있다. 이를 개선하기 위해서 커밋 로그, 메세지 재전송, 프로토콜 종료 및 재시작 등을 추가할 수 있다.

1. 모든 요청을 보내기 전에 커밋 로그(Commit Log)를 기록한다.

2. 시스템 장애 후 회복 시 커밋 로그(Commit Log)를 조회하여 아래의 조치를 수행한다.

   1. 메세지 재전송

   2. 이체 명령을 취소

라이브니스 보장을 위한 조치

앞서 안정성의 조치를 했음에도 네트워크 장애로 인해서 라이브니스가 보장되지 않는다.

은행 S는 확약(Commit)을 요청 받았지만, 은행 K와 트랜잭션 코디네이터 상에 네트워크 장애가 발생하면 어떻게 될까?

발생 가능한 시나리오는 다음과 같다.

1. 은행 K는 무한히 확약(Commit)을 기다리게 된다.

2. 트랜잭션 코디네이터가 재시작할 수 있으나 전체 과정이 반복되는 비효율이 발생한다.

따라서 은행 S, K에서 실행되는 개별 작업자가 상대방 은행에 확약 및 취소를 확인하고 이를 그대로 준수함으로써 이 문제를 개선할 수 있다.

(은행 K는 대기 상태였고 은행 S에 확인해보니 확약 상태였다. 이 경우, 은행 K와 트랜잭션 코디네이터 사이의 네트워크 문제일 것이며 은행 K 또한 확약을 받게 될 것이다.
이에 따라 재시작 없이 은행 K는 확약에 따른 작업을 진행하게 된다.)

이런 방법을 통해서 라이브니스 문제를 해소할 수 있다.

2단계 커밋 프로토콜

원자적 커밋 프로토콜(Atomic Commit Protocol)에서 아래의 3가지가 포함된 프로토콜을 2단계 커밋 프로토콜(2-Phase Commit Protocol)이라고 한다.

1. 선제적 메세지 기록, 커밋 로그(Write-ahead Commit Log) → 안정성 보장을 위한 조치

2. 메세지 재전송 → 안정성 보장을 위한 조치

3. 프로토콜 종료 및 재시작 → 라이브니스 보장을 위한 조치

정리

두 장군 이야기, 계좌 이체 문제, 부동산 거래 문제 등을 통해서 분산 컴퓨팅 환경의 문제와 이를 해결하기 위한 2단계 커밋 프로토콜(2-Phase Commit Protocol)을 배웠습니다.

아래는 정리한 내용입니다.

1. 분산 프로세스 간, 안정성과 라이브니스의 동시 충족은 불가능하다.

2. 이를 보완하기 위해서 트렌젝션 코디네이터(Transaction Coordinator)와 2단계 커밋 프로토콜(2-Phase Commit Protocol)을 도입해야 한다.

   커밋 프토로콜의 발전 과정

   1. 스트로우맨 프로토콜(Straw Man Protocol)

      1. 구조 : 트랜잭션 코디네이터 도입

      2. 특징

         1. 안정성, 라이브니스 확보 안됨

         2. 장애 감내성 매우 낮음

   2. 원자적 커밋 프로토콜(Atomic Commit Protocol)

      1. 구조 : 준비(Prepare) 및 확인(Ok) 단계 도입

      2. 특징

         1. 안정성, 라이브니스 확보 안됨

         2. 장애 감내성 낮음

   3. 2단계 커밋 프로토콜(2-Phase Commit Protocol)

      1. 구조

         1. 선제적 메세지 기록, 커밋 로그 도입 → 안정성 보장

         2. 메세지 재전송 → 안정성 보장

         3. 프로토콜 종료 및 재시작 → 라이브니스 보장

      2. 특징

         1. 안정성, 라이브니스 확보됨