[데이터 중심 애플리케이션 설계] 09장. 정족수와 합의

Part 2. 분산 데이터

 

8장에서 설명했듯이 분산 시스템에서는 많은 것들이 잘못될 수 있다. 이런 결함을 다루는 가장 간단한 방법은 전체 서비스가 실패하도록 두고 사용자에게 오류 메시지를 보내는 것이다. 하지만 이 해결책을 받아들이기 힘들다면 결함을 견뎌낼(tolerating), 즉 내부 구성 요소 중 뭔가에 결함이 있더라도 서비스는 올바르게 동작하도록 할 방법을 찾아야 한다.

이번 장에서는 내결함성을 지닌 분산 시스템을 구축하는 데 쓰이는 알고리즘과 프로토콜의 몇 가지 예를 얘기한다. 내결함성을 지닌 시스템을 구축하는 가장 좋은 방법은 유용한 보장을 해주는 범용 추상화을 찾아 이를 구현하고 애플리케이션에서 이 보장에 의존하게 하는 것이다. 트랜잭션을 예로 들면, 트랜잭션을 사용함으로써 애플리케이션은 충돌이 없고(원자성) 다른 누구도 데이터베이스에 동시 접근하지 않으며(격리성) 저장 서비스는 완전히 믿을 수 있는(지속성) 것처럼 해동할 수 있다. 데이터베이스에 결함이 발생하더라도 트랜잭션 추상화가 이런 문제들을 숨겨서 애플리케이션이 걱정하지 않게 해준다.

이제 같은 방식을 사용해 애플리케이션이 분산 시스템에 있는 문제를 무시할 수 있게 만들어주는 추상화를 찾는다. 그 중 하나는 합의, 즉 모든 노드가 어떤 것에 동의하게 만드는 것이다.

애플리케이션은 합의의 구현을 다양한 목적으로 사용할 수 있다. 이를테면 단일 리더 복제 데이터베이스에서 리더가 죽었을 때, 노드들이 합의를 사용해서 새 리더를 뽑는 것이다. 이 때 두 노드가 자신이 리더라고 생각하는 split brain(스플릿 브레인)이 발생하여 데이터가 손실될 수 있는데, 올바르게 구현된 합의는 이런 문제들을 피할 수 있다.

이번 장 초반부에서는 분산 시스템에서 제공될 수 있는 보장과 추상화의 범위를 알아보고, 이후 합의와 합의 관련 문제를 해결하는 알고리즘을 살펴본다. 어떤 것을 할 수 있고, 없는지에 대한 범위를 이해해야 한다. 이러한 범위들과 한계는 수십년 동안 연구되어 왔기 떄문에, 겉핥기 방식으로 진행한다.

일관성 보장

복제 데이터베이스에는 타이밍 문제, 즉 동시에 다른 노드 2개를 볼 떄 서로 다른 데이터를 볼 가능성이 있다. 이런 불일치는 어떤 복제 방법을 쓰느냐에 상관 없이 일어난다.

복제 데이터베이스는 대부분 최소한 최종적 일관성을 제공한다. 쓰기 이후 시간이 지나면 결과적으로 모든 복제본이 같은 값으로 수렴되며, 읽기 요청이 같은 값을 반환한다는 뜻이다. 불일치는 일시적이며, 결국 스스로 해소된다.

하지만 이것은 매우 약한 보장이다. 왜냐하면 언제 복제본이 수렴될지에 대해서는 모르기 때문이다. 이런 약한 보장만 제공하는 데이터베이스를 다룰 때는 그 제한을 계속 알아야 하고 뜻하지 않게 너무 많은 것을 가정하면 안 된다. 대부분의 시간 동안은 잘 동작하겠지만, 동시성이 높아지거나 시스템에 결함이 생길 때 최종적 일관성의 에지 케이스가 드러난다.

이번 장에서는 데이터 시스템이 선택적으로 제공할 수 있는 더욱 강한 일관성 모델을 살펴본다. 이들은 성능이 나쁘거나 내결함성이 떨어질지도 모르지만, 이들은 올바르게 사용하기 쉬우므로 매력적이다.

분산 일관성 모델과 앞서 설명한 트랜잭션 격리 수준 계층에는 비슷한 점이 있다. 그러나 겹치는 부분이 있기는 해도 이들은 대개 독립적인 관심사이다.

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

이번 장에서는 광범위한 주제를 다루지만 앞으로 보게 될 것처럼 사실 이 영역들은 깊게 연결돼 있다.

• 먼저 공통적으로 사용하는 가장 강한 일관성 모델 중 하나인 linearizability(선형성)을 살펴보고 장점과 단점을 검토한다.
• 그 후 두 번쨰 절인 “순서화 보장”에서 분산 시스템에서 이벤트 순서화 문제. 특히 인과성과 전체 순서화와 관련된 문제를 검토한다.
• 마지막으로 세 번째 절인 “분산 트랜잭션과 합의”에서 분산 트랜잭션을 원자적으로 커밋하는 방법을 알아본다. 분산 트랜잭션은 마침내 합의 문제의 해결책으로 우리를 안내해 준다.

선형성

최종적 일관성을 지닌 데이터베이스에서 두 개의 다른 복제본에 같은 질문을 동시에 하면 두 가지 다른 응답을 받을지도 모른다. 이 때, 데이터베이스에는 복제본이 하나만 있다(즉 데이터 복사본이 하나만 있다)는 환상을 만들어준다면 모든 클라이언트는 똑같은 데이터를 보고 복제 지연을 걱정할 필요가 없을 것이다.

이것이 선형성을 뒷받침하는 아이디어다(atomic consistency(원자적 일관성), strong consistency(강한 일관성), immediate consistency(즉각 일관성), external consistency(외부 일관성)라고도 한다). 기본 아이디어는 시스템에 데이터 복사본이 하나만 있고, 그 데이터를 대상으로 수행하는 모든 연산은 원자적인 것처럼 보이게 만드는 것이다. 이런 보장이 있으면 현실에는 여러 복제본이 있더라도 애플리케이션은 거기에 신경 쓸 필요가 없다.

선형성 시스템에서는 클라이언트가 쓰기를 성공적으로 완료하자마자 그 데이터베이스를 읽는 모든 클라이언트는 방금 쓰여진 값을 볼 수 있어야 한다. 데이터의 복사본이 하나만 있다는 환상을 유지하는 것은 읽히는 값이 최근에 갱신된 값이며 뒤처진 캐시나 복제본에서 나온 값이 아니라고 보장해준다는 뜻이다. 다시 말해 선형성은 recency gurantee(최신성 보장)이다.

이 아이디어를 명확하게 하기 위해 비선형성 시스템의 예를 살펴보자.

이 시스템은 비선형이라서 축구팬들을 혼란스럽게 한다.

위의 예시에서는 앨리스와 밥이 같은 방에 앉아서 자신의 휴대폰으로 피파 월드컵 결승전 결과를 확인하고 있는 상황이다. 이 때 앨리스가 먼저 결과를 알게 되어 밥에게 독일이 이겼다고 알려주는데, 밥은 이 이야기를 들은 밥은 자신의 휴대폰의 웹사이트를 새로고침하지만, 그의 요청이 지연된 데이터베이스 복제본으로 전달돼서 아직 경기가 진행 중인 것으로 나타난다. 밥은 앨리스로부터 경기 결과를 들은 후에 새로고침 버튼을 눌렀음에도, 앨리스보다 데이터보다 오래된 데이터를 보게 된다. 질의가 오래된 결과를 반환했다는 것은 선형성 위반이다.

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

선형성을 뒷받침하는 아이디어는, 시스템에 데이터 복사본이 하나뿐인 것처럼 보이게 만드는 것이다. 이것이 무슨 뜻이지 정확히 알기 위해서 몇 가지 예를 더 살펴본다.

아래의 예는 선형성 데이터베이스에서 동시에 같은 키 x를 읽고 쓰는 세 클라이언트를 보여준다. 분산 시스템 분야에서는 x는 register(레지스터, 현실에서는 키-값 저장소의 키, 관계형 데이터베이스의 로우, 문서 데이터베이스 문서일 수 있음)라고 불린다.

읽기 요청이 쓰기 요청과 동시에 실행되면 과거의 값을 반환할 수도 있고 새로운 값을 반환할 수도 있다.

예시는 클라이언트들의 관점이며, 막대는 클라이언트의 요청, 막대의 시작은 요청을 보낸 시간, 막대의 끝은 클라이언트가 응답을 받은 시간이다. 클라이언트는 데이터베이스가 언제 자신의 요청을 처리했는지 알지 못한다.

이 예제에서 레지스터는 두 가지 종류의 연산이 있다.

• read(x) ⇒ v : 클라이언트가 v는 클라이언트가 레지스터 x의 값을 읽기를 요청했고 데이터베이스가 값 v를 변환했다는 것을 의미한다.
• write(x, v) ⇒ r : r은 클라이언트가 레지스터 x의 값을 v로 설정하라고 요청했고 데이터베이스가 응답 r(ok일 수도 있고, error일 수도 있음)을 반환했다는 것을 의미한다.

x의 값은 처음에 0이고, 클라이언트 C는 그 값을 1로 설정하는 쓰기 요청을 실행한다. 그 동안 클라이언트 A와 B는 최신 값을 받기 위해 주기적으로 x를 폴링한다.

이 때 A와 B는 자신의 읽기 요청에 대해 어떤 응답을 받을 수 있을까?

• 클라이언트 A가 실행한 첫 번째 읽기 연산은 쓰기가 시작하기 전에 완료되므로 이전 값인 0을 반환해야 하는 게 명백하다.
• 클라이언트 A가 실행한 마지막 읽기는 쓰기가 완료된 후 시작하므로 데이터베이스가 선형적이라면 새로운 값 1을 반환해야 한다.
• 쓰기 연산과 시간이 겹치는 읽기 연산은 0을 반환했을 수도, 1을 반환했을 수도 있다. 이 연산들은 쓰기와 동시에 실행된다.

현재 쓰기와 읽기가 동시에 실행되며, 읽기가 오래된 값과 새로운 값 중 하나를 반환할 수 있기 떄문에, 이는 “데이터의 단일 본사본”을 모방(선형성)하는 시스템에 기대하는 바가 아니다.

시스템을 선형적으로 만들려면 아래처럼 또 다른 제약 조건을 추가해야 한다.

읽기가 새로운 값을 반환한 적이 있은 후에는 모든 후속 읽기는 반드시 새로운 값을 반환해야 한다.

선형성 시스템에서는 x의 값이 원자적으로 0에서 1로 바뀌는 어떤 시점이 있다고 상상한다. 따라서 클라이언트의 읽기가 새로운 값 1을 반환하면 이후의 모든 읽기 또한 새로운 값을 반환해야 한다(쓰기 연산이 아직 완료되지 않았더라도).

클라이언트 A가 새로운 값 1을 읽은 첫 번째 클라이언트이므로, 이후의 읽기(클라이언트 B의 이어지는 읽기(화살표로 나타났음), 추가적인 클라이언트 A의 읽기)는 모두 1을 반환해야 한다.

이 타이밍 다이어그램을 더 개선해서 어떤 시점에 원자적으로 영향을 주는 개별 연산을 시각화할 수 있다.

읽기와 쓰기의 영향이 나타나는 것으로 보이는 시점을 시각화하기. B의 마지막 읽기는 선형적이지 않다.

읽기와 쓰기 외에 세 번째 종류의 연산을 추가한다.

• cas(x, v(old), v(new)) ⇒ r : r은 클라이언트가 원자적 compare-and-set 연산을 요청했다는 뜻이다. 레지스터 x의 현재 값이 v(old)와 같으면 원자적으로 v(new)로 설정돼야 한다. x ≠ v(old)라면 이 연산은 레지스터를 그대로 두고 오류를 반환해야 한다. r은 데이터베이스의 응답이다(ok나 error).

위의 그림에서 연산의 실행 시점이 수직선으로 표시되어 있다. 선형성의 요구사항은 이 수직선들을 이은 선들이 항상 시간순으로 진행돼야 하고, 결코 뒤로 가서는 안 된다는 것이다. 이 요구사항은 앞에서 설명한 최신성 보장이 되도록 만들어준다. 새로운 값이 쓰여지거나 읽히면 이후 실행되는 모든 읽기는 값이 다시 덮어쓰여질 때까지 쓰여진 값을 읽게 된다.

여기서 주목할 만한 흥미로운 세부 사항이 몇 가지 있다.

