TIL

09장 일관성과 합의

• 분산 시스템에서의 문제를 해결하는 방법
  • 전체 서비스가 실패하도록 두고 오류 메시지를 보여주기
  • 위 해결이 싫다면 결함을 견뎌낼(tolerating) 수 있도록 내결함성 구축하기

살아 있지만 틀린 게 나은가, 올바르지만 죽은 게 나은가?

• 내결함성이 지닌 분산 시스템이 극복해야 하는 것
  • 네트워크 상의 패킷 손실
  • 패킷 순서의 변경 및 중복
  • 네트워크 지연
  • 노드 장애
• 내결함성을 지닌 시스템을 구축하려면 유용한 보장을 해주는 범용 추상화를 찾고 애플리케이션에서 이 보장에 의존하게 해야 한다.
  • ex) 트랜잭션 추상화를 통해 충돌, 경쟁 조건, 디스크 장애로부터 애플리케이션이 신경쓰지 않게 해줌
  • 분산 시스템에서 중요한 추상화 중 하나는 바로 ‘합의’다.

일관성 보장

• 복제 데이터베이스는 대부분 최소한 최종적 일관성을 제공한다.
  • DB에 쓰기를 멈추고 불특정 시간 동안 기다린다면 결국 모든 읽기 요청이 같은 값을 반환한다는 뜻
  • 매우 약한 보장이기도 한데 언제 복제본에 값들이 수렴될지에 대해선 불확실하다.
  • 최종적 일관성의 에지 케이스는 시스템에 결함이 있거나 동시성이 높을 때만 분명히 드러난다.
• 이에 반해 강한 일관성 모델도 존재하는데 그 중 하나가 바로 선형성(linearizability)이다.

선형성

• 선형성
  • 정확한 정의는 매우 미묘하다.
  • 기본 아이디어는 시스템에 데이터 복사본이 하나만 있고 모든 연산은 원자적인 것처럼 보이게 만드는 것
• 선형성 시스템에선 클라이언트가 쓰기를 완료하면 데이터베이스를 읽는 모든 클라이언트는 그 값을 바로 볼 수 있어야 한다.
  • 선형성은 다시 말해 최신성 보장(recency guarangee)다.
  • 데이터 복사본이 하나만 있다는 환상을 유지하는 것은 뒤쳐진 캐시나 복제본에서 나온 값이 아니라고 보장해준다는 뜻

시스템에 선형성을 부여하는 것은 무엇인가?

• 여러 클라이언트가 동시에 같은 키를 읽고 쓴다고 가정했을 때 쓰기 연산과 시간이 겹치는 읽기 연산은 이전 값을 반환할 수도, 새로운 값을 반환할 수 도 있다.
  • 읽기 연산이 처리되는 시점에 쓰기의 영향을 받았는지 알 수 없기 때문
  • 하지만 이러한 현상은 ‘데이터의 단일 복사본’을 모방하는 시스템에 기대하는 바는 아니다.
• 시스템이 선형적이려면 한 클라이언트의 읽기가 새로운 값을 반환하면 이후의 모든 읽기 또한 새로운 값을 반환해야 한다.
  • 심지어 쓰기 연산이 아직 완료되지 않았더라도 말이다.
• 선형성을 만족하려면 모든 연산들이 항상 시간순으로 진행되어야 하고 결코 뒤로 가서는 안 된다.

선형성에 기대기

• 시스템이 선형적으로 동작하려면 요구되는 몇 가지 영역이 있다.
• 잠금과 리더 선출
  • 단일 리더 복제를 사용하는 것처럼 되어야 하기에 스플릿 브레인 현상을 방지해야 한다.
  • 그러려면 리더 선출 시 잠금을 사용할 필요가 있다.
  • 분산 잠금과 리더 선출을 위해 아파치 주키퍼 등의 코디네이션 서비스가 주로 이용된다.
• 제약 조건과 유일성 보장
  • 유일성 제약 조건은 데이터베이스에서 흔하다. ex) 이메일 주소는 사용자 당 유일해야 함
  • 데이터 기록 시 유일성을 강제하려면 선형성이 필요하다.
  • 실제 애플리케이션에서 때때로 이러한 제약을 느슨하게 다룰 때도 있다.
    • ex) 항공기 좌석 예매에서 좌석이 초과되었다면 고객 불편에 대한 보상을 해줄 수 있다.
  • 관계형 저장소에서 외래 키나 속성 제약 조건 등은 선형성을 요구하지 않고도 구현할 수 있다.
