상태 기계 복제

위키백과, 우리 모두의 백과사전.

상태 기계 복제(state machine replication) 또는 상태 기계 접근법(state machine approach)는 컴퓨터 과학에서 서버들을 복사하고 복제된 서버와 클라이언트 간의 상호적용을 조율하는 것으로 장애 허용 서비스를 구현하는 일반적인 방법이다. 이 방법은 복제본 관리 프로토콜을 이해하고 설계하기 위한 틀을 제공한다.[1]

문제의 정의[편집]

분산 서비스들[편집]

분산형 소프트웨어는 종종 고객과 서비스 측면에서 구조화된다. 각 서비스는 하나 이상의 서버들로 구성되고 고객의 요청에 따라 작업을 수행한다. 중앙화된 서버 하나만 사용하는 것이 서비스를 구현하는 가장 간단한 방법이지만 결과물은 서버를 실행시키는 프로세서만큼의 장애허용을 제공한다. 만약 이 수준의 장애 허용이 허용되지 않는다면, 반드시 장애에 대해 독립적인 여러개의 서버들을 사용해야한다. 보통, 단일 서버의 복제들은 분산 시스템의 프로세서들로 나눠져 실행되고, 프로토콜은 클라이언트와 복제간의 상호작용을 중재하기 위해 쓰인다. 분산시스템의 프로세서들의 물리적, 전기적 분리는 서버 장애들이 서로 독립적임을 보장한다.

상태 기계[편집]

이후 논의를 위하여 상태 기계는 다음과 같은 값들의 집합으로 정의한다.[2] (밀리 기계와 무어 기계를 참고하라):

  • 상태의 집합
  • 입력의 집합
  • 출력의 집합
  • 전이 함수 (Input × State → State)
  • 출력 함수 (Input × State → Output)
  • 시작이라 불리는 특별한 상태

상태 기계는 시작이라 표시된 상태에서 시작한다. 도착한 각 입력은 새 상태와 출력을 얻기 위해 전이 함수와 출력 함수로 전달된다. 상태는 새로운 입력이 도착할 때까지 안정적으로 유지되며 출력은 적절한 수신기에게 전달된다.

이 논의는 상태 머신이 결정적(deterministic)일 것을 요구한다.즉, 같은 상태 머신의 복사본들은 시작 상태에서 동일한 입력을 받았을 때 동일한 상태와 동일한 출력을 가진다.

상태 기계는 적절한 입력에 대해 어떤 알고리즘으로도 구현될 수 있다. (튜링 기계를 참고). 일반적으로 상태 머신 이중화 기반 시스템은 간단한 에러 복구를 위해 유한 상태 기계를 구현에 사용한다.

장애 허용[편집]

결정론(Determinism)은 장애 허용 제공을 위한 이상적 특징이다. 직관적으로 여러개의 복사본이 존재하면 한 곳에서 일어난 장애는 다른 것들과의 상태 및 출력의 차이로 확인 가능하다.

장애 허용에 필요한 복사본은 최소 3개임을 추론할 수 있다. 하나의 복사본에 장애가 발생하였을 때 그것을 확인하기 위해서는 적어도 상태와 출력을 비교할 2개의 복사본이 필요하기 때문이다.

더 나아가서 복사본 3개로 구성된 시스템은 최대 1개의 장애만 지원한다는 것을 추론할 수 있다. 하나 이상의 복제본이 실패한다면 셋의 상태와 출력이 모두 다를수있으며 어느 것이 정상인지 판별할 수 없게 된다.

일반적으로, F개의 장애를 지원하는 시스템은 2F + 1개의 복제본을 가진다.[3] 추가 복제본은 어떤 본제본이 정확하고 어떤 복제본이 장애가 발생했는지 판별하는 증거로 사용된다. 특수한 사례에선 이 제약을 넘을 수 있다.[4]

앞선 추론들은 복제본들이 메모리 오류나 하드 드라이브 손상과 같은 랜덤한 장애만 겪는 것을 전제로 했다. 기만이나 거짓말, 결탁하는 복제본으로 인한 장애 또한 상태 기계 접근법으로 해결될 수 있다.

실패한 복제본의 정지가 요구되지 않는다는 것을 기억해야한다. 복제본들은 계속 동작하고 의심스럽거나 잘못된 출력을 발생 시킬 수 있다.

특수한 사례: 고장-중단[편집]

이론적으로 실패한 복제본이 출력을 내놓지 않고 정지하는 것을 보장한다면 복재본이 F + 1개만 필요하며 클라이언트는 시스템에서 첫번째로 만들어진 출력을 수용할 수 있다. 이 제약을 만족할 수 있는 시스템은 존재하지 않지만 장애 허용 계층 위에 설계된 시스템을 분석할 때 자주 쓰인다.(장애 허용 계층이 고장-중단 개념을 모든 상위 계층에 제공할 때에 한정된다.)

