[additional] 정족수 합의와 벡터 시계

정족수 합의 프로토콜

정족수 합의 프로토콜은 분산 환경에서 쓰기, 읽기 연산에 대해 K개 이상의 성공 결과를 받아낸 뒤에 클라이언트에 반환함으로써 데이터의 일관성을 유지하는 프로토콜이다.

정족수 합의 프로토콜에는 “중재자 (coordinator)” 노드가 필요하며, 중재자가 실제 클라이언트와 통신하는 매개체이다.

정족수 합의 프로토콜은 세 가지 변수가 존재한다. N, W, R

N : 하나의 키가 다중화되는 노드의 개수 (=replica의 개수)
W : 쓰기 연산의 일관성 판단을 위해 성공 응답을 받아야 하는 노드의 개수
R : 읽기 연산의 일관성 판단을 위해 성공 응답을 받아야 하는 노드의 개수

N, W, R 변수를 튜닝하는 과정은 애플리케이션의 성격에 따라 다르다.

빠른 읽기 연산을 지원해야 하는 앱은 R이 작아야 한다.

빠른 쓰기 연산을 지원해야 하는 앱은 W가 작아야 한다.

보통 아래와 같은 공식으로 강한 일관성, 약한 일관성을 판단한다.

R = 1, W = N : 빠른 읽기 연산 지원
R = N, W = 1 : 빠른 쓰기 연산 지원
W + R > N : 강한 일관성
W + R ≤ N : 약한 일관성

W + R > N. 어떻게 강한 일관성을 보장할까?

N = 3인 상황을 가정해보자.

위 식에 의하면, W, R은 아래와 같은 값을 가질 때 강한 일관성이 보장된다.

W = 1, R = 3

쓰기 연산이 레플리카 중 하나에만 수행되므로, 레플리카 세 곳에서 모두 읽어야 최신 데이터를 확인할 수 있다.
W = 2, R = 2

쓰기 연산이 레플리카 중 두 곳에 수행되므로, 레플리카 두 곳을 읽으면 최신 데이터를 확인할 수 있다.
W = 3, R = 1

쓰기 연산이 모든 레플리카에 수행되므로, 레플리카 한 곳만 읽으면 최신 데이터를 확인할 수 있다.

벡터 시계

벡터 시계는 각 데이터에 [서버, 버전] 쌍을 달아두는 버저닝 방법이다.

이렇게 각 데이터에 벡터 시계를 달아두면, 서로 다른 여러 노드에 다중화된 데이터가 현재 일관적인 상태인지 아닌지 판별할 수 있다.

벡터 시계는 아래와 같은 규칙으로 변화한다.

벡터 시계 [si, vi] 가 존재하면 vi를 1 증가시킨다.
없다면 [si, 1]을 추가한다.

벡터 시계는 어디에 위치한 값이고, 누가 관리하는가?

데이터가 실제 저장되는 가상 노드에 존재한다.

즉, 키-값-벡터시계 형태로 각 가상 노드에 데이터가 저장된다.

아울러 벡터 시계를 증가시키는 건 각각의 가상 노드가 관리한다.

벡터시계를 coordinator가 관리한다고 가정하면, coordinator는 각각의 가상 노드의 벡터 시계 인덱스를 가지고 있어야 한다. 만약 coordinator에 장애가 생겨서 새로운 coordinator가 선출될 경우, 이전 coordinator가 관리하던 벡터 시계 인덱스들이 전부 사라졌기 때문에 데이터 버저닝에 문제가 생긴다.

책에서 제시한 키-값 저장소 분석

책의 예시를 가져와서, 키-값 분산 저장소를 설계해보자.

키-값 저장소 구조.jpg

어떤 구조인가?

분산 시스템은 크게 두 가지로 구분된다.

Leader-based Architecture

분산 시스템 내에 클라이언트의 요청을 먼저 받는 leader가 존재하는 구조.

요청을 받아 순서를 조정하는 등의 선작업이 가능하고, 이후 실제 요청을 처리할 가상 노드에게 포워딩한다.

leader의 개수에 따라 Single Leader, Multi Leader로 구분할 수도 있다.

클라이언트의 요청을 leader가 직접 받기 때문에, leader 장애 시 failover가 필요하다.

여기서 말하는 failover란?
- 분산 시스템 노드 중 새로운 leader를 선출하고
- 클라이언트가 새로운 leader의 존재를 인지하여, 앞으로의 요청은 새로운 leader에게 보낼 수 있어야 하며
- 나머지 노드들은 새로운 leader로부터 요청을 forward받을 수 있어야 한다.
Leaderless Architecture

분산 시스템 내의 모든 노드가 클라이언트의 요청을 직접 받을 수 있는 구조.

클라이언트가 어느 노드에게나 요청을 보낼 수 있기 때문에, failover 작업이 필요없다.

leaderless 구조의 단점

레플리카 장애 후, 복구 됐을 시 데이터 일관성 깨졌을 수 있음.
위 문제 때문에, 레플리카 사용 시 클라이언트가 모든 레플리카에 요청을 보내고 성공 응답을 받아야 함 → 읽기, 쓰기 성능 저하
위 과정에서 데이터 일관성이 깨졌다면, 이 문제를 클라이언트가 해결해야됨. (관심사 분리 오류)

이 때문에, 책에서는 coordinator라 불리는 Single Leader 구조를 제시하고 있다.

coordinator는 leaderless 구조에서 클라이언트가 맡았던

요청의 성공, 실패 판단
데이터 일관성 조율

등에 더해서

정족수 합의 프로토콜을 위한 proxy

역할을 수행한다.

= 백엔드 애플리케이션, 키-값 저장소의 역할이 분명하게 나뉘었다!!

coordinator는 Single Leader인가? Leaderless인가?

coordinator는 Leader의 역할 중 하나인 “선작업” 을 수행하지 않는다.

단순히 요청을 포워딩하는 proxy역할을 할 뿐이다. 이 부분 때문에 coordinator가 섞여있는 구조가 Single Leader인지, Leaderless인지 애매한 부분이 있지만, 클라이언트가 요청을 coordinator에게만 보낸다는 점, 요청의 성공 여부를 coordinator가 판단한다는 점을 봐서 Single Leader 구조라고 생각하겠다.

정족수 합의 프로토콜, 벡터 시계의 역할

모든 레플리카에 요청을 보내서 모두 성공 응답을 받는 방식은 비효율적.

→ 정족수 합의 프로토콜을 사용해서 읽기, 쓰기 성능을 향상시킬 수 있다.

단, 정족수 합의 프로토콜을 사용하면 네트워크 파티션 등으로 인한 데이터 일관성 깨짐이 발생할 수 있다.

→ 이에 대한 해결책으로 벡터 시계가 제시되었다.

정족수 합의 프로토콜 + 벡터 시계

두 가지 기술이 함께 사용될 때, 데이터 저장 흐름은 아래와 같다.

(레플리카는 2개로 가정한다.)

클라이언트는 coordinator에게 데이터 쓰기 요청을 보낸다.
coordinator는 해당 key를 저장하는 2개의 가상 노드 중 하나를 primary 서버로 인지하고 있다. coordinator는 클라이언트의 쓰기 요청을 primary 서버로 전달한다.
primary 서버는 데이터를 쓰고, 벡터 시계를 1 올리거나 새로 만들어서 coordinator에게 전달한다.
coordinator는 이 쓰기 결과를 레플리카 서버 (secondary 서버) 로 전달한다.
secondary 서버는 이 값을 그대로 저장한다. 이 때 벡터시계를 증가시키지 않는다.