상태 컴퓨터 복제

State machine replication

컴퓨터 과학에서 상태 기계 복제(SMR) 또는 상태 기계 접근법은 서버를 복제하고 서버 복제본과 클라이언트 상호작용을 조정하여 오류 방지 서비스를 구현하기 위한 일반적인 방법이다.또한 이 접근방식은 복제 관리 프로토콜을 이해하고 설계하기 위한 프레임워크를 제공한다.[1]

문제 정의

분산서비스

고객 및 서비스 측면에서각 서비스는 하나 이상의 서버로 구성되며 클라이언트가 요청하여 호출하는 작업을 내보낸다.중앙 집중식 단일 서버를 사용하는 것이 서비스를 구현하는 가장 간단한 방법이지만, 결과 서비스는 해당 서버를 실행하는 프로세서만큼 내결함성이 있을 수 밖에 없다.이 수준의 내결함성을 허용할 수 없는 경우, 독립적으로 장애가 발생하는 여러 서버를 사용할 수 있다.일반적으로, 단일 서버의 복제본은 분산 시스템의 별도 프로세서에서 실행되며, 프로토콜은 이러한 복제본과의 클라이언트 상호작용을 조정하는데 사용된다.

상태 기계

주요 기사:유한 상태 기계

이후 논의를 위해 상태 기계는 다음과 같은 값의 튜플로 정의된다(Mealy 기계 및 Moore Machine 참조).

  • 주의 집합
  • 입력 집합
  • 출력 세트
  • 전환 함수(입력 × State → State)
  • 출력 함수(입력 × 상태 → 출력)
  • Start라고 불리는 유수한 주입니다.

State Machine은 Start라는 레이블이 붙은 상태에서 시작한다.수신된 각 입력은 전환 및 출력 기능을 통해 전달되어 새로운 상태와 출력을 생성한다.상태는 새로운 입력이 수신될 때까지 안정적으로 유지되며, 출력은 적절한 수신기로 전달된다.

이 논의는 State Machine이 결정론적이어야 하는데, 동일한 State Machine의 여러 복사본이 Start 상태에서 시작되며, 동일한 순서로 동일한 Inputs를 수신하면 동일한 Outputs를 생성한 동일한 State에 도착한다는 것이다.

일반적으로 State Machine Replication에 기반한 시스템은 오류 복구를 단순화하기 위해 유한 상태 기계를 사용하도록 구현을 자발적으로 제한한다.

내결함성

결정론은 고장 내구성을 제공하기 위한 이상적인 특성이다.직관적으로, 한 시스템의 여러 복사본이 존재하는 경우, 한 시스템의 결함은 다른 시스템과의 상태 또는 출력 차이로서 눈에 띈다.

약간의 추리는 결함 허용에 필요한 최소 사본의 수를 보여준다. 하나는 결함이 있고 다른 하나는 State와 Output을 비교하는 것이다.어느 카피가 불량인지 알 길이 없어 두 장으로는 부족하다.

추가 추정을 보면 3부 시스템이 최대 1부 고장을 지원할 수 있다는 것을 보여준다(이후에는 고장 난 사본을 수리하거나 교체해야 한다).사본 중 두 부 이상이 고장날 경우, 세 개의 상태와 출력부가 모두 다를 수 있으며, 어느 것이 올바른 것인지 선택할 방법이 없을 것이다.

일반적으로 F 장애를 지원하는 시스템은 2F+1 복사본(복제본이라고도 함)[3]을 가져야 한다.여분의 사본은 그 사본들 중 어느 것이 정확하고 어떤 것이 결함이 있는지를 결정하기 위한 증거로 사용된다.특별한 경우는 이러한 한계를 개선할 수 있다.[4]

이 모든 추론은 복제본이 메모리 오류나 하드 드라이브 충돌과 같은 임의의 독립적 결함만을 경험하고 있다는 것을 미리 보장한다.거짓말을 하거나 속이거나 결탁하려는 복제본에 의해 야기되는 실패는 State Machine 접근법에 의해 처리될 수 있으며, 분리된 변경사항도 있다.

