9. Consistency and Consensus

분산형 시스템에서는 많은 것들이 잘못될 수 있으며, 이에 대처하는 법을 익혀야 한다. 이 장에서는 실패에 대처하는 분산형 시스템을 만드는 알고리즘과 프로토콜을 알아보자. 실패에 대처하는 시스템을 만드는 최고의 방법은 유용한 보장을 하는 범용 추상화를 찾은 뒤 이를 구현하고 애플리케이션들이 이에 의존하게 하는 것이다. 예를 들어, 분산형 시스템에서 가장 중요한 추상화 중 하나는 컨센서스로, 모든 노드가 무언가에 동의하도록 하는 것이다. 컨센서스를 구현하고 나면 애플리케이션은 여러 목적으로 쓸 수 있다. 먼저 분산형 시스템에서 제공될 수 있는 보장과 추상화의 범위를 알아보자. 그 이전에 어떤 것이 가능하고 불가능한지를 판단해야 한다. 이는 다양한 주제로 이루어져 있다.

Consistency Guarantees

데이터베이스간 노드들에는 비일관성이 발생할 수 있다. 많은 복제 데이터베이스는 최소한 궁극적 일관성, 즉 데이터베이스에 쓰기를 멈추고 얼마간을 기다리면 궁극적으로 모든 읽기 요청이 같은 값을 반환함을 보장한다. 하지만 이는 매우 약한 보장으로, 복제들이 언제 수렴할지는 알려주지 않는다. 궁극적 일관성은 애플리케이션 제작자들에게 있어 매우 힘든데 일반적인 단일 스레드 프로그램의 변수의 동작과 매우 다르기 때문이다. 약한 보장만 제공하는 데이터베이스와 작업을 하면 그 한계를 알고 있어야 하고 실수로 너무 지나친 가정을 하지 말아야 한다. 이 장에서는 데이터 시스템이 제공할 수 있는 더 강한 일관성 모델을 알아본다. 분산형 일관성 모델과 계층화된 트랜잭션 분리 수준에는 유사성이 있지만, 이들은 서로 다른 것이다. 먼저 선형화 가능성, 이벤트 순서화, 분산된 트랜잭션의 원자적 수행 등을 알아보자.

Linearizability

데이터베이스가 단일 복제만 존재하는 것처럼 동작한다면? 이를 선형화 가능성이라 한다. 선형화 가능한 시스템에서는 클라이언트가 쓰기를 끝마치면 데이터베이스로부터 읽는 모든 클라이언트가 쓰여진 값을 볼 수 있어야 한다. 이는 최근성 보장이라고도 볼 수 있다. 쿼리가 오래 된 결과를 반환하면 선형화 가능성을 깨는 것이다.

What Makes a System Linearizable?

선형화 가능성의 아이디어는 간단하다: 시스템에서 데이터의 복제가 단 하나만 있는 것처럼 보이게 하는 것이다. 분산형 시스템에서 레지스터를 동시에 읽고 쓰는 경우를 보자. 이 때 클라이언트의 입장에서는 데이터베이스 내에서 어떤 일이 일어나고 있는지 알 수 없다. 레지스터에는 읽기, 쓰기 두 가지 연산이 존재한다. 읽기에 대한 경우 수는 어떻게 될까? 읽기와 쓰기가 동시에 일어나는 경우 문제가 된다. 선형화 가능한 시스템에서는 레지스터의 값이 원자적으로 뒤집히는 시점이 존재한다. 이는 쓰기 연산이 끝나기 전일 수도 있다. 이를 위해서 비교 후 대입 (CAS) 연산이 추가로 필요하다. 선형화 가능성의 필요조건은 연산들을 묶는 선들은 항상 전방으로만 이동하고 후방으로는 이동하지 않는다는 것이다. 모든 요청과 반응의 타이밍을 기록해 시스템의 동작이 선형화 가능하고 올바른 순서화될 수 있는지 시험해볼 수 있다.

Relying on Linearizability

어떤 상황에서 선형화 가능성이 유용할까?

Locking and leader election

단일 리더 복제를 사용하는 시스템은 한 리더만 존재함을 보장해야 한다. 이 경우 락은 선형화 가능해야 한다. 분산 락은 어떤 분산형 시스템에서는 훨씬 더 작은 수준으로 쓰이기도 한다.

Constraints and uniqueness guarantees

