분산 트랜잭션과 합의

들어가며

요즘 여러 대규모 서비스들은 MSA를 사용하고 있습니다. 이는 각 서버별로 확장을 용이하게 하며 한 서비스의 장애가 다른 서비스로 옮겨가지 않도록 해줍니다.

하지만 MSA가 장점만 가지고 있지는 않습니다. 대표적으로 트랜잭션의 문제가 있습니다.

예를 들어 주문 서비스와 재고 서비스가 분리된 온라인 쇼핑몰을 생각해봅시다. 여기서 주문을 처리하던 도중 서버가 다운됐다고 가정하겠습니다. MSA에선 일반적으로 각 서비스가 서로 다른 DB를 가지고 있어 트랜잭션이 보장되지 않습니다. 즉, 주문은 생성됐지만 재고가 차감되지 않거나 재고는 차감됐지만 주문이 생성되지 않는 문제가 발생할 수 있습니다. 이처럼 분산 시스템에서는 여러 노드가 하나의 작업에 대해 일관된 결정을 내리기가 쉽지 않습니다.

그렇기에 과거부터 계속 분산 시스템에서 여러 노드가 하나의 값에 대해 일치된 결정을 내리는 문제를 해결하기 위해 이를 합의 알고리즘이라고 부르며 이에 대해 많은 연구가 이뤄졌습니다. 

이 글에서는 분산 트랜잭션 프로토콜인 2PC와 3PC의 한계를 살펴보고, 이를 통해 합의 알고리즘이 갖춰야 할 핵심 특징들을 알아보겠습니다.

2PC (Two-Phase Commit)

2PC는 코디네이터를 사용해 모든 노드들이 원자적으로 commit 하거나 abort 하도록 하는 방법입니다.

2PC 알고리즘은 2단계로 동작합니다. 우선 prepare 단계로 코디네이터가 모든 노드에 prepare 메시지를 전송합니다. 이는 각 노드들이 커밋을 할 수 있는지 여부를 물어보는 단계로 각 노드들은 커밋이 가능한 지 불가능한지에 대해 응답을 보냅니다. 만약 여기서 1개의 노드라도 커밋이 불가능하다고 하면 코디네이터는 전체 노드에 abort 요청을 보내 요청을 롤백하고 전체 노드가 커밋이 가능하다고 동의하면 commit 명령을 내려 일괄적으로 커밋을 하게 됩니다.

 

하지만 이런 2PC는 큰 문제점이 존재합니다. 바로 블로킹 프로토콜이라는 점입니다. 2PC에서 모든 노드들은 코디네이터의 명령에 의해 커밋하거나 롤백을 수행합니다. 만약 코디네이터에 장애가 발생하면 어떻게 될까요?

코디네이터에 장애가 발생하면 각 노드들은 지금 트랜잭션을 커밋을 할지 롤백을 할지 결정하지 못합니다. 코디네이터의 명령없이 결정하게 되면 데이터 불일치가 발생할 수 있기 때문입니다. 그렇기에 2PC가 완료되기 위해선 코디네이터가 복구되기를 기다려야 합니다.

3PC (Three-Phase Commit)

3PC는 2PC의 블로킹 프로토콜이라는 문제를 해결하기 위한 방법입니다. 3PC는 2PC와 달리 총 3단계로 이뤄집니다.

• CanCommit : 참여자들의 커밋 가능 여부 확인 (2PC의 prepare 단계와 유사하다고 생각하면 될 것 같습니다.)
• PreCommit : 실제 커밋 준비 명령, 참여자들이 커밋 준비 완료 상태로 전환
• DoCommit : 최종 커밋 실행

여기에 타임 아웃을 추가함으로써 3PC는 2PC의 블로킹 문제를 완화합니다.

2PC에서는 Prepare 단계 이후 코디네이터에 장애가 발생하면 참여자들은 전부 대기해야 합니다. 즉, 스스로 결정하지 못합니다.

하지만 3PC의 경우 CanCommit 이후 코디네이터에 장애가 발생했을 시 일정 시간 이후 타임 아웃 됩니다.