실패한 복제본은 중지할 필요가 없으며, 가짜 또는 잘못된 출력을 생성하는 것을 포함하여 계속 작동할 수 있다.

특수 케이스: 페일스톱

이론적으로, 실패한 복제본이 출력물을 생성하지 않고 정지하도록 보장된 경우, F+1 복제본만 요구되며, 클라이언트는 시스템에서 생성된 첫 번째 출력을 받아들일 수 있다.기존 시스템은 이 한계를 달성하지 못하지만, 단층 내 계층 위에 구축된 시스템을 분석할 때 자주 사용된다(단층 내결함성 계층은 그 위의 모든 계층에 페일 스톱 의미론을 제공하기 때문이다).

특별한 경우: 비잔틴 실패

복제본이 서로 다른 방향으로 다른 값(예를 들어, 일부 동료 복제본에 대한 올바른 출력 및 다른 복제본에 대한 잘못된 출력)을 보내는 결함을 비잔틴 실패라고 한다.[5]비잔틴 실패는 무작위, 가짜 결함 또는 악의적이고 지능적인 공격일 수 있다. 2F+1 복제본은 비결정학적 해시가 있는 것으로 모든 비악의 비잔틴 실패에서 살아남기에 충분하다(높은 확률).악의적인 공격은 2F+1(메시지 서명을 사용하여)을 달성하려면 암호 원형이 필요하거나 비암호화 기법을 적용할 수 있지만 복제본을 3F+1로 늘려야 한다.[5]

State Machine 접근 방식

앞서 언급한 직관적인 논의는 상태 기계의 관점에서 내결함성 서비스를 구현하기 위한 간단한 기술을 의미한다.

  1. 상태 시스템의 복사본을 여러 독립 서버에 배치하십시오.
  2. State Machine에 대한 입력으로 해석된 클라이언트 요청 수신
  3. 입력에 대한 순서를 선택하십시오.
  4. 각 서버에서 선택한 순서대로 입력 실행
  5. State Machine의 Output을 사용하여 클라이언트에 응답하십시오.
  6. 상태 또는 출력의 차이점에 대한 복제본 모니터링

이 글의 나머지 부분은 이 기법의 세부사항을 전개한다.

부록에는 로깅, 체크포인트, 재구성 및 상태 전송과 같은 실제 시스템에 사용되는 일반적인 확장에 대한 논의가 포함되어 있다.

입력 순서 지정

상태 머신의 분산 시스템을 구축하는 데 있어 중요한 단계는 입력을 처리할 순서를 선택하는 것이다.모든 오류 없는 복제본은 동일한 입력이 주어진 경우 동일한 상태와 출력에 도달하므로, 각 복제본에서 동일한 순서로 입력을 제출하는 것이 필수적이다.문헌에는 많은 해결책이 제시되어 있다.[2][6][7][8][9]

Visible Channel은 시스템에 적극적으로 참여하는 두 실체(예: 클라이언트와 서버) 간의 통신 경로다.예: 클라이언트에서 서버로, 서버에서 서버로

Hidden Channel은 시스템에 드러나지 않는 통신 경로다.예: 클라이언트와 클라이언트 채널은 일반적으로 숨겨져 있다. 예를 들어, 전화를 통해 통신하는 사용자나 다른 프로세스에 의해 읽히는 디스크에 파일을 쓰는 프로세스와 같이.

모든 통신 경로가 가시적 채널이고 숨겨진 채널이 존재하지 않는 경우, 통신의 패턴으로부터 부분적 글로벌 순서(Causion Order)를 유추할 수 있다.[8][10]인과 순서는 각 서버에 의해 독립적으로 도출될 수 있다.상태 기계에 대한 입력은 모든 결함 없는 복제본에 대해 일관적인 상태 및 출력을 보장하는 인과적 순서로 실행될 수 있다.