• 먼저 클라이언트 B가 x 읽기 요청을 보낸 후 클라이언트 D가 x를 0으로 설정하는 요청을 보낸다. 그렇지만 B의 읽기가 반환한 값은 1이다. 이것은 문제 없다. 데이터베이스가 D의 쓰기를 먼저 처리한 후 A의 쓰기를 처리헀고 마지막으로 B의 읽기를 처리했다는 의미다. 요청을 보낸 순서와는 다르지만 세 요청이 동시적이기 때문에 이 순서는 허용된다. 아마도 B의 읽기 요청이 네트워크에서 조금 지연돼서 두 개의 쓰기 요청보다 나중에 데이터베이스로 전달됐을 것이다.
• 클라이언트 B의 읽기는 클라이언트 A가 데이터베이스로부터 값을 1로 쓰는 데 성공했다는 응답을 받기 전에 1을 반환했다. 이것도 괜찮다. 값이 쓰여지기 전에 읽혔다는 의미가 아니라 데이터베이스에서 클라이언트 A로 가는 ok 응답이 네트워크에서 약간 지연됐다는 의미일 뿐이다.
• 이 모델은 어떤 트랜잭션 격리도 가정하지 않는다. 다른 클라이언트가 언제라도 값을 바꿀지 모른다. 예를 들어 C는 먼저 1을 읽고 그 다음에는 2를 읽었는데, 두 번의 읽기 사이에 B가 값을 변경했기 때문이다. 다른 클라이언트가 동시에 값을 바꾸지 않았는지 확인하기 위해 원자적 compare-and-set (cas) 연산을 쓸 수 있다. B와 C의 cas 요청은 성공하지만 D의 cas 요청은 실패한다(데이터베이스가 그 요청을 처리하는 시점에 x의 값은 더 이상 0이 아니므로).
• 클라이언트 B의 마지막 읽기(응영 처리된 막대)는 선형적이지 않다. 이 연산은 x를 2에서 4로 갱신하는 C의 cas 쓰기와 동시적이다. 다른 요청이 없다면 B의 읽기가 2를 반환해도 괜찮다. 그러나 클라이언트 A는 B의 읽기가 시작하기 전에 이미 새로운 값 4를 읽었다. 따라서 B는 A가 읽을 것보다 과거의 값을 읽는 것은 허용되지 않는다.

이것이 선형성 뒤에 있는 직관이다. 공식 정의에서는 이 선형성을 더 정확히 기술한다. (계산 비용이 크지만) 모든 요청과 응답 시점을 기록하고 그것들이 유효한 순차 순서로 배열되는지 확인함으로써 시스템의 동작이 선형적인지 테스트할 수도 있다.

선형성과 직렬성은 모두 “순차적인 순서로 배열될 수 있는” 뭔가를 의미하지만, 이 둘은 매우 다른 보장이며 이들을 구별하는 게 중요하다. 선형성: 선형성은 레지스터(개별 객체)에 실행되는 읽기와 쓰기에 대한 최신성 보장이다. 직렬성: 직렬성은 여러 트랜잭션들이 어떤 순서에 따라 실행되는 것처럼 동작하도록 보장해준다. 데이터베이스는 선형성과 직렬성 모두를 제공할 수 있으며 이들을 strict serializability(엄격한 직렬성)이나 strong one-copy serializability(강한 단일 복사본 직렬성)이라고 한다. 2단계 잠금을 기반으로 한 직렬성 구현은 선형적이지만, 직렬성 스냅숏 격리는 선형적이지 않다(스냅숏은 나중에 실행된 쓰기를 포함하지 않고, 이전의 데이터를 계속 반환하기 때문에 선형적이지 않음).

선형성에 기대기

위의 스포츠 시합의 최종 점수 조회에서 선형성은 크게 유용하지 않다. 하지만 시스템이 올바르게 동작하도록 만들기 위해 선형성이 중요한 요구사항이 되는 영역이 몇 가지 있다.

 

잠금과 리더 선출

단일 리더 복제를 사용하는 시스템은 리더가 하나만 존재하도록 보장해야 한다. 리더를 선출하는 한 가지 방법은 잠금을 이용하는 것이다. 모든 노드에서 잠금 획득을 시도하고, 성공한 노드가 리더가 되는 방식을 사용하는데, 이 때 잠금은 선형적이여야 한다. 모든 노드는 어느 노드가 잠금을 소유하는지에 동의해야 한다.

분산 잠금과 리더 선출을 구혆하기 위해 Apache ZooKeeper(아파치 주키퍼)나 etcd 같은 코디네이션 서비스가 종종 사용된다. 이들은 합의 알고리즘을 사용해 선형성 연산을 내결함성이 있는 방식으로 구현한다. 잠금과 리더 선출을 올바르게 구현하는 데는 미묘한 세부 사항이 여전히 많고 Apache Cuartor(아파치 큐레이터) 같은 라이브러리는 주키퍼 위에 고수준 레시피를 제공해서 도움을 준다. 그러나 이런 코디네이션 작업에는 선형성 저장소 서비스가 기초적인 기반이 된다.

분산 잠금은 Oracle Real Applciation Cluster, RAC(오라클 리얼 애플리케이션 클러스터) 같은 분산 데이터베이스에서 훨씬 세분화된 수준으로 사용되기도 한다. RAC은 여러 노드가 동일한 디스크 저장 시스템을 공유해서 접근하며 디스크 페이지마다 잠금을 사용한다. 이런 선형성 잠금은 트랜잭션 실행의 critical path(중요 경로)에 있으므로 RAC을 배치할 때는 보통 데이터베이스 노드들 사이의 통신용으로 전용 클러스터 연결 네트워크를 사용한다.

 

제약 조건과 유일성 보장

유일성 제약 조건은 데이터베이스에서 흔하다(사용자명이 유일해야 하거나, 파일 이름이 유일해야 하거나). 이 제약 조건을 강제하고 싶다면 선형성이 필요하다.

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

이 외에도 은행 계좌 잔고, 재고 관리, 좌석 예약 등에서 비슷한 문제가 생긴다. 모든 이런 제약 조건은 모든 노드가 동의하는 하나의 최신 값(계좌 잔고, 재고 수준, 좌석 점유)이 있기를 요구한다. 실제 애플리케이션에서는 때때로 이런 제약 조건을 느슨하게 다뤄도 된다(좌석이 점유됬으면 다른 곳으로 옮기고 보상을 하는 등). 이런 경우에는 선형성이 필요 없을 수도 있다.

그러나 관계형 데이터베이스에서 전형적으로 볼 수 있는 엄격한 유일성 제약 조건은 선형성이 필요하다. 외래 키나 속성 제약 조건 같은 다른 종류의 제약 조건은 선형성을 요구하지 않고도 구현할 수 있다.

 

채널 간 타이밍 의존성

위의 스포츠 시합의 최종 점수 조회에서, 앨리스가 점수를 밥에게 알려주지 않았다면, 밥은 자신의 질의 결과가 뒤쳐졌다는 것을 알지 못했을 것이다. 이처럼 선형성 위반은 시스템에 부가적인 통신 채널이 있었기 떄문에 발견됐다.

컴퓨터 시스템에서 비슷한 상황이 발생할 수 있다.

웹 서버와 이미지 크기 변경 모듈은 파일 저장소와 메시지 큐를 모두 써서 통신하므로 경쟁 조건이 발생할 가능성이 열려 있다.

위의 예시에서는 사용자가 사진을 올릴 때, 웹 서버에서 이미지를 받은 후 원본을 파일 저장소에 올리고, 이미지 크기 변경 모듈에 크기 변경 작업 메시지를 메시지 큐에 넣는다. 이후 메시지를 이미지 크기 변경 모듈이 받으면, 파일 저장소에서 원본 이미지를 가져와 크기 변경 후 다시 저장한다.

파일 저장 서비스가 선형적이면 이 시스템은 잘 동작한다. 하지만 선형적이지 않다면 경쟁 조건의 위험이 있다. 만약 메시지 큐가 파일 저장소의 내부의 복제보다 빠르면, 크기 변경 모듈이 없는 이미지를 읽거나, 과거 버전의 이미지를 읽어 원본과 변경된 이미지가 영구적으로 불일치하게 된다.

이 문제는 웹 서버와 크기 변경 모듈 사이에 두 가지 다른 통신 채널, 파일 저장소와 메시지 큐가 있기 때문에 발생한다. 선형성의 최신성 보장이 없으면 이 두 채널 사이에 경쟁 조건이 발생할 수 있다.

선형성이 경쟁 조건을 회피하는 유일한 방법은 아니지만 이해하기에 가장 단순하다. 부가적인 통신 채널을 제어한다면 복잡성이 추가되는 대신 “자신이 쓴 내용 읽기”와 같은 비슷한 대안을 사용할 수도 있다.

선형성 시스템 구현하기

선형성이 유용한 몇 가지 예를 살펴보았으니 이제 선형성 시맨틱을 제공하는 시스템을 어떻게 구현할지 생각해 보자.

선형성은 근본적으로 “데이터 복사본이 하나만 있는 것처럼 동작하고 그 데이터에 실행되는 모든 연산은 원자적”이라는 것을 의미하므로, 가장 간단한 해답은 정말로 데이터 복사본 하나만 사용하는 것이다.

하지만 이 방법으로는 결함을 견뎌낼 수 없다. 하나의 복사본을 저장한 노드에 장애가 나면 데이터에 소실 또는 접근할 수 없기 때문이다.

시스템이 내결함성을 지니도록 만드는 가장 흔한 방법은 복제를 사용하는 것이다. 복제 방법들을 살펴보며 선형적으로 만들 수 있는지 비교해 보자.

• 단일 리더 복제(선형적이 될 가능성이 있음): 리더나 동기식으로 갱신된 팔로워에서 실행한 읽기는 선형적이 될 가능성이 있다. 그러나 모든 단일 리더 데이터베이스가 실제로 선형적인 것은 아니다. 설계 때문일 수도 있고, 동시성 버그 때문일 수도 있다.
• 합의 알고리즘(선형적): 이 알고리즘은 단일 리더 복제를 닮았다. 그러나 합의 프로토콜에는 스플릿 브레인과 복제본이 뒤처지는 문제를 막을 수단이 포함된다. 이런 세부 사항 덕에 합의 알고리즘은 선형성 저장소를 안전하게 구현할 수 있다. 예를 들어 Zookeeper와 etcd가 이렇게 동작한다.
• 다중 리더 복제(비선형적): 여러 노드에서 동시에 쓰기를 처리하고 그렇게 쓰여진 내용을 비동기로 다른 노드에 복젭하기 떄문에 이들은 선형적이지 않다. 이런 까닭으로 다중 리더 복제 시스템은 충돌 해소가 필요한 충돌 쓰기를 만들 수 있다. 이런 충돌은 데이터의 단일 복사본만 존재하는 게 아니라서 발생하는 부산물이다.
• 리더 없는 복제(아마도 비선형적): 사람들은 때떄로 다이나모 스타일에 대해 정족수 읽기/쓰기를 통해 “엄격한 일관성”을 달성할 수 있다고 생각한다. 하지만 이는 정족수의 정확한 설정에 따라, 그리고 엄격한 일관성을 어떻게 정의하느냐에 따라 달라진다. 일 기준 시계를 기반으로 한 “최종 쓰기 승리” 충돌 해소 방법은 거의 확실히 비선형적이다. 시계 타임스탬프는 clock skew(시계 스큐) 때문에 이벤트의 실제 순서와 일치하리라고 보장할 수 없기 때문이다. 느슨한 정족수도 선형성의 가능성을 망친다.

선형성과 정족수

직관적으로 다이나모 스타일 모델에서 엄격한 정족수를 사용한 읽기 쓰기는 선형적인 것처럼 보인다. 하지만 아래 예처럼 네트워크 지연의 변동이 심하면 경쟁 조건이 생길 수 있다.

엄격한 정족수를 사용하지만 비선형적인 실행

위에서 x의 초깃값은 0이고 쓰기 클라이언트가 세 복제본에 모두 쓰기 요청을 보내서 x를 1로 갱신한다(n = 3, w = 3). 동시에 클라이언트 A는 두 노드로 구성된 정속수로부터 읽어서(r=2) 그러한 노드들 중 하나에서 새로운 값 1을 본다. 또 쓰기와 동시에 클라이언트 B는 두 노드로 구성된 다른 정족수로부터 읽어서 두 노드 모두에서 예전 값 0을 본다.

이처럼 정족수 조건이 만족(w + r > n)됨에도 이 실행은 선형적이지 않다. B의 요청은 A의 요청이 완료된 후 시작하지만 A는 새 값을 반환하는 반면 B는 예전 값을 반환한다.

흥미롭게도 성능이 떨어지는 비용을 지불하고 다이나모 스타일 정족수를 선형적으로 만드는 게 가능하다. 읽기를 실행하는 클라이언트는 결과를 애플리케이션에 반환하기 전에 읽기 복구를 동기식으로 수행해야 하고, 쓰기를 실행하는 클라이언트는 쓰기 요청을 보내기 전에 노드들의 정족수부터 최신 상태를 읽어야 한다.

그러나 Riak은 성능상의 불이익 떄문에 동기식 읽기 복구를 수행하지 않으며, Cassandra는 정족수 읽기를 할 때 읽기 복구가 완료되기를 기다린다. 최종 쓰기 승리 충돌 해소 방법을 쓰기 때문에 같은 키에 여러 쓰기를 동시에 실행하면 선형성을 잃게 된다. 또한 이 방법으로는 선형성 읽기와 쓰기 연산만 구현할 수 있다. 선형성 compare-and-set 연산은 합의 알고리즘이 필요하므로 구현할 수 없다.

요약하면 다이나모 스타일 복제를 하는 리더 없는 시스템은 선형성을 제공하지 않는다고 보는 게 가장 안전하다.

