[데이터 중심 애플리케이션 설계] 일관성과 합의

내결함성을 지닌 분산 시스템을 구축하는 데 스이는 알고리즘과 프로토콜의 몇 가지 에를 얘기한다. 네트워크에서 패킷이 손실되고, 순서가 바뀌고, 중복되거나 임의의 시간 동안 지연이 발생할 수 있다. 시간은 최선을 다하더라도 근사치밖에 쓸 수 없다. 노드는 멈출 수 있고 언제라도 죽을 수 있다. 

 

내결함성을 지닌 시스템을 구축하는 가장 좋은 방법은 유용한 보장을 해주는 범용 추상화를 찾아 이를 구현하고 애플리케이션에서 이 보장에 의존하게 하는 것이다. 트랜잭션을 사용함으로써 애플리케이션은 충돌이 없고 다른 누구도 데이터베이스에 동 시 접근하지 않으며 저장 서비스는 완전히 믿을 수 있는 것처럼 행동할 수 있다. 충돌, 경쟁 조건, 디스크 장애가 발생하더라도 트랜잭션 추상화가 이런 문제들을 숨겨서 애플리케이션이 걱정하지 않게 해준다.

 

분산 시스템에 가장 중요한 추상화 중 하나는 합의, 즉 모든 노드가 어떤 것에 동의하게 만드는 것이다. 합의 관련 문제를 해결하는 알고리즘을 살펴본다. 먼저 분산 시스템에서 제공될 수 있는 보장과 추상화의 범위를 알아본다.

일관성 보장

복제 데이터베이스는 대부분 최소한 최종적 일관성을 제공한다. 시간이 지나면 모든 읽기는 같은 값을 반환하지만, 업데이트 시에 불일치가 일시적으로 생길 수 있다. 

이것은 매우 약한 보장이다. 언제 복제본이 수렴될지에 대해서는 아무것도 얘기하지 않는다.

최종적 일관성은 보통의 단일 스레드 프로그램에 있는 변수의 동작과 매우 다르므로 애플리케이션 개발자에게 어렵다.

 

트랜잭션 격리는 주로 동시에 실행되는 트랜잭션 때문에 발생하는 경쟁 조건을 회피하는 것에 관한 것이지만 분산 일관성은 대개 지연과 결함이 있더라도 복제본의 상태를 코디네이션하는 것에 관한 것이다.

선형성

데이터베이스가 복제본이 하나만 있다는 환상을 만들어준다면 훨씬 더 단순하지 않을까?

그러면 모든 클라이언트는 똑같은 데이터를 보고 복제 지연을 걱정할 필요가 없다.

 

이것이 선형성을 뒷받침하는 아이디어다. 기본 아이디어는 시스템에 데이터 복사본이 하나만 있고 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것이다.

 

선형성 시스템에서는 클라이언트가 쓰기를 성공적으로 완료하자마자 그 데이터베이스를 읽는 모든 클라이언트는 방금 쓰여진 값을 볼 수 있어야 한다.

 

선형성은 최신성 보장이다. 

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

시스템에 데이터 복사본이 하나뿐인 것처럼 보이게 만드는 것이다.

모든 요청과 응답 시점을 기록하고 그것들이 유효한 순차 순서로 배열되는지 확인함으로써 시스템의 동작이 선형적인지 테스트할 수도 있다.

 

선형성 대 직렬성

직렬성: 모든 트랜잭션이 여러 객체를 읽고 쓸 수 있는 상황에서의 트랜잭션들의 격리 속성. 쿼리에 대한 순서를 보장한다.

선형성: 실행되는 읽기와 쓰기에 대한 최신성 보장. 선형성은 연산을 트랜잭션으로 묶지 않아서 충돌 구체화 같은 부가적인 수단을 사용하지 않으면 쓰기 스큐 같은 문제를 막지 못한다.

데이터베이스는 직렬성과 선형성 모두를 제공할 수 있으며 이를 엄격한 직렬성이라 한다. 2단계 잠금이나 실제적인 직렬 실행을 기반으로 한 직렬성 구현은 보통 선형적이다.

직렬성 스냅숏 격리는 선형적이지 않다. 읽는 쪽과 쓰는 쪽 사이의 잠금 경쟁을 피하기 위해 일관된 스냅숏에서 읽는다. 일관된 스냅숏의 요점은 스냅숏에 스냅숏보다 나중에 실행된 쓰기를 포함하지 않는다는 것이고 따라서 스냅숏에서 읽으면 선형적이지 않다.

 

선형성에 기대기

어떤 환경에서 선형성이 필요할까?

시스템이 올바르게 동작하도록 만들기 위해 선형성이 중요한 요구사항이 되는 몇 가지 있다.

잠금과 리더 산출

단일 리더 복제를 사용하는 시스템은 리더가 여러 개가 아니라 진짜로 하나만 존재하도록 보장해야 한다. 리더를 선출하는 한 가지 방법은 잠금을 사용하는 것이다. 이는 선형적이어야 한다.

분산 잠금과 리더 선출을 구현하기 위해 아파치 주키퍼나 etcd 같은 코디네이션 서비스가 종종 사용된다. 이들은 합의 알고리즘을 사용해 선형성 연산을 내결함성이 있는 방식으로 구현한다.

분산 잠금은 오라클 리얼 애플리케이션 클러스터 같은 분산 데이터베이스에서 훨씬 세분화된 수준으로 사용되기도 한다. 

제약 조건과 유일성 보장

유일성 제약 조건은 데이터베이스에서 흔하다.

이는 잠금과 비슷하다. 사용자가

서비스에 가입할 때 그들이 선택한 사용자명에 "잠금"을 획득하는 것으로 생각할 수 있다. 그 연산은 원자적 compare-and-set과도 매우 비슷하다. 사용자명이 이미 점유되지 않았다면 요구한 사용자의 ID에 해당 사용자명을 설정한다.

 

관계형 데이터베이스에서 전형적으로 볼 수 있는 엄격한 유일성 제약 조건은 선형성이 필요하다.

채널 간 타이밍 의존성

선형성의 최신성 보장이 없으면 두 채널 사이에서 경쟁 조건이 발생할 수 있다. 

선형성 시스템 구현하기

데이터 복사본 하나만 사용하는 것이다. 그러나 이 방법으로는 결함을 견뎌낼 수 없다. 내결함성을 지니도록 만드는 가장 흔한 방법은 복제를 사용하는 것이다.

복제 방법들 중에 선형적인게 뭐가 있을까?

단일 리더 복제(선형적이 될 가능성이 있음): 망상에 빠진 리더가 계속 요청을 처리하면 선형성을 위반. 비동기 복제 사용시 장애 복구를 할 때 커밋된 쓰기가 손실될 수 있음.

