1. 일관성 보장
•
약한보장
◦
복제 데이터 베이스는 대부분 최소한 최종적 일관성을 제공한다.
◦
모든 복제본이 결국 같은 값으로 수렴되기를 기대함으로 최종적 일관성보다 수렴이 더 나은 이름일 수도 있다.
◦
다만 이는 매우 약한 보장이며, 언제 복제본이 수렴될지에 대해서는 이야기가 없다.
•
강한보장
◦
데이터 시스템이 선택적으로 제공
◦
올바르게 사용하기 쉬우나 시스템 성능이 나쁘거나 내결함성이 약할수도 있다.
2. 선형성
•
최종적 일관성을 지닌 데이터베이스에서 두 개의 다른 복제본의 같은 질문을 동시에 하면 두 가지 다른 응답을 받을 수도 있기에 혼란스럽다.
•
위 문제에서 데이터베이스가 복제본이 하나만 있다면 더 단순해지지 않을까라는 생각을 할 수 있으며, 이는 선형성을 뒷받침해주는 아이디어다.
◦
원자적 일관성(atomic consistency)
◦
강한 일관성(strong consistency)
◦
즉각 일관성(immediate consistency)
◦
외부 일관성(external consistency)
•
기본적인 아이디어는 시스템에 데이터 복사본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것
•
선형성 시스템에서는 클라이언트가 쓰기를 성공적으로 완료하자마자 그 데이터베이스를 읽는 모든 클라이언트는 방금 쓰여진 값을 볼 수 있어야 함
◦
즉, 선형성은 최신성 보장(recency guarantee) 를 의미함
2.1. 시스템에 선형성을 부여하는 것은 무엇인가?
•
선형성을 받침하는 기본 아이디어는 시스템에 데이터 복사본이 하나뿐인 것처럼 보이게 만드는 것이다.
•
선형성 데이터베이스에서 동시에 같은 키 x를 읽고 쓰는 세 클라이언트를 보여준다.
◦
분산 시스템에 분야에서는 x를 레지스터(register) 라고 부른다.
•
이 예제에서는 레지스터는 두 가지 종류의 연산이 있다.
◦
read(x) => v 는 클라이언트가 레지스터 x의 읽기를 요청하고 데이터베이스가 값 v를 반환했다는 것을 의미
◦
write(x, v) => r 은 클라이언트가 레지스터 x의 값을 v로 설정하라고 요청했고 데이터베이스가 응답 r을 반환했다는 것을 의미
•
클라이언트 C가 쓰기를 실행하는 동안 A와 B는 지속적으로 값을 폴딩하는데 어떤 응답을 받을 수 있는가
◦
A가 첫 번째 실행한 요청은 0을 반환하는게 명백하다.
◦
A의 마지막 응답은 명백히 1을 반환받게 된다.
◦
쓰기가 실행 중 읽기 연산은 동시에 실행되므로 0을 받을지 1을 받을지 명확하지 않다.
선형적 읽기를 위해 최근 읽은적 있는 값은 후속 읽기에도 같은 값을 반환한다.
2.2. 선형성에 기대기
•
시스템이 올바르게 동작하도록 만들기 위한 선형성이 중요한 몇 가지 영역
2.2.1. 잠금과 리더 선출
•
단일 리더 복제를 사용하는 시스템은 리더가 여러개(스플릿 브레인)가 아니라 진짜 하나만 보장하도록 해야한다.
•
분산 잠금과 리더 선출을 구현하기 위해 아파치 주키퍼(Apache ZooKeepr)나 etcd 같은 코디네이션 서비스가 종종 사용된다.
◦
이들은 합의 알고리즘을 사용해 선형성 연산을 내결함성이 있느 방식으로 구현한다.
•
분산 잠금은 오라클 리얼 애플리케이션 클러스터 같은 분산 데이터베이스에서 훨씬 세분화된 수준으로 사용되기도 한다.
2.2.2. 제약 조건과 유일성 보장
•
유일성 제약 조건은 데이터베이스에서 흔하다.
◦
이러한 조건을 강제하고 싶다면 선형성이 필요하다.
◦
마찬가지로, 은행 계좌 잔고가 음수가 되지 않거나 예약의 경우 모든 노드가 동의하는 하나의 최신 값이 있기를 요구한다.
•
실제 애플리케이션에서는 종종 이런 제약 조건을 느슨하게 다르기도 하지만, 관계형 데이터베이스에서 전형적으로 볼 수 있는 엄격한 유일성 제약 조건은 선현성이 필요하다.
2.2.3. 채널 간 타이밍 의존성
웹 서버와 이미지 크기 변경 모듈은 파일 저장소와 메시지 큐를 모두 써 통신하므로 경쟁 조건 발생 가능
•
파일 저장 서비스가 선형적이면 잘 돌아가지만, 아니라면 경쟁 조건의 위험이 언제나 있다.
•
선형성이 경쟁 조건을 회피하는 유일한 방법은 아니지만 이해하기에 가장 단순하다.
2.3. 선형성 시스템 구현하기
•
선형성은 근본적으로 데이터 복사본이 하나만 있는 것처럼 동작하고 그 데이터에 실행되는 모든 연산은 원자적 이라는 것을 의미한다.
◦
But 이 방법으로 결함을 견뎌낼 수 없다.
•
시스템이 내결함성을 지니는 흔한 방법은 복제를 이용하는 것으로 앞서 다웠던 내용들을 정리하고 선형적으로 만들 수 있을지 정리한다.
◦
단일 리더 복제 : 선형적 가능성 존재
▪
읽기에 리더를 사용하기 위해서는 누가 리더인지를 정확하게 안다고 가정해야 한다.
◦
합의 알고리즘 : 선형적
▪
주키퍼 등의 코디네이트를 통해서 가능하다.
◦
다중 리더 복제 : 비선형적
▪
여러 노드에서 동시 쓰기를 처리하고 쓰여진 내용을 비동기적으로 처리하기 때문에 선형적이지 않다.
◦
리더 없는 복제 : 아마도 비선형적
▪
정족수 및 엄격한 일관성에 따라 결정된다.
2.3.1. 선형성과 정족수
•
엄격한 정족수를 사용한 읽기 쓰기는 선형적인 것처럼 보인다.
◦
But. 네트워크 지연의 변동이 심하면 경쟁 조건이 생길 수 있다.
•
정족수 조건이 만족됨에도 실행은 선형적이지 않을 수 있다.
•
성능이 떨어지는 비용을 지불하고 다이타모 스타일 정족수를 선형적으로 만드는 것도 가능하다.
◦
다만 이경우는 선형성 읽기와 쓰기 연산만 수행할 수 있다.
•
요약하면 다이나모 스타일 복제를 하는 리더 없는 시스템은 선형성을 제공하지 않는다고 보는 게 안전하다.
2.4. 선형성의 비용
네트워크가 끊기면 선형성과 가용성 사이에서 선택해야 한다.
2.4.1. CAP 정리
•
어떤 선형성 데이터베이라도 해당 문제를 가지고 있고 발생하는 트레이드오프를 정리해보자.
◦
애플리케이션에서 선형성을 요구하고 네트워크 문제 때문에 일부 복제 서버가 다른 복제 서버와 연결이 끊기면 일부 복제 서버는 연결이 끊긴 동안은 요청을 처리할 수 없다.
▪
네트워크 문제가 고쳐질 때까지 기다리거나 오류를 반환해야 한다.
•
즉, 가용성이 없다.
◦
애플리케이션에서 선형성을 요구하지 않는다면 각 복제 서버가 다른 복제 서버와 연결이 끊기더라도 독립적으로 요청을 처리하는 방식으로 쓰기를 처리할 수 있다.
▪
이 경우 애플리케이션은 네트워크 문제에 직면해도 가용한 상태를 유지하지만 그 동작은 선형적이지 않다.
•
따라서 선형성이 필요 없는 애플리케이션은 네트워크 문제에 더 강인하다.
◦
이는 CAP 정리로 널리 알려졌다.
•
CAP는 데이터베이스에서 트레이드오프에 대한 논의를 시작하려는 목적으로 정확한 정의 없이 경험 법칙으로 제안됐다.
•
공식적으로 정의된 CAP 정리는 매우 범위가 좁으며, 오직 하나의 일관성 모델과 한 종류의 결함만 고려한다.
◦
역사적인 영향력은 있으나 시스템 설계시 실용적인 가치는 없습니다.
2.4.2. 선형성과 네트워크 지연
•
선형성은 유용한 보장이지만 현실에서는 실제로 선형적인 시스템은 놀랄만큼 드물다.
•
성능을 위해 선형성이 손실되는 트레이드 오프가 발생하는 경우가 자주 발생한다.
•
분산 데이터베이스도 마찬가지의 이유다.
•
즉, 선형성을 원하면 읽기와 쓰기 요청의 응답 시간이 적어도 네트워크 지연의 불확싱성에 비례한다.
•
지연시간에 민감한 시스템에서는 이러한 트레이드오프가 중요하다.
3. 순서화 보장
•
순서화, 선형성, 합의 사이에는 깊은 연결 관계가 있음을 드러난다.
3.1. 순서화와 인과성
•
순서화는 인과성을 보존하는데 도움을 준다.
3.1.1. 인과적 순서가 전체 순서는 아니다
•
전체 순서(total order)은 어떤 두 요소를 비교할 수 있게 하므로 두 요소가 있으면 항상 어떤 것이 더 크고 어떤 것이 더 작은지 말할 수 있다.
◦
But. 수학적 집합은 이와 달리 비교불가(incomparable)하고, 부분적으로 순서가 정해진다(partially ordered).
•
전체 순서와 부분 순서의 차이점은 다른 데이터베이스 일관성 모델에 반영된다.
◦
선형성 : 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다.
◦
인과성 : 두 연산 중 다른 것보다 먼저 실행되지 않았다면 두 연산이 동시적이라고 말했고, 인과성이 전체 순서가 아닌 부분 순서를 정의한다.
•
이 정의를 통해 선형성 데이터스토어는 동시적 연산이 없습니다. 하나의 타임라인이 있고 모든 연산은 그 타임라인을 따라서 전체 순서가 정해져야 한다.
•
동시성은 타임라인이 갈라졌다 다시 합쳐지는 것을 의미한다.
•
깃의 버전 히스토리는 인과적 의존성 그래프와 매우 유사하다.
3.1.2. 선형성은 인과적 일관성보다 강하다.
•
선형성은 인과성을 내포한다.
•
선형성은 인과성을 보장해준다는 사실은 이해하기도 쉽고 매력적으로 보이게 만들어 준다.
◦
But. 네트워크 지연에 따라 성능과 가용성에 해가 될 수 있다.
•
절충선으로 선형적으로 만들지 않고도 인과적 일관성을 만족시킬 수 있다.
•
대부분의 시스템에서 실제로 필요한 것은 선형성이 아닌 인과성입니다.
3.2.3. 인과적 의존성 담기
•
인과성을 유지하기 위해서는 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다.
•
인과적 의존성을 결정하려면 시스템에 있는 노드에 관한 지식을 기술할 방법이 필요하다.
•
리더 없는 데이더 저장소는 갱신 손실 방지를 위해 같은 키에 대한 동시 쓰기를 검출해야한다.
◦
인과적 의존성은 여기서 더 나아가 버전 벡터(version vector)를 일반화할 수 있다.
3.3. 일련번호 순서화
•
인과성은 중요한 이론적 개념이지만 모든 인과적 의존성을 추적하는 것은 실용성이 떨어진다.
•
더 좋은 방법으로는 일련번호나 타임스탬프를 써서 이벤트의 순서를 정할 수 있다.
◦
타임스템프는 물리적 시계 대신 논리적 시계에서 얻어도 된다.
•
이러한 일련번호나 타임스탬프는 크기가 작고 전체 순서를 제공한다.
•
특히 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다.
•
단일 리더 복제를 쓰는 데이터베이스에서는 복제 로그가 인과성에 일관적인 쓰기 연산의 전체 순서를 정의한다.
3.3.1. 비인과적 일련번호 생성기
•
단일 리더가 없다면 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않습니다. 현실에서는 다양한 방법이 사용된다.
◦
각 노드가 자신만의 독립적인 일련번호 집합을 생성할 수 있다.
▪
각 노드는 초당 연산수가 다를 수 있다.
◦
각 연산에 일 기준 시계에서 얻은 타임스탬프를 붙일 수 있다.
▪
물리적 시계에서 얻은 타임스탬프는 시계 스큐에 종속적이다.
◦
일련번호 블록을 미리 할당할 수 있다.
▪
블록 할당자의 경우, 한 연산이 1001과 2000사이의 구간에서 일련번호를 받고 인과적으로 나중에 실행되는 연산이 1과 1000사이의 구간에서 일련번호를 받을 수 있다.
•
위의 세가지 선택지는 카운터를 증가하는 단일 리더에 모든 연산보다는 확장성이 좋으나, 생성된 일련번호가 인과성에 일관적이지 않다.
3.3.2. 램포트 타임스탬프
램포트 타임스탬프는 인과성에 일관적인 전체 순서화를 제공한다.
•
이러한 방법 대신 인과성에 일관적인 일련번호를 생성하는 간단한 방법은 램포트 타임스탬프(Lamport timestamp)다.
•
램포트 타임스탬프는 카운터, 노드ID의 쌍이다.
◦
두 노드는 때때로 카운터 값이 같을 수 있지만 노드ID가 포함되어 타임스탬프는 유일하다.
3.3.3. 타임스탬프 순서화로는 충분하지 않다
•
램포트 타임스탬프가 인과성에 일관적인 연산의 전체 순서를 정의하지만 분산 시스템의 공통 문제를 해결하는 데 아주 충분하지는 않다.
•
램포트 타임스탬프는 사후에 성공하는 쪽을 결정하는 데는 효과적이다.
◦
시스템에서 사용자명 생성 연산을 모두 모으면 그들의 타임스태프를 비교할 수 있다.
◦
But. 노드가 사용자로부터 사용자명 생성 요청을 막받고 그 요청이 성공해야 하는지 실패해야 하는지 당장 결정해야 할 때는 이 방법으로 부족하다.
•
다른 어떤 노드도 동시에 더 낮은 타임스탬프를 가지고 동일한 사용자명으로 계정 생성을 처리하는 중이 아니라고 확신하려면 다른 노드가 무엇을 하고 있는지 확인해야한다.
◦
다른 노드 중 하나에 장애가 생기거나 네트워크 문제 때문에 연결할 수 없다면 시스템이 멈추게 된다.
◦
문제는 연산의 전체 순서는 모든 연산은 모은 후에야 드러난다.
•
결론적으로 사용자명에 대해 유일성 제약 조건 같은 것을 구현하려면 연산의 전체 순서가 있는 것으로는 충분하지 않다.
3.4. 전체 순서 브로드캐스트
•
단일 리더 복제는 한 노드를 리더로 선택하고 리더의 단일 CPU 코어에서 모든 연산을 차례대로 배열함으로써 연산의 전체 순서를 정한다.
•
분산 시스템 분야에서 이 문제는 전체 순서 브로드캐스트(total order broadcast)나 원자적 브로드 캐스트(atomic broadcast)로 알려져 있다.
•
전체 순서 브로드캐스트는 보통 노드 사이에 메시지를 교환하는 프로토콜로 기술된다.
•
비공식적으로는 두 가지 안전성 속성을 항상 만족해야 한다.
◦
신뢰성 있는 전달(reliable delivery)
▪
어떤 메시지도 손실되지 않습니다. 메시지가 한 노드에 전달되면 모든 노드에도 전달된다.
◦
전체 순서가 정해진 전달(Totally ordered delivery)
▪
메시지는 모든 노드에 같은 순서로 전달된다.
3.4.1. 전체순서 브로드캐스트 사용하기
•
주키퍼나 etcd 같은 합의 서비스는 전체 순서 브로드캐스트를 실제로 구현한다.
•
모든 메시지가 데이터베이스의 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는상태를 유지한다.
◦
이 원리를 상태 기계 복제(state machine replication) 이라고 한다.
•
전체 순서 브로드캐스트는 직렬성 트랜잭션을 구현하는데도 쓸 수 있다.
◦
모든 노드가 메시지들을 같은 순서로 처리한다면 데이터베이스의 파티션과 복제본은 서로 일관적인 상태를 유지한다.
•
전체 순서 브로드캐스트의 중요한 특면은 메시지가 전달되는 시점에 그 순서가 고정된다는 것이다.
◦
이 때문에 전체 순서 브로드캐스트가 타임스탬프 순서화보다 강하다.
•
전체 순서 브로드캐스트를 보는 또 다른 관점은 로그를 만드는 방법 중 하나라는 것이다.
4. 분산 트랜잭션과 합의
•
합의는 분산 컴퓨팅에서 가장 중요하고 근본적인 문제 중 하나이며 목적은 여러 노드들이 뭔가에 동의하게 만드는 것이다.
•
노드가 동의하는 것이 중요한 상황
◦
리더 선출 = 단일 리더 복제를 사용하는 데이터베이스에서는 모든 노드는 어떤 노드가 리더인지를 동의해야 한다.
◦
원자적 커밋 = 트랜잭션 원자성을 유지하고 싶다면 모든 노드가 트랜잭션의 결과에 동의하게 만들어야 한다.
4.1. 원자적 커밋과 2단계 커밋(2PC)
•
트랜잭션 원자성의 목적은 여러 쓰기를 실행하는 도중 뭔가 잘못되는 경우에 간단한 시맨틱을 제공하기 위함이다.
•
트랜잭션의 결과는 커밋 성공이나 어보트입니다.
•
원자성은 실패한 트랜잭션이 절반만 완료된 결과나 절반만 갱신된 상태로 데이터베이스를 어지럽히는 것을 막아준다.
4.1.1. 단일 노드에서 분산 원자적 커밋으로
•
단일 데이터베이스 노드에서 실행되는 트랜잭션에게 원자성은 흔히 저장소 엔진에서 구현된다.
•
단일 노드에서 트랜잭션 커밋은 데이터가 디스크에 지속성 있게 쓰여지는 순서에 결정적으로 의존한다.
◦
커밋을 원자적으로 만들어주는 것은 단일 장치다.
•
트랜잭션에 여러 노드가 관여된다면 어떤 노드에서는 커밋이 성공하고 다른 노드에서는 실패해서 원자성 보장을 위반하기 쉽다.
◦
어떤 노드들은 제약 조건 위반이나 충도을 가짐해서 어브가 필요하게 되지만 다른 노드들은 성공적으로 커밋될 수 있다.
◦
어떤 커밋 요청은 네트워크에서 손실되어 타임아웃 때문에 결국 어보트되지만 다른 커밋 요청은 전달될 수 있다.
◦
어떤 노드는 커밋 레코드가 완전히 쓰여지기 전에 죽어서 복구할 때 롤백되지만 다른 노드는 성공적으로 커밋될 수 있다.
•
어떤 노드가 트랜잭션을 커밋하지만 다른 노드는 어보트한다면 노드들이 서로 일관성이 없어진다.
•
트랜잭션 커밋은 되돌릴 수 없어야하며 이 원칙은 "커밋 후 읽기"에서 설명한 커밋 후 읽기 격리의 기반을 형성한다.
•
커밋된 트랜잭션의 효과를 나중에 다른 보상 트랜잭션(compensating transaction) 이 취소하는 것은 가능하다.
4.1.2. 2단계 커밋 소개
•
2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장되는 알고리즘이다.
•
일부 데이터베이스는 2PCV가 내부적으로 사용되고 XA 트랜잭션의 형태나 SOAP 웹 서비스용 WS-AtomicTransaction을 통해 애플리케이션에서 사용할 수 있다.
2단계 커밋의 성공적인 실행
•
2PC는 단일 노드 트랜잭션에서는 보통 존재하지 않느 새로운 컴포넌트인 코디네이터를 사용한다.
•
2PC 트랜잭션에서 데이터베이스 노드를 트랜잭션의 참여자(participant) 라고 부른다.
•
애플리케이션이 커밋할 준비가 되면 코디네이터가 1단계를 시작하고, 각 노드에 준비 요청을 보내서 커밋할 수 있는지 물어본 뒤 그 후 코디네이터는 참여자들의 응답을 추적한다.
◦
모든 참여자가 커밋할 준비가 됐다는 뜻으로 "네"라고 응답하면 코디네이터는 2단계에서 커밋 요청을 보내고 커밋이 실제로 일어난다.
◦
함여자 중 누구라도 "아니오"로 응답하면 코디네이터는 2단계에서 모든 노드에 어보트 요청을 보낸다.
4.1.3. 약속에 관한 시스템
•
준비 요청과 커밋 요청은 2단계에서 경우에서 그냥 쉽게 손실될 수 있다.
◦
애플리케이션은 분산 트랜잭션을 시작할 때 코디네이터에게 트랜잭션 ID를 요청한다.
▪
이 트랜잭션 ID는 전역적으로 유일하다.
◦
애플리케이션은 발급받은 트랜잭션 ID를 가지고 각 참여자에서 단일 노드 트랜잭션을 시작한다.
▪
읽기와 쓰기는 이런 단일 노드 트랜잭션 중 하나에서 실행된다.
▪
이 단계에서 노드가 죽거나 타임아웃 등의 문제가 발생하면 코디네이터나 참여자 중 누군가 어보트할 수 있다.
◦
참여자가 준비 요청을 받으면 트랜잭션 커밋할 수 있는지 확인한다.
▪
가능하다고 판단이 되면 코디네이터에게 ‘네’라고 응답을 한다.
◦
코디네이터가 준비 요청에 대한 응답을 받은 후, 트랜잭션을 커밋할지 어보트 할지 최종적으로 결정한다.
▪
모든 참여자가 ‘네’에 투표했을 때만 커밋한다.
▪
코디네이터가 추후 죽을 수도 있으므로 결정을 디스크의 트랜잭션 로그에 기록하는데 이를 커밋 포인트라 한다.
◦
코디네이터가 최종 결정을 완료하였으니, 모든 참여자에게 커밋 또는 어보트 요청을 전송한다.
▪
이 요청이 실패하거나 타임아웃이 발생하면 성공할 때 까지 영원히 재시도해야 한다.
•
코디네이터가 한 번 결정하면 그 결정은 변경할 수 없다.
•
이러한 약속으로 2PC의 원자성을 보장한다.
4.1.4. 코디네이터 장애
•
코디네이터가 준비 요청을 보내기 전에 장애가 나면 참여자가 안전하게 트랜잭션을 어보트할 수 있다.
•
코디네이터로부터 트랜잭션이 커밋됐는지 회신을 받는 와중, 코디네이터가 죽거나 이 시점에 네트워크 장애가 나면 참여자는 기다릴 수 밖에 없으며 이 트랜잭션을 의심스럽다(in doubt) 혹은 불확실하다(uncertain) 라고 한다.
•
2PC가 완료할 수 있는 유일한 방법은 코디네이터가 복구되기를 기다리는 것 뿐이다.
◦
이때문에 코디네이터가 참여자들에게 커밋이나 어보트 요청을 보내기 전에 디스크에 있는 트랜잭션 로그에 자신의 커밋이나 어보트 결정을 써야하는 이유이다.
4.1.5. 3단계 커밋
•
2단계 커밋은 2PC가 코디네이터가 복구하기를 기다리느라 멈출 수 있다는 사실 때문에 블로킹 원자적 커밋 프로토콜이라고 부른다.
•
2PC의 대안으로 3단계 커밋(3PC)이라는 알고리즘이 제안되었다.
◦
논블로킹 원자적 커밋은 완벽한 장애 감지기(perfect failure detector) ,노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메커니즘이 필요하다.
◦
타임아웃은 신뢰성 잇는 장애 감지기가 아니다.
◦
이러한 이유로 2PC가 계속 사용된다.
