08장. 분산 시스템의 골칫거리

어떤 것이든지 잘못될 가능성이 있다면 잘못된다.

0. 분산 시스템의 골칫거리

• 분산 시스템을 다루는 것은 한 컴퓨터에서 실행되는 소프트웨어를 작성하는 일과는 근본적으로 다르다.
• 엔지니어로서의 우리의 임무는 모든게 잘못되더라도 사용자가 기대하는 보장을 만족시키는 제 역할을 해내는 시스템을 구축하는 것이다.

1. 결함과 부분 장애

• 컴퓨터에 내부 결함이 발생하면 잘못된 결과를 반환하기보다는 완전히 동작하지 않기를 원한다.
• 단일 컴퓨터 기준
  • 하드웨어가 올바르게 동작하면 같은 연산은 항상 같은 결과를 낸다. (결정적이다.)
  • 하드웨어 문제가 있으면 보통 시스템이 완전히 실패하는 결과를 낳는다.
• 분산 시스템 기준
  • 네트워크 문제, 부분적인 실패, 타이밍 문제 등 다양한 문제가 발생할 수 있다.
  • 부분 장애는 비결정적이다.
  • 이러한 문제들은 예측하기 어렵고, 디버깅하기도 어렵다.

1.1. 클라우드 컴퓨팅과 슈퍼컴퓨팅

• 슈퍼 컴퓨팅
  • 슈퍼컴퓨터에서 실행되는 작업은 보통 가끔씩 계산 상태를 지속성 있는 저장소에 체크포인트로 저장한다.
  • 노드 하나에 장애가 발생했을 때 흔한 해결책은 그냥 전체 클러스터 작업부하를 중단하는 것이다.
  • 슈퍼컴퓨터는 부분 장애를 전체 장애로 확대하는 방법으로 처리하는데 시스템의 어느 부분에 장애가 발생하면 그냥 전체가 죽게 한다.
• 분산 시스템이 동작하게 만들려면 부분 장애 가능성을 받아들이고 소프트웨어에 내결함성 메커니즘을 넣어야 한다.
• 올바르게 동작하던 시스템도 시간이 지나면 어떤 부분에 결함이 생길 것이고 소프트웨어는 어떤 식으로든 그 결함을 처리해야 한다.

2. 신뢰성 없는 네트워크

• 분산 시스템은 비공유 시스템, 즉 네트워크로 연결된 다수의 장비다.
• 인터넷과 데이터센터 내부 네트워크 대부분은 비동기 패킷 네트워크다.
• 노드는 다른 노드로 패킷을 보낼 수 있지만 도착을 보장하지 않고 요청을 보내고 응답을 기다리는 사이에 여러 잘못이 생길 수 있다.
• 이런 문제를 다루는 가장 흔한 방법은 타임아웃이다.

2.1. 현실의 네트워크 결함

• 네트워크 문제는 놀랄 만큼 흔하다.
• 중간 규모의 데이터센터에서 매달 12번의 네트워크 결함이 발생함을 발견했다.
• EC2 같은 공개 클라우드 서비스는 일시적으로 네트워크 결함이 자주 발생하는 것으로 알려져 있다.
• 소프트웨어는 예측하지 못하는 상황이지만 네트워크 결함을 반드시 견뎌내도록 처리할 필요는 없다.
• 네트워크 문제에 어떻게 반응하는지 알고 시스템이 그로부터 복구할 수 있도록 보장해야 한다.
• 고의로 네트워크 문제를 유발하여 시스템의 반응을 테스트해보는 것도 좋다. (카오스 몽키)

2.2. 결함 감지

• 결함을 자동으로 감지할 수 있어야 한다.
• 네트워크는 불확실성이 있기 때문에 노드가 동작 중인지 아닌지 구별하기 어렵다.
• TCP가 패킷이 전달됐다는 확인 응답을 했더라도 애플리케이션이 그것을 처리하기 전에 죽을 수도 있다.
• 요청이 성공했음을 확신하고 싶다면 애플리케이션 자체로부터 긍정 응답을 받아야 한다.

2.3. 타임아웃과 기약 없는 지연