• 채널 간 타이밍 의존성
  • 선형성 위반은 시스템에 부가적인 통신 채널이 있으면 발견이 쉬워진다.
  • 선형성의 최신성 보장이 없으면 두 채널 사이에 경쟁 조건이 발생할 수 있다.
    • 웹 서버에서 이미지를 파일 저장소에 업로드 후 웹서버가 메시지 큐를 통해 이미지 크기 변경 모듈로 이미지 크기 리사이징을 시키는 경우
    • 이미지 변경 모듈이 메시지 큐로부터 요청을 받고 파일 저장소에서 리사이징할 이미지를 찾을 때 이미지의 과거 버전을 볼 수도, 아무것도 보지 못할 수도 있다.
  • 부가적인 통신 채널을 제어한다면 복잡성이 추가되겠지만 강한 일관성을 보장할 수 있다.

선형성 시스템 구현하기

• 선형성 구현을 간단하게 하는 방법은 정말 데이터 복사본을 하나만 사용하는 것이다.
• 하지만 단일 노드 시스템은 장애에 취약하기에 복제를 사용할 수밖에 없다.
• 복제 방식에 따른 선형성 고려
  • 단일 리더 복제 - 선형적이 될 가능성이 있음
    • 리더나 동기식으로 갱신된 팔로워에서의 읽기는 선형적일 가능성이 있다.
    • 하지만 모든 단일 리더 데이터베이스가 선형적인 것은 아니다.
    • 설계 때문일 수도, 스냅숏 격리나 동시성 버그 때문일 수도 있다.
  • 합의 알고리즘 - 선형적
    • 합의 프로토콜엔 스플릿 브레인과 복제본이 뒤쳐지는 문제를 막을 수 있다.
  • 다중 리더 복제 - 비선형적
    • 여러 노드에서 동시에 쓰기를 처리하고 비동기로 다른 노드에 복제하기 때문
  • 리더 없는 복제 - 아마도 비선형적
    • 정족수 읽기와 쓰기를 통해 엄격한 일관성을 달성할 수 있다고 하지만 정족수 설정에 따라 상이하기위 완전한 진실은 아니다.
    • 느슨한 정족수도 선형성의 가능성을 떨어뜨린다.
• 다이나모 스타일 모델(리더 없는 복제)에서 엄격한 정족수를 사용하더라도 네트워크 지연 변동이 심하면 경쟁 조건이 생길 수 있다.
  • 쓰기에 성공해야 하는 w개를 모두 만족하더라도 각 복제본에 쓰기를 반영하는 시간에 간격이 크다면 r개의 복제본으로부터 읽기 요청 시 타이밍이 따라 다른 결과를 받을 수 있다.
  • 다이나모 스타일에선 선형성을 제공하지 않는다고 보는 게 가장 안전

선형성의 비용

• 다중 리더 복제의 경우 네트워크가 단절되도 각 데이터센터는 정상 동작한다.
  • 각 데이터센터에 리더가 존재하기 때문
  • 쓰기 데이터는 단지 큐에 쌓였다가 네트워크 복구 시 다른 데이터센터로 전달되면 된다.
• 단일 리더 복제의 경우 네트워크가 끊기면 리더 없는 데이터센터는 동작할 수 없다.
  • 단일 리더에서는 모든 쓰기와 선형성 읽기는 리더로 보내져야 한다.
  • 팔로워 데이터센터로 접속한 클라이언트는 네트워크가 끊겨있으면 아무것도 할 수가 없다.
• 애플리케이션이 선형성을 요구하느나에 따라 동작이 아래처럼 달라진다.
  • 애플리케이션에서 선형성을 요구하는 경우 다른 복제 서버와 네트워크가 끊기면 문제가 고쳐질 때까지 오류를 반환해야 한다. (즉 가용성이 없다.)
  • 애플리케이션이 선형성을 요구하지 않는다면 복제 서버 간 연결이 끊기더라도 독립적으로 요청을 처리하면 된다. (가용성이 있지만 선형성이 없다.)
  • 즉 선형성이 필요 없다면 네트워크 문제에 더 강인하고 이를 CAP 정리라고 한다.
• CAP 정리
  • 보통 일관성(Consistency), 가용성(Availability), 분단 내성(Partition tolerance) 세 개 중 두 개만 만족시킬 수 있다는 정리
  • 하지만 네트워크 분단은 발생할 수밖에 없는 결함이다.
    • 네트워크 분단이 없다고 단정할 수 있다면 일관성, 가용성 둘 다 지킬 수 있다.
  • 따라서 CAP는 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 선택하라는 의미로 보는게 좋다.
  • 이 외에도 CAP 논의에서 ‘가용성’에 대한 모순된 정의가 존재하고 많은 오해와 혼란이 있기에 CAP는 시스템을 잘 이해하는 데 도움이 되지 않는다.