합의 알고리즘(선형적): 주키퍼, etcd

다중 리더 복제(비선형적): 비동기로 다른 노드에 복제

리더 없는 복제(아마도 비선형적): 일 기준 시계를 기반으로 한 "최종 쓰기 승리" 충돌 해소 방법은 거의 확실히 비선형적.

선형성과 정족수

다이나모 스타일 모델에서 엄격한 정족수를 사용한 읽기 쓰기는 선형적인 것처럼 보인다. 그러나 다이나모 스타일 복제를 하는 리더 없는 시스템은 선형성을 제공하지 않는다고 보는 게 가장 안전하다.

선형성의 비용

두 데이터센터 사이에 네트워크가 끊기면 무슨 일이 생길지 생각해 보자.

다중 리더 데이터베이스를 사용하면 각 데이터센터는 계속 정상 동작할 수 있다.

단일 리더 복제를 사용하면 리더가 데이터센터 중 하나에 있어야만 한다.

단일 리더 설정에서 데이터센터 사이의 네트워크가 끊기면 선형성 읽기를 할 수 없다. 

CAP 정리

애플리케이션에서 선형성을 요구하고 네트워크 문제 때문에 일부 복제 서버가 다른 복제 서버와 연결이 끊기면 일부 복제 서버는 연결이 끊긴 동안은 요청을 처리할 수 없다.

애플리케이션이 선형성을 요구하지 않는다면 각 복제 서버가 다른 복제 서버와 연결이 끊기더라도 독립적으로 요청을 처리하는 방식으로 쓰기를 처리할 수 있다.

선형성이 필요 없는 애플리케이션은 네트워크 문제에 더 강인하다. 이 통찰력은 에릭 브루어가 이름 붙인 CAP 정리로 알려져있다. 

선형성과 네트워크 지연

현실에서 선형적인 시스템은 드물다. CPU와 램도 선형성을 손실해야 성능 개선이 생긴다. 다중코어 메모리 일관성 모델을 정당화하기 위해 CAP 정리를 쓰는 것은 말이 안된다. 선형적 제거의 이유는 성능이다. 분산 데이터베이스도 마찬가지다. 내결함성 때문이 아니라 성능 때문이다. 선형성은 느리다. 그리고 이것은 네트워크 결함이 있을 때만 그런 게 아니라 항상 참이다.

효율적인 선형 저장소 구현을 찾을 수 없을까?

선형성을 원하면 읽기와 쓰기 요청의 응답 시간이 적어도 네트워크 지연의 불확싱성에 비례해야 함이 증명됐다. 

순서화 보장

순서화, 선형성, 합의 사이에는 깊은 연결 관계가 있다. 

순서화와 인과성

순서화가 인과성을 보존하는 데 도움을 준다.

인과성은 이벤트에 순서를 부과한다. 결과가 나타나기 전에 원인이 발생한다. 시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적이라고 한다. 

인과적 순서가 전체 순서는 아니다

전체 순서는 어떤 두 요소를 비교할 수 있게 하므로 두 요소가 있으면 항상 어떤 것이 더 크거 어던 것이 더 작은지 말할 수 있다. 자연수는 전체 순서를 정할 수 있다.

전체 순서와 부분 순서의 차이점은 다른 데이터베이스 일관성 모델에 바녕ㅇ된다.

선형성: 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다.

인과성: 두 연산 중 어떤 것도 다른 것보다 먼저 실행되지 않았다면 두 연산이 동시적이라고 말했다. 두 이벤트에 인과적인 관계가 있으면 이들은 순서가 있지만 이들은 동시에 실행되면 비교할 수 없다. 인과성이 전체 순서가 아닌 부분 순서를 정의한다는 것이다.

 

선형성 데이터스토어에는 동시적 연산이 없다. 하나의 타임라인이 있고 모든 연산은 그 타임라인을 따라서 전체 순서가 정해져야 한다.

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

인과적 순서와 선형성 사이에는 어떤 관계가 있을까? 그 답은 선형성은 인과성을 내포한다.

선형성이 인과성을 보장한다는 사실은 선형성 시스템을 이해하기도 쉽고 매력적으로 보이게 만들어 준다. 선형적으로 만들면, 특히 시스템의 네트워크 지연이 크면 성능과 가용성에 해가 될 수 있다. 그래서 선형성을 포기하고 성능을 달성한다.

절충이 가능하다.

인과적 일관성은 네트워크 지연 때문에 느려지지 않고 네트워크 장애가 발생해도 가용한 일관성 모델 중 가장 강한 것이다.

선형성이 필요한 것처럼 보이는 시스템에 사실 진짜로 필요한 것은 인과적 일관성이며 이는 더 효율적으로 구현될 수 있다. 이 연구는 아주 최근의 것이라 아직 많은 부분이 프로덕션 시스템에 반영되지 않았고 극복해야 할 도전 과제가 여전히 있다. 미래의 시스템에 유망한 방향이다.

인과적 의존성 담기

인과성을 유지하기 위해 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다.

전체 데이터베이스에 걸친 인과적 의존성을 추적해야 한다. 이를 위해 버전 벡터를 일반화할 수 있다.

인과적 순서를 결정하기 위해 데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야 한다.

일련번호 순서화

모든 인과적 의존성을 실제로 추적하는 것은 실용성이 떨어진다.

여러 애플리케이션에서 클라이언트는 뭔가를 쓰기 전에 많은 데이터를 읽고, 쓰기가 이전의 모든 읽기에 인과적으로 의존하는지 아니면 일부 읽기에만 의존하는지 명확하지 않다. 읽는 데이터를 모두 명시적으로 추적하는 것은 오버헤드가 크다.

 

일련번호나 타임스탬프를 써서 이벤트의 순서를 정할 수 있다. 많은 문제가 생길 수 있는 물리적 시계(일 기준 시계)에서 얻을 필요가 없다. 대신 논리적 시계에서 얻어도 된다. 논리적 시계는 연산을 식별하는 일련번호를 생성하는 알고리즘이고 보통 모든 연산마다 증가하는 카운터를 사용한다. 이런 일련번호나 타임스탬프는 크기가 작고 전체 순서를 제공한다.

 

특히 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다. 연산 A가 B보다 인과적으로 먼저 실행됐다면 A는 전체 순서에서도 B보다 먼저다. 동시 연산은 순서가 제멋대로일 수 있다. 이런 전체 순서는 인과 정보를 모두 담지만 인과성에 꼭 필요한 것보다 순서화를 더 부과한다.

 

