일관성과 합의

일관성 보장

동시에 데이터베이스 두 대를 본다면, 복제 방법에 상관 없이 서로 다른 데이터를 볼 가능성이 크다.

약한보장

복제 데이터 베이스는 대부분 최소한 최종적 일관성을 제공하나, 언제 수렴될지 모른다. 버그는 시스템 결함이 있거나 동시성이 높을 때만 명확하기 때문에 테스트로 발견하기 어렵다.

강한보장

데이터 시스템이 선택적으로 제공 올바르게 사용하기 쉬우나 시스템 성능이 나쁘거나 내결함성이 약할수도 있다.

선형성

공통적으로 사용되는 가장 강한 일관성 모델 중 하나 시스템에 복사본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 하는 것

원자적 일관성 (atomic consistency), 강한 일관성(strong consistency) 등으로 불림 최신성 보장 (recency guarantee) : 클라이언트가 쓰기를 성공하자마자 그 데이터를 읽는 모든 클라이언트는 방금 쓰여진 값을 볼 수 있어야 함.

시스템에 선형성을 부여하는 것

클라이언트는 자신의 요청이 언제 처리됐는지는 알지 못하고 요청, 응답 시간 사이에 처리됐다는 것만 앎

클라이언트 C의 쓰기 요청 전의 읽기 요청은 0, 쓰기 요청이 끝난 후의 읽이 요청은 1을 반환해야 하는 것은명백함

쓰기 요청 중 읽기 요청에서는 0 또는 1이 반환될 수 있음 읽기가 새로운 값을 반환하면 그 이후 모든 읽기는 새로운 값을 반환해야 함

잠금과 리더 선출

단일 리더 복제에서는 리더가 하나만 존재해야 함 잠금은 리더를 선출하는 방법

모든 노드가 시작할 때 잠금 획득을 시도하고, 성공한 노드가 리더가 됨 이 잠금은 선형적이어야 하고, 모든 노드는 어느 노드가 잠금을 소유하는지에 동의해야 한다. 분산 잠금과 리더 선출을 위해 아파치 주키퍼, etcd 같은 코디네이션 서비스가 사용되기도 함

선형성 시스템 구현하기

복제 방법에 따른 선형성 구현

단일 리더 복제 - 선형적이 될 가능성이 있다. 스플릿 브레인이나 복제본이 뒤쳐지는 문제가 있을 수 있음

합의 알고리즘 - 선형적 스플릿 브레인과 복제본이 뒤쳐지는 문제를 막을 수단이 있어 선형성 저장소를 안전하게 구현할 수 있음

다중 리더 복제(비선형적) 여러 노드에서 동시에 쓰기를 처리하고, 비동기로 다른 노드에 복제하므로 일반적으로 선형적이지 않음

리더 없는 복제(아마도 비선형적) 시계를 기반으로 한 최종 쓰기 승리의 경우 타임스탬프는 이벤트의 실제 순서와 일치한다고 보장할 수 없다.

선형성의 비용

네트워크가 끊기면 선형성과 가용성 사이에서 선택해야만 한다.

선형성

단일 리더 경우로 네트워크 중단 시 팔로워 데이터센터로 접속한 Client 는 사용에 문제가 있다. 데이터센터 DC로 직접 접속이 가능하면 정상 동작할 수 있다.

가용성

• 다중 리더 경우로 비선형적이지만 데이터센터 간 네트워크 중단에도 정상 동작은 가능하다.

• 네트워크 복구 시 복제 요청이 전달됨

선형성과 네트워크 지연

최신 다중코어 CPU의 RAM조차 선형적이지 않을 정도로 선형적인 시스템은 드물다. 이러한 트레이드 오프는 내결함성 대신 성능을 선택했기 떄문이다.

여러 분산 데이터 베이스도 마찬가지이다.

순서화 보장

순서화와 인과성

인과성

결과가 나타나기 전에 원인이 발생한다. 순서화가 인과성을 보존하는데 도움을 준다.

