반응형
들어가기전
Fault : 오류의 원인. 설계 오류, 제조 결함, 악화 또는 외부 간섭에서 발생
1. Fault Tolerance
관점: 컴퓨팅 시스템을 더 신뢰성 있게 만들어야 하는 필요성
- 컴퓨팅 시스템은 신뢰성이 높지 않음:
- 빈번한 운영체제 충돌, 버그 있는 소프트웨어, 신뢰성이 낮은 하드웨어, 소프트웨어/하드웨어 불일치 등
- 과거에는 컴퓨터 사용자들이 능숙한 tech savvy한 사람들.
- 요즘에는 "초보자" 사용자가 늘어남
→ 더 신뢰성 있고 의존할 수 있는 컴퓨팅 시스템을 구축해야 함!
a. 용어 설명
// 용어 정의 문제 나올 수 있음. 외우기.
- Failure : 정상적인 기능을 수행할 수 없는 상태
- Error : 진실이나 정확성 ❌. 의도치 않은 벗어남(unintentional deviation)을 포함한 행위
- Recursive :
- Failure은 Fault가 될 수 있다.
- 제조상의 Fault는 disk Failure로 이어질 수 있다.
- disk Failure은 데이터베이스 Failure로 이어질 수 있는 Fault(원인)이다.
- 데이터베이스 Failure는 이메일 서비스 Failure로 이어질 수 있는 Fault이다.
b. 비분산 / 분산 시스템에서의 Failure
- 분산 시스템, Single machine system과 차이점 : partial failure(부분적인 실패)
- Single machine system ⇒ Failure의 의미 : 완전 먹통 or 아무일도 아님.
- 운영 체제 충돌, 디스크 실패 등 → all stop
- 분산 시스템에서는 여러 독립적인 노드로 구성 → 일부 노드 Fail But 다른 노드는 계속 작동 가능
- Q: partial failure에서 전체 performance에 영향 주지 않으면서, automatically recover 시스템을 설계할 수 있을까?
- (시스템 내 노드의 수가 증가함에 따라 실패 확률이 증가)
- A: 100% 는 불가능!! but, failure consequences 를 최소화하려고 노력!
- 분산 시스템
- 실패는 부분적 이다.
- 일부 구성 요소는 여전히 작동할 수 있음.
- 전체 시스템은 여전히 기능할 수 있음.
- 비분산 시스템
- 실패는 전체적 이다.
- 모든 구성 요소가 영향을 받을 것이다.
- 전체 시스템이 다운될 수 있음. → SPoF의 가능성
Q: Faults의 영향을 숨길 수 있을까?
partial failures로부터 recover할 수 있을까?
A: 신뢰성 있는 시스템(dependable systems)과 관련!!!
c. 고장 감내 (Fault Tolerance)
- 분산 시스템은 Fault Tolerance을 가져야 한다!!
- Fault Tolerance은 dependability(의존도)과 관련이 있습니다.
- dependability은 다음을 포함.
- 가용성 (Availability)
- 신뢰성 (Reliability)
- 안전성 (Safety)
- 유지보수성 (Maintainability)
d. Dependability (믿을 수 있니?)
#~지를 나타내는 측정 지표 ⬇️
- Availability (가용성): 즉시 사용할 준비가 되어 있는지?
- 언제든지 시스템이 가동 중인 상태
- Reliability (신뢰성): failure 없이 계속 작동할 수 있는지?
- 시스템이 오랜 기간 동안 계속해서 기능 수행
- Safety (안전성): failure이 발생했을 때 그 실패가 얼마나 안전한지?
- 안전하다 = 시스템 전체에 심각한 문제가 발생하지 않음
- Maintainability (유지보수성): 시스템을 수리하는 것이 얼마나 쉬운지?
- 높은 유지보수성을 갖춘 시스템 → 높은 가용성을 보일 가능성 크다.
e. 어떻게 믿음직한 시스템을 구축할 것인가?
⇒ 어떻게 faults을 컨트롤할 것인가?
- Fault prevention (결함 예방)
- 결함의 발생을 미리(pre) 방지하는 것
- Fault removal (결함 제거)
- 결함의 존재, 수량, 심각성을 감소시키는 것 (remove! 최대한 제거!)
- Fault forecasting (결함 예측)
- 현재의 결함 수, 미래의 발생률, 그리고 결함의 결과를 예상하는 것
- Fault tolerance (고장 감내)
- 컴포넌트가 결함이 발생한 상태에서도, 명세에 충족할 수 있도록 component를 만들어야 함
- 고장에 견딜 수 있는 힘
Faults의 Type
- 일시적 결함 (Transient faults)
- 한 번 발생 후 사라진다.
- 예) 무선 통신 중의 간섭
- 간헐적 결함 (Intermittent faults)
- 간헐적으로 나타나는 결함. 꼭 기사님 오시면 결함 안나타남;;
- 예측하기 어렵다!
- 예) 커넥터의 느슨한 연결
- 지속적 결함 (Permanent faults)
- 고장난 구성 요소가 지속!
- 예) 고장난 칩, 수명이 다한 칩
실패 유형
- Crash Failure : 서버 중단! (중단 되기 전에는 정상 작동. 즉, 기기에는 큰 문제가 없다.)
- Omission Failure (Receive, Send) : Omission = 빼먹다. server와 보내고 받는 messages들을 빼 먹음
- Timing Failure : 타이밍을 벗어날 때. (specified time interval을 벗어난 response)
- Response Failure (Value, State transition) : 응답 실패
- Arbitrary Failure (Byzantine Failure) : 임의의 실패, 비잔틴 실패. 종잡을 수 없음.
- "Byzantine failure"는 악의적이거나 임의의 동작을 하는 컴포넌트로 인한 시스템의 실패
이는 다른 컴포넌트와는 다르게 올바르지 않은 정보를 전송하거나, 임의로 동작을 변경하거나, 악의적인 방식으로 시스템을 고의로 손상시키는 것 - → Crash Failure는 가장 덜 심각, Arbitrary Failure는 가장 심각!
실패 감지! (Detection)
- client 입장 : crashed componet와 just 조금 느려진 것과 구별 가능?
- 가정
- Fail-stop : 충돌 실패 → 알림 또는 타임아웃 을 통해 해당 실패를 감지 가능
- Fail-silent : 생략 또는 충돌 실패 → client는 어떤 문제가 발생했는지 알 수 없다.
- Fail-safe : 임의의 무해한 실패 → 피해
2. Fault Tolerance Techniques
- 목표! ⛳
전반적인 Performance에 큰 영향을 주지 않으면서, Partial Failure로 부터 Automatic한 Recover할 수 있도록 - 기술:
- Prevention (예방): faults 방지, 줄임
- Prediction (예측): faults 예측 & 처리
- Masking (가리기): faults의 발생 hide
- Recovery (회복): 오류 없던 상태로 복원
a. Failure Masking (Hiding)
- How to? ⇒ Redundancy ; 다중화 (여분의 것 여러개 둠)
- 정보, 시간, 물리적 (s/w or h/w) 인 redundancy가 있을 수 있음
결론
- 동일한 작업을 수행하는 여러 구성 요소를 동시에 가동시키는 것이 Redundancy이며,
- Redundancy를 통해, Failure Masking을 구현할 수 있으며
- Failure Masking을 통해 Fault Tolerance, Process Resilience을 가질 수 있다!
- Fault Tolerance는 dependability를 제공해주며,
- 이를 통해 Dependable Distributed System을 구현할 수 있다.
3. Process Resilience (회복성)
- 결함이 있는 프로세스를 용인하기 위해 동일한 프로세스를 여러 개 그룹화한다!
- Redundancy를 통해 Process Resilience을 가질 수 있다!
⇒ 그렇다면 어떻게 그룹화 할 것인가?
- 메시지를 보낼 때 그룹의 모든 구성원이 이를 수신해야 한다.
- 그룹은 동적이어도 된다. (다만 관리 메커니즘 필요)
a. Flat vs. Hierarchical Groups
- Flat Groups : 모든 그룹 멤버와 정보 교환이 즉시 일어남.
- 장점 : fault tolerance 👍, SPoF ❌, overhead 🔺
- 단점 : 구현 hard..
- Hierarchical Groups (계층적 그룹): 모든 통신이 Coordinator를 통해 이루어짐
- 단점 : fault tolerance or Scalable 별로 안조아
- Coordinator가 감당할 수 있는 한계가 있기 때문에 Salable이 좋지 않다.
- 장점 : 구현이 쉽다!!
- 단점 : fault tolerance or Scalable 별로 안조아
b. Group 관리 정책
그룹을 추가/삭제하고 멤버를 가입/탈퇴를 관리하는 방법!!
- 중앙집중식 (Centralized):
- 각 그룹에 대한 DB를 유지 관리하는 GROUP SERVER를 하나 둔다.
- 효율적이고 구현이 쉬우나, SPoF
- 분산 (Distributed) :
- 그룹에 가입하려면 🆕procsee 가 “가입 요청 메시지!” 를 모든 그룹 멤버에게 보낼 수 있음
- 나가려면 모두에게 “굿 바이 메시지!”
4. K-Fault Tolerance
(K-예비군 그런거 아니다..)
- 시스템이 k-fault tolerant 이다.
⇒ k 개의 componet가 fault 나도 여전히 명시된 사양을 충족할 수 있다(제대로 돌아간다.)
Redundancy의 Level
상황에 따라, k-fault tolerant 를 지키려면 몇 k개의 component가 필요할까?
- 상황 가정 1: crash failure semantics를 가정 (즉, fail-stop)
<component가 down되는 상황 가정>- k 개의 실패에서 생존하려면, k + 1 개의 component가 필요!
(k 개가 중단 → 마지막 하나 작동 가능)
- k 개의 실패에서 생존하려면, k + 1 개의 component가 필요!
- 상황 가정 2-1:
- arbitrary/Byzantine (but non-malicious // 악의적이지 않은 비잔틱 문제) failure semantics를 가정
(즉, failure 상황에서 계속해서 실행하고, 무작위 또는 잘못된 응답을 보냄)- 1/2의 다수결!!!
- 2k+1 개의 구성 요소가 필요!!
- k개 까지는 잘못되어도, (k+1)은 올바르게 작동한다~ ⇒ 다수결의 원칙에 따라 올바른 output을 낸다
- arbitrary/Byzantine (but non-malicious // 악의적이지 않은 비잔틱 문제) failure semantics를 가정
상황 가정 2-1에서 Malicious 하다면? : Agreement 문제
- 상황 가정 2-2: Byzantine (malicious) failure를 가정!
- Faulty components들이 협력하여 cheat 할 수 있다~
- 2/3의 다수결!!!
- k 개의 실패를 견딜 수 있도록 하려면 3k+1 개의 구성 요소가 필요!!
- k가 전체의 1/3까지는 잘못되어도 됨! 적어도 2k +1 (전체의 2/3 이상)은 올바르게 작동!
a. Faulty systems에서의 Agreement
- Agreement!! (합의) 는 다음 작업 등 여러 곳에서 필요함!
- 계산 결과, leader 선출, 동기화, 트랜잭션 커밋
- ex) 2/3이상의 의견이 합의가 되면 그것으로 결정~
- 현실적으로, 완벽한 합의가 일어나기 쉽지 않음
Q. Distributed System에서 해당 시스템이 Faulty System이라면, Agreement가 어려운 이유를 쓰시오!
(분산 시스템이 결함이 있는 시스템이라면 합의를 도달하는 것이 어려운 이유)
A. 통신에서는 메시지 전송에 신뢰성을 잃고, 악의적인 존재가 메시지를 가로챌 가능성이 있다.
또한 프로세스는 정상작동에 실패할 수 있고, 잘못된 결과를 도출하도록 협업할 수 있다.
이러한 이유에서 결함이 있는 환경에서 합의를 도달하기 어렵다.
- 목표 : 정상적인 프로세스들이 유한한 단계 내에 합의에 도달할 수 있도록 하는 것!
b. Byzantine Agreement Problem
- k 명의 traitors(배신자) 포함, 총 N 명의 generals(장군)
- 문제: 신뢰할 수 있는 장군들이 자신들의 군대 규모에 대해 합의할 수 있을까요? N과 k는 어떻게 결정되어야 할까?
- 수학적인 문제로 간다..
Byzantine Agreement Problem Solution ; Lamport’s Agreement Algorithm
- 각 장군 i는 자신의 군대 규모 Vi (값) 를 다른 장군들에게 보냅니다.
- Loyal generals : 진실!
- Traitors : 배신!
- 각 general은 받은 정보를 자신이 결함이 없는 경우에 한해 V[i] == Vi 벡터로 수집!
- 각 general은 자신의 벡터를 다른 장군들에게 보냅니다.
- Loyal generals : 자기가 수집한 것 그대로 보냄!
- Traitors : 조작할 수 있다!
- 각 장군은 모든 받은 벡터에 대한 투표를 통해 벡터의 요소를 결정 (다수결 등)
이렇게 함으로써 각 장군은 자신의 군대 규모를 합의하여 결정하게 됩니다. Lamport의 합의 알고리즘은 배신자에 의한 잘못된 정보에도 견고하게 동작하며, 벡터의 각 요소를 투표를 통해 결정함으로써 신뢰성을 유지합니다.
Byzantine Agreement Problem Solution
1. Case1 : N = 4 and k = 1
Step 1: 각 프로세스는 자신의 값을 다른 프로세스에게 보낸다.
Step 2: 각 프로세스는 받은 값을 하나의 벡터로 수집합니다. Got(1,2,3,4)
왼쪽의 경우 3번 process가 거짓말 쟁이!
Step 3: 각 프로세스는 자신의 벡터를 모든 다른 프로세스에게 전달!
3번은 이때도 마구마구 바꿔서 보냄!
Step 4:
- 각 프로세스는 새로 받은 벡터의 i번째 요소를 확인합니다.
- 어떤 값이 다수를 차지하고 있다면, 해당 값은 결과 벡터에 넣습니다.
- 만약 어떤 값도 다수를 차지하지 않으면, 결과 벡터의 해당 요소는 UNKNOWN으로 표시됩니다.
⇒ Agreement 성공 ✔️
(예상문제? .. 한계?
3이 모든 프로세스에게 9라는 값을 보낸다고 치면,
그러면 모든 프로세스가 3의 값을 9로 다수결의 원칙으로 해당 벡터의 요소를 표시… 오류…)
2. Case2 : N = 3 and k = 1
위와 같은 방식!
하지만 1번은, 2번에서 온 벡터 & 3번에서 온 벡터 2가지로 다수결 진행.
여기서 3번이 이상한 값 보냄? → 합의 할 방법이 없다.
⇒ Agreement 실패 😢
종합 : 다수결로는 부족하다!
→
k개의 오동작 프로세스가 있는 시스템에서
합의를 달성하기 위해서는
총 3k+1개의 프로세스 중에서 2k+1개가 정상적으로 작동해야 한다
5. Failure detection
- Actively send mechanisms : 적극적으로 "Are you alive?"를 보내고, 답장을 기대.
- passively wait mechanisms : 댕댕이 마냥 답장 올 때까지 기다리기
- Failure Detection 에서는 보통 timeout 메커니즘이 사용됨.
6. Recovery 전략
- 장애가 발생 → 시스템을 에러 없는 상태로 되돌리기! 복원!
- Backward Recovery (역방향)
- 시스템을 이전의 에러 없는 상태로 되돌림.
- 예) 패킷 재전송
- Forward Recovery (순방향)
- 시스템이 계속 작동할 수 있는 새로운 미래 상태를 찾는다.
- 예) 오류 정정 코드
a. Forward and Backward Recovery
// 외우자!
- Backward Recovery의 주요 단점:
- Checkpointing → very expensive (특히 오류가 매우 드문 경우).
- 비용이 높지만, 현실에서느 역방향 복구가 더 자주 구현됨…
- "logging"도 일종의 Checkpointing*
- Forward Recovery의 주요 단점:
- 모든 잠재적인 error를 미리 고려!
- 오류가 발생하면 복구 메커니즘이 시스템을 올바른 상태로 되돌리기 위해 무엇을 해야 하는지 알고 있어야 한다.
- 로직 구현이 어려움…ㅠㅠ
b. 분산 시스템에서의 Recovery
- 각 프로세스가 복구할 상태를 식별하기 위해 또 cooperate(협력)해야 해야함!!!
- ”콩쥐야 ㅈ댔어. 멈춰봐” 메시지 다 보내야됨*
- → 각 프로세스는 자신의 상태를 지속적으로 local stable storage (checkpoint)에 저장
- Failure 🚨→ 가장 최근의 consistent global state 또는 recovery line을 가져온다.
- Checkpoint 에는 두 가지 종류!
- 독립적인 Checkpointing
- Coordinate가 정해주는 Checkpointing
1) Independent Checkpointing
- 각 프로세스 독립적으로 snapshots!!
- Failure 🚨 → 일관된 cut을 찾기 위해 역방향 찾아 들어감.
- Problem ⚠️
- failure 지점에서 뒤로 돌아감
- 가장 최근의 checkpoint가 inconsistent cut이라면?
- consistent cut이 찾아질 때까지 계속 rolling back!
- 연쇄적인 롤백 → domino effect!
- 시스템이 계속해서 롤백되는 상황이 발생할 수 있다.
2) Coordinated Checkpointing
- 전역적으로 coordinated 작업 후, checkopoint를 찍음
- 간단한 해결책: two-phase blocking protocol
- coordinater 가 체크포인트 요청 브로드케스트.
- 해당 요청 받으면 응용프로그램 블락. 후, 체크포인트 찍고 찍었다고 coordinater에게 다시 답장함.
- coordinater는 모든 ok 메시지 받으면, 체크포인트 완료 메시지 브로드케스트.
- 이후 이 메시지 받으면 바로 응용 프로그램 블락 풀고 정상 작동 시작
→ 3) 단점 보완 : Message Logging과의 결합
- Checkpointing 작업이 너무 expensive
- 모든 프로세스는 이전 일관된 컷에서 다시 시작
- snapshot 찍는 것, 비용이 많이 듦
- 해결책: checkpointing (expensive) 을 message logging (cheap)과 결합
- 불규칙적인 체크포인트를 찍음
- 체크포인트 사이의 모든 메시지를 local stable storage(hard disk)에 기록
- 복구할 때 : 이전 체크포인트 이후의 메시지를 단순히 다시 재생하면 됨
- a checkpoint ———————————— b checkpoint —————— Failure 🚨
주고 받은 메시지 주고 받은 메시지
**local stable storage에 기록!** **local stable storage에 기록 중…**
→ **Recovery!**
반응형
