Skip to content

juneyr.dev

[데이터중심어플리케이션설계] 9장. 일관성과 합의

19 min read

09. 일관성과 합의

8장에서 보았듯이 분산시스템에서는 망할 일 투성이다. 가장 간단한 해결법은 전체 서비스가 실패하도록 두고 에러 메시지를 보여주는 것이다. 그러고 싶지않다면, 결함을 견뎌낼 방법을 찾아야한다. 이 성질을 갖는 애플리케이션을 내결함성 이라고한다.

내결함성을 지닌 시스템을 구축하는 가장 좋은 방법은 유용한 보장을 해주는 범용 추상화를 찾아서 이 보장에 의존하는것이다. 같은 방식으로 분산 시스템에서도 적용될 추상화를 찾아보자. 가장 중요한 추상화 중 하나는 합의 이다.이 구현이 있으면 다양한 목적으로 사용할 수 있다. 일단, 분산시스템에서 제공될 수 있는 보장과 추상화의 범위를 알아보고, 그 다음 합의 알고리즘에 대해서 알아보자.

일관성 보장

복제 데이터베이스는 보통 최소한 최종적 일관성을 제공한다. / 수렴이라고 부르는 게 낫다. 그러나 이것은 매우 약한 보장이다. 언제 복제본이 수렴될 지에 대해서는 아무것도 얘기하지 않는다.

  • 개발자가 구현하기도 어렵다. 단일 스레드 프로그램 변수처럼 동작하지 않으니까.

  • 약한 보장만 제공하는 DB를 다룰 때는 너무 많은 걸 기대하지 말아야하고, 한계를 알아야한다. 최종적 일관성의 에지케이스는 시스템에 결함이 있거나 동시성이 높을 때만 나타날 수 있어서, 잡기도 어렵다.

    그러니, Data system이 선택적으로 제공할 수 있는 좀더 높은 수준의 강한 일관성 모델을 알아보자. 물론 이건 공짜가 아니다. 강한 보장을 제공하는 시스템은 성능이 나쁘거나, 약한 보장을 제공하는 시스템보다 내결함성이 약할지모른다.

선형성

최종적 일관성(약한 보장)을 한 DB의 서로 다른 복제본에 동시에 같은 질문을 하면 두 가지 다른 응답을 받을 가능성이 있다. 만약, DB의 복제본이 하나만 있다(는 환상)을 만들어준다면, 훨씬 단순해지지 않을까?

이 가정에 입각해서 나온 강한 보장이 바로 선형성 (원자적 일관성, 강한 일관성, 즉각 일관성, 외부 일관성 이라고도 부른다.) 이다. 위와 같은 보장이 있으면 현실에는 여러 복제본이 있어도 애플리케이션은 거기에 신경 쓸 필요가 없다.

선형성 시스템에서는 클라이언트가 쓰기를 완료하자마자, 그 DB를 읽는 모든 클라이언트가 방금 쓰여진 값을 볼 수 있어야한다. 즉, 선형성은 최신성 보장(recency gurantee) 이다.

비선형시스템 위의 비선형 시스템, 축구 웹사이트 예제를 잠시 보자. 밥은 앨리스가 최종 점수 발표 직후에 홈페이지에 접속했지만, 예전의 값만 보게 된다. 그의 질의가 오래된 결과를 반환했다는 사실은 선형성 위반이다.

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

기본 아이디어는 역시, 시스템에 데이터 복사본이 하나뿐인 것처럼 만드는 것이다. 예시를 보자. 읽기요청이 쓰기와 동시에 실행되면 위 그림에서 동시에 같은 키 x를 읽고 쓰는 세 클라이언트를 보여준다. 분산 시스템에서 이 x는 레지스터라고 불린다. 현실에서는 key-value의 key, RDB의 로우 하나, 문서DB의 문서 하나가 될 수 있다. 위 그림처럼 읽기 요청이 쓰기와 동시에 실행되면 과거의 값을 반환할 수도, 새로운 값을 반환할 수도 있다. 즉 B의 모든 요청, A의 두번째 요청은 쓰기의 영향이 발생했는지 모른다. 이런 경우는 선형적인 시스템이 아니다.

시스템을 선형적으로 만들려면 위 그림에서 제약 조건을 추가해야한다.

읽기가 새로운 값을 반환한 일이 있었으면, 그 이후의 읽기는 모두 반드시 새로운 값을 반환해야한다.

제약조건

선형성 시스템에서 우리는 x가 0 -> 1 인 시점이 있다고 생각한다. 따라서 한 클라이언트의 읽기가 새로운 값 1을 반환하면, 이후의 모든 후속 읽기는 새로운 값이다. 쓰기 연산이 완료되지 않았다고 하더라도 말이다.

이제 세번째 연산을 추가해보자. compare-and-set이라는 뜻의 cas(x, v1, v2) 는 x==v1 ? v2 : throw 의 뜻이다.

새로운연산추가

읽기와 쓰기의 영향이 나타난 것으로 보이는 시점을 시각화 했다. 위 그림에서 몇가지를 알 수 있다.

  • B가 읽기를 시작한 이후, D가 레지스터를 0으로 만들고 이후에 A가 레지스터를 1로 요청한다. 하지만 B가 읽은 값은 1이다. 이 말은 DB가 D->A->B 순으로 요청을 끝냈다는 말이다. 요청을 보낸 순서는 다르지만 세 요청은 동시적이기 때문에 이 순서는 허용된다.

  • B의 읽기는 A가 성공 응답을 듣기전에 1을 반환했다. 이것도 괜찮다.

  • 이 모델은 어떤 트랜잭션 격리도 가정하지 않는다. 예를 들어 C는 두번의 읽기에서 1, 2를 순서대로 읽었다. 이는 동시점에 B가 값을 변경했기 때문이다. 다만 다른 클라이언트의 값 변경을 확인하기 위해 cas 를 사용한다.

  • B의 마지막 읽기는 선형적이지 않다. A가 이미 4로 읽었기때문이다. 이 연산은 cas 연산과 동시적이기때문에 이런 결과를 받았다.

여기서 선형성과 직렬성의 차이를 짚고 넘어가자.

직렬성: 모든 트랜잭션들이 여러 객체를 읽고 쓸 수 있는 상황에서의 트랜잭션들의 격리 속성이다. 직렬성은 트랜잭션의 실행 순서와 상관없이 트랜잭션이 어떤 순서에 따라 실행하는 것처럼 동작하게 보장해준다.