여기서 2PC와의 차이점이 나타납니다. 2PC는 참여자들끼리 통신이 불가능합니다. 하지만 3PC에서는 타임 아웃이 될 경우 참여자들끼리 통신하게 됩니다. 이는 정상 상황에서는 코디네이터가 흐름을 제어하면서 제어 흐름을 단순화하고 효율적으로 동작하지만 장애 상황에서는 블로킹을 해결할 수 있게 해주는 방법입니다.

이렇게 참여자들끼리 통신하여 하나의 노드라도 PreCommit 메시지를 받았다면 이는 커밋이 가능한 상황으로 인지하고 모든 참여자가 커밋을 하게 됩니다. 만약 단 하나의 노드도 PreCommit 메시지를 받지 못 했다면 모든 참여자가 롤백을 하게 됩니다.

 

하지만 3PC라고 항상 원자성이 보장되지는 않습니다. 왜냐하면 3PC는 "시스템 내의 모든 살아있는 참여자들이 서로에게 도달할 수 있다" 즉, "네트워크 파티션이 발생하지 않는다"는 암묵적인 가정하에 동작하기 때문입니다.

그렇기에 네트워크 파티션이 발생하여 참여자들이 독립된 파티션으로 분리되면 하나의 파티션에는 모두 롤백을 다른 파티션에서는 모두 커밋을 하는 원자성이 보장되지 않는 상황이 생길 수 있습니다.

현실의 분산 트랜잭션

현실의 분산 트랜잭션은 2PC나 3PC의 한계를 극복하기 위해 아래 4가지 특징을 만족해야 합니다.

• 균일한 동의 : 어떤 두 노드도 다르게 결정하지 않는다
• 무결성 : 어떤 노드도 두 번 결정하지 않는다
• 유효성 : 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다
• 종료 : 죽지 않는 모든 노드는 결국 어떤 값을 결정한다

균일한 동의와 무결성은 합의의 핵심 아이디어입니다. 이 2가지를 간단히 정의하면 합의 알고리즘에서 채택된 값에 대해 모든 노드가 해당 값으로 결정해야 되며 한번 정의된 값은 다시 변경될 수 없다는 뜻입니다.

유효성은 항상 고정된 값을 선택하게 되는 상황을 배제하는 속성입니다. 즉 결정된 값은 반드시 어떤 노드가 제안한 값이어야 하며 무조건 null로 결정되는 알고리즘과 같은 상황을 막아줍니다.

종료는 블로킹과 관련되어 있습니다. 2PC에서 코디네이터에 장애가 발생하면 각 노드들은 결정을 할 수 없습니다. 이는 종료 속성을 만족하지 않습니다. 즉, 다른 노드에 장애가 발생하더라도 다른 노드들은 결정을 내려야 합니다.

다만, 종료 속성에는 암묵적인 가정이 있습니다. 바로 죽거나 연결할 수 없는 노드가 전체의 절반 미만이라는 가정입니다. 이는 정족수라는 개념과 관련이 있습니다.

 

정족수는 분산 시스템에서 특정 작업을 수행하기 위해 필요한 최소한의 노드 수를 의미합니다. 3개 노드일 경우 정족수는 2, 5개 노드일 경우 정족수는 3, 7개 노드일 경우 정족수는 4, ... 입니다.

정족수가 필요한 이유를 설명하기 위해 5개의 노드가 있다고 가정해보겠습니다. 이때 네트워크 분할이 발생하여 2대 / 3대로 분할이 되었습니다.

만약 정족수가 없다면 각 그룹에서 각각 리더를 선출하게 될 겁니다. 이는 데이터 불일치를 발생시킵니다. 하지만 정족수가 있다면 5대의 정족수는 3이므로 3대 그룹에서만 리더를 선출하게 되고 이로 인해 데이터 불일치를 막을 수 있습니다.

 

그러나 현재 사용하는 내결함성을 지닌 합의 구현은 과반수의 노드에 장애가 발생해도 합의 시스템을 오염시키지 않도록 구현되어 있습니다.

이런 알고리즘에는 대표적으로 라프트(Raft), 뷰스탬프 복제(Viewstamped Replication), 팍소스(Paxos), 잽(Zab) 등이 있습니다.