책너두 (데이터 중심 애플리케이션 설계) 30일차 (~348p)

요약

• 데이터 순서화 보장에 대한 내용을 알게됨.
  • 순서화는 인과성을 보존하는데 도움을 줌.
• 인과적 의존성을 보존하기 위해 일련번호를 사용한다.
  • 일련번호의 순서화임.
  • ex) 램포트 타임스탬프
• 전체 순서 브로드캐스트는 연산의 순서를 보고 전체 순서를 정한다.

메모

순서화 보장

• 순서화는 이 책에서 되풀이된 주제임.
• 중요한 근본적 아이디어일 수 있음을 시사함.
• 순서화, 선형성, 합의 사이에는 깊은 연결 관계가 있음.
  • 이 개념은 시스템이 무엇을 할 수 있고 무엇을 할 수 없는지에 대한 이해를 명확하게 하는데 큰 도움이 됨.

순서화와 인과성

• 순서화가 인과성을 보존하는 데 도움을 줌.
• 인과성은 이벤트에 순서를 부과함.
  • 결과가 나타나기 전에 원인이 발생함.
• 시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적이라고 함.

인과적 순서가 전체 순서는 아님.

• 선형성 시스템에서는 연산의 전체 순서를 정할 수 있음.
• 인과성은 전체 순서가 아닌 부분 순서를 정의함.
  • 어떤 연산들은 서로에 대해 순서를 정할 수 있지만, 어떤 연산들은 비교할 수 없음.

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

• 인과적 순서와 선형성 사이의 관계
  • 선형성은 인과성을 내포함.
  • 즉, 어떤 시스템이든지 선형적이라면 인과성도 올바르게 유지함.
• 그러나 선형성에서 네트워크 지연이 크면 성능과 가용성에 해가될 수 있음.
  • 이는 절충 가능함.
  • 선형성은 인과성을 보존하는 유일한 방법이 아님.
  • 많은 경우, 선형성이 필요한 것처럼 보이는 시스템에 사실 진짜로 필요한 것은 인과적 일관성이며, 이는 더 효율적으로 구현될 수 있음.

인과적 의존성 담기

• 인과성을 유지하기 위해 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 함.
  • 이는 부분 순서임.
  • 복제 서버가 연산을 처리할 때 인과적으로 앞서는 모든 연산이 이미 처리됐다고 보장할 수 있어야 함.
  • 선행 연산 중 빠진게 있으면 후속 연산은 그 선행 연산이 처리될 때까지 기다려야 함.
• 인과적 순서를 결정하기 위해 데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야 함.

일련번호 순서화

• 모든 인과적 의존성을 실제로 추적하는 것은 실용성이 떨어짐.
  • 읽은 데이터를 모두 명시적으로 추적하는 것은 오버헤드가 큼.
    • 더 좋은 방법으로 일련 번호나 타임 스탬프를 써서 이벤트의 순서를 정할 수 있음.
    • 이를, 물리적 시계가 아니라 논리적 시계에서 얻어도 됨.
      • 논리적 시계는 연산을 식별하는 일련번호를 생성하는 알고리즘임.
      • 이러한 일련번호나 타임스탬프는 크기가 작고, 전체 순서를 제공함.

비인과적 일련번호 생성기

• 단일 리더가 없다면 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않음.
• 현실에서 다양한 방법이 사용됨.
  • 일련번호를 노드별로 홀, 짝만 생성하도록 한다.
  • 일 기준 시계에서 얻은 타임스탬프를 각 연산에 붙인다.
  • 일련번호 블록을 미리 할당한다.
• 위 세 가지 방법은 카운터를 증가시키는 단일 리더에 모든 연산을 밀어 넣는 것보다 확장성이 좋음.
• 하지만, 생성한 일련번호가 인과성에 일관적이지 않음.
  • p342 참고

램포트 타임스탬프

• 램포트 타임스탬프는 인과성에 일관적인 일련번호를 생성하는 간단한 방법임.
  • 분산 시스템 분야에서 가장 많이 인용된 논문중 하나임.
