9장. 일관성과 합의

일관성 보장

• 복제 데이터베이스는 대부분 최소한 최종적 일관성을 제공한다.
  • 데이터베이스에 쓰기를 멈추고 불특정 시간 동안 기다리면 결국 모든 읽기 요청이 같은 값을 반환한다는 의미이다.
  • 바꿔 말하면 불일치는 일시적이며 결국 스스로 해소한다(네트워크 결함도 결국에는 복구된다고 가정)
  • 하지만 이것은 매우 약한 보장이다. 언제 복제본이 수렴될지에 대해서는 아무것도 얘기하지 않는다. 수렴될 때까지 읽기는 뭔가를 반환할 수도, 아무것도 반환하지 않을 수도 있다.
  • 약한 보장만 제공하는 데이터베이스를 다룰 때는 그 제한을 계속 알아야 하고 뜻하지 않게 너무 많은 것을 가정하면 안 된다.
• 분산 일관성은 대개 지연과 결함이 있더라도 복제본의 상태를 코디네이션하는 것과 관련되어 있다.

 

선형성

• 선형성을 뒷받침하는 아이디어
  • 원자적 일관성(atomic consistency)
  • 강한 일관성(strong consistency)
  • 즉각 일관성(immediate consistency)
  • 외부 일관성(external consistency)
• 선형성의 기본 아이디어는 시스템에 데이터 복사본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것이다.
• 선형성 시스템에서는 클라이언트가 쓰기를 성공적으로 완료하자마자 그 데이터베이스를 읽는 모든 클라이언트는 방금 쓰여진 값을 볼 수 있어야 한다.
• 선형성은 최신성 보장(recency guarantee)으로, 읽힌 값이 최근에 갱신된 값이며 뒤처진 캐시나 복제본에서 나온 값이 아니라고 보장해준다는 의미이다.

 

잠금과 리더 선출

• 단일 리더 복제를 사용하는 시스템은 리더가 여러 개(스플릿 브레인)가 아니라 진짜로 하나만 존재하도록 보장해야 한다.
• 리더를 선출하는 한 가지 방법은 잠금을 사용하는 것으로, 모든 노드가 시작할 때 잠금 획득을 시도하고 성공한 노드가 리더가 된다.
• 분산 잠금과 리더 선출을 구현하기 위해 아파치 주키퍼나 etcd 같은 코디네이션 서비스가 사용된다.

 

제약 조건과 유일성 보장

• 유일성 제약 조건은 데이터베이스에서 흔하다.(ex 사용자명, 이메일 주소)
• 데이터가 기록될 때 이 제약 조건을 강제하고 싶다면 선형성이 필요하다.
• 실제 애플리케이션에서는 이런 제약 조건을 느슨하게 다뤄도 되지만, 관계형 데이터베이스에서 전형적으로 볼 수 있는 엄격한 유일성 제약 조건은 선형성이 필요하다.

 

채널 간 타이밍 의존성

• 선형성의 최신성 보장이 없으면 채널 사이의 경쟁 조건이 발생할 수 있다.
• 선형성이 경쟁 조건을 회피하는 유일한 방법은 아니지만 이해하기에 가장 단순하다.

 

선형성 시스템 구현하기

• 가장 간단한 방법은 데이터 복사본을 하나만 사용하는 것이지만, 이 방법으로는 결함을 견뎌낼 수 없다.
• 시스템이 내결함성을 지니도록 만드는 가장 흔한 방법은 복제를 사용하는 것이다.
  • 단일 리더 복제(선형적이 될 가능성이 있음) : 리더는 쓰기에 사용되는 데이터의 주 복사본을 갖고 있고 팔로워는 다른 노드에 데이터의 백업 복사본을 보관한다. 리더나 동기식으로 갱신된 팔로워에서 실행한 읽기는 선형적이 될 가능성이 있다.
  • 합의 알고리즘(선형적) : 합의 프로토콜에서는 스플릿 브레인과 복제본이 뒤처지는 문제를 막을 수단이 포함되어있어 선형성 저장소를 안전하게 구현할 수 있다.
  • 다중 리더 복제(비선형적) : 여러 노드에서 동시에 쓰기를 처리하고 비동기로 다른 노드에 복제하기 때문에 일반적으로 선형적이지 않다.
  • 리더 없는 복제(아마도 비선형적) : 정족수의 정확한 설정과 엄격한 일관성을 어떻게 정의하냐에 따라 비선형적으로 동작할 가능성이 있다.

 

선형성과 정족수

• 엄격한 정족수를 사용한 읽기쓰기는 선형적인 것처럼 보이지만 네트워크 지연의 변동이 심하면 경쟁 조건이 생길 수 있다.
• 정족수 조건이 만족(w + r > n)됨에도 실행은 선형적이지 않을 수 있다.
• 성능 저하 비용을 지불하면 다이나모 스타일 정족수를 선형적으로 만드는게 가능하다.
  • 읽기 클라이언트는 결과를 애플리케이션에 반환하기 전에 읽기 복구를 동기식으로 수행해야 한다.
  • 쓰기 클라이언트는 쓰기 요청을 보내기 전에 노드들의 정족수로부터 최신 상태를 읽어야 한다.