유일성 조건은 데이터베이스에서 흔하다. 이 경우에도 선형화 가능성이 필요하다. 은행 계좌가 음수가 되지 않는다던가 하는 조건에도 필요하다. 실제 애플리케이션에는 이런 조건을 느슨하게 다뤄야 할 수도 있다. 이런 경우에는 선형화 가능성이 필요 없다.

Cross-channel timing dependencies

선형화 가능성 위반은 시스템에 추가 통신 채널이 있어야 발생한다. 컴퓨터 시스템에서도 비슷한 상황이 발생할 수 있다. 예를 들면 이미지 리사이저는 리사이즈를 위해서는 명시적으로 웹 서버로부터 메시지 큐로 명령되어야 한다. 이 때 파일 시스템이 선형화 가능하지 않다면 경합 조건이 발생할 수 있다. 이 경우 문제는 파일 저장소와 메시지 큐, 웹 서버와 리사이저 간 두 개의 다른 통신 채널이 있어서 생긴다. 선형화 가능성은 경합 조건을 피하기 위한 유일한 방법은 아니지만 가장 이해하기 쉽다.

Implementing Linearizable Systems

선형화 가능성이 유용한 몇 가지 예들을 알아보았다. 가장 간단한 구현법은 데이터의 단일 복제만 쓰는 것이지만 이는 실패에 대처 가능하지 않다. 단일 리더 복제는 아마도 선형화 가능하다. 컨센서스 알고리즘은 선형화 가능하다. 다수 리더 복제는 선형화 가능하지 않다. 리더 없는 복제는 아마도 선형화 가능하지 않다.

Linearizability and quorums

강한 정족수 읽기/쓰기도 경합 조건이 발생할 수 있다. 이는 선형화 가능하지 않다. 정족수 조건이 만족되더라도 그렇다. 하지만 성능을 댓가로 읽는 쪽에서 동기적으로 읽기 수리를 수행하면 선형화 가능하게 할 수 있다. 선형화 가능한 읽기/쓰기 연산은 이 방식으로밖에 구현할 수 없다. 즉, 리더 없는 Dynamo식 복제는 선형화 가능성을 보장하지 않는다고 가정하는 것이 안전하다.

The Cost of Linearizability

선형화 가능성의 장단점을 더 알아보자. 앞에서 여러 복제 방법을 알아보았다. 두 데이터 센터간 네트워크 간섭이 발생하면 어떻게 될까? 복수 리더 데이터베이스에서는 각 데이터 센터가 평상시처럼 동작할 수 있다. 다만 단일 리더 복제는 그렇지 않다. 이 경우에는 리더가 아닌 데이터 센터에 연결된 클라이언트는 쓰기를 할 수 없고 선형화 가능한 읽기도 할 수 없다. 클라이언트가 리더 데이터 센터에 연결할 수 있다면 문제가 없다.

The CAP theorem

이 문제는 모든 선형화 가능한 데이터베이스에서 존재한다. 애플리케이션이 선형화 가능성을 요구하면 어떤 복제가 네트워크 문제로 인해 다른 복제와 연결이 끊어지면 어떤 복제들은 연결이 끊어진 동안 요청을 수행할 수 없다. 애플리케이션이 선형화 가능성을 요구하지 않는다면 각 복제가 연결이 끊어진 경우에도 요청을 독립적으로 수행할 수 있게 되지만 동작이 선형화 가능하지 않아진다. 즉, 이 경우가 더 네트워크 문제에 대처 가능하다고 할 수 있다. 이는 CAP 정리라 불린다. 이는 엄밀하게는 매우 좁은 의미로 정의된다. 요즈음은 잘 쓰이지 않는 개념이다.

Linearizability and network delays

선형화 가능성은 유용한 보장이지만 실제로 가능한 시스템은 거의 없다. 이는 각 CPU 코어가 고유 메모리 캐시나 버퍼 저장소를 갖고 있기 때문이다. 선형화 가능성을 없앤 이유는 실패에 대처하기 위해서라기보단 성능 문제 때문이다. 많은 분산형 데이터베이스에서도 같은 이유로 같은 접근을 한다. 선형화 가능한 저장소의 더 효율적인 구현은 없나? 없다.

Ordering Guarantees

선형화 가능성의 정의는 동작들이 잘 정의된 순서로 실행됨을 의미한다. 순서화는 이 책에서 자주 등장하는 중요한 개념이다. 순서화, 선형화 가능성, 컨센선스에는 밀접한 관계가 있다.

Ordering and Causality