선형성의 비용

복제 방법 중에는 선형성을 제공하는 것도 있고 그렇지 않은 것도 있으므로 선형성의 장단점을 더 깊이 살펴보는 것은 흥미로운 일이다.

5장에서 이미 다양한 복제 방법의 몇 가지 사용 사례를 살펴봤다. 예를 들어 다중 리더 복제는 종종 다중 데이터센터 복제에 좋은 선택이라는 것을 봤다. 이런 배치의 예가 아래에 나와있다.

네트워크가 끊기면 선형성과 가용성 사이에서 선택해야만 한다.

만약 두 데이터센터 사이에 네트워크가 끊기면 무슨 일이 생길지 생각해 보자. 각 데이터센터 내부 네트워크는 동작하고 클라이언트들은 데이터센터에 접근할 수 있지만 데이터센터끼리는 서로 연결할 수 없다고 가정한다.

다중 리더 데이터베이스를 사용하면 각 데이터센터는 계속 정상 동작할 수 있다. 한 데이터센터에 쓰여진 내용이 비동기로 다른 데이터센터로 복제되므로 쓰기는 그냥 큐에 쌓였다가 네트워크 연결이 복구되면 전달된다.

반면 단일 리더 복제를 사용하면 리더가 데이터센터 중 한 곳에만 존재한다. 모든 쓰기와 선형성 읽기는 리더로 보내져야 하지만, 네트워크가 끊겨 팔로워 데이터센터로 접속한 클라이언트들은 리더로 연결할 수 없으므로 데이터베이스에 아무것도 쓸 수 없고, 선형성 읽기로 할 수 없다. 읽을 수 있는 데이터는 예전 데이터일 수 있다(비선형적). 따라서 리더에 접속할 수 없고, 팔로워 데이터센터로만 접속할 수 있는 클라이언트는 네트워크 링크가 복구될 떄까지 중단을 경험하게 된다.

CAP 정리

사실 이 문제는 어떤 선형성 데이터베이스라도 구현이 어떻게 됐는지에 상관없이 이 문제가 있으며, 다중 데이터베이스의 배치에 특정되지도 않은, 한 데이터센터 내에서도 발생할 수 있는 문제이다.

이에 관한 트레이드오프는 다음과 같다.

• 애플리케이션에서 선형성을 요구하고 네트워크 문제 때문에 일부 복제 서버가 다른 복제 서버와 연결이 끊기면 일부 복제 서버는 연결이 끊긴 동안은 요청을 처리할 수 없다. 네트워크 문제가 고쳐질 때까지 기다리거나 오류를 반환해야 한다 → 가용성을 포기 (CP)
• 애플리케이션에서 선형성을 요구하지 않는다면 각 복제 서버가 다른 복제 서버와 연결이 끊기더라도 독립적으로 요청을 처리하는 방식으로 쓰기를 처리할 수 있다. 이 경우 애플리케이션은 네트워크 문제에 직면해도 가용한 상태를 유지하지만 그 동작은 선형적이지 않다 → 일관성을 포기 (AP)

따라서 선형성이 필요 없는 애플리케이션은 네트워크 문제에 더 강인하다. 이런 통찰력은 CAP 정리로 널리 알려졌다. 이 법칙은 1970년대부터 분산 데이터베이스 설계자들에게 알려졌으며, 데이터베이스에서의 트레이드오프에 관한 논의를 목적으로 제안됐다. 이후 대규모 웹 서비를 구현하는 데 더욱 적합한 분산 비공유 시스템에서도 활용되기 시작했다.

도움이 안 되는 CAP 정리 CAP는 때떄로 Consistency(일관성), Availability(가용성), Partition tolerance(분단 내성)이라는 세 개 중 두 개를 고르라는 것으로 표현된다. 하지만 이런 식으로 생각하면 오해의 소지가 있다. 네트워크 분단은 일종의 결함이지 선택할 수 있는 뭔가가 아니기 때문이다. 네트워크 분단은 좋던 싫든 발생한다. 네트워크가 올바르게 동작할 때는 시스템이 일관성(선형성)과 완전한 가용성 모두를 제공할 수 있다. 네트워크 결함이 생기면 선형성과 완전한 가용성 사이에서 선택해야 한다. 따라서 CAP는 네트워크 분단이 생겼을 때 일관성과 가용성 중 하나를 선택하라는 의미로 보는 게 좋다. CAP에 대한 논의에는 단어에 몇 가지 모순된 정의가 있고, 공식적인 정리가 보통의 의미와 부합하지 않으므로, 많은 오해와 혼란이 있다. 따라서 CAP는 피하는 게 최선이다.

하지만 공식적으로 정의된 CAP 정리는 매우 범위가 좁다. 오직 하나의 일관성 모델(즉 선형성)과 한 종류의 결함(네트워크 분단 혹은 노드가 살아있지만 서로 연결이 끊긴 상황)만 고려한다. 네트워크 지연, 죽은 노드나 다른 트레이드오프에 대해서는 어떤 것도 얘기하지 않는다. 그러므로 CAP가 역사적인 영향력은 있지만 시스템을 설계할 때는 실용적인 가치가 거의 없다. 이제 분산 시스템에는 여러 가지 더욱 흥미로운 impossibility(불가능성) 결과가 있고 CAP는 이제 더 정확한 결과로 대체됐으므로 오늘날에는 대부분 역사적인 관심사일 뿐이다.

선형성과 네트워크 지연

선형성은 유용한 보장이지만 현실에서 실제로 선형적인 시스템은 놀랄 만큼 드물다. 예를 들어 최신 다중코어 CPU의 RAM 조차 선형적이지 않다. 하나의 CPU 코어에서 실행 중인 스레드가 메모리 주소에 쓴 후 곧 다른 CPU 코어에서 실행되는 스레드가 같은 주소를 읽을 때 첫 번쨰 스레드가 쓴 값을 읽을 것이라고 보장되지 않는다(메모리 배리어나 펜스를 쓰지 않으면).

이렇게 동작하는 까닭은 모든 CPU 코어가 저마다 메모리 캐시와 저장 버퍼를 가지고 있기 때문이다. 메모리 접근은 기본적으로 캐시로 먼저 가고 변경은 메인 메모리에 비동기로 기록된다. 캐시에 있는 데이터를 접근하는 게 메인 메모리로 가는 것보다 훨씬 더 빠르므로 이런 특성은 최신 CPU에서 좋은 성능을 내는 데 필수적이다. 따라서 데이터 복사본은 몇 개(메인 메모리, 캐시들)에 생기며 비동기로 갱신되기 때문에, 선형성이 손실된다.

다중코어 CPU가 이러한 트레이드오프를 만든 이유는 성능(빠르게 데이터를 처리하기 위함) 때문이다. 마찬가지로 만약 분산 데이터베이스에서 선형성 보장을 제공하지 않도록 택했다면 그것은 내결함성 때문이 아니라 주로 성능을 향상시키기 위함이다.

그렇다면 좀 더 효율적인 선형 저장소 구현을 찾을 수 없을까? 아직은 찾지 못했다. Attiya와 Welch는 선형성을 원하면 읽기와 쓰기 요청의 응답 시간이 적어도 네트워크 지연의 불확실성에 비례해야 함을 증명했다. 대부분의 컴퓨터 네트워크처럼 지연의 변동의 매우 심한 네트워크에서 선형성 읽기와 쓰기의 응답 시간은 필연적으로 높아진다.

선형성을 제공하는 더욱 빠른 알고리즘은 존재하지 않지만 완화된 일관성 모델은 훨씬 더 빠를 수 있다. 따라서 지연 시간에 민감한 시스템에서는 이 트레이드오프가 중요하다. 12장에서는 정확성을 희생하지 않고 선형성을 회피하는 방법을 설명한다.

순서화 보장

앞에서 선형성 레지스터는 데이터 복사본이 하나만 있는 것처럼 동작하고, 모든 연산이 어느 시점에 원자적으로 효과가 나타나는 것처럼 보인다고 했다. 이 정의는 연산들이 어떤 잘 정의된 순서대로 실행된다는 것을 암시한다. 즉, 순서화를 나타낸다.

순서화는 계속 되풀이된 주제이며, 이는 순서화가 중요한 근본적 아이디어일 수도 있다는 것을 시사한다.

• 5장에서 단일 리더 복제에서 리더의 주 목적은 복제 로그에서 쓰기의 순서, 즉 팔로워가 쓰기를 적용하는 순서를 결정하는 것이라고 배웠다. 단일 리더가 없다면 동시에 실행되는 연산 때문에 충돌이 발생할 수 있다.
• 7장에서 설명한 직렬성은 트랜잭션들이 마치 어떤 일련 순서에 따라 실행되는 것처럼 동작하도록 보장하는 것과 관련돼 있다. 말 그대로 트랜잭션을 직렬적인 순서대로 실행해서 직렬성을 얻을 수도 있고 동시 실행을 허용하지만 직렬성 충돌을 막는 방법이다.
• 8장에서 설명한, 분산 시스템에서 타임스탬프와 시계 사용은 무질서한 세상에 질서를 부여하려는 또 다른 시도다. 두 개의 쓰기 중 어느 것이 나중에 일어났는지 결정하는 것을 한 가지 예로 들 수 있다.

순서화, 선형성, 합의 사이에는 깊은 연결 관계가 있음이 드러난다. 이들은 이론적이지만 시스템이 무엇을 할 수 있고 무엇을 할 수 없는지에 대한 이해를 명확하게 하는 데 매우 큰 도움이 된다. 다음 몇 개의 절에서 이 주제를 살펴보겠다.

순서화와 인과성

순서화가 계쏙 나오는 이유가 몇 가지 있는데 그 중 하나는 순서화가 인과성을 보존하는 데 도움을 준다는 것이다. 앞 장들에서 인과성이 중요한 몇 가지 예를 이미 살펴보았다.

• “일관된 순서로 읽기”에서 대화의 관찰자가 질문에 대한 응답을 먼저 보고 나서 응답된 질문을 보게 되는 예를 봤다. 이는 원인과 결과에 관한 직관을 위반하기 때문에 혼란스럽다. 이를 질문과 답변 사이의 causal dependency(인과적 의존성)이 있다고 말한다.
• 세 리더 사이의 복제에서, 네트워크 지연 떄문에 어떤 쓰기가 다른 쓰기를 “추월”할 수 있음을 알았다. 복제 서버 중 한 대의 관점에서는 존재하지 않는 로우를 갱신한 것처럼 보인다. 여기서 인과성은 로우가 갱신되기 전에 먼저 생성돼야 함을 의미한다.
• “동시 쓰기 감지”에서 두 개의 연산 A와 B가 있으면 세 가지 가능성이 있음을 봤다. 이런 happened bdfore(이전 발생) 관계는 인과성을 표현하는 또 다른 방법이다.
• 트랜잭션용 스냅숏 격리의 맥락에서 트랜잭션은 일관된 스냅숏으로부터 읽는다고 했다. 여기서 일관적이라는 것은 consistent with causality(인과성에 일관적)이라는 의미이다. 한 시점에 그 시점 이전의 모든 데이터를 볼 수 있고, 이후의 데이터를 볼 수 없다면 인과성에 일관적이게 된다. 읽기 스큐는 이 인과성을 위반하는 상태에 있는 데이터(시점 이후 데이터)를 읽는 것을 의미한다.
• 트랜잭션들 사이의 쓰기 스큐 예제는 인과적 의존성도 보여준다. 쓰기는 해당 전제에 인과적으로 의존한다. 직렬성 스냅숏 격리(SSI)는 트랜잭션 사이의 인과적 의존성을 추적함으로써 쓰기 스큐를 검출한다.
• 앨리스와 밥의 예제에서 밥이 앨리스로부터 결과를 들은 후 서버로부터 뒤쳐진 결과를 받은 것은 인과성 위반이다. 이미지 크기 변경 서비스 예제도 같은 패턴을 나타낸다.

인과성은 이벤트에 순서를 부과한다. 결과(메시지 받기, 답변하기 등)이 나타나기 전에 원인(메시지 보내기, 질문하기)이 발생한다. 또한 한 가지가 다른 것을 유발할 수 있다(노드의 데이터 전파 등). 인과적으로 의존하는 연산의 이런 연쇄는 시스템에서 인과적 순서, 즉 무엇이 무엇보다 먼저 일어났는가를 정의한다.

시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 causally consistent(인과적으로 일관적)이라고 한다. 예를 들어 스냅숏 격리는 인과적 일관성을 제공한다. 데이터베이스에서 읽어서 데이터의 어떤 조각을 봤다면 그보다 인과적으로 먼저 발생한 어떤 데이터도 볼 수 있어야 한다.

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

total order(전체 순서)는 어떤 두 요소를 비교할 수 있게 하므로 두 요소가 있으면 항상 어떤 것이 더 크고 어떤 것이 더 작은지 말할 수 있다. 예를 들어 자연수는 전체 순서를 정할 수 있다(5는 13보다 크다).

