[분산시스템특론] 5. CAP 이론 & FLP 정리

CAP 이론

두 저장소가 서로 단절된 상태에서는 Consensus 를 유지하는 동시에 Available 을 유지하는 것이 불가능하다는 이론이다.

간단히 말하면, 단절된 상태에서는 가용성과 강한 일관성을 동시에 만족할 수 없다.

(P = Partition tolerance, 단절 내성, 분할 허용성, 네트워크 장애등으로 노드간 통신이 끊겨도 시스템이 동작 가능해야 한다는 특성.

정확하게는 분산시스템에서 CAP 3가지 특성을 모두 만족하는 것은 불가능하다는 이론이다.)

 

먼저 두 저장소가 서로 단절된 상태에서 각 저장소에 서로 다른 데이터가 업데이트 되었다고 해보자.

각 저장소는 상대방 저장소에 어떤 데이터가 들어있는지 알 수 없으므로 일관성을 유지할 수 없다.

 

만약 일관성을 유지하고자 한다면, 직접 (수동으로) 일관성을 맞춰주어야 한다.

이를 위해서는 내 데이터가 수정되었을 때 상대 저장소에 수정사항을 반영하기 위해서 상대 저장소에 대한 업데이트를 막고 동기화를 시켜주어야 한다. 그런데 상대 저장소에 대해 업데이트를 막는다는 것은, 그 저장소를 사용하지 못하게 막는다는 것과 같다.

따라서 강한 일관성을 지키려고 하면 Availability 를 잃을 수 밖에 없다.

 

따라서 어떤 저장소가 서로 단절되어있을 때는 가용성과 일관성 중 하나를 선택해야 한다.

물론 일반적으로는 가용성이 더 중요하다.

예를 들어 소셜미디어라면 내가 수정한 데이터가 상대 DB에 잘 보이는지보다는 내가 데이터를 잘 올리는 것이 더 중요하므로 가용성이 더 중요하다. 내가 올린 데이터를 상대가 무조건 봐야하는 것은 아니기 때문이다.

 

 

FLP Impossibility 정리

FLP 정리는 다음에 대한 증명을 말한다.

 

비동기 분산 시스템에서는, 단 하나의 노드라도 장애가 발생할 수 있다면,

합의를 항상 보장할 수 있는 결정적 알고리즘이 존재하지 않는다.

 

쉽게 말하면, 합의에 참여하는 노드 중 하나라도 장애가 발생하면 전체가 합의에 다다르지 못할 수 있다는 정리이며,

더 쉽게 말하면, 비동기 네트워크에서 장애가 존재할 수 있다면, 모든 노드가 동일한 의사결정을 내리는 것이 불가능함을 말한다.

 

이 정리가 지지받는 가장 근본적인 원인은 '메세지 지연' 과 '장애' 를 구분하는 것이 불가능하기 때문에 그렇다.

(즉, 완벽한 failure detection 은 불가능하다. 이것도 증명되어 있다!)

 

그래서 분산 시스템에서는 약간의 타협을 봐서, 장애가 발생할 수 있음을 인정하고, 일정 정족수 이상의 인원만이라도 합의를 해보자는 방향을 추구한다.

 

 

전제

장애의 전제 조건

- 네트워크 장애는 없다. (메세지는 안정적으로 한번만 전달된다)

- 악의를 가진 행동은 하지 않는다.

- 절대시계는 없고, timeout 개념도 없다.

- 단, 프로세스가 죽는 일은 발생할 수 있다.

 

상황

- 모든 분산 프로세스는 0 또는 1의 값을 가지고 시작한다.

- 장애가 없는 분산 프로세스는 어느 순간 0 또는 1 중 하나의 값을 결정한다.

- 우리가 원하는 상황은 합의에 도달한 상황, 즉, 모든 프로세스가 같은 값을 결정한 상황을 만드는 것이 목표이다.

- 단, 초기값에 상관없이 임의값 하나로 결정짓는 프로토콜은 생각하지 않는다.

 

프로세스

- 모든 프로세스는 오토마타를 따르며, 여러 state 로 이루어져 있다.

- 프로세스는 하나의 state 에서 메세지를 받거나 임의 동작을 수행하거나, 유한한 수의 메세지를 한번에 여러 프로세스에게 보낼 수 있다. (브로드캐스트)

- 프로세스는 1 비트 인풋, 아웃풋을 가지며, 무한한 내부 저장소를 가진다.