• 선형성과 네트워크 지연
  • 현실에서 선형적인 시스템은 논랄 만큼 드물다.
    • 최신 다중코어 CPU의 램조차 선형적이지 않음
    • 좋은 성능을 위해 CPU 코어가 저마다 메모리 캐시와 저장 버퍼를 갖기 때문
  • 선형성 보장을 제공하지 않기를 택한 여러 분산 데이터베이스도 마찬가지다.
    • 주로 성능을 향상시키기 위해 선형성을 포기
  • 선형성을 제공하는 매우 빠른 알고리즘은 없지만 완화된 일관성 모델은 훨씬 빠를 수 있다.

순서화 보장

• 선형성 정의를 다시 말하면 연산들이 잘 정의된 순서대로 실행된다는 것을 암시한다.
• 또한 순서화, 선형성, 합의 사이에는 깊은 연결 관계가 있다.
  • 단일 리더 복제에서 리더의 주 목적은 쓰기 순서를 결정하는 것
  • 트랜잭션에서 직렬성은 연산들이 어떤 일련 순서에 따라 실행되는 것처럼 동작하도록 보장하는 것과 관련이 있다.
  • 분산 시스템에서 타임스탬프와 시계 사용은 무질서한 세상에 질서를 부여하려는 시도

순서화와 인과성

• 전체 순서(total ordered)와 부분 순서(partially ordered)
  • 전체 순서란 어떤 두 요소가 있으면 항상 어떤 것이 더 크고 작은지 말할 수 있다.
    • ex) 5와 13중 13이 더 크다고 말할 수 있다.
  • 하지만 수학적 집합은 전체 순서를 정할 수 없고 부분적으로 순서가 정해진다.
    • ex {a, b}가 {b, c}보다 클까?
    • 어떤 경우엔 한 집합이 다른 집합보다 크지만 다른 경우에는 비교 불가능하다.
  • 전체 순서와 부분 순서는 데이터베이스 일관성 모델에 반영된다.
    • 선형적 시스템에선 연산의 전체 순서를 정할 수 있다.
      • 선형적 데이터 스토어에는 동시적 연산이 없고 모든 연산은 하나의 타임라인에 따라 순서가 정해져 있다.
    • 인과성은 전체 순서가 아닌 부분 순서를 정의하는데 이는 연산들이 서로에 대해 순서를 정할 수 있지만 어떤 연산들은 비교할 수 없기 때문이다.
      • 두 이벤트에 인과 관계가 있다면 순서가 있지만 어떤 이벤트들은 인과 관계가 없다.
      • 심지어 두 연산 중 어떤 것도 다른 것보다 먼저 실행되지 않았다면 두 연산이 동시적이라고 말한다.
• 선형성은 인과적 일관성보다 강하다. (선형성이 인과성을 내포)
  • 어떤 시스템이 선형적이라면 인과성도 올바르게 유지한다.
  • 선형성이 인과성을 포함하는게 매력적이겠지만 시스템의 선형성은 높은 비용을 요구하고 가용성을 해친다.
  • 하지만 많은 경우 시스템이 진짜로 필요한 것은 선형성이 아닌 인과적 일관성이고 이는 더 효율적으로 구현될 수 있다.
• 인과적 의존성 담기
  • 비선형적 시스템이 인과성을 유지하려면 어떤 연산이 다른 어떤 연산보다 먼저 실행됐는지 알아야 한다.
    • 이는 부분 순서다.
    • 동시 실행 연산은 상관 없지만 인과가 있는 연산은 순서를 지키며 처리되어야 한다.
  • 인과적 의존성을 결정하려면 시스템의 노드에 관한 ‘지식’을 기술해야 한다.
    • ex) 같은 키에 대한 동시 쓰기 검출
    • ex) 데이터의 어떤 버전을 읽었는지 알기

일련번호 순서화

• 일련번호나 타임스탬프를 사용해서 이벤트 순서를 정할 수 있다.
  • 타임스탬프는 일 기준 시계가 아닌 논리적 시계에서 얻어도 된다.
• 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다.
  • 인과적으로 먼저 실행됐다면 전체 순서에서도 먼저다.
• 단일 리더 복제 데이터베이스에선 복제 로그가 전체 순서를 정의한다.
  • 리더는 연산마다 단조 증가 일련번호를 할당
  • 팔로워가 복제 로그에 나오는 순서대로 쓰기를 적용하면 팔로워 상태는 언제나 인과성에 일관적이다.
