Paxos Protocol 핵심 정리

최근 구글 서버의 에러가 잦는 일이 있었다. 구글에서 문제가 발생한 이유에 대해 설명글을 올렸고 그것을 보다가 Paxos protocol이라는 것을 처음 듣게 되어 공부해보았다. 구글 문서에 보면 distributed database에서 paxos protocol을 사용한다고 했다. 문맥상 분산 환경에서 사용하는 프로토콜이라는 것을 짐작해보았다.

 

Paxos란?

Paxos, 1989년 Leslie Lamport에 의해서 소개되었다. 팩소스는 신뢰할 수 없거나 실패할 수  있는 processers 네트워크에서 합의 문제를 해결하기 위한 프로토콜 그룹, 여러 노드 사이에서 하나의 값을 도출하기 위한 synod 알고리즘이다. 어떤 노드도 leader는 아님. leader가 없어서 발생하는 문제가 있다. livelock, dueling leader 문제. 이를 해결하기 위해서 Multi-paxos가 나옴.

 

안정성(consistency) 보장을 중요하게 생각함. 그래서 진행을 방해하면 안 되는 상황에서 많이 사용.

예를 들어, 파일이나 데이터 베이스를 복제하는 경우, 절대 변경되면 안되는 데이터 베이스를 전송하는 경우 등이 있을 수 있다.

 

Processors

• 임의의 속도로 동작하고 요청을 실패할 수 있다.
• 실패 후의 다시 안정화된 프로세서가 참여할 수 있다.

 

Network

• 다른 프로세서에게 메시지를 보낼 수 있다.
• 메시지는 비동기적으로 보내지고, 시간은 알 수 없다. 오래걸릴 수 있다.
• 메시지는 잃어버릴 수 있고, 복재될 수 있고, 순서가 보장되지 않는다.
• 메시지는 훼손되지 않는다.

 

Point

1. 불안정한 상황에서도 사용 가능

분산 트랜잭션에서 해당 프로토콜을 사용하는 이유는 분산 환경의 여러 노드 중 일부가 문제가 생겨 동작하지 않더라도 클라이언트의 요청을 수행할 수 있기 때문이다. 단 결함 있는 노드가 결함 없는 노드보다 적어야 한다.

 

2. 장애 허용

메시지는 느리게 배달되거나 중복, 소실이 가능하지만 데이터가 훼손되는 일은 없음

 

 

그 외

Livelock

다른 replica에서 들어오응 요청 비율이 수락률보다 높은 경우, 각 요청은 새로운 요청을 거부하고, 시스템이 실행 중이라도 커밋되지 않음

 

Dueling Leader

2개 이상의 nodes가 서로 각자가 leader라고 생각하는 경우의 문제. 

 

 

참고

medium.com/designing-distributed-systems/paxos-a-distributed-consensus-algorithm-41946d5d7d9

Paxos — A distributed consensus algorithm