순서화가 중요한 이유는 인과성을 보존하는 데 도움이 되기 때문이다. 이것이 필요한 예는 인과적 의존성, 이전에 발생한 관계, 인과성과의 일관성 등 여럿이 있다. 인과성은 이벤트의 순서를 도입한다. 시스템이 인과성에 의해 유도된 순서를 따르면 이는 인과적으로 일관적이라 한다.

The causal order is not a total order

완전 순서는 모든 두 원소가 비교될 수 있다는 것이다. 하지만 수학적 집합은 완전 순서가 아니라 부분 순서인 경우가 더 많다. 선형화 가능성은 완전 순서이다. 인과성은 부분 순서이다. 즉 선형화 가능한 데이터 저장소에는 동시적 연산은 없다. 동시성은 타임라인이 갈라졌다가 병합될 수 있음을 뜻하며 이 때 다른 가지의 연산들은 비교 가능하지 않다. Git과 같은 버전 관리 시스템은 인과적 의존성의 그래프와 비슷하다.

Linearizability is stronger than causal consistency

그래서 인과적 순서와 선형화 가능성의 관계는 무엇인가? 선형화 가능성은 인과성을 보장한다. 또한 이 사이 어딘가도 존재한다. 대부분 선형화 가능성을 요구하는 것처럼 보이는 시스템의 경우 인과적 일관성으로 충분하며 이는 더 효율적으로 구현될 수 있다. 이는 많이 구현되진 않았다.

Capturing causal dependencies

핵심 아이디어를 알아보자. 인과성을 보장하기 위해서는 어떤 연산이 다른 연산 이전에 일어났는지를 알아야 한다. 인과적 의존성을 판정하기 위해서는 노드의 지식을 시스템 내에서 묘사할 수 있어야 한다. 이를 위한 기법은 동시적 쓰기를 감지하는 기법과 비슷하다. 인과적 순서화를 판정하기 위해서는 애플리케이션에서 어떤 버전의 데이터가 읽어지는지를 알 수 있어야 한다.

Sequence Number Ordering

인과성은 중요한 이론적 개념이지만 모든 인과적 의존성을 추적하는 것은 비현실적이다. 이벤트를 순서화하기 위해 순차 번호를 도입할 수 있다. 이는 컴팩트해야 하고 전체 순서를 제공해야 한다. 이 전체 순서는 인과성과 일관적인 전체 순서이다. 단일 리더 복제의 데이터베이스에서는 복제 로그가 인과성과 일관적인 쓰기 연산의 전체 순서를 정의한다.

Noncausal sequence number generators

단일 리더가 없다면 어떻게 할까? 각 노드가 독립적인 순차 번호를 쓸 수 있다. 각 연산에 타임스탬프를 붙일 수도 있다. 순차 번호의 블록을 사전에 할당할 수 있다. 이는 모든 연산을 카운터를 증가시키는 단일 리더에 넣는 것보다 더 확장성이 있다. 이 때 인과성 문제가 발생할 수 있다.

Lamport timestamps

인과성과 일관적인 순차 번호를 생성하는 간단한 방법으로 램포트 타임스탬프가 있다. 각 노드는 고유 식별자가 있고 각 노드는 수행한 연산의 숫자를 센다. 이는 물리적 시계와 관계가 없지만 전체 순서를 제공한다. 각 노드와 각 클라이언트는 그것이 본 최대 카운터 값을 추적해서 이를 매 요청에 포함시킬 수 있다. 더 큰 값을 보면 최대값은 업데이트된다. 이는 인과적 일관성을 보장한다. 이는 항상 전체 순서를 강제한다는 점에서 버전 벡터와는 다르다.

Timestamp ordering is not sufficient

램포트 타임스탬프로는 충분하지 않다. 이를 써도 분산형 시스템에서는 여러 문제가 발생할 수 있다. 전체 순서로는 불충분한가? 노드가 사용자로부터 사용자명을 만들라는 요청을 방금 받고 그 요청이 성공해야 하는지의 여부를 즉시 결정해야 할 때는 불충분하다. 이러면 모든 노드의 타임스탬프를 조사해야 하기 때문이다. 문제는 연산의 완전 순서는 연산을 전부 모은 이후에나 판단 가능해진다는 것이다. 사용자 명같은 고유성 조건을 구현하기 위해서는 연산의 완전 순서로는 충분치 않으며, 그 순서가 언제 완료되는지도 알고 있어야 한다. 이는 전체 순서 방송으로 이루어진다.

Total Order Broadcast