선형성: 레지스터 (개별 객체)에 실행되는 읽기와 쓰기에 대한 보장이다. 연산을 트랜잭션으로 묶지 않아서 충돌 구체화 같은 수단을 쓰지 않으면 쓰기 스큐같은 문제를 막지 못한다. (읽은 값 기반으로 쓰지만, 쓰는 시점에는 그 값이 참이 아님)

DB는 이 두가지를 모두 제공할 수도 있고 그 조합은 엄격한 직렬성이나 강한 단일 복사본 직렬성이라고 한다. 2PL 은 선형적이지만, 7장에서 함께 언급한 SSI 은 선형적이지 않다.

선형성에 기대기

어떤 환경에서 선형성이 유용할까?

  • 잠금과 리더 선출
    • 단일리더 복제를 사용하는 시스템은 리더가 하나만 있도록 보장해야한다. 한 방법은 잠금을 사용하는 것인데, 이 잠금을 구현할 때는 선형적이어야한다. 모든 노드는 어느 노드가 잠금을 소유할지 동의해야한다.
    • 분산 잠금과 리더 선출에는 아파치 주키퍼나 etcd와 같은 코디네이션 서비스가 종종 사용된다. 이 서비스에서도 선형성 저장소 서비스가 기초가된다.
  • 제약조건과 유일성 보장
    • unique constraint 는 데이터베이스에서 흔하다. 이 상황은 실제로 잠금과 비슷하고, 연산 자체가 compare-and-set과도 비슷하다. 은행 계좌 잔고, 영화좌석과 같은 경우도 제약이 있다. 이 제약들은 모든 노드가 동의하는 하나의 최신값을 요구한다.
    • 이런 경우 선형성이 필요하다. 외래키나 속성 제약같은 건 선형성 없이도 구현할 수 있다.
  • 채널 간 타이밍 의존성
    • 썸네일 시스템을 생각해보자. 사용자가 이미지를 올리면, 다른 사용자가 쉽게 받을 수 있도록 저해상도로 만드는 시스템이다. 이 썸네일링 명령은 메시지 큐를 통해 웹서버에서 크기 변경 모듈로 보내진다. ![썸네일시스템])(./5.png) 이 시스템이 선형적이지 않으면, 메시지 큐의 단계가 저장서비스 내부의 복제보다 빠를 수 있다. 그러면 메시지를 받은 모듈이 이미지를 가져오려고할 때 아무것도 못보거나 과거버전만 볼 수 있다.
    • 이 문제는 웹서버 <->크기 변경 모듈 사이에 두가지 채널, 즉 파일 저장소와 메시지 큐가 있기때문에 발생한다. 선형성의 최신 보장이 없으면 경쟁 조건이 발생할 수 있다.

선형성 시스템 구현하기

그럼 이제 어떻게 구현할 지 알아봐야한다. 🦦 선형성은 "데이터 복사본이 하나만 있는 것 처럼 동작하는 것" 이므로 정말 데이터 복사본은 하나만 사용하자.

절대 결함을 버텨낼 수 없다.

결함을 버텨내는 가장 흔한 방법이 복제이므로 .. 복제에서 선형성을 찾아보자.

  • 단일리더복제 (선형적으로 할 수도 있음)

    • 리더나 동기식으로 복제된 팔로워에서 읽으면, 선형적이 될 수도 있다.그러나 모든 단일리더 DB가 선형적인 것은 아니다. 동시성 버그나 설계상의 이유가 있다.
    • 앞선 예시 처럼 split brain이 일어나면 지속성과 선형성을 모두 위반하게 된다.
  • 합의 알고리즘(선형적)

    • 이후에 살펴볼 합의 알고리즘은 선형적이다. 합의 프로토콜에는 split brain과 복제본이 뒤처지는 것을 막는 수단이 둘다 있다. e.g.) 주키퍼, etcd
  • 다중 리더 복제(비선형적)

    • 이들은 여러 노드에서 동시에 쓰기를 처리하고, 비동기로 이 내용을 복제하므로 충동 쓰기를 만들어낸다(문제!)
  • 리더 없는 복제(아마도 비선형적)

    • 정족수를 통해서 엄격한 일관성을 달성할 수 있다고 주장하는 사람들이 있다. 그러나 정족수 설정과 일관성의 정의에 따르면 이 주장이 완벽한 진실은 아니다.

    선형성과 정족수

    다이나모 스타일(리더없는 복제) 에서 엄격한 정족수를 사용한 읽기, 쓰기는 선형적인 것처럼 보인다. 그러나 변동이 심하면 경쟁조건이 생길 수 있다.

    정족수를 만족하지만 경쟁 조건인 정족수가 만족 (w=3, r=2, n=3)되지만 A가 1을 보고, B는 0을 본다. 이런 경우 선형성을 만족하지 않는다. 그러나 성능을 비용으로 지불하고 선형적으로 만드는게가능하다.

    • 동기식 읽기 복구
    • 쓰기는 쓰기 전 최신 상태 읽기

    이 방법으로는 선형성 읽기와 쓰기 연산만 구현할 수 있다. 그러므로 다이나모스타일은 선형성을 만족하지 않는다고 보는게 안전하다.

선형성의 비용

다중 리더 데이터베이스를 생각해보자. 만약 데이터 센터 간 연결이 해제되면, 각 데이터 센터는 따로 따로 정상동작한다. 서로 동기화 안된 부분은 네트워크가 복구되면 따라잡을 수 있다. 그러나 단일 리더에서 데이터 센터가 분리된 예제에서는, 팔로워 데이터 센터로 접속한 클라이언트가 write할 수 없다. 이 경우 클라이언트는 서비스 중단을 경험한다.

모든 선형성 데이터베이스는 이런 문제가 있다. 이 트레이드 오프를 CAP 정리로 표현한다.

  • 애플리케이션에서 선형성을 요구하고, 네트워크 문제때문에 복제서버가 다른 복제서버와 연결이 끊기면 일부 복제 서버는 연결이 끊긴 동안은 요청을 처리할 수 없다.
  • 애플리케이션에서 선형성을 요구하지 않는다면, 독립적인 방식으로 요청을 처리할 수 있고 따라서 가용한 상태를 유지한다.

CAP 은 이 트레이드 오프를 이야기한다. Consistency(일관성), Availablility(가용성), Partition tolerance(분단 내성)이라는 셋 중 둘을 고르라는 식의 해석이 있지만 오해의 소지가 있다. 이는 사실 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 고르라는 의미에 가깝다. (네트워크가 정상 작동하면 둘다 챙길 수 있다.)

선형성과 네트워크 지연

