Chapter 9. 일관성과 합의 - Part 2

소개

본 글은 데이터 중심 어플리케이션(마틴 클레프만)으로 스터디하며 해당 책의 내용을 요약 정리한 내용입니다.

https://github.com/ddia-study/ddia-study

GitHub - ddia-study/ddia-study: 데이터 중심 어플리케이션 설계

 

분산 트랜잭션과 합의

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

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

• 리더 선출 : Split brain
• 원자적 커밋 : 모든 노드가 트랜잭션 결과에 동의하게 만들어야 함.

 

원자적 커밋과 2PC

트랜잭션의 결과는 커밋 성공이나 어보트

 

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

단일 노드에서 트랜잭션 커밋은 데이터가 디스크에 지속성 있게 쓰이는 순서에 결정적으로 의존한다.

트랜잭션에 여러 노드가 관여한다면?

모든 노드에 커밋 요청을 보내고 각 노드에서 독립적으로 트랜잭션을 커밋하는 것으로는 충분하지 않다.

어떤 노드에서는 커밋이 성공하고 다른 노드에서는 실패해서 원자성 보장을 위반하기 쉽다.

• 어떤 노드들은 어보트가 필요하지만, 다른 노드들은 성공적으로 커밋될 수 있다.
• 어떤 커밋 요청은 네트워크에서 손실되어 타임아웃 때문에 어보트될 수 있다.
• 어떤 노드들은 커밋 레코드가 완전히 쓰이기 전에 죽어서 복구할 때 롤백될 수 있다.

트랜잭션 커밋은 되돌릴 수 없어야 한다.

보상 트랜잭션(compensating transaction) : 커밋된 트랜잭션의 효과를 나중에 다른 트랜잭션이 취소하는 것.

 

2PC

모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘.

애플리케이션이 커밋할 준비가 되면 coordinator가 1단계를 시작한다.

• 애플리케이션은 분산 트랜잭션을 시작하기 원할 때 coordinator에게 트랜잭션 ID를 요청한다.
• 애플리케이션은 각 참여자에서 단일 노드 트랜잭션을 시작하고 단일 노드 트랜잭션에 전역적으로 유일한 트랜잭션 ID를 붙인다.
• 각 노드에 준비 요청을 보내서 커밋할 수 있는지 "준비 요청"을 물어본다.
  • 참가자는 트랜잭션을 커밋할 수 있는지 확인한다.
  • 모두 네라고 응답했으면 coordinator는 커밋할지 안 할지 최종적 결정을 한다. 추후 죽는 경우에 어떻게 결정했는지 알 수 있도록 그 결정을 디스크에 있는 트랜잭션 로그에 기록해야 한다. -> 커밋 포인트
  • 커밋 포인트가 남으면 요청이 실패하거나 타임아웃이 될 때 성공할 때까지 영원히 재시도해야 한다.
  • 아니요라고 한 노드라도 응답하면 2단계에서 모든 노드에 어보트를 보낸다.

 

coordinator 장애

coordinator가 준비 요청을 보내고 나서 "네"에 투표한 다음 장애가 났다면, 참여자는 기다리기만 해야 한다.

이 상태에 있는 참여자의 트랜잭션을 in doubt 혹은 uncertain이라고 한다.

2PC가 완료할 수 있는 유일한 방법은 코디네이터가 복구되기를 기다리는 것뿐이다.

 

3PC

이론상으로는 노드에 장애가 나도 멈추지 않도록 원자적 커밋 프로토콜을 non-blocking하게 만들 수 있다.

기약 없는 네트워크 지연과 프로세스 중단이 있는 대부분 실용적 시스템에서 3PC는 원자성을 보장하지 못한다.

 

현실의 분산 트랜잭션

특정 분산 트랜잭션 => ex. MySQL의 경우, 10배 이상 느림.

두 종류의 분산 트랜잭션

• 데이터베이스 내부 분산 트랜잭션 : 분산 DB에서 DB 노드 간 트랜잭션 지원 -> 아래의 방법보다 쉽고, 흔히 매우 잘 동작한다.
• Heterogeneous 트랜잭션 : 서로 다른 벤더의 DB일 수도, 메시지 브로커처럼 비데이터베이스 시스템일 수도 있다.

 

정확히 한 번 메시지 처리

Heterogeneous 트랜잭션에서, 메시지 확인과 데이터베이스 쓰기를 단일 트랜잭션에서 원자적으로 커밋함으로써 구현할 수 있다.