분산형 시스템에서는 모든 노드가 동의하는 연산의 완전 순서를 만들기는 까다롭다. 단일 리더 복제가 판정하는 연산의 완전 순서를 확장할 수는 없나? 이를 위해서는 두 가지 조건이 필요하다: 신뢰성 있는 전송, 완전 순서 전송. 완전 순서 방송은 이 둘 모두를 만족시켜야 한다.

Using total order broadcast

컨센서스 서비스는 전체 순서 방송을 구현한다. 이는 데이터 복제에 필요한 것이다. 또한 이는 직렬화 가능한 트랜잭션 구현에도 쓸 수 있다. 전체 순서 방송의 중요한 관점은 메시지가 전송된 시점으로 순서가 고정된다는 것이다. 이는 로그를 만드는 방식으로 볼 수도 있다. 이는 펜싱 토큰을 제공하는 락 서비스를 구현하는 데도 유용하다.

Implementing linearizable storage using total order broadcast

선형화 가능성과 전체 순서 방송은 같지는 않다. 전체 순서 방송은 비동기적이다. 하지만 이것이 있다면 선형화 가능한 저장소를 그 위에 만들 수 있다. 즉, 사용자명이 사용자 계정을 유일하게 식별하도록 할 수 있다. 선형화 가능한 비교-대입 연산을 구현할 수 있다. 로그 엔트리는 모든 노드에 같은 순서로 전송되므로 여러 동시적 쓰기가 있더라도 모든 노드가 어떤 것이 먼저 왔는지 합의할 수 있다. 이는 선형화 가능한 쓰기를 보장하지만 선형화 가능한 읽기는 보장하지 않는다. 이를 위해서는 로그에 메시지를 덧붙이거나, 마지막 로그의 위치를 가져오거나, 읽기를 쓰기에 동기적으로 만드는 법이 있다.

Implementing total order broadcast using linearizable storage

선형화 가능한 저장소가 있을 때 전체 순서 방송은 어떻게 구현하나? 선형화 가능한 레지스터에 원자적인 증가-획득 연산을 카운터와 쓰면 된다. 전체 순서 방송을 통해 전송하고 싶은 모든 메시지에 대해 선형화 가능한 정수를 증가시키고 획득한 뒤 그 값을 메시지에 붙이면 된다. 램포트 타임스탬프와는 달리, 이 숫자들은 중간에 빠진 숫자가 있어선 안 된다. 문제가 발생하지만 않는다면 이는 구현하기 쉽다. 선형화 가능한 비교-대입 레지스터와 전체 순서 방송은 컨센서스에 대해 동치이다. 이제 컨센서스 문제를 알아보자.

Distributed Transactions and Consensus

컨센서스는 여러 노드가 무언가에 합의하는 것을 뜻한다. 이는 매우 중요하지만 제대로 이해하기는 힘들다. 이것이 중요한 예는 리더 선택, 원자적 수행 등이 있다. 먼저 원자적 수행 문제를 알아보자. 먼저 두 단계 수행 알고리즘을 알아보자.

Atomic Commit and Two-Phase Commit (2PC)

트랜잭션 원자성의 목적은 여러 쓰기 도중에 무언가 잘못되었을 때에 대한 간단한 시맨틱을 제공하기 위한 것이다. 원자성은 데이터베이스에서 트랜잭션이 실패했을 때 절반만 끝난 결과와 절반만 업데이트된 상태가 되는 것을 막는다.

From single-node to distributed atomic commit

단일 데이터베이스 노드에서 실행되는 트랜잭션들에 대해서는 원자성은 저장소 엔진을 통해 구현된다. 단일 노드에서 트랜잭션 수행은 데이터가 디스크에 쓰이는 순서에 의존한다. 하지만 트랜잭션에 복수 노드가 구현된다면? 이 경우에는 수행 요청을 모든 노드에 보내고 각 노드에서 트랜잭션을 독립적으로 수행하는 것만으로는 충분치 않다. 어떤 노드가 트랜잭션을 수행하고 다른 노드가 중단하면 노드는 서로 비일관적이 된다. 트랜잭션 수행은 변경 불가능해야 한다.

Introduction to two-phase commit

두 단계 수행은 복수 노드간 원자적 트랜잭션 수행을 하기 위한 알고리즘이다. 수행/중단 과정은 두 단계로 나뉜다. 이는 조정자라는 컴포넌트를 갖는다. 두 단계 트랜잭션은 복수 데이터베이스 노드에 데이터를 읽고 쓰는 것으로 시작된다. 모든 참가자가 동의하면 수행되고 한 참가자라도 반대하면 수행은 멈춘다.

A system of promises