• 타임아웃이 길면 노드가 죽었다고 선언될 때까지 기다리는 시간이 길어진다.
• 타임아웃이 짧으면 결함을 빨리 발견하지만 노드가 일시적으로 느려졌을 뿐인데도 죽었다고 잘못 선언할 위험이 높아진다.
• 빠른 타임아웃은 다른 노드로 역할을 넘겨주게 되고 해당 요청이 중복되어 실행될 수도 있다.
• 역할이 다른 노드로 전달되어 다른 노드와 네트워크에 추가적인 부하를 준다.
• 비동기 네트워크는 기약 없는 지연(unbounded delay)이 있다.

2.3.1. 네트워크 혼잡과 큐 대기

• 네트워크 링크가 붐비면 패킷은 슬롯을 얻을 수 있을 때까지 잠시 기다려야할 수도 있는데 이를 네트워크 혼잡(Network Congestion)이라고 부른다.
• 패킷이 목적지에 도착했을 때 모든 CPU가 바쁜 상태라면 운영체제 큐에 넣어둔다.
• TCP는 혼잡 회피, 배압이라고 하는 흐름 제어를 수행하여 데이터가 네트워크로 들어가기 전에 송신을 제어하는 부가적인 큐 대기를 할 수 있다.
• TCP는 타임아웃이 발생하면 손실로 간주하고 자동으로 재전송하는데 애플리케이션에서는 패킷의 손실과 재전송이 보이지 않지만 지연은 확인할 수 있다.
• 다양한 요인으로 네트워크 지연의 변동성에 영향을 준다.
• 이런 환경에서는 실험적으로 타임아웃을 선택하는 수 밖에 없다.
• 고정된 타임아웃을 설정하는 대신 시스템이 지속적으로 응답 시간과 그들의 변동성을 측정하고 관찰된 응답 시간 분포에 따라 타임아웃을 자동으로 조절하게 하는 방법이 있다.

2.4. 동기 네트워크 대 비동기 네트워크

• 전화 통화는 회선(circuit)을 만들어 고정되고 보장된 양의 대역폭이 할당된다. (동기식 네트워크)
• 큐 대기가 없으므로 네트어워크 종단 지연 시간의 최대치가 고정돼 있다. - 제한 있는 지연 (bounded delay)
• TCP 연결의 패킷은 가용한 네트워크 대역폭을 기회주의적으로 사용한다. (비동기식 네트워크)
• 웹 페이지 요청, 이메일/파일 전송 처럼 순간적으로 몰리는 트래픽의 경우 TCP 패킷 교환이 적절하다.
• 네트워크 혼잡, 큐 대기, 기약 없는 지연이 발생할 것이라고 가정하고 타임아웃의 올바른 값은 실험을 통해 결정해야 한다.

3. 신뢰성 없는 시계

• 분산 시스템에서는 통신이 즉각적이지 않으므로 시간을 다루기 까다롭다.
• 메시지가 네트워크를 거쳐 전달되는 데 시간이 걸리고 네트워크의 지연 변동성 때문에 얼마나 거릴지 알 수 없다.
• 개별 장비는 수정 발진기(quartz oscillator)라는 시계를 갖고 있지만 다른 장비와 차이가 있을 수 있다.
• 네트워크 시간 프로토콜(NTP) 메커니즘으로 서버 그룹 내에 시계를 조정할 수 있게 한다.
• GPS로 더 정확한 시간을 동기화시킬 수 있다.

3.1. 단조 시계 대 일 기준 시계

• 일 기준 시계(Wall-Clock Time)
  • 모두가 같이 보는 벽 시계
  • created_at 기록에 적합하다.
• 단조 시계(Monotonic Clock vs)
  • 나 혼자 보는 손목 시계
  • elapsed_time 측정에 적합하다.
• 리눅스 서버 ntp 동기화 설정

3.1.1. 일 기준 시계

• 일 기준 시계는 직관적으로 시계에 기대하는 일을 한다.
• 어떤 달력에 따라 현재 날짜와 시간을 변환한다.
  • 리눅스: clock_gettime(CLOCK_REALTIME)
  • 자바: System.currentTimeMillis()
  • 에포크(epoch)부터 흐른 초(or 밀리초) 수를 반환한다. (에포크: 1970년 1월 1일 0시 0분 0초 - UTC)
• 일 기준 시계는 보통 NTP로 동기화되어 한 장비의 타임스탬프는 다른 장비의 타임스탬프와 동일한 의미를 지닌다는 뜻이다.
• 로컬 시계가 NTP 서버보다 너무 앞서면 강제 리셋되어 과거 시점으로 거구로 뛰는 것처럼 보일 수 있다.