단일 리더 복제를 쓰는 데이터베이스에서는 복제 로그가 인과성에 일관적인 쓰기 연산의 전체 순서를 정의한다. 리더는 연산마다 카운터를 증가시키고 복제 로그의 각 연산에 단조 증가하는 일련번호를 할당하기만 하면 된다. 팔로워가 복제 로그에 나오는 순서대로 쓰기를 적용하면 팔로워의 상태는 언제나 인과성에 일관적이다.

비인과적 빌련번호 생성기

단일 리더가 없다면 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않는다. 현실에서는 다양한 방법이 사용된다.

• 각 노드가 자신만의 독립적인 일변번호 집합을 생성할 수 있다. 한 노드는 홀수, 다른 노드는 작수 생성.
• 각 연산에 일 기준 시계에서 얻은 타임스탬프를 붙일 수 있다. 이런 타임스탬프는 순차적이지 않지만 해상도가 충분히 높다면 연산의 전체 순서를 정하는 데 충분할 수 있다.
• 일련번호 블록을 미리 할당. 노드 A는 1 ~1000, B는 1001 ~ 2000까지 블록을 차지. 이것들은 연산마다 고유한 근사 증가 일련번호를 생성한다. 그러나 생성한 일련번호가 인과성에 일관적이지 않다.

위 세 가지 선택지는 잘 동작하며, 카운터를 증가시키는 단일 리더에 모든 연산을 밀어넣는 것보다 확장성이 좋다. 이것들은 연산마다 고유한 근사 증가 일련번호를 생성한다. 그러나 생성한 일련번호가 인과성에 일관적이지 않다.

인과성 문제는 이런 일련번호 생성기들이 여러 노드에 걸친 연산들의 순서를 올바르게 담지 못하기 때문에 발생한다.

• 각 노드는 초당 연산수가 다를 수 있다. 한 노드가 짝수를 생성하고 다른 노드가 홀수를 생성하면 짝수용 카운터가 홀수용 카운터보다 뒤처지거나 반대 상황이 발생할 수 있다. 홀수 연산과 짝수 연산이 있을 때 어떤 것이 인과적으로 먼저 실행됐는지 정확히 알 수 없다.
• 물리적 시계에서 얻은 타임스탬프는 시계 스큐에 종속적이어서 인과성에 일관적이지 않게 될 수 있다. 인과적으로 나중에 실행된 연산이 실제로 더 낮은 타임스탬프를 받을 수 있다.
• 블록 할당자의 경우 한 연산이 1001과 2000 사이의 구간에서 일련번호를 받고 인과적으로 나중에 실행되는 연산이 1과 1000사이의 구간에서 일련번호를 받을 수도 있다. 

램포트 타임스탬프

위에 설명한 세 가지 일련번호 생성기는 인과성에 비일관적이지만 인과성에 일관적인 일련번호를 생성하는 간단한 방법이 있다.

레슬리 램포트가 1978년에 한 논문에서 제안한 방법, 램포트 타임스탬프. 분산 시스템에서 가장 많이 인용된 논문이다.

 

각 노드는 고유 식별자를 갖고 각 노드는 처리한 연산 개수를 카운터로 유지한다. 램포트 타임스탬프는 그냥 (카운터, 노드ID)의 쌍이다. 두 노드는 때때로 카운터 값이 같을 수 있지만 타임스탬프에 노드 ID를 포함시켜서 각 타임스탬프는 유일하게 된다.

 

물리적 일 기준 시계와 아무 관련이 없지만 전체 순서화를 제공.

카운터가 큰 것이 타임스탬프가 크다.

카운터 값이 같으면 노드 ID가 큰 것이 타임스탬프다.

 

핵심 아이디어

• 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다.
• 노드가 자신의 카운터 값보다 큰 최대 카운터를 가진 요청이나 응답을 받으면 바로 자신의 카운터를 그 최댓값으로 증가시킨다.

모든 연산에 최대 카운터 값이 따라다니는 한 이 방법은 램포트 타임스탬프로부터 얻은 순서가 인과성에 일관적이도록 보장해준다.

버전 벡터와 혼동되기도 하는데 목적이 다르다.

버전 벡터는 두 연산이 동시적인지 또는 어떤 여산이 다른 연산에 인과적으로 의존하는지 구별.

램포트 타임스탬프는 항상 전체 순서화를 강제.

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

램포트 타임스탬프가 인과성에 일관적인 여산의 전체 순서를 정의하지만 분산 시스템의 여러 공통 문제를 해결하는 데 아주 충분하지는 않다.

예를 들어 사용자명으로 유일한 식별자를 선택할 경우, 사용자명이 동일한 두 개의 계정이 생성되면 타임스탬프가 더 낮은 것을 성공한 것으로 선택하고 타임스탬프가 더 큰 것은 실패한다. 타임스탬프는 전체 순서를 정할 수 있으므로 이 비교는 항상 유효하다.

이 방법은 사후에 성공하는 쪽을 결정하는 데는 효과적이다.

그러나 노드가 사용자로부터 사용자명 생성 요청을 막 받고 그 요청이 성공해야 하는지 실패햐야 하는지 당장 결정해야 하할 때는 이 방법으로는 부족하다.

다른 어떤 노드도 동시에 더 낮은 타임스탬프를 가지고 동일한 사용자명으로 계정 생성을 처리하는 중이 아니라고 확신하려면 다른 모든 노드가 무엇을 하고 잇는지 확인해야 한다. 다른 모드 중 하나에 장애가 생기거나 네트워크 문제 때문에 연결할 수 없다면 시스템이 멈추게 된다.

여기서의 문제는 연산의 전체 순서는 모든 연산을 모은 후에야 드러난다는 것이다. 다른 노드가 어떤 연산을 생성했지만 그것이 무엇인지 아직 알 수 없다면 연산의 최종 순서를 만들어낼 수 없다. 다른 노드에서 실행되는 미지의 연산을 전체 순서의 여러 위치에 끼워넣어야 할지도 모른다.

사용자명에 대한 유일성 제약 조건 같은 것을 구현하려면 연산의 전체 순서가 있는 것으로는 충분치 않다. 언제 그 순서가 확정되는지도 알아야 한다.

전체 순서 브로드캐스트

분산 시스템에서는 모든 노드에서 연산의 전체 순서가 동일하도록 합의하기가 까다롭다. 타임스탬프나 일련번호를 사용한 순서화를 설명했지만 단일 리더 복제만큼 강력하지 않았다. 타임스탬프 순서화로를 사용해 유일성 제약 조건을 구현하면 어떤 결함도 버틸 수 없다.

 