• 다이나모 스타일 복제를 하는 리더 없는 시스템은 선형성을 제동하지 않는다고 보는게 안전하다.

 

선형성의 비용

• 다중 리더 복제
  • 다중 데이터 센터는 데이터 센터 간 네트워크 연결이 끊겨도, 각 데이터 센터는 정상 동작하고 복제는 큐에 쌓였다가 네트워크 연결이 복귀되면 다른 데이터 센터로 전달된다.
• 단일 리더 복제
  • 리더가 데이터센터 중 하나에만 있어야 하고 모든 쓰기와 선형성 읽기는 리더로 보내져야 한다.
  • 데이터센터 사이의 네트워크가 끊기면 팔로워 데이터센터로 접속한 클라이언트들은 리더로 연결할 수 없으므로 쓰기와 읽기가 불가능하다. 팔로워로부터 읽을 수는 있지만 데이터가 뒤처졌을 수 있다.(비선형적)

 

CAP 정리

• 일관성(Consistency), 가용성(Availability), 분단 내성(Partition tolerance)
• 트레이드 오프
  • 애플리케이션에서 선형성을 요구하고 네트워크 문제 때문에 일부 복제 서버가 다른 복제 서버와 연결이 끊기면 일부 복제 서버는 연결이 끊긴 동안은 요청을 처리할 수 없다. 네트워크 문제가 고쳐질 때까지 기다리거나 오류를 반환해야 한다(가용성이 없다)
  • 애플리케이션에서 선형성을 요구하지 않는다면 각 복제 서버가 다른 복제 서버와 연결이 끊기더라도 독립적으로 요청을 처리하는 방식으로 쓰기를 처리할 수 있다. 네트워크 문제가 발생해도 가용한 상태를 유지하지만 선형적이지 않다.
• 하나의 일관성 모델(선형성)과 한 종류의 결함(네트워크 분단 혹은 노드가 살아 있지만 서로 연결이 끊긴 상황)만 고려한다.
• 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 선택하라는 의미이다.

 

선형성과 네트워크 지연

• 선형성 보장을 제공하지 않는 이유는 내결함성이 아니라 성능 때문이다.(선형성은 느림)
• 선형성을 제공하는 더울 빠른 알고리즘은 존재하지 않지만 완화된 일관성 모델은 훨씬 더 빠를 수 있다. 따라서 지연 시간에 민감한 시스템에서는 이 트레이드오프가 중요하다.

 

순서화 보장

• 순서화, 선형서으 합의 사이에는 깊은 연결 관계가 존재한다.

 

순서와 인과성

• 순서화는 인과성을 보존하는 데 도움을 준다.
• 인과성은 이벤트에 순서를 부과한다. 결과가 나타나기 전에 원인이 발생한다.
• 인과적으로 의존하는 연산의 연쇄는 시스템에서 인과적 순서, 즉 무엇이 무엇보다 먼저 일어났는가를 정의한다.
• 시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적(causally consistent)이라고 한다.

 

인과적 순서가 전체 순서는 아니다.

• 전체 순서는 어떤 두 요소를 비교할 수 있게 하므로 두 요소가 있으면 항상 어떤 것이 더 크고 어떤 것이 더 작은지 말할 수 있다.
• 부분 순서는 비교가 불가능하고 부분적으로 순서가 정해진다.
• 데이터베이스 일관성 모델
  • 선형성 : 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다.
  • 인과성 : 두 이벤트가 인과적인 관계가 있으면 이들은 순서가 있지만, 동시에 실행되면 비교할 수 없다. 인과성은 전체 순서가 아닌 부분 순서를 정의한다.
• 선형성 데이터스토어에는 동시적 연산이 없다. 하나의 타임라인이 있고 모든 연산은 그 타임라인을 따라서 전체 순서가 정해져야 한다.
• 동시성은 타임라인이 갈라졌다 다시 합쳐지는 것을 의미하며, 다른 가지에 있는 연산은 비교 불가(동시적)하다.

 

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

• 선형성은 인과성을 내포한다.
• 어떤 시스템이든지 선형적이라면 인과성도 올바르게 유지한다.
• 하지만 네트워크 지연이 크면 선형성은 성능과 가용성에 해가 될 수 있다.
• 선형성은 인과성을 보존하는 유일한 방법이 아니다. 시스템은 선형적으로 만드는 성능 손해를 유발하지 않고도 인과적 일관성을 만족시킬 수 있다.
• 많은 경우에 선형성이 필요한 것처럼 보이는 시스템에 진짜로 필요한 것은 인과적 일관성이다.

 

인과적 의존성 담기

• 비선형 시스템이 인과적 일관성을 유지하는 방법
  • 인과성 유지를 위해서는 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다.(부분 순서)
  • 동시에 실행되는 연산은 어떤 순서로든 처리될 수 있지만 한 연산이 다른 연산보다 먼저 실행됐다면 모든 복제 서버는 그 순서로 처리되어야 한다.
  • 복제 서버가 연산을 처리할 때 인과적으로 앞서는 모든 연산이 이미 처리됐다고 보장할 수 있어야 한다.