그러나 수학적 집합은 항상 전체 순서를 정할 수 있는 것은 아니다. {a,b}가 {b,c}는 서로의 부분 집합이 아니므로 비교 불가능하다. 이 경우를 incomparable(비교불가)하고 따라서 수학적 집합은 partially ordered(부분적으로 순서가 정해진다).

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

• 선형성: 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다. 선형성 시스템에서는 하나의 데이터에 대해 모든 연산이 원자적으로 수행되므로 순서가 항상 존재한다.
• 인과성: 인과성은 부분 순서를 정의한다. 두 이벤트에 인과성이 있으면 순서가 존재하지만, 동시에 실행되면 비교할 수 있다.

그러므로 이 정의에 따르면 선형성 데이터스토어에는 동시적 연산이 없다. 모든 연산은 하나의 타임라인을 따라서 원자적으로 처리된다는 것이 보장된다. 만약 동시성이 발생한다면 타임라인이 갈라졌다 다시 합쳐지는 것을 의미한다.

Git 같은 분산 버전 관리 시스템에서의 버전 히스토리는 인과적 의존성 그래프와 매우 유사하다. 종종 하나의 커밋은 다른 것보다 일직선 상에서 나중에 실행되지만 여러 브랜치에 동시에 만들어진 커밋을 합칠 때 머지 커밋이 생성된다.

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

선형성은 인과성을 내포한다. 어떤 시스템이든지 선형적이라면 인과성도 올바르게 유지한다. 이러한 사실은 선형성 시스템을 이해하기도 쉽고 매력적으로 보이게 만들어준다. 하지만 시스템을 선형적으로 만들면, 네트워크 지연이 클 경우 성능과 가용성에 해가 될 수 있다.

하지만 절충안이 있다. 이를 통해 성능 손해를 유발하지 않고도 인과적 일관성을 만족시킬 수 있다. 사실 인과적 일관성은 네트워크 지연 때문에 느려지지 않고 네트워크 장애가 발생해도 가용한 일관성 모델 중 가장 강한 것이다.

많은 경우에 선형성이 필요한 것처럼 보이는 시스템에 사실 진짜로 필요한 것은 인과적 일관성이며 이는 더 효율적으로 구현될 수 있다. 현재 이를 구현하는 데이터베이스 연구가 진행되고 있다.

인과적 의존성 담기

비선형성 시스템이 인과적 일관성을 유지할 수 있는 핵심 아이디어 중 일부만 간단히 살펴보자.

인과성을 유지하기 위해 어떤 연산이 어떤 다른 연산보다 먼저 실행됐는지 알아야 한다. 이것은 부분 순서이며, 연산의 순서는 모든 복제 서버에서 똑같아야 한다. 따라서 복제 서버에서 아직 처리하지 못한 선행 연산이 있다면 먼저 처리해야 한다.

인과적 의존성을 결정하려면 시스템에 있는 노드에 관한 “지식”을 기술할 방법이 필요하다. “동시 쓰기 감지”에서 살펴본 갱신 손실 방지를 위해 같은 키에 대한 동시 쓰기 검출 기법에서 더 나아가, 단일 키뿐만 아니라 전체 데이터베이스에 걸친 인과적 의존성을 추적해야 한다. 이를 위해 version vector(버전 벡터)를 일반화할 수 있다.

인과적 순서를 결정하기 위해 데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아야 한다(이를 위해 이전 연산의 버전 번호를 데이터베이스로 되돌려줘야 함). “직렬성 스냅숏 격리(SSI)”에서 설명한 SSI 충돌 검출에서도 비슷한 아이디어가 나타난다. 트랜잭션이 커밋을 원할 때 데이터베이스는 읽은 데이터의 버전이 여전히 최신인지 확인한다. 이런 목적으로 데이터베이스는 어떤 데이터를 어떤 트랜잭션이 읽었는지 추적한다.

일련번호 순서화

인과성은 중요한 이론적 개념이지만 모든 인과적 의존성을 실제로 추적하는 것은 실용성이 떨어진다. 여러 애플리케이션은 뭔가를 쓰기 전에 많은 데이터를 읽고, 쓰기가 어떤 읽기에 인과적으로 의존하는지 명확하지도 않다. 읽은 데이터들을 모두 명시적으로 추적하는 것은 오버헤드가 크다.

그러나 더 좋은 방법이 있다. 일련번호나 타임스탬프를 써서 이벤트의 순서를 정할 수 있다. 타임스탭프는 일 기준 시계(신뢰성 없는 시계) 대신 논리적 시계에서 얻어도 된다. 논리적 시계는 연산을 식별하는 일련번호를 생성하는 알고리즘이고 보통 모든 연산마다 증가하는 카운터를 사용한다.

이런 일련번호나 타임스탬프는 크기가 작고 전체 순서를 제공한다. 특히 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다. 모든 연산은 고유 일련번호를 가지고, 이들을 비교해서 항상 인과성을 결정할 수 있다는 것이다.

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

비인과적 일련번호 생성기

단일 리더가 없다면(다중 리더, 리더 없는 데이터베이스, 파티셔닝된 데이터베이스) 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않는다. 현실에서는 다양한 방법이 사용된다.

• 각 노드가 자신만의 독립적인 일련번호 집합을 생성할 수 있다. 예를 들어 노드가 두 대 있으면 한 노드는 홀수만 생성하고 다른 노드는 짝수만 생성할 수 있다. 일반적으로 일련번호의 이진 표현에서 몇 비트를 예약해서 고유 노드 식별자를 포함할 수 있고, 이렇게 하면 두 대의 다른 노드가 같은 일련번호를 생성하는 일은 결코 없을 거라고 확신할 수 있다.
• 각 연산에 일 기준 시계(물리적 시계)에서 얻은 타임스탬프를 붙일 수 있다. 이런 타임스탬프는 순차적이지 않지만 해상도가 충분히 높다면 연산의 전체 순서를 정하는 데 충분할 수도 있다. 이 사실은 최종 쓰기 승리 충돌 해소 방법에서 사용된다.
• 일련번호 블록을 미리 할당할 수 있다. 이를테면 노드 A는 일련번호 1부터 1,000까지의 블록을 차지하고 노드 B는 1,001부터 2,000까지의 블록을 차지할 수 있다. 그러면 각 노드는 독립적으로 자신의 블록에서 일련번호를 배정할 수 있고 일련번호 비축량이 낮아지기 시작하면 새 블록을 할당할 수 있다.

이 세 가지 선택지는 모두 잘 동작하며, 카운터를 증가시키는 단일 리더에 모든 연산을 밀어넣는 것보다 확장성이 좋다. 이것들은 연산마다 approximately increasing(고유한 근사 증가) 일련번호를 생성한다. 그러나 여기엔 문제가 하나 있는데, 생성한 일련번호가 인과성에 일반적이지 않다는 것이다. 이는 일련번호 생성기들이 여러 노드에 걸친 연산의 순서를 올바르게 담지 못하기 때문에 발생한다.

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

램포트 타임스탬프

위의 세 가지 일련번호 생성기는 인과성에 비일관적이다. 하지만 인과성에 일관적인 일련번호를 생성하는 간단한 방법이 실제로 있다. Lamport timestamp(램포트 타임스탬프)라고 불리는 이 방법은 레슬리 램포트(Leslie Lamport)가 1978년에 제안하였으며, 현재 분산 시스템 분야에서 가장 많이 인용된 논문 중 하나이다.

램포트 타임스탬프는 인과성에 일관적인 전체 순서화를 제공한다.

위의 그림에서 설명된 것과 같이, 각 노드는 고유 식별자를 가지고 각 노드는 처리한 연산 개수를 카운터로 유지한다. 램포트 타임스탬프는 (카운터, 노드 ID)의 쌍이다. 노드의 카운터 값이 같을 수는 있지만, 노드 ID가 다르기 때문에 유일하다.

램포트 타임스탬프는 전체 순서화를 제공한다. 카운터가 큰 것이 타임스탬프가 크며, 만약 카운터 값이 같으면 노드 ID가 큰 것이 타임스탬프가 크다. 여기까지는 짝수/홀수 카운터와 본질적으로 같다.

하지만 여기서 램포트 타임스탬프가 인과성에 일관적이게 되는 핵심 아이디어가 추가된다. 모든 노드와 모든 클라이언트가 지금까지 본 카운터 값 중 최댓값을 추적하고(응답으로 더 큰 카운터 값을 받으면 본인의 카운터를 갱신), 모든 요청에 그 최댓값을 포함시킨다.

위의 그림에서 클라이언트 A는 노드 2로부터 카운터 값 5를 받고, 이후 노드 1에게 최댓값 5을 보낸다. 그러면 노드 1의 카운터는 기존 1에서 5로 바뀌고, 따라서 다음 연산은 증가된 카운터 값 6을 갖는다.

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

램포트 타임스탬프는 “동시 쓰기 감지”에서 봤던 버전 벡터와 혼동된다. 둘은 비슷한 점이 있지만 목적이 다르다.

• 버전 벡터: 두 연산이 동시적인지 또는 어떤 연산이 다른 연산에 인과적으로 의존하는지 구별할 수 있음
• 램포트 타임스탬프: 항상 전체 순서화를 강제함. 전체 순서화로부터 두 연산이 동시적인지 또는 인과적으로 의존성이 있는지를 알 수 없다.

램포트 타임스탬프가 버전 벡터보다 좋은 점은 크기가 더 작다는 것이다.

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

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

예를 들어 사용자명으로 사용자 계정을 유일하게 식별할 수 있는 시스템에서, 두 사용자가 동시에 동일한 사용자명으로 계정을 생성하려고 하면 더 빠른 쪽이 성공하고, 다른 사람은 실패해야 한다.

연산의 전체 순서화(더 낮은 타임스탬프가 성공, 더 큰 타임스탬프는 실패)가 이를 해결할 수 있는 것처럼 보이지만, 노드가 다른 노드들과 통신하지 않고 당장 성공 여부를 결정해야 하는 상황에서는 부족하다. 동일한 사용자명을 처리하는 다른 노드가 그 연산에 어떤 타임스탬프를 배정할지 알지 못하기 때문이다.

연산의 전체 순서화에서는 다른 모든 노드가 무엇을 하고 있는지 확인해야 하며, 일부 노드가 장애 또는 네트워크 문제가 발생하면 시스템에 멈추게 된다. 이것은 우리가 필요한 내결함성 시스템의 유형이 아니다. 연산의 전체 순서화에서의 문제는, 연산의 전체 순서가 모든 연산을 모은 후에야 드러난다는 것이다.

따라서 사용자명 같은 것에 대한 유일성 제약 조건 같은 것을 구현하려면 연산의 전체 순서가 있는 것으로는 충분치 않다. 언제 그 순서가 확정되는지도 알아야 하며, 사용자명 생성 연산 이전에 다른 노드가 끼워 넣을 수 없다고 판단되면 그 연산을 성공으로 선언해도 안전하다.

이렇게 전체 순서가 확정되는지 알아야 한다는 아이디어는 전체 순서 브로드캐스트의 주제로 넘어가게 된다.

전체 순서 브로드캐스트

프로그램이 단일 CPU 코어에서만 실행된다면 CPU에서 실행된 순서가 전체 순서이므로 연산의 전체 순서를 정하기 쉽다. 하지만 분산 시스템에서는 모든 노드에서 연산의 전체 순서가 동일하도록 합의하기가 까다롭다. 이를 해결하기 위한 타임스탬프나 일련번호를 사용한 순서화는 단일 리더 복제만큼 강력하지 않다는 것을 발견했다.

단일 리더 복제에서는 리더 노드의 CPU 코어에서 모든 연산을 차례대로 배열함으로써 연산의 전체 순서를 정할 수 있다. 하지만 문제는 처치량이 단일 리더가 처리할 수 있는 수준을 넘어셨을 때 시스템을 어떻게 확장할 것인가와, 리더에 장애가 발생했을 때 어떻게 장애 복구를 처리할 것인가다.

분산 시스템 분야에서 이 문제는 total order broadcast(전체 순서 브로드캐스트)나 atomic broadcast(원자적 브로드캐스트)로 알려져 있다. 전체 순서 브로드캐스트는 보통 노드 사이에 메시지를 교환하는 프로토콜로 기술된다. 비공식적으로는 두 가지 안전성 속성을 항상 만족해야 한다.

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

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

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

Zookeeper나 etcd 같은 합의 서비스는 전체 순서 브로드캐스트를 실제로 구현한다. 전체 순서 프로트캐스트와 합의 사이에는 강한 연관이 있다.

전체 순서 브로드캐스트는 여러 곳에서 사용할 수 있다.