두 단계 수행은 어째서 원자성을 제공할까? 우선 조정자로부터 트랜잭션 ID를 받는다. 단일 노드 트랜잭션에는 전역적으로 고유한 트랜잭션 ID를 붙인다. 애플리케이션이 수행할 준비가 되면 조정자는 준비 요청을 모든 참가자에 보낸다. 참가자가 준비 요청을 받으면 모든 상황에서 트랜잭션을 수행할 수 있는지를 보장한다. 조정자가 모든 준비 요청들로부터 응답을 받으면 트랜잭션을 수행할지 중단할지 결정한다. 조정자의 결정이 디스크에 쓰여지면 수행 요청은 모든 참가자에 전송된다. 즉, 프로토콜은 2개의 핵심 번복 불능 지점을 포함한다. 트랜잭션이 수행되면 되돌릴 수 없다.

Coordinator failure

참가자가 실패하면 트랜잭션은 중단된다. 하지만 조정자가 준비 요청에 대한 대답을 받은 뒤 크래시되면 불확실 상태가 된다. 그러므로 일방적인 수행은 안전하지 않다. 조정자로부터의 응답을 기다리지 않으면 참가자는 수행할지 중단할지 알 수 없다. 두 단계 수행이 완료되는 유일한 방법은 조정자가 복구되는 것을 기다리는 것이다.

Three-phase commit

두 단계 수행은 조정자의 복구를 기다리느라 막힐 수 있으므로 블로킹 원자적 수행 프로토콜이라고도 불린다. 이에 대한 대안으로 세 단계 수행이 제안되었다. 일반적으로, 비블로킹 원자적 수행은 노드가 크래시되었는지를 신뢰성 있게 판정하는 메커니즘인 완전 실패 감지기를 필요로 한다.

Distributed Transactions in Practice

분산 트랜잭션은 특히 두 단계 수행과 구현되었을 때 복합적인 평판을 받고 있다. 분산 트랜잭션의 어떤 구현들은 큰 성능 패널티를 유도하기도 한다. 하지만 이를 바로 버리는 대신 더 알아보는 것이 좋다. 분산 트랜잭션에는 데이터베이스 내부 분산 트랜잭션, 불균질 분산 트랜잭션의 두 가지 유형이 있으며 이 둘이 복합되기도 한다.

Exactly-once message processing

불균질 분산 트랜잭션은 여러 시스템이 강력한 방식으로 통합될 수 있도록 한다. 메시지 전송이나 데이터베이스 트랜잭션이 실패하면 모두가 중단되고 메시지 브로커는 메시지를 안전하게 차후에 재전송할 수 있다. 분산형 트랜잭션은 트랜잭션에 영향 받은 모든 시스템이 같은 원자적 수행 프로토콜을 사용할 수 있어야만 가능하다. 정확히 한 번-메시지 처리는 나중에 알아보자.

XA transactions

X/Open XA는 불균질한 기술 스택간 두 단계 수행을 구현하기 위한 표준이다. 이는 네트워크 프로토콜은 아니며 트랜잭션 조정자와 인터페이스하는 C API이다. 이는 애플리케이션이 네트워크 드라이버나 클라이언트 라이브러리를 써서 참가자 데이터베이스나 메시지 서비스와 통신함을 가정한다. 트랜잭션 조정자는 XA API를 구현한다. 애플리케이션 프로세스가 크래시되거나 애플리케이션이 동작하는 기계가 크래시되면 조정자도 그를 따른다.

Holding locks while in doubt

트랜잭션이 불확실 상태가 되면 안 되나? 문제는 락에 있다. 데이터베이스는 트랜잭션이 수행되거나 중단될 때까지 락을 풀 수 없다. 락이 걸린 동안에는 다른 트랜잭션이 행을 수정할 수 없어져서 문제가 되는 것이다.

Recovering from coordinator failure

실제로는 고아 상태의 불확실 트랜잭션, 즉 조정자가 결과를 결정할 수 없는 트랜잭션이 발생할 수 있다. 데이터베이스 재부팅도 이 문제를 해결할 수 없다. 관리자의 유일한 방법은 트랜잭션을 수행할지 되돌릴지 직접 결정하는 것이다. 많은 XA 구현은 휴리스틱 겨정이라 불리는 긴급 탈출 해치를 갖고 있다.

Limitations of distributed transactions