• 비인과적 일련번호 생성기
  • 단일 리더가 아니라면 연산에 사용할 일련번호가 겹칠 수도 있기에 다양한 방안이 사용된다.
    • 각 노드가 자신만의 독립적인 일련번호 집합 생성 (ex. 한 노드는 홀수만, 한 노드는 짝수만)
    • 해상도가 충분히 높은 타임스탬프
    • 각 노드 당 일련번호 블록을 미리 할당
  • 하지만 이렇게 생성한 일련번호는 인과성에 일관적이지 않아 연산들의 순서를 올바르게 담지 못한다.
• 램포트 타임스탬프
  • 인과성에 일관적인 일련번호를 생성하는 방법
  • 각 노드는 고유 식별자를 갖고 처리한 연산 개수를 카운터로 유지한다.
  • (카운터, 노드ID) 쌍의 형태고 카운터 값이 같으면 노드 ID가 더 큰 것이 타임스탬프가 크다.
  • 모든 노드와 클라이언트는 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다.
• 인과성에 일관적인 타임스탬프의 문제점은 연산의 전체 순서가 모든 연산을 모은 후에야 드러난다는 것이다.
  • 어떤 연산을 생성했지만 그것이 무엇인지 아직 알 수 없다면 연산 최종 순서를 만들 수 없다.
  • 만약 분산 환경에서 유일성 제약 조건을 구현하려면 전체 순서가 있는 것만으로는 충분치 않다.
  • 언제 전체 순서가 확정되는지 알아야 한다.
    • 유일성 제약이 있는 값을 생성하는 연산이 있고, 전체 순서상 그 연산보다 앞서는, 동일한 유일성 제약 값을 생성하는 연산을 다른 어떤 노드도 끼워 넣을 수 없다면 그 연산을 성공 처리해도 안전하다.

전체 순서 브로드캐스트

• 단일 리더 복제에선 한 노드를 리더로 선택하고 단일 CPU 코어에서 모든 연산을 차례대로 배열해 연산 전체 순서를 정한다.
• 분산 시스템에선 모든 노드에서 연산 전체 순서가 동일하도록 합의하기가 까다롭다.
  • 타임스탬프 순서화로 유일성 제약 조건을 구현하기 어려움
• 전체 순서 브로드캐스트(total order broadcast), 원자적 브로드캐스트(atomic broadcast)
  • 분산 시스템에서 전체 순서를 정하기 위해 노드 사이 메시지를 교환하는 프로토콜
  • 신뢰성 있는 전달 - 어떤 메시지도 손실되지 않고 한 노드에 전달되면 모든 노드에 전달된다.
  • 전체 순서가 정해진 전달 - 메시지는 모든 노드에 같은 순서로 전달된다.
• 전체 순서 브로드캐스트의 사용
  • 주키퍼나 etcd 같은 합의 서비스에선 전체 순서 브로드캐스트를 실제로 구현한다.
  • 전체 순서 브로드캐스트를 통해 모든 복제 서버가 같은 쓰기 연산을 순서대로 처리하면 복제 서버들은 일관성 있는 상태를 유지하게 된다. (상태 기계 복제)
  • 직렬성 트랜잭션을 구현하는 데도 사용할 수 있다.
  • 펜싱 토큰 기반 잠금 서비스 구현에도 유용하다.
• 전체 순서 브로드캐스트로 선형성 저장소 구현
  • 전체 순서 브로드캐스트는 선형성과 완전 똑같진 않지만 밀접한 관계가 있다.
  • 전체 순서 브로드캐스트는 비동기식이라 고정된 순서로 메시지가 전달되지만 언제 전달될진 보장되지 않는다.
    • 어떤 수신자는 뒤쳐질 수 있다.
  • 전체 순서 브로드캐스트를 추가 전용 로그로 사용해 선형성 compare-and-set 연산을 통해 유일성 제약을 아래와 같이 구현할 수 있다.
    • 메시지를 로그에 추가해 점유하기 원하는 유일값을 시험적으로 가리킴
    • 로그를 읽고, 추가한 메시지가 되돌아오기를 기다림
    • 원하는 값을 점유하려고 있는 메시지가 있는지 확인한다. 원하는 유일 값에 해당하는 첫 번째 메시지가 자신의 메시지라면 성공, 다른 사용자가 보낸 메시지라면 연산을 어보트시킨다.
  • 이는 선형성 쓰기를 보장하지만 선형성 읽기를 보장하진 않는데 읽기를 선형적으로 하려면 몇 가지 선택지가 있다.
    • 로그를 통해 순차 읽기 하는 방법 - 로그에 메시지를 추가하고 로그를 읽어 메시지가 되돌아왔을 때 실제 읽기를 수행하는 것.
    • 로그에서 최신 로그 메시지의 위치를 선형적 방법으로 얻을 수 있다면 그 위치를 질의하고 그 위치까지의 모든 항목이 전달 되기를 기다린 후 읽기를 수행
    • 쓰기 실행 시 동기식으로 갱신된 최신성이 보장된 복제 서버에서 읽기
