엔트리 ( 서버나 클라이언트 ) 간의 통신 경로이다. 비가시 채널 ( Hidden Channel ) 은 시스템에 공개되지 않은 통신 경로이다. 예 : 클라이언트 간의 채널은 보통 숨겨져 있다. 전화기를 통한 유저 간의 통신, 또는 두 프로세스 간의 파이프 통신. 모든 통신 경로가 가시 채널일 때 부분적인 전역 순서 ( 인과 순서 ) 는 통신 패턴으로부터 유추될 수 있다. [ 9 ] 인과 순서는 각 서버에 독립적으로 전달된다. 상태 기계에 대한 입력은 인과 순서에 따라 실행 될 수 있으며, 정상 복제본에 대하여 상태와 출력의 구성을 보장한다. 공개 시스템에서 비가시 채널이 일반적이며 약한 형태의 순서가 사용되어야한다. 입력의 순서는 가시 채널에 기반한 투표 프로토콜의 결과를 사용하여 결정할 수 있다. 독립적인 엔트리 그룹에 의한 단일 값 투표 문제는 합의라고 불린다. 좀 더 나아가, 일련의 값들이 일련의 합의 작업들로 정해 질 수 있다. 이 문제는 참여자들 또는 그들의 통신 매체가 장애를 겪을 때 어려워진다. 입력은 합의 작업들에 의해 정렬될 수 있으며 이를 ( 합의 순서 ) 라 한다. 합의 순서는 각 서버에 독립적으로 전달될 수 있다. 상태 기계에 대한 입력은 합의 순서에 의해 따라 실행 될 수 있으며, 정상 복제본에서 상태와 출력을 보장
과반수의 복제본이 없거나 과반수보다 적은 복제본만이 응답한다면, 시스템 장애가 발생한다. " 클라이언트 응답은 반드시 유일해야한다. " 라는 명제가 성립하지 않는다. 감사와 장애 탐지 [ 편집 ] 지속적인 계획되지 않은 복제본의 구성은 장애라 불린다. 복제본이 느리게 응답하거나, [ 12 ] 상태에 대해 거짓말을 할 경우 장애 증명은 어려워진다. 정상 복제본들은 항상 같은 상태를 지니고 같은 출력을 발생시킨다. 이 법칙은 모든 복제본들의 상태오 출력을 비교하는 것으로 장애 탐지가 가능하게 만든다. 일반적으로 과반의 복제본들과 다른 상태의 출력을 가진 복제본은 장애로 정의된다. 일반적인 구현 방법은 현재 복제본 상태의 체크섬과 최근 출력을 서버들 사이에 전달하는 방법이다. 각 서버는 감사 과정에서 로컬 복제본의 결함을 감지했을 경우 로컬 복제본을 재시작한다. [ 13 ] 체크섬에는 암호학적 보안이 필요하지 않다. 로컬 서버가 손상되거나 감사 과정이 장애가 날 경우 복제본은 부정확하게 계속 동작한다. 이 경우는 앞에서 설명한 출력 검열에 의해 처리된다. ( 결과 전송을 보시오 ). 부록 : 확장들 [ 편집 ] 입력 로그 [ 편집 ] 이 문단은 비어있습니다. 내용
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 Symposium on Operating systems principles ( SOSP ) 》 21 ( 5 ) : 123. doi : 10. 1145 / 37499. 37515. 2008년 3월 13일에 확인함. ↑ Lampson, Butler ( 1996 ). " How to Build a Highly Available System Using Consensus ". 2008년 3월 13일에 확인함. ↑ Lamport, Leslie ( July 1978 ). " Time, Clocks and the Ordering of Events in a Distributed System ". 《 Communications
수 있다. 상태 기계에 대한 입력은 합의 순서에 의해 따라 실행 될 수 있으며, 정상 복제본에서 상태와 출력을 보장한다. 인과 순서와 합의 순서의 최적화 몇가지 경우에선 추가적 정보가 이용 가능하다. ( 예를 들자면 현재 시각 ). 이러한 경우에, 메시지 개수, 메시지 라운드를 줄이거나 메시지 크기를 줄여 입력에 대한 인과 순서 또는 합의 순서를 더 효과적으로 정할 수 있다. 더 자세한 내용은 참고문헌을 보시오. [ 1 ] [ 10 ] 상태 기계의 동작이 의미를 가질 때 더욱 최적화가 가능하다. ( 예를 들어 읽기 명령과 쓰기 명령 ). 일반화된 팩소스에 대한 참고 문헌을 보시오. [ 11 ] 결과 전송 [ 편집 ] 클라이언트 요청들은 상태 기계에 대한 입력으로 번역되고, 적절한 순서에 따라 출력으로 가공된다. 각 복제본은 독립적으로 출력을 발생시킨다. 정상 복제본은 항상 같은 출력을 발생시킨다. 클라이언트 응답이 전송 가능해지기 전에, 장애 응답은 반드시 걸러져야 한다. 일반적으로 복제본들의 과반수가 같은 응답을 반환할 때 클라이언트에게 응답으로 반환된다. 시스템 장애 [ 편집 ] 만약 같은 출력을 가진 과반수의 복제본이 없거나 과반수보다 적은 복제본만이 응답한다면, 시스템 장애가 발생한다. " 클라이언트 응답은
##는다. 입력들의 순서를 결정한다. 각 서버에서 결정된 순서로 입력을 실행한다. 상태 기계로부터 얻은 출력으로 클라이언트에게 응답한다. 복재본 간의 상태 및 출력 차이를 감시한다. 상세한 구현 기술은 아래에서 다룬다. 1단계와 2단계는 이 문서의 범위를 벗어나므로 다루지 않는다. 3단계는 핵심적인 작업이다. 순차 입력을 보시오. 4단계는 상태 기계 정의에서 다룬다.. 5단계는 순차 출력을 보시오. 6단계는 감사와 장애 탐지를 보시오. 부록은 로깅, 검역소, 재구성과 상태 전이 등 실제 운용되는 시스템에서 사용되는 전형적인 확장에 대해서 논의한다. 순차 입력 [ 편집 ] 상태 머신의 분산 시스템을 구성에서 핵심적인 단계는 입력의 처리 순서를 정하는 것이다. 동일한 입력이 주어지면 모든 정상 복제본이 같은 상태와 출력에 도달하므로, 입력이 각 복제본에 동일한 순서로 제출되는 것이 필수적이다. 이 분야에는 많은 솔루션이 제안되어 있다. [ 6 ] [ 7 ] [ 8 ] 가시 채널 ( Visible Channel ) 은 시스템에 능동적으로 참여한 두 엔트리 ( 서버나 클라이언트 ) 간의 통신 경로이다. 비가시 채널 ( Hidden Channel ) 은 시스템에 공개되
##은 새 상태와 출력을 얻기 위해 전이 함수와 출력 함수로 전달된다. 상태는 새로운 입력이 도착할 때까지 안정적으로 유지되며 출력은 적절한 수신기에게 전달된다. 이 논의는 상태 머신이 결정적 ( deterministic ) 일 것을 요구한다. 즉, 같은 상태 머신의 복사본들은 시작 상태에서 동일한 입력을 받았을 때 동일한 상태와 동일한 출력을 가진다. 상태 기계는 적절한 입력에 대해 어떤 알고리즘으로도 구현될 수 있다. ( 튜링 기계를 참고 ). 일반적으로 상태 머신 이중화 기반 시스템은 간단한 에러 복구를 위해 유한 상태 기계를 구현에 사용한다. 장애 허용 [ 편집 ] 결정론 ( Determinism ) 은 장애 허용 제공을 위한 이상적 특징이다. 직관적으로 여러개의 복사본이 존재하면 한 곳에서 일어난 장애는 다른 것들과의 상태 및 출력의 차이로 확인 가능하다. 장애 허용에 필요한 복사본은 최소 3개임을 추론할 수 있다. 하나의 복사본에 장애가 발생하였을 때 그것을 확인하기 위해서는 적어도 상태와 출력을 비교할 2개의 복사본이 필요하기 때문이다. 더 나아가서 복사본 3개로 구성된 시스템은 최대 1개의 장애만 지원한다는 것을 추론할 수 있다. 하나 이상의 복제본이 실패한다면
. ( 결과 전송을 보시오 ). 부록 : 확장들 [ 편집 ] 입력 로그 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 검문소 ( Checkpoint ) [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 재구성 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 중단 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 참여 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 상태 전이 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 리더 선출 ( 팩소스를 위한 ) [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 역사적 배경 [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 참조 [ 편집 ] ↑ 가 나 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 Rel
] 분산형 소프트웨어는 종종 고객과 서비스 측면에서 구조화된다. 각 서비스는 하나 이상의 서버들로 구성되고 고객의 요청에 따라 작업을 수행한다. 중앙화된 서버 하나만 사용하는 것이 서비스를 구현하는 가장 간단한 방법이지만 결과물은 서버를 실행시키는 프로세서만큼의 장애허용을 제공한다. 만약 이 수준의 장애 허용이 허용되지 않는다면, 반드시 장애에 대해 독립적인 여러개의 서버들을 사용해야한다. 보통, 단일 서버의 복제들은 분산 시스템의 프로세서들로 나눠져 실행되고, 프로토콜은 클라이언트와 복제간의 상호작용을 중재하기 위해 쓰인다. 분산시스템의 프로세서들의 물리적, 전기적 분리는 서버 장애들이 서로 독립적임을 보장한다. 상태 기계 [ 편집 ] 이후 논의를 위하여 상태 기계는 다음과 같은 값들의 집합으로 정의한다. [ 2 ] ( 밀리 기계와 무어 기계를 참고하라 ) : 상태의 집합 입력의 집합 출력의 집합 전이 함수 ( Input x State → State ) 출력 함수 ( Input x State → Output ) 시작이라 불리는 특별한 상태 상태 기계는 시작이라 표시된 상태에서 시작한다. 도착한 각 입력은 새 상태와 출력을 얻기 위해 전이 함수와 출력 함수로 전달된다. 상태는 새로운 입력이 도착할 때까지 안정
/ 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월 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. 1145 / 357172. 357176. 2007년 2월 2일에 확인함. ↑ Lamport, Leslie ( 1984 ). " Using Time Instead of
Perspective " ( PDF ). 《 PODC'07 : 26th ACM Symposium on Principles of Distributed Computing 》. 외부 링크 [ 편집 ] Replicated state machines video on MIT TechTV Apache Bookkeeper a replicated log service which can be used to build replicated state machines 원본 주소 " " 분류 : 분산 컴퓨팅데이터 동기화숨은 분류 : 영어 표기를 포함한 문서빈 문단이 포함된 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 English 中 文 링크 편집 이 문서는 2019년 5월 12일 ( 일 ) 13 : 11에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수
상태 기계 복제(state machine replication) 또는 상태 기계 접근법(state machine approach)는 컴퓨터 과학에서 서버들을 복사하고 복제된 서버와 클라이언트 간의 상호적용을 조율하는 것으로 장애 허용 서비스를 구현하는 일반적인 방법이다. 이 방법은 복제본 관리 프로토콜을 이해하고 설계하기 위한 틀을 제공한다.