3.1.2. 단조 시계

• 단조 시계는 타임아웃이나 서비스 응답 시간 같은 지속 시간(시간 구간)을 재는 데 적합하다.
  • 리눅스: clock_gettime(CLOCK_MONOTONIC)
  • 자바: System.nanoTime()
• 두 시점의 단조 시계 값을 확인하여 두 값 사이의 차이로 시간이 얼마나 흘렀는지 알 수 있다.
• 그러나 시계의 절대적인 값은 의미가 없다.
• 컴퓨터가 시작한 이래 흐른 나노초 수일 수도 있고 비슷한 어떤 것일 수도 있다.
• 두 대의 다른 컴퓨터에서 나온 단조 시계 값은 동일한 것을 의미하지 않기 때문에 이 둘을 비교하는 것은 의미가 없다.
• 여러 개의 CPU 소켓이 있는 서버는 CPU마다 독립된 타이머가 있을 수 있다.
  • 운영체제는 차이를 보정하여 스레드가 여러 CPU에 걸쳐 스케쥴링 되더라도 시계가 단조적으로 보이게 하려고 한다.
  • 단조성 보장은 곧이 곧대로 받아들이지 않는게 현명하다.
• 단조 시계의 해상도는 좋은 편이기 때문에 마이크로초나 그 이하 단위로 측정할 수 있다.
• 분산 시스템의 경과 시간을 재는데 단조 시계를 쓰는 것은 측정이 약간 부정확해도 민감하지 않기 때문에 일반적으로 괜찮다.

3.2. 시계 동기화와 정확도

• 단조 시계는 동기화가 필요 없지만 일 기준 시계는 NTP 서버나 다른 외부 시간 출처에 맞춰 설정돼야 유용하다.
• 하드웨어 시계와 NTP는 생각보다 정확하지 않다.
  • 컴퓨터의 수정 시계는 장비 온도에 따라 더 빠르거나 느리게 실행되는 드리프트 현상이 생긴다.
  • 컴퓨터 시계와 NTP 서버와 차이가 심하면 동기화가 거부되거나 강제로 리셋될 수 있다.
  • 방화벽으로 NTP 서버가 차단되어 잘못된 설정이 얼마동안 알려지지 않을 수 있다.
  • NTP 동기화는 잘해야 네트워크 지연만큼만 좋을 수 있다. (최소 오차 35ms)
  • 어떤 NTP 서버들은 이상이 잇거나 설정이 잘못돼서 몇 시간 정도 차이 나는 시간을 보고하고 있다.
  • 윤초가 발생하면 1분이 길이가 59-61초가 되어 윤초를 고려하지 않고 설계된 시스템에서는 시간에 관한 가정이 엉망이 돼 버린다.
  • 가상 장비에서 하드웨어 시계는 가상화돼서 정확한 시간 엄수가 필요한 애플리케이션에게 추가적인 어려움이 생긴다.
  • 완전히 제어할 수 없는 장치에서 소프트웨어를 실행하면 아마도 그 장치의 하드웨어 시계를 전혀 믿을 수 없을 것이다.
• 유럽 금융 규제 기관 초안은 고빈도 트레이딩 펀드는 모두 그들의 시계를 UTC와 100마이크로초 이내 동기화를 요구한다.
  • GPS, 정밀 시간 프로토콜(PTP), 세심한 배포와 모니터링
  • 상당한 노력과 전문 기술이 필요하며 시계 동기화가 잘못될 수 있는 수많은 가능성이 존재한다.
    • 잘못된 NTP 대몬 설정, 방화벽 NTP 트래픽 차단 등

3.3. 동기화된 시계에 의존하기

• 하루는 정확히 86400초가 아닐 수도 있고, 일 기준 시계가 거꾸로 갈 수도 있으며, 노드 간 시간 차이가 많이 날 수도 있다.
• 소프트웨어는 네트워크 결함을 가정해서 설계돼야하며 시계도 마찬가지로 고려 대상이다.
• 견고한 소프트웨어는 잘못된 시계에 대비할 필요가 있다.
• 시계가 잘못된다는 것을 눈치채기 어렵다.
• 동기화된 시계가 필요한 소프트웨어를 사용한다면 모든 장비 사이의 시계 차이를 모니터링해야 한다.
• 시계 차이가 큰 노드는 죽은 것으로 간주하고 클러스터에서 제거돼야 한다.