메시지 전달이나 DB 트랜잭션 중 하나가 실패하면 둘 다 어보트되고 메시지 브로커는 나중에 메시지를 안전하게 재전달할 수 있다.

그러므로 메시지와 그 처리 과정의 side effect를 원자적으로 커밋함으로써 effectively exactly once 처리되도록 보장할 수 있다.

그렇지만 이런 분산 트랜잭션은 트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능하다.

 

XA Transaction(eXtended Architecture)

heterogeneus 기술에 걸친 2단계 커밋을 구현하는 표준.

XA는 네트워크 프로토콜이 아니라, 트랜잭션 코디네이터와 연결되는 인터페이스를 제공하는 API일 뿐이다.

드라이버가 XA를 지원한다는 것은 연산이 분산 트랜잭션의 일부가 돼야 하는지 알아내기 위해 XA API를 호출한다는 것을 뜻한다.

그리고 만약 그렇다면 드라이버는 DB 서버로 필요한 정보를 보낸다.

트랜잭션 코디네이터는 XA API를 구현한다.

 

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

트랜잭션이 의심스러운 상태에 빠지는 것이 왜 문제일까?

문제는 잠금과 관련이 있다. 데이터베이스 트랜잭션은 보통 더티 쓰기를 막기 위해 그들이 변경한 로우에 로우 수준의 독점적인 잠금을 획득한다.

추가로 직렬성 격리를 원한다면 2단계 잠금을 사용하는 데이터베이스는 트랜잭션에서 읽은 로우에 공유 잠금도 획득해야 한다.

데이터베이스는 트랜잭션이 커밋하거나 어보트할 때까지 이런 잠금을 해제할 수 없다.

그러므로 2단계 커밋을 사용할 때 트랜잭션은 의심스러운 상태에 있는 동안 내내 잠금을 잡고 있어야 한다.

 

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

이론상으로는 코디네이터가 죽은 후 재시작하면 로그로부터 그 상태를 깨끗하게 복구하고 의심스러운 트랜잭션을 해소해야 한다.

그러나 현실에서는 orphaned 의심스러운 트랜잭션, 즉 코디네이터가 어떤 이유 때문인지 그 결과를 결정할 수 없는 트랜잭션이 생길 수 있다.

이런 트랜잭션은 자동으로 해소될 수 없어서 잠금을 유지하고 다른 트랜잭션을 차단하면서 데이터베이스에 영원히 남는다.

여기서 빠져나가는 유일한 방법은 관리자가 수동으로 트랜잭션을 커밋하거나 롤백할지 결정하는 것뿐이다.

여러 XA 구현에는 참여자가 코디네이터로부터 확정적 결정을 얻지 않고 의심스러운 트랜잭션을 어보트하거나 커밋할지를 일방적으로 결정할 수 있도록 하는 경험적 결정(heuristic decision)이라고 부르는 비상 탈출구가 있다.

 

분산 트랜잭션의 제약

XA 트랜잭션은 여러 참여 데이터 시스템이 서로 일관성을 유지하게 하는 실제적이고 중요한 문제를 해결해 주지만 지금까지 본 것처럼 XA 트랜잭션도 중요한 운영상 문제를 가져온다.

특히 핵심 구현은 트랜잭션 코디네이터 자체가 트랜잭션 결과를 저장할 수 있는 일종의 DB여야 한다는 점이고 따라서 다른 중요한 DB와 동일하게 신경 써서 접근해야 한다.

• 코디네이터가 복제되지 않은 경우 SPOF가 될 수 있다.
• 코디네이터의 로그가 지속적인 시스템 상태의 중대한 부분이 된다. 코디네이터 로그는 죽은 후에 의심스러운 트랜잭션을 복구하기 위해 필요하므로 DB 자체만큼 중요하다.
• XA는 광범위한 데이터 시스템과 호환돼야 하므로 최소 공통분모가 될 필요가 있다.
• 결과적으로 시스템의 어떤 부분이라도 고장 나면 트랜잭션도 실패한다. 따라서 분산 트랜잭션은 장애를 증폭시키는 경향이 있다.

 

내결함성을 지닌 합의

합의 문제 : 하나 또는 그 이상의 노드들이 값을 제안할 수 있고 합의 알고리즘이 그 값 중 하나를 결정한다.

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

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

 

내결함성이 상관없다면 처음 세 개의 속성을 만족시키는 것은 쉽다.

그냥 한 노드를 "독재자"로 하드 코딩하고 그 노드가 모든 결정을 내리게 하면 된다.