• 선형성 저장소를 사용해 전체 순서 브로드캐스트 구현하는 것도 가능하다.
  • 전체 순서 브로드캐스트를 통해 보내고 싶은 메시지에 선형성 정수로 increment-and-get 연산을 수행 후 얻은 값을 일련번호로 메시지에 붙이면 수신자들은 일련번호 순서대로 메시지를 전달한다.
  • 램포트 타임스탬프와는 달리 틈이 없는 순열을 형성한다.
    • 메시지 4를 받고 6을 받았다면 메시지 5를 기다려야 한다는 것을 알 수 있음
    • 램포트 타임스탬프에선 불가능하다.
  • 원자적 increment-and-get 연산이 지원되는 선형성 정수를 만드는 것은 실패가 없다면 쉽다.
    • 문제는 네트워크 등 장애 시 그 값을 복구하는 것
  • 선형성 일련번호 생성기에 고심하다 보면 합의 알고리즘에 도달하게 된다.

분산 트랜잭션과 합의

• 합의는 분산 컴퓨팅에서 가장 중요하고 근본적 문제다.
• 비공식적으로 합의의 목적은 여러 노드들이 뭔가에 동의하게 만드는 것
• 노드가 동의하는 것이 중요한 상황
  • 리더 선출
  • 원자적 커밋
• 단일 노드에서 트랜잭션은 흔히 저장소 엔진에서 구현된다.
  • 데이터가 디스크에 지속성 있게 쓰여지는 순서에 의존
• 하지만 분산 노드 환경에서선 모든 노드에 커밋 요청을 보내고 독립적으로 커밋하는 것으론 충분하지 않다.
  • ex) 색인 항목이 주 데이터와 다른 노드에 있는 경우
  • 트랜잭션이 한 노드에서 커밋되면 다른 노드에서 어보트시키기가 어렵다.
• 트랜잭션 커밋은 되돌릴 수 없기에 다른 노드에서 어보트된게 밝혀져도 취소할 수 잆다.
  • 보상 트랜잭션이라는 개념이 있지만 데이터베이스 관점에서 이는 분리된 트랜잭션이다.

2단계 커밋

• 2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하도록 보장하는 알고리즘이다.
  • 커밋/어보트 과정이 두 단계로 나뉜다.
  • 코디네이터(트랜잭션 관리자)를 사용
• 왜 2PC의 2단계 커밋이 원자성을 보장하는지 이해하려면 자세한 과정을 볼 필요가 있다.
  • 애플리케이션이 분산 트랜잭션을 시작할 때 코디네이터에게 트랜잭션 ID를 요청한다. (전역적으로 유일한 ID)
  • 해당 트랜잭션 ID로 애플리케이션은 각 참여자에서 단일 노드 트랜잭션을 시작한다.
    • 이 때 뭔가 잘못되면 코디네이터나 참여자 중 누군가가 어보트할 수 있다.
  • 애플리케이션이 커밋할 준비가 되면 코디네이터는 모든 참여자에게 전역 트랜잭션 ID로 태깅된 준비 요청을 보낸다.
    • 이 때 실패하거나 타임아웃이 발생하면 코디네이터는 모든 참여자에게 그 트랜잭션 ID로 어보트 요청을 보낸다.
  • 참여자가 준비 요청을 받으면 커밋 가능한지 확인한 뒤 ‘네’라고 응답한다.
    • 트랜잭션을 오류 없이 커밋할 것이라는 보장이지만 실제로 커밋하지는 않는다.
  • 코디네이터가 모든 준비 요청에 응답을 받으면 트랜잭션을 커밋할지 어보트할지 최종 결정을 한다.
    • 이 때 결정을 디스크의 트랜잭션 로그에 기록하는데 이를 커밋 포인트라 한다.
  • 코디네이터 결정이 기록되면 모든 참여자에게 커밋/어보트 요청이 전송된다.
    • 이 요청은 성공할 때까지 영원히 재시도된다.
• 위 과정을 보면 2PC의 원자성을 보장하는 결정들이 존재한다.
  • 참여자가 ‘네’라고 응답함으로써 나중에 분명 커밋할 것이라 보장 (코디네이터가 어보트시킬 순 있지만)
  • 코디네이터가 한 번 결정하면 그 결정은 변경할 수 없다.
• 코디네이터에 장애가 발생하면 참여자는 커밋할지 어보트할지 알 방법이 없다.
  • 2PC가 복구되려면 코디네이터가 복구되기를 기다려야만 한다.
  • 때문에 2PC는 블로킹 원자적 커밋 프로토콜이라 불린다.
  • 코디네이터가 복구하길 기다리느라 멈출 수 있기 때문