단일 리더 복제는 한 노드를 리더로 선택하고 리더의 단일 CPU 코어에서 모든 연산을 차례대로 배열함으로써 연산의 전체 순서를 정한다. 어려운 문제는 처리량이 단일 리더가 처리할 수 있는 수준을 넘어설 때 시스템을 어떻게 확장할 것인가와 리더에 장애가 발생했을 때 어떻게 장애 복구를 처리할 것인가다. 분산 시스템 분야에서 이 문제는 전체 순서 브로드캐스트나 원자적 브로드캐스트로 알려져 있다.

 

전체 순서 브로드캐스트는 보통 노드 사이에 메세지를 교환하는 프로토콜로 기술된다. 비공식적으로는 두 가지 안전성 속성을 항상 만족해야 한다.

• 신뢰성 있는 전달
  • 어떤 메세지도 손실되지 않는다. 메세지가 한 노드에 전달되면 모든 노드에도 전달된다.
• 전체 순서가 정해진 전달
  • 메세지는 모든 노드에 같은 순서로 전달된다.

전체 순서 브로드캐스트를 구현하는 올바른 알고리즘은 노드나 네트워크에 결함이 있더라도 신뢰성과 순서화 속성이 항상 만족되도록 보장해야 한다. 네트워크가 끊긴 동안 메세지를 전달할 수 없지만 복구되면 전달되고 올바른 순서로 전달해야 한다.

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

주키퍼나 etcd 같은 합의 서비스는 전체 순서 브로드캐스트 실제로 구현한다. 이 사실은 전체 순서 브로드캐스트와 합의 사이에는 강한 연관이 있다는 것을 암시한다.

 

전체 브로드캐스트는 데이터베이스 복제에 딱 필요한 것이다. 모든 메세지가 데이터베이스에 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태를 유지한다. 이 원리를 상태 기계 복제라고 한다.

 

전체 순서 브로드캐스트는 직렬성 트랜잭션을 구현하는 데도 쓸 수 있다. 모든 메세지가 스토어드 프로시저로 실행되는 결정적 트랜잭션을 나타낸다면, 그리고 모든 노드가 그 메세지들을 같은 순서로 처리한다면 데이터베이스의 파티션과 복제본은 서로 일관적인 상태를 유지한다.

 

전체 순서 브로드캐스트의 중요한 측면은 메세지가 전달되는 시점에 그 순서가 고정된다는 것이다. 후속 메세지가 이미 전달됐다면 노드는 그 순서의 앞에 메세지를 소급적으로 끼워넣는 게 허용되지 않는다. 이 사실 때문에 전체 수서 브로드캐스트가 타임스탬프 순서화보다 강하다.

 

전체 순서 브로드캐스트를 보드 또 다른 관점은 로그를 만드는 방법 중 하나라는 것이다. 메세지 전달은 로그에 추가하는 것과 비슷하다. 모든 노드가 같은 메세지를 같은 순서로 전달해야 하므로 모든 노드는 로그를 읽어서 순서가 동일한 메세지를 볼 수 있다.

 

전체 순서 브로드캐스트는 펜싱 토큰을 제공하는 잠금 서비스를 구현하는데도 유용하다. 잠금을 획득하는 모든 요청은 메세지로 로그에 추가되고 모든 메세지들은 로그에 나타난 순서대로 일련번호가 붙는다. 그러면 일련번호는 단조 증가하므로 펜싱 토큰의 역할을 할 수 있다. 주키퍼에서는 이 일련번호를 zxid라고 한다.

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

선형성 시스템에는 연산의 전체 순서가 있다. 이게 선형성이 전체 순서 브로드캐스트와 같다는 뜻일까?

전체 순서 브로드캐스트는 비동기식이다. 메세지는 고정된 순서로 신뢰성 있게 전달되도록 보장되지만 언제 메세지가 전달될지는 보장되지 않는다. 반대로 선형성은 최신성을 보장한다. 읽기가 최근에 쓰여진 값을 보는 게 보장된다.

 

그러나 전체 순서 브로드캐스트 구현이 있다면 이를 기반으로 한 선형성 저장소를 만들 수 있다. 예를 들어 사용자명으로 사용자 계정을 유일하게 식별하도록 보장할 수 있다.

 

사용 가능한 모든 사용자명마다 compare-and-set 원자적 연산이 구현된 선형성 저장소를 가질 수 있다록 상상해 보자. 모든 레지스터는 초기에 널 값을 갖는다. 사용자가 사용자명을 생성하기를 원할 때 해당 사용자명에 해당하는 레지스터에 compare-and-set 연상을 실행해 레지스터의 이전 값이 널이라는 조건하에 그 값을 사용자 계정 ID로 설정한다. 여러 사용자가 동시에 같은 사용자명을 가지려고 사면 compare-and-set 연삼 중 하나만 성공한다. compare-and-set 여난은 널이 아닌 값을 보게 되기 때문이다.

 

전체 순서 브로드캐스트를 추가 전용 로그로 사용해 선형성 compare-and-set 연산을 다음과 같이 구현할 수 있다.

• 1. 메세지를 로그에 추가해서 점유하기 원하는 사용자명을 시험적으로 가리킨다.
• 2. 로그를 읽고 추가한 메세지가 되돌아오기를 기다린다.
• 3. 원하는 사용자명을 점유하려고 하는 메세지가 있는지 확인한다. 원하는 사용자명에 해당하는 첫 번째 메세지가 자신의 메세지라면 성공한 것이다. 사용자명 획득을 커밋하고 클라이언트에게 확인 응답을 보낼 수 있다. 원하는 사용자명에 해당하는 첫 번째 메세지가 다른 사용자가 보낸 것이라면 연산을 어보트시킨다.

로그 항목은 모든 노드에 같은 순서로 너달되므로 여러 개의 쓰기가 동시에 실행되면 모든 노드가 엌던 쓰기가 먼저 실행된 것이지 동의한다. 충돌하는 쓰기 중 첫 번째 것을 승자로 택하고 나머지를 어보트시키면 모든 노드는 쓰기가 커밋되거나 어보트되는지에 동의하게 된다. 로그를 기반으로 직렬성 다중 객체 트랜잭션을 구현할 때도 비슷한 방법을 쓸 수 있다.

 

선형성 쓰기를 보장하지만 선형성 읽기는 보장하지 않는다. 읽기를 선형적으로 만들기 위한 선택지가 있다.

• 로그를 통해 순차 읽기를 할 수 있다. 로그 메세지를 추가하고 로그를 읽어서 메세지가 되돌아왔을 때 실제 읽기를 수행하면 된다. 따라서 로그 상의 메세지 위치는 읽기가 실행된 시점을 나타낸다.
• 로그에서 최신 로그 메세지의 위치를 선형적 방법으로 얻을 수 있다면 그 위치를 질의하고 그 위치까지의 모든 항목이 전달되기를 기다린 후 읽기를 수행할 수 있다. 주키퍼의 sync() 연산의 기반이 되는 아이디어다.
• 쓰기를 실행할 때 동기식으로 갱신돼서 최신이 보장되는 복제 서버에서 읽을 수 있다.

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

