TIL: 실제 세계 분산 시스템에서의 Byzantine Generals Problem

Source: Dev.to

Preface

Raft 알고리즘을 학습할 때, 비잔틴 장애는 보통 제외됩니다. 그런데 작년 11월에 발표된 CloudFlare 사고 보고서에서는 실제 세계의 비잔틴 문제를 제목으로 사용했습니다. 이를 바탕으로 몇 가지 생각을 정리해 보겠습니다.

What is Byzantine failure

분산 시스템에서 서로 다른 컴퓨터들은 합의 통신 데이터 확인 과정으로 서로 소통합니다. 이는 컴퓨터가 자신이 할 일을 보고하거나 리더에게 투표하도록 요구합니다.

만약 어떤 컴퓨터가 일부 멤버 A에게는 한 가지를, 다른 그룹 B에게는 다른 내용을 전달해 전체 그룹이 합의에 이르지 못하거나 예상치 못한 상태에 빠지게 된다면 이를 비잔틴 장애(Byzantine Failure) 라고 합니다.

Paxos와 Raft 같은 많은 합의 알고리즘은 비잔틴 장애가 존재하지 않는다고 가정합니다. 왜냐하면 이를 처리하려면 합의 복잡도가 한 단계 더 높아지기 때문입니다.

Reference articles

• Wiki Byzantine Generals Problem (Chinese)

About CloudFlare’s recovery mechanism

보다 복잡한 문제를 살펴보기 전에, CloudFlare 사고 보고서에는 시스템 유지보수를 위한 백업 메커니즘에 대한 흥미로운 관점이 있습니다.

Service backup mechanism

• 각 서비스는 일련의 랙 서버들로 구성됩니다.
• 각 머신은 두 개의 스위치를 가지고 있습니다.
• 각 랙에는 두 개 이상의 전원 공급 장치가 있습니다.
• 각 서버는 RAID‑10 백업 메커니즘(RAID 1 + RAID 0)을 사용합니다.
• 각 랙에는 최소 세 대의 머신이 배치됩니다.

The problem that occurred

Image explanation: 왼쪽 위가 Server 1, 오른쪽 위가 Server 2, 아래쪽이 Server 3이며, 이 서버가 Leader입니다.

• Server 1과 Server 2 사이의 네트워크 문제로 인해 두 서버가 서로 다른 정보를 갖게 되었습니다.
  • Server 1은 Leader(Server 3)가 오프라인이라고 판단했습니다.
  • Server 2는 Leader가 정상적으로 실행 중이라고 판단했습니다.
• 이러한 불일치 때문에 CloudFlare는 이번 사고를 비잔틴 장애(Byzantine Failure) 로 분류했습니다.

Reference

• Cloudflare Dashboard and Cloudflare API service issues
• A Byzantine failure in the real world (Cloudflare blog)
• Raft does not Guarantee Liveness in the face of Network Faults
• Wiki: Byzantine Generals Problem (Chinese)
• Raft lecture (Raft user study) by Diego Ongaro
• The Cloudflare Blog
• Improving the Resiliency of Our Infrastructure DNS Zone
• Link aggregation – Wikipedia
• The power of the adversary
• Pull requests · etcd-io/etcd
• Understanding the Byzantine Generals’ Problem (Medium)
• 拜占庭將軍問題 – 維基百科 (Chinese)
• Raft Consensus Algorithm