이 문서는 [월간-CS][24년 5월] 핵심 이론부터 프로그래밍 실습까지, 분산컴퓨팅을 위해서 작성된 문서입니다. 이 문서에는 작성자(unchaptered)의 어떤 저작권이 포함되어 있지 않으며, 오직 도서 “분산 컴퓨팅”의 저작권만 포함될 수 있습니다.
“학습 목표” 분석
도서 “분산 컴퓨팅 4장 CAP과 FLP 정리”에서는 분산 컴퓨팅 환경에서의 데이터 일관성에 대해서 이야기 하고자 한다.
“복제 시 발생하는 네트워크 장애” 소개
3장 시간 동기화 문제와 논리적 시계 #분산 데이터베이스 환경에서의 시간 동기화 문제에서는 네트워크의 정상 작동을 가정하였습니다만, 실제로는 네트워크 장애가 많이 발생합니다.
1장 #두 장군 이야기와 2장, 계좌 이체 문제 등에서 살펴본 바와 같습니다.
비일관성의 문제(Inconsistency)
분산된 데이터베이스 병행 갱신 문제에서 만약 K은행-서울과 K은행-부산에서 긴급하게 실행해줘야 하는 건이 있다고 생각해보자.
각 서울-부산 지점은 네트워크 장애로 동기화가 이루어지지 않았다. 이 때, 각 지점에서 급한 용건을 처리하게 된다면 비일관성(Incosistency)이 발생한다.
K은행-서울 : Alice와 Bob의 공동계좌 — Alice가 1,000원 입금
K은행-서울 : Alice와 Bob의 공동 계좌 — Bob이 1,000원 출금
이 경우 네트워크 장애로 인해서 동기화가 이루어지지 않아서 아래와 같은 상황에 빠질 것이다.
초기
2024-05-18 15:00:00 서울 Alice & Bob 10,000원 보유 중
2024-05-18 15:00:00 부산 Alice & Bob 10,000원 보유 중
거래 | 네트워크 장애로 동기화 끊김
2024-05-18 15:00:01 부산 Alice & Bob 100원 이자수령 (1% 이자)
2024-05-18 15:00:02 서울 Alice & Bob 1,000원 입금
2024-05-18 15:00:03 부산 Alice & Bob 1,000원 출금
최종 | 네트워크 장애로 동기화 끊김 상태 유지 + 각 지점에서 별도 조치
2024-05-18 15:11:00 서울 Alice & Bob 11,000원 보유 중
2024-05-18 15:15:00 부산 Alice & Bob 9,100원 보유 중
가용성의 문제(Availability)
만약 은행이 서비스 가용성을 극대화 시키기 위해서 서울-부산의 각 지점이 독립적으로 서비스를 수행할 수 있도록 하면, 정보의 일관성(Consistency)가 크게 망가질 것입니다.
전용 네트워크 사용 혹은 대체 네트워크 설정 또한 문제를 복잡하게 만들 여지가 심합니다.
은행의 경우 정보의 일관성이 매우 중요하므로, 이를 해결하기 위해서 특정한 프로토콜을 엄격히 준수해야 합니다.
그 대신 사용자는 긴 서비스 지연을 겪을 수 있지만, 은행 입장에서는 보수적인 입장을 고수해야 합니다.
최종 일관성(Eventual Consistnecy) 혹은 강한 일관성(Strong Consistency)
일시적으로 일관성이 깨지더라도 성능을 중요시하는 선택입니다.
일정 시간 이후에는 일광성(Consistency)이 준수되므로 최종 일관성(Eventual Consistency)으로 부릅니다.
S3 Transfer Accelerator 기능이 이러한 최종 일관성에 맞춰서 만들어진 서비스 예시로 직관적이고 적절할 것 같습니다.
하지만 항상 일관성 있는 데이터가 동기화 되려면 가용성(Availability)이 일부 희생될 것입니다. 동시에 이런 환경을 강한 일관성(Strong Consistency)을 충족하는 환경이라고 합니다.
일관성과 가용성 동시 충족 딜레마
CAP 정리는 다음의 3가지를 모두 충족하는 것은 불가능하며, 2개를 충족하는 시스템은 나머지 1개를 충족할 수 없다는 내용입니다.
Consistency : 일관성
Availability : 가용성
Partition : 네트워크 파티셔닝
즉 분산 컴퓨팅 환경에서는 CA, CP, AP 만을 충족하는 시스템이 있다는 것입니다.
하지만 실제 상황에서는 네트워크 파티셔닝이 발생하면, 일관성 혹은 가용성을 모두 충족하는 것은 앞선 예시들과 같이 불가능합니다. 따라서 CA는 이론상으로만 존재 가능하다는 것이 일관성과 가용성 동시 충족 딜레마라고 할 수 있습니다.
“합의” 소개
1~2장에서는 2개의 참여자가 합의(COnsensus)를 마무리 짓기 위해서 중재자인 트랜잭션 코디네이터(TC, Transaction Coodrinator)가 필요하며 안정성(Safety)과 라이브니스(Liveness)를 충족시키기 위한 몇 가지 기법이 적용된 2단계 커밋 프로토콜(2PC Protocol, Two Phase Commit Protocol)을 배웠습니다.
하지만 합의의 개념이 3개 이상의 참여자로 확장하면 문제가 복잡해집니다.
합의 조건(Consensus Condition)
다음 세 가지 조건이 합의의 충족 여부를 판단하는 기준으로 정한다.
국문명 | 영문명 | 설정 |
|---|---|---|
종결 | Termination | 장애가 없는 모든 분산된 장치들은 궁극적으로 어떤 값을 결정한다. |
동의 | Agreement | 장치들이 어떤 값을 결정했다면, 그 값들은 모두 동일해야 한다. |
타당성 | Validity | 결정된 어떤 값은 반드시 누군가로부터 제안이 된 것이다. |
“FLP 정리” 소개
FLP 정리는 다음과 같은 가설 위에서 고찰되었다.
각 장치는 무기한 메세지 지연이 발생할 수 있는 비동기적 네트워크 상황에 존재한다.
각 장치는 반드시 결정을 내려야 한다.
궁극적으로 장애를 겪지 않은 장치들은 합의(Consensus)에 도달한다.
이런 상황에서 장애가 발생하면 궁극적으로 합의(Consensus)가 발생할 수 없는 상황이 있을 수 있다. 즉 분산 컴퓨팅 환경에서 비결정론적 알고리즘(Non-deterministic Algorithm)으로 작동할 것이다.
즉 FLP 정리에서 배울 점은 다자간 합의에서는 단 하나의 프로세스도 문제를 일으켜서는 안된다는 점이다.
자세한 내용은 각 챕터에서 다루고 있다.
분산 장치들 간의 동일값 결정 문제
장애 발생 시 결정론적 합의 알고리즘 존재 여부
분산 장치들 간의 동일값 결정 문제
3개의 프로세스가 있고 합의를 해야 한다.
하지만 1개의 프로세스가 장애를 겪어서 합의에 참여하지 못하면 시스템 전체도 합의를 마무리 할 수 없을 것입니다.
즉, 알고리즘이 항상 결정을 내릴 수 있는 결정론적 알고리즘(Deterministic Algorithm)은 존재할 수 없다. 여기서는 비결정론적 알고리즘(Non-deterministic Algorithm)일 것입니다.
장애 발생 시 결정론적 합의 알고리즘 존재 여부
3개의 프로세스가 모두 동의하면 0-valent로, 모두 거절하면 1-valent라고 한다고 해보자.
하지마 실제로 장애가 발생하면 서로 연관된 프로세스가 결정을 내리지 못하여 2-valent 상태가 필요할 것이다.
이러한 장애가 존재하는 한 결정론적 합의 알고리즘(Deterministic Consensus Algorithm)은 존재할 수 없을 것이다.
“무결한 프로세스 간의 합의” 소개
FLP 정리의 저자들은 합의(Consensus) 시점부터 작동하지 않는 프로세스가 있다면 이를 배제하고 합의를 결정하도록 하는 방법을 고안했다.
정족수 충족 합의(Quorum Fulfillment Consensus)
앞서 N개의 참여자 중에 합의(Consensus) 시점부터 일정시간 작동하지 않는 참여자는 배제할 것임을 말했습니다.
따라서 모든 무결한 참여자들은 이웃 프로세스들에게 동작하는지에 대한 메세지를 보내고 응답을 기다립니다. 동시에 자신의 상태와 함께 무결한 참여자의 집합도 함께 전달한다.
이렇게 취합한 무결한 참여자들의 상태 정보를 기반으로 각 프로세스는 미리 정해진 규칙에 따라서 값을 결정한다.
직장인 회식 여부 합의 예시
앞서 Alice, Bob, Craig가 회식을 가는 것을 합의하는 내용에서 Craig가 응답하지 않았다.
따라서 Alice도 결정을 내리지 못하고 대기 상태가 되었고 최종적으로 합의(Consensus)를 내리지 못하는 상태가 되었다.
하지만 이제는 Alice는 Craig가 무응답 상태에 빠졌으므로 Craig는 합의 과정에 참여할 수 없다고 인지했다. 따라서 Alice, Bob은 회식에 참여한다는 동일한 결정을 내릴 수 있게 된다.
Alice와 Bob은 무결한 참여자로서 의사 결정을 종결(Termination)하였고 동일한 결정을 내렸으므로 동의(Agreement)를 충족했으며 이 회식은 Alice가 제안한 것이므로 타당성(Validity)도 충족한다.
앞서 FLP 정리에서 다자간 합의에서 일부 프로세스가 장애를 일으켰을 때도 합의(Consensus)를 내리기 위해서 정족수 합의 프로토콜(Quorum Consensus Protocol)을 사용하는 사례를 언급했습니다.