지난 절에서 전체 순서 브로드캐스트로부터 선형성 compare-and-set 연산을 구현하는 방법을 봤다. 그 반대로 선형성 저장소가 있을 떄 이를 기반으로 전체 순서 브로드캐스트를 구현하는 것도 가능하다. 

가장 쉬운 방법은 정수를 저장하고 원자적 increment-and-get 연산이 지원되는 선형성 레지스터가 있다고 가정하는 것이다. 대신 원자적 compare-and-set 연산이 있어도 된다.

알고리즘은 간단하다. 전체 순서 브로드캐스트를 통해 보내고 싶은 모든 메세지에 대해 선형성 정수로 increment-and-get 연산을 수행하고 레지스터에서 얻은 값을 일련번호로 메세지에 붙인다. 램포트 타임스탬프와 달리 선형성 레지스터를 증가시켜서 얻은 숫자들은 틈이 없는 순열을 형성한다. 따라서 어떤 노드가 메세지 4를 전달하고 일련번호 6인 메세지를 받았다면 메세지 6을 전달하기 전에 메세지 5를 기다려야 한다는 것을 알 수 있다.

분산 트랜잭션과 합의

비공식적으로 합의의 목적은 여러 노드들이 뭔가에 동의하게 만드는 것이다.

노드가 동의하는 것이 중요한 상황이 다음과 같이 많이 있다.

 

리더 선출

단일 리더 복제를 사용하는 데이터베이스에서 모든 노드는 어떤 노드가 리더인지 동의해야 한다. 어떤 노드가 네트워크 결함 때문에 다른 노드와 통신할 수 없으면 리더십 지위를 놓고 경쟁할 수 있다. 이 경우 합의는 두 노드가 자신이 리더라고 생각하는 스플릿 브레인을 유발할 수 있는 잘못된 장애 복구를 피하는데 중요하다. 

 

원자적 커밋

여러 노드나 파티션에 걸친 트랜잭션을 지원하는 데이터베이스에는 트랜잭션이 어떤 노드에서는 성공하고 어떤 노드에서는 실패할 수도 있는 문제가 있다. 트랜잭션 원자성을 유지하고 싶다면 모든 노드가 트랜잭션의 결과에 동의하게 만들어야 한다. 뭔가 잘못되면 모두 어보트/롤백되거나 모두 커밋된다. 이런 합의 문제를 원자적 커밋 문제라고 한다.

 

원자적 커밋을 해결하는 가장 흔한 방법이고 다양한 데이터베이스, 메세징 시스템, 애플리케이션 서버에서 구현된 2단계 커밋 알고리즘을 다룬다. 2PC를 배워 주키퍼(Zab)와 etcd(Raft)에서 쓰이는 더 좋은 합의 알고리즘을 본다.

원자적 커밋과 2단계 커밋

원자성을 실패한 트랜잭션이 절반만 완료된 결과나 절반만 갱신된 상태로 데이터베이스를 어지럽히는 것을 막아준다. 원자성은 보조 색인이 주 데이터와 일관성을 유지하도록 보장한다.

단일 노드에서 분산 원자적 커밋으로

단일 데이터베이스 노드에서 실행되는 트랜잭션에게 원자성은 흔히 저장소 엔진에서 구현된다.

따라서 단일 노드에서 트랜잭션 커밋은 데이터가 디스크에 지속성 있게 쓰여지는 순서에 결정적으로 의존한다. 트랜잭션이 커밋되거나 어보트되는지를 결정하는 핵심적인 시점은 디스크가 커밋 레코드 쓰기를 마치는 시점이다. 그 시점 전에는 아직 어보트될 가능성이 있지만 그 시점 후에는 트랜잭션이 커밋된 상태다. 따라서 커밋을 원자적으로 만들어주는 것은 단일 장치(특정 하나의 노드에 부착된 하나의 특정 디스크 드라이버의 컨트롤러)다.

 

그러나 트랜잭션에 여러 노드가 관여한다면 어떻게 될까? 파티셔닝된 데이터베이스에서 다중 객체 트랜잭션을 쓰거나 용어 파티션닝된 보조 색인을사용할 수 있다. 이런 경우 각 노드에서 독립적으로 트랜잭션을 커밋하는 것으로는 충분치 않다.

어떤 노드에서는 커밋이 성공하고 다른 노드에서는 실패해서 원자성 보장을 위반하기 쉽다.

2단계 커밋 소개

2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘이다. 

2PC는 단일 노드 트랜잭션에서는 보통 존재하지 않는 새로운 컴포넌트인 코디네이터를 사용한다. 코디네이터는 종종 트랜잭션을 요청하는 애플리케이션 프로세스 내에서 라이브러리 형태로 구현되지만 분리된 프로세스나 서비스가 될 수도 있다.

 

2PC 트랜잭션은 평상시처럼 애플리케이션이 여러 데이터베이스 노드에서 데이터를 읽고 쓰면서 시작한다. 이런 데이터베이스 노드를 트랜잭션의 참여자라고 부른다. 애플리케이션이 커밋할 준비가 되면 코디네이터가 1단계를 시작한다. 각 노드에 준비 요청을 보내서 커밋할 수 있는지 물어본다. 그 후 코디네이터는 참여자들의 응답을 추적한다.

• 모든 참여자가 커밋할 준비가 됐다는 뜻으로 '네'로 응답하면 코디네이터는 2단계 커밋 요청을 보내고 커밋이 실제로 일어난다.
• 참여자 중 누구라도 '아니오'로 응답하면 코디네이터는 2단계에서 모든 노드에 어보트 요청을 보낸다.

약속에 관한 시스템

이 프로토콜에는 두 개의 중대한 '돌아갈 수 없는 지점'이 있다. 참여자는 '네'에 투표할 때 나중에 분명히 커밋할 수 있을 거라고 약속한다. 그리고 코디네이터가 한 번 결정하면 그 결정은 변경할 수 없다. 이런 약속은 2PC 원자성을 보장한다.

개별 노드가 '네'라고 대답을 한 순간 코디네이트로 부터 'OK'를 듣지 못하고 죽더라도 나중에 복구 될 경우 코디네이터에게 전역 트랜잭션 ID의 상태를 질의해서 커밋했는지 아닌지 확인할 수 있다.

코디네이터 장애

