결함과 부분 장애
단일 환경의 프로그래밍은 보통 예측 가능하고 결정적인 방식으로 동작한다. 예측 가능함과 결정적의 의미는 하드웨어가 올바르게 동작하면 같은 연산은 항상 같은 결과를 만든다. 또한 하드웨어에 문제가 있더라도 보통 시스템이 완전히 실패하는 결과를 만들기 때문에 중간 상태가 없다. 현실 세계의 불분명한 물리적 문제를 감추고 수학적 완벽함을 갖고 동작하는 이상화된 시스템 모델을 보여준다.
네트워크로 연결된 분산 환경 프로그래밍은 단일 환경과는 근본적으로 상황이 다르다. 물리 세계의 지저분한 현실을 마주해야 한다. 예측할 수 없는 방식으로 고장 나는 시스템의 일부분들은 비결정적인 부분 장애를 만든다. 심지어 성공 했는지 아닌지 알지 못하는 경우도 많다.
비결정성과 부분 장애 가능성이 분산 시스템을 다루기 어렵게 한다.
부분 장애 대응 철학
분산 시스템에서 일부 노드에 부분 장애가 발생 했을 때, 대응할 수 있는 철학들이 있다.
1. 전체 시스템을 실패하게 만들기
고성능 연산을 수행하는 슈퍼 컴퓨터 시스템들은 주기적으로 계산 상태를 지속성 있는 저장소에 체크포인트로 저장한다.
시스템의 노드에서 문제가 발생할 경우 단일 노드의 커널 패닉이 일어난 것 처럼 모든 노드 전체를 실패 처리하고, 해당 노드가 복구된 다음 마지막 체크포인트 부터 다시 계산을 수행한다.
2. 부분 장애를 허용하기
시스템의 노드에서 문제가 발생해도, 전체에 전파시키지 않는다. 시스템이 문제가 발생한 노드를 감내하고 전체적으로 계속 동작할 수 있도록 한다. 이를 통해 다음의 이점을 얻을 수 있다.
- 여러 인터넷 서비스들은 사용자게에 지연이 낮은 서비스 제공을 목표로 한다. 이런 인터넷 서비스를 구성하는 시스템은 일부 노드의 실패 때문에 전체 서비스가 실패해선 안된다.
- 시스템의 규모가 커지면 커질 수록 구성 노드가 고장날 가능성은 커진다. 전체 시스템으로 문제를 확대하는 방식은 시스템이 유용한 일을 하기 보단, 복구하는데 시간을 쓰게 될 수도 있다.
- 유지/보수의 유용성을 위해 일부 노드들을 순회하며 재시작할 수도 있으며, 노드에 문제가 생겨도 교체가 간단하다.
어떤 철학을 선택할지는 시스템의 목표와 특징마다 다르다. 하지만 우리는 인터넷 서비스를 구현하는 시스템을 집중적으로 다룬다.
분산 시스템이 동작하게 만들려면 부분 장애 가능성을 받아들이고 소프트웨어에 내결함성 매커니즘을 넣어야 한다. 이를 통해 신뢰성 없는 구성 요소를 사용해 신뢰성 있는 시스템을 구축해야 한다.
결함이 생기지 않을거란 믿음은 현명하지 못하다. 발생 가능성이 낮더라도 생길 수 있는 결함을 광범위하게 이해하고, 테스트 환경에서 인위적으로 이런 상황을 만드는 등의 의심, 비관주의 그리고 편집증은 값어치가 있다.
신뢰성 없는 구성 요소를 사용해 신뢰성 있는 시스템 구축하기
직관적으로 시스템은 구성 요소 중 가장 신뢰성이 낮은 것 만큼만 신뢰성을 제공할 수 있을 것 같지만 사실은 그렇지 않다. 신뢰성이 낮은 환경에서 신뢰성이 높은 시스템은 구축하는 것은 오래된 아이디어이다.
- 오류 수정 코드는 무선 네트워크에서 발생하는 전파 장애 등의 이유로 가끔 일부 비트가 잘못 되는 통신 채널을 토해 디지털 데이터를 정확히 전송할 수 있게 해 준다.
- IP 프로토콜은 신뢰성이 없으나, 이를 TCP 프로토콜을 이용해 신뢰성을 확보한다.
하지만 신뢰성을 얼마나 높일 수 있는지는 항상 제한이 있다. 예를들어 오류 수정 코드는 소량의 단일 비트 오류는 처리할 수 있지만, 신호가 전파 방해에 심한 영향을 받으면 통신 채널을 통해 전송할 수 있는 데이터의 양에 근본적으로 제한이 생긴다. TCP는 패킷 손실/중복/순서가 섞이는 문제는 감추지만 네트워크 지연을 해결해주진 못한다.
신뢰성 없는 네트워크
비공유 분산 시스템은 네트워크로 연결된 다수의 장비로 구성된다. 각 장비는 네트워크로만 통신 가능하며, 자신만의 메모리와 디스크를 가지고 있고, 다른 장비의 디스크나 메모리에 접근할 수 없다고 가정한다.
비동기 패킷 네트워크
비동기 패킷 네트워크에서 노드는 다른 노드로 패킷을 보낼 수 있지만, 네트워크는 메시지가 언제 도착할지 혹은 메시지가 도착하기는 할 것인지를 보장하지 않는다. 다양한 이유로 여러 가지가 잘못될 수 있다.
전송 측은 패킷이 전송됐는지 아닌지조차 구별할 수 없기 때문에, 수신 측의 응답을 이용해야 전송 성공 여부를 알 수 있다. 하지만 이 응답 또한 지연 및 손실될 수 있으며 이런 문제는 비동기 네트워크에서 구분할 수 없다.
이런 문제를 다루는 보편적인 전략은 타임아웃이다. 일정 시간이 지날때 까지 응답이 오지 않으면 응답지 오지 않는 것으로 간주한다. 요청이 네트워크 어딘가의 큐에 들어있다면, 전송측이 요청을 포기 했더라도 메시지가 수신측에 도착할 수도 있다.
현실 세계의 네트워크
현실 세계의 네트워크는 다양한 원인으로 다양한 문제가 나타날 수 있다. 매우 낮은 확률이더라도 시스템에서 네트워크로 인한 결함이 발생할 수 있고, 시스템을 구성하는 소프트웨어가 이를 처리할 수 있어야 한다.
처리라고 하는 것이 꼭 강한 내결함성을 의미하는 것은 아니다. 네트워크의 신뢰성이 높다면 네트워크에 문제가 있을 때 그냥 사용자에게 오류를 보여줄 수도 있다. 다만 중요한 것은 소프트웨어가 네트워크 문제에 대해 어떻게 반응하는지, 시스템이 그것으로 부터 복구될 수 있는지다.
이런 이해도를 기르기 위해 고의로 네트워크를 문제를 유발하고 관찰할 수도 있다.
결함 감지
시스템이 올바르게 동작하기 위해 결함이 있는 노드를 감지할 수 있어야 한다. 하지만 네트워크의 불확실성 때문에 노드가 동작 중인지 구별하기 어렵다. 특정 환경은 뭔가 동작하지 않는다는 명시적 피드백을 받을 수도 있다.
- TCP 연결을 요청 했을 때 목적지 포트에서 수신 대기하는 프로세스가 없으면 OS가 RST나 FIN을 응답으로 보내 TCP 연결을 닫거나 거부한다. 그러나 노드가 요청을 처리하다 죽었다면 얼마나 처리 되었는지 알 수 있는 방법은 없다.
- 노드 프로세서가 죽었지만 노드의 운영체제가 실행 중이라면 스크림트로 나른 노드에게 자신의 프로세스가 죽었음을 알려 다른 노드가 타임아웃이 만료되기를 기다릴 필요 없이 문제가 생겼음을 즉각 알게 한다.
- 네트워크를 구성하는 하드웨어에 접근할 수 있다면, 모니터링을 통해 하드웨어 수준의 장애를 감지할 수 있다.
- 접속하려는 IP 주소에 도달할 수 없다고 라우터가 확신하면 ICMP Destination Unreachable 패킷으로 응답할 수도 있다.
원격 노드가 다운되고 있다는 피드백은 유용하지만 여기에 의존할 수 없다. 예를 들어 TCP를 통해 전송한 패킷에 대해 ACK를 수신하더라도, 그 요청이 애플리케이션에서 처리 되었는지는 알 수 없다. 이를 알 수 있는 방법은 애플리케이션에서 명시적으로 긍정 응답을 얻는 것이다.
또한 무엇인가 잘못 된다면 아무 응답이 오지 않을 수도 있다고 가정해야 한다. 몇 번 재시도를 해 보고 타임아웃 내에 응답을 받지 못하면 그때서야 마침내 노드가 죽었다 판단할 수 있다.
타임아웃과 기약 없는 지연
타임아웃은 얼마나 길어야 할까? 이를 위한 쉬운 답은 없다.
타임아웃이 길면 노드가 죽었음을 선언하기까지 시간이 오래 걸리며, 사용자들은 그동안 대기하거나 오류 메시지를 봐야 한다. 하지만 너무 짧다면 일시적으로 느려졌음에도 죽었다고 판단될 수 있다.
성급하게 노드가 죽었다고 판단하는 것은 문제가 된다. 노드가 실제로 살아 있다면, 그 노드의 역할을 다른 노드가 대체하는 동안 두 번 동작할 수 있다.
또한 해당 노드의 책무를 다른 노드에게 위임하는 것 또한 비용이다. 특히 시스템이 고부하에 의해 일시적으로 느려졌다면 이런 행위는 연쇄 장애를 유발할 수 있다.
비동기 네트워크는 패킷의 도착하는데 걸리는 상한치가 없는 기약 없는 지연이 있고, 서버 구현은 대부분 어떤 최대 시간 내에 요청을 처리 한다고 보장할 수 없다.
네트워크 혼잡과 큐 대기
네트워크에 패킷 지연의 변동성은 큐 대기 때문인 경우가 많다. 큐를 이용하는 경우들은 다음과 같다.
- 여러 다른 노드가 동시에 같은 목적지로 패킷을 보내려고 할 경우, 네트워크 스위치는 패킷을 큐에 넣고 한 번에 하나씩 목적지 네트워크 링크로 넘겨야 한다. 이때문에 네트워크가 잘 동작 하더라도 들어오는 데이터가 많아서 스위치 큐를 꽉 채울 정도가 되면 패킷이 유실되어 재전송해야 한다.
- 패킷이 목적지 장비에 도착 했더라도 CPU 코어가 바쁜 상태라면 네트워크 패킷은 애플리케이션이 처리할 때까지 운영체제 큐에 넣어 둔다. 장비의 부하에 따라 큐에서 대기하는 시간은 제각각이다.
- 가상 환경에서 실행되는 운영체제는 다른 가상 장비가 CPU 코어를 사용하는 동안 수십 밀리초 동안 멈출 때가 흔하다. 이 시간 동안 가상 장비는 네트워크에서 어떤 데이터도 받아들일 수 없으므로 가상 장비 모니터가 들어오는 데이터를 큐에 넣어 네트워크 지연 변동성을 더욱 증가시킨다.
- TCP는 흐름 제어를 수행한다. 자신의 송신율을 제한하기 때문에 네트워크에 들어가기 전에도 지연이 발생할 수 있다.
이런 문제는 시스템이 최대 용량에 가까울 때 특히 광범위하게 일어난다. 지연성의 변동이 얼마나 되는지 알아내기 위해선 긴 시간에 걸쳐 네트워크 왕복 시간의 분포를 측정해야 한다. 그 후 애플리케이션의 특징을 감안하여 적절한 타임아웃을 정할 수 있다.
더 좋은 방법은 고정된 타임아웃 대신 시스템이 지속적으로 응답 시간과 그들의 변동성을 측정하고 응답 시간 분포에 따라 타임아웃을 자동으로 조절하게 하는 것이다.
동기 네트워크 대 비동기 네크워크
패킷 전송 지연 시간의 최대치가 고정돼 있고 패킷을 유실하지 않는 네트워크에 기댈 수 있다면 분산 시스템은 더 간단해질 수 있다. 하지만 왜 이런 문제가 하드웨어 수준에서 해결되지 못하고 소프트웨어 수준에 영향을 주는 것일까?
동기식 네트워크
고정회선 전화 네트워크를 통해 문제를 알아볼수 있다. 전화 네트워크는 극단적으로 높은 신뢰성을 유지하기 위해 각 회선마다 고정 대역폭을 네트워크에 할당한다. 양 끝단의 노드들 사이의 전체 경로 구간에서 해당 통화에 대해 고정되고 보장된 양의 대역폭이 할당된 회선을 생성한다. (대역폭을 할당할 수 없다면 회선 생성을 허용하지 않는다.)
이런 종류의 네트워크를 동기식 네트워크라고 부르며, 모든 네트워크 홉에 고정된 대역폭이 할당 되었기 때문에 데이터가 여러 라우터를 거치더라도 큐 대기 문제를 겪지 않는다. 또한 큐 대기가 없다면 네트워크는 종단 지연 시간의 최대치가 고정 되어 있다. 이를 제한 있는 지연이라고 한다.
회선 & 패킷 교환
회선은 만들어져 있는 동안은 다른 누구도 사용할 수 없는 고정된 양의 대역폭이다. TCP 패킷은 이와 다르게 가용한 네트워크 대역폭을 기회주의적으로 사용한다. TCP 패킷은 연결(전화 네트워크와는 다른 개념의 회선)이 맺어져 있더라도 유휴 상태에 있을 때는 네트워크의 대역폭을 점유하지 않는다.
이더넷과 IP는 회선 개념이 없는 큐 대기의 영향을 받는 패킷 교환 프로토콜이기 때문에 네트워크에 기약 없는 지연이 있다. 하지만 패킷 교환은 순간적으로 몰리는 트래픽에 최적화 되어 있다. 회선은 통화를 하는 동안 초당 비트 개수가 상당히 정돼 있는 음성과 영상 통화에 적합하다. 반면 가능하면 빨리 처리되기를 원하기만 하는 트랜잭션들은 대역폭에 대해 특별한 요구사항이 없기 때문에 패킷 교환 알고리즘이 네트워크를 효율적으로 사용할 수 있다.
결국 제한된 지연등의 특징을 위해 정적으로 네트워크에 대역폭을 할당하여 비효율을 감수하느냐, 기약 없는 지연을 감지하고 네트워크를 효율적으로 사용할지 선택해야 한다.
신뢰성 없는 시계
애플리케이션은 지속 시간을 측정하거나 시점을 기술하는 등의 문제 해결을 위해 시계를 이용한다.
하지만 분산 시스템의 통신은 즉각적이지 않기 때문에 시간은 다루기 까다롭다. 메시지를 받은 시간은 항상 보낸 시간보다 나중이지만, 얼마나 나중일지는 알 수 없다. 이러한 상황은 여러 노드에 걸쳐 어떤 일이 발생한 순서를 알아내기 어렵게 만든다.
또한 개별 노드의 장비의 시간은 모두 정확히 같지 않다. 시간을 어느정도 동기화할 수 있는 수단들이 있지만 정확하지 않기 때문에 다른 노드들보다 조금 빠르거나 느릴 수 있다.
일 기준 시계 VS 단조 시계
현대의 컴퓨터는 최소 두 가지 시계를 가지고 있다. 둘은 다른 목적으로 사용 되기 때문에 이를 구분할 수 있어야 한다.
일 기준 시계
어떤 달력에 따라 현재 날짜와 시간을 반환한다. 예를 들어 UTC 1970/01/01을 가리키는 epoch 이래로 흐른 초나 밀리초를 반환한다. 리눅스의 clock_gettime(CLOCK_REALTIME) 그리고 자바의 System.currentTimeMillis() 등이 있다. (시스템에 따라 기준 시간은 다를 수 있다.)
일 기준 시계는 보통 NTP로 동기화 되고, 한 장비의 타임스템프는 다른 장비의 타임스템프와 동일한 의미를 지닌다. 하지만 일 기준 시계는 로컬 시계가 NTP 서버보다 너무 앞서면 강제로 리셋되어 과거 시점으로 거꾸로 뛰는 것 처럼 보이기도 한다. 또한 윤초를 무시한다.
단조 시계 (시간이 항상 앞으로 흐름)
단조 시계는 타임아웃이나 서비스 응답 시간 같은 지속 시간을 재는데 적합하다. clock_gettime(CLOCK_MONOTONIC) 이나 System.nanoTime()이 있다.
한 시점에 단조 시계의 값을 확인하고 어떤 일을 한 후 나중에 시간을 다시 잴 수는 있고 두 값 사이의 차이로 시간이 얼마나 흘렀는지 알 수 있다. 하지만 시간의 절대적인 값 자체는 의미가 없으며, 특히 서로 다른 노드에서 나온 단조 시계 값을 비교하는 것은 의미가 없다.
여러 개의 CPU 소켓이 있는 장비들은 CPU 마다 독립된 타이머가 있을 수 있다. 이 타이머는 다른 CPU와 반드시 동기화 되는 것이 아니다. 애플리케이션 스레드가 여러 CPU에 걸쳐 스케쥴링 되더라도 운영체제가 이를 보정하여 시계가 단조적으로 보이게 하려 한다.
하지만 그럼에도 불구하고 단조성 보장은 곧이 곧대로 받아들이지 않는 것이 현명하다.
NTP는 컴퓨터의 로컬 시계가 NTP 서버보다 빠르거나 느리다는 것을 발견하면 단조 시계가 진행하는 진도수를 조정할 수 있다. 통상 0.05%까지 올리거나 내리는걸 허용하지만 단조 시계가 앞이나 뒤로 뛰게할 수는 없다.
분산 시스템에서 경과 시간을 재는 데 단조 시계를 쓰는 것은 일반적으로는 괜찮다. 다른 노드의 시계 사이에 동기화 되어야 한다는 가정이 없고 측정이 약간 부정확해도 민감하지 않기 때문이다.
시계 동기화와 정확도
일 기준 시계는 NTP 서버나 다른 외부 시간 출처에 맞춰 설정돼야 유용하다. 하지만 시계가 정확한 시간을 알려주게 하는 방법은 그렇게 신뢰성이 있거나 정확하지 않다.
- 컴퓨터의 수정 시계는 아주 정확하지 않다. 장비 온도에 따라 시간이 더 빠르게 흐르거나 느리게 흐르는 드리프트 현상이 생길 수 있다.
- 컴퓨터 시계가 NTP와 너무 큰 차이가 나면 시간이 리셋될 수 있다.
- 노드와 NTP 서버의 네트워크에 문제가 생길 수 있으며 지연이 발생해 시간차가 발생할 수 있다.
- 네트워크에 있는 일부 NTP는 잘못된 시간값을 가지고 있다.
- 윤초가 발생하면 1분의 길이가 59초나 61초가 되어 이를 고려하지 않은 시스템에서 문제를 일으킬 수 있다.
- 가상 장비에서 하드웨어 시계는 가상화된다. CPU 코어가 다른 가상 장비 사이에서 공유될 때 각 VM은 다른 VM이 실행될 동안 수십 밀리초 동안 멈춘다. 애플리케이션에서는 시간이 갑자기 앞으로 뛰는 문제로 나타난다.
- 신뢰할 수 없는 하드웨어를 통해 고의로 시간을 올바르지 않게 설정할 수 있다.
시간과 관련된 문제는 조금씩 달라지는 시간값의 차이에 의해 발생하기 때문에 인지하기 어렵고 미묘하다. 또한 시스템에 조금씩 문제를 전파해간다. 따라서 고장난 시계를 알아챌 수 있는 시스템이 필요하다.
이벤트 순서화용 타임스탬프
시계에 의존하고 싶지만 고려해야할 점이 많다.
리더 노드에서 발생한 데이터를 복제 노드에 복제할 때, 리더 노드와 복제 노드간의 일 기준 시계가 동기화 되어 있지 않다면 이벤트의 선후 관계가 섞일 수 있다. 특히 최종 쓰기 전략등에서 문제를 일으킬 수 있다. 또한 동일한 타임스탬프 값을 가지는 데이터들의 충돌도 발생할 수 있다.
논리적 시계는 수정 시계 대신 증가하는 카운터 기반이며 이벤트 순서화에 대한 안전한 대안이다. 논리적 시계는 일 기준 시간이나 경과한 초 수를 측정하지 않고 이벤트의 상대적 순서만 측정한다. (이와 반대로 일 기준 시계와 단조 시계는 실제 경과 시간을 측정하며 물리적 시계라고 한다.)
시계 읽기의 신뢰 구간
단일 장비 기준으로 일 기준 시계를 여러 해상도로 읽을 수는 있으나, 그것이 실제 시간과의 정확도를 의미하지 않는다. NTP와 매분 동기화 하더라도 수정 시계의 드리프트는 쉽게 몇 밀리 초가 될 수 있다. 또한 공개 인터넷의 NTP를 사용하면 달성 가능한 최선의 정확도는 아마도 수십 밀리초 정도 될것이며, 네트워크 혼잡이 있으면 100밀리초 이상으로 급증한다.
따라서 시계 읽기를 어떤 시점으로 생각하는 것은 타당하지 않다. 어떤 신뢰 구간에 속하는 시간의 범위로 읽는 것이 나을 것이다.
불확실성의 경계는 시간 출처를 기반으로 계산할 수 있다. 하드웨어 시계들은 제조사에서 제공하는 예상 오류의 범위가 있다. 시간을 서버에서 얻는다면 불확실성은 서버와 마지막으로 동기화한 시간 이후로 예상되는 시계 드리프트에 NTP 서버의 불확실성을 더하고 그 서버와 통신할 때 걸리는 네트워크 왕복 시간을 더한 값을 기반으로 한다.
많은 시스템은 불확실성의 범주에 대해 응답하지 않으나, 구글 트루타임 API 처럼 로컬 시계의 신뢰 구간을 응답하는 것들도 있다. 이 API는 현재 시간 조회 요청에 대해 가능한 타임스탬프 범위 중 가장 이른값과 가장 늦은값을 반환한다. 이를 통해 실제 시간이 그 구간 사이 어딘가에 있다는 것을 알 수 있다.
전역 스냅숏용 동기화된 시계
스냅숏 격리를 위해 단조 트랜잭션 ID가 필요하다. 단일 노드 데이터베이스는 문제 없으나 분산 노드 데이터베이스는 코디네이션이 필요하므로 전역 노드에 따른 단조 트랜잭션 ID를 만들기 어렵다.
하지만 시간 동기화의 문제로 시간값을 이용하기는 힘드나, 신뢰구간을 알 수 있다면 신뢰 구간이 겹치지 않았을 경우엔 트랜잭션간의 선후 관계를 명시적으로 알 수 있다. 트랜잭션의 타임스탬프가 인과성(트랜잭션의 선후 관계)을 반영하는 것을 보장하기 위해 트랜잭션을 커밋하기 전에 신뢰 구간의 길이만큼 대기한다. 이때 대기 시간을 줄이기 위해 신뢰 구간을 좁히는 것이 중요하다.
하지만 이런 방식은 아직 연구중이며, 주류 데이터베이스 시스템중 구글을 제외하고는 이런 시스템을 구현한 곳이 없다고 한다.
프로세스 중단
분산 시스템에서 시계를 위험하게 사용하는 예시 중 하나는 임차권이다. 임차권은 리더의 역할을 유지하기 위해 정해진 시간마다 다른 노드들에게 임차권을 받는 매커니즘이다. 특정 시점에 오직 하나의 리더만 임차권을 얻을 수 있기 때문에 임차권을 얻은 리더는 일정 시간동안 자신이 리더임을 보장할 수 있다. 그리고 해당 노드가 계속 리더를 유지하기 위해 주기적으로 임차권을 획득하도록 시도한다.
while (true) {
request = receiveIncomingRequest();
// 임차권의 만료 시간은 다른 장비에서 설정한다.
if (lease.expiryTimeMillis - System.currentTimeMillis() < 10_000L) {
lease = lease.renew();
}
if (lease.isValid()) {
process(request);
}
}
위의 코드는 다음의 문제를 가진다.
- 임차권의 만료 시간이 다른 장비에서 설정 되었는데, 그것을 현재 장비의 시간과 비교하고 있다. 이는 시간 동기화의 문제로 인한 시간이 때문에 올바르게 동작 못할 수 있다.
- 로컬 단조 시계만 사용하도록 프로토콜을 수정하더라도, 시간을 확인하는 시점과 요청을 처리하는 시점 사이에 매우 짧은 시간이 흐른다고 가정한다. 하지만 예상치 못한 긴 중단이 있으면 어떨까?
우리는 스레드가 아주 오랫동안 중단될거라 쉽사리 생각하지 않지만, 실제로 이런 일들은 발생할 수 있다.
- (자바 가상 머신 같은) 여러 프로그래밍 언어는 런타임에 가끔 모든 실행을 중단 시키는 가비지 컬렉터가 있다. stop-the-world 가 발생하는 빈도와 시간은 조절할 수 있지만, 견고한 시스템을 제공하기 위해선 최악의 상황을 가정해야 한다.
- 가상 환경에서 가상 장비는 Suspend/Resume 될 수 있다. 프로세스 실행 중 언제나 발생할 수 있고 임의의 시간동안 지속될 수 있다.
- 노트북 같은 장비도 Suspend/Resume이 될 수 있다.
- 애플리케이션이 동기화 I/O를 수행한다.
- 운영체제가 디스크로 스왑할 수 있게 설정 되어있다면, 단순히 메모리에 접근만 해도 페이지를 디스크에서 메모리로 로드하는 I/O가 발생할 수 있다.
- 유닉스 프로세스는 SIGSTOP을 보내서 멈출 수 있다.
이런 경우가 발생하면 실행 중인 스레드를 어떤 시점에 선점하고 얼마간의 시간이 흐른 뒤 다시 수행할 수 있다. 하지만 컨텍스트 스위치가 임의로 발생할 수 있고 병렬성이 발생할 수도 있으므로 타이밍에 대한 어떤 가정도 할 수 없다.
분산 시스템의 노드는 어느 시점에 실행이 상당한 시간 동안 멈출 수 있다고 가정해야 한다. 심지어 함수 중간에 멈출 수도 있다. 해당 노드가 멈춘 동안 외부 세계는 계속 움직이기 때문에 해당 노드가 응답하지 않을 때 죽었다고 판단할 수도 있다. 해당 노드는 결국엔 다시 실행 되겠지만, 얼마 후 시계를 다시 확인할 때까지 잠들었다는 것을 알아채지 못한다.
응답 시간 보장
하드 리얼타임 시스템은 실시간 운영체제와 여러 노력을 바탕으로 최악의 시간내에 동작을 만족시킨다. 이를 위해 많은 양의 부가작업이 필요하고 사용할 수 있는 도구들의 범위를 엄격히 제한한다. 이런 이유들로 시스템의 개발은 매우 많은 비용이 든다. 또한 시간내에 응답하는 것을 보장해야 하기 때문에 성능은 더 나쁠 수도 있다.
우리가 다루는 서버측 데이터 처리 시스템에 응답 시간 보장 매커니즘은 경제적이지도 않으며 적절하지도 않다. 이런 시스템은 비실시간 환경에서 운영될 때 발생하는 중단과 시계 불안정으로부터 고통 받을 수 밖에 없다.
가바지 컬렉션 영향을 제한하기
이런 문제의 원인 중, 가비지 컬렉션으로 부터 발생하는 문제를 완화하는 전략들이 있다. 그 중 하나는 GC 중단을 노드가 잠시 계획적으로 중단하는 것으로 간주하고, 노드가 가비지 컬랙션을 하는 동안 클라이언트로부터의 요청을 다른 노드들이 처리하게 하는 것이다. 런타임이 애플리케이션에게 노드가 곧 GC 중단이 필요하다는 경고를 할 수 있다면 애플리케이션은 그 노드로 새로운 요청을 보내는 것을 멈추고, 그 노드가 처리되지 않은 요청을 완료한 후 아무요청도 처리하지 않는 동안 GC를 실행하기를 기다릴 수 있다.
이 전략의 변종은 수명이 짧은 객체만 GC를 사용하고, 수명이 긴 객체의 전체 GC가 필요할 만큼 객체가 쌓이기 전에 주기적으로 프로세스를 재시작하는 방법이다. 한 번에 한 노드씩 순차적으로 재시작하며 트래픽을 다른 노드로 옮길 수 있다.
지식, 진실 그리고 거짓말
지금까지 살펴본것과 같이 분산 시스템은 신뢰할 수 없는 네트워크를 통해 메시지를 보낼 수 있을 뿐이며 부분 장애, 신뢰성 없는 시계 그리고 프로세스 중단에 시달릴 수 있다.
분산 시스템에 익숙하지 않다면 이런 문제들은 매우 혼란스럽다. 네트워크에 있는 노드는 어떤 것도 확실히 알 수 없다. 네트워크를 통해 받은(또는 받지 않은) 메시지를 기반으로 추측만 할 수 있다. 원격지의 노드가 응답하지 않더라도 네트워크 문제인지 노드 자체의 문제인지 구분할 수 없다.
인식하고 측정하는 수단을 갖추기 위해, 분산 시스템에서 동작에 관해 정의한 가정을 명시하고, 이런 가정을 만족시키는 방식으로 실제 시스템을 설계할 수 있다. 어떤 시스템 모델 내에서 알고리즘이 올바르게 동작하는지 증명할 수 있다. 기반 시스템 모델이 매우 적은 보장만 제공하더라도 신뢰성 있는 동작을 달성할 수 있다.
진실은 다수결로 결정된다.
노드는 상황에 대한 자신의 판단을 반드시 믿을 수 있는 것은 아니다. 분산 시스템은 하나의 노드에 의존할 수 없다. 따라서 분산 알고리즘은 노드 사이의 투표인 정족수에 의존한다. 특정 노드 하나에 의존을 줄이기 위해선 최소 개수의 투표를 받아야 한다.
통상 노드의 과반수를 정족수로 삼으면 개별 노드들에 장애가 나더라도, 최소 구성수 이상이라면 시스템은 계속 동작할 수 있다.
리더와 잠금
시스템이 오직 하나의 주체가 필요할 때가 있다. 분산 시스템에서 이것을 구현하려면 주의해야 한다. 특정 노드가 스스로를 선택된 주체라고 생각할지라도, 다른 노드들의 합의와는 다를 수 있다.
선택된 노드가 무엇인가의 문제로 죽은 것으로 판단 되어 새로운 노드를 선택했을 때, 죽은줄 알았던 노드가 돌아와 선택된 노드인 것 처럼 행동할 수도 있다. 이는 오직 하나의 선택된 노드라는 규칙을 어기게 되고 시스템에 문제를 일으킬 수 있다.
펜싱 토큰
위의 문제를 피하기 위해 정족수에 의해 선택 받지 못한 노드가 시스템을 방해할 수 없도록 보장해야 한다. 펜싱 토큰 같은 방법으로 이 문제를 간단히 해결할 수 있다.
임차권을 갱신할 때마다 펜싱 토큰을 함께 발급한다. 펜싱 토큰은 임차권 갱신이 승인될 때마다 증가하는 숫자값이며, 클라이언트는 쓰기 요청을 저장소에 보낼 때마다 이 토큰을 포함해야 한다.
클라이언트가 요청에 펜싱 토큰을 함께 보내면, 이를 수신한 저장소는 자신의 펜싱 토큰과 비교하여 오래 되었다면 요청을 버린고 올바르다면 처리한다. 자원 제공자가 토큰의 유효성을 검증해야 하는 책임이 있으며, 클라이언트들이 직접 펜싱 토큰을 이용하여 임차권 상태를 확인하는 것만으로는 충분하지 않다.
비잔틴 결함
시스템의 오류에는 부주의에 의한 오류와 고의적인 오류가 있다. 책에서 다루던 오류는 부주의하지만 선량하기 때문에 진실만 응답한다고 가정한다. 하지만 어떤 노드가 거짓말을 하다고 있다고 가정한다면, 분산 시스템의 문제는 더욱이 복잡해진다.
일부 노드가 오작동하고 프로토콜을 준수하지 않거나, 악의적인 공격자가 네트워크를 방해하더라도 시스템이 올바르게 동작하면 이 시스템을 비잔틴 내결함성을 가진다고 한다.
- 항공우주 산업 환경에서 컴퓨터 메모리나 CPU 레지스터에 저장된 데이터는 방사선에 오염돼서 그 컴퓨터가 다른 노드에게 전혀 예측할 수 없는 방식으로 반응할 수 있다. 이런 시스템은 장애 비용이 매우 크기 때문에 비잔틴 내성을 지녀야 한다.
- 여러 이해관계자가 참여하는 시스템에서 어떤 참여자는 시스템을 속이거나 편익을 취하기 위해 악의적인 메시지를 보낼 수 있다. 이런 환경에서 다른 노드의 메시지를 그대로 믿는 것은 안전하지 않다.
하지만 이 책에서 살펴보는 많은 종류의 시스템은 비잔틴 결함이 없다고 가정할 수 있다. 비잔틴 내성을 지니는 비용은 매우 비싸기 때문에 실용적이지 않기 때문에 이 시스템들에선 이 문제를 다루지는 않는다. 또한 비잔틴 내결함성은 웹 애플리케이션 처럼 중앙 권한이 있는 시스템보단 중앙 권한이 없는 P2P 네트워크에 더 적합하다.
또한 대부분의 비잔틴 내결함성 알고리즘은 노드의 2/3 이상의 압도적 다수가 올바르게 동작하기를 요구하기 때문에, 동일한 버그가 있는 소프트웨어를 모든 노드에 배포하면 내결함성을 기대할 수 없다.
약한 형태의 거짓말
선량한 노드들로 구성된 시스템도 약한 형태의 거짓말에 내한 내결함성을 가지는 것이 도움이 될 때가 있다. 약한 형태의 거짓말은 추상적으로 느껴질 수 있다. 여기에서는 탐지나 복구를 차단할 수 있는 경우의 수가 매우 적어 악의적인 형태가 아닌 버그나 오류로는 발생이 어려운 문제를 의미한다고 생각된다. 또한 악의적인 공격에 대한 내결함성은 없음으로 비잔틴 내결함성은 기대할 수 없으나 신뢰성 있는 시스템으로 조금 더 나아갈 수 있다.
- 간혹 네트워크 패킷의 체크썸은 검출을 피하는 경우도 있다. 이를 방지하기 위해 애플리케이션 레벨에서 체크썸을 고려해볼 수 있다.
- 통제할 수 없는 접점을 가진 애플리케이션은 사용자 입력을 신뢰하지 않고 적절한 소독 처리를 해야한다.
- NTP 클라이언트가 여러 서버를 참조하고, 그 중 비정상적인 응답을 하는 NTP 서버를 검출하여 동기화 대상에서 제거
시스템 모델과 현실
분산 시스템 문제를 해결하기 위한 많은 알고리즘들을 유용하기 위해선 분산 시스템의 다양한 결함을 견딜 수 있어야 한다. 알고리즘을 시스템에 적용하기 위해서 시스템에서 예상 되는 결함의 종류를 정형된 형태로 모델링 하여 알고리즘과 비교해야 한다.
타이밍 가정 관련 모델
- 동기식 모델
네트워크 지연, 프로세스 중단 그리고 시계 오차에 모두 제한이 있다고 가정한다. 시계가 정확히 동기화 되거나 네트워크에 지연이 없다고 암시하는 것이 아니다. 그 무엇도 결코 상한을 넘지 않는다는 것이다. 하지만 이 모델은 현실 시스템 대부분에서 현실적인 모델은 아니다. - 부분 동기식 모델
대부분의 경우엔 동기식 처럼 동작하지만 때때로 네트워크 지연, 프로세스 중단, 시계 드리프트의 한계치를 초과하는 모델이다. 이 모델은 많은 시스템에서 현실적인 모델이다. 가끔씩 타이밍 가정이 산산조각 날지도 모른다는 사실을 고려해야 한다. - 비동기식 모델
이 모델에서 알고리즘은 타이밍에 대한 어떠한 것도 가정할 수 없다. 심지어는 시계가 없을 수도 있다. 제한적인 알고리즘만 비동기식 모델용으로 설계할 수 있다.
노드 장애 관련 모델
- 죽으면 중단하는 결함
이 모델에서 알고리즘은 노드의 장애는 죽는 것으로만 나타난다. 노드가 갑자기 응답하기를 멈추면 그 이후로 노드는 영원히 사용할 수 없다. - 죽으면 복구하는 결함
노드가 어느 순간에 죽을 수 있지만 알려지지 않은 시간 뒤에 다시 동작할 것으로 가정한다. 죽으면 복구하는 모델에서 노드는 메모리에 있는 상태는 손실되지만 죽어도 데이터가 남아 있는 안정된 저장소가 있다고 가정한다. - 비잔틴(임의적인) 결함
노드는 지난 절에서 설명한 것처럼 다른 노드를 속이거나 기만하는 것을 포함해 적적으로 뭐든 할 수 있다.
죽으면 복구하는 결함 모델은 현실세계에서 가장 적합한 모델이다. 분산 알고리즘을 이에 대응하기 위한 것은 다음과 같다.
알고리즘의 정확성
알고리즘이 정확하다는 것의 의미를 정의하기 위해 알고리즘의 속성을 기술할 수 있다. 펜싱 토큰 알고리즘의 속성들을 통해 살펴보자.
- 유일성
펜싱 토큰 요청이 같은 값을 반환하지 않는다. - 단조 일련번호
요청 x가 토큰 Tx를, 요청 y가 토큰 Ty를 반환했고 y가 시작하기 전에 x가 완료 되었다면 Tx < Ty를 만족한다. - 가용성
펜싱 토큰을 요청하고 죽지 않은 노드는 결국에는 응답을 받는다.
알고리즘은 시스템 모델에서 발생하리라고 가정한 모든 상황에서 그 속성들을 항상 만족시키면 해당 시스템 모델에서 정확하다. 하지만 이를 이해하기 위해서는 두 가지 종류에서 속성이 만족하는지 판단해야 한다.
안정성과 활동성
알고리즘의 속성을 두 가지 종류로 구별할 필요가 있다. 안정성과 활동성이다. 펜싱 토큰에서 유일성과 단조성은 안정성이며, 가용성은 활동성이다. 보통 활동성은 '결국에는'이라는 표현이 포함된다.
- 안정성 속성이 위반되면 그 속성이 깨진 특정 시점을 가리킬 수 있다. 안정성 속성이 위반된 후에는 그 위반을 취소할 수 없다. 이미 손상된 상태에 빠져있다.
펜싱 토큰에서 같은 값을 반환할 경우, 실제 점유자가 아닌 노드가 연산을 요청할 수 있다. 이로인해 처리된 연산은 시스템에 오류를 만든다. - 활동성 속성은 어떤 시점을 정할 수는 없지만 항상 미래에 그 속성을 만족시킬 수 있다는 희망이 있다.
일반적으로 분산 알고리즘은 시스템 모델의 모든 상황에서 안정성 속성이 항상 만족하길 바란다. 모든 노드가 죽거나 네트워크 전체에 장애가 있더라도 알고리즘은 잘못된 결과를 반환하지 않는다고 보장할 수 있어야 한다.
그러나 활동성은 조금 다르다. 활동성 속성에 대해서는 경고만 하는 것도 허용된다. 시스템에 장애가 생기더라도 한정된 기간 동아만 지속된 후 복구되기를 요구한다.
시스템 모델을 현실 세계에 대응시키기
우리가 따져본 모델과 속성들은 사실 현실세계를 추상화하고 그것을 검토한 것에 지나지 않는다. 현실 세계의 지저분한 문제는 우리에게 더 많은 고민을 준다.
알고리즘을 이론적으로 설명할 때는 그냥 어떤일이 일어나지 않는다고 가정할 수도 있다. 비잔틴 시스템에서는 일어날 수 있는 결함과 없는 결함에 대한 가정을 동반한다. 하지만 실제 구현에서는 불가능하다고 가정했던 일이 발생하는 경우를 처리하는 코드를 포함시켜야 할 수도 있다.
하지만 이론적인 추상 모델이 쓸모 없다는 것이 아니다. 추상 시스템 모델은 현실 세계의 지저분함과 복잡함에서 우리가 추론할 수 있는 관리 가능한 결함의 집합을 뽑아내서, 문제를 이해하고 체계적으로 해결할 수 있게 도와준다. 어떤 시스템 모델에서 그것들의 속성이 항상 성립한다고 보여줌으로써 알고리즘이 올바르다고 증명할 수 있다.
하지만 알고리즘이 올바르다고 증명 됐다고 하더라도 반드시 현실 시스템에서의 구현도 언제나 올바르게 동작한다는 뜻은 아니다. 그럼에도 불구하고 알고리즘의 증명은 아주 좋은 첫걸음이며, 시스템에 잠재적으로 숨어있는 문제를 찾아내는 단초일 수도 있다.