• 데이터베이스 복제: 모든 메시지가 데이터베이스에 쓰기를 나타내고 모든 복제 서버가 같은 쓰기 연산을 같은 순서로 처리(전체 순서 브로드캐스트)하면 복제 서버들은 서로 일관성 있는 상태를 유지한다. 이 원리는 state machine replication(상태 기계 복제)라고 하며, 11장에서 다시 살펴본다.
• 직렬성 트랜잭션 구현: 모든 메시지가 스토어드 프로시저로 실행되는 결정적 트랜잭션을 나타낸다면, 그리고 모든 노드가 그 메시지들을 같은 순서로 처리(전체 순서 브로드캐스트)한다면 데이터베이스의 파티션과 복제본은 서로 일관적인 상태를 유지한다.
• 로그 생성: 로그에 추가하는 것처럼 메시지 전달을 수행하며, 모든 노드가 같은 메시지를 같은 순서로 전달(전체 순서 브로드캐스트)해야 하므로 모든 노드는 로그를 읽어서 순서가 동일한 메시지를 볼 수 있다.
• 펜싱 토큰을 제공하는 잠금 서비스 구현: 잠금을 획득하는 모든 요청은 메시지로 로그에 추가되고 모든 메시지들은 로그에 나타난 순서대로(전체 순서 브로드캐스트) 일련번호가 붙는다. 그러면 일련번호는 단조 증가하므로 펜싱 토큰의 역할을 할 수 있다. Zookeeper에서는 이 일련번호를 zxid라고 한다.

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

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

선형성 시스템에는 연산의 전체 순서가 있다. 이게 선형성이 전체 순서 브로드캐스트와 같다는 뜻일까? 완전히 똑같지는 않지만 이 둘 사이에는 밀접한 관계가 있다.

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

그러나 전체 순서 브로드캐스트 구현이 있다면 이를 기반으로 한 선형성 저장소를 만들 수 있다. 이전 사용자명 예제에서, 사용 가능한 모든 사용자명마다 원자적 compare-and-set 연산이 구현된 선형성 저장소를 가진다고 가정하고, 모든 레지스터는 초기에 null 값을 갖는다. 이후 사용자명 생성 요청마다 해당 레지스터의 compare-and-set 연산을 실행해 해당 값이 null인 경우 성공, 동시에 요청이 올 경우 compare-and-set 연산 중 하나만 성공한다. 다른 comapre-and-set 연산은 선형성 떄문에 널이 아닌 값을 보게 되기 때문이다.

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

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

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

이 절차를 sequential consistency(순차적 일관성), timeline consistency(타임라인 일관성)이라고 한다. 이 절차는 선형성 쓰기는 보장하지만 선형성 읽기는 보장하지 않는다. 로그로부터 비동기로 갱신되는 저장소를 읽으면 오래된 값이 읽힐 수 있다. 읽기를 선형적으로 만들려면 몇 가지 선택지가 있다.

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

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

전체 순서 브로드캐스트로부터 선형성 compare-and-set 연산을 구현할 수 있듯이, 반대로 선형성 저장소가 있을 때 이를 기반으로 전체 순서 브로드캐스트를 구현할 수도 있다.

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

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

램포트 타임스탬프와 달리 선형성 레지스터를 증가시켜서 얻은 숫자들은 “틈이 없는” 순열을 형성한다. 따라서 어떤 노드가 메시지 4를 전달하고 일련번호가 6인 메시지를 받았다면 메시지 6을 전달하기 전에 메시지 5를 기다려야 한다는 것을 알 수 있다. 램포트 타임스탬프는 그렇지 않다. 이것이 전체 순서 브로드캐스트와 타임스탬프 순서화의 핵심적인 차이이다.

원자적 increment-and-get 연산이 지원되는 선형성 정수를 만드는 것은 단순히 노드 하나에 변수 하나로 저장하면 끝이다. 문제는 그 노드와 네트워크 연결이 끊긴 상황 등의 장애가 날 때 그 값을 복구하는 데 있다. 이렇게 선형성 일련번호 생성기에 대해 충분히 고심하다 보면 필연적으로 합의 알고리즘에 도달하게 된다.

선형성 compare-and-set(또는 increment-and-get) 레지스터와 전체 순서 브로드캐스트는 둘 다 equivalent to consensus(합의와 동등하다)고 증명할 수 있다. 즉 이 문제 중 하나를 해결할 수 있으면 다른 문제 또한 해결할 수 있다는 것이다. 그렇다면 이제 합의 문제를 다뤄보자.

분산 트랜잭션과 합의

합의는 분산 컴퓨팅에서 가장 중요하고 근본적인 문제 중 하나다. 합의의 목적은 단지 여러 노드들이 뭔가에 동의하게 만드는 것이다. 겉으로는 간단해 보이지만 이 문제는 많은 선행 지식들과 과정을 필요로 한다. 앞 절에서 선행 지식들을 배웠으므로 이제 합의 문제를 살펴보자.

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

• 리더 선출: 단일 리더 복제를 사용하는 데이터베이스에서 모든 노드는 어떤 노드가 리더인지 동의해야 한다. 어떤 노드가 네트워크 결함 때문에 다른 노드와 통신할 수 없으면 리더십 지위를 놓고 경쟁할 수 있다. 이 경우 합의는 두 노드가 자신이 리더라고 생각하는 스플릿 브레인을 유발할 수 있는 잘못된 장애 복구를 피하는 데 중요하다. 리더가 두 대 있으면 둘 다 쓰기를 받아들여 데이터가 서로 달라져서 비이로간성과 데이터 손실로 이어진다.
• 원자적 커밋: 여러 노드나 파티션에 걸친 트랜잭션을 지원하는 데이터베이스에는 트랜잭션이 어떤 노드에서는 성공하고 어떤 노드에서는 실패할 수도 있는 문제가 있다. 트랜잭션 원자정을 유지하고 싶다면 모든 노드가 트랜잭션의 결과에 동의하게 만들어야 한다. 이런 합의 문제를 원자적 커밋 문제라고 한다.

이번 절에서는 먼저 원자적 커밋 문제를 더 자세히 살펴본다. 먼저 다양한 시스템에서 구현된 2PC(2단계 커밋) 알고리즘을 다룬다. 하지만 2PC 알고리즘은 좋은 알고리즘이 아니다. 따라서 이후 Zookeeper(Zab)과 etcd(Raft)에서 쓰이는 더 좋은 합의 알고리즘을 살펴본다.

원자적 커밋과 2단계 커밋(2PC)

트랜잭션 원자성의 목적은 여러 쓰기를 실행하는 도중 뭔가 잘못되는 경우에 간단한 시멘틱을 제공하기 위함이다. 트랜잭션의 결과는 커밋 성공(내용이 반영되어 지속성을 가짐)이나 어보트(내용이 롤백되어 폐기됨)다.

원자성은 실패한 트랜잭션이 절반만 완료/갱신된 상태로 데이터베이스를 어지럽히는 것을 막아준다. 이는 다중 객체 트랜잭션과 보조 색인을 유지하는 데이터베이스에서 특히 중요하다. 개별 보조 색인은 주 데이터와 분리된 자료이기에, 주 데이터와의 일관성을 유지해야 한다. 이를 원자성이 보장해준다.

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

단일 데이터베이스 노드에서 실행되는 트랜잭션에게 원자성은 저장소 엔진 수준에서 구현된다. 트랜잭션 커밋은 먼저 트랜잭션의 쓰기가 지속성 있게 한 후 디스크에 있는 로그에 커밋 레코드를 추가하는 방식으로 진행된다.

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

하지만 트랜잭션에 여러 노드가 관여하는 경우, 모든 노드에 커밋 요청을 보내고 각 노드에서 독립적으로 트랜잭션을 커밋하는 것으로는 충분하지 않다. 그렇게 하면 어떤 노드에서는 커밋이 성공하고 다른 노드에서는 실패해서 원자성 보장을 위반하기 쉽다.

• 어떤 노드들은 제약 조건 위반이나 충돌을 감지해서 어보트가 필요하게 되지만, 다른 노드들은 성공적으로 커밋될 수도 있다.
• 어떤 커밋 요청은 네트워크에서 손실되어 타임아웃 때문에 결국 어보트되지만 다른 커밋 요청은 전달될 수 있다.
• 어떤 노드는 커밋 레코드가 완전히 쓰여지기 전에 죽어서 복구할 때 롤백되지만 다른 노드는 성공적으로 커밋될 수 있다.

어떤 노드에서는 트랜잭션이 커밋되고 어떠 노드에서는 어보트된다면 노드들이 서로 일관성이 없어지만. 따라서 노드는 트랜잭션에 참여하는 다른 모든 노드도 커밋될 것이라고 확신할 때만 커밋이 돼야 한다.

트랜잭션 커밋은 되돌릴 수 없어야 한다. 왜냐하면 커밋된 데이터를 클라이언트가 읽어서 의존할 수도 있기 떄문이다. 이 원칙은 커밋 후 읽기 격리의 기반을 형성한다.

2단계 커밋 소개

2단계 커밋은 여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘이다. 일부 데이터베이스에서는 2PC가 내부적으로 사용되고 XA 트랜잭션의 형태나 SOAP 웹 서비스용 WS-AtomicTransaction을 통해 애플리케이션에서도 사용할 수 있다.

2단계 커밋(2PC)의 성공적인 실행

위의 그림은 2PC의 기본 흐름이다. 단일 노드 트랜잭션에서처럼 하나의 커밋 요청을 하는 대신 2PC의 커밋/어보트 과정은 두 단계로 나뉜다(그래서 2PC라는 이름이 붙었다).

2PC는 단일 노드 트랜잭션에서는 보통 존재하지 않는 새로운 컴포넌트인 coordinator(코디네이터, 트랜잭션 관리자라고도 함)를 사용한다. 코디네티어는 라이브러리 형태나 프로세스 또는 서비스로 구현될 수 있다. 예로 Narayana, JOTM, BTM, MSDTC가 있다.

2CP 트랜잭션에서 트랜잭션 참여 데이터베이스 노드들을 트랜잭션의 participant(참가자)라고 부르며, 애플리케이션이 커밋할 준비가 되면 코디네이터가 1단계를 시작한다. 먼저 각 노드에 준비 요청을 보내서 커밋할 수 있는지 물어본 후, 참여자들의 응답을 추적한다.

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

약속에 관한 시스템

이 짧은 설명으로는 왜 여러 노드에 걸친 1단계 커밋은 원자성을 보장하지 못하지만 2단계 커밋은 보장하는지 명확하게 설명해주지 않는다. 무엇이 2PC를 다르게 만들어줄까?

왜 동작하는지 이해하려면 그 과정을 더 자세히 분해해 봐야 한다.

1. 애플리케이션은 분산 트랜잭션을 시작하기를 원할 때 코디네이터에게 트랜잭션 ID를 요청한다. 이 트랜잭션 ID는 전역적으로 유일하다.
2. 애플리케이션은 각 참여자에서 단일 노드 트랜잭션을 시작하고 단일 노드 트랜잭션에 전역적으로 유일한 트랜잭션 ID를 붙인다. 모든 읽기와 쓰기는 이런 단일 노드 트랜잭션 중 하나에서 실행된다. 이 단계에서 뭔가 잘못되면(예를 들어 노드가 죽거나 요청이 타임아웃되면) 코디네이터나 참여자 중 누군가가 어보트할 수 있다.
3. 애플리케이션이 커밋할 준비가 되면 코디네이터는 모든 참여자에게 전역 트랜잭션 ID로 태깅된 준비 요청을 보낸다. 이런 요청 중 실패하거나 타임아웃된 것이 있으면 코디네이터는 모든 참여자에게 그 트랜잭션 ID로 어보트 요청을 보낸다.
4. 참여자가 준비 요청을 받으면 모든 상황에서 분명히 트랜잭션을 커밋할 수 있는지 확인한다. 여기에는 모든 트랜잭션 데이터를 디스크에 쓰는 것과 충돌이나 제약 조건 위반을 확인하는 것이 포함된다. 코디네이터에게 “네”라고 응답함으로써 노드는 요청이 있으면 트랝개션을 오류 없이 커밋할 것이라고 약속한다. 달리 말하면 참여자들은 트랜잭션을 어보트할 권리를 포기하지만 실제로 커밋하지는 않는다.
5. 코디네이터가 모든 준비 요청에 대해 응답을 받았을 때 트랜잭션을 커밋할 것인지 어보트할 것인지 최종 결정을 한다(모든 참여자가 “네”에 투표했을 때만 커밋한다). 코디네이터는 추후 죽는 경우에 어떻게 결정했는지 알 수 있도록 그 결정을 디스크에 있는 트랜잭션 로그에 기록해야 한다. 이를 커밋 포인트라고 한다.
6. 코디네이터의 결정이 디스크에 쓰여지면 모든 참여자에게 커밋이나 어보트 요청이 전송된다. 이 요청이 실패하거나 타임아웃이 되면 코디네이터는 성공할 때까지 영원히 재시도해야 한다. 그 결정이 커밋이였다면 커밋될 때까지 재시도해야 한다. 도중에 한 참여자가 죽었다면 트랜잭션은 그 참여자가 복구될 때 커밋된다. 참여자가 “네”라고 투표했으므로 복구될 때 커밋을 거부할 수 없다.

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

코디네이터 장애

2PC 도중에 참여자 중 하나나 네트워크에 장애가 나면 무슨 일이 생기는지 설명해싿. 준비 요청 중 어떤 게 실패하거나 타임아웃이 되면 코디네이터는 트랜잭션을 어보트한다. 커밋이나 어보트 요청이 실패하면 코디네이터는 무한히 재시도한다.