코디네이터가 죽었을 때 2PC가 완료할 수 있는 유일한 방법은 코디네이터가 복구되기를 기다리는 것뿐이다.

3단계 커밋

2단계 커밋은 2PC가 코디네이터가 복구하기를 기다리느라 멈출 수 있다는 사실 때문에 블로킹 원자적 커밋 프로토콜이라고 불린다. 이론상으로는 노드에 장애가 나도 멈추기 않도록 원자적 커밋 프로토콜을 논블로킹하게 만들 수 있다.

 

3PC는 2PC의 대안으로 기약 없는 네트워크 지연과 프로세스 중단이 있는 대부분의 실용적 시스템에서 3PC는 원자성을 보장하지 못한다.

 

일반적으로 논블로킹 원자적 커밋은 완벽한 장애 감지기, 즉 노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메커니즘이 필요하다. 기약 없는 지연이 있는 네트워크에서 타임아웃은 신뢰성 있는 장애 감지기가 아니다. 아무 노드도 안 죽었지만 네트워크 문제 떄문에 요청이 타임아웃될 수 있기 때문이다.

현실의 분산 트랜잭션

분산 트랜잭션, 특히 2단계 커밋으로 구현된 분산 트랜잭션은 평판이 엇갈린다. 안전성 보장을 제공하는 것과 운영상의 문제를 일으키고 성능을 떨어뜨린다. 여러 클라우드 서비스들은 분산 트랜잭션이 낳은 운영상 문제 때문에 분산 트랜잭션을 구현하지 않는 선택을 한다.

 

그러나 분산 트랜잭션을 완전히 일축하기보다는 좀 더 자새히 조사해봐야 한다. 우선 "분산 트랜잭션"이 무엇을 의미하는지 정확히 해야 한다.

데이터베이스 내부 분산 트랜잭션

어떤 분산 데이터베이스는 데이터베이스 노드 사이에 내부 트랜잭션을 지원한다. 볼트DB, 마이SQL 클러스터의 NDB 저장소 엔진은 이런 내부 트랜잭션을 지원한다.

 

이종 분산 트랜잭션

이종 트랜잭션에서 참여자들은 둘 혹은 그 이상의 다른 기술이다. 이를테면 두 가지 서로 다른 벤더의 데이터베이스일 수도, 심지어 메세지 브로커처럼 비데이터베이스 시스템일 수도 있다. 이런 시스템에 걸친 분산 트랜잭션은 시스템의 내부가 완전히 다르더라도 원자적 커밋을 보장해야 한다.

 

데이터베이스 내부 분산 트랜잭션은 흔히 매우 잘 동작한다. 반면에 이종 기술에 걸친 트랜잭션은 훨씬 더 어렵다.

정확히 한 번 메세지 처리

이종 분산 트랜잭션은 다양한 시스템들이 강력한 방법으로 통합될 수 있게 한다. 예를 들어 메세지 큐에서 나온 메세지는 그 메세지를 처리하는 데이터베이스 트랜잭션이 커밋에 성공했을 때만 처리된 것으로 확인받을 수 있다.

메세지와 그 처리 과정의 부수 효과를 원자적으로 커밋함으로써 메세지가 결과적으로 정확히 한 번(exactly once) 처리되도록 보장할 수 있다. 성공하기 전에 몇 번 재시도가 필요할 수는 있겠지만 말이다. 어보트는 부분적으로 완료된 트랜잭션의 부수 효과를 폐기한다.

그렇지만 이런 분산 트랜잭션은 트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능하다.

XA 트랜잭션

XA(extended Architecture)는 이종 기술에 걸친 2단계 커밋을 구현하는 표준이다. XA는 네트워크 프로토콜이 아니라 트랜잭션 코디네이트와 연결되는 인터페이스를 제공하는 C API일 뿐이다. 

 

XA는 애플리케이션이 네트워크 드라이버나 클라이언트 라이브러리를 사용해 참여자 데이터베이스나 메세징 서비스와 통신한다고 가정한다. 드라이버가 XA를 지원한다는 것은 연산이 분산 트랜잭션의 일부가 돼야 하는지 알아내기 위해 XA API를 호출한다는 것을 뜻한다. 그리고 만약 그렇다면 드라이버는 데이터베이스 서버로 필요한 정보를 보낸다. 드라이버는 코디네이터가 참여자에게 준비, 커밋, 어보트를 요청할 수 있는 콜백도 제공한다.

의심스러운 상태에 있는 동안 잠금을 유지하는 문제

문제는 잠금이다. 데이터베이스는 트랜잭션이 커밋하거나 어보트할 때까지 이런 잠금을 해제할 수 없다. 2단계 커밋을 사용할 때 트랜잭션은 의심스러운 상태에 있는 동안 내내 잠금을 잡고 있어야 한다. 코디네이터가 죽어서 재시작하는 데 20분이 걸린다면 잠금은 20분 동안 유지된다.

코디네이터의 로그가 어떤 이유로 완전히 손실되면 이런 잠금은 영원히, 또는 적어도 관리자가 수동으로 상황을 해결할 때까지 유지횐다.

이런 잠금이 유지되는 동안 다른 어떤 트랜잭션도 그 로우를 변경할 수 없다.

동일한 데이터에 접근하려고 하면 차단된다. 이는 의심스러운 트랜잭션이 해소될 때까지 애플리케이션의 많은 부분을 사용할 수 없게 되는 원인이 된다.

코디네이터 장애에서 복구하기

코디네이터가 죽은 후 재시작하면 로그로부터 그 상태를 깨끗하게 복구하고 의심스러운 트랜잭션을 해소해야 한다. 그러나 고아가 된 의심스러운 트랜잭션, 즉 코디네이트가 어떤 이유 때문인지 그 결과를 결정할 수 없는 트랜잭션이 생길 수 있다(로그 손실, 소프트웨어 버그).

 

데이터베이스 서버를 재부팅해도 이 문제는 고칠 수 없다. 2PC의 올바른 구현은 재시작을 하더라도 의심스러운 트랜잭션의 잠금을 유지해야 하기 때문이다.

 

여기서 빠져나가는 유일한 방법은 관리자가 수동으로 트랜잭션을 커밋하거나 롤백할지 결정하는 것 뿐이다. 이 문제를 해결하려면 잠재적으로 많은 수작업이 필요하고, 대부분 심각한 서비스 중단이 있는 도중에 스트레스가 높고 시간 압박이 있는 상태에서 처리해야 할 가능성이 높다.

 