• 인과적 의존성을 결정하려면 시스템에 있는 노드에 관한 지식을 기술할 방법이 필요하다.(어떤 연산이 다른 연산보다 먼저 실행됐는지 결정하는 기법)
• 인과적 순서를 결정하기 위해 데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야 한다.

 

일련번호 순서화

• 인과성은 중요한 이론적 개념이지만 모든 인과적 의존성을 실제로 추적하는 것은 실용성이 떨어진다.
• 읽은 데이터를 모두 명시적으로 추적하는 것은 오버헤드가 크다.
• 일련번호나 타임스탬프를 써서 이벤트의 순서를 정하는 방법이 더 좋다.
  • 일련번호나 타임스탬프는 크기가 작고 전체 순서를 제공한다.
  • 즉 모든 연산은 고유 일련번호를 갖고 항상 두 개의 일련번호를 비교해서 어떤 것이 큰지 결정할 수 있다.
  • 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다.
  • ex) 단일 리더 복제 : 리더는 연산마다 카운터를 증가시키고 복제 로그의 각 연산에 단조 증가하는 일련번호를 할당 -> 팔로워가 복제 로그에 나오는 순서대로 쓰기 적용

 

비인과적 일련번호 생성기

• 단일 리더가 없는 경우(다중 리더, 리더 없는 데이터베이스, 데이터베이스 파티셔닝)
  • 각 노드가 자신만의 독립적인 일련번호 집합을 생성
  • 각 연산에 일 기준 시계(물리적 시계)에서 얻은 타임스탬프를 붙임
  • 일련번호 블록을 미리 할당(A - 1~1000, B - 1001 ~ 2000)
• 카운터를 증가시키는 단일 리더에 모든 연산을 밀어넣는 것보다 확장성이 좋다.
• 하지만 생성한 일련번호가 인과성에 일관적이지 않다.
  • 각 노드는 초당 연산수가 다를 수 있어서 홀수 연산과 짝수 연산이 있을 때 어떤 것이 인과적으로 먼저 실행됐는지 알 수 없다.
  • 시계 스큐에 종속적이어서 인과성에 일관적이지 않게 될 수 있다.(나중에 실행된 연상이 더 낮은 타임스탬프 배정)
  • 블록 할당자의 경우 나중에 실행되는 연산이 1~1000 사이의 구간에서 일련번호를 받을 수 있다.

 

램포트 타임스탬프

• 인과성에 일관적인 일련번호를 생성하는 간단한 방법
• 각 노드는 고유 식별자를 갖고 각 노드는 처리한 연산 개수를 카운터로 유지한다.
• (카운터, 노드ID)의 쌍이다.
• 물리적 일 기준 시계와 아무 관련이 없지만 전체 순서화를 제공한다.
• 두 타임스탬프가 있으면 카운터가 큰 것이 타임스탬프가 크다. 카운터 값이 같으면 노드 ID가 큰 것이 타임스탬프가 크다.
• 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다.
• 노드가 자신의 카운터 값보다 큰 최대 카운터를 가진 요청이나 응답을 받으면 바로 자신의 카운터를 그 최댓값으로 증가시킨다.

 

타임스탬프 순서화로는 충분하지 않다

• 램포트 타임스탬프가 인과성에 일관적인 연산의 전체 순서를 정의하지만 분산 시스템의 여러 공통 문제를 해결하는 데 충분하지는 않다.
• 예를들어 사용자명에 대하 유일성 제약 조건 같은 것을 구현하려면 연산의 전체 순서가 있는 것으로는 충분하지 않다. 언제 그 순서가 확정되는지도 알아야 한다.
• 연산의 전체 순서는 모든 연산을 모은 후에야 드러난다. 다른 노드가 어떤 연산을 생성했지만 그것이 무엇인지 아직 알 수 없다면 연산의 최종 순서를 만들어낼 수 없다.
• 언제 전체 순서가 확정되는지 알아야 한다. => 전체 순서 브로드캐스트

 

전체 순서 브로드캐스트(total order broadcast)

• 노드 사이에 메시지를 교환하는 프로토콜로 기술된다.
• 두 가지 안전성 속성을 항상 만족해야 한다.
  • 신뢰성 있는 전달(reliable delivery) : 어떤 메시지도 손실되지 않는다. 메시지가 한 노드에 전달되면 모든 노드에도 전달된다.
  • 전체 순서가 정해진 전달(totally ordered delivery) : 메시지는 모든 노드에 같은 순서로 전달된다.
• 전체 순서 브로드캐스트를 구현하는 알고리즘은 노드나 네트워크에 결함이 있더라도 신뢰성과 순서화 속성이 항상 만족되도록 보장해야 한다.
• 네트워크가 끊긴 동안 메시지가 전달될 수 없지만 알고리즘이 재시도를 계속해서 네트워크가 복구되면 메시지가 전달되게 할 수 있다.

 

전체 순서 브로드캐스트 사용하기