XA 트랜잭션은 유용하지만 여러 한계점도 갖고 있다. 조정자가 복제되지 않는다면 전체 시스템의 단일 실패 지점이 될 수 있다. 또한 서버 사이드의 상태 없는 모델도 깨트린다. 서로 다른 시스템간 데드록도 감지할 수 없으며 SSI와도 작동하지 않는다. 참가자 중 하나만 실패해도 트랜잭션은 실패하므로 실패를 확대하는 부분도 있다. 그러면 대안은 없나?

Fault-Tolerant Consensus

컨센서스는 여러 노드가 무언가에 합의하는 것을 말한다. 엄밀히 말하면 하나 이상의 노드가 값을 제안하고 컨센서스 알고리즘은 그 값들 중 하나를 결정하는 것이다. 이는 균일한 동의, 통합성, 정확성, 종료성을 만족해야 한다. 균일한 동의와 통합성은 컨센서스의 핵심 아이디어를 정의한다. 실패에 대한 대처를 신경쓰지 않으면 처음 3개의 조건을 만족하는 것은 쉽다. 종료성은 고장에 대한 대처의 아이디어를 엄밀화한다. 컨센서스의 시스템 모델은 노드가 크래시되었을 때 사라진 뒤 돌아오지 않음을 가저한다. 모든 노드가 크래시되면 알고리즘이 동작할 수 없으므로 크래시되는 노드 수에는 제한이 존재한다. 즉 종료성은 노드의 절반 미만이 고장이라는 가정에 근거한다. 또한 비잔틴 실패가 없음을, 즉 노드가 프로토콜을 따르지 않으면 프로토콜의 안전성을 깨트림을 가저한다.

Consensus algorithms and total order broadcast

가장 뛰어나다고 알려진 실패에 대처하는 컨센서스 알고리즘은 뷰스탬프 복제, Paxos, Raft, Zab 등이다. 이들 대부분은 여기 거론된 엄밀한 모델을 직접 사용하진 않는다. 전체 순서 방송은 여러 라운드의 컨센서스를 수행하는 것으로 볼 수 있다. 즉, 전체 순서 방송은 여러 라운드의 컨센서스와 동치이다.

Single-leader replication and consensus

단일 리더 복제는 전체 순서 방송이 아닌가? 이는 리더가 어떻게 선택되는지에 달려 있다. 어떤 데이터베이스는 원자적 리더 선거와 대체를 수행해 이전 리더가 실패하면 다른 팔로워를 새 리더로 승격시킨다. 리더를 결정하는 데는 컨센서스가 필요하다. 하지만 그러면 최초의 리더는 어떻게 정하는가?

Epoch numbering and quorums

지금까지 다룬 컨센서스 프로토콜에서는 프로토콜이 에포크 번호를 정의하고 그 에포크 내에서 리더가 유일함을 가정한다. 현재 리더가 죽으면 노드간의 선거가 열려 새 리더를 뽑는다. 리더는 다른 리더가 존재해서 충돌되는 결정을 내리지 않는지를 먼저 검사해야 한다. 그래서 노드의 정족수로부터 표를 모아야 한다. 그래서 두 단계의 투표가 존재한다: 리더의 선택, 리더의 제안에 대한 선택. 이는 두 단계 수행과 비슷하다.

Limitations of consensus

컨센서스 알고리즘은 분산형 시스템을 크게 발전시켰다. 하지만 그에는 대가가 따른다. 노드가 제안에 대해 하는 투표는 동기적 복제와 같다. 또한 동작하려면 강한 다수를 필요로 한다. 대다수의 컨센서스 알고리즘은 투표에 참가하는 고정된 노드들을 가정하므로 클러스터에서 노드를 단순히 삭제/삽입할 수 없다. 컨센서스 시스템은 실패한 노드를 감지하기 위해 타임아웃에 의존한다. 때론 컨센서스 알고리즘은 네트워크 문제에 민감하다.

Membership and Coordination Services

ZooKeeper 서비스 등의 API는 데이터베이스의 그것과 비슷하다. 그러면 컨센서스 알고리즘을 구현해야 할 필요는 무엇인가? 이는 메모리 전체에 들어갈 수 있는 작은 데이터를 담기 위해 만들어졌기 때문이다. 이는 Google의 Chubby 락 서비스로부터 모델링되었으나 다음의 흥미로운 특성도 갖는다: 선형화 가능한 원자적 연산, 연산의 전체 순서, 실패 감지, 변화 감지.

Allocating work to nodes