개방형 시스템에서는 숨겨진 채널이 일반적이며, 더 약한 형태의 순서를 사용해야 한다.입력 순서는 결과가 가시적 채널에만 의존하는 투표 프로토콜을 사용하여 정의할 수 있다.

독립된 단체들의 집단에 의한 단일 가치에 투표하는 문제를 컨센서스라고 한다.확장자에 의해 일련의 값은 일련의 합의된 예에 의해 선택될 수 있다.참가자나 그들의 의사소통 매체가 실패를 경험할 수 있을 때 이 문제는 어려워진다.[3]

입력은 일련의 합의 사례(Consension Order)에서 그들의 위치에 의해 명령될 수 있다.[7]컨센서스 오더는 각 서버에 의해 독립적으로 도출될 수 있다.상태 기계에 대한 입력은 모든 결함 없는 복제본에 대해 일관적인 상태 및 출력을 보장하는 합의 순서에 따라 실행될 수 있다.

인과관계 및 합의 순서 최적화
어떤 경우에는 (실시간 시계와 같은) 추가 정보를 이용할 수 있다.이러한 경우, 메시지 수 감소, 메시지 회진 감소 또는 메시지 크기 감소로 입력에 대한 보다 효율적인 인과관계 또는 합의 순서를 달성할 수 있다.자세한 내용은 참조 참조
상태 기계 작동의 의미론(예: 읽기 대 쓰기 작업)을 설명할 때 추가 최적화를 이용할 수 있다.참고문헌 일반 팩소 참조.Paxos)를 참조하십시오.[2][12]

출력 전송

클라이언트 요청은 State Machine에 대한 입력으로 해석되어 적절한 순서로 Outputs로 처리된다.각 복제본은 독립적으로 출력을 생성한다.오류가 없는 복제본은 항상 동일한 출력을 생성한다.클라이언트 응답을 전송하기 전에 결함이 있는 출력을 필터링해야 한다.일반적으로, 대부분의 복제본은 동일한 출력을 반환하며, 이 출력은 클라이언트에 대한 응답으로 전송된다.

시스템 오류

동일한 출력을 가진 대부분의 복제본이 없거나, 또는 대다수의 복제본이 출력을 반환하는 경우, 시스템 오류가 발생한 것이다.클라이언트 응답은 고유한 출력: FAIL이어야 한다.

감사 및 실패 탐지

복제본의 영구적이고 계획되지 않은 타협을 실패라고 부른다.실패에 대한 증거는 얻기 어렵다. 왜냐하면 복제본이 단지 느리게 반응하거나 [13]심지어 그것의 상태에 대해 거짓말을 할 수도 있기 때문이다.[5]

오류 없는 복제본은 항상 동일한 상태를 포함하고 동일한 출력을 생성한다.이 불변제는 모든 복제본의 Status와 Outputs를 비교하여 장애 감지를 가능하게 한다.일반적으로 대부분의 복제본과 다른 상태 또는 출력이 있는 복제본은 오류로 선언된다.

일반적인 구현은 서버 간에 현재 복제본 상태 및 최근 출력물의 체크섬을 전달하는 것이다.각 서버의 감사 프로세스는 편차가 탐지된 경우 로컬 복제본을 재시작한다.[14]체크섬에는 암호 보안이 필요하지 않다.

로컬 서버가 손상되었거나 감사 프로세스가 잘못되어 복제본이 계속 잘못 작동하고 있을 가능성이 있다.이 경우는 앞에서 설명한 출력 필터에 의해 안전하게 처리된다(출력 전송 참조).

부록: 확장자

입력 로그

고장이 없는 시스템에서는 State Machine에 의해 처리된 후 입력을 폐기할 수 있다.현실적인 배포는 메시지 손실, 네트워크 파티션 및 저속 프로세서와 같은 시스템의 일시적인 비고장 동작을 보상해야 한다.[14]