• 주키퍼나 etcd 같은 합의 서비스는 전체 순서 브로드캐스트를 실제로 구현한다.
• 데이터베이스 복제에 딱 필요한 것이다.
  • 상태 기계 복제(state machine replication)
  • 모든 메시지가 데이터베이스에 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태를 유지한다.
• 직렬성 트랜잭션을 구현하는 데도 사용된다.
  • 모든 메시지가 스토어드 프로시저로 실행되는 결정적 트랜잭션을 나타낸다면, 그리고 모든 노드가 그 메시지들을 같은 순서로 처리한다면 데이터베이스의 파티션과 복제본은 서로 일관적인 상태를 유지한다.
• 메시지가 전달되는 시점에 그 순서가 고정된다.(타임스탬프 순서화보다 강하다)
• 로그를 만드는 방법 중 하나이다.(복제 로그, 트랜잭션 로그, 쓰기 전 로그)
• 펜싱 토큰을 제공하는 잠금 서비스를 구현하는 데도 유용하다.

 

전체 순서 브로드캐스트를 사용해 선형성 저장소 구현하기

• 선형성 시스템과 전체 순서 브로드캐스트 사이에는 밀접한 관계가 있다.
• 전체 순서 브로드캐스트
  • 비동기식
  • 메시지는 고정된 순서로 신뢰성 있게 전달되도록 보장되지만 언제 메시지가 전달될지는 보장하지 않는다.
• 선형성 시스템
  • 최신성 보장
  • 읽기가 최근에 쓰여진 값을 보는게 보장된다.
• 전체 순서 브로드캐스트 구현이 있다면 이를 기반으로 한 선형성 저장소를 만들 수 있다.
• 사용자 계정의 사용자명으로 식별 -> 사용 가능한 모든 사용자명마다 원자적 compare-and-set 연산이 구현된 선형성 저장소
  
  • 메시지를 로그에 추가해서 점유하기 원하는 사용자명을 시험적으로 가리킨다.
  • 로그를 읽고, 추가한 메시지가 되돌아오기를 기다린다.
  • 원하는 사용자명을 점유하려고 하는 메시지가 있는지 확인한다. 자신의 메시지가 첫번째면 성공, 아니면 어보트한다.
• 로그 항목은 모든 노드에 같은 순서로 전달되므로 여러 개의 쓰기가 동시에 실행되면 모든 노드가 어떤 쓰기가 먼저 실행될 것인지 동의한다.
• 충돌하는 쓰기 중 첫 번째 것을 승자로 택하고 나머지를 어보트시키면 모든 노드는 쓰기가 커밋되거나 어보트되는지에 동의하게 된다.
• 이 절차는 선형성 쓰기를 보장하지만 선형성 읽기는 보장하지 않는다. 로그로부터 비동기로 갱신되는 저장소를 읽으면 오래된 값이 읽힐 수 있다.

 

선형성 저장소를 사용해 전체 순서 브로드캐스트 구현하기

• 정수를 저장하고 원자적 increment-and-set 연산이 지원되는 선형성 레지스터가 있다고 가정
• 전체 순서 브로그캐스트를 통해 보내고 싶은 모든 메시지에 대해 선형성 정수로 increment-and-get 연산을 수행하고 레지스터에서 얻은 값을 일련번호로 메시지에 붙힌다.
• 그 후 메시지를 모든 노드에 보낼 수 있고 수신자들은 일련번호 순서대로 메시지를 전달한다.
• 전체 순서 브로드캐스트와 타임스탬프 순서화의 핵심 차이
  • 선형성 레지스터를 증가시켜서 얻은 숫자들은 틈이 없는 순열을 형성
  • 따라서 어떤 노드가 메시지 4를 전달하고 일련번호가 6인 메시지를 받았다면 메시지 6을 전달하기 전에 메시지 5를 기다려야 한다는 것을 알 수 있다.
  • 램포트 타임스탬프는 그렇지 않다.
• 선형성 compare-and-set(또는 increment-and-get) 레지스터와 전체 순서 브로드캐스트는 둘 다 합의와 동등하다고 증명할 수 있다.

 

분산 트랜잭션과 합의

• 합의의 목적은 단지 여러 노드들이 뭔가에 동의하게 만드는 것이다.
  • 리더 선출 : 모든 노드는 어떤 노드가 리더인지 동의해야 한다.
  • 원자적 커밋 : 여러 노드나 파티션에 걸친 트랜잭션을 지원하는 데이터베이스에서는 모든 노드가 트랜잭션의 결과에 동의하게 만들어야 한다.(모두 어보트/롤백되거나 모두 커밋)

 

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

단일 노드에서 분산 원자적 커밋으로

• 단일 노드
  • 트랜잭션 커밋은 데이터가 디스크에 지속성 있게 쓰여지는 순서에 결정적으로 의존한다.
  • 데이터가 먼저고 커밋 레코드는 그 다음이다.
  • 트랜잭션이 커밋되거나 어보트되는지를 결정하는 핵심적인 시점은 디스크가 커밋 레스트 쓰기를 마치는 시점이다.
  • 커밋을 원자적으로 만들어주는 것은 단일 장치(특정한 하나의 노드에 부탁된 하나의 특정 디스크 드라이브의 컨트롤러)다.