선형성은 유용한 보장이지만 현실에서 실제로 선형적인 시스템은 매우 드물다. e.g.) 최신 다중 코어의 RAM 만약 하나의 CPU 코어에서 실행 중인 스레드가 메모리 주소(x)에 쓴 후 바로 다른 코어에서 실행되는 스레드가 같은 주소(x)를 읽으면 처음에 읽은 값을 읽으라는 보장이 없다.

이는 모든 CPU 코어가 저마다의 캐시와 버퍼를 사용하기 때문이다. 캐시가 물론 저장소보다 빠르므로 좋은 성능에 필수적이고, 각자의 저장소를 바라보는 결과를 낳는다. 여기에서 선형성을 제거한 이유는 내결함성이 아니라 성능이다.

선형성은 느리다. 그리고 이는 네트워크 결함이 있을 때뿐만 아니라 항상 참이다. 좀더 효율적인 선형 저장소를 찾으려는 시도가 있었지만, 아직까지는 답이 없다. (p.336) 다만 완화된 일관성 모델은 훨씬 더 빠를 수 있다. 따라서 지연 시간에 민감한 시스템에서는 이 트레이드 오프가 중요하다.

순서화 보장

선형성 register는 데이터 복사본이 하나만 있는 것 처럼 동작하며, 연산이 순서대로 실행된다는 것을 암시했다. 순서 그리고 순서화는 이 책에서 되풀이 된 주제이다 == 즉, 중요하다.

  • 5장 단일 리더 복제에서 복제로그의 쓰기 순서에 대해 배웠다. 순서와 단일 리더가 없으면 충돌이 발생한다.
  • 7장 직렬성에서 트랜잭션이 어떤 일련 순서에 따라 실행되는 보장하는 것을 배웠다.
  • 8장에서의 타임스탬프와 시계는 질서를 부여하려는 시도다.

순서화와 인과성

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

  • 일관된 순서로 읽기 : 예지력이 있는 사용자의 예시를 기억하나요? 답변을 먼저보고 질문을 나중에 보게 되는 이 예시는 인과성을 위반했기때문에 혼란스럽다.
  • 네트워크 지연때문에 존재하지 않는 로우를 갱신하는 예제.
  • 동시 쓰기 감지에서 happened before 관계를 얘기했다. A < B (시간적으로) 라면, B가 A에 의존하거나 기반으로 한다는 뜻이다. 동시적이면 서로에 대해서 모른다는 뜻이다.
  • 트랜잭션 스냅숏 격리의 맥락에서 일관적 스냅숏을 이야기했다. 일관적은 인과성에 일관적이라는 의미다. 스냅숏에 답변이 포함되면 응답된 질문 또한 포함되어야한다.
  • 쓰기 스큐 예제에서도 인과적 의존성을 보여준다. SSI 는 트랜잭션 사이의 인과적 의존성을 추론해서 쓰기 스큐를 검출한다. (on call 의사 예제)
  • 앨리스와 밥의 축구 예제에서 밥이 앨리스가 결과를 외치는 것을 들은 후 서버에서 결과를 확인할 수 없는 것은 인과성 위반이다. (채널 간 타이밍 의존성)

시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적이라고 한다.

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

전체 순서는 어떤 두 요소를 비교할 수 있게하므로 두 요소가 있으면 항상 어느 것이 크고 작은지 비교할 수 있다. 이제 집합을 생각해보자. 집합의 크기는 비교가 불가능하다. {a, b} 와 {b,c} 중 어느것이 크고 작은가? 집합은 부분적으로 순서가 정해진다(partially ordered) 이것이 부분 순서이다.

이 차이는 데이터베이스 일관성 모델에도 반영된다.

  • 선형성
    • 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다. DB 복제본이 하나만 있는 것 처럼 동작하고 연산이 원자적이면 어떤 두 연산에 대해서 항상 둘 중 하나가 먼저 실행되었다고 말할 수 있다.
  • 인과성
    • 두 연산 중 어떤 것도 다른 것보다 먼저 실행되지 않았다면 동시적이라고 말한다. 두 연산이 동시에 실행되면 비교할 수 없다. 인과성은 부분 순서를 정의한다.

이 정의에 따르면 선형성은 동시적 연산이 없다. 하나의 타임라인이 있고, 모든 연산은 해당 타임라인을 따라 순서가 정해져야한다.

동시성은 타임라인이 갈라졌다 다시 합쳐지는 것을 말한다. 이 경우 다른 branch 에 있는 연산은 비교가 불가능하다.

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

그러면 이런 결론에 다다른다. 선형성은 인과성을 포함한다. 어떤 시스템이든지 선형적이라면 일관성도 올바르게 유지한다. 좋은 소식처럼 보이지만, 앞서 말했듯이 선형성은 비용이 비싸다.

좋은 소식은 절충이 가능하다는 것이다. 선형성은 인과성을 유지하는 유일한 방법은 아니고 성능 손해를 유발하지 않고도 인과적 일관성을 유지할 수 있다. 이 연구는 현재 계속 진행되고 있다.

인과적 의존성 담기

이 인과적 의존성의 핵심 아이디어만 살펴본다. 인과성을 유지하기 위해서는 어떤 연산이 어떤 다른 연산보다 먼저 실행되었는지 알아야한다. 인과적 의존성을 결정하려면 시스템 노드에 있는 지식을 기술할 방법이 필요하다. 노드가 쓰기 y를 실행했을 때 값 x를 본 상황이라면 x, y는 인과적 관련이 있을 지 모른다. 이 분석은 범죄 수사와도 같은 질문을 사용한다. 'y라는 결정을 한 당시에 x에 대해 알았을까?'

인과적 순서를 결정하기 위해서 DB 는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야한다. 트랜잭션이 커밋을 원할 때 DB 는 읽은 데이터의 버전이 최신인지 확인한다. 이런 목적으로 DB는 어떤 데이터를 어떤 트랜잭션이 읽었는지 추적한다.

일련번호 순서화

하지만 모든 인과적 의존성을 추적하는 것은 실용성이 떨어진다.(오버헤드가 큼) 대신, 일련번호나 타임스탬프를 써서 이벤트의 순서를 정할 수 있다. 타임스탬프는 논리적 시계에서 얻어도 되고, 보통 모든 연산마다 증가하는 카운터를 사용한다. 이 일련번호나 타임스탬프는 크기가 작고, 전체 순서를 제공한다. 전체순서 -> 부분 순서도 제공하니, 인과성에 일관적일 수 있다.

비인과적 일련번호 생성기