• 블로킹되는 것에 대한 대안으로 3단계 커밋(3PC) 알고리즘이 존재한다.
  • 3PC는 지연에 제한이 있는 네트워크와 응답 시간에 제한이 있는 노드를 가정한다.
  • 하지만 기약 없는 지연이 발생할 수 있는 대부분의 실용적 시스템에서 3PC는 원자성을 보장하지 못한다.

분산 트랜잭션의 두 의미

• 분산 트랜잭션은 보통 두 가지 의미가 혼용되어 사용된다.
  • 데이터베이스 내부 분산 트랜잭선
    • 분산 데이트베이스에서 노드 사이의 내부 트랜잭션을 의미
    • 트랜잭션에 참여하는 모든 노드는 동일 소프트웨어를 실행
  • 이종(heterogeneous) 분산 트랜잭션
    • 트랜잭션에서 참여자들이 둘 혹은 그 이상인 다른 기술 (ex) 서로 다른 벤더의 데이터베이스)
    • 노드 간의 시스템 내부가 완전히 다르더라도 원자적 커밋을 보장해야 한다.
• 데이터베이스 내부 분산 트랜잭션의 경우 같은 시스템을 사용하기에 특정 기술에 기반한 최적화를 적용 가능하고 흔히 매우 잘 동작한다.
  • 반면 이종 분산 트랜잭션은 훨씬 더 어렵다.

현실의 분산 트랜잭션

• 정확히 한 번 메시지 처리
  • 이종 분산 트랜잭션은 다양한 시스템들이 통합될 수 있게 한다.
    • ex) 메시지 큐에서 나온 메시지는 그 메시지를 처리하는 데이터베이스 트랜잭션이 커밋 되었을 때만 처리된 것으로 확인 받을 수 있음
  • 메시지 전달이나 데이터베이스 트랜잭션 중 하나가 실패하면 둘 다 어보트되고 메시지 브로커는 다시 메시지를 전달할 수 있다.
    • 이를 달성하려면 메시지와 그 처리과정의 부수 효과를 원자적으로 다루고 정확히 한 번 처리되도록 보장해야 한다.
  • 하지만 모든 시스템이 원자적 프로토콜을 사용 가능한 것은 아니다.
    • ex) 부수 효과가 이메일 전송의 경우 메시지 처리 실패 시 이메일이 두 번 이상 전송될 수도 있다.
• X/Open XA(eXtended Architecture)
  • 이종 기술에 걸친 2단계 커밋을 구현하는 표준
  • 여러 관계형 데이터베이스와 메시지 브로커에서 지원된다.
  • 트랜잭션 코디네이터와 연결되는 인터페이스를 제공
    • ex) 자바 진영에선 자바 트랜잭션 API(Java transaction API, JTA)를 사용해 구현
  • 트랜잭션 코디네이터는 XA API를 구현한다.
    • 흔히 독립된 서비스가 아닌 트랜잭션을 시작하는 애플리케이션과 같은 프로세스에 로딩되는 라이브러리다.
    • 트랜잭션 참여자 추적, 응답 수집, 커밋/어보트 결정을 위해 로컬 디스크의 로그를 이용한다.
    • 애플리케이션 장애 시 복구되면서 코디네이터는 디스크의 로그를 통해 트랜잭션 결과를 복구해야 한다.
• 트랜잭션 수행 중 장애로 인해 커밋/어보트를 대기하는 상황에선 잠금 또한 해제할 수 없다.
  • 이는 더티 쓰기 방지 및 직렬성 격리를 필요로 해야 하는 경우가 있기 때문이다.
  • 의심스러운 트랜잭션이 해소될 때까지 애플리케이션의 장애가 전파되는 원인이 되기도 한다.
• 이론상 코디네이터 복구 후 트랜잭션들의 상태를 깨끗히 복구해야 하지만 어떤 이유로 인해 그 결과를 정할 수 없는 트랜잭션이 발생할 수 있다.
  • 트랜잭션 로그 손실 또는 버그로 인해 발생할 수 있다.
  • 해결하는 유일한 방법은 관리자가 수동으로 커밋/롤백 여부를 결정하는 것이다.
  • 여러 XA 구현엔 이러한 의심스러운 트랜잭션의 커밋/어보트를 결정하는 경험적 결정(heuristic decision)이라는 방안이 존재한다.
    • 경험적 결정은 2PC 체계를 위반하기에 원자성을 깰 수도 있다.