특수한 사례: 비잔틴 장애[편집]

복제본이 다른 값을 다른 방향으로 전달하는 장애를 비잔틴 장애라 부른다.[5]
비잔틴 장애는 우연, 의심스러운 실패 또는 악의적, 지능적 공격일 수 있다.

2F + 1개의 복제본이 있을 때, 비암호학적 해시를 사용하여 최대 F개의 비악의적 비잔틴 장애를 견딜 수 있다. 하지만 F개의 악의적 공격을 막기 위해선 메시지 서명과 같은 기본적인 암호학 요소가 필요하다. 비암호학적 기술도 악의적 공격을 막을 수 있으나 필요한 복제본이 3F + 1개로 증가한다.

상태 기계 접근법[편집]

앞서 다룬 논의는 상태 기계 측면에서 장애 허용 서비스를 구축하는 간단한 기술을 함축하고 있다 :

  1. 독립적인 여러개의 서버에 상태 기계의 복사본을 둔다.
  2. 상태 기계에 대한 입력으로 번역 가능한 클라이언트 요청을 받는다.
  3. 입력들의 순서를 결정한다.
  4. 각 서버에서 결정된 순서로 입력을 실행한다.
  5. 상태 기계로부터 얻은 출력으로 클라이언트에게 응답한다.
  6. 복재본 간의 상태 및 출력 차이를 감시한다.

상세한 구현 기술은 아래에서 다룬다.

  • 1단계와 2단계는 이 문서의 범위를 벗어나므로 다루지 않는다.
  • 3단계는 핵심적인 작업이다. 입력 순서 정리을 보시오.
  • 4단계는 상태 기계 정의에서 다룬다..
  • 5단계는 결과 전송을 보시오.
  • 6단계는 감사와 장애 탐지를 보시오.

부록은 로깅, 검역소, 재구성과 상태 전이 등 실제 운용되는 시스템에서 사용되는 전형적인 확장에 대해서 논의한다.

입력 순서 정리[편집]

상태 머신의 분산 시스템을 구성에서 핵심적인 단계는 입력의 처리 순서를 정하는 것이다. 동일한 입력이 주어지면 모든 정상 복제본이 같은 상태와 출력에 도달하므로, 입력이 각 복제본에 동일한 순서로 제출되는 것이 필수적이다. 이 분야에는 많은 솔루션이 제안되어 있다.[6][7][8]

가시 채널(Visible Channel )은 시스템에 능동적으로 참여한 두 엔트리 (서버나 클라이언트) 간의 통신 경로이다.

비가시 채널(Hidden Channel)은 시스템에 공개되지 않은 통신 경로이다. 예: 클라이언트 간의 채널은 보통 숨겨져 있다. 전화기를 통한 유저 간의 통신, 또는 두 프로세스 간의 파이프 통신.

모든 통신 경로가 가시 채널일 때 부분적인 전역 순서 (인과 순서)는 통신 패턴으로부터 유추될 수 있다.[9] 인과 순서는 각 서버에 독립적으로 전달된다. 상태 기계에 대한 입력은 인과 순서에 따라 실행될 수 있으며, 정상 복제본에 대하여 상태와 출력의 구성을 보장한다.

공개 시스템에서 비가시 채널이 일반적이며 약한 형태의 순서가 사용되어야한다. 입력의 순서는 가시 채널에 기반한 투표 프로토콜의 결과를 사용하여 결정할 수 있다.

독립적인 엔트리 그룹에 의한 단일 값 투표 문제는 합의라고 불린다. 좀 더 나아가, 일련의 값들이 일련의 합의 작업들로 정해 질 수 있다. 이 문제는 참여자들 또는 그들의 통신 매체가 장애를 겪을 때 어려워진다.

입력은 합의 작업들에 의해 정렬될 수 있으며 이를 (합의 순서)라 한다. 합의 순서는 각 서버에 독립적으로 전달될 수 있다. 상태 기계에 대한 입력은 합의 순서에 의해 따라 실행될 수 있으며, 정상 복제본에서 상태와 출력을 보장한다.

인과 순서와 합의 순서의 최적화
몇가지 경우에선 추가적 정보가 이용 가능하다. (예를 들자면 현재 시각). 이러한 경우에, 메시지 개수, 메시지 라운드를 줄이거나 메시지 크기를 줄여 입력에 대한 인과 순서 또는 합의 순서를 더 효과적으로 정할 수 있다. 더 자세한 내용은 참고문헌을 보시오.[1][10]
상태 기계의 동작이 의미를 가질 때 더욱 최적화가 가능하다. (예를 들어 읽기 명령과 쓰기 명령). 일반화된 팩소스에 대한 참고 문헌을 보시오.[11]

결과 전송[편집]

