상태 기계 복제(state machine replication) 또는 상태 기계 접근법(state machine approach)은 컴퓨터 과학 분야, 특히 분산 컴퓨팅에서 장애 허용(fault-tolerant) 서비스를 구현하기 위해 사용되는 일반적인 방법이다. 이 개념은 복제된 서버들을 관리하고 복제본과 클라이언트 간의 상호작용을 조율하는 데 핵심적인 역할을 하며, 복제본 관리 프로토콜을 이해하고 설계하기 위한 이론적 틀을 제공한다.
개요
상태 기계 복제의 기본 원리는 단일 서버(상태 기계)의 사본을 여러 개의 독립적인 서버에 배치하고, 클라이언트의 요청을 상태 기계의 입력으로 변환한 뒤, 모든 복제본이 동일한 순서로 동일한 입력을 처리하도록 하는 것이다. 각 복제본은 결정적(deterministic) 알고리즘에 따라 동작하므로, 동일한 시작 상태와 동일한 입력 순서를 가지는 모든 정상 복제본은 항상 동일한 상태와 출력에 도달한다.
이 개념에서 상태 기계는 다음과 같은 요소들의 집합으로 정의된다.
- 상태의 집합
- 입력의 집합
- 출력의 집합
- 전이 함수(Input × State → State)
- 출력 함수(Input × State → Output)
- 시작 상태
상태 기계는 시작 상태에서 출발하여, 도착한 각 입력이 전이 함수와 출력 함수를 통해 처리됨에 따라 상태가 갱신되고 출력이 생성된다.
장애 허용
결정성(Determinism)은 장애 허용을 제공하는 데 있어 핵심적인 특성이다. 여러 개의 복사본이 존재할 경우, 어느 한 복사본에서 장애가 발생하면 그 복사본의 상태 및 출력이 다른 정상 복사본들과 달라지므로 장애를 식별할 수 있다.
일반적인 이론적 원리에 따르면, 장애 허용을 위해 필요한 복제본의 최소 수는 3개이다. 한 복사본의 장애를 확인하려면 장애 복사본의 상태와 출력을 비교할 대상이 되는 정상 복사본이 최소 2개 필요하기 때문이다. 보다 일반적으로, F개의 장애를 허용하는 시스템에는 2F + 1개의 복제본이 필요하다.
비잔틴 장애(byzantine failure)를 다루는 경우, 즉 복제본이 서로 다른 값이나 잘못된 정보를 의도적으로 전달할 수 있는 상황에서는 상황에 따라 2F + 1개 또는 3F + 1개의 복제본이 필요할 수 있다.
주요 절차
상태 기계 접근법은 다음과 같은 단계로 구현된다.
- 독립적인 여러 서버에 상태 기계의 복사본을 배치한다.
- 상태 기계의 입력으로 변환 가능한 클라이언트 요청을 수신한다.
- 입력들 간의 처리 순서를 결정한다.
- 각 서버에서 결정된 순서대로 입력을 실행한다.
- 상태 기계의 출력을 클라이언트에게 응답으로 전송한다.
- 복제본 간의 상태 및 출력 차이를 감시한다.
이 중 3번째 단계인 입력 순서 결정은 가장 핵심적이며, 동일한 입력이라도 각 복제본에 동일한 순서로 제출되어야 모든 복제본이 동일한 결과에 도달할 수 있다. 입력 순서를 정하는 방법으로는 인과 순서(causal order)에 기반한 방법과 합의(consensus) 프로토콜을 이용한 방법 등이 있다.
역사적 배경 및 관련 연구
상태 기계 복제 개념은 1978년 레슬리 램포트(Leslie Lamport)의 "The Implementation of Reliable Distributed Multiprocess Systems" 논문과 1990년 프레드 슈나이더(Fred Schneider)의 "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial" 논문을 통해 체계적으로 정립되었다. 이후 팩소스(Paxos), 래프트(Raft), 뷰스탬프 복제(Viewstamped Replication) 등의 합의 알고리즘이 상태 기계 복제의 입력 순서 보장을 위해 활용되어 왔다.
상태 기계 복제는 분산 데이터베이스, 합의 기반 로그 서비스, 장애 허용 분산 시스템 등 현대 클라우드 기반 분산 시스템의 내결함성(fault tolerance)과 고가용성(high availability)을 보장하는 데 기여하는 기반 기술로 널리 사용된다.