여러 XA 구현에는 참여자가 코디네이터로부터 확정적 결정을 얻지 않고 의심스러운 트랜잭션을 어보트하거나 커밋할지를 일방적으로 결정할 수 있도록 하는 경험적 결정이라고 부르는 비상 탈출구가 있다. 여기서 경험적은 2단계 커밋의 약속 체계를 위반하기 때문에 아마도 원자성을 깰 수 있다를 표현한 것이다. 경험적 결정은 큰 장애 상황을 벗어나고자 할 때만 쓰도록 의도된 것이다.

분산 트랜잭션의 제약

XA 트랜잭션은 여러 참여 데이터 시스템이 서로 일관성을 유지하게 하는 실제적이고 중요한 문제를 해결해 주지만 XA 트랜잭션도 운영상 문제를 가져온다. 트랜잭션 코디네이터 자체가 일종의 데이터베이스여야 한다는 점이고 다른 중요한 데이터베이스와 동일하게 신경 써서 접근해야 한다는 것이다.

• 코디네이터가 복제되지 않고 단일 방비에서만 실행되면 단일 장애점이 된다. 여러 코디네이터 구현은 기본적으로 고가용성을 제공하지 않거나 가장 기초적인 복제만 지원한다.
• 코디네이터가 애플리케이션 서버의 일부가 되면 배포의 특성이 바뀌게 된다. 코디네이터의 로그가 지속적인 시스템 상태의 중대한 부분이 된다. 코디네이터 로그는 죽은 후에 의심스러운 트랜잭션을 복구하기 위해 필요하므로 데이터베이스 자체만큼 중요하다 
• XA는 광범위한 데이터 시스템과 호환돼야 하므로 최소 공통 분모가 될 필요가 있다. 여러 시스템에 걸친 교착 상태를 감지할 수 없고, SSI와 함께 동작하지 않는다. SSI를 지원하려면 여러 시스템에 걸친 충돌을 식별할 프로토콜이 필요하기 때문이다.
• 분산 트랜잭션은 2PC가 성공적으로 커밋하려면 모든 참여자가 응답해야 하는데 이는 장애를 증폭시키는 경향이 있다. 내결함성을 지닌 시스템의 목적에 어긋난다.

이런 제약은 일관성을 포기해야 한다는 것 처럼 보인다. 그러나 대안이 있다.

내결함성을 지닌 합의

합의 문제는 다음과 같이 형식화된다. 하나 또는 그 이상의 노드들이 값을 제안할 수 있고 합의 알고리즘이 그 값 중 하나를 결정한다.

이 형식에서 합의 알고리즘은 다음 속성을 만족해야 한다.

균일한 동의

어떤 두 노드도 다르게 결정하지 않는다.

무결성

어떤 노드도 두 번 결정하지 않는다.

유효성

한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안된 것이다.

종료

죽지 않는 모든 노드는 결국 어떤 값을 결정한다.

 

균일한 동의와 무결성 속성은 합의의 핵심 아이디어를 정의한다.

유효성 속성은 주로 뻔한 해결책을 배제하기 위해 존재한다.

종료 속성은 내결함성의 아이디어를 형식화한다. 이 속성은 본질적으로 합의 알고리즘은 그냥 그 상태에 머물러서 영원히 아무것도 안 할 수는 없다. 어떤 노드에 장애가 나더라도 다른 노드들은 여전히 결정을 내려야 한다.

합의 시스템에서 노드가 죽으면 그 노드가 갑자기 사라져서 결코 돌아오지 않는다고 가정한다. 이 시스템 모델에서 노드가 복구되기를 기다리는 알고리즘은 어던 것이라도 종료 속성을 만족할 수 없다. 특히 2PC는 종료에 대한 요구사항을 만족하지 않는다.

종료를 보장하려면 과반수에 따른다.

대부분의 합의 알고리즘은 비잔틴 결함이 없다고 가정한다. 즉 노드가 프로토콜을 올바르게 따르지 않으면 프로토콜의 안전성 속성이 깨질지도 모른다. 1/3 미만의 노드만 비잔틴 결함이 있다면 비잔틴 결함에도 견고하도록 합의를 만들 수 있다.

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

내결함성을 지닌 합의 알고리즘 중 가장 널리 알려진 것은 뷰스탬프 복제, 팍소스, 라프트, 잽이다.

 

이 알고리즘 중 대다수는 실제로는 여기서 설명한 형식적 모델(동의, 무결성, 유효성, 종료 속성을 만족하면서 하나의 값을 제안하고 결정)을 직접 사용하지 않는다. 대신 값의 순차열에 대해 결정해서 전체 순서 브로드캐스트 알고리즘을 만든다.

 

전체 순서 브로드캐스트를 하려면 모든 노드에게 메세지가 정확히 한 번, 같은 순서로 전달돼야 한다는 점을 기억하자. 

• 합의의 동의 속성 때문에 모든 노드는 같은 메세지를 같은 순서로 전달하도록 결정한다.
• 무결성 속성 때문에 메세지는 중복되지 않는다.
• 유효성 속성 때문에 메세지는 오염되지 않고 난데없이 조작되지 않는다.
• 종료 속성 때문에 메세지는 손실되지 않는다.

단일 리더 복제와 합의

리더를 운영팀에 있는 사람이 수동으로 선택해서 설정한다면 독재자 방식의 알고리즘을 사용하는 것이다. 이런 시스템은 현실에서 잘 동작하지만 진행하기 위해 사람의 개입이 필요하므로 합의의 종료 속성을 만족하지 않는다.

리더 장애시 새로운 리더 선출 및 장애 복구를 하는 시스템도 있다. 내결함성을 지닌 전체 순서 브로드캐스트에 가까워지고 따라서 합의를 해결하는 데도 가까워진다. 그러나 스플릿 브레인 문제가 있다. 몯느 노드들이 누가 리더인지 동의해야 한다고 했다. 두 개의 다른 노드가 각자 자신이 리더라고 생각하고 결과적으로 데이터베이스가 일관성이 깨진 상태가 된다. 리더를 선출하려면 합의가 필요하다.

리더를 선출하려면 리더가 필요한 것 처럼 보인다. 합의를 해결하려면 먼저 합의를 해결해야 한다. 

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

합의 프로토콜은 모두 내부적으로 어떤 형태로든 리더를 사용하지만 리더가 유일하다고 보장하지 않는다.

 

현재 리더가 죽었다고 생각할 때 새 노드를 선출하기 위해 노드 사이에서 투표가 시작된다. 이 선출은 에포크 번호를 증가시키며 따라서 에포크 번호는 전체 순서가 있고 단조 증가한다. 두 가지 다른 에포크에 있는 두 가지 다른 리더 사이에 충돌이 있으면 에포크 번호가 높은 리더가 이긴다.

 

리더가 뭔가를 결정하도록 허용하기 전에 충돌되는 결정을 할지도 모르는 에포크 번호가 더 높은 다른 리더가 없는지 먼저 확인해야 한다.

 