3.3.1. 이벤트 순서화용 타임스탬프

• 그림 8-3 다중 리더 복제를 쓰는 데이터베이스에서 일 기준 시간을 위험하게 사용하는 예 - 291p
  • 노드 간 시계 차이로 데이터 수정의 순서가 변경될 수 있다.
• 최종 쓰기 승리 (last write win, LWW) 전략으로 충돌을 해소할 수 있고 다중 리더 복제, 리더 없는 데이터베이스에서 널리 사용된다.
• 타임스탬프를 서버가 아니라 클라이언트에서 생성하는 구현도 있지만 LWW에 존재하는 근본적은 문제를 바꾸지는 못한다.
  • 시계가 뒤처지는 노드는 시계가 빠른 노드가 먼저 쓴 내용을 그들 사이에 차이나는 시간이 흐를 때까지 덮어쓸 수 없기 때문에 데이터베이스 쓰기가 사라질 수 있다.
  • 순차적인 쓰기가 빠른 시간 내에 연속으로 실행되는 것과 진짜 동시에 쓰기가 실행되는 것을 구별할 수 없다.
  • 두 노드가 독립적으로 동일한 타임스탬프를 가진 쓰기 작업을 만들 수도 있다.
• 가장 최근 값을 유지하고 다른 것들을 버림으로써 충돌을 해소하고 싶더라도 최근의 정의는 로컬 일 기준 시게에 의존하며 그 시게는 틀릴 수도 있다는 것을 아는게 중요하다.
• 잘못된 순서화가 발생하지 않을 정도로 NTP 동기화를 정확하게 하기는 거의 불가능하다.
• 올바른 순서화를 위해서는 시계 출처가 측정하려고 하는 대상(네트워크 지연)보다 훨씬 더 정확해야한다.
  • 논리적 시계 (logical clock)
    • 진동 수정 대신 증가하는 카운터 기반
    • 일 기준, 경과한 초 수를 측정하지 않고 이벤트의 상대적인 순서만 측정
  • 물리적 시계 (physical clock)
    • 일 기준 시계와 단조 시계는 실제 경과 시간을 측정
    • 순서화 보장 336p

3.3.2. 시계 읽기는 신뢰 구간이 있다

• 시계 읽기를 어떤 시점으로 생각하는 것보다 어떤 신뢰 구간에 속하는 시간의 범위로 생각하는 것이 좋다.
  • 장비의 일 기준 시계를 마이크로초, 나노초 해상도로 읽을 수 있지만 그 값이 그런 정밀성을 제공할 만큼 정확하지 않다.
  • 로컬 네트워크에 있는 NTP 서버와 매분 동기화하더라도 부정확한 수정 시계에서 발생하는 드리프트는 쉽게 몇 ms가 될 수 있다.
  • 공개 인터넷 NTP 서버를 사용하면 달성 가능한 최선의 정확도는 아마 수십 ms 정도이고 네트워크가 혼잡하다면 100ms 이상이 될 수 있다.
• 불확실성 경계는 시간 출처를 기반으로 계산할 수 있다.
  • GPS, 컴퓨터의 원자 시계: 제조사에서 제공하는 예상 오류 범위
  • NTP 서버: 마지막 동기화 시간 이후로 예상되는 시간 드리프트 + NTP 서버의 불확실성 + 네트워크 왕복 시간
  • clock_gettime()을 호출하더라도 예상 오차를 알려주지는 않는다.
  • 스패너의 구글 트루타임 API는 로컬 시계의 신뢰 구간을 명시적으로 보여준다.
  • 구글 스패너

3.3.3. 전역 스냅숏용 동기화된 시계

