데이터 중심의 애플리케이션 설계 - 시스템 모델과 현실

대부분의 알고리즘들은 분산 시스템 문제를 해결하기 위해 만들어졌다. 알고리즘은 하드웨어나 소프트웨어에 종속되지 않고 구동될 수 있도록 작성된다. 시스템에서 발생할 수 있는 여러 종류의 오류들을 형식화하는 작업이 시스템 모델링이다. 시스템 모델링은 일종의 알고리즘이 어떻게 동작하는지를 추상화한 것이다.

시각 문제와 관련한 시스템 모델

동기화 모델(Synchronous model)

동기식 모델은 제한된 네트워크 지연, 제한된 프로세스 지연, 제한된 시각 오류를 가정한다. 이는 정확히 동기화된 시각이나 제로 네트워크 지연을 의미하지는 않지만, 네트워크 지연, 일시 정지, 시각 드리프트가 정해진 상한을 넘지 않는다는 것을 의미한다. 동기 모델은 대부분의 실제 시스템에서 현실적인 모델이 아니다. 왜냐하면, 무제한 지연 및 일시 중지가 발생하기 때문이다.

부분 동기 모델

부분 동기화는 시스템이 대부분의 시간 동안 동기 시스템처럼 작동하지만 네트워크 지연, 프로세스 일시 중지 및 시각 드리프트의 한계를 넘는 경우가 있음을 의미한다. 부분 동기화는 대부분의 시스템에 맞는 현실적인 모델이다. 대부분의 경우 네트워크와 프로세스는 잘 작동하지만, 타이밍 가정이 때때로 깨질 수 있다는 사실을 고려해야 한다. 이 경우 네트워크 지연, 일시 정지, 시각 오류가 임의로 커질 수 있다.

비동기 모델

이 모델에서는 알고리즘에 어떤 타이밍 가정도 허용되지 않으며, 실제로 시계도 없으므로 타임아웃을 사용할 수 없다. 일부 알고리즘은 비동기 모델용으로 설계할 수 있지만 매우 제한적이다. 이외에도, 타이밍 문제 외에도 노드 장애를 고려해야 한다.

노드에 대한 가장 일반적인 세 가지 시스템 모델

크래시-스톱 결함

크래시-스톱 모델에서 알고리즘은 노드가 오직 크래시를 통해서만 실패할 수 있다고 가정한다. 즉, 노드가 어느 순간 갑자기 응답을 멈출 수 있으며, 그 이후에는 해당 노드가 영원히 사라지고 다시는 돌아오지 않는다.

크래시 복구 결함

노드는 언제든 충돌할 수 있으며, 예측 불가능한 시간이 지난 후 다시 응답을 시작할 수 있다고 가정한다. 크래시 복구 모델에서 노드는 크래시 발생 시에도 보존되는 안정적인 스토리지(비휘발성 디스크 스토리지)를 가지고 있는 것으로 가정하고, 인메모리 상태는 손실된 것으로 가정한다.

비잔틴(임의) 결함

어떠한 노드는 다른 노드를 속이거나 속이려는 시도를 포함하여 무엇이든 할 수 있다.

분산 알고리즘이 크래시-복구 장애에 대처하는 방법

알고리즘의 정확성

알고리즘이 정확하다는 것은 알고리즘의 속성을 통해 설명 가능하다. 예를 들어, 정렬 알고리즘의 출력은 출력 목록의 두 요소 중 왼쪽에 있는 요소가 오른쪽에 있는 요소보다 작다는 속성을 갖는다. 이는 단순히 목록이 정렬된다는 것이 무엇을 의미하는지 정의하는 형식적인 방법이다.

마찬가지로 분산 알고리즘에서 원하는 속성을 적어 올바른 알고리즘의 의미를 정의할 수 있다. 예를 들어 잠금에 대한 펜싱 토큰을 생성하는 경우, 알고리즘에 다음과 같은 속성이 필요하다:

• 유일성 (Uniqueness) 펜싱 토큰을 요구하는 어떠한 요청도 같은 값을 반환하지 않는다.

• 모노톤 시퀀스(Monotonic sequence) x라는 요청이 토큰 tx를 받으면, 요청 y는 토큰 ty를 받는다. x는 y보다 더 빠르므로, tx < ty 다.

• 가용성 (Availability) 노드가 펜싱 토큰을 요청하고 충돌하지 않는 다면, 결국 응답을 받는다.

안정성과 활력

시스템의 문제 상황을 명확히 하려면 두 가지 다른 종류의 속성인 안전성(safety)과 활력(livenees)속성을 구분할 필요가 있다. 위 예시에서, 고유성과 모노톤 시퀀스는 안전 속성이지만 가용성은 활력 속성이다.

이 두 가지 속성의 차이점은 무엇일까? 한 가지 차이점은 활력 속성의 정의는 “결국(eventually)”이라는 단어가 포함된다는 점이다.

안전 속성과 활력 속성을 구분하는 것의 장점은 어려운 시스템 모델을 처리하는 데 도움이 된다는 것이다. 분산 알고리즘의 경우, 시스템 모델의 모든 가능한 상황에서 안전 속성이 항상 유지되도록 요구하는 것이 일반적이다. 즉, 모든 노드가 충돌하거나 전체 네트워크에 장애가 발생하더라도 알고리즘은 잘못된 결과를 반환하지 않아야 한다(즉, 안전성이 만족되는 상태를 유지해야 한다).

예를 들어, 대다수의 노드가 충돌하지 않은 경우에만 요청이 응답을 수신해야 하고, 네트워크가 결국 정전으로부터 복구되는 경우에만 응답을 수신해야 한다고 말할 수 있다. 부분 동기식 모델의 정의에 따르면 결국 시스템이 동기식 상태로 돌아가는 것, 즉 네트워크 중단 기간이 한정된 기간 동안만 지속되고 복구되는 것이 필요하다.

시스템 모델을 실제 세계에 적용하기

안전성과 생명력 속성과 시스템 모델은 분산 알고리즘의 정확성을 추론하는 데 매우 유용하다. 이론적이고 추상적인 시스템 모델이 쓸모없다는 뜻은 아니며, 오히려 그 반대다. 실제 시스템의 복잡성을 추론할 수 있는 결함의 집합으로 정의하여 문제를 이해하고 해결할 수 있도록 하는 데 매우 유용하다. 알고리즘의 속성이 특정 시스템 모델에서 항상 유지된다는 것을 보여줌으로써 알고리즘이 정확하다는 것을 증명할 수 있다. 알고리즘이 정확하다는 것을 증명한다는 것은 실제 시스템에서 알고리즘을 구현해도 항상 올바르게 작동한다는 의미는 아니다. 하지만 이론적 분석은 실제 시스템에서 오랫동안 숨겨져 있다가 비정상적인 상황으로 인해 가정이 무너졌을 때만 드러나는 알고리즘의 문제를 발견할 수 있기 때문에 첫 단계에서 수행해야 한다. 이론적 분석과 경험적 테스트는 똑같이 중요하다.