분산시스템의 결함 허용 (Fault Tolerance)

Fault Tolerance Basic Concepts

○ Fault Tolerance: 분산시스템상 어느 정도 Fault가 발생해도 시스템이 Crash 되지 않음

○ Fault Tolerance의 Dependability (Fault Tolerance의 요소)

 - 가용성(Availability)

 - 신뢰성(Reliability)

 - 안정성(Safety)

 - 유지보수성(Maintenance)

Failure Models

 

○ Failure의 유형

 - CrashFailure: 한 시스템 또는 전체가 중단됨

 - OmissionFailure: 생략, 요청에 대한 응답 실패

     • Receive Omission: 메시지 수신 실패

     • Send Omission: 메시지 전송 실패

 - Timing Failure: 시간 초과, Time Interval 이내에 응답 실패

 - Response Failure: 부정확한 응답

     • Value Failure: 응답의 Value가 잘못됨

     • State Transition Failure: 제어 흐름이 엉뚱한 곳으로 전개됨(Algorithm or Logic의 문제)

 - Arbitrary Failure: 예상하지 못한 Failure

     • ex. BFT(Byzantine Fault Tolerance)

 

 

Failure Masking by Redundancy 

○ Redundancy:Failure를극복하는방법의 하나

○ Redundancy환경에서의FailureMasking원리

   1) 어떤 Node에 Fail이 발생함

   2) Vote에 연결된 Redundancy의 절반 이상 정상이면 정상, 아니면 Fail을 결정

○ Failure Masking의 한계: Overhead 발생

 

 

 

Figure 8-2

똑같은 컴포넌트를 중복해서 같는다

Voter: A2가 고장나더라도 A1과 A3가 과반수 이상 동작하므로 문제없이 돌아간다.

단 오버헤드가 크다.

 

 

 

 

Flat Group versus Hierarchical Groups

그룹핑방법: FlatGorups / Hierarchical Groups

 

 

 

 

○ Flat Group

 - 특징: Group 내 Peer들이 Mesh 형태로 연결 되어있어 구현 및 동작이복잡

 - 동작: Peer 간 합의(Agreement)를 통해 Communication

 

○ Hierarchical Group 

- 특징   

   • Group 내 Peer들이 하나의 Coordinator 에 연결되어 있음   

   • Flat에 비해 구현 및 동작이 간단   

   • Coordinator Crash 시 전체 시스템 Crash 

- 동작: Coordinator를 통해 Communication

 

 

Agreement in Faulty Systems

○ Agreement: Flat Group에서 Fail 시 Peer 간 합의 방법

 

○ 분산시스템 내 합의의 고려사항 

- 동기 vs. 비동기 (Synchronous vs. Asynchronous) 

- 통신 지연 시간이 고정적 or 가변적(무한대) (Communication Delay is Bounded or Not) 

- 메시지 전송이 순차적 or 비순차적 (Message Delivery is ordered or not) 

- 메시지 전달이 Unicasting or Multicasting (Message transmission is Unicasting(1:1) or Multicasting(1:N))

○ 이러한 고려요소 때문에 일반적으로 분산시스템 내에서 합의가 어려움

 

 

 

 

 

X= 합의가능 빈칸= 합의불가능

 

 

 

 

○ K-FT(Fault Tolerance) : K만큼 고장이 생겨도 정상적으로 작동할 수 있다.

- 비잔틴 합의에서 유래, 다른 말로 BFT(Byzantine Fault Tolerance)라고 부름   

   • Block Chain에서는 이를 발전시켜 PBFT(Practical BFT)를 사용

 

Figure 8-5 (3)번 그림

1. 각자 나머지에게 자신의 값을 보낸다.

2. Vector 형태로 수집

3. Vector -> Broadcasting

4. 합의 (과반수) 4개의 스텝구성

 

 

Figure 8-5 (4)번 그림

1. Flat Group 내 Peer 들은 자신의 값을 서로 교환함 (이때 3번 Peer가 정수형이 아닌 Char형을 전송(Fail))

2. 모든 Peer 들은 전송받은 값에 대해 각 Peer에 대응하는 Vector 형태로 저장

3. 자신의 vector를 자신을 제외한 모든 Peer에게 Broadcasting 

4. Vector를 비교하여 절반 이상 같은 값을 갖는다면 합의

K-FT의 성립조건

- 정상 Peer의 수 ≥ 2k???? +???? 1????

 

 

Figure 8-5 (5)번 그림

2개라 비교합의가 되지 않는다.

 

 

 

PBFT

○ BFT는 동기환경에서만  동작하지만 PBFT는 비동기환경에서도 동작

○ BFT에 대응하는 PBFT 동작

 

 

[그림 설명 - PBFT]

- C : Client , 0 : Primary Replica

① Reqeust : Client 가 상태 변환을 요청하는 Request 메시지를 Primary (0) 에게 전송한다.

② Pre-Prepare : Primary 는 나머지 모든 Node 에게 메시지를 전송한다.

③ Prepare : 메시지를 받고 문제가 없는 경우 (1,2 번 Node) 는 자신의 값을 다른 Node 에 전송한다

④ Commit : Pre-Prepare 메시지와 Prepare 메시지를 수집, 합의를 한 후 결과를 모든 Node에 전송한다.

⑤ Reply : 최종 합의 결과를 Client 에 전송한다.

 

 

