분산 트랜잭션과 합의 - 내결함성

내결함성을 지닌 합의

• 단순하게 말해 합의란 어떤 노드(들)이 값을 제안하며, 합의 알고리즘이 그 값 중 하나를 결정하는 것. 이를 위해 달성해야 할 속성은 다음과 같음

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

• 균일한 동의와 무결성은 합의의 핵심 아이디어

• 유효성은 뻔한 해결책을 배제하기 위해 존재(ex. 무엇을 제안하든지 간에 널값으로 값을 결정하는 알고리즘, 이 알고리즘은 균일한 동의와 무결성을 만족함)

• 종료를 내결함성을 만족시키기 위해 존재(ex. 만일 독재 노드가 모든 결정을 내리면, 위 세 가지 조건은 만족하지만 내결함성을 보장하지는 못함)

• 종료 조건에서 시스템은 어떤 노드가 죽으면 그 노드가 결코 돌아오지 않는다고 가정함. 즉, 앞서 살펴본 2PC는 종료에 대한 요구사항을 만족하지 않음

• 또한 종료 조건은 죽거나 연결할 수 없는 노드 대수가 절반 미만이라는(과반수 정족수)에 종속적으로 동작함

• 다만, 과반수 이상의 노드에 장애가 나거나 심각한 네트워크 문제가 있더라도 안전성 속성(동의, 무결성, 유효성)은 항상 만족해야 함. 그렇게 함으로써 시스템이 요청을 처리할 수는 없지만, 유효하지 않은 결정을 내려서 합의 시스템을 오염시키는 것은 방지할 수 있음

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

• 내결함성을 지닌 합의 알고리즘 중 가장 널리 알려진 것은 뷰스탬프 복제(Viewstamped Replication, VSR), 팍소스(Paxos), 라프트(Raft), 잽(Zab) 등이 있음

• 이 책에선 이러한 알고리즘에 대한 자세한 설명을 보기보다는 공통적으로 적용되는 고수준의 아이디어를 살펴볼 것

• 다만, 이 알고리즘 중 대다수는 실제로 앞서 설명된 형식적 모델(동의, 무결성, 유효성, 종료)를 직접 사용하지 않음. 대신 값의 순차열(sequence)에 대해 결정해서 전체 순서 브로드캐스트 알고리즘을 만듦

• 전체 순서 브로드캐스트는 앞서 살펴봤듯이, 신뢰성 있는 전달과 전체 순서가 정해진 전달을 만족시키는 노드 사이에 메시지를 교환하는 프로토콜임

• 이를 위해선 모든 노드에게 메시지가 정확히 한 번, 같은 순서로 전달돼어야 함

• 다시 말해 전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일함(각 합의 결정이 하나의 메시지 전달에 해당)

  • 합의의 동의 속성으로 모든 노드는 같은 메시지를 같은 순서로 전달하도록 결정

  • 무결성 속성으로 메시지는 중복되지 않음

  • 유효성 속성으로 메시지는 오염되지 않고 조작되지 않음

  • 종료 속성으로 메시지는 손실되지 않음

단일 리더 복제와 합의

• 단일 리더 복제는 모든 쓰기를 리더에게 전달하고 쓰기를 같은 순서로 팔로워에 적용함

• 여기서 한 가지 의문이 들 수 있는 데, 단일 리더 복제는 본질적으로 전체 순서 브로드캐스트인 것으로 보이는데, 왜 합의에 대한 걱정은 할 필요가 없었을까?

• 그 답은 리더를 어떻게 선택하느냐에 달라짐. 리더를 사람이 수동으로 선택해서 설정한다면 본질적으로 독재자 방식의 합의 알고리즘을 사용하는 것과 마찬가지이며, 리더 노드가 죽을면 시스템은 운영자가 수동으로 다른 리더를 선출해줘야 함

• 여기서 또 하나의 의문이 들 수 있음. 리더를 선출하기 위해선 합의가 필요해짐. 하지만 방금 말했듯 합의 알고리즘들이 실제로는 전체 순서 브로드캐스트 알고리즘이라면 전체 순서 브로드캐스트는 단일 리더 복제와 같고 단일 리더 복제는 리더가 필요하고... 즉, 리더를 선출하려면 먼저 리더가 필요한 것처럼 보임. 합의를 해결하려면 먼저 합의를 해결해야 한다?

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

• 합의 프로토콜은 모두 내부적으로 리더를 사용하지만, 리더가 유일하다고는 보장하지 않으며 조금 더 약한 보장을 함

• 이들은 에포크 번호(epoch number, 팍소스에서는 투표 번호, 뷰스탬프에서는 뷰 번호, 라프트에서는 텀 번호)를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장함