시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적(causally consistent) 라고 함

선형성은 인과적 일관성보다 강하다

선형성은 인과성을 내포하기에 선형적 시스템은 인과성도 올바르게 유지함 다만 성능, 가용성에 해가 될 수 있음 (네트워크 지연 등으로 인한)

절충을 통해 성능 손해 없이 인과적 일관성을 만족 시킬 수 있고, 연구 중

인과적 의존성 담기 - 비선형성 시스템

인과성을 유지하기 위해 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다.

데이터베이스는 애플리케이션이 어떤 데이터를 어떤 트랜잭션이 읽었는지 추적한다.

일련번호 순서화

모든 인과적 의존성을 추적하는건 실용성이 떨어지고, 오버헤드가 큼 따라서 일련번호, 타임스탬프로 이벤트 순서를 정하는 방법이 있음

크기가 작고, 고유해서 전체 순서를 알 수 있음

비인과적 일련번호 생성기

단일 리더가 없다면 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않는다. 그럴 경우 아래와 같은 다양한 방법을 사용한다.

노드 별 일련번호

각 노드 개별로 독립적인 일련번호 집합 생성 ex) node A = {2, 4, 6, 8..} , node B = {1, 3, 5, 7…}

but, 노드마다 초당 연산 수가 다를 수 있어 홀수 연산과 짝수 연산이 있을 때 어떤것이 인과적으로 먼저인지 정확히 알 수 없음

고해상도 타임스탬프

각 연산에 일 기준 시계의 타임스탬프를 붙임 ex) X = 40.00001, Y = 40.00003

but, 노드 간 타임스탬프 불일치

노드에 일련번호 블록 할당

일련번호들을 노드에 미리 할당 ex) node A = {1 ~ 1000}, node B = {1001 ~ 2000}

but, 블록 일련번호 간 일관성 불일치

위 세가지는 전부 잘 동작하며 카운터를 증가시키는 단일 리더에 모든 연산을 밀어 넣는것 보다 확장성이 좋다.

그러나 생성한 일련번호가 인과성에 일관적이지 않다.

램포트 타임스탬프

인과성에 일관적인 일련번호를 생성하는 간단한 방법 현재 분산 시스템 분야에서 가장 많이 인용된 논문에 나온 방법

각 노드는 처리한 연산의 갯수의 카운터, 노드 ID 를 쌍으로 가지는 타임스탬프를 가짐 두 타임스탬프에서 카운터가 큰 것이, 그리고 노드 ID가 큰 값이 타임 스탬프가 큼

→ 모든 노드, 클라이언트는 최댓값을 가지는 카운터를 추적하고 요청, 응답에 따라 최댓값 갱신

타임스탬프 순서화로는 불충분

일관적 인과성을 갖는 연산의 전체 순서를 정의하지만 분산 시스템의 공통 문제를 해결하는데 불충분 연산들을 사후에 결정하는게 아닌, 요청을 받는 즉시 결정해야 할 때 문제가 생김

연산의 전체 순서를 모든 연산을 모은 후에 결정되는 것이 원인 전체 순서를 언제 확정할 것인지 전체 순서 브로드캐스트를 통해 다룸

전체 순서 브로드캐스트

신뢰성 있는 전달

어떤 메시지도 손실되지 않는다.
메시지가 하나의 노드에 전달되면 모든 노드에 전달되어야 한다.

전체 순서가 정해진 전달 : 메시지는 모든 노드에 같은 순서로 전달된다.

이 두 속성은 노드나 네트워크 결함이 있어도 항상 만족되어야 한다. 물론 네트워크가 끊긴 순간에는 메시지가 전달되지 못하지만 결국 복구될 것이고 메시지 전송을 계속하여 재시도하면 이를 만족할 수 있을 것이다.

메시지가 전달되는 순서가 곧 시스템에서 연산의 전체 순서를 의미한다. 전체 순서 브로드캐스트의 중요한 측면은 메시지가 전달되는 시점에 순서가 고정된다는 것이다.