- 각 state 는 input value, output value, pc, 저장소에 저장된 값들로 정의된다.

- initial state 는 인풋을 제외하고 기본값으로 시작한다. (output = b, 만약 output = 1 / 0 이면 그 값으로 결정된 것으로 간주, 절대 변하지 않는다)

 

메세지

- 프로세스가 주고받는 메세지는 p 와 m 으로 표현된다. ( p = 목적지 프로세스, m = 메세지 내용)

- send(p, m) : p 로 향하는 메세지 m 을 전송 버퍼에 넣는다

- receive(p) : p 로 향하는 메세지를 버퍼에서 꺼내 m 을 추츨하거나, 아무것도 받지 않는다. (실제로 있더라도)

- 초기에는 메세지 버퍼가 비어있다.

 

Configuration

- 프로세스들의 상태와 현재 메세지 버퍼의 상태를 가리켜 configuraion 이라고 한다.

- configuration 의 변화를 가리켜 step 이라고 한다.

- 한 프로세스의 step 은 'receive(p) -> 현재 프로세스의 상태와 수신한 메세지 내용에 따른 새로운 내부상태로의 결정론적 전환' 과정으로 변화한다.

- 수행되는 step 을 가리켜 event 라고 표현하며 e = (p, m) 으로 표현한다.

- 이 이벤트 e 에 의해 발생한 configuration 을 가리켜 e(C) 로 표현한다.

- (p, NULL) 은 어떤 C (configuration) 에서도 발생 가능하다. 즉, 메세지의 수정 없이 버퍼만 수정하는 것도 스텝으로 본다.

 

스케줄

- 어떤 C 를 시작점으로 하여 수행되는 이벤트의 sequence 를 가리켜 스케줄이라고 하며,  sigma 로 표현한다.

- 스케줄에 따라 수행된 step 시퀀스를 가리켜 run 이라고 한다.

- 어떤 run 이 admissiable 하다는 것은 최대 1개의 프로세스만 장애가 발생하고, 나머지 비장애 프로세스에게는 메세지가 잘 도착한 경우를 말한다.

- 어떤 run 이 deciding run 이라면, 모든 프로세스가 결정을 내린 것이다.

- 어떤 스케줄을 통해 도달한 C 를 가리켜 sigma(C) 로 표현하며, 이 C 를 가리켜 reachable 이라고 표현한다.

- 초기 C 로부터 도달 가능한 C 를 가리켜 accessible 이라고 표현한다.

 

증명

Lemma 1

서로 독립적인 두 스케줄 sigma1, sigma2 에 대해

같은 어떤 상태에서부터 sigma1, sigma2 순으로 적용하나, sigma2, sigma1 순으로 적용하나 도착 C 는 동일하다.

 

C 를 구성하는 프로세스 중 decision value 를 가진 프로세스가 있다면, 그 C 도 decision value 를 가지고 있다고 표현한다.

 

증명을 위해, 장애를 가진 프로세스가 1개 있음에도 합의에 성공했다는 명제가 틀렸음을 증명해보자. (귀류법)

즉, 프로토콜이 영원히 합의에 도달하지 못하는 케이스가 있음을 보여주면 된다.

 

Lemma 2

초기 C 로부터 도달 가능한 모든 C 의 결정값 집합의 크기는 1보다 크다.

(즉, 초기 상태로부터 결정될 수 있는 값의 가능성은 1가지로 확정되지 않는다)

 

 

lemma 3

결정값이 2개가 나올 수 있는 C 에 대해 적용가능한 이벤트 e 가 있다.

이 e 를 적용하지 않고 C로부터 도달 가능한 configurations 들의 집합을 'C' 라고 하고,

이 'C' 들로부터 e 를 적용해서 나온 configuration 을 'D' 라고 하면, 이 'D' 는 결정값이 2개가 나올 수 있다.

 

즉, 어떤 프로세스에 장애가 생겨서 그 프로세스를 포함하는 (p, m) 이벤트를 사용하지 않고 새로운 C 로 갔다고 가정해보면, 그 C 들에 대해서 '이제서야' e 를 적용해봤더니 그 결과는 결정값이 2개가 나올 수 있다는 것이다.

 

따라서 장애가 발생한 프로세스가 단 한 개가 있더라도 합의에 도달할 수 있다는 가정은 거짓이므로 기존 명제가 증명된다.