데이터베이스 인터널스 - 12장 안티-엔트로피와 배포

개요

데이터베이스 인터널스를 완독했다. 11장 복제와 일관성에 이어서 12장 안티-엔트로피와 배포까지는 정리를 해둔다.

11장 돌아보기

분산 시스템에서는 복제를 통해 가용성과 내결함성을 확보한다. 노드(서버)를 여러 개 복제해서 여러 요청을 바로바로 대응하고, 그 중 일부 노드가 잘못되어도 일관성을 유지할 수 있어야 한다.

CAP 이론에 따르면 분산 시스템은 일관성(C), 가용성(A), 분할 허용(P) 중 두 가지만을 만족시킬 수 있으며, 현실적으로는 CP 또는 AP 중 하나를 선택하게 된다.

일관성 모델을 여러 사용자가 동시에 접근하는 경우를 다루며 선형화 가능성, 순차 일관성, 인과적 일관성 등으로 나뉘며, 각각 구현 난이도와 현실성에 차이가 있다. 세션 모델은 개별 사용자 관점에서의 일관성을 보장하며, 자신이 쓴 값 읽기, 단조 읽기/쓰기, 읽기 후 쓰기 등의 개념으로 구성된다. 결과적 일관성은 시간이 지나면 결국 모든 노드가 동일한 값을 갖게 되는 모델로, CRDT와 함께 사용되면 합의 없이도 안정적인 복제를 가능하게 한다.

안티-엔트로피

엔트로피는 무질서도라고 볼 수 있다. 내버려두면 무질서해진다. 길거리를 청소하지 않으면 쓰레기가 쌓이게 되고, 교통 신호로 통제하지 않으면 교통은 마비된다.

12장에서 말하는 안티-엔트로피는 분산 시스템에서 업데이트 내역이 모든 노드들에게 전파되지 않은, 엔트로피(무질서도)가 올라가는 상황을 다시 질서있게 만들어주는 것이다. 전파되지 않아서 생기는 노드들 간의 불일치를 줄이거나 없애주는 것이다.

읽기 복구

읽기 복구(read repair)는 모든 노드들에 같은 데이터를 요청해서 변경사항이 누락된 노드를 최신 상태로 복구하는 것이다. 이 때 모든 노드를 읽을 것인가, 읽기 복구시에 블로킹을 할 것인가 등으로 기술이 나뉘어지고 개선된다. 원본은 한 노드에만 요청하고 다른 노드에는 요약본(다이제스트)만을 요청할 수도 있다.

힌트 핸드오프

읽기 복구가 읽을 때의 복구를 다룬다면 힌트 핸드오프(hinted handoff)는 쓸때의 문제를 복구하는 것이다. 메커니즘은 간단하다.

예를 들어 A노드가 B노드에 쓰는 중에 문제가 생기면 다른 노드인 C노드에 저장하고 힌트를 남겨둔다. “이건 B노드에 저장할 거였어”. A노드는 B노드가 장애에서 복구된 것을 확인하면 C노드에 저장했던 데이터를 힌트 메모를 참고하여 B노드에 쓴다.

머클 트리

읽기 복구와 힌트 핸드오프가 포어그라운드에서 실행되는 것이라면, 머클 트리는 백그라운드에서 실행된다. 실제 데이터를 비교하는 대신 데이터를 저장한 트리를 계층별로 해시 트리로 저장해서 해시를 비교하는 것이다. 모든 데이터를 직접 비교하지 않고 계층적으로 구성된 해시 트리(Merkle Tree)의 해시를 루트에서부터 비교함으로써,어느 부분에서 차이가 나는지 빠르게 파악할 수 있다.

비트맵 버전 벡터

비트맵 버전 벡터(Bitmap Version Vector)는 분산 시스템에서 노드 간 데이터의 최신 여부를 판단하기 위해 사용되는 메타데이터 구조다.

일반적인 버전 벡터는 각 노드가 마지막으로 본 변경 시점을 숫자로 관리하는데 비트맵 버전 벡터는 각 노드가 갖고 있는 데이터 범위를 비트맵처럼 표시하여 비교한다. 메모리 사용량을 줄이고,노드 간 어느 범위의 데이터가 누락됐는지 빠르게 파악할 수 있다.

다음 예시에서 A는 B보다 3번 키의 데이터가 더 최신이라는 걸 쉽게 알 수 있다.

• 노드 A: [1, 1, 1, 0, 0]
• 노드 B: [1, 1, 0, 0, 0]

가십 전파

가십 프로토콜은 노드 간 정보를 퍼뜨릴 때 사용하는 방식으로, 사람들 사이의 “가십(소문)”처럼 무작위 이웃에게 정보를 전달한다.

1. 한 노드가 주변 노드 하나를 무작위로 선택해 최신 정보를 전달한다.
2. 받은 노드도 다시 다른 노드에게 전달한다.
3. 이 과정을 반복하면서 전체 네트워크에 정보가 퍼진다.

네트워크 전체에 정보가 빠르게, 그리고 견고하게 전파되고, 일부 노드가 실패해도 전파가 계속 이어질 수 있기에 내결함성이 뛰어나다. 가십 프로토콜은 Cassandra, DynamoDB 등에서 노드 상태, 버전 벡터, 쓰기 복제 상태 등을 전파할 때 사용한다.

마무리

12장은 복제된 데이터 간의 불일치를 정리하고 일관성을 유지하기 위한 다양한 전략들을 다룬다. 읽기 시점의 복구(읽기 복구), 쓰기 시점의 임시 저장(힌트 핸드오프), 백그라운드 비교(머클 트리), 메타데이터 비교 방식(비트맵 버전 벡터), 그리고 정보 확산 전략(가십 전파)까지. 각 기법은 일관성, 가용성, 성능 간의 트레이드오프 속에서 목적에 따라 적절히 선택된다.