후속 메시지가 이미 전달된 경우 그 앞의 순서에 메시지를 끼워넣는 것을 허용하지 않는다.

4. 분산 트랜잭션과 합의

합의의 목적 : 여러 노드들이 무언가에 동의하게 만드는 것

노드가 동의하는 것이 중요한 상황

리더 선출

단일 리더 복제의 경우 리더가 어떤 노드인지 합의가 필요
스플릿 브레인 현상을 방지

분산 트랜잭션의 원자적 커밋

여러 노드나 파티션에 걸친 트랜잭션이 노드 별로 성공, 실패의 결과가 다를 수 있음
성공이든 실패든 모든 노드가 트랜잭션의 하나의 결과에 동의해야 함
트랜잭션의 원자성 유지를 위함

원자적 커밋과 2단계 커밋 (2PC)

파티셔닝된 데이터베이스에 다중 객체 트랜잭션을 사용하거나 용어 파티셔닝된 보조 색인을 사용할 수 있다.

각 노드에서 독립적으로 트랜잭션을 커밋 하면 어떤 노드는 성공, 어떤 노드는 실패할 가능성이 다분하다. 이는 부분적인 성공, 실패를 의미하므로 원자성을 위반하며 이를 허용하면 노드 간의 일관성도 없어진다.

일단 커밋 후 문제가 있으면 취소하면 되지 않을까?

직후 발생한 또 다른 트랜잭션에서 커밋된 데이터에 의존할 가능성이 있다.
이러한 트랜잭션도 모두 취소 되어야 한다. 그래서 커밋 후 취소하는 방법은 적절하지 않다.
따라서 트랜잭션 커밋은 되돌릴 수 없다.
노드가 트랜잭션을 커밋 하려면 다른 노드에서도 이 트랜잭션이 커밋되리라는 확신을 갖고 있어야 한다.

단계 커밋(2PC, 2-phase commit) 소개

2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는 알고리즘이다.

코디네이터와 참여자

코디네이터

트랜잭션 관리자라고도 한다.
애플리케이션 프로세스 내에서 라이브러리 형태로 구현되거나 분리된 프로세스 또는 서비스로 제공될 수 있다.

참여자

트랜잭션을 커밋하는 각 데이터베이스 노드

2단계 커밋의 절차

애플리케이션이 여러 노드에 데이터를 기록한다.
애플리케이션이 커밋할 준비가 되면 코디네이터가 1단계를 시작한다. 각 노드에 준비 요청을 보낸다.
모든 참여자가 커밋 준비가 완료되면 2단계에서 커밋 요청을 한다.
커밋 준비가 되지 않은 참여자가 있다면 2단계에서 어보트 요청을 한다.

약속에 관한 시스템

위에서 설명한 내용 만으로는 2단계 커밋이 원자성을 어떻게 보장하는 지 명확하지 않다. 준비 요청과 커밋 요청은 2단계에서 손실될 가능성이 있기 때문이다.

애플리케이션은 분산 트랜잭션을 시작할 때 코디네이터에게 트랜잭션 ID를 요청한다. 이 트랜잭션 ID는 전역적으로 유일하다.

애플리케이션은 발급받은 트랜잭션 ID를 가지고 각 참여자에서 단일 노드 트랜잭션을 시작한다. 읽기와 쓰기는 이 과정에서 실행된다.

이 단계에서 노드가 죽거나 타임아웃 등의 문제가 발생하면 코디네이터나 참여자 중 누군가 어보트할 수 있다.
이후 코디네이터가 준비 요청을 한다. 참여자가 준비 요청을 받으면 트랜잭션 커밋이 가능한지 점검한다.

코디네이터가 준비 요청에 대한 응답을 받은 후, 트랜잭션을 커밋할지 어보트 할지 최종적으로 결정한다.
코디네이터가 최종 결정을 완료하였으니, 모든 참여자에게 커밋 또는 어보트 요청을 전송한다.