하지만 단일리더가 없다면 일련번호를 어떻게 생성할까? 현실에서는 다양한 방법을 사용한다.

  • 각 노드가 자신만의 독립적인 일련번호 집합을 사용한다. 예를 들어 노드 두대이면 하나는 홀수, 하나는 짝수. 일반적으로는 일련번호의 몇 비트를 사용해서 노드 식별자를 포함한다.
  • 각 연산에 wallclock time을 사용할 수 있다. 이 타임스탬프는 순차적이지 않지만 해상도가 충분히 높다면 연산의 전체순서를 정하는데 충분할 수도 있다. 이는 최종쓰기승리 충돌해소법에서 사용한다.
  • 일련번호 블록을 미리 할당할 수 있다. 노드A는 1~1000까지, B는 1001부터~ 2000까지라는 식이다. 번호 비축량이 낮아지면 새 블록을 할당한다.

위 세가지는 잘 동작하지만, 문제가 있다. 생성한 일련번호가 인과성에 일관적이지 않다. 1) 각 노드는 초당 연산수가 다를수있다. 따라서 한 노드가 짝수를 생성하고 다른 노드가 홀수라면, 짝수용 카운터가 뒤처지거나 너무 앞지를 수 있다. 2) 물리적 시계에서 얻은 타임스탬프는 인과성에 일관적이지 않을 수 있다. 3) 블록 할당자의 경우 인과적으로 나중에 할당되는 연산이 1-1000 블록을 받을 수도 있다.

램포트 타임스탬프

위 문제를 해결한 타임스탬프가 실제로 있다. 이 방법은 램포트 타임스탬프라고하고, 분산시스템에서 가장 많이 인용된 논문 중 하나다.

lamport timestamp

각 노드는 고유 식별자를 갖고, 각 노드는 처리한 연산 갯수를 카운터로 유지한다. 램포트 타임스탬프는 그냥 (카운터, 노드ID)의 쌍이다.

이는 물리적 시계와 아무 관련이 없지만, 전체 순서화를 제공한다. 두 타임스탬프가 있으면 카운터가 큰 것이 타임스탬프가 크다. 카운터 값이 같으면 노드 ID가 큰것이 타임스탬프가 크다.

핵심 아이디어는 이것이다. 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고 모든 요청에 그 최댓값을 포함시킨다. 노드가 자신의 카운터보다 큰 값을 받으면 바로 자신의 카운터를 그 값으로 올린다.

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

램포트 타임스탬프가 전체순서를 정의해주긴하지만, 분산시스템의 공통 문제를 해결하기엔 부족하다.

예를 들어 유니크한 유저네임을 갖도록 보장하는 시스템을 고려해보자. 두 사용자가 동시에 같은 이름으로 만들려고 하면 하나는 성공하고 하나는 실패한다. 사용자가 둘다 생성된 이후에 타임스탬프로 하나를 실패하게 할 수는 있다. (사후 처리) 그러나 노드가 사용자로부터 유저네임 생성 요청을 받고 그 요청을 당장 성공/실패 처리해야하는 경우라면 이 노드는 다른 노드가 같은 유저네임 생성을 하고 있는지, 어떤 타임스탬프를 배정받았는지 알지 못한다.

이를 알기 위해서는 다른 모드 노드가 뭘하고 있는지 확인해야한다. 이를 구현하면 한 노드만 장애가 생겨도 시스템이 멈추게 된다. 이는 내결함성 위반이다.

즉 문제는 전체 순서가 모든 연산을 모은 이후에 드러난다는 것이다. 그러므로 유일성 제약 조건 같은 것을 구현하려면 전체 순서로 충분하지 않다. 언제 전체순서가 확정되는지도 중요하다.

전체순서 브로드캐스트

위에서 언제 전체순서가 확정되는지에 대한 아이디어를 이야기했다. 프로그램이 단일 CPU 코어에서 실행된다면 연산의 전체 순서를 정하기 쉽다. 하지만 분산 시스템에서는 위와 같이 타임스탬프나 일련번호를 이용할 수 있지만, 문제가 있다는 것을 발견했다.

단일 리더 복제의 단일 코어에서 일을 하다가, 처리량이 급증할 때 시스템을 확장하고 리더에 장애가 발생했을 때 어떻게 할 것인가의 문제를 전체 순서 브로드캐스트라고한다. 이는 노드 사이에 메시지를 교환하는 프로토콜로 기술된다.

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

전체 순서 브로드캐스트를 구현하는 올바른 알고리즘은 위 두 조건을 항상 만족해야한다.

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

주키퍼나 etcd와 같은 합의 서비스는 전체 순서 브로드캐스트를 실제로 구현한다. 즉, 전체순서브로드캐스트 <-> 합의 간 강한 연관이 있다는 암시이다.

전체 순서 브로드 캐스트는 복제에 필요한 것이다. 모든 메시지가 DB에 쓰기를 나타내고, 모든 복제 연산이 같은 순서로 처리하면 복제 서버들은 서로 일관성 있는 상태를 유지한다. 이 원리를 상태 기계 복제라고한다. (state machine replication)

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

  • 스토어드 프로시저:DB 내부에 저장된 일련의 SQL 명령문들을 하나의 함수처럼 실행하기 위한 쿼리의 집합 (까먹어서 다시 적기)

중요한 측면은 전체 순서 브로드캐스트는 메시지가 전달되는 시점에 그 순서가 고정된다는 것이다. 나중에 도착된 메시지가 중간에 끼어들거나 소급적용되는것이 없다. 이때문에 앞서 말한 타임스탬프 순서화보다 강하다.

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

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

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

그러나 전체 순서 브로드캐스트 구현이 있다면 이를 기반으로 한 선형성 저장소를 만들 수 있다. unique constraint 예제를 보자.

모든 사용자 명마다 원자적 compare and set 연산이 구현된 선형성 저장소를 가질 수 있다고 상상해보자. 모든 레지스터는 초기에 null이다 (점유되지 않음). 사용자명을 생성할 때 null 인 경우만 set할 수 있도록 한다. 선형성때문에 여러 유저가 같은 사용자명을 가지려고하면 compare-and-set 연산 중 하나만 성공한다.

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

  • 메시지를 로그에 추가해서 점유하기 원하는 사용자명을 시험적으로 가리킨다
  • 로그를 읽고, 추가한 메시지가 되돌아오기를 기다린다.
  • 원하는 사용자명을 점유하려고하는 메시지가 있는지 확인한다. 본인이 첫 메시지라면 성공이다. 다른 사용자가 보낸 메시지라면 연산을 어보트 시킨다.