• 다중 노드
  • 어떤 노드에서는 커밋이 성공하고 다른 노드에서는 실패해서 원자성 보장을 위반하기 쉽다.
  • 어떤 노드는 트랜잭션을 커밋하지만 다른 노드는 어보트한다면 노드들이 서로 일관성이 없어진다.
  • 노드는 트랜잭션에 참여하는 다른 모든 노드도 커밋될 것이라고 확신할 때만 커밋 돼야 한다.

 

2단계 커밋 소개

• 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘이다.
• 단일 노드 트랜잭션에서는 보통 존재하지 않는 새로운 컴포넌트인 코디네이터(coordinator, 트랜잭션 관리자)를 사용한다.
• 코디네이터는 종종 트랜잭션을 요청하는 애플리케이션 프로세스 내에서 라이브러리 형태(자바 EE 컨테이너에 내장)로 구현되지만 분리된 프로세스나 서비스가 될 수 있다.(Narayana, JOTM, BTM, MSDTC)
• 과정
  • 애플리케이션이 여러 데이터베이스 노드(트랜잭션 참여자, participant)에서 데이터를 읽고 쓰기 시작
  • 애플리케이션이 커밋할 준비가 되면 코디네이터가 1단계를 시작한다.
    • 각 노드에 준비 요청을 보내서 커밋할 수 있는지 물어본다.
    • 그 후 코디네이터는 참여자들의 응답을 추적한다.
  • 모든 참여자가 커밋할 준비가 됐다고 응답하면 코디네이터는 2단계에서 커밋 요청을 보내고 커밋이 실제로 일어난다.
  • 만약 참여자 중 누구라도 아니오로 응답하면 코디네이터는 2단계에서 모든 노드에 어보트 요청을 보낸다.

 

약속에 관한 시스템

• 애플리케이션은 분산 트랜잭션을 시작하기 원할 때 코디네이터에게 트랜잭션 ID를 요청하고, 이는 전역적으로 유일하다.
• 애플리케이션은 각 참여자에게 단일 노드 트랜잭션을 시작하고, 단일 노드 트랜잭션에 전역으로 유일한 트랜잭션 ID를 붙인다.
  • 모든 읽기와 쓰기는 단일 노드 트랜잭션 중 하나로 실행된다.
  • 이 단계에서 잘못되면 코디네이터나 참여자 중 누군가 어보트할 수 있다.
• 애플리케이션이 커밋할 준비가 되면 코디네이터는 모든 참여자에게 전역 트랜잭션 ID로 태깅된 준비 요청을 보낸다. 요청 중 실패하거나 타임아웃이 될 경우 코디네이터는 모든 참여자에게 어보트 요청을 보낸다.
• 참여자가 준비 요청을 받으면 모든 상황에서 트랜잭션을 커밋할 수 있는지 확인한다.
  • 트랜잭션 데이터를 쓰는 것과 충돌, 제약조건 위반 등을 확인
  • 코디네이터에게 '네'라고 응답함으로써 노드에 요청이 있으면 트랜잭션을 오류없이 커밋할 것이라고 약속
  • 트랜잭션을 어보트할 권리를 포기하지만 실제로 커밋하지는 않음
• 코디네이터가 모든 준비 요청에 응답을 받았을 때 최종적으로 커밋/어보트 결정한다. 코디네이터가 추후 죽는 경우에 어떻게 결정했는지를 알 수 있도록 그 결정을 디스트에 있는 트랜잭션 로그에 기록해야 한다.(=커밋 포인트)
• 코디네이터 결정이 디스크에 쓰여지면 모든 참여자에게 커밋/어보트 요청이 전송되고, 요청이 실패하거나 타임아웃이 되면 코디네이터는 성공할 때까지 영원히 재시도 한다.
• 코디네이터가 한 번 결정하면 그 결정은 변경할 수 없다.

 

코디네이터 장애

• 코디네이터가 준비 요청을 보내기 전에 장애가 나면 참여자가 안전하게 트랜잭션을 어보트할 수 있다.
• 참여자가 준비 요청을 받고 "네" 응답을 보낸 이후에는 더 이상 일방적으로 어보트할 수 없다.
• 코디네이터로부터 트랜잭션이 커밋됐는지 어보트됐는지 회신 받을 때까지 기다려야 하는데, 이 때 코디네이터가 죽거나 네트워크 장애가 발생하면 참여자는 기다릴 수밖에 없다.
• 이 상태에 있는 참여자의 트랜잭션을 의심스럽다(in doubt) 또는 불확실하다(uncertain)고 한다.
• 2PC를 완료할 수 있는 유일한 방법은 코디네이터의 복구이다.

 

3단계 커밋