트랜잭션 커밋을 결정하는 참여자의 응답과 코디네이터의 결정은 번복될 수 없다. 이러한 약속이 2PC의 원자성을 보장한다.

코디네이터 장애

앞에서 2PC 과정 중 문제가 발생하면 어떻게 진행되는 지 설명했다.

1단계에서 문제가 발생하면 코디네이터가 트랜잭션을 어보트한다. 2단계에서 문제가 발생하면 코디네이터가 요청을 무한히 재시도한다.

코디네이터가 죽는다면?

코디네이터가 준비 요청을 보내기 전에 장애가 발생하면 참여자가 트랜잭션을 어보트할 수 있다. 그런데 준비 요청에 ‘네’라고 대답을 보낸 이후는 참여자가 일방적으로 어보트할 수 없다.

코디네이터로부터 2단계 요청을 받을 때 까지 기다려야 한다. 이런 상태의 트랜잭션을 의심스럽다 또는 불확실하다고 한다.

데이터베이스1은 코디네이터의 커밋 요청을 대기하고 있다. 이러한 경우 코디네이터가 복구되는 것을 기다릴 수 밖에 없다.

다행히 코디네이터는 요청을 보내기 전에 커밋 로그를 기록했다. 코디네이터가 복구되면 트랜잭션 로그를 읽어 의심스러운 트랜잭션들의 상태를 결정한다.

커밋 레코드가 없는 트랜잭션은 어보트된다. 있다면 커밋 요청을 재시도할 것이고 2단계 과정도 완료될 것이다. 2단계 커밋은 코디네이터가 복구될 때 까지 중단되므로 블로킹 원자적 커밋 프로토콜이라 한다.

3단계 커밋

3단계 커밋

2PC의 대안으로 제안된 알고리즘

지연에 제한이 있는 네트워크, 응답 시간에 제한이 있는 노드를 전제로 한다. (→ 현실과 동떨어짐) 따라서 현실적인 분산 시스템에서 3PC를 적용하기는 어려워 코디네이터 장애 관련 문제가 있음에도 불구하고 2PC가 계속 사용됨

현실의 분산 트랜잭션

분산 트랜잭션에 대한 엇갈린 평판

부정적

운영상의 문제 유발
성능 이슈의 원인
 ㄴ 장애 복구에 필요한 부가적인 디스크 강제 쓰기(fsync), 부가적인 네트워크 왕복 시간을 강요
 ㄴex. MySQL : 분산 트랜잭션이 단일 노드 트랜잭션보다 10배 이상 느리다.
분산 트랜잭션이 제공해주는 이점에 비해 비용이 너무 큰 것 아닌가?

두 가지 종류의 분산 트랜잭션

데이터베이스 내부 분산 트랜잭션

분산 시스템(복제, 파티셔닝)을 지원하는 데이터베이스는 노드 사이의 내부 트랜잭션을 지원 트랜잭션에 참여하는 모든 노드는 동일한 데이터베이스 소프트웨어를 실행한다.

다른 시스템과 호환될 필요가 없어 프로토콜 선택, 구현이 자유롭고 최적화가 가능하다.

이종 분산 트랜잭션

참여자들이 각기 다른 기술을 기반으로 하는 경우

두 가지 서로 다른 벤더의 데이터베이스나 메시지 브로커와 같은 비데이터베이스 시스템이 참여하는 경우 서로 다른 시스템 간의 원자적 커밋을 보장해야 함

다양한 시스템들이 강력한 방법으로 통합될 수 있게 한다.

의심스러운 상태에 있는 동안 잠금을 유지하는 문제

트랜잭션이 의심스러운 상태에 있는 동안 트랜잭션과 관련된 객체에 잠금이 설정될 수 있다. 잠금은 트랜잭션이 커밋, 어보트 되기 전까지 해제가 불가능하다.