로그 항목은 모든 노드에 같은 순서로 전달되므로 여러 쓰기가 동시에 실행되면 모든 노드가 어떤 쓰기가 먼저 실행된 것인지 동의한다.

이 절차는 선형성 쓰기를 보장하지만, 선형성 읽기는 보장하지않는다. 로그로부터 비동기로 갱신되는 저장소를 읽으면 오래된 값이 읽힐 수 있다. 읽기를 선형적으로 만들려면 몇가지 선택지가 있다.

  • 로그를 통해 순차 읽기를 할 수 있다. 로그에 메시지를 추가하고 로그를 읽어서 메시지가 되돌아왔을 때 실제 읽기를 수행하면 된다. 따라서 로그상의 메시지 위치는 읽기가 실행된 시점을 나타낸다.

  • 로그에서 최신 로그 메시지의 위치를 선형적 방법으로 얻을 수 있다면 그 위치를 질의하고 그 위치까지의 모든 항목이 전달되기를 기다린 후 읽기를 수행할 수 있다.

  • 쓰기를 실행할 때 동기식으로 갱신돼서 최신이 보장되는 복제 서버에서 읽을 수 있다.

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

전체 순서 브로드캐스트 -> 선형성 저장소 만들기 뿐 아니라 반대로도 구현할 수 있다. 가장 쉬운 방법은 정수를 저장하고 원자적 increment-and-get연산이 지원되는 선형성 레지스터가 있다고 가정하는 것이다.

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

실패가 없다면 이 방법은 제대로 동작한다. 메시지 4를 전달하고, 일련번호가 6인 메시지를 받았다면 5를 기다려야한다는 것을 알 수 있다. 문제는 노드에 장애나 네트워크 오류가 발생했을 때 일어난다. 이렇게 일련번호 생성에 대해서 고민하다보면 필연적으로 합의 알고리즘에 도달하게 된다. 이는 우연히 아니다. 선형성 레지스터 <-> 전체 순서 브로드캐스트 <-> 합의는 동등한 것으로, 하나의 해결책을 다른 하나로 변형할 수 있다.

분산 트랜잭션과 합의

합의는 분산 컴퓨팅에서 가장 중요하고 근본적인 문제 중 하나다. 목적은 노드들이 뭔가에 동의하게 만드는 것이다. 이 문제는 생각만큼 간단하진 않다.

노드가 동의하는 것이 중요한 상황이 여럿 있다.

  • 리더 선출
    • 단일 리더 복제를 사용하는 DB에서 모든 노드는 어떤 노드가 리더인지 동의해야한다. 어떤 노드가 네트워크 결함때문에 통신이 불가능하면, 리더십 지위를 놓고 경쟁할 수 있다.
  • 원자적 커밋
    • 여러 노드나 파티션에 걸친 트랜잭션을 지원하는 DB에서는... 트랜잭션이 어떤 노드에서는 성공하고, 어디서는 실패하는 문제가 있을 수 있다. 원자성을 유지하고 싶다면 노드들이 성공/실패 여부에 합의하게 만들어야한다.

합의불가능성 사실 합의는 불가능하다? 피셔, 린치, 패터슨은 FLP 라는 결과를 내놓았다. 이 내용인 즉슨 어떤 노드가 죽을 위험이 있다면 항상 합의에 다다를 알고리즘은 없다는 것이다. 아니 그럼 왜 이걸 배워요. 🤔 사실 이 결과는 어떤 시계나 타임아웃도 사용할 수 없는 경우에 증명/적용되는 모델이다. 타임아웃이 있거나 죽은 노드를 살펴볼수있는 방법이 있다면 보통의 현실에서 분산시스템은 합의를 달성할 수 있다.

원자적 커밋과 2단계 커밋

트랜잭션 원자성의 목적은 여러 쓰기 중 잘못되는 경우 간단한 시맨틱을 제공하기 위함이다. 트랜잭션의 결과는 커밋 성공이나 어보트다.

이 원자성은 특히 다중 객체 트랜잭션과 보조 색인을 유지하는 데이터베이스에서 중요하다. 개별 보조색인은 주 데이터와 분리된 자료이고, 주 데이터가 변경되면 그 내용이 반영되어야한다.

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

단일 노드에서는 커밋 요청을 받으면 디스크 로그에 커밋 레코드를 추가한다. 이 과정에서 DB가 죽으면 트랜잭션은 노드가 재시작될때 로그로 복구하고, 죽기전에 레코드가 쓰였다면 커밋이 된것이다. 그러니까, 단일 노드에서 ㅋ커밋은 데이터가 디스크에 지속성 있게 쓰여지는 순서에 의존한다. 데이터가 먼저고 커밋 레코드는 그 다음이다. (어보트 될 가능성이 있지만, 이 시점에서는 커밋이다. )

그런데 트랜잭션에 여러 노드가 관여한다면 어떨까? e.g) 파티셔닝된 데이터베이스에서 다중 객체 트랜잭션을 쓰거나, term-파티셔닝이 된 보조 색인을 사용할수도 있다.

이런 경우 모든 노드에 커밋 요청을 보내고 각 노드에서 트랜잭션을 독립적으로 지원하는 것으로는 충분치 않다. 언제 누가 죽을지 몰라... 이러면 한 노드는 성공, 다른 노드는 실패하면서 원자성을 위반하기 쉽다.

트랜잭션 커밋은 되돌릴 수 없어야한다. 데이터가 커밋되면 다른 트랜잭션에게 보이게 되고 다른 클라이언트도 이 데이터에 의존하기 시작할지도 모르기때문이다.

2단계 커밋 소개

2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는 알고리즘이다. 일부 DB에서는 2PC(two-phase commit) 이 내부적으로 사용되고, XA트랜잭션이나 MSA 웹서비스 용 WS- atomic transcation을 통해 애플리케이션에서도 사용할 수 있다. 이게된단 말이여?

2PC 단일 노드 트랜잭션에서처럼 하나의 커밋 요청을 하는 대신 2PC의 커밋/어보트 과정은 두 단계로 나뉜다.

2PC는 코디네이터라는 새로운 컴포넌트를 사용한다. 라이브러리나, 포르세스, 서비스 형태를 띌수도 있다. e.g.) Narayana, JOTM

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

  • 모든 참여자가 네라고 응답하면 코디네이터는 2단계에서 커밋 요청을 보내고 커밋이 실제로 일어난다.
  • 참여자 중 누구라도 아니오 라고 응답하면 2단계에서 어보트를 한다.

약속에 관한 시스템