하지만 코디네이터가 죽으면 어떻게 될까? 코디네이터가 준비 요청을 보내기 전에 장애가 나면 참여자는 안전하게 트랜잭션을 어보트할 수 있다. 그러나 참여자가 준비 요청을 받고 “네”에 투표했다면 더 이상 어보트할 수 없다. 코디네이터에서 커밋/어보트 회신을 받을 때까지 기다려야 하며, 이 떄 코디네이터에 장애가 발생해도 기다려야 한다. 이 상태에 있는 참여자의 트랜잭션을 in doubt(의심스럽다) 또는 uncertain(불확실하다)고 한다.

참여자들이 “네”라고 투표한 후 코디네이터가 죽는다. 데이터베이스 1은 커밋할지 어보트할지 알지 못한다.

위 그림은 이 상황을 표현한 그림이다. 이 예에서 코디네이터는 실제로 커밋하기를 결정했고 데이터베이스 2는 커밋 요청을 받았지만, 데이터베이스 1은 코디네이터가 죽는 바람에 요청을 받지 못했다. 이 상황에서 데이터베이스 1은 아무런 행동도 취하지 못한다(어보트하면 데이터베이스 2와 일관성이 깨지고, 커밋하는 것도 다른 참여자가 어보트했을지도 모르므로 불확실하다).

코디네이터에게 듣지 않고 참여자는 커밋할지 어보트할지 알 방법이 없다. 2PC가 완료할 수 있는 유일한 방법은 코디네이터가 복구되기를 기다리는 것뿐이다. 이것이 코디네이터가 참여자들에게 커밋이나 어보트 요청을 보내기 전에 디스크에 있는 트랜잭션 로그에 자신의 커밋이나 어보트 결정을 써야 하는 이유다. 코디네이터가 복구될 때 트랜잭션 로그를 읽어서 모든 의심스러운 트랜잭션들의 상태를 결정한다. 코디네이터의 로그에 커밋 레코드가 없는 트랜잭션들은 어보트되며, 따라서 2PC의 커밋 포인트는 단일 노드 원자적 커밋 수준으로 내려온다.

3단계 커밋

2단계 커밋은 2PC가 코디네이터가 복구하기를 기다려야 하기 때문에 블로킹 원자적 커밋 프로토콜이라고 불린다. 2PC의 대안으로 3PC(3단계 커밋)이라는 알고리즘이 제안되었는데, 지연과 응답 시간에 제한이 있는 노드를 가정한 이론적인 알고리즘이기 때문에, 기약 없는 네트워크 지연과 프로세스 중단이 있는 대부분의 실용적 시스템에서 3PC는 원자성을 보장하지 못한다.

일반적으로 논블로킹 원자적 커밋은 perfect failure detector(완벽한 장애 감지기), 즉 노드가 죽었는지 아닌지 구별할 수 있는 신뢰성 있는 메커니즘이 필요하다. 이는 기약 없는 지연이 있는 네트워크에서 불가능하기 때문에 코디네이터 장애가 있음에도 불구하고 2PC가 현실에서는 쓰이고 있다.

현실의 분산 트랜잭션

분산 트랜잭션, 특히 2단계 커밋으로 구현된 분산 트랜잭션은 평판이 엇갈린다. 또한 여러 클라우드 서비스들은 분산 트랜잭션이 낳는 운영상 문제 때문에 분산 트랜잭션을 구현하지 않는 선택을 한다.

어떤 분산 트랜잭션 구현은 무거운 성능 손해를 수반한다. 예를 들어 MySQL의 분산 트랜잭션은 단일 노드 트랜잭션보다 10배 이상 느리다고 보고된다. 이는 2단계 커밋의 내장된 성능 비용이 대부분이 장애 복구를 위한 부가적인 디스크 강제 쓰기와 네트워크 왕복 시간 때문이다,

그러나 분산 트랜잭션을 완전히 일축하기보다는 좀 더 자세히 조사해봐야 한다. 이로부터 배울 수 있는 중요한 교훈이 있기 떄문이다. 먼저 분산 트랜잭션의 의미를 명확히 해야한다. 두 가지의 분산 트랜잭션이 혼용되기 때문이다.

• 데이터베이스 내부 분산 트랜잭션: 어떤 분산 데이터베이스(표준 설정에서 복제/파티셔닝을 하는 데이터베이스)는 데이터베이스 노드 사이에 내부 트랜잭션을 지원한다. 예를 들어 VoltDB와 MySQL 클러스터의 NDB 저장소 엔진은 이런 내부 트랜잭션을 지원한다. 이 경우 트랜잭션에 참여하는 모든 노드는 동일한 데이터베이스 소프트웨어를 실행한다.
• 이중 분산 트랜잭션: heterogeneous(이중) 트랜잭션에서 참여자들은 둘 혹은 그 이상의 다른 기술이다. 이를테면 두 가지 서로 다른 벤더의 데이터베이스일 수도, 심지어 메시지 브로커처럼 비데이터베이스 시스템일 수도 있다. 이런 시스템에 걸친 분산 트랜잭션은 시스템의 내부가 완전히 다르더라도 원자적 커밋을 보장해야 한다.

데이터베이스 내부 트랜잭션은 다른 시스템과 호환될 필요가 없으므로 아무 프로토콜이나 쓸 수 있고 최적화가 가능하기 때문에 매우 잘 동작하지만, 이종 기술에 걸친 트랜잭션은 기술적 난이도가 높다.

정확히 한 번 메시지 처리

이종 분산 트랜잭션은 다양한 시스템들이 강력한 방법으로 통합될 수 있게 한다. 예를 들어 메시지 큐에서 나온 메시지는 그 메시지를 처리하는 데이터베이스 트랜잭션이 커밋에 성공했을 때만 처리된 것으로 확인받을 수 있다. 메시지 확인과 데이터베이스 쓰기를 단일 트랜잭션에서 원자적으로 커밋함으로써 이를 구현할 수 있다. 분산 트랜잭션이 지원되면 메시지 브로커와 데이터베이스가 서로 다른 장비에서 실행되는 두 가지 무관한 기술이더라도 이것이 가능하다.

메시지 전달이나 데이터베이스 트랜잭션 중 하나가 실패하면 둘 다 어보트되고 메시지 브로커는 재시도할 수 있다. 메시지와 그 부수 효과(DB 트랜잭션)을 원자적으로 커밋함으로써 메시지가 effectively(결과적으로) exactly once(정확히 한 번) 처리되도록 보장할 수 있다. 그렇지만 이런 분산 트랜잭션은 트랜잭션의 영향을 받는 모든 시스템이 동일한 원자적 커밋 프로토콜을 사용할 수 있을 때만 가능하다.

먼저 이런 이종 분산 트랜잭션을 가능케하는 원자적 커밋 프로토콜을 살펴본다.

XA 트랜잭션

X/Open XA(eXtended Architecture)는 이종 기술에 걸친 2단계 커밋을 구현하는 표준이다. XA는 여러 전통적인 관계형 데이터베이스와 메시지 브로커에서 지원된다.

XA는 네트워크 프로토콜이 아닌 트랜잭션 코디네이터와 연결되는 인터페이스를 제공하는 C API일 뿐이다. 다른 언어들은 이 API 바인딩을 가지고 있다. 예를 들어 Java EE에서 XA는 JTA를 사용해 구현되면 JTA는 다시 JDBC(DB)와 JMS(MQ)에서 지원된다.

XA는 애플리케이션이 네트워크 드라이버나 클라이언트 라이브러리를 사용해 참여자 데이터베이스나 메시징 서비스와 통신한다고 가정한다. 연산이 분산 트랜잭션의 일부가 된다면 XA API를 호출하며, 이 때 드라이버가 데이터베이스와 코디네이터에게 필요한 정보를 보낸다.

트랜잭션 코디네이터는 XA API를 구현하며, 단순한 라이브러리 형태로 참여자 추적/준비 요청/응답 수집/커밋/어보트 결정 등을 수행한다.

만약 애플리케이션 프로세스가 죽으면 라이브러리로 존재하던 코디네이터도 죽을 수 있으며, 이는 참여자들을 의심스러운 상태로 빠지게 만든다. 이후 애플리케이션이 복구된다면 로그를 통해 커밋/어보트 결과 복구 후 재요청을 수행한다.

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

트랜잭션이 의심스러운 상태에 빠지는 것에 집중하는 이유는, 데이터베이스 트랜잭션이 보통 로우에 락(더티 쓰기 방지를 위한 exclusive lock, 직렬성을 위한 shared lock)을 걸기 때문이다.

데이터베이스는 트랜잭션이 커밋하거나 어보트할 때 이런 잠금을 해제할 수 없다. 그러므로 2단계 커밋을 사용할 때 트랜잭션이 의심스러운 상태에 빠지면 복구될 때까지 잠금을 잡고 있어야 한다. 이렇게 잠금이 유지되면 다른 어떤 트랜잭션도 로우 읽기/쓰기가 불가능해지면, 이는 트랜잭션이 해소될 때까지 애플리케이션의 많은 부분을 사용할 수 없게 되는 원인이 된다.

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

현실에서 코디네이터에 장애가 발생하면 orphaned(고아가 된) 의심스러운 트랜잭션들이 생길 수 있다. 이런 트랜잭션들은 잠금을 유지하고 다른 트랜잭션을 차단하면서 데이터베이스에 영원히 남는다.

2PC의 올바른 구현은 재시작을 하더라도 의심스러운 트랜잭션의 잠금을 유지하는 것이기 때문에, 이 상태를 해결할 수 있는 방법은 관리자가 수동으로 트랜잭션을 커밋/롤백할지 결정하는 것이다. 이런 현상은 심각한 서비스 중단이 있는 도중에 발생하며, 스트레스 및 시간 압박의 상태에서 해결을 해야할 수 있다.

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

분산 트랜잭션의 제약

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

• 코디네이터가 복제되지 않고 단일 장비에서만 실행되면 전체 시스템의 SPOF가 된다. 하지만 여러 코디네이터 구현은 기본적으로 고가용성을 제공하지 않거나 가장 기초적인 복제만 지원한다.
• 여러 서버 사이드 애플리케이션은 모든 영속적인 상태를 데이터베이스에 저장하고 무상태 서버로 존재한다. 이는 서버의 확장성에 이점이 있다. 하지만 코디네이터가 애플리케이션 서버의 일부가 되면 코디네이터 로그를 유지해야 하므로, 애플리케이션이 더 이상 무상태가 아니게 된다.
• XA는 광범위한 데이터 시스템과 호환돼야 하므로 최소 공통 분모가 될 필요가 있다. 예를 들어 여러 시스템에 걸친 교착 상태를 감지할 수 없고, SSI와 함께 동작하지 않는다. SSI를 지원하려면 여러 시스템에 걸친 충돌을 식별할 프로토콜이 필요하기 때문이다.
• (XA가 아닌) 데이터베이스 내부 분산 트랜잭션은 XA처럼 제한이 크지 않다. 예를 들어 분산 버전 SSI를 쓸 수 있다. 그러나 2PC가 성공적으로 트랜잭션을 커밋하려면 모든 참여자가 응답해야 한다는 문제가 남는다. 결과적으로 시스템의 어떤 부분이라도 고장 나면 트랜잭션도 실패하며, 이는 분산 트랜잭션이 장애를 증폭시키는 경향을 가져온다. 이는 내결함성을 지닌 시스템을 구축하려면 목적에 어긋난다.

그렇다면 이러한 제약에서 벗어나 여러 시스템 서로 일관성을 유지하게 만들 수 있는 방법은 없을까? 다행히 대안적인 방법이 존재한다. 이는 11장과 12장에서 살펴본다.

내결함성을 지닌 합의

비공식적으로 합의는 여러 노드가 어떤 것에 동의해야 한다는 뜻이다. 예를 들어 같은 좌석 예약 등, 서로 공존할 수 없는 연산 중 어떤 것이 승자가 돼야 하는지 결정하는 데 합의 알고리즘을 사용할 수 있다.

합의 문제는 보통 다음과 같이 형식화된다. 하나 또는 그 이상의 노드들이 값을 제안할 수 있으며, 합의 알고리즘이 그 값 중 하나를 결정한다. 좌석 예약을 예로 든다면 각 노드는 좌석을 배정할 고객 ID를 제안하고, 결정은 ID 중 하나를 고르는 것이다.

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

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

균일한 동의와 무결성 속성은 합의의 핵심 아이디어를 정의한다. 모두 같은 결과로 결정하며 한 번 결정하면 마음을 바꿀 수 없다. 유효성 속성은 뻔한 해결책을 배제하기 위해 존재한다. 예를 들어 null로 항상 제안하는 알고리즘은 유효성 속성을 만족하지 않는다.

내결함성이 상관없다면 처음 세 개의 속성을 만족시키기 쉽다. 한 노드를 “독재자”로 하드코딩한 후 해당 노드가 결정을 내리게 하면 되는 것이다. 하지만 해당 노드가 장애가 난다면 결정을 내릴 수 없는 상황이 발생한다. 종료 속성은 내결함성의 아이디어를 형식화한다. 장애가 발생하더라도 노드들은 어떤 값을 결정해야 한다는 것이다.