• XA 트랜잭션 운영 시 트랜잭션 코디네이터 자체가 일종의 데이터베이스여아 하기에(트랜잭션 결과를 저장해야 함) 운영상 문제를 가져온다.
  • 코디네이터가 단일 장비에서 실행되면 단일 장애점이 된다.
  • 보통 애플리케이션은 상태를 가지지 않아 배포가 간단한 경우가 많은데 코디네이터가 트랜잭션 로그를 영속하게 되면서 배포 특성이 변경된다.
  • 광범위한 데이터 시스템과 호환되어야 하므로 최소 공통 분모가 될 필요가 있다.
    • 여러 시스템에 걸친 교착 상태를 감지할 수 없다.
    • 직렬성 스냅숏 격리(SSI)와 함께 동작하지 않는데 이를 지원하려면 여러 시스템에 걸친 충돌을 식별할 프로토콜이 필요하기 때문이다.
  • 데이터베이스 내부 분산 트랜잭션은 제한이 크지 않아 분산 버전 SSI를 사용 가능하지만 2PC가 성공적으로 트랜잭션을 커밋하려면 모든 참여자가 응답해야 한다는 문제가 남는다.

내결함성을 지닌 합의

• 합의 알고리즘은 다음 속성을 만족해야 한다.
  • 균일한 동의 - 어떤 두 노드도 다르게 결정하지 않는다.
  • 무결성 - 어떤 노드도 두 번 결정하지 않는다.
  • 유효성 - 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다.
  • 종료 - 죽지 않은 모든 노드는 결국 어떤 값을 결정한다.
• 균일한 동의와 무결성은 합의의 핵심 아이디어를 정의한다.
  • 모두 같은 결과로 결정하며 결정을 번복하지 않음
• 유효성을 주로 뻔한 해결책을 배제하기 위해 존재한다.
  • ex) 무엇을 제안해도 항상 null로 결정하는 알고리즘이 있다면 유효성을 만족하지 않는다고 본다.
• 종료 속성은 내결함성의 아이디어를 형식화한다.
  • 내결함성이 상관 없다면 처음 세 속성만으로 충분한데 한 노드를 ‘독재자’로 사용해 모든 결정을 내리면 된다.
• 종료 속성은 죽거나 연결 가능한 노드 대수가 절반 미만이라는 가정에 종속적이다.
  • 대부분의 합의 구현은 과반수 노드에 장애가 나도 안전성 속성(동의, 무결성, 유효성)은 만족한다.
  • 하지만 대부분의 노드가 실행 중이 아니라면 어떤 알고리즘을 쓰든 내결함성을 보장하진 못한다.
• 앞서 살펴봤던 전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일하다.
  • 합의의 동의 속성 때문에 모든 노드는 같은 메시지를 같은 순서로 전달하도록 결정
  • 무결성 속성 때문에 메시지는 중복되지 않는다.
  • 유효성 속성 때문에 메시지는 오염되거나 조작되지 않는다.
  • 종료 속성 때문에 메시지는 손실되지 않는다.

    리더와 합의

• 단일 리더 시스템에선 리더가 수동으로 선택되고, 리더 노드가 죽으면 시스템은 동작하지 않기에 합의 알고리즘의 ‘종료’ 속성을 불만족한다.
• 복수 리더가 있는 시스템에서 스플릿 브레인 문제를 해결하기 위해 합의가 또 필요하다.
  • 누가 리더인지 노드들의 동의가 필요
• 합의 프로토콜은 내부적으로 어떠한 리더를 사용하지만 리더가 유일하다고 보장하지는 않는다.
• 대신 에포크 번호를 정의해 약한 보장을 제공한다.
  • 각 에포크 번호 내에선 리더가 유일하다고 보장
  • 리더 선출 시 에포크 번호를 단조 증가 시키고, 리더 사이에 충돌이 존재하면 에포크 번호가 높은 리더가 승리한다.
• 따라서 합의 시스템에선 두 번의 투표가 있다.
  • 리더 선출 투표
  • 리더의 제안에 투표
  • 중요한 것은 두 번의 투표를 하는 정족수는 겹쳐야 한다.
    • 제안에 대한 투표에 참여한 노드중 최소 하나는 가장 최근의 리더 선출 투표에더 참여했어야 하는데 이는 가장 최근 선출된 리더의 에포크 번호를 두 투표에 참여한 노드가 알 수 있기 때문

합의의 제약

• 제안이 결정되기 전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제다.
  • 이는 성능의 오버헤드를 가져온다.
• 합의 시스템은 엄격한 과반수가 동작하기를 요구한다.
  • 노드 1대 장애를 견디려면 최소 3대의 노드가 필요하고 2대를 견디려면 최소 5대가 필요하다.