그런데, 준비 요청과 커밋요청도 손실될 수있다. 그런 위험이 있는데 2PC가 어떻게 원자성을 보장한다는 걸까? 이 과정을 좀더 자세히 뜯어보자.

  • 애플리케이션은 분산 트랜잭션을 시작하기 원할 때 코디네이터에 트랜잭션 ID를 요구한다. 이 트랜잭션 ID는 전역적으로 유일하다.

  • 애플리케이션은 각 참여자에서 단일 노드 트랜잭션을 시작하고 ... 해당 트랜잭션에 아까 받은 ID를 붙여준다. 모든 읽기와 쓰기는 이런 단일 노드 트랜잭션중 하나에서 실행된다. 이 단계에서 뭔가 잘못되면 코디네이터나 노드에서 어보트할 수 있다.

  • 애플리케이션이 커밋할 준비가 되면 코디네이터는 모든 참여자에게 전역 트랜잭션 ID로 태깅된 준비 요청을 보낸다. 요청 중 실패/타임아웃이 나면 코디네이터가 어보트 요청을 모든 참여자에게 보낸다.

  • 참여자는 준비요청을 받으면 분명히 트랜잭션을 커밋할 수 있는지 확인한다. 여기에는 모든 트랜잭션 데이터를 디스크에 쓰는 것과, 충돌, 제약 조건 확인까지 포함된다. 코디네이터에게 yes 응답을 주면서 요청이 있으면 무조건 오류없이 커밋할 것을 보장한다(어보트할 권리를 포기함)

  • 코디네이터는 모든 응답을 받고 트랜잭션을 커밋할 건지 어보트할 건지에 대한 최종 결정을 한다. 코디네이터는 이 결정을 추후 트래킹하기 위해서 디스크에 있는 트랜잭션 로그에 기록해야한다. 이를 커밋 포인트 라고 한다.

  • 코디네이터의 결정이 디스크에 기록되면 모든 참여자에게 커밋이나 어보트 요청이 전송된다. 이 요청이 실패하거나 타임아웃이 되면 코디네이터는 성공할 때까지 영원히 재시도해야한다... 돌아갈 곳이 없다! 😇 도중에 한 참여자가 죽었다면 트랜잭션은 그 참여자가 돌아올때 커밋된다.

두가지 포인트가 있는데,

  • 참여자는 yes 투표를 할때 나중에 분명 커밋할거라 약속하고 어보트 권리를 포기한다.
  • 코디네티어가 한번 결정하면 그 결정은 변경할 수 없다.

이 두가지가 2PC 의 원자성을 보장한다.

코디네이터 장애

위에서 참여자 노드가 장애가 생길 경우에도 계속 시도한다는 점을 분명히 했다. 그런데 코디네이터에 장애가 생기면 어떡할까?

  • 코디네이터가 준비 요청을 보내기 전에 장애가 나면 참여자가 안전하게 트랜잭션을 어보트할 수 있다.
  • 하지만 yes 투표 이후에 장애가 나면 참여자는 기다릴 수 밖에 없다. 이 상태의 참여자 트랜잭션을 in doubt / uncertain 하다고 한다.

2PC 를 완료할 유일한 방법은 코디네이터 복구를 기다리는 방법이다. 이때문에 코디네이터는 자신의 결정을 디스크에 쓴다.

3단계 커밋

2단계 커밋은 코디네이터 복구를 기다리느라 멈출수있다는 점때문에 블로킹 원자적 커밋 프로토콜이라고 불린다. 이론상으로는 이를 논 블로킹하게 만들 수 있지만 현실에서는 어렵다.

2PC에 대한 대안으로 3PC가 제안됐다. 하지만 3PC의 가정은 지연과 응답시간에 제한이 있는노드다. 기약없는 네트워크 중단과 프로세스 지연이 있는 현실은 3PC에 적합하지 않다. 논블로킹 원자적 커밋은 완벽한 장애 감지기(perfect failure detector), 즉 노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메카니즘이 필요하다. 현실에서는 타임아웃이 신뢰성 있는 메카니즘이 아니다.

현실의 분산 트랜잭션

현실의 분산 트랜잭션은 평판이 엇갈린다.

  • 중요한 안정성을 달성하는 방법이다.
  • 운영상의 문제를 일으키고, 과한 약속을 하는 것 뿐이다.

어떤 분산 트랜잭션 구현은 무거운 성능 손해를 수반한다. mySQL의 분산 트랜잭션은 단일 노드 트랜잭션보다 10배 이상 느리다. 이 비용은 장애 복구를 위해 필요한 디스크 강제 쓰기와 부가적인 네트워크 왕복시간 때문이다.

그러나 단점만 있다고 에잉 더 안봐 할게 아니다. 중요한 교훈이 있다. 일단 분산 트랜잭션은 두가지 종류가 있다.

  • 데이터 베이스 내부 부분산 트랜잭션
    • 복제와 파티셔닝을 사용하는 데이터베이스는 노드사이에 내부 트랜잭션을 지원한다. 이 경우 모든 노드가 동일한 DB 소프트웨어를 사용한다.
  • 이종 (heterogeneous) 분산 트랜잭션
    • 참여하는 노드가 서로 다른 DB 소프트웨어를 사용한다.(종류가 2개 이상) e.g.) 레디스와 mySQL 동시에 쓰기. 이런 시스템에 걸친 분산 트랜잭션은 시스템의 내부가 완전히 다르더라도 원자적 커밋을 보장해야한다.

정확히 한번 메시지 처리

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

이런 분산 트랜잭션은 트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능하다. e.g.) 메시지를 처리하는 부수 효과가 이메일 전송이고, 이메일 서버는 2단계 커밋을 지원하지 않는다고 하자. 메시지가 처리가 실패하고 재시도되면 이메일이 두번 이상 전송될 수 있다.

이종 분산 트랜잭션을 가능하게 하는 원자적 커밋 프로토콜 : XA 트랜잭션

X/Open XA(eXtended Architecture). XA는 postgresSQL, mySQL, DB2, SQL 서버, 오라클, 그리고 activeMQ 등의 메시지 브로커에서도 지원한다.

XA는 네트워크 프로토콜이 아니다. 트랜잭션 코디네이터와 연결하는 인터페이스를 제공하는 C API 이다. 다른 언어에도 이 API 가 있다. 자바 EE에서는 XA 트랜잭션이 java transaction API (JTA) 를 사용해 구현되며 JTA는 다시 JDBC나 JMS 를 사용하는 시스템에서 지원된다.