ZooKeper/Chubby 모델이 잘 작동하는 사례 중 하나는 프로세스나 서비스의 인스턴스가 여러 개이고 이들 중 하나가 리더로 선택되어야 할 때이다. 분할된 자원을 가졌고 어떤 분할이 어떤 노드에 할당되어야 할지 결정할 때에도 필요하다. 이런 작업들은 원자적 연산의 신중한 사용을 통해 얻을 수 있다. ZooKeeper는 노드의 투표를 할 때 일종의 아웃소싱을 거친다. ZooKeeper에 의해 관리되는 데이터는 대개 느리게 변화한다.

Service discovery

ZooKeeper, etcd, Consul은 특정 서비스에 도달하기 위해 그에 연결하기 위한 IP 주소를 찾아야 하므로 서비스 발견으로도 불린다. 하지만 서비스 발견이 컨센서스를 필요로 하는지는 명확하지 않다. 서비스 발견은 컨센서스를 필요로 하지 않지만 리더 선출이 필요로 한다.

Membership services

ZooKeeper류는 멤버십 서비스의 일부로 볼 수 있다. 이는 어떤 노드가 살아 있고 클러스터의 어떤 멤버가 활성화되어 있는지를 결정한다. 컨센서스가 노드의 생존을 잘못 감지할 수도 있지만 그래도 유용하다.

Summary

이 장에서는 일관성과 컨센서스에 관한 주제들을 여러 다른 관점에서 살펴보았다. 인기 있는 일관성 모델인 선형화 가능성을 알아보았으며, 이의 목적은 복제 데이터를 단일 복제만 있는 것처럼 보이게 하면서 그에 작용하는 모든 연산을 원자적으로 만드는 것이다. 선형화 가능성은 이해하기 쉽기 때문에 매력적이지만 데이터베이스가 단일 스레드 프로그램 내 변수처럼 동작하도록 한다. 그래서 느려진다는 단점, 특히 긴 네트워크 딜레이를 가진 환경에서 그러한 단점이 있다.

시스템 내 이벤트에 순서를 주는 인과성(어떤 것 이전에 어떤 것이 원인과 결과의 관계로 발생한 것)에 대해서도 알아보았다. 모든 연산을 단일 전체 순서화된 타임라인에 넣는 선형화 가능성과 반대로, 인과성은 더 약한 일관성 모델을 제공한다. 어떤 것들은 동시적일 수 있으므로 버전 히스토리는 가지치기와 병합을 하는 타임라인과도 같다. 인과적 일관성은 선형화 가능성의 조정 오버헤드가 없고 네트워크 문제에 훨씬 덜 민감하다.

하지만, 인과적 순서를 포착하더라도 (예를 들면 램포트 타임스탬프를 쓴다던가) 어떤 것들은 이 방식으로는 구현될 수 없다. “타임스탬프 순서화는 충분치 않다” 에서 고유 사용자명이 유일함을 보장하고 같은 사용자명의 동시적 등록을 거절하는 데는 충분치 않음을 알아보았다. 한 노드가 등록을 수용하려면, 다른 노드가 동시에 같은 이름을 등록하는 과정에 있지 ㅏㅇㄶ음을 알아야 한다. 이 문제는 컨센서스를 도입한다.

컨센서스를 얻는 것은 모든 노드가 무엇이 결정되었는지에 합의하고 그 결정이 되돌릴 수 없는 방식으로 이루어지는 식으로 결정을 하는 것이다. 약간의 연구를 하면 많은 범위의 문제들이 컨센서스로 환원 가능하며, 서로 동치이다 (즉, 하나에 대해 해답이 있으면 이를 다른 하나에 대한 해답으로 쉽게 변환 가능하다). 이러한 동치인 문제에는 다음이 있다:

  • 선형화 가능한 비교-대입 레지스터. 레지스터는 자동적으로 값을 대입할지를 결정해야 한다. 이는 그 현재 값이 연산에 주어진 매개변수와 같은지에 기반한다.
  • 원자적 트랜잭션 수행. 데이터베이스는 분산 트랜잭션을 수행할지 중단할지 결정해야 한다.
  • 전체 순서 방송. 메시징 시스템은 메시지를 전송할 순서를 결정해야 한다.
  • 락과 리스. 여러 클라이언트가 락이나 리스를 얻기 위해 경합한다면 락은 무엇이 그것을 성공적으로 얻을지 결정해야 한다.
  • 멤버십/조정 서비스. 실패 감시자 (타임아웃) 등이 주어졌을 때 시스템은 어떤 노드가 생존했는지 결정해야 하며 세션이 타임아웃 되었다면 죽은 노드로 간주해야 한다.
  • 고유 조건. 여러 트랜잭션이 동시에 같은 키에 대해 충돌하는 기록을 만들려고 한다면 조건은 무엇을 허가하고 무엇을 조건 위반으로 실패시킬지 결정해야 한다.