한 가지 기법은 입력 시리즈를 로그에 저장하는 것이다.일시적인 동작의 시간 동안, 복제본은 누락된 입력을 채우기 위해 다른 복제본에서 로그 항목의 복사본을 요청할 수 있다.[7]

일반적으로 로그는 지속적일 필요가 없다(기억에 보관될 수 있다).영구 로그는 장기간의 과도 기간을 보상하거나 체크포인트 및 재구성 등의 추가 시스템 기능을 지원할 수 있다.

체크포인트

선택하지 않은 상태로 두면 사용 가능한 모든 스토리지 리소스가 소진될 때까지 로그가 커진다.계속 작동하려면 로그 항목을 잊어버려야 한다.일반적으로 로그 항목은 내용이 더 이상 관련되지 않을 때 잊혀질 수 있다(예를 들어, 모든 복제본에서 입력을 처리한 경우, 입력에 대한 지식이 더 이상 필요하지 않음).

로그 크기를 제어하는 일반적인 기술은 중복된 상태(검문소라 함)를 저장한 다음 체크포인트에 기여하는 로그 항목을 삭제하는 것이다.이렇게 하면 중복된 상태가 로그 크기보다 작을 때 공간이 절약된다.

체크포인트는 Checkpoint라는 추가 입력을 지원하여 State Machine에 추가될 수 있다. 각 복제본은 현재 상태 값 외에 체크포인트를 유지한다.로그가 커지면 복제본은 클라이언트 요청과 마찬가지로 체크포인트 명령을 제출한다.시스템은 결함이 없는 복제본이 동일한 순서로 이 명령을 처리하도록 보장하며, 이후 체크포인트를 삭제하기 전의 모든 로그 항목이 삭제될 수 있다.

체크포인트가 있는 시스템에서는 체크포인트가 무시되기 전에 발생하는 로그 항목 요청.필요한 로그 항목의 복사본을 찾을 수 없는 복제본은 결함이 있으며 시스템을 다시 결합해야 한다(재구성 참조).

재구성

재구성을 통해 클라이언트 요청이 계속 처리되는 동안 시스템에서 복제본을 추가 및 제거할 수 있다.계획된 유지보수 및 복제본 오류는 재구성의 일반적인 예다.재구성은 탈퇴와 가입을 포함한다.

그만두다

서버가 State 또는 Output에 결함이 있는 경우(Auditing and Failure Detection 참조), 선택적으로 시스템을 종료할 수 있다.마찬가지로 관리자는 유지보수용 복제본을 삭제하는 명령을 수동으로 실행할 수 있다.

새로운 입력이 State Machine에 추가되며,[2][6] 복제본은 클라이언트 요청과 마찬가지로 이 명령을 시스템에 제출한다.오류가 없는 모든 복제본은 입력을 처리할 때 시스템에서 종료 복제본을 제거하십시오.이 시간 동안 복제본은 모든 프로토콜 메시지를 무시할 수 있다.오류가 없는 복제본이 다수 남아 있으면 종료가 성공한다.그렇지 않으면 시스템 장애가 있다.

가입

서버를 종료한 후, 장애가 발생한 서버는 선택적으로 시스템을 재시작하거나 재조명할 수 있다.마찬가지로, 관리자는 추가 용량을 위해 그룹에 새로운 복제본을 추가할 수 있다.