코디네이터는 XA API 를 구현한다. 현실에서는 코디네이터가 단순히 트랜잭션 시작 어플리케이션과 같은 프로세스에 로딩되는 같은 라이브러리다. 이제 참여자를 추적하고 준비 요청을 보내고, 응답을 수집하고 로컬 디스크에 있는 로그를 사용한다.

in-doubt 상태의 코디네이터, 잠금을 유지하는 것의 문제

in-doubt 상태의 코디네이터가 생기면, 트랜잭션은 보통 로우 수준의 잠금을 획득하므로 문제가 생긴다. 데이터베이스는 트랜잭션이 커밋/어보트할 때까지 이 잠금을 해제할 수 없다. 코디네티어 로그가 어떤 이유로 완전히 손실되면 이 잠금은 여원히, 혹은 관리자가 수동으로 해결할때까지 유지된다.

따라서 다른 트랜잭션이 그냥 일을 할수가 없다.

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

이론상으로는 코디네이터가 죽은 후 재시작하면 로그로부터 그 상태를 깨끗하게 복구하고 의심스러운 트랜잭션을 해소해야한다. 그러나 orphaned 트랜잭션이 생길 수 있는데, 즉 어떤 이유인지 그 결과를 결정할 수 없는 트랜잭션이다. (로그 손실 or 버그로 오염) 이런 트랜잭션은 자동으로 해소가 안되어서 잠금을 유지하고 다른 트랜잭션을 차단하면서 영원히 데이터베이스에 남는다. DB 서버를 재부팅해도 2PC를 제대로 구현했다면 의심스러운 트랜잭션은 잠금이 된다.

여기서 빠져나가는 유일한 방법은 관리자가 수동으로 트랜잭션을 커밋하거나 롤백할지 결정하는 것이다. 이 결정을 할때는 심각한 서비스 중단일 가능성이 높다. 여러 XA 구현에는 참여자가 코디네티어로부터 확정적 결정을 얻지 않고 의심스러운 트랜잭션을 어보트하거나 커밋할지 일방적으로 결정할 수 있는 경험적 결정(heuristic descision) 이 있다. 일종의 비상 탈출이다.

분산 트랜잭션의 제약

XA 트랜잭션은 여러 참여 데이터 시스템이 서로 일관성을 유지하게 해주지만, 중요한 운영상 문제도 위와 같이 생긴다. 특히 핵심 구현은 코디네이터 자체가 트랜잭션 결과를 저장할 수 있는 일종의 데이터베이스 여야하고, 따라서 다른 중요 데이터베이스와 동일하게 신경써서 접근해야한다.

  • 코디네이터가 복제가 없고 단일 장비에서 실행되면 전체 시스템의 단일 장애점이 된다. 놀랍게도 여러 코디네이터 구현은 기본적으로 고가용성 X 거나 기초적인 복제만 지원한다.

  • 코디네이터가 어플리케이션 서버의 일부가 되면 배포의 특성이 바뀌게 된다. stateful 해진다.

  • XA 는 여러 시스템에 걸친 교착 상태를 감지할 수 없다. 그리고 SSI 와 함께 동작하지 않는다.

  • 데이터베이스 내부 분산 트랜잭션은 그 제한이 그리 크지 않다. (XA 가 아닌) 그러나 여전히 모든 참여자가 응답해야하므로 장애를 증폭시키는 경향이 있으며 이는 내결함성을 지닌 시스템 구축이라는 목적에 부합하지 않는다.

내결함성을 지닌 합의

정리를 해보자. 합의는 '하나 또는 그 이상의 노드들이 값을 제안할 수 있고 합의 알고리즘이 그 값 중 하나를 결정한다.' 이 형식에서 합의 알고리즘은 다음을 만족해야한다.

  • 균일한 동의 : 어떤 두 노드도 다르게 결정하지 않는다.
  • 무결성 : 어떤 노드도 두번 결정하지 않는다.
  • 유효성: 한 노드가 값 v를 결정한다면 v는 어떤 노드에서 제안되었던 값이다.
  • 종료: 죽지않은 모든 노드는 결국 어떤 값을 결정한다.

균일한 동의와 무결성 속성은 합의의 핵심 아이디어를 정의한다. 유효성 속성은 뻔한 해결책을 배제한다. e.g.) 안되면 무조건 null로 세팅. 내결함성이 상관없다면 처음 세개를 만족시키는 것은 쉽다. 그냥 한 노드를 독재자로 하드코딩하면 된다. 그러나 그 노드에 장애가 나면 그 시스템은 어떤 결정도 할 수 없다. 여기서 종료 속성은 내결함성의 아이디어를 형식화 한다. 이 속성은 본질적으로 합의 알고리즘은 그 상태에 머무르기만 할 수 없다는 이야기를 하는 것이다. 다시 말해 진행해야한다. 어떤 노드가 장애가 나도 다른 노드들은 여전히 결정을 내려야한다.

종료 속성은 죽거나 연결할 수 없는 노드가 절반 이하라는 가정이 암묵적으로 있긴하다. 그러나 대부분 합의 구현은 과반수 노드가 장애가 나더라도 위 세가지(균일한 동의, 무결성, 유효성) 은 만족하므로 요청을 처리할수 없을 지라도 유효하지 않는 결정을 내리진 않는다.

또 합의 알고리즘은 비잔틴 결함이 없다고 가정한다. (모든 노드는 프로토콜을 올바르게 따르고 있다고 생각함.)

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

내결함성을 지닌 합의 알고리즘 중 가장 널리 알려진 것은 viewstamped replication, paxos, raft, zab 이다. 이 내용을 상세히 다루지는 않는다. 이 알고리즘 중 대다수는 형식적 모델을 직접사용하지 않는다. 대신 값의 sequence를 정해서 전체 순서 브로드캐스트 알고리즘을 만든다. 이는 앞서 말했듯이 합의로 변환할 수 있다.

전체순서 브로드캐스트는 모든 노드에게 메시지가 정확히 한번, 같은 순서로 전달된다. 이는 합의를 몇회하는 것과 동일하다.

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

잠깐 단일리더복제를 생각해보자. 리더가 없어지면 새로운 리더를 선출해야한다. 합의는 전체 순서 브로드캐스트와 같고, 전체순서브로드캐스트는 단일리더와 같고, 단일리더 복제는 리더가 필요하고.. 그런데 리더를 새로 선출하려면 리더가 필요한것같다. 합의를 하려면 합의를 해야한다.

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

지금까지의 합의 프로토콜은 모두 내부적으로 어떤 형태로든 리더를 사용하지만 리더가 유일하다고 보장하지는 않는다. 대신 약한 보장을 한다. 에포크 번호를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장한다.