이 모든 것은 단일 노드만 있거나 결정을 내리는 능력을 단일 노드에만 지우게 된다면 매우 간단하다. 이것이 단일 리더 데이터베이스에서 일어나는 것이다. 결정을 내리는 모든 능력은 리더에 있으며, 그러므로 이러한 데이터베이스는 선형화 가능한 연산들, 고유성 조건, 전체 순서화된 복제 로그 등을 제공할 수 있다.

하지만, 그 단일 리더가 고장나거나, 네트워크 간섭이 리더에 접근 불가능하게 한다면, 시스템은 더 이상 진행할 수 없다. 이 상황을 해결하기 위한 세 가지 방법이 있다.

  • 리더가 복구되기를 기다리고 그 시스템이 그 동안 블록되는 것을 받아들인다. 많은 XA/JTA 트랜잭션 조정자는 이 방법을 선택한다. 이 접근법은 컨센서스를 완전히 해결하지는 못한다. 종료성 특성을 만족시키지 않기 때문이다. 리더가 복구되지 않으면 시스템은 영원히 블록된다.
  • 사용자가 새 리더 노드를 직접 선택하게 하고 시스템이 그것을 사용하도록 재설정한다. 많은 관계형 데이터베이스는 이 접근법을 사용한다. 이는 신의 행위라는 컨센서스와 비슷하다. 컴퓨터 시스템 밖의 사람 제어자가 결정을 내린다. 실패에서의 복구 속도는 사람이 반응할 수 있는 속도에 제한되어 있으며 이는 대개 컴퓨터보다 느리다.
  • 새 리더를 자동으로 선택하는 알고리즘을 사용한다. 이 접근법은 컨센서스 아고리즘을 필요로 하며 불리한 네트워크 조건을 올바르게 다룰 수 있는 검증된 알고리즘을 쓰는 것이 추천된다.

단일 리더 데이터베이스는 쓰기마다 컨센서스 알고리즘을 실행할 필요 없이 선형화 가능성을 제공할 수 있지만, 이는 리더성을 유지하고 리더를 변경하기 위해 여전히 컨센서스를 필요로 한다. 그러므로, 어떤 점에선, 리더를 가지는 것은 그 자체만으로도 컨센서스를 필요로 한다. 단지 다른 지점에서 덜 빈번하게 필요로 할 뿐이다. 좋은 소식은 컨센서스에 대해 실패에 대처하는 알고리즘과 시스템이 존재한다는 것이며 이 장에서 그것들을 알아보았다.

ZooKeeper와 같은 도구들은 아웃소싱된 컨센서스, 실패 감지, 멤버십 서비스를 애플리케이션이 사용할 수 있게 하는 중요한 역할을 한다. 사용하기는 쉽지 않지만 이전 장에서 다루었던 모든 문제를 해결하기 위한 알고리즘을 직접 개발하는 것보다는 훨씬 낫다. 컨센서스로 환원되는 것들 중 하나를 하고 싶으면서 그것이 실패에 대처 가능하도록 하고 싶다면 ZooKeeper같은 것을 쓰는 것이 추천된다.

그럼에도 불구하고, 모든 시스템이 컨센서스를 필요로 하는 것은 아니다. 예를 들어, 리더가 없거나 복수 리더 복제 시스템은 전역 컨센서스를 대개 쓰지 않는다. 이런 시스템에서 발생하는 충돌은 다른 리더간 컨센서스를 갖지 않음으로써 생기는 결과이지만 아마도 괜찮을 수 있다. 아마도 선형화 가능성 없이 견디고 버전 역사를 가지치기와 병합하기하는 데이터와 작업하는 것이 나을 수도 있다.

이 장에서는 분산형 시스템 이론의 여러 연구 역사를 참조하였다. 이론적 논문과 증명이 항상 이해하기 쉬운 것은 아니며 어떨 때는 비현실적인 가정을 하기도 하지만 이 분야에서 실제적 작업을 알리기에는 매우 값지다. 이들은 무엇이 가능하고 무엇이 불가능한지 근거지을 수 있게 하며 분산형 시스템이 대개 잘못 동작하게 되는 직관에 반하는 방법들을 찾을 수 있게 한다. 시간이 있다면 이 참고 문헌들은 참고할 가치가 있다.

이로서 파트 2가 끝났다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중