• 2단계 커밋은 2PC가 코디네이터가 복구하기를 기다리느라 멈출 수 있다는 사실 때문에 블로킹 원자적 커밋 프로토콜이라고 불린다.
• 3단계 커밋 알고리즘
  • 2PC의 대안
  •  지연에 제한이 있는 네트워크와 응답 시간에 제한이 있는 노드를 가정
  • 기약 없는 네트워크 지연과 프로세스 중단이 있는 대부분의 실용적 시스템에서 3PC는 원자성을 보장하지 못한다.
• 논블로킹 원자적 커밋
  • 완벽한 장애 감지기, 즉 노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메커니즘이 필요하다.

 

현실의 분산 트랜잭션

• 2단계 커밋으로 구현된 분산 트랜잭션은 안전성 보장을 제공하지만, 운영상의 문제를 일으키고 성능을 떨어뜨린다는 평가를 받는다.
• 어떤 분산 트랜잭션 구현은 무거운 성능 손해를 수반한다.(ex MySQL의 분산 트랜잭션)
• 분산 트랜잭션 종류
  • 데이터베이스 내부 분산 트랜잭션: 데이터베이스 노드 사이에 내부 트랜잭션을 지원한다. 트랜잭션에 참여하는 모든 모드는 동일한 데이터에비스 소프트웨어를 실행한다.
  • 이종 분산 트랜잭션: 서로 다른 벤더의 데이터베이스이거나 메시지 브로커처럼 비데이터베이스 시스템 간의 트랜잭션으로 시스템의 내부가 완전히 다르더라도 원자적 커밋을 보장해야 한다.

 

정확히 한 번 메시지 처리

• 이종 분산 트랜잭션은 다양한 시스템들이 강력한 방법으로 통합될 수 있게 한다.
  • 메시지 큐에서 나온 메시지는 그 메시지를 처리하는 데이터베이스 트랜잭션이 커밋에 성공했을 때만 처리된 것으로 확인받을 수 있다.
  • 메시지 확인과 데이터베이스 쓰기를 단일 트랜잭션에서 원자적으로 커밋함으로써 구현할 수 있다.
• 이런 분산 트랜잭션은 트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능하다.

 

XA 트랜잭션

• X/Open XA(eXtended Architecture)는 이종 기술에 걸친 2단계 커밋을 구현하는 표준이다.
• XA는 네트워크 프로토콜이 아니라 트랜잭션 코디네이터와 연결되는 인터페이스를 제공하는 C API일 뿐이다.
• XA는 애플리케이션이 네트워크 드라이브나 클라이언트 라이브러리를 사용해 참여자 데이터베이스나 메시징 서비스와 통신한다고 가정한다.
  • 드라이버가 XA를 지원한다는 것은 연산이 분산 트랜잭션의 일부가 돼야 하는지 알아내기 위해 XA API를 호출한다는 의미이다.
  • 드라이버는 데이터베이스 서버로 필요한 정보를 보낸다.
  • 드라이버는 코디네이터가 참여자에게 준비, 커밋, 어보트를 요청할 수 있는 콜백을 제공한다.
• 트랜잭션 코디네이터는 XA API를 구현한다.
  • 현실에서는 트랜잭션을 시작하는 애플리케이션과 같은 프로세스에 로딩되는 단순란 라이브러리다.
  • 트랜잭션의 참여자를 추적하고 참여자들에게 준비 요청을 보낸 후 그들의 응답을 수집하고 각 트랜잭션에 대한 커밋/어보트 결정을 추적하기 위해 로컬 디스크에 있는 로그를 사용한다.
• 애플리케이션 프로세스가 죽거나 애플리케이션이 실행 중인 장비가 죽으면 코디네이터도 함께 사라진다.
  • 준비됐지만 커밋되지 않은 트랜잭션들을 가진 참여자들은 의심스러운 상태에 빠진다.
  • 서버가 재시작되면 코디네이터 라이브러리가 로그를 읽어서 각 트랜잭션의 커밋/어보트 결과를 복구해야 한다.
  • 데이터베이스의 드라이버의 XA 콜백을 사용해 요청할 수 있다.

 

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

• 데이터베이스 트랜잭션은 보통 더티 쓰기를 막기 위해 그들이 변경한 로우에 로우 수준의 독자적인 잠금을 획득하고, 추가로 직렬성 격리를 원한다면 2단계 잠금을 사용하는 데이터베이스는 트랜잭션에서 읽은 로우에 공유 잠금도 획인해야 한다.
• 데이터베이스는 트랜잭션이 커밋하거나 어보트할 때까지 이런 잠금을 해제할 수 없다.
• 2단계 커밋을 사용할 때 트랜잭션은 의심스러운 상태에 잇는 동안 내내 잠금을 잡고 있어야 한다.
• 이런 잠금이 유지되는 동안 다른 어떤 트랜잭션도 그 로우를 변경할 수 없어 일을 처리할 수 없다.
• 의심스러운 트랜잭션이 해소될 때까지 성능 이슈가 발생하게 된다.

 

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

