6장 키-값 저장소 설계 - 데이터 일관성

가상 면접 사례로 배우는 대규모 시스템 설계 기초 – System Design Interview

6장 키-값 저장소 설계 - 데이터 일관성

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.

정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.
* 정족수 : 여러 사람의 합의로 운영되는 의사기관에서 의결을 하는데 필요한 최소한의 참석자 수

기호 정의 정리
N = 사본 개수.
W = 쓰기 연산에 대한 정족수. (쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.)
R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 한다.

N = 3 인 경우의 예시를 살펴보자.

* ACK = acknowledgement

N,W,R 값에 따른 구성

R = 1, W = N: 빠른 읽기 연산에 최적화된 시스템
W = 1, R = N: 빠른 쓰기 연산에 최적화된 시스템
W + R > N: 강한 일관성이 보장됨 (보통 N=3, W=R=2)
W + R ≤ N: 강한 일관성이 보장되지 않음

일관성 모델

강한 일관성

모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 다시 말해서 클라이언트는 절대로 낡은(out-of-date) 데이터를 보지 못한다.

약한 일관성

읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.

최종 일관성

약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화)되는 모델이다.

강한 일관성을 달성하는 일반적인 방법은, 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 데이터에 대한 읽기/쓰기를 금지하는 것이다. 이 방법은 고가용성 시스템에는 적합하지 않다. (새로운 요청의 처리가 중단됨)

다이나모 또는 카산드라 같은 저장소는 최종 일관성 모델을 택하고 있다.

여기서도 최종 일관성 모델을 기준으로 키-값 저장소를 설계한다.

최종 일관성 모델을 따를 경우 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있는데, 이 문제는 클라이언트가 해결해야 한다.

비 일관성 해소 기법: 데이터 버저닝

데이터를 다중화 하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아진다.
버저닝(versioning)과 벡터 시계(vector clock)는 그 문제를 해소하기 위해 등장한 기술이다.

동일하게 name: john 이라는 값을 가지고 있는 서버 n1, n2 에서
동시에 n1 에서는 “johnSanFrancisco”로, n2 에서는 “johnNewyork”으로 바꾼다고 하자.
이렇게 되면 충동(conflict)하는 두 값을 갖게 된다. 그 각각을 버전 v1, v2 라고 하자.

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이다. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.

벡터 시계는 D([S1, v1], [S2, v2], … [Sn, vn])와 같이 표현한다고 가정하자.
여기서 D는 데이터이고, vi 는 버전 카운터 Si는 서버 번호 이다.

만일 데이터 D를 서버 Si에 기록하면, 시스템은 아래 작업 가운데 하나를 수행하여야 한다.

• [Si, vi]가 있으면 vi를 증가시킨다.
• 그렇지 않으면 새 항목 [Si, 1]를 만든다.

예시를 통해 이해해보자.

① 클라이언트가 데이터 D1을 시스템에 기록한다. 이 쓰기 연산을 처리한 서버는 Sx이다. 따라서 벡터 시계는 D1[Sx, 1]으로 변한다.

② 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트한 다음 기록한다. D2는 D1에 대한 변경이므로 D1을 덮어쓴다. 이때 쓰기 연산은 같은 서버 Sx가 처리한다고 가정하자. 벡터 시계는 D2([Sx, 2])로 바뀔 것이다.

③ 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록한다. 이 쓰기 연산은 Sy가 처리한다고 가정하자. 벡터 시계 상태는 D3([Sx, 2], [Sy, 1])로 바뀐다.

④ 또 다른 클라이언트가 D2를 읽고 D4로 갱신한 다음 기록한다. 이때 쓰기 연산은 서버 Sz가 처리한다고 가정하자. 벡터 시계는 D4([Sx, 2], [Sz, 1])일 것이다.

⑤ 어떤 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 된다. D2를 Sy와 Sz가 각기 다른 값으로 바꾸었기 때문이다. 이 충돌은 클라이언트가 해소한 후에 서버에 기록한다. 이 쓰기 연산을 처리한 서버는 Sx였다고 하자. 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1]) 로 바뀐다. 충돌이 일어났다는 것을 어떻게 감지하는지는 잠시 후에 더 자세히 살펴볼 것이다.

벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지 (따라서 충돌이 없는지) 쉽게 판단할 수 있다.

버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 된다.
* 여기서 D 뒤에 붙은 숫자는 순서 구분을 위해 붙인 것이라고 생각된다.

단점은 두가지 이다.

첫 번째는 충돌 감지및 해소 로직이 클라이언트에 들어가야 하므로 클라이언트 구현이 복잡해진다.

두 번째는 [서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다는 것이다. 이 문제를 해결하려면 그 길이에 어떤 임계치(threshold)를 설정하고, 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 해야 한다.
이론적으로는 이렇게 하면 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지게 된다.
그러나 아마존의 문헌에 따르면 실제 서비스에서 그런 문제가 벌어지는 것을 발견한 적이 없다고 한다. 그러니 대부분의 기업에서 적용해도 괜찮은 솔루션 일 것이다.

장애 처리

장애 감지 후 장애 해소 시도 

장애 감지

분산 시스템에서는 그저 한 대 서버가 “지금 서버 A가 죽었습니다”라고 한다 해서 바로 서버 A를 장애처리 하지는 않는다. 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주하게 된다.

모든 노드 사이에 멀티캐스팅(multicasting) 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이다. 하지만 이 방법은 서버가 많을 때는 분명 비효율 적이다.
* 멀티캐스트(multicast)란 한 번의 송신으로 메시지나 정보를 목표한 여러 컴퓨터에 동시에 전송하는 것을 말한다. (wiki)

가십 프로토콜(gassip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 채택하는 편이 보다 효율적이다.

가십 프로토콜의 동작 원리는 다음과 같다.

- 각 노드는 멤버십 목록(membership list)를 유지한다. 멤버십 목록은 각 멤버 ID와 그 박동 카운터(heartbeat counter) 쌍의 목록이다.
- 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.
- 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주한다.

일시적 장애 처리

엄격한 정족수 접근법을 쓴다면 앞에서 설명한대로 읽기와 쓰기 연산을 금지해야한다.

느슨한 정족수 접근법은 이 조건을 완화하여 가용성을 높인다. 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건상한 서버를 해시 링에서 고른다. (이때 장애 상태인 서버는 무시한다.)

장애 서버로 가는 요청은 다른 서버가 잠시 맡아 처리한다. 장애 서버가 복구되었을 때 그동안 발생한 변경사항은 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서(hint)를 남겨둔다. (이러한 장애 처리 방안을 “단서 후 임시 위탁(hinted handoff)” 기법이라 부른다.)

영구 장애 처리

반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화 한다.

반-엔트로피 프로토콜은 사본들을 데이터를 비교하여 각 사본을 최신 버전으로 갱신 하는 과정을 의미한다.

사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서 머클(Merkle) 트리를 사용하면 좋다.

머클 트리

해시 트리(hash tree)라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시(자식 노드가 종단(leaf 노드 인 경우), 또는 자식 노드들의 레이블로부터 계산된 해시 값을 테이블로 붙여두는 트리다. 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증(verification)할 수 있다. (wiki)

머클 트리를 사용하면 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해진다.

데이터 센터 장애 처리

데이터를 여러 데이터 센터에 다중화 하는 것이 중요하다.

fin.