코디네이터의 로그가 손실된 경우 관리자가 수동으로 잠금을 해제해야 하는 경우도 있다. 잠금이 유지되면 다른 트랜잭션 실행에 지장을 초래하여 애플리케이션에도 치명적이다.

코디네이터 장애에서 복구하기

고아가 된 의심스러운 트랜잭션

이론과 달리 현실에서는 코디네이터가 복구 과정에서 결과를 결정할 수 없는 트랜잭션이 존재

트랜잭션 로그가 손실된 경우, 소프트웨어 버그

이런 트랜잭션에 의한 잠금은 자동으로 해소되지 않아 관리자의 개입을 필요로 한다.

데이터베이스 서버 재부팅을 해도 잠금이 유지된다.
잠금이 자동으로 해소되면 원자성이 깨질 위험이 있기 때문
관리자가 참여자의 상태를 조사하고 커밋, 롤백을 수동으로 결정한다.
경험적 결정(heuristic decision) 관리자가 개입하여 해결하는 것은 많은 수작업을 요구하고 (심각한 상황이므로) 높은 스트레스를 유발한다.
그런데 이는 2PC의 약속을 깨뜨리기 때문에 원자성을 위반할 위험이 있다.
따라서 경험적 결정은 평상시에 사용하는 것이 아닌, 큰 장애 상황을 벗어나기 위한 용도로 의도된 것이다.

분산 트랜잭션의 제약

코디네이터가 전체 시스템의 단일 장애점(single point of failure)

코디네이터가 복제되지 않고 단일 장비에서만 실행되면 전체 시스템의 단일 장애점이 된다.
코디네이터에 장애가 생기면 결과적으로 애플리케이션 전체에 영향을 주기 때문
그럼에도 불구하고 여러 코디네이터 구현은 고가용성을 제공하지 않거나 기본적인 복제만 지원

애플리케이션 서버가 상태를 갖게(stateful) 된다

서버 애플리케이션은 영속적인 상태를 데이터베이스에 저장한다.
이는 서버가 무상태성(stateless)이어야 확장성에 유리하기 때문
코디네이터가 애플리케이션 서버의 일부가 되면 트랜잭션 로그가 서버의 로컬 디스크에 저장된다.
따라서 서버가 상태를 갖게 되는 문제가 발생한다.

내결함성을 지닌 합의

비공식적으로 합의는 여러 노드가 어떤 것에 동의하는 것을 의미한다.
여러 사용자가 동시에 동일한 좌석 예약을 하는 경우 처럼 공존할 수 없는 연산들 중 어떤 것이 승자가 되는 지를 결정하기 위해 합의 알고리즘을 사용할 수 있다.
하나 또는 그 이상의 노드들이 값을 제안하고 합의 알고리즘이 값 중 하나를 결정한다.

합의 알고리즘의 속성

합의 알고리즘은 아래의 속성들을 만족해야 한다.

균일한 동의 : 어떤 두 노드도 다르게 결정하지 않는다.
무결성 : 어떤 노드도 두 번 결정하지 않는다.
유효성 : 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다.
종료 : 죽지 않은 노드는 결국 어떤 값을 결정한다.

균일한 동의, 무결성, 유효성 균일한 동의와 무결성 속성은 합의의 핵심 아이디어를 정의 모두 같은 결과로 결정하며 한 번 결정하면 바꿀 수 없다.

유효성 속성은 뻔한 해결책을 배제하기 위해 존재한다.

종료 종료는 내결함성과 관련된 속성으로 종료 속성에 의해 합의 알고리즘에서 합의는 중단될 수 없고 반드시 진행되어야 한다.

내결함성을 만족시킬 필요가 없으면 종료를 제외한 세 개의 속성을 만족하는 것은 간단하다. 종료는 활동성 속성이고 다른 세 개는 안전성 속성이다.

합의의 제약

합의 알고리즘을 통해 분산 시스템에서 일관성과 내결함성을 모두 달성할 수 있다. 그러나 합의 알고리즘을 유지하기 위한 비용이 적지 않다.