• 현재 리더가 죽었다고 생각되면, 새 리더를 선출하기 위한 투표가 진행됨. 이 선출은 에포크 번호를 증가시키며 진행되고 따라서 에포크 번호는 전체 순서가 있고 단조 증가함

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

  • 이 때 리더들은 노드의 정속수로부터 투표를 받으며, 노드들은 에포크 번호가 더 높은 다른 리더를 알지 못할 때만 제안에 찬성하는 투표를 할 수 있음

• 따라서 투표는 총 두 번(1. 리더 선출, 2. 리더 제안에 투표) 일어남

  • 이 때 2번 투표를 위해서는 1번 투표에 참여한 노드가 최소 하나 이상 포함되어야 함

합의의 제약

• 합의의 장점

  • 불확실한 시스템에 구체적인 안전성 속성(동의, 무결성, 유효성)을 가져옴

  • 그러면서도 내결함성을 유지

  • 전체 순서 브로드캐스트를 제공함으로서 내결함성 있는 방식으로 선형성 원자적 연산을 구현할 수 있음

• 제약 조건

  • 노드가 리더의 제안에 투표하는 과정은 일종의 동기식 복제임

  • 이런 설정에서는 커밋된 데이터가 장애 복구 시 잠재적으로 손실될 수 있음. 다만 많은 사람들이 더 나은 성능을 위해 이 위험을 받아들이고 있는 상황

  • 합의 시스템은 항상 엄격한 과반수가 동작하기를 요구함. 즉, 1대의 장애를 견디기 위해선 최소 3대의 노드가 필요하다는 것을 의미하며, 2대의 장애를 견디기 위해선 최소 5대의 노드가 필요함

  • 대부분의 합의 알고리즘은 투표에 참여하는 노드 집합이 고정되어 있다고 가정하기에 클러스터에 노드를 그냥 추가하거나 제거할 수는 없음(동적 멤버십(dynamic membership)을 통해 구현되지만, 그냥 추가하는 것과 이해하기 어려운 동적 멤버십 알고리즘을 사용하는 것에는 차이가 있음)

  • 합의 시스템은 장애 노드 감지를 위해 타임아웃에 의존함. 안전성 속성을 해치지는 않지만, 경우에 따라 끔찍한 성능을 유발할 수 있음

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

• 주키퍼나 etcd 같은 프로젝트는 종종 "분산 키-값 저장소"나 "코디네이션과 설정 서비스"라고 설명됨. 주어진 키에 대한 값을 읽거나 쓸 수 있고 키에 대해 순회할 수 있음

• 기본적으로 데이터베이스라면, 무엇이 이들을 다른 종류의 데이터베이와 다르게 만들까?

• 기본적으로 주키퍼와 etcd는 완전히 메모링 안에 들어올 수 있는 작은 양의 데이터를 보관하도록 설계됨(지속성을 위해 디스크에 쓰기는 함)

• 이 데이터들은 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제됨

• 또한 전체 순서 브로드캐스트 뿐만 아니라, 분산 시스템을 위한 다양한 기능 집합도 구현되어 있음

  • 선형성 원자적 연산

    • 원자적 compare-and-set 연산을 사용해 잠금을 구현할 수 있음. 분산 잠금은 보통 장애가 난 경우 해제될 수 있게 만료시간이 있는 임차권(lease)로 구현됨

  • 연산의 전체 순서화

    • 어떤 자원이 잠금이나 임차권으로 보호될 때는 클라이언트들이 서로 충돌하는 것을 막기 위해 펜싱 토큰이 필요함. 주키퍼는 모든 연산에 전체 순서를 정하고 각 연산에 단조 증가하는 트랜잭션 ID(zxid)와 번전 번호(cversion)을 할당해서 이를 제공함

  • 장애 감지

    • 클라이언트는 주키퍼 서버에 수명이 긴 세션을 유지하며, 주기적으로 서로 하트비트를 교환해서 장애를 탐지함

  • 변경 알림

    • 클라이언트는 다른 클라이언트가 생성한 잠금과 값을 읽는 것뿐만 아니라, 변경사항이 있는지도 감지할 수 있음. 즉, 다른 클라이언트가 언제 클러스터에 합류했는지, 어떤 클라이언트에 장애가 발생했는지 알 수 있음. 이것은 알림을 구독하는 형태로 구현됨

애플리케이션이 처음에는 단일 노드에서 실행될 수 있지만, 결국 수 천대의 노드로 늘어날 수도 있음
수 천대의 노드에서 과반수 투표를 진행한다는 것은 매우 비효율적임
주키퍼는 보통 셋이나 다섯의 고정된 수의 노드에서 실행되고 이 노드들 사이에서 과반수 투표를 진행함
따라서 주키퍼는 노드들을 코디네이트하는 작업(합의, 연산 순서화, 장애 감지)의 일부를 외부 서비스에 위탁하는 방법을 제공함