• 이론상 코디네이터가 죽은 후 재시작하면 로그로부터 그 상태를 깨끗하게 복구하고 의심스러운 트랜잭션을 해소해야 한다.
• 현실에서는 코디네이터가 어떤 이유 때문이지 그 결과를 결정할 수 없는 고아가 된 의심스러운 트랜잭션이 생길 수 있다.
• 이런 트랜잭션은 자동으로 해소될 수 없어서 잠금을 유지하고 다른 트랜잭션을 차단하면서 데이터베이스에 영원히 남는다.
• 관리자가 수동으로 커밋하거나 롤백할지 결정해야하는 것으로 해결할 수 있다.
• 여러 XA 구현에는 참여자가 코디네이터로부터 확정적 겨정을 얻지 않고 의심스러운 트랜잭션을 어보트하거나 커밋할지를 일방적으로 결정할 수 있도록 하는 경험적 결정(heuristic decision)을 제공한다.
• 경험적 결정은 2단계 커밋의 약속 체계를 위반하기 땜누에 원자성을 깰 수 있다.

 

분산 트랜잭션의 제약

• 코디네이터가 복제되지 않고 단일 장비에서만 실행되면 전체 시스템의 단일 장애점이 된다.
• 여러 서버 사이드 애플리케이션은 모든 영속적인 상태를 데이터베이스에 저장하고 상태 비저장 모드로 개발되지만, 코디네이터가 애플리케이션 서비의 일부가 되면 코디네이터 로그가 시스템 상태의 중대한 부분이 되므로 더 이상 상태 비저장이 아니게 된다.
• XA는 광범위한 시스템과 호환돼야 하므로 최소 공통 분모가 될 필요가 있다. 여러 시스템에 걸친 교착 상태를 감지할 수 없고 SSI와 함께 동작하지 않는다.
• 2PC가 성공적으로 트랜잭션을 커밋하려면 모든 참여자가 응답해야 하는 문제가 있는데, 이는 시스템의 어떤 부분이라도 고장나면 트랜잭션도 실패하게 된다. 따라서 분산 트랜잭션은 장애를 증폭시키는 경향이 있으며 이는 내결함성을 지닌 시스템을 구축하려는 목적에 어긋한다.

 

내결함성을 지닌 합의

• 합의는 여러 노드가 어떤 것에 동의해야 한다는 의미이다.
• 하나 또는 그 이상의 노드들이 값을 제안할 수 있고 합의 알고리즘이 그 값 중 하나를 결정한다.
• 합의 알고리즘 속성
  • 균일한 동의 : 어떤 두 노드도 다르게 결정하지 않는다.
  • 무결성 : 어떤 노드도 두 번 결정하지 않는다.
  • 유효성 : 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다.
  • 종료 : 죽지 않은 모든 노드는 결국 어떤 값을 결정한다.

 

합의 알고리즘과 전체 순서 브로드캐스트

• 합의 알고리즘
  • 뷰스탬프 복제(viewstamped Replication)
  • 팍소스(Paxos)
  • 라프트(Raft)
  • 잽(Zab)
• 전체 순서 브로드캐스트를 하려면 모든 노드에게 메시지가 정확히 한 번, 같은 순서로 전달돼야 한다.
• 합의를 몇 회 하는 것과 동일하다. 각 회마다 노드들은 다음에 보내기 원하는 메시지를 제안하고 전체 순서 상에서 전달될 다음 메시지를 결정한다.
• 전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일하다.(각 합의 결정이 하나의 메시지 전달에 해당)
  • 합의의 동의 속성 때문에 모든 노드는 같은 메시지를 같은 순서로 전달하도록 결정한다.
  • 무결성 속성 때문에 메시지는 중복되지 않는다.
  • 유효성 속성 때문에 메시지는 오염되지 않고 난데없이 조작되지 않는다.
  • 종료 속성 때문에 메시지는 손실되지 않는다.

 

단일 리더 복제와 합의

• 수동으로 리더를 선택
  • 독재자 방식의 합의 알고리즘 사용
  • 한 노드만 쓰기를 받아들이는게 허용되고, 그 노드가 죽으면 시스템은 운영자가 수동으로 다른 노드를 리더로 설정할 때까지 쓰기 불가능
  • 사람의 개입이 필요하므로 합의의 종료 속성을 만족하지 않음
• 자동 리더 선출과 장애 복구
  • 내결함성을 지닌 전체 순서 브로드캐스트에 가까워지고 합의를 해결하는 데도 가까워짐
  • 스플릿 브레인 문제가 존재
  • 리더를 선출하려면 합의가 필요하다.

 

에포크 번호 붙이기와 정족수

• 합의 프로토콜은 모두 내부적으로 어떤 형태로든 리더를 사용하지만 리더가 유일하다고 보장하지 않는다. 대신 더 약한 보장을 할 수 있다.
• 프로토콜들은 에포크 번호(epoch number)를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장한다.
• 리더 선출 투표
  • 선출은 에포크 번호를 증가시킨다(에포크 번호는 전체 순서가 있고 단조 증가한다.)
  • 두가지 다른 에포크에 있는 두 가지 다른 리더 사이에 충돌이 있으면 에포크 번호가 높은 리더가 이긴다.