리더가 죽었다고 생각될때마다 투표가 시작된다. 이 선출은 에포크 번호를 증가시키며 따라서 에포크 번호는 전체 순서가 있고 단조 증가한다. 다른 에포크에 있는 리더 사이에 충돌이 있으면 번호가 큰 쪽이 이긴다.

리더는 노드의 정족수로부터 투표를 받는다. 노드는 에포크 번호가 더 높은 리더를 알지 못할 때만 제안에 찬성하는 투표를 한다.

따라서 두번의 투표가 있다.

  • 한번은 리더 선출
  • 두번째는 리더의 제안에 투표

중요한 것은 두번 투표하는 정족수가 최소 한명은 겹쳐야한다. 제안에 참여하는 노드 중 최소 하나는 가장 최근의 리더 선출에 참여했어야 리더는 다른 (에포크가 높은) 리더가 없다고 확신하고 안전하게 제안된 값을 결정할 수 있다.

겉보기에는 2PC와 비슷해보인다. 가장 큰 차이는 2PC에서 코디네이터는 선출되지 않는다는 것과 2PC는 모든 참여자로부터 yes가 필요하지만 내결함성을 지닌 합의 알고리즘은 과반수로부터만 투표를 받으면 된다는 것이다.

합의의 제약

합의 알고리즘은 분산시스템의 커다란 발전이다.

  • 구체적인 안전성 속성을 가져와준다.(동의, 무결성, 유효성)
  • 그럼에도 내결함성을 유지한다(노드의 과반수가 동작하는 한)
  • 전체 순서 브로드캐스트를 제공하고 따라서 내결함성있는 방식으로 선형성 원자적 연산을 구현할 수 있다.

그럼에도 모든 곳에 쓰이지않는다. 비용이 따르기 때문이다.

  • 노드가 제안에 투표하는 과정은 일종의 동기식 복제다. (성능에 손실)
  • 합의시스템은 엄격한 과반수가 동작하기를 요구한다.
  • 대부분 합의 알고리즘은 투표에 참여하는 노드가 고정되어있다고 가정한다. 이는 클러스터에 그냥 노드를 추가하거나 제거할 수 없다는 뜻이다.
  • 합의 시스템은 장애노드 감지를 대개 타임아웃에 의존한다. 네트워크 변동이 심한 환경에서 리더 선출이 빈번하게 생길 수 있는 가능성이 있다.
  • 네트워크 문제에 민감하다. e.g.) raft는 특정 네트워크링크가 불안정하다면 리더십이 두 노드 사이에서 왔다갔다 하는 현상이 발생해서 사실 상 시스템이 전혀 진행되지 못했다.

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

주키퍼나 etcd같은 프로젝트는 종종 분산 key-value 저장소 혹은 코디네이션과 설정 서비스라고 설명된다. 이게 데이터베이스라면 이것들은 왜 합의 알고리즘에 쓰이는걸까?

주키퍼는 보통 다른 프로젝트를 통해 간접적으로 의존하게 된다. e.g.) HBase, Hadoop Yarn, OpenStack Nova, kafka 등.

주키퍼와 etcd는 완전히 메모리 안에 들어올 수 있는 작은 데이터를 보관하도록 설계되었다. 이 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제된다.

주키퍼는 구글의 chubby 잠금 서비스를 모델로 삼아 전체 순서 브로드캐스트(그리고 합의도)를 구현할 뿐 아니라 다른 유용한 기능도 구현한다.

  • 선형적 원자적 연산

    • compare-and-set을 이용해 잠금을 구현할 수 있다. 분산 잠금은 보통 제한 시간이 있는 잠금, 즉 lease(임차권)으로 구현된다.
  • 연산의 전체 순서화

    • 펜싱토큰. 주키퍼는 모든 연산에 전체 순서를 정하고 트랜잭션 ID와 버전 번호를 할당해 달성한다.
  • 장애 감지

    • 클라이언트는 주키퍼 서버에 수명이 긴 세션을 유지하고 클라이언트와 서버는 주기적으로 하트비트를 교환해서 다른쪽이 살아있는지 확인한다. 세션 타임아웃보다 긴 시간동안 하트비트가 멈추면 주키퍼는 세션이 죽었다고 선언한다
  • 변경 알림

    • 클라이언트는 다른 클라이언트가 생성한 잠금과 값을 읽을 수 있을 뿐만 아니라 거기에 변경이 있는지 감시할 수도 있다.

작업을 노드에 할당하기

주키퍼/처비 모델이 잘 동작하는 예 1

  • 여러개의 프로세스나 서비스가 있고, 그 중 하나가 리더나 주 구성요소로 선택돼야할 때다. 단일리더 데이터베이스, 작업 스케줄러나 비슷한 상태저장시스템에도 유용하다

또다른 예 2

  • 파티셔닝된 자원이 있고 어떤 파티션을 어느 노드에 할당해야할지 결정하는 경우.
  • 파티셔닝 재균형화

이 종류의 작업은 주키퍼에서 원자적연산, 단명 노드, 알림을 잘 사용하면 사람의 개입 없이 결함으로부터 자동 복구하면서 잘 돌아간다. 애플리케이션은 결국 수천대의 노드로 늘어날 수도 있다. 매우 많은 노드에서 과반수 투표를 하는 것은 비효율적이므로, 주키퍼는 노드들을 코디네이트하는 작업의 일부를 외부 서비스의 위탁하는 방법을 제공한다.

서비스 디스커버리

주키퍼, etcd, 콘술은 서비스 찾기의 용도로 자주 사용된다. (특정 서비스에 연결하려면 어떤 IP로 접속해야하는가)

그런데 서비스 찾기가 실제로 합의가 필요한지는 분명해보이지 않는다. DNS는 서비스 이름으로 IP 주소를 찾는 전통적인 방법이고, 좋은 성능을 위해 다층 캐시를 이용한다. 이러면 분명히 기능이 선형적이지 않지만, 질의 결과가 뒤처지더라도 문제로 생각되지 않는다.

멤버십 서비스

주키퍼와 유사 프로젝트들은 오랜 멤버십 서비스 연구의 일부다. 멤버십 서비스는 클러스터에서 어떤 노드가 활성화된 멤버인지 결정한다. 장애 감지를 합의와 연결하면 (실제 상태와는 사실 무관하게) 어떤 노드가 살아있다고 여겨지고, 어떤게 죽었다고 여겨져야하는지 동의할 수 있다.