클라이언트 요청들은 상태 기계에 대한 입력으로 번역되고, 적절한 순서에 따라 출력으로 가공된다. 각 복제본은 독립적으로 출력을 발생시킨다. 정상 복제본은 항상 같은 출력을 발생시킨다. 클라이언트 응답이 전송 가능해지기 전에, 장애 응답은 반드시 걸러져야 한다. 일반적으로 복제본들의 과반수가 같은 응답을 반환할 때 클라이언트에게 응답으로 반환된다.

시스템 장애[편집]

만약 같은 출력을 가진 과반수의 복제본이 없거나 과반수보다 적은 복제본만이 응답한다면, 시스템 장애가 발생한다.
"클라이언트 응답은 반드시 유일해야한다."라는 명제가 성립하지 않는다.

감사와 장애 탐지[편집]

지속적인 계획되지 않은 복제본의 구성은 장애라 불린다. 복제본이 느리게 응답하거나,[12] 상태에 대해 거짓말을 할 경우 장애 증명은 어려워진다.

정상 복제본들은 항상 같은 상태를 지니고 같은 출력을 발생시킨다. 이 법칙은 모든 복제본들의 상태오 출력을 비교하는 것으로 장애 탐지가 가능하게 만든다. 일반적으로 과반의 복제본들과 다른 상태의 출력을 가진 복제본은 장애로 정의된다.

일반적인 구현 방법은 현재 복제본 상태의 체크섬과 최근 출력을 서버들 사이에 전달하는 방법이다. 각 서버는 감사 과정에서 로컬 복제본의 결함을 감지했을 경우 로컬 복제본을 재시작한다.[13] 체크섬에는 암호학적 보안이 필요하지 않다.

로컬 서버가 손상되거나 감사 과정이 장애가 날 경우 복제본은 부정확하게 계속 동작한다. 이 경우는 앞에서 설명한 출력 검열에 의해 처리된다. (결과 전송을 보시오).

부록: 확장들[편집]

입력 로그[편집]

검문소 (Checkpoint)[편집]

재구성[편집]

중단[편집]

참여[편집]

상태 전이[편집]

리더 선출 (팩소스를 위한)[편집]

역사적 배경[편집]

참조[편집]

  1. ↑ 가 나 Schneider, Fred (1990). “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial” (PS). 《ACM Computing Surveys》 22 (4): 299. doi:10.1145/98163.98167. 
  2. ↑ Lamport, Leslie (1978). “The Implementation of Reliable Distributed Multiprocess Systems”. 《Computer Networks》 2: 95–114. doi:10.1016/0376-5075(78)90045-4. 2008년 3월 13일에 확인함. 
  3. ↑ Lamport, Leslie (2004). “Lower Bounds for Asynchronous Consensus”. 
  4. ↑ Lamport, Leslie; Mike Massa (2004). “Cheap Paxos”. 《Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004)》. 
  5. ↑ Lamport, Leslie; Robert Shostak; Marshall Pease (July 1982). “The Byzantine Generals Problem”. 《ACM Transactions on Programming Languages and Systems》 4 (3): 382–401. doi:10.1145/357172.357176. 2007년 2월 2일에 확인함. 
  6. ↑ Lamport, Leslie (1984). “Using Time Instead of Timeout for Fault-Tolerant Distributed Systems”. 《ACM Transactions on Programming Languages and Systems》 6 (2): 254–280. doi:10.1145/2993.2994. 2008년 3월 13일에 확인함. 
  7. ↑ Birman, Kenneth; Thomas Joseph (1987). “Exploiting virtual synchrony in distributed systems”. 《Proceedings of the 11th ACM Symposium on Operating systems principles (SOSP)》 21 (5): 123. doi:10.1145/37499.37515. 2008년 3월 13일에 확인함. 
  8. ↑ Lampson, Butler (1996). “How to Build a Highly Available System Using Consensus”. 2008년 3월 13일에 확인함. 
  9. ↑ Lamport, Leslie (July 1978). “Time, Clocks and the Ordering of Events in a Distributed System”. 《Communications of the ACM》 21 (7): 558–565. doi:10.1145/359545.359563. 2007년 2월 2일에 확인함. 
  10. ↑ Lamport, Leslie (2005). “Fast Paxos”. 
  11. ↑ Lamport, Leslie (2005). “Generalized Consensus and Paxos”. 
  12. ↑ Fischer, Michael J.; Nancy A. Lynch; Michael S. Paterson (1985). “Impossibility of Distributed Consensus with One Faulty Process”. 《Journal of the Association for Computing Machinery》 32 (2): 347–382. doi:10.1145/3149.214121. 2008년 3월 13일에 확인함. 
  13. ↑ Chandra, Tushar; Robert Griesemer; Joshua Redstone (2007). “Paxos Made Live – An Engineering Perspective” (PDF). 《PODC '07: 26th ACM Symposium on Principles of Distributed Computing》. 

외부 링크[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=상태_기계_복제&oldid=35189343"