합의 시스템 모델은 노드가 “죽으면” 다시 돌아오지 않는다고 가정한다. 따라서 노드 복구를 기다리는 알고리즘은 어떤 것이라도 종료 속성을 만족할 수 없다. 특히 2PC는 종료에 대한 요구사항을 만족하지 않는다. 물론 모든 노드가 죽어서 실행할 수 없는 상태에서는 의미가 없다. 따라서 어떤 합의 알고리즘이라도 종료를 보장하려면 최소한 노드의 과반수가 올바르게 동작해야 한다. 과반수는 안전하게 정족수를 형성할 수 있다.

따라서 종료 속성은 죽은 노드의 대수가 절반 미만이라는 가정에 종속적이다. 그러나 대부분의 합의 구현은 과반수에 장애가 나거나 심각한 네트워크 문제가 있더라도 안정성 속성을 항상 만족한다. 이는 즉 대규모 중단이 발생하면 시스템은 요청 처리는 못하더라도 유효하지 않은 결정을 내려서 합의 시스템을 오염시키지는 않는다는 뜻이다.

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

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

내결함성을 지닌 합의 알고리즘 중 가장 널리 알려진 것은 Viewstamped Replication, VSR(뷰스탬프 복제), Paxos(팍소스), Raft(라프트), Zab(잽)이다. 이들 알고리즘 사이에는 상당 유사성이 있지만 똑같지는 않다. 합의 시스템 구현은 어렵기 때문에 이러한 알고리즘들이 공통으로 가지고 있는 고수준의 아이디어를 아는 것으로 충분하다.

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

전체 순서 브로드캐스트를 하려면 모든 노드에게 메시지가 정확히 한 번, 같은 순서로 전달돼야 한다. 이는 합의를 몇 회 하는 것과 동일하다고 볼 수 있다. 각 회마다 노드들은 다음에 보내기 원하는 메시지를 제안하고 전체 순서 상에서 전달될 다음 메시지를 결정한다. 그래서 전체 순서 브로드캐스트는 합의를 여러 번 반복하는 것과 동일하다(각 합의 결정이 하나의 메시지 전달에 해당한다).

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

VSR, Raft, Zab은 전체 순서 브로드캐스트를 직접 구현한다. 그렇게 하는 게 한 번에 한 값을 처리하는 합의를 여러 번 하는 것보다 효율적이기 때문이다. Paxos의 최적화 구현은 Multi-Paxos(다중 팍소스)라고 한다.

단일 리더 복제와 합의

사실 5장에서 모든 쓰기를 리더에게 전달하고 쓰기를 같은 순서로 팔로워에 적용해서 복제본이 최신 상태를 유지하게 하는 단일 리더 복제가 본질적으로 전체 순서 브로드캐스트가 아닌가? 왜 5장에서는 합의에 대해 걱정할 필요가 없었을까?

그 답은 리더를 어떻게 선택하느냐에 있다. 사람이 수동으로 선택해서 설정한다면 본질적으로 독재자 방식의 “합의 알고리즘”을 사용하는 것이고, 리더 노드가 죽으면 수동으로 다른 노드가 리더로 설정할 떄까지 쓰기를 할 수 없게 된다. 이런 시스템은 현실에서 잘 동작하지만 사람의 개입이 필요하므로 합의의 종료 속성을 만족하지 않는다.

어떤 데이터베이스는 기존 리더에 장애가 나면 팔로워 하나를 새 리더로 승격시켜 자동 리더 선출과 장애 복구를 수행한다. 이렇게 하면 내결함성을지닌 전체 순서 브로드캐스트에 가까워지고 합의를 해결하는 데도 가까워진다.

하지만 이 방식에는 문제가 있다. 스플릿 브레인 문제를 회피하기 위해 모든 노드들이 누가 리더인지 동의해야 한다. 하지만 리더를 선출하려면 합의가 필요하고, 여기서 합의 알고리즘들이 실제로는 전체 순서 브로드캐스트 알고리즘이면 "전체 순서 브로드캐스트 = 단일 리더 복제 = 리더 필요”라는 리더 선출을 위해 리더가 필요한 재귀적인 상황이 발생하게 된다.

즉 합의를 해결하려면 합의를 해결해야 한다. 어떻게 이 난제에서 벗어날 수 있을까?

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

지금까지 설명한 합의 프로토콜은 모두 내부적으로 어떤 형태로든 리더를 사용하지만 리더가 유일하다고 보장하지는 않는다. 대신 그들은 더 약한 보장을 할 수 있다. 이 프로토콜들은 epoch number(에포크 번호, Paxos에서는 ballot number(투표 번호), Viestamp Replication에서는 view number(뷰 번호), Raft에서는 term number(텀 번호)라고 한다)를 정의하고 각 에포크 내에서는 리더가 유일하다고 보장한다.

현재 리더가 죽었다고 판단되면 새 리더를 선출하기 위해 노드 사이에서 투표가 시작되고, 이 때 선출은 에포크 번호를 단조 증가시킨다. 따라서 다른 에포크에 있는 두 가지 다른 리더 사이의 충돌이 난다면 에포크 번호가 더 높은 리더가 이긴다.

리더가 뭔가를 결정하도록 허용하기 전에 더 높은 에포크 번호를 가진 리더가 없는지 확인해야 한다. 따라서 리더 노드는 다른 노드들의 정족수로부터 투표를 받아, 본인이 내리려고 하는 모든 결정의 제안 값을 다른 노드에게 보내서 노드의 정족수가 그 제안을 찬성하기를 기다려야 한다. 이 떄 노드는 에포크 번호가 더 높은 다른 리더를 알지 못할 때만 제안에 찬성하는 투표를 한다.

따라서 두 번의 투표가 있다. 한 번은 리더를 선출하기 위해, 두 번째는 리더의 제안에 투표하기 위해서다. 이 때 두 번의 투표를 하는 정족수가 겹쳐야 한다(노드 중 최소 하나는 리더 선출과 제안 투표 모두를 수행했어야 한다). 따라서 제안에 대한 투표가 찬성되면, 현재 리더는 본인보다 높은 에포크 번호를 가진 리더가 없다는 것을 확신할 수 있고, 안전하게 제안된 값을 결정할 수 있다.

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

합의의 제약

합의 알고리즘은 분산 시스템의 커다란 발전이다. 그들은 그 밖의 모든 것이 불확실한 시스템에 구체적인 안정성 속성(동의, 무결성, 유효성)을 가져오고, 그럼에도 내결함성을 유지한다(노드의 과반수가 동작하고 통신할 수 있는 한 진행할 수 있다). 그들은 전체 순서 브로드캐스트를 제공하고 따라서 내결함성 있는 방식으로 선형성 원자적 연산을 구현할 수 있다.

그럼에도 합의 알고리즘이 모든 곳에 쓰이지는 않는다. 이득에는 대가가 따르기 때문이다.

• 제안이 결정되기 전에 노드가 제안에 투표하는 과정은 일종의 동기식 복제다. 하지만 데이터베이스들은 종종 비동기 복제를 사용하도록 설정된다. 이런 설정에서 커밋된 데이터는 장애 복구 시 잠재적으로 손실될 수 있으나, 많은 사람들이 더 나은 성능을 위해 이 위험을 받아들이기로 선택한다.
• 합의 시스템은 항상 엄격한 과반수가 동작하기를 요구한다. 따라서 최소로 유지되어야 하는 노드의 대수가 존재한다. 이 때 노드 간 연결이 끊기면 네트워크의 과반수 부분만 진행할 수 있다.
• 대부분의 합의 알고리즘은 투표에 참여하는 노드 집합이 고정돼 있다고 가정하며 이는 노드 추가/제거가 불가능하다는 뜻이다. 합의 알고리즘의 dynamic membership(동적 멤버십) 확장은 클러스터에 있는 노드 집합이 시간이 지남에 따라 바뀌는 것을 허용하지만 이들은 정적 멤버십 알고리즘보다 훨씬 더 이해하기 어렵다.
• 합의 시스템은 장애 노드를 감지하기 위해 일반적으로 타임아웃에 의존한다. 따라서 네트워크 지연의 변동이 심한 환경, 일시적인 네트워크 문제 떄문에 불필요한 리더 재선출 과정이 발생할 수 있다. 만약 네트워크가 끊임없이 불안정하다면 리더 재선출 과정 때문에 시스템이 사실상 전혀 진행하지 못할 수도 있다. 이처럼 합의 알고리즘은 네트워크의 문제에 특히 민감하다. Raft 같은 경우 불쾌한 에지 케이스가 있다고도 한다.

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

Zookeeper나 etcd 같은 프로젝트 종종 “분산 키-값 저장소”나 “코디네이션과 설정 서비스”라고 설명된다. 이런 서비스들의 API는 데이터베이스의 API와 매우 비슷해 보인다. 하지만 이들이 데이터베이스라면 왜 합의 알고리즘을 구현하는 데 모든 노력을 다하는 것일까? 무엇이 이것들을 다른 종류의 데이터베이스와 다르게 만들까?

이를 이해하기 위해서는 Zookeeper같은 서비스가 어떻게 사용되는지 살펴봐야 한다. 사실 Zookeeper는 애플리케이션 개발자가 직접 사용할 일은 없고, 다른 프로젝트들이 Zookeeper에 의존하며 동작하는 방식으로 사용된다. 이를테면 HBase, Haddop YARN, Openstack Nova, Kafka는 모두 배후에서 실행되는 Zookeeper에 의존한다. 이 프로젝트들이 주키퍼에 얻는 것은 무엇일까?

Zookeeper와 etcd는 완전히 메모리 안에 들어올 수 있는 작은 양의 데이터를 보관하도록 설계되었다(여전히 지속성을 위해 디스크에 쓰기는 하지만). 이 소량의 데이터는 내결함성을 지닌 전체 순서 브로드캐스트 알고리즘을 사용해 모든 노드에 걸쳐 복제된다. 앞서 설명했듯이 전체 순서 브로드캐스트는 데이터베이스 복제에 딱 필요한 것이다. 개별 메시지가 데이터베이스에 쓰기를 나타낸다면 같은 쓰기를 같은 순서로 적용함으로써 복제본들이 서로 일관성을 유지할 수 있다.

Zookeeper는 Google의 Chubby 잠금 서비스를 모델로 삼아 전체 순서 브로드캐스트 뿐만 아니라 분산 시스템을 구축할 때 특히 유용한 것으로 알려진 다른 흥미로운 기능 집합도 구현한다.

• 선형성 원자적 연산, 분산 잠금: 원자적 compare-and-set 연산을 사용해 잠금을 구현할 수 있다. 여러 노드가 동시에 같은 연산을 수행하려고 하면 그것들 중 하나만 성공한다. 합의 프로토콜은 노드에 장애가 나거나 어느 시점에 네트워크가 끊기더라도 그 연산이 원자적이고 선형적일 것을 보장한다. 분산 잠금은 보통 클라이언트에 장애가 난 경우 결국에는 해제되도록 만료 시간이 있는 lease(임차권)으로 구현된다.
• 연산의 전체 순서화: 어떤 자원이 잠금이나 임차권으로 보호될 때는 프로세스가 중단되는 경우 클라이언트들이 서로 충돌하는 것을 막기 위해 펜싱 토큰이 필요하다. 펜싱 토큰은 잠금을 획득할 때마다 단조 증가하는 어떤 숫자다. Zookeeper는 모든 연산에 전체 순서를 정하고 각 연산에 단조 증가하는 트랜잭션 ID(zxid)와 버전 번호(cversion)을 할당해서 이를 제공한다.
• 장애 감지: 클라이언트는 Zookeeper 서버에 수명이 긴 세션을 유지하고 클라이언트와 서버는 주기적으로 heartbeat(하트비트)를 교환해서 다른 쪽이 여전히 살아 있는지 확인한다. 연결이 일시적으로 끊기거나 Zookeeper 노드에 장애가 나더라도 세션은 살아 있다. 그러나 세션 타임아웃보다 긴 기간 동안 하트비트가 멈추면 Zookeeper는 세션이 죽었다고 선언한다. 세션에서 획득한 잠금은 세션이 타임아웃 됐을 때 자동으로 해제되도록 설정할 수 있다(Zookeeper에서는 이를 ephemeral node(단명 노드)라고 한다).
• 변경 알림: 클라이언트는 다른 클라이언트가 생성한 잠금과 값을 읽을 수 있을 뿐만 아니라 거기에 변경에 있는지 감시할 수도 있다. 따라서 클라이언트는 다른 클라이언트가 언제 클러스터에 합류했는지 혹은 또다른 클라이언트에 장애가 났는지 알아챌 수 있다. 알림을 구독함으로써 클라이언트는 변경을 발견하기 위해 주기적으로 폴링해야 하는 필요를 피할 수 있다.

이 기능 중에서 오직 선형성 원자적 연산만 실제로 합의가 필요하다. 그러나 Zookeeper 같은 시스템을 분산 코디네이션에 매우 유용하게 만들어주는 것은 이 기능들의 조합이다.

작업을 노드에 할당하기

Zookeeper/Chubby 모델이 잘 동작하는 여러 예가 있다.