• 노드의 정족수 투표
  • 리더가 무너가를 결정하도록 허용하기 전에 충돌되는 결정을 할지도 모르는 에포크 번호가 더 높은 다른 리더가 없는지 먼저 확인해야 한다.
  • 리더는 내리려고 하는 모든 결정에 대해 제안된 값을 다른 노드에게 보내서 노드의 정족수가 그 제안을 찬성한다고 응답하기를 기다려야 한다.
  • 노드는 에포크 번호가 더 높은 다른 리더를 알지 못할 때만 제안에 찬성하는 투표를 한다.
• 두 번의 투표가 존재(리더 선출, 리더의 제안)하는데, 두 번의 투표를 하는 정족수가 겹쳐야 한다.
• 제안에 대한 투표가 성공하면 그것에 투표한 노드 중 최소 하나는 가장 최근의 리더 선출에도 참여했어야 한다.
• 제안에 대한 투표를 할 때 에포크 번호가 더 큰 것이 있다고 밝혀 지지 않았다면, 현재 리더는 에포크 번호가 더 높은 리더 선출이 발생하지 않았다고 결론내려 리더십 유지가 가능하다.
• 2PC와 차이점
  • 2PC의 코디네이터는 선출되지 않고 2PC는 모든 참여자로부터 "네" 응답을 받아야 한다.
  • 합의 알고리즘은 노드의 과반수로부터만 투표를 받으면 된다.
  • 합의 알고리즘은 새로운 리더가 선출된 후 노드를 일관적인 상태로 만들어주는 복구 과정을 정의해서 안전성 속성이 항상 만족되도록 보장한다. => 정확성과 내결함성의 핵심

 

합의의 제약

• 제안이 결정되기전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제이다. 비동기식 복제 설정 시 커밋된 데이터는 장애 복구 시 잠재적으로 손실될 수 있다.
• 항상 엄격한 과반수가 동작하기를 요구한다. 노드 1대가 장애를 견디려면 최소 3대의 노드가 필요하고 두 대의 장애를 견디려면 최소 5대의 노드가 필요하다.
• 투표에 참여하는 노드 집합이 고정돼 있다고 가정하며 이는 클러스터에 노르를 그냥 추가하거나 제거할 수 없다는 의미이다.
• 장애 노드를 감지하기 위해 일반적으로 타임아웃에 의존한다. 네트워크 지연의 변동이 심한 환경에서 일시적인 네트워크 문제 때문에 노드가 리더에 장애가 발생했다고 잘못 생각하는 일이 발생할 수 있다.
• 때때로 네트워크 문제에 민감하다.

 

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

• 주키퍼와 etcd
  • 분산 키-값 저장소나 코디네이션과 설정 서비스라고 설명된다.
  • 완전히 메모리 안에 들어올 수 있는 작은 양의 데이터를 보관하도록 설계됐다.
  • 이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제된다.
  • 개별 메시지가 데이터베이스에 쓰기를 나타낸다면 같은 쓰기를 같은 순서로 적용함으로써 복제본들이 서로 일관성을 유지할 수 있다.
• 주키퍼는 구글의 처비(Chubby) 잠금 서비스를 모델로 삼아 전체 순서 브로드캐스트뿐만 아니라 분산 시스템을 구축할 때 유용한 기능 집합도 구현한다.
  • 선형성 원자적 연산: 원자적 compare-and-set 연산을 사용해 잠금 구현
  • 연산의 전체 순서화: 펜싱 토큰
  • 장애 감지
  • 변경 알림

 

작업을 노드에 할당하기

• 주키퍼/처비 모델이 잘 동작하는 예시
  • 여러 개의 프로세스나 서비스가 있고 그 중 하나가 리더나 주 구성요소로 선택돼야 할 때
  • 파티셔닝된 자원이 있고 어떤 파티션을 어느 노드에 할당해야 할지 결정해야 하는 경우
• 매우 많은 노드에서 과반수 투표를 수행하려고 하는 것은 비효율적이다.
• 주키퍼는 고정된 수의 노드에서 실행되고, 이 노드들 사이에서 과반수 투표를 수행하면서 많아질 수 있는 클라이언트를 지원한다.
• 노드들을 코디네이트하는 작업(합의, 연산 순서화, 장애 감시)의 일부를 외부 서비스에 위탁하는 방법을 제공한다.

 

서비스 찾기

• 주키퍼, etcd, 콘술(Consul)은 서비스 찾기, 즉 특정 서비스에 연결하려면 어떤 IP 주소로 접속해야 하는지 알아내는 용도로도 자주 사용된다.
• 서비스 찾기가 합의가 필요한지는 분명하지 않다.

 

멤버십 서비스

• 멤버십 서비스는 클러스터에서 어떤 노드가 현재 활성화된 살아 있는 멤버인지 결정한다.
• 장애 감지를 합의와 연결하면 노드들은 어떤 노드가 살아있는 것으로 여겨져야 하는지 혹은 죽은 겻으로 여겨져야 하는지 동의할 수 있다.
• 합의는 시스템에서 어떤 노드가 현재 멤버십을 구성하는지 동의하는 데 매우 유용하다.