[분산 컴퓨팅] CAP과 FLP 정리

CAP

네트워크 문제로 인해 분산된 장치에 두 가지 문제가 발생할 수 있다.

• 일관성 문제 - 두 개의 분산된 장치가 일관되지 않은 정보를 제공하는 문제
• 가용성 문제 - 동일한 정보를 제공하기 위해 처리 속도가 느려지는 문제

 

CAP 정리는 네트워크 단절로부터 회복이 이루어지는 상태에서 서로 다른 분산 장치들이 위의 두 조건을 동시에 충족할 수 없음을 증명한 이론이다.

따라서 분산 컴퓨팅의 용도에 따라 궁극적 일관성(가용성 우선) 또는 강한 일관성(일관성 우선) 중 선택할 필요가 있다.

 

여기서 말하는 궁극적 일관성과 강한 일관성을 쉽게 설명하면 다음과 같다.

• 궁극적 일관성 - 시간이 지나면 결국 모든 노드가 같은 데이터를 갖게 된다는 것을 보장하기 때문에 일단 사용자에게 데이터를 제공한다.
• 강한 일관성 - 모든 사용자에게 같은 데이터를 제공하기 위해, 모든 노드의 데이터가 갱신되기 전까지 사용자에게 데이터를 제공하지 않는다.

 

FLP

지금까지 분산된 장치 간의 정보 복제 문제를 다루었다.

두 장치가 복제 상태에 있다는 것은 결국, 이 두 장치에 접근한 사용자들이 동일한 정보를 보는지에 대한 여부를 나타낸다.

 

N개의 분산 장치가 존재하고, 서로 메시지를 주고 받아 각자의 상태에 따라 결정을 내린다고 가정해보자.

이 중 하나의 장치가 장애로 인해 무응답하거나 메시지 전달에 지연이 발생했다면, 나머지 N - 1개의 장치는 어떻게 최종 데이터를 결정할까?

 

여기서 FLP 정리에 대한 이야기가 나온다.

FLP 정리는 비동기 시스템에서 단 하나의 프로세스라도 고장 날 수 있는 상황이라면, 확실한 합의를 이룰 수 있는 알고리즘이 존재할 수 없음을 증명한다.

즉, 어떠한 트레이드 오프도 없이 완벽한 분산 시스템을 구축할 수 없다는 이야기다.

 

정족수 충족 합의(Quorum-based consensus)는 분산 시스템에서 특정 결정이나 합의를 도출하기 위해, 시스템의 일부 노드만 응답하면 합의가 이루어지도록 하는 메커니즘이다.

전체 노드가 아닌 정족수에 해당하는 수의 노드만 응답하면 해당 연산을 성공한 것으로 판단하고, 시스템의 가용성과 어느 정도의 일관성을 유지할 수 있다.