• 합의 시스템에서클러스터에 노드를 그냥 추가하거나 제거할 수 없다.
  • 대부분 합의 알고리즘은 투표에 참여하는 노드 집합이 고정돼 있다고 가정하기 때문
  • 합의 알고리즘의 동적 멤버십(dynamic membership) 확장을 통해 시간이 지남에 따라 노드 집합의 변경을 허용하는 것도 가능하지만 이해하기 어려운 알고리즘을 사용한다.
• 합의 시스템은 노드 장애 감지에 일반적으로 타임아웃에 의존한다.
  • 때문에 네트워크 지연 시 리더 선출이 발생해 성능이 더 안좋아질 위험이 있다.

코디네이션 서비스

• 주키퍼나 etcd 같은 프로젝트는 종종 ‘분산 키-값 저장소’나 ‘코디네이션과 설정 서비스’라 설명된다.
  • API 자체는 데이터베이스와 비슷해 보이지만 실제로 범용 데이터베이스에는 적합하지 않다.
• 개발자가 주키퍼를 직접 쓸 필요는 거의 없고 다른 프로젝트를 통해 간접적으로 의존하게 되는 경우가 많다.
  • HBase, 하둡 얀, 노바, 카프카 등이 모두 배후의 주키퍼에 의존한다.
• 주키퍼는 메모리에 적재 가능한 작은 양의 데이터를 보관하도록 설계되었다.
  • 이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트를 통해 모든 노드에 복제된다.
• 주키퍼는 브로드캐스트 뿐 아니라 분산 시스템 구축 시 유용한 다양한 기능을 구현한다.
  • 선형적 원자적 연산
    • 여러 노드의 동시 연산 수행 시 하나의 성공만을 보장한다.
    • 원자적 compare-and-set 연산으로 잠금을 구현하고, 장애 상황에 결국엔 해제되도록 만료 시간이 있는 임차권을 사용
  • 연산의 전체 순서화
    • 잠금 획득 시마다 펜싱 토큰을 증가시켜 클라이언트 간 충돌을 막는다.
  • 장애 감지
    • 클라이언트는 주키퍼 서버와 수명이 긴 세션을 유지하며 주기적으로 하트비트를 교환한다.
    • 세션 타임아웃보다 긴 기간 동안 하트비트가 멈추면 주키퍼는 세션이 죽었다고 선언한다.
    • 세션에서 획득한 잠금은 타임아웃 시 자동 해제되도록 설정할 수 있는데 이를 ‘단명 노드’라 한다.
  • 변경 알림
    • 클라이언트는 다른 클라이언트의 변경을 감시할 수 있다.
    • 변경에는 생성한 잠금, 언제 클러스터에 합류했는지, 장애가 났는지 등이 있다.
    • 알림을 구독하여 주기적으로 폴링하며 변경을 감시한다.
• 주키퍼는 노드들을 코디네이트하는 작업(합의, 연산, 순서화)의 일부를 외부 서비스에 위탁하는 방법을 제공한다.
  • 애플리케이션의 너무 많은 노드들 간의 과반수 투표는 매우 비효율적이다.
  • 대신 주키퍼는 (보통 3~ 5) 고정된 수의 노드만을 사용하여 투표를 진행하여 매우 많은 클라이언트를 지원한다.
• 보통 주키퍼로 관리되는 데이터는 매우 느리게 변한다.
  • 매초 수천에서 수백만 번까지 변경될지 모르는 데이터에 사용되도록 의도된 게 아니다.

주키퍼 사용 사례

• 여러 프로세스나 서비스 중 리더를 선출
  • 리더 장애 시 새로운 노드가 리더를 넘겨 받아야 한다.
  • 단일 리더 데이터베이스 또는 작업 스케줄러 같은 상태 저장 시스템에도 유용
• 파티셔닝된 자원에서 어떤 파티션을 어느 노드에 할당할지 결정
  • 새 노드가 클러스터에 합류하는 경우 부하의 재균형화 때문에 기존 노드에서 새 노드로 파티션을 옮겨야 한다.
  • 노드가 제거되거나 장애 시에도 마찬가지다.
• 서비스 찾기 (service discovery)
  • 특정 서비스에 연결하기 위해 어떤 IP 주소로 접속해야 하는지 알아내는 방법
  • 합의 시스템이 누가 리더인지 이미 안다면 다른 서비스들이 리더가 누구인지 찾는데 그 정보를 사용하는 것이 타당하다.
  • 때문에 합의 시스템은 읽기 전용 캐시 복제 서버를 사용하는데 합의 알고리즘의 모든 결정에 관한 로그를 비동기로 받는다.
  • 읽기 전용 캐시 복제 서버는 선형적일 필요가 없는 읽기 요청을 서비스할 수 있다.