• 스냅숏 격리는 작고 빠른 읽기 쓰기 트랜잭션과 크고 오래 실행되는 읽기 전용 트랜잭션 모두를 지원해야 하는 데이터베이스에서 아주 유용한 기능이다.
• 가장 흔한 스냅숏 격리 구현은 단조 증가하는 트랜잭션 ID가 필요하다.
• 스냅숏보다 나중에 쓰기가 실행됐다면 그 내용은 스냅숏 트랜잭션에게 보이지 않는다.
• 단일 노드 데이터베이스에서는 단순한 카운터가 트랜잭션 ID를 생성하는데 충분하다.
• 분산 데이터베이스는 코디네이션이 필요하다.
• 분산 시스템에서 작고 빠른 트랜잭션이 많으면 트랜잭션 ID 생성은 방어할 수 없는 병목이 된다.
• 구글 스패너 예시
  • 트루타임 API의 시계 신뢰 구간을 사용하여 신뢰 구간이 겹치지 않는다면 트랜잭션의 우선 순위를 보장할 수 있다.
    • A-earliest < A-latest < B-earliest < A-earliest
  • 트랜잭션 타임스탬프가 인과성을 반영하는 것을 보장하기 위해 읽기 쓰기 트랜잭션을 커밋하기 전에 의도적으로 신뢰 구간의 길이만큼 기다린다.
  • 그 데이터를 읽을지도 모르는 트랜잭션은 충분히 나중에 실행되는 게 보장되므로 신뢰 구간이 겹치지 않는다.
  • 시계 불확실성을 가능하면 작게 유지해야하기 때문에 각 데이터센터에 GPS 수신기나 원자 시계를 배치해서 약 7ms 이내로 동기화되게 한다.

3.4. 프로세스 중단

• 분산 시스템에서 리더가 안전하게 쓰기를 받을 수 있는 임차권(lease) 예제 - 295p
• 프로그램 실행 중에 예상치 못한 중단이 있어서 오랫동안 요청이 오랫동안 멈춰있다면 이미 임차권이 만료되어 다른 노드가 리더 역할을 맡고 있을 수 있다.
• 단일 장비에서는 뮤텍스, 세마포어, 원자적 카운터, 락프리, 블로킹 큐 등 다양한 스레드 안전 기법을 사용할 수 있지만 분산 시스템에서는 불가능 하다.
• 분산 시스템의 노드는 어느 시점에 실행이 상당히 멈출 수 있다고 가정해야 하고 심지어 함수 중간에 멈출 수도 있다.

3.4.1. 응답 시간 보장

• 명시된 시간안에 응답하는 데 실패하면 심각한 손상을 유발할 수 있는 환경에서 실행되는 소프트웨어는 데드라인이 명시된다.
• 프로세스가 명시된 간격의 CPU 시간을 할당받을 수 있게 보장되도록 스케쥴링 해주는 실시간 운영체제가 필요하다.
• 라이브러리 함수는 최악의 실행 시간을 문서화해야 한다.
• 동적 메모리 할당은 제한되거나 완전히 금지될 수 있다.
• 보장 만족의 확신을 위해 막대한 양의 테스트와 측정을 해야 한다.
• 프로그래밍 언어, 라이브러리, 도구의 범위를 엄격하게 제한한다.
• 안전이 필수적인 임베디드 장치에서 가장 흔하게 사용된다.
• 실시간 시스템은 무엇보다도 제때에 응답하는 것을 우선시해야 하므로 처리량이 더 낮을 수도 있다. (실시간은 고성능과 동일하지 않다.)

3.4.2. 가비지 컬렉션의 영향을 제한하기

• 언어 런타임은 객체 할당률과 시간에 따라 남아 있는 여유 메모리 공간을 추적할 수 있으므로 언제 GC 할지와 관련된 어느정도 유연성을 갖고 있다.
• GC 중단을 노드가 잠시 동안 계획적으로 중단되는 것으로 간주하고 노드가 GC 하는 동안 클라이언트 요청을 다른 노드들이 처리하게 한다.
• 런타임이 애플리케이션에게 노드가 곧 GC 중단이 필요하다는 경고를 할 수 있다면 애플리케이션은 그 노드로 새로운 요청을 멈추고, 그 노드가 요청 처리를 완료한 후 아무 요청도 처리 하지 않는 동안 GC를 실행하기를 기다릴 수 있다.
• GC를 클라이언트로부터 감추고 응답 시간의 상위 백분위를 줄여준다.
• 지연 시간에 민감한 금융 거래 시스템 중에 이 방법을 쓰는 것도 있다.
• 수명이 짧은 객체만 GC를 사용하고 수명이 긴 객체의 전체 GC가 필요할 만큼 객체가 쌓이기 전에 주기적으로 프로세스를 재시작하는 방법도 있다.
• GC 중단을 완전히 막을 수는 없지만 애플리케이션에 미치는 영향은 유용하게 줄일 수 있다.

4. 지식, 진실, 그리고 거짓말

