분산 시스템의 결함과 한계

분산 시스템의 특징

• 분산 시스템에는 공유 메모리가 없고 지연 변동이 큰 신뢰할 수 없는 네트워크를 통해 메시지를 보낼 수 있을 뿐이며 부분 장애, 신뢰성 없는 시계, 프로세스 중단이 발생할 수 있음

• 네트워크에 있는 노드는 어떤 것도 확실히 알지 못함. 따라서 타임아웃을 사용해 상대 노드의 상태값을 추측함

다수결의 원칙

• 하나의 노드가 메시지는 수신하지만 송신 메시지는 유실된다면, 다른 기능이 완벽하게 작동한다할지라도 다른 노드들에 의해 죽었다고 선언됨

• 반대로 수신은 모두 받지만, 송신이 안된다면 마찬가지로 다른 노드들에 의해 죽었다고 선언됨

• GC에서 긴 STW가 일어나는 노드의 경우도 마찬가지. 노드가 STW로 멈춘 동안, 다른 노드들에 의해 죽었다고 선언됨. STW가 끝나고 다시 완벽하게 정상적으로 돌아온다 하더라도

• 이 말은 곧 노드가 자신의 상태에 대한 자신의 판단을 온전히 믿을 수 없다는 의미이며, 이를 해결하기 위해 분산 시스템에서는 분산 알고리즘, 정족수(Quorum) 에 의존

리더와 잠금

• 시스템이 오직 하나의 무언가를 필요로할 때가 있음

  • 스플릿 브레인을 피하기 위해 오직 한 노드만 데이터베이스 파티션의 리더가 되어야 함

  • 오직 하나의 트랜잭션이나 클라이언트만 어떤 자원이나 객체의 잠금을 획득해야 함

  • 오직 한 명의 사용자만 특정한 사용자명으로 등록할 수 있음

• 분산 시스템에서는 어떤 노드가 스스로가 "선택된 자"라고 믿을지라도 전체 노드의 정족수도 동의한다고 말할 수 없음

• 실제로 HBase에서 이런 문제들로 인해 버그가 생긴 적이 있음

펜싱 토큰

• 위와 같은 문제를 해결하기 위한 단순한 기법으로 펜싱(fencing)이 있음

• 잠금 서버가 잠금이나 임차권을 승인할때마다 펜싱 토큰도 반환한다고 가정하는 것

• 펜싱 토큰은 잠금이 승인될 때마다 증가하는 숫자이며, STW가 발생했던 클라이언트의 쓰기 요청은 펜싱 토큰이 최신값보다 낮기 때문에 거부됨

• 잠금 서비스로 주키퍼를 사용하면 트랜잭션 ID zxid나 노드 버전 cversion을 펜싱 토큰으로 사용할 수 있음

비잔틴 결함

• 펜싱 토큰은 부주의에 의한 오류를 차단할 수 있음. 여기서 부주의란 의도치 않게(자신은 임차권이 아직 유효하다고 판단했기 때문에) 발생한 오류를 의미

• 하지만 노드가 고의로 시스템의 보장을 무너뜨리려한다면, 단순히 더 큰 펜싱 토큰을 포함한 메시지를 보내기만하면 됨

• 분산 시스템에서는 노드들이 신뢰할 수는 없지만 항상 정직하다고 가정함

• 만일 노드들이 거짓말을 할 위험이 있다고 가정한다면, 많은 부분에서 구현하기가 상당히 까다로워 짐. 노드가 거짓말을 하는 현상을 비잔틴 결함이라고 하며, 신뢰할 수 없는 환경에서 합의에 도달하는 문제를 비잔틴 장군 문제라고 함

• 일부 노드가 오작동하거나 악의적으로 네트워크를 방해하더라도 시스템이 올바르게 동작한다면 이 시스템은 비잔틴 내결함성을 지닌다라고 표현함

• 비잔틴 내결함성은 특정 상황들에서 매우 유의미함

  • 항공우주 산업 환경에서는 특정 노드가 방사선에 오염되어 전혀 예측할 수 없는 방식으로 동작할 수 있음

  • 비트코인이나 다른 블록체인 같은 피어투피어 네트워크에서 특정 사용자는 다른 사용자들을 속이거나 사취를 시도하려고 할 수 있음

• 하지만 대부분의 서버 측 데이터 시스템에서 비잔틴 내결함성 솔루션을 배치하는 것은 비용이 커서 실용적이지 않음