• 램포트 타임스탬프는 그냥 (카운터, 노드ID)의 쌍임.
• 램포트 타임스탬프는 물리적 일 기준 시계와 아무 관련이 없지만, 전체 순서화를 제공함.
• 램포트 타임스탬프를 인과성 일관적으로 만들어주는 핵심아이디어는 다음과 같음.
  • 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다.
  • 노드가 자신의 카운터 값보다 큰 최대 카운터를 가진 요청이나 응답을 받으면 바로 자신의 카운터를 그 최댓값으로 증가시킨다.

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

• 노드가 사용자로부터 사용자명 생성 요청을 막 받고 그 요청이 성공해야 하는지 실패해야 하는지 당장 결정해야 할 때는 타임 스탬프 순서화만으로는 부족함.
• 다른 어떤 노드도 동시에 더 낮은 타임스탬프를 가지고 동일한 사용자명으로 계정 생성을 처리하는 중이 아니라고 확신하려면 다른 모든 노드가 무엇을 하고 있는지 확인해야 함.
• 연산의 전체 순서는 모든 연산을 모은 후에야 드러나는 것이 문제임.
  • 전체 순서가 언제 확정되는지도 알아야 함.

전체 순서 브로드캐스트

• 단일 리더 복제는 한 노드를 리더로 선택하고 리더의 단일 CPU 코어에서 모든 연산을 차례대로 배열함으로써 연산의 전체 순서를 정함.
  • 처리량이 단일 리더가 처리할 수준이 넘어선다면 시스템을 확장해야함.
  • 리더에 장애가 발생했을 때 어떻게 장애복구를 처리할지가 중요함.
    • 이 문제는 전체 순서 브로드 캐스트나 원자적 브로드캐스트로 알려져 있음.
• 전체 순서 브로드 캐스트는 노드 사이에 메시지를 교환하는 프로토콜로 기술됨.
  • 신뢰성 있는 전달
    • 어떤 메시지도 손실되지 않음.
    • 메시지가 한 노드에 전달되면 모든 노드에 전달됨.
  • 전체 순서가 정해진 전달
    • 메시지는 모든 노드에 같은 순서로 전달됨.

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

• 주키퍼나 etcd 같은 합의 서비스는 전체 순서 브로드캐스트를 실제로 구현함.
  • 순서 브로드캐스트와 합의 사이에 강한 연고나이 있음.
• 전체 순서 브로드캐스트는 데이터베이스 복제에 딱 필요함.
  • 모든 복제 서버들이 일관성 있는 상태로 유지가됨.
  • 이 원리를 상태 기계 복제(state machine replication)라고 함.
• 직렬성 트랜잭션을 구현하는 데도 쓸 수 있음.
• 전체 순서 브로드캐스트의 중요한 측면은 메시지가 전달되는 시점에 그 순서가 고정됨.
  • 이 사실 때문에 전체 순서 브로드캐스트가 타임스탬프 순서화보다 강함.

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

• 전체 순서 브로드캐스트는 비동기식임.
  • 메시지를 고정된 순서로 신뢰성있게 전달되도록 보장하지만 언제 메시지가 전달될지 보장되지 않음.
• 그러나 전체 순서 브로드 캐스트 구현이 있다면 한 선형성 저장소를 만들 수 있음.
  • ex) p347 참고
  • 이 절차는 선형성 쓰기를 보장하지만 선형성 읽기는 보장하지 않음.
  • 로그로부터 비동기로 갱신된 저장소를 읽으면 오래된 값이 읽힐 수 있음.

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

• 전체 순서 브로드캐스트를 통해 보내고 싶은 모든 메시지에 대해 선형성 정수 increment -and-get 연산을 수행하고 레지스터에 얻은 값을 일련번호로 메시지에 붙임.
  • 그 후, 메시지를 모든 노드에 보낼 수 있고 수신자들은 일련번호 순서대로 메시지를 전달한다.