분산 데이터

09장: 일관성과 합의

결함의 가장 간단한 해결방법은 서비스가 실패하도록 두고 사용자에게 오류메시지를 보내는것

내결함성을 지닌 시스템을 구축하는 가장 좋은 방법은 유용한 보장을 해주는 범용 추상화를 찾아 이를 구현하고 애플리케이션에서 이 보장에 의존하게 하는것

분산시스템에 가장 중용한 추상화 중 하나는 합의

스플릿 브래인(split brain) : 두 노드가 자신이 리더라고 생각하는 상황

일관성 보장

복제 데이터베이스는 대부분 최소한 최종적 일관성(Eventual Consistency)을 제공한다

이것은 매우 약한 보장 언제 복제본이 수렴될지에 대해선 모른다

트랜젝션 격리는 주로 동시에 실행되는 트랜젝션 때문에 발생하는 경쟁조건을 회피하는것에 관한것

분산 일관성은 대게 지연과 결함이 있더라도 복제본 상태를 코디네이션 하는것

선형성

선형성을 뒷바침 하는 아이디어

원자적 일관성(atomic consistency)
강한 일관성(strong consistency)
즉각 일관성(immediate consistency)
외부 일관성(external consistency)

선형성은 최신성 보장(recency guarantee)이다

시스템에 선형성을 부여하는 것은 무엇인가?
- 읽기가 새로운 값을 반환한 적이 있은 후에는 모든 후속 읽기도 반드시 새로운 값을 반환 해야 된다
- 선형성 대 직렬성
  - 직렬성 : 트랜잭션들의 격리 속성(트랜잭션이 어떤 순서에 따라 실행되는 것처럼 동작하도록 보장해 준다)
  - 선형성 : 레지스터에 실행되는 읽기 쓰기에 대한 최신성 보장이다
선형성에 기대기
- 어떤 환경에서 선형성이 유용할까?
  - 잠금과 리더 선출
    - 아파치 주키퍼
    - etcd
  - 제약 조건과 유일성 보장
    - 엄격한 유일성 제약조건은 선형성이 필요하다
  - 채널 간 타이밍 의존성
    - 웹서버와 이미지 크기 변경 모듈 사이에 다른 통신 채널, 파일저장소와 메시지 큐 때문에 발생하는 문제
선형성 시스템 구현하기
- 복제 방법
  - 단일 리더 복제(선형적이 될 가능성이 있음)
  - 합의 알고리즘(선형적)
  - 다중 리더 복제(비선형적)
  - 리더 없는 복제(아마도 비선형적)
- 선형성과 정족수
  - 엄격한 정족수를 사용한 읽기는 선형적인 것처럼 보인다 하지만 네트워크 지연의 변동이 심하면 경쟁조건이 생길수 있다
선형성의 비용
- 복제 방법중 선형성을 제공하는 것도 있고 그렇지 않은 것도 있다
- 단일 리더를 사용하는 데이터 베이스는 선형성을 제공하지만 리더가 장애가 나면 선형성을 제공하지 못한다
- CAP 정리
  - 일관성(Consistency) : 모든 클라이언트가 같은 순간의 데이터를 보는 것
  - 가용성(Availability) : 모든 클라이언트의 요청에 항상 응답을 주는 것
  - 분단 내성(Partition tolerance) : 네트워크 장애가 일어나도 시스템이 정상적으로 동작하는 것
- 선형성과 네트워크 지연
  - 실제로 선형적인 시스템은 놀랄 만큼 드물다
  - cpu의 램조차 선형적이지 않다
  - 선형성을 제거한 이유는 내결함성이 아니라 성능이다

순서화 보장

선형성을 보장할때 순서하가 중요한 근본적 아이디어일 수도 있다는것

순서화와 인과성
- 순서화가 인과성을 보존하는데 도움을 준다
- 질문과 답변사이의 인과적 의존성이 있다
- 트랜젝션은 일관된 스냅숏에서 읽는다고 했다 여기서 일관성은 인과성에 일관적이란 의미
- 시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적이라고 한다
- 인과적 순서가 전체 순서는 아니다
  - 수학적 집합은 항성 전체 순서를 정할수 있는건 아니다
  - 부분적으로 순서가 정해진다(partially ordered)
  - 선형성 : 시스템에서 연산의 전체순서를 정할수 있다
  - 인과성 : 인과성이 전체 순서가 아닌 부분 순서를 정의한다는 뜻
- 선형성은 인과적 일관성보다 강하다
  - 선형성은 인과성을 내포한다
- 인과적 의존성 담기
  - 인과성이 유지하기 위해서 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다
일련번호 순서화
- 일련번호나 타임스탬프를 써서 이벤트의 순서를 정할수 있다
- 일련번호나 타임스템프느는 크기가 작고 전체 순서를 제공한다
- 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다
- 비인과적 일련번호 생성기
  - 각 노드가 자신만에 독립적인 일련번호 집합을 생성할수 있다
  - 각 연산에 일 기준 시계에서 얻은 타임스템프를 붙일수 있다
  - 일련번호 블록을 미리 할당할수 있다
  - 생성한 일련번호가 인과성에 일관적이지 않다
- 램포트 타임스템프
  - 인과성에 일관적인 일련번호 생성
  - 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다
  - 항상 전체순서화를 강제화
전체 순서 브로드캐스트
- cpu에서 실행된 순서가 바로 전체 순서다
- 전체 순서 브로드캐스트(total order broadcast)
- 원자적 브로드캐스트(atmoic broadcast)
- 만족해야할 안전성 속성
  - 신뢰성 있는 전달(reliable delivery)
  - 전체 순서가 정해진 전달(totally ordered delivery)