• 분산 시스템은 공유 메모리가 없고 지연 변동이 있는 네트워크로 통신하여 부분 장애, 신뢰성 없는 시계, 프로세스 중단 등 다양한 문제가 있다.
• 분산 시스템에서 동작(시스템 모델)에 관해 정한 가저을 명시하고, 이런 가정을 만족시키는 방식으로 실제 시스템을 설계할 수 있다.
• 어떤 시스템 모델 내에서 알고리즘이 올바르게 동작하는지 증명할 수 있다.
• 기반 시스템 모델이 매우 적은 보장만 제공하더라도 신뢰성 있는 동작을 달성할 수 있다.
• 그러나 신뢰성 없는 시스템 모델에서 잘 동작하는 소프트웨어를 만드는 게 가능할지라도 그것이 간단하지는 않다.

4.1. 진실은 다수결로 결정된다

• 분산 시스템은 한 노드에만 의존할 수 없고 노드에 언제든 장애가 나서 잠재적으로 시스템이 멈추고 복구할 수 없게 될 수도 있다.
• 여러 분산 알고리즘은 정족수(quorum), 노드들 사이의 투표에 의존한다.
• 노드의 과반수 이상을 정족수로 삼는 게 가장 흔하다.

4.1.1. 리더와 잠금

• 파티션의 리더, 잠금 획득, 식별자
• 어떤 노드가 스스로를 리더라고 믿더라도 정족수도 반드시 동의하지는 않고 다른 노드들이 그 노드가 죽었다고 선언하면 그 노드는 강등되고 다른 리더가 이미 선출되었을 수도 있다.
• 임차권 잠금 예시
  • 임차권을 가진 클라이어트가 너무 오랫동안 멈춰 있어서 임차권이 만료된다.
  • 다른 클라이언트가 임차권을 얻어서 쓰기를 시작할 수 있다.
  • 멈췄던 클라이언트가 여전히 유효한 임차권을 갖고 있느 것으로 잘못 알고 파일에 쓴다.
  • 두 클라이언트의 쓰기가 충돌되고 파일이 오염된다.

4.1.2. 펜싱 토큰

• 잠금(임차권)을 쓸 때 자신이 잠금을 얻었다고 잘못 믿고 있는 노드가 시스템을 방해할 수 없도록 보장하기 위한 단순한 기법이 펜싱이다.
• 잠금 서버가 잠금이나 임차권을 승인할 때마다 펜싱 토큰을 반환하고 클라이언트가 쓰기 요청을 할 때 펜싱 토큰을 포함하도록 한다.
• 오랫동안 중단된 클라이언트의 임차권은 만료되어 쓰기를 거부할 수 있다.
• 잠금 서비스로 주키퍼를 사용하면 트랜잭션 ID zxid나 노드 버전 cversion을 펜싱토큰으로 사용할 수 있고 이들은 단조 증가가 보장된다.

4.2. 비잔틴 결함

• 노드가 고의로 시스템의 보장을 무너뜨리기 위해 가짜 펜싱 토큰을 포함한 메시지를 보낼 수 있다.
• 노드들은 느리거나 응답하지 않을 수 있고 그들의 상태는 뒤쳐질 수도 있지만 노드가 응답한다면 그 노드는 진실을 말한다고 가정한다. (프로토콜의 규칙에 따라 동작한다.)
• 분산 시스템의 노드가 거짓말을 할지도 모른다는 위험이 있다면 훨씬 더 어려워진다.
• 어떤 노드가 실제로 받지 않은 특정 메시지를 받았다고 주장하는 동작을 비잔틴 결함이라고 하며 신뢰할 수 없는 환경에서 합의에 도달하는 문제를 비잔틴 장군 문제라고 한다.
• 비잔틴 장군 문제 - 두 장군 문제 (304p)
• 일부 노드가 오작동하고 프로토콜을 준수하지 않거나 악의적인 공격자가 네트워크를 방해하더라도 시스템이 계속 올바르게 동작한다면 이 시스템은 비잔틴 내결함성을 지닌다.
• 비잔틴 내결함성을 지닌 시스템은 비잔틴 장군 문제를 해결할 수 있다.
• 웹 애플리케이션은 최종 사용자가 제어하는 웹브라우저 같은 클라이언ㅌ의 행동이 임의적이고 악이적이라고 예상해야 한다.
  • SQL 인잭션, 크로스 사이트 스크립팅, CSRF, 클릭재킹, DDoS