노드의 정족수로부터 투표를 받아야 한다. 리더는 내리려고 하는 모든 결정에 대해 제안된 값을 다른 노드에게 보내서 노드의 정족수가 그 제안을 찬성한다고 응답하기를 기다려야 한다. 정족수는 항상은 아니지만 전형적으로 노드의 과반수로 구성된다. 노드는 에포크 번호가 더 높은 다른 리더를 알지 못할 때만 제안에 찬성하는 투표를 한다.

 

두번의 투표가 있다. 한 번은 리더를 선출하기 위해, 두 번째는 리더의 제안에 투표하기 위해서다. 중요한 것은 두 번의 투표를 하는 정족수가 겹쳐야 한다는 점이다.

 

이 투표 과정은 2단계 커밋과 비슷해 보인다. 차이는 2PC에서 코디네이터는 선출되지 않는다는 것과 2PC는 모든 참여자로부터 "네"투표가 필요하지만 내결함성을 지닌 합의 알고리즘은 노드의 과반수로부터만 투표를 받으면 된다는 것이다. 합의 알고리즘은 새로운 리더가 선출된 후 노드를 일관적인 상태로 만들어주는 복구 과정을 정의해서 안전성 속성이 항상 만족되도록 보장한다. 이런 차이점은 합의 알고리즘의 정확성과 내결함성의 핵심이다.

합의의 제약

제안이 결정되기 전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제다. 데이터베이스는 종종 비동기 복제를 사용하도록 설정된다. 이런 설정에서 커밋된 데이터는 장애 복구 시 잠재적으로 손실될 수 있다. 많은 사람들은 성능을 위해 위의 리스크를 감수한다.

 

합의 시스템은 엄격한 과반수가 동작하기를 요구한다. 대부분의 합의 알고리즘은 투표에 참여하는 노드 집합이 고정돼 있다고 가정한다. 클러스터에 노드 추가 및 제거가 안된다. 합의 알고리즘의 동적 멤버쉽 확장은 클러스터에 있는 노드 집합이 시간이 지남에 따라 바뀌는 것을 허용하지만 정적 멤버쉽보다 훨씬 더 이해하기 어렵다.

 

합의 시스템은 장애 노드를 감지하기 위해 타임아웃에 의존한다. 합의 알고리즘은 네트워크 문제에 민감하다. 전체 네트워크가 올바르게 동작하지만 특정 네트워크 링크 하나가 끊임없이 불안정하다면 라프트는 리더십이 두 노드 사이에서 지속적으로 왔다 갔다 하거나 현재 리더가 꾸준히 리더에서 강제로 내려오는 상황이 발생해서 시스템이 사실상 전혀 진행하지 못할 수 있다. 다른 합의 알고리즘도 비슷한 문제가 있고 신뢰성이 없는 네트워크에 더욱 견고한 알고리즘을 설계하는 것은 여전히 해결되지 않은 연구 문제다.

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

주키퍼나 etcd 같은 프로젝트는 종종 "분산 키-값 저장소"나 "코디네이션과 설정 서비스"라고 설명된다. 이런 서비스의 API는 데이터베이스의 API와 매우 비슷해 보인다. 키에 대한 값을 읽고 쓰고 순회할 수 있다. 이것들이 기본적으로 데이터베이스라면 합의 알고리즘을 구현하는데 있어서 다른 종류의 데이터베이스와 차이가 무엇일까?

 

애플리케이션 개발자로서 주키퍼를 직접 쓸 필요는 거의 없다. 다른 프로젝트를 통해서 주키퍼에 의존하게 될 가능성이 더 높다. HBase, YARN, Kafka는 모두 주키퍼에 의존한다.

 

주키퍼, etcd는 완전히 메모리안에 들어올 수 있는 작은 양의 데이터를 보관도록 설계됐다. 여기에 애플리케이션의 모든 데이터를 저장하고 싶지는 않을 것이다. 이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제된다. 앞서 설명했듯이 전체 순서 브로드캐스트는 데이터베이스 복제에 딱 필요한 것이다.

개별 메세지가 데이터베이스에 쓰기를 나타낸다면 같은 쓰기를 같은 순서로 적용함으로써 복제본들이 서로 일관성을 유지할 수 있다.

 

주키퍼는 구글의 처비 잠금 서비스를 모델로 삼아 다른 흥미로운 기능 집합도 구현한다.

• 선형성 원자적 연산
  • 원자적 compare-and-set 연산을 사용해 잠금을 구현할 수 있다. 여러 노드가 동시에 같은 연산을 수행하려고 하면 그것들 중 하나만 성공한다.
• 연산의 전체 순서화
  • 어떤 자원이 잠금이나 임차권으로 보호될 때는 프로세스가 중단되는 경우 클라이언트들이 서로 충돌하는 것을 막기 위해 펜싱 토큰이 필요하다. 펜싱 토큰근 잠금을 획득할 때 마다 단조 증가하는 어떤 숫자다. 주키퍼는 모든 연산에 전체 순서를 정하고 각 연산에 단조 증가하는 트랜잭션 ID와 버전 번호를 할당해서 이를 제공한다.
• 장애 감지
  • 수명이 긴 세션을 유지하고 클라이언트와 서버는 주기적으로 하트비트를 교환해서 다른 쪽이 여전히 살아 있는지 확인하다.
• 변경 알림
  • 클라이언트는 다른 클라이언트가 생성한 잠긍과 값을 읽을 수 있을 뿐만 아니라 거기에 변경이 있는지 감시할 수도 있다.

작업을 노드에 할당하기

애플리케이션은 처음에는 단일 노드에서만 실행도리지 모르지만 결국에는 수천 대의 노드로 늘어날 수도 있다. 매우 많은 노드에서 과반수 투표를 수행하려고 하는 것은 비효율적이다.

주키퍼는 3, 5개의 고정된 수의 노드에서 실행되고 이 노드들 사이에서 과반수 투표를 수행하면서 많아질 수 있는 클라이언트를 지원한다. 주키퍼는 노드들을 코디네이트하는 작업(합의, 연산 순서화, 장애 감지)의 일부를 외부 서비스에 위탁하는 방법을 제공한다.

서비스 찾기

특정 서비스에 연결하려면 어떤 IP 주소로 접속해야 하는지 알아내는 요도로도 자주 사용된다. 합의 시스템이 누가 리더인지 이미 안다면 다른 서비스들이 리더가 누구인지 찾는 데 그 정보를 사용한다.

멤버십 서비스

주키퍼와 유사 프로젝트들은 오랜 멤버십 서비스 연구 역사의 일부로 볼 수 있다.