동기식 복제가 강제됨

제안이 결정되기 전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제다. 동기식 복제가 비동기 복제보다 일관성, 지속성 측면에서 안전함에도 불구하고 성능을 이유로 선호되지 않는다.

과반수에 대한 제약

합의 시스템은 항상 엄격한 과반수가 동작하는 것을 요구한다. 노드 한 대의 장애를 견디려면 최소한 세 대의 노드, 두 대의 장애를 견디려면 최소 다섯 대의 노드가 필요하다.

네트워크 장애로 일부 노드가 다른 노드와 연결이 끊기면 과반수의 부분만 동작이 가능하고 나머지는 차단된다.

노드 수 변경에 대한 제약

대부분 합의 알고리즘은 투표에 참여하는 노드 집합이 고정되어 있다고 가정하므로 클러스터에 노드를 그냥 추가/제거할 수 없다.

합의 알고리즘의 동적 멤버십 확장은 클러스터에 있는 노드 집합이 시간이 지남에 따라 바뀌는 것을 허용하지만 정적 멤버십 알고리즘보다 훨씬 이해하기 어렵다.

네트워크 문제에 민감

합의 시스템은 장애를 감지하기 위해 타임아웃에 의존한다. 타임아웃은 노드의 문제와 네트워크 문제를 구별하지 못해 네트워크 문제 시에도 노드가 죽었다고 판단할 수 있다.

이러한 오류로 인해 리더가 자주 새로 선출되면 시스템이 본연의 일이 아닌 리더를 선출하는 데 더 집중하게 된다.

이러한 현상은 성능 문제로 연결된다.

멤버십과 코디네이션 서비스

주키퍼나 etcd 같은 프로젝트는 종종 ‘분산 키-값 저장소’나 ‘코디네이션 설정 서비스’라고 설명된다. 주키퍼와 etcd는 메모리에 적재가 가능한 작은 양의 데이터를 보관하도록 설계되었다. 이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트를 통해 모든 노드에 걸쳐 복제된다.

작업을 노드에 할당하기

작업을 노드에 할당해야 하는 경우

단일 리더 복제에서 리더에 장애가 발생하면 다른 노드 중 하나가 넘겨 받아야 한다.
파티셔닝된 자원에서 어떤 파티션을 어떤 노드에 할당해야 할 지 결정해야 한다.
새 노드들이 클러스터에 합류하면서 부하의 재균형화를 위해 어떤 파티션들은 새로운 노드로 이동해야 한다.
노드가 제거되거나 장애가 나면 다른 노드들이 장애가 난 노드의 작업을 넘겨받아야 한다.

이런 종류의 작업은 주키퍼에서 원자적 연산, 단명 노드, 알림을 신중하게 사용하면 잘 수행할 수 있다. 매우 많은 노드에서 과반수 투표를 수행하는 것은 비효율적이므로 주키퍼는 고정된 수의 노드에서 실행되고 이 노드들 사이에서 과반수 투표를 수행한다.

주키퍼는 노드들을 코디네이트 하는 작업의 일부를 외부 서비스에 위탁하는 방법을 제공한다.

서비스 찾기

주키퍼, etcd, 콘술(Consul)은 서비스 찾기(특정 서비스에 연결하기 위해 IP 주소를 알아내는 것) 용도로도 자주 사용된다.

멤버십 서비스

멤버십 서비스는 클러스터에서 어떤 노드가 현재 살아있는 멤버인지 결정한다. 장애 감지를 합의와 연결하여 노드들이 어떤 노드가 살아있고 죽었는지에 동의할 수 있다.

물론 기약 없는 네트워크 지연 때문에 노드에 장애가 발생한 것인지 확실히 알 수는 없고, 잘못 판단할 수 있다. 그럼에도 불구하고 합의는 시스템에서 어떤 노드가 현재 멤버십을 구성하는 지 동의하는데 매우 유용하다.