• 모든 노드가 동일한 소프트웨어를 실행하고 있기 때문에 공격자가 노드 하나를 침해한다면 모든 노드를 침해할 수 있다.

4.2.1. 약한 형태의 거짓말

• 약한 형태의 거짓말: 하드웨어 문제, 소프트웨어 버그, 잘못된 설정으로 유효하지 않은 메시지
• 약한 형태의 거짓말로부터 보호해주는 메커니즘을 소프트웨어에 추가하는 게 가치가 있을 수 있다.
  • 애플리케이션 수준 프로토콜에서 체크섬을 사용한다.
  • 사용자 입력값을 신중하게 살균(검증)한다.
  • NTP 서버를 사용할 때는 여러 개의 서버를 사용하고 그들의 응답을 비교한다.

4.3. 시스템 모델과 현실

• 알고리즘은 하드웨어와 소프트웨어 설정의 세부 사항에 너무 심하게 의존하지 않는 방식으로 작성해야 한다.
• 시스템에서 발생할 것으로 예상되는 결함의 종류를 어떻게 정형화해야한다.
• 시스템 모델을 정의해서 정형화하는데 시스템 모델은 알고리즘이 가정하는 것을 기술한 추상화다.
  • 동기식 모델: 네트워크 지연, 프로세스 중단, 시계 오차 모두 제한이 있다고 가정
  • 부분 동기식 모델: 대부분의 시간에는 동기식으로 동작하지만 때때로 네트워크 지연, 프로세스 중단, 시계 드리프트 한계치를 초과할 수 있다고 가정
  • 비동기식 모델: 타이밍에 대한 어떠한 가정도 할 수 없음
• 노드 장애를 고려하기 위한 노드용 시스템 모델
  • 죽으면 중단하는 결함
  • 죽으면 복구하는 결함
  • 비잔틴 결함

4.3.1. 알고리즘의 정확성

• 알고리즘의 정확하다는 게 어떤 의미인지 정의하기 위해 알고리즘의 속성을 기술할 수 있다.
• 정확하다는 게 어떤 뜻인지 정의하고 싶은 분산 시스템의 속성을 써볼 수 있다.
• 펜싱 토큰이라면 유일성, 단조 일련번호, 가용성
• 모든 노드가 죽거나 모든 네트워크 지연이 갑자기 무한히 길어진다면 어떤 알고리즘이라도 아무것도 할 수 없다.

4.3.2. 안정성과 활동성

• 안정성(safety): 유일성, 단조 일련번호
• 활동성(liveness): 가용성
• 활동성은 eventually 라는 단어를 포함한다. (최종적 일관성: eventually consistency)
• 안정성이 위반되면 그 속성이 깨진 시점을 가리킬 수 있어야 한다. 위반된 후에는 취소할 수 없다.
• 활동성은 시점을 정하지 못할 수는 있지만 항상 미래에 만족시킬 수 있다는 희망이 있다.
• 분산 알고리즘은 시스템 모델의 모든 상황에서 안정성이 항상 만족되기를 요구하는게 일반적이다.
• 활동성 속성에 대해서는 경고를 하는게 허용된다. - 노드의 다수가 죽지 않고 네트워크가 복구됐을 때만 요청이 응답받아야 한다.

4.3.3. 시스템 모델을 현실 세계에 대응시키기

• 안정성 및 활동성 속성과 시스템 모델은 분산 시스템의 정확성을 따져보는 데 매우 유용하다.
• 그러나 현업에서 알고리즘을 구현할 때 현실의 지저분한 사실들이 여러분을 곤란하게 만든다.
  • 죽으면 복구하는 모델에서 디스크의 데이터가 오염되거나, 하드웨어 오류, 잘못된 설정으로 데이터가 삭제된다면?
  • 정족수 알고리즘에서 노드가 저장했던 데이터를 잊어버리고 정족수 조건을 깨뜨린다면?
• 알고리즘이 올바르다고 증명됐더라도 반드시 현실 시스템에서의 구현도 언제나 올바르게 동작한다고 보장할 수 없다.
• 그렇지만 알고리즘을 이론적으로 분석하여 실제 시스템에 오랫동안 숨어 있다가 흔치 않은 상황 때문에 가정이 깨질 때만 나타나서 알고리즘의 문제를 드러낼 수 있다.
• 알고리즘의 이론적 분석과 경험적 실험은 똑같이 중요하다.