종료 속성은 내결함성의 아이디어를 형식화한다. 어떤 노드들에 장애가 나더라도 다른 노드들은 여전히 결정을 내려야 한다.

합의 시스템 모델은 노드가 "죽으면" 그 노드가 갑자기 사라져서 결코 돌아오지 않는다고 가정한다.

이 시스템 모델에서 노드가 복구되기를 기다리는 알고리즘은 어떤 것이라도 종료 속성을 만족할 수 없다.

물론 모든 노드가 죽어서 아무 노드도 실행 중이 아니라면 어떤 알고리즘을 쓰든지 아무것도 결정할 수 없다.

그러나 대부분의 합의 구현은 과반수의 노드에 장애가 나거나 심각한 네트워크 문제가 있더라도 안전성 속성(동의, 무결성, 유효성)을 항상 만족한다.

 

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

대다수의 합의 알고리즘은 값의 sequence에 대해 결정해서 전체 순서 브로드캐스트 알고리즘을 만든다.

각 회마다 노드들은 다음에 보내기 원하는 메시지를 제안하고 전체 순서 상에서 전달될 다음 메시지를 결정한다.

그래서 전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일하다.

 

단일 리더 복제와 합의

리더를 선출하려면 먼저 리더가 필요해 보이고, 합의를 해결하려면 먼저 합의를 해결해야 할 것 같다. 어떻게 해결할까?

 

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

합의 프로토콜(뷰스탬프 복제, 팍소스, 라프트, 잽)은 모두 내부적으로 어떤 형태로든 리더를 사용하지만 리더가 유일하다고 보장하지는 않는다.

대신 더 약한 보장을 하는데, 이 프로토콜들은 epoch number를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장한다.

리더가 죽었다고 생각될 때마다 새 노드를 선출하기 위해 노드 사이에서 투표가 시작된다.

이 선출은 에포크 번호를 증가시키며 따라서 에포크 번호는 전체 순서가 있고 단조 증가한다.

두 가지 다른 에포크에 있는 두 가지 다른 리더 사이에 충돌이 있으면 에포크 번호가 높은 리더가 이긴다.

리더는 내리려고 하는 모든 결정에 대해 제안된 값을 다른 노드에게 보내서 노드의 정족수가 제안을 찬성한다고 응답하기를 기다려야 한다.

즉 두 번의 투표가 있다.

• 리더 선출
• 리더의 제안에 대한 투표

 

중요한 것은 제안에 대한 투표가 성공하면 그 제안에 투표한 노드 중 최소 하나는 가장 최근의 리더 선출에도 참여했어야 한다.

따라서 제안에 대한 투표를 할 때 에포크 번호가 더 큰 것이 있다고 밝혀지지 않았다면 현재 리더는 에포크 번호가 더 높은 리더 선출이 발생하지 않았다고 결론을 내릴 수 있다.

 

합의의 제약

합의 알고리즘 : 안전성 속성을 가져오고, 내결함성을 유지하지만 다양한 이슈가 있다.

• 성능
• 엄격한 과반수 동작으로 인한 비용
• 네트워크 지연이 심한 경우 리더 선출에 시간을 더 쓸 수 있음
• 그 외 (라프트 예시)

 

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

주키퍼 & etcd는 전부 메모리 안에 들어올 수 있는 작은 양의 데이터를 보관하도록 설계됐다. (지속성을 위해 디스크에 쓰기는 한다.)

이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제된다.

개별 메시지가 데이터베이스에 쓰기를 나타낸다면 같은 쓰기를 같은 순서로 적용함으로써 복제본들이 서로 일관성을 유지할 수 있다.

주키퍼는 유용한 기능 집합도 제공한다.

• 선형적 원자적 연산
• 연산의 전체 순서화
• 장애 감지
• 변경 알림

 

작업을 노드에 할당하기

주키퍼 예시

• 여러 개의 서비스 중 하나가 리더나 주 구성요소로 선택돼야 할 때
• 파티셔닝 된 자원이 있고 어떤 파티션을 어느 노드에 할당해야 할지 결정해야 할 때. => 결함으로부터 자동 복구가 가능하긴 하지만 대부분 실패함

 

서비스 찾기

주키퍼, etcd, Consul => Service Discovery로 활용 가능

서비스 디스커버리는 합의가 필요한가? => 굳이... (DNS, 다층 캐시)

합의 시스템이 누가 리더인지 안다면 다른 서비스들이 리더가 누구인지 찾는 데 사용.