새로운 입력이 JOIN이라는 상태 시스템에 추가된다.복제본은 클라이언트 요청과 마찬가지로 이 명령을 시스템에 제출한다.모든 오류 없는 복제본은 입력을 처리할 때 시스템에 결합 노드를 추가한다.새 복제본은 가입하기 전에 시스템 상태(State Transfer)에서 최신 상태여야 한다(State Transfer(State Transfer)

국가 이전

새 복제본을 사용할 수 있게 만들거나 이전 복제본을 재시작할 경우 입력을 처리하기 전에 현재 상태로 전환해야 한다(가입 참조).논리적으로 이것은 시스템 새벽부터 모든 입력을 적절한 순서로 적용해야 한다.

일반적인 배포는 가장 최근의 체크포인트의 상태 전송을 수행하여 논리적 흐름을 단락시킨다(체크포인트 참조).여기에는 대역 외 프로토콜을 사용하여 한 복제본의 상태를 다른 복제본에 직접 복사하는 작업이 포함된다.

체크포인트가 클 수 있으므로 전송 기간이 길어야 한다.이 시간 동안 새로운 입력을 로그에 추가할 수 있다.이런 경우, 새로운 복제본도 새로운 입력을 수신하고 체크포인트를 수신한 후 이를 적용해야 한다.일반적인 배포는 상태 전송을 시작하기 전에 새 복제본을 순서 프로토콜에 관찰자로 추가하므로, 새 복제본이 이 기간 동안 입력을 수집할 수 있다.

상태 전송 최적화

공통 배포는 서로 다른 상태 구성 요소만 전송하여 상태 전송 시간을 단축한다.이것은 State Machine의 내부 지식을 필요로 한다.국가 이전은 대개 대역 외 프로토콜이기 때문에, 이러한 가정은 달성하기 어렵지 않다.

압축은 상태 전송 프로토콜에 일반적으로 추가되는 또 다른 기능으로, 전체 전송의 크기를 줄인다.

지도자 선거(팩소스의 경우)

팍소스는[7] 컨센서스 해결을 위한 프로토콜로, 컨센서스 오더 이행을 위한 프로토콜로 활용될 수 있다.

팍소스는 리빙을 보장하기 위해 단 한 명의 리더가 필요하다.[7]즉, 복제품 중 하나는 국가 기계의 다음 작동에 대한 합의를 얻을 수 있을 만큼 충분히 오랫동안 리더로 남아 있어야 한다.시스템 동작은 리더가 매 인스턴스 이후에 변경되거나 리더가 인스턴스당 여러 번 변경되는 경우 영향을 받지 않는다.유일한 요구사항은 하나의 복제본이 시스템을 발전시킬 수 있을 만큼 충분히 오랫동안 리더로 남아 있다는 것이다.

충돌 해결

일반적으로 어떤 작전을 수행할지,[11] 그리고 그 작전이 어떤 식으로든 충돌하는 경우(예를 들어 통근하지 않는 경우)에 대해 이견이 있을 때만 리더가 필요하다.[12]

상충하는 작전이 제안되면 리더는 기록을 바로 세우는 단일 권한으로 작용하여 작업 순서를 규정함으로써 시스템이 진척될 수 있도록 한다.

팍소스와 함께, 여러 복제품들은 그들이 동시에 리더라고 믿을지도 모른다.이 특성은 팍소스를 위한 지도자 선거를 매우 단순하게 만들고, '이벤트 리더'를 보장하는 알고리즘은 모두 작동할 것이다.

역사적 배경

많은 연구자들이 1980년대 초에 복제된 주 기계 접근법에 대한 기사를 발표하였다.Anita Borg는 1983년 논문 "내결함성을 지원하는 메시지 시스템"에서 복제된 상태 시스템을 기반으로 한 내결함성 운영 체제의 구현을 설명했다.레슬리 램포트도 1984년 논문 '분산 시스템에서 시간 초과 대신 시간 사용'에서 주 기계 접근법을 제안했다.Fred Schneider는 나중에 "State Machine 접근법을 사용한 결함 방지 서비스 구현: 자습서"에서 이 접근 방식을 상세히 설명했다.

Ken Birman은 1985년에서 1987년 사이에 발표된 일련의 논문에서 가상의 동기화 모델을 개발했다.이 작품의 일차적 언급은 뉴욕과 스위스 증권거래소 건설에 사용됐던 이시스 툴킷, 프랑스 항공교통관제시스템, 미 해군 이지스함 등 응용분야를 기술한 '분산시스템에서의 가상동기화 탐구'이다.

미겔 카스트로(Miguel Castro)와 바바라 리스크코프의 최근 연구는 램포트의 원래 상태 머신 접근방식을 사용하여 특별히 민감한 서비스를 복제하지만 성능을 실질적으로 향상시키는 최적화와 함께 소위 "실용적인 비잔틴 내결함성" 아키텍처에서 주 머신 접근법을 사용했다.

가장 최근에는 자바에서 개발된 고성능 비잔틴 내결함성 상태 기계 복제 라이브러리인 [15]BFT-SMaRt 라이브러리도 만들어졌다.이 라이브러리는 PBFT와 매우 유사한 프로토콜과 더불어 호스트의 상태 전송 및 즉각적인 재구성(즉, JOIN 및 REACK 작업)을 제공하는 보완 프로토콜을 구현한다.BFT-SMaRt는 주 시스템 복제를 구현하기 위한 가장 최근의 노력이며 여전히 활발하게 유지되고 있다.

합의 기반 알고리즘인 래프트는 2013년 개발됐다.

PBFT에 의해 동기 부여된 Tendermint BFT는[16] 부분 비동기 네트워크용으로 도입되었으며 주로 PoC(Proof of Stake) 블록체인에 사용된다.

참조

  1. ^ a b Schneider, Fred (1990). "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial" (PS). ACM Computing Surveys. 22 (4): 299–319. CiteSeerX 10.1.1.69.1536. doi:10.1145/98163.98167. S2CID 678818.
  2. ^ a b c d Lamport, Leslie (1978). "The Implementation of Reliable Distributed Multiprocess Systems". Computer Networks. 2 (2): 95–114. doi:10.1016/0376-5075(78)90045-4. Retrieved 2008-03-13.
  3. ^ a b Lamport, Leslie (2004). "Lower Bounds for Asynchronous Consensus".
  4. ^ a b Lamport, Leslie; Mike Massa (2004). Cheap Paxos. Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004). pp. 307–314. doi:10.1109/DSN.2004.1311900. ISBN 978-0-7695-2052-0. S2CID 1325830.
  5. ^ a b c Lamport, Leslie; Robert Shostak; Marshall Pease (July 1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. Retrieved 2007-02-02.
  6. ^ a b c Lamport, Leslie (1984). "Using Time Instead of Timeout for Fault-Tolerant Distributed Systems". ACM Transactions on Programming Languages and Systems. 6 (2): 254–280. CiteSeerX 10.1.1.71.1078. doi:10.1145/2993.2994. S2CID 402171. Retrieved 2008-03-13.
  7. ^ a b c d e Lamport, Leslie (May 1998). "The Part-Time Parliament". ACM Transactions on Computer Systems. 16 (2): 133–169. doi:10.1145/279227.279229. S2CID 421028. Retrieved 2007-02-02.
  8. ^ a b 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. hdl:1813/6651.
  9. ^ Lampson, Butler (1996). "How to Build a Highly Available System Using Consensus". Retrieved 2008-03-13.
  10. ^ 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. S2CID 215822405. Retrieved 2007-02-02.
  11. ^ a b Lamport, Leslie (2005). "Fast Paxos".
  12. ^ a b Lamport, Leslie (2005). "Generalized Consensus and Paxos". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  13. ^ 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. S2CID 207660233. Retrieved 2008-03-13.
  14. ^ a b Chandra, Tushar; Robert Griesemer; Joshua Redstone (2007). Paxos Made Live – An Engineering Perspective (PDF). PODC '07: 26th ACM Symposium on Principles of Distributed Computing. pp. 398–407. doi:10.1145/1281100.1281103. ISBN 9781595936165. S2CID 207164635.
  15. ^ BFT-SMaRt.BFT-SMaRt 복제 라이브러리의 Google 코드 저장소.
  16. ^ Buchman, E.; Kwon, J.; Milosevic, Z. (2018). "The latest gossip on BFT consensus". arXiv:1807.04938 [cs.DC].

외부 링크