RPC (remote procedure call) SemanticsinthePresenceof Failures

 

○ RPC 환경에서 발생할 수 있는 5가지 Failure 

- 클라이언트가 서버의 위치를 알 수 없음 

- 클라이언트의 요청 메시지가 서버에 도달 전 손실 

- 요청을 수신한 서버가 Crash ☆

- 서버의 응답 메시지가 클라이언트에 도달 전 손실 

- 클라이언트가 응답을 수신하고 Crash

 

서버크래쉬의 경우

 

 

 

Server Crashes(1)

(a) 일반적 상황

(b) 실행후 크래시

(c) 실행전 크래시

 

 

Server Crashe 시 메시지 보증 전략​

- At Least Once : 적어도 한번 실행 시킨다. Clinet 가 요청을 확실하게 받았다고 응답할 때 까지 보낸다.

- At Most Once : 최대 한번만 수행해야한다. 못받은 것과는 무관하게 한번만 요청을 보내고 끝낸다.

- Guarantee Nothing : 아무것도 없을을 보증한다. Server Crashe 가 발생하면 클라이언트는 어떤 도움도 얻지 않고, 무엇이 발생한 건지도 모른다. 구현하기 가장 쉽다.

- Exactly Once : 정확하게 한 번의 메시지 전송을 보증한다. 중복과 유실을 허용하지 않기 때문에 구현이 어렵다. (BEST CASE)

 

 

​

Server Crashes (2) & Server Crashes (3)

○ 서버 Crash는 요청에 대한 처리를 수행하기 전과 처리를 수행한 뒤인가에 따라서 다름

 - 3가지 Event로 살펴 본 Crash 동작   

* M: Message 수신, P: Print, C: Crash   3!

   • Crash가 나중에 일어남 M→P→C or P→M→C (시스템 영향이 가장 적음, Best)   

   • Crash가 중간에 일어남 M→C(→P) or P→C(→M) (괄호 안의 작업은 수행되지 못함)   

   • Crash가 처음부터 일어남 C(→M→P) or C(→P→M) (모든 작업이 수행되지 못함, Worst)

○ Fault에 대한 서버의 4가지 동작 방식 

- at least once: 적어도 한 번 이상 재시도를 함 

- at most once: 많아야 한 번 재시도 

- Guarantee Nothing: Fault를 무시 

- Exactly Once: 오직 한번에 완료 (Best Case)

○ Fault 동작에 따라 동일한 작업이 한 번에 끝 날 수도 반복될 수도 있음

 

Server Crashes (4)

Strategy M->P 피른트 이전 메시지 (비동기방식)

Strategy P->M 프린트 이후 메시지 (동기방식)

 

 

- Always (문제 발생 시 항상 요청), Never (다시 요청 안함), Only When ACKed (Acked일 때 리이슈), Only when not ACKed (Acked가 없을 경우 리이슈)

- 4가지 재 요청 방식 중 어떤 것을 채택하더라도 모든 경우 OK 가 떨어지는 경우는 없다.

- 그래서 정책이 중요한데, 예를 들어 프린터가 안되는 경우는 없게 하라라고 정책을 정하면 Always 방법을 사용한다. (다만 2회 Print 가 될 수 도 있다.) 

 

 

Basic Reliable-Multicasting Schemes

 

○ Multicasting환경에서 신뢰성을 보장받는방법

○ 원리 

- Multicast 이후 Peer로부터 Feedback 수신 

- Peer가 많을경우FeedbackImplosion 발생   

   • Feedback Implosion: 다수의 Peer가 Feedback을 발생시킴으로써 분산시스템 내에 Overload 또는 Congestion 발생

그림에서는 잘받는 경우 그리고 못받는 경우 전부 피드백을 하고 있다.

 

 

Nonhierarchical Feedback Control

○ Feedback Implosion을 해결하는 방법 

- SRM(Scalable Reliable Multicast) 

- Hierarchical

 

○ SRM  - Nonhierarchical Feedback Control 

- 정상인 경우에는 별도 ACK Message가 없어도 정상으로 가정하고 문제가 있을 경우에는 NACK 메세지를 Sender 측으로 전송하는 방식이다.

- 다만, 언제까지 데이터 패킷을 가지고 있어야 하는지 알 수 없기 때문에 시간을 정해  NACK 발생한 경우 순차적으로 NACK Message 를  전체 노드로 Multicastiong 한다.

 

- 동작   

   • ACK는 Default(Bypass), NACK만 동작   

   • NACK 응답을 각 Peer가 임의의 순서로 시간 간격을 두고 전송   

   • NACK 응답은 Broadcast 전송

   • Broadcast 된 NACK 응답을 수신한 다른 Peer는 자신이 보낼 NACK 응답 유형과 같은 것이라면 NACK를 보내지 않음

 

Hierarchical Feedback Control

○ Peer들의 Group을 형성하고 Group 내에 Coordinator를 설정

○ Group 내 Peer들은 Coordinator를 통해 Communication

* 코디네이터끼리 센더 역활을 하며 리시버는 그룹내 센더에게 요청함

 

 

○ 동작 

- Fail 발생 시 NACK 응답을 Coordinator에게 보냄 

- Coordinator가 재전송 수행

 

Vitrual Synchrony (Multicasting 동기 문제 해결)