• 여러 개의 프로세스가 있고 그중 하나가 리더나 주 구성요소로 선택돼야 할 때: 리더에 장애가 나면 다른 노드 중 하나가 넘겨받아야 한다. 이는 당연히 단일 리더 데이터베이스에 유용하지만 작업 스케줄러나 비슷한 상태 저장 시스템에도 유용하다.
• 파티셔닝된 자원(데이터베이스, 메시지 스트림, 파일 저장소, 분산 액터(actor) 시스템 등)이 있고 어떤 파티션을 어느 노드에 할당해야 할지 결정해야 할 때: 새 노드들이 클러스터에 합류하면서 부하의 재균형화를 위해 어떤 파티션들은 기존 노드에서 새로운 노드로 이동돼야 한다. 노드가 제거되거나 장애가 나면 다른 노드들이 장애가 난 노드의 작업을 넘겨받아야 한다.

이런 종류의 작업은 Zookeeper에서 원자적 연산, 단명 노드, 알림을 신중하게 사용하면 잘 해낼 수 있다. 올바르게 사용한다면 사람의 개입 없이도 애플리케이션이 결함으로부터 자동으로 복구될 수 있게도 한다. 하지만 이는 쉬운 작업이 아니다(API를 더욱 추상화하여 고수준 도구를 제공하는 Apache Curator가 있음에도 불구하고. 그래도 합의 알고리즘을 밑바닥부터 구현하는 것보다는 낫다).

애플리케이션은 처음에는 단일 노드에서만 실행될지 모르지만 결국에는 수천 대의 노드로 늘어날 수도 있다. 이 때 매우 많아진 노드에서 과반수 투표를 수행하려고 하는 것은 지독하게 비효율적이다. 대신 Zookeeper는 3~5대의 고정된 수의 노드에서 실행되고 이 노드들 사이에서 과반수 투표를 수행하면서 많아질 수 있는 클라이언트를 지원한다. 따라서 Zookeeper는 노드들을 코디네이트하는 작업(합의, 연산 순서화, 장애 감지)의 일부를 외부 서비스에 “위탁”하는 방법을 제공한다.

보통 Zookeeper로 관리되는 데이터의 종류는 매우 느리게 변한다. “10.1.1.23에서 실행되는 노드가 파티션 7의 리더다”처럼 몇 분이나 몇 시간 단위로 변경될 수 있는 정보를 표현한다. 매초 수천 번 혹은 수밴만 번까지 변경될지 모르는 애플리케이션 런타임 상태 저장용으로 의도된 게 아니다(애플리케이션 상태 복제를 위해서는 Apache BookKeeper를 사용할 수 있다).

서비스 찾기

Zookeeper, etcd, Consul은 service discovery(서비스 찾기), 즉 특정 서비스에 연결하려면 어떤 IP 주소로 접속해야 하는지 알아내는 용도로도 자주 사용된다. 가상 장비가 지속적으로 들어왔다 나갔다 하는 게 흔한 클라우드 데이터센터 환경에서 서비스의 IP 주소를 사전에 알지 못할 때가 자주 있다. 대신 서비스가 시작할 때 자신의 네트워크 종점을 서비스 등록소에 등록하도록 설정할 수 있다. 그러면 다른 서비스들은 서비스 등록소에서 서비스를 찾을 수 있다.

그러나 서비스 찾기가 실제로 합의가 필요한지는 분명해 보이지 않는다. DNS는 서비스 이름으로 IP 주소를 찾는 전통적인 방법이고, 좋은 성능과 가용성을 달성하기 위해 다층 캐시를 사용한다. DNS에서 읽는 것은 선형적이지 않고, DNS 질의의 결과가 조금 뒤처지더라도 보통 문제로 생각되지는 않는다. DNS는 신뢰성 있게 사용 가능하고 네트워크 끊김에 견고하다는 게 더 중요하다.

서비스 찾기는 합의가 필요 없지만 리더 선출은 합의가 필요하다. 따라서 합의 시스템이 누가 리더인지 이미 안다면 다른 서비스들이 리더가 누구인지 찾는 데 그 정보를 사용하는 것도 타당하다. 이런 목적으로 어떤 합의 시스템은 읽기 전용 캐시 복제 서버를 지원한다. 이 복제 서버는 합의 알고리즘의 모든 결정에 관한 로그를 비동기로 받지만 능동적으로 투표에 참여하지는 많는다. 그러므로 그들은 선형적일 필요가 없는 읽기 요청을 서비스할 수 있다.

멤버십 서비스

Zookeeper와 유사 프로젝트들은 오랜 membership service(멤버십 서비스) 연구 역사의 일부로 볼 수 있다. 그 역사는 1980년대로 거슬러 올라가며 항공 교통 관제 같은 고신뢰성 시스템을 구축하는 데 중요한 역할을 했다.

멤버십 서비스는 클러스터에서 어떤 노드가 현재 활성화된 살아 있는 멤버인지 결정한다. 기약 없는 네트워크 지연 때문에 다른 노드에 장애가 생겼는지 신뢰성 있게 감지하는 것은 불가능하다. 그러나 장애 감지를 합의와 연결하면 노드들은 어떤 노드가 살아있는/죽어있는 것으로 여겨야 하는지에 동의할 수 있다.

여전히 노드가 실제로는 살아 있지만 합의에 의해 죽은 것으로 잘못 선언될 가능성이 있다. 그럼에도 합의는 시스템에서 어떤 노드가 현재 멤버십을 구성하는지 동의하는 데 매우 유용하다.

정리

이번 장에서는 일관성과 합의에 관한 주제들을 여러 다양한 각도에서 살펴봤다.

먼저 인기 있는 일관성 모델인 선형성을 깊게 알아봤다. 그 목적은 복제된 데이터가 오직 하나의 복사본만 있는 것처럼 보이게 하고 데이터에 대한 모든 연산을 원자적으로 만드는 것이다. 선형성은 이해하기 쉬우므로(데이터베이스가 단일 스레드 프로그램의 변수처럼 동작하게 만들어준다) 매력적이지만 느리다는 단점이 있다. 네트워크 지연이 큰 환경에서 특히 그렇다.

시스템에서 발생한 이벤트에 순서를 부과하는 인과성(원인과 결과를 기반으로 어떤 것이 어떤 것보다 먼저 실행됐는지)도 살펴봤다. 모든 연산을 하나의 전체 순서가 정해진 타임라인에 넣는 선형성과 달리 인과성은 더 약한 일관성 모델을 제공한다. 어떤 연산들은 동시에 실행될 수도 있어서 버전 기록은 branching(가지치기)와 merging(합치기)가 있는 타임라인과 같다. 인과적 일관성은 선형성의 코디네이션 오버헤드가 없고 네트워크 문제에 훨씬 덜 민감하다.

그러나 인과적 순서를 담아내더라도(예를 들어 램포트 타임스탬프를 써서) 어떤 것들은 이 방법으로 구현할 수 없다는 것을 알았다(예를 들어 사용자명을 유일하게 만들 때 동일한 사용자명으로 동시에 등록하지 못하게 거부하는 것을 보장하는 시스템). 한 노드가 등록을 받아들이려면 다른 노드가 동시에 동일한 사용자명으로 등록하는 과정에 있지 않다는 것을 어떤 식으로든 알아야 한다. 이 문제는 우리를 합의로 이끈다.

합의를 달성하는 것은 결정된 것에 모든 노드가 동의하고 결정을 되돌릴 수 없는 방식으로 뭔가를 결정한다는 뜻임을 배웠다. 자세히 살펴보니 광범위한 문제가 실제로는 합의로 환원될 수 있고 서로 동일하다는 게 드러났다. 이렇게 동일한 문제에는 아래와 같은 것들이 있다.

• 선형성 compare-and-set 레지스터: 레지스터는 현재 값이 연산의 매개변수로 넘겨진 값과 같은지 여부에 따라 값을 설정할지 말지 원자적으로 결정해야 한다.
• 원자적 트랜잭션 커밋: 데이터베이스는 분산 트랜잭션을 커밋할 것인지 어보트할 것인지 결정해야 한다.
• 전체 순서 브로드캐스트: 메시징 시스템은 메시지를 전달할 순서를 결정해야 한다.
• 잠금과 임차권: 여러 클라이언트들이 잠금이나 임차권을 얻기 위해 경쟁하고 있을 때 잠금은 누가 성공적으로 잠금을 획득할지 결정한다.
• 멤버십/코디네이션 서비스: 장애 감지기(예를 들어 타임아웃)가 주어지면 시스템은 어떤 노드는 살아 있고 어떤 노드는 세션 타임아웃이 발생해서 죽었다고 생각돼야 하는지 결정해야 한다.
• 유일성 제약 조건: 여러 트랜잭션들이 동시에 같은 키로 충돌되는 레코드를 생성하려고 할 떄 이 제약 조건은 어떤 것을 허용하고 어떤 것을 제약 조건 위반으로 실패하도록 할 것인지 결정해야 한다.

이 모든 것들은 노드가 하나만 있거나 결정하는 능력을 한 노드에만 준다고 하면 간단하게 정리되는 문제들이다. 이것들은 바로 단일 리더 데이터베이스에서 일어나는 일이다. 결정을 하는 모든 능력은 리더에게만 부여되는데, 이것이 단일 리더 데이터베이스가 선형성 연산과 유일성 제약 조건, 전체 순서가 정해진 복제 로그 등을 제공할 수 있는 이유다.

그러나 그 단일 리더에 장애가 나거나 네트워크가 끊겨서 리더에 접속할 수 없게 되면 이런 시스템은 아무 진행도 하지 못하게 된다. 이런 상황을 처리하는 세 가지 방법이 있다.

1. 리더가 복구될 때까지 기다리고 시스템이 그동안 차단되는 것을 받아들인다. 여러 XA/JTA 트랜잭션 코디네이터는 이 선택지를 채택한다. 이 방법은 종료 속성을 만족하지 않기 떄문에 합의를 완전히 해결하지는 않는다. 리더가 복구되지 않으면 시스템은 영원히 차단된다.
2. 사람이 새 리더 노드를 선택하고 시스템이 그 노드를 사용하도록 재설정해서 수동으로 쟁애 복구를 한다. 많은 관계형 데이터베이스가 이 방법을 취한다. 컴퓨터 시스템 밖에 있는 인간 운영자가 결정을 내리기 때문에, 장애 복구 속도는 사람이 행동하는 속도로 제한되며 일반적으로 컴퓨터보다 느리다.
3. 자동으로 새 리더를 선택하는 알고리즘을 사용한다. 이 방법은 합의 알고리즘이 필요하고 불리한 네트워크 조건을 올바르게 처리하는 입증된 알고리즘을 사용하는 게 현명하다.

단일 리더 데이터베이스는 모든 쓰기마다 합의 알고리즘을 실행하지 않고 선형성을 제공할 수 있지만, 리더십을 유지하고 리더십 변경을 위해서는 여전히 합의가 필요하다. 좋은 소식은 합의를 달성하는 내결함성을 지닌 알고리즘과 시스템이 존재한다는 것이고 이번 장에서 이것들을 간략히 설명했다.

Zookeeper 같은 도구는 애플리케이션이 사용할 수 있는 합의, 장애 감지, 멤버십 서비스를 “위탁”하는 데 중요한 역할을 수행한다. 이는 합의 알고리즘을 직접 구현하는 것보다 훨씬 낫다. 합의로 환원될 수 있는 문제 중 하나를 원하고 그것이 내결함성을 지니기를 원한다면 Zookeepr 같은 것을 쓰는 게 현명하다.

그럼에도 모든 시스템이 반드시 합의가 필요한 것은 아니다. 예를 들어 리더 없는 복제 시스템과 다중 리더 복제 시스템은 보통 전역 합의를 사용하지 않는다. 이런 시스템에서 발생하는 충돌은 다른 리더에 걸친 합의가 없어서 생긴 결과지만 괜찮을 것이다. 그냥 선형성 없이 대처하고, 가지치기와 합치기의 버전 기록이 있는 데이터를 잘 처리하는 법을 배울 필요가 있다.

이번 장에서는 분산 시스템 이론에 관한 많은 연구를 참고했다. 이론적 논문과 증명이 항상 이해하기 쉽지는 않고 때로는 비현실적인 가정을 하기도 하지만, 이 분야에서 실용적인 작업을 알리는 데 엄청난 가치가 있다. 논문과 증명은 무엇을 할 수 있고 무엇을 할 수 없는지를 추론하는 데 도움을 주고 분산 시스템에 종종 결함이 있는 반직관적인 방법을 찾는 데 도움을 준다. 시간이 있다면 참고 문헌을 살펴볼 가치가 있다.

이로써 복제(5장), 파티셔닝(6장), 트랜잭션(7장), 분산 시스템 장애 모델(8장), 일관성과 합의(9장)을 다룬 2부를 마무리한다. 이제 확고한 이론적 기반을 닦았으므로 3부에서는 다시 한 번 더욱 실용적인 시스템으로 돌아가서 이종(heterogeneous) 구성 요소로부터 강력한 애플리케이션을 구축하는 방법을 설명한다.

 

Reference: http://www.yes24.com/Product/Goods/59566585

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