• 웹 애플리케이션에서의 공격(SQL injection, cross site scripting) 등을 방어할 때도 보통은 비잔틴 내결함성 프로토콜을 쓰지는 않으며, 클라이언트의 행동이 허용된 것인지 결정하는 권한을 서버에 줌으로서 해결함

시스템 모델

• 분산 시스템에서 발생할 것으로 예상되는 결함의 종류를 시스템 모델로 정의해서 정형화함

• 타이밍 가정에 대해 다음 세 가지 모델이 주로 사용됨

  • 동기식 모델

    • 네트워크 지연, 프로세스 중단, 시계 오차에 모두 제한이 있다고 가정. 완전히 오차가 없다고 가정하는 것은 아니며, 어떤 고정된 상한치를 초과하지 않는다고 가정

  • 부분 동기식 모델

    • 대부분의 시간에는 동기식 시스템처럼 동작하지만 때때로 네트워크 지연, 프로세스 중단, 시계 드리프트의 한계치를 초과한다는 의미이며, 가장 현실적인 모델

  • 비동기식 모델

    • 타이밍에 대한 어떤 가정도 할 수 없다고 가정. 심지어는 시계가 없을 수도 있음

• 노드 장애에 대한 시스템 모델은 다음과 같음

  • 죽으면 중단하는(crash-stop) 결함

    • 노드에 장애가 발생하는 방식은 노드가 죽는 것뿐이라고 가정. 노드가 응답을 멈추면 그 노드는 영원히 배제함

  • 죽으면 복구하는(crash-recovery) 결함

    • 노드가 죽을 수 있지만 특정 시간이 흐른 이후에는 다시 응답할 것이라고 가정

  • 비잔틴 결함

    • 노드는 다른 노드를 속이는 것을 포함해 전적으로 무슨 일이든 할 수 있다고 가정

• 현실적으로 죽으면 복구하는 부분 동기식 모델이 가장 일반적으로 유용한 모델로서 사용되고 있음

• 그렇다면 분산 알고리즘은 이 모델에 어떻게 대응할까?

알고리즘의 정확성

• 알고리즘이 정확하다는 것은 어떻게 정의해야 할까?

• 이를테면 정렬 알고리즘의 결과는 결과 목록에서 두 개의 다른 요소를 선택하면 왼쪽보다 오른쪽이 크다는 속성이 있음

• 마찬가지로 분산 시스템에서의 알고리즘의 정확성을 판단하기 위해서는 분산 시트템의 속성을 써볼 수 있음

• 잠금에 사용한 펜싱 토큰의 예를 들어보자

  • 유일성 : 펜싱 토큰 요청이 같은 값을 반환하지 않음

  • 단조 일련번호: 토큰 x, y가 반환됐고 요청이 x, y 순대로 완료됐다면, x < y를 만족함

  • 가용성 : 펜싱 토큰을 요청하고 죽지 않은 노드는 결국엔 응답을 받음

• 알고리즘은 시스템 모델에서 발생하리라고 가정한 모든 상황에서 그 속성을 만족시키면 해당 시스템 모델에서 정확하다라고 표현할 수 있음

• 즉, 모든 노드가 죽거나, 모든 네트워크 지연이 갑자기 무한히 길어지는 등의 가정하지 않은 상황이 발생한다면, 알고리즘은 무의미함

안정성과 활동성

• 속성은 크게 두 가지로 분류될 수 있음

• 앞선 예제에서 유일성과 단조 일련번호는 안전성 속성, 가용성은 활동성 속성임

• 흔히 말해, "결국에는"이라는 단어를 포함한다면 활동성 속성임(최종적 일관성 또한 활동성 속성임)

• 안전성은 흔히 "나쁜 일은 일어나지 않는다"이고, 활동성은 "좋은 일은 결국 일어난다"로 표현됨

• 안전성 속성이 위반되면 그 속성이 깨진 특정 시점을 가리킬 수 있다(예를 들어 유일성 속성이 위반되면 중복된 펜싱 토큰을 반환한 특정 연산을 식별할 수 있다). 안전성 속성이 위반된 후에는 그 위반을 취소할 수 없다. 이미 손상된 상태다.

• 활동성 속성은 반대로 동작한다. 어떤 시점을 정하지 못할 수 있지만(예를 들어 노드가 요청을 보냈지만 아직 응답을 받지못했을 수도 있다) 항상 미래에 그 속성을 만족시킬 수 있다는 희망이 있다.

• 일반적으로 분산 알고리즘은 시스템 모델의 모든 상황에서 안전성 속성이 항상 만족되기를 요구하며, 활동성 속성에 대해서는 경고함