- 전체 순서 브로드캐스트 사용하기
  - 상태 기계 복제(state machine replication) : 모든 메시지가 데이터베이스에 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태를 유지한다
  - 직렬성 트랜적션을 구현하는데도 쓸수 있다
  - 메시지가 전달하는 시점에 그 순서가 고정됨
  - 로그를 만드는 방법 중 하나
- 전체 순서 브로드캐스트를 사용해 선형성 저장소 구현하기
  - 전체 순서 브로드캐스트는 비동기식이다
  - 순차적 일관성(sequential consistency) : 모든 클라이언트가 같은 순서로 메시지를 보는 것
  - 타임라인 일관성(timeline consistency) : 모든 클라이언트가 같은 순서로 메시지를 보는 것
- 선형성 저장소를 사용해 전체 순서 브로드캐스트 구현하기
  - 선형성 레지스터와 전체순서 브로드캐스트는 둘 다 합의와 동등하다고 증명할수 있다

분산 트랜잭션과 합의

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

리더선출, 원자적커밋

원자적 커밋과 2단계 커밋(2PC)
- 원자성은 주데이터와 보조색인이 일관성을 유지하도록 보장한다
- 단일 노드에서 분산 원자적 커밋으로
  - 단일 데이터베이스 노드에서 실행되는 트랜잭션에게 원자성은 흔히 저장소 엔진에서 구현됨
  - 커밋된 트랜잭션 효과는 나중에 다른 보상 트랜잭션(compensation transaction)을 실행해 취소할수 있다
- 2단계 커밋 소개
  - XA 트랜잭션
  - 트랜잭션의 참여자(participant)
  - 트랜잭션 코디네이터(coordinator)
- 약속에 관한 시스템
  - 2PC는 약속에 관한 시스템(promise system)이다
- 코디네이터 장애
  - 코디네이터가 장애가 나면 참여자들은 영원히 대기 상태에 빠진다
- 3단계 커밋
  - 2PC는 코디네이터가 복구하기를 기다리느라 멈출 수 있다는 사실때문에 블로킹 원자적 커밋 프로토콜
  - 2PC 대안으로 3PC가 있다
  - 3PC는 원자성을 보장하지못한다
현실의 분산 트랜잭션
- 데이터베이스 내부 분산 트랜잭션
- 이종 분산 트랜잭션
- 정확히 한 번 메시지 처리
  - 결과적으로(effectively), 정확히 한번(exactly once) 처리 되도록 보장할수 있다
- XA 트랜잭션
  - X/Open XA(Extended Architecture) 이종 기술에 걸친 2단계 커밋을 구현하는 표준
- 의심스러운 상태에 있는 동안 잠금을 유지하는 문제
  - 데이터베이스는 트랜잭션이 커밋하거나 어보트할 떄까지 이런 잠금을 해제할 수 없다
- 코디네이트 장애에서 복구하기
  - 고아가된(orphand) 트랜잭션 해결방법은 수동 커밋 롤백 선택
  - 경험적 결정(hueristic decision) : 코디네이터가 장애가 나면 참여자들이 트랜잭션을 커밋하거나 어보트할 수 있다
  - 경험적은 2PC 약속 체계를 위반하기 때문에 아마도 원자성을 깰 수 있다
- 분산트랜잭션 제약
  - 코디네이터가 복제되지 않고 단일 장비에서 실행되면 단일 장애점(single point of failure)이 된다
  - 코디네이터 서버가 어플리케이션의 일부가 되면 상태 비저장 서버가 아니다
  - XA가 최소 공통 분모가 되어야 된다
  - 분산 트랜잭션은 장애를 증폭시키는 경향이 있다
내결함성을 지닌 합의
- 합의 알고리즘
  - 군일한 동의
  - 무결성
  - 유효성
  - 종료
- 합의 알고리즘과 전체 순서 브로드캐스트
  - 뷰스탬프 복제(viewstamped replication), 팍소스(paxos), 라프트(raft)
  - 순차열(sequence)에 대해 결정해서 전체 순서 알고리즘을 만든다
  - 전체 순서 브로드캐스트는 합의를 여러번 반복하는것과 동일
- 단일 리더 복제와 합의
  - 리더를 선출 할려면 먼저 리더가 필요?
- 에포크 번호 붙이기와 정족수
  - 에포크 번호(epoch number)
  - 투표 번호(ballot number)
  - 뷰 번호(view number)
  - 팀 번호(team number)
- 합의의 제약
  - 장애 노드 감지를 위해 일반적으로 타임아웃에 의존
멤버십과 코디네이션 서비스
- 분산 키-값 저장소, 코디네이션과 설정 서비스
- 선형성 원자적 연산
- 연산의 전체 순서화
- 장애 감지
- 변경 알림
- 작업을 노드에 할당하기
  - 노드들을 코디네이션 하는 작업의 일부를 외부 서이스에 위탁
- 서비스 찾기
  - 서비스 디스커버리
- 맴버십 서비스
  - 주키퍼와 유사 프로젝트들은 맴버쉽 서비스(membership service)

정리

합의의 문제점

선형성 레지스터
원자적 트랜잭션 커밋
전체 순서 브로드캐스트
잠금과 임차권
맴버십/코디네이션 서비스
유일성 제약조건

참조

데이터 중심 애플리케이션 설계