상태 기계 이중화 - 위키백과, 우리 모두의 백과사전 상태 기계 이중화 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 컴퓨터 과학에서, 상태 기계 이중화 ( state machine replication ) 또는 상태 기계 접근법 ( state machine approach ) 는 서버들을 복사하고 복제된 서버와 클라이언트 간의 상호적용을 조율하는 것으로 장애 허용 서비스를 구현하는 일반적인 방법이다. 이 방법은 복제본 관리 프로토콜을 이해하고 설계하기 위한 틀을 제공한다. [ 1 ] 목차 1 문제의 정의 1. 1 분산 서비스들 1. 2 상태 기계 1. 3 장애 허용 1. 3. 1 특수한 사례 : 실패 정지 1. 3. 2 특수한 사례 : 비잔틴 장애 2 상태 기계 접근법 2. 1 순차 입력 2. 2 결과 전송 2. 3 시스템 장애 2. 4 감사와 장애 탐지 3 부록
을 때, 비암호학적 해시를 사용하여 최대 F개의 비악의적 비잔틴 장애를 견딜 수 있다. 하지만 F개의 악의적 공격을 막기 위해선 메시지 서명과 같은 기본적인 암호학 요소가 필요하다. 비암호학적 기술도 악의적 공격을 막을 수 있으나 필요한 복제본이 3F 1개로 증가한다. 상태 기계 접근법 [ 편집 ] 앞서 다룬 논의는 상태 기계 측면에서 장애 허용 서비스를 구축하는 간단한 기술을 함축하고 있다 : 독립적인 여러개의 서버에 상태 기계의 복사본을 둔다. 상태 기계에 대한 입력으로 번역 가능한 클라이언트 요청을 받는다. 입력들의 순서를 결정한다. 각 서버에서 결정된 순서로 입력을 실행한다. 상태 기계로부터 얻은 출력으로 클라이언트에게 응답한다. 복재본 간의 상태 및 출력 차이를 감시한다. 상세한 구현 기술은 아래
정지 [ 편집 ] 이론적으로, 실패한 복제본이 출력을 내놓지 않고 정지하는 것을 보장한다면 복재본이 F 1개만 필요하며 클라이언트는 스스템에서 첫번째로 만들어진 출력을 수용할 수 있다. 이 제약을 만족할 수 있는 시스템은 존재하지 않지만 장애 허용 계층 위에 설계된 시스템을 분석할 때 자주 쓰인다. ( 장애 허용 계층이 실패 정지 개념을 모든 상위 계층에 제공할 때에 한정된다. ) 특수한 사례 : 비잔틴 장애 [ 편집 ] 복제본이 다른 값을 다른 방향으로 전달하는 장애를 비잔틴 장애라 부른다. [ 5 ] 비잔틴 장애는 우연, 의심스러운 실패 또는 악의적, 지능적 공격일 수 있다. 2F 1개의 복제본이 있을 때, 비암호학적 해시를 사용하여 최대 F개의 비악의적 비잔틴 장애를 견딜 수 있다
상태 기계 접근법 2. 1 순차 입력 2. 2 결과 전송 2. 3 시스템 장애 2. 4 감사와 장애 탐지 3 부록 : 확장들 3. 1 입력 로그 3. 2 검문소 ( Checkpoint ) 3. 3 재구성 3. 4 중단 3. 5 참여 3. 6 상태 전이 3. 7 리더 선출 ( 팩소스를 위한 ) 4 역사적 배경 5 참조 6 외부 링크 문제의 정의 [ 편집 ] 분산 서비스들 [ 편집 ] 분산형 소프트웨어는 종종 고객과 서비스 측면에서 구조화된다. 각 서비스는 하나 이상의 서버들로 구성되고 고객의 요청에 따라 작업을 수행한다. 중앙화된 서버 하나만 사용하는 것이 서비스를 구현하는 가장 간단한 방법이지만 결과물은 서버를 실행시키는 프로세서만큼의 장애허용을 제공한다. 만약 이 수준의 장애 허용이 허용되지 않는다면, 반드시 장애에 대해 독립적인 여러개의 서버
95 - 114. doi : 10. 1016 / 0376 - 5075 ( 78 ) 90045 - 4. 2008년 3월 13일에 확인함. ↑ Lamport, Leslie ( 2004 ). " Lower Bounds for Asynchronous Consensus ". ↑ Lamport, Leslie ; Mike Massa ( 2004 ). " Cheap Paxos ". 《 Proceedings of the International Conference on Dependable Systems and Networks ( DSN 2004 ) 》. ↑ 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.
M 》 21 ( 7 ) : 558 - 565. doi : 10. 1145 / 359545. 359563. 2007년 2월 2일에 확인함. ↑ Lamport, Leslie ( 2005 ). " Fast Paxos ". ↑ Lamport, Leslie ( 2005 ). " Generalized Consensus and Paxos ". ↑ 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일에 확인함. ↑ Chandra,
문단은 비어있습니다. 내용을 추가해 주세요. 역사적 배경 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 참조 [ 편집 ] ↑ 가 나 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. ↑ 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
. 장애 허용 [ 편집 ] 결정론 ( Determinism ) 은 장애 허용 제공을 위한 이상적 특징이다. 직관적으로 여러개의 복사본이 존재하면 한 곳에서 일어난 장애는 다른 것들과의 상태 및 출력의 차이로 확인 가능하다. 장애 허용에 필요한 복사본은 최소 3개임을 추론할 수 있다. 하나의 복사본에 장애가 발생하였을 때 그것을 확인하기 위해서는 적어도 상태와 출력을 비교할 2개의 복사본이 필요하기 때문이다. 더 나아가서 복사본 3개로 구성된 시스템은 최대 1개의 장애만 지원한다는 것을 추론할 수 있다. 하나 이상의 복제본이 실패한다면 셋의 상태와 출력이 모두 다를수있으며 어느 것이 정상인지 판별할 수 없게 된다. 일반적으로, F개의 장애를 지원하는 시스템은 2F 1개의 복제본을 가진다. [ 3 ]
ming Languages and Systems 》 4 ( 3 ) : 382 - 401. doi : 10. 1145 / 357172. 357176. 2007년 2월 2일에 확인함. ↑ 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일에 확인함. ↑ Birman, Kenneth ; Thomas Joseph ( 1987 ). " Exploiting virtual synchrony in distributed systems ". 《 Proceedings of the 11th ACM S
은 상태와 출력에 도달하므로, 입력이 각 복제본에 동일한 순서로 제출되는 것이 필수적이다. 이 분야에는 많은 솔루션이 제안되어 있다. [ 6 ] [ 7 ] [ 8 ] 가시 채널 ( Visible Channel ) 은 시스템에 능동적으로 참여한 두 엔트리 ( 서버나 클라이언트 ) 간의 통신 경로이다. 비가시 채널 ( Hidden Channel ) 은 시스템에 공개되지 않은 통신 경로이다. 예 : 클라이언트 간의 채널은 보통 숨겨져 있다. 전화기를 통한 유저 간의 통신, 또는 두 프로세스 간의 파이프 통신. 모든 통신 경로가 가시 채널일 때 부분적인 전역 순서 ( 인과 순서 ) 는 통신 패턴으로부터 유추될 수 있다. [ 9 ] 인과 순서는 각 서버에 독립적으로 전달된다. 상태 기계에 대한 입력은 인과 순서에 따라 실행 될 수 있으며, 정상 복제본에 대하여 상태
상태 기계 복제(state machine replication) 또는 상태 기계 접근법(state machine approach)는 컴퓨터 과학에서 서버들을 복사하고 복제된 서버와 클라이언트 간의 상호적용을 조율하는 것으로 장애 허용 서비스를 구현하는 일반적인 방법이다. 이 방법은 복제본 관리 프로토콜을 이해하고 설계하기 위한 틀을 제공한다.