키-값 저장계

분산 키-값 저장소

💬 CAP 정리

분산 키-값 저장소는 분산 해시 테이블이라고도 불립니다. 키-값 쌍을 여러 서버에 분산시키는 탓입니다. 분산 시스템을 설계할 때는 흔히 CAP 정리를 이해하고 있어야 합니다.

CAP 정리란, C(Consistency), A(Availability), P(Partition)이라는 세 가지 요구성을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 것입니다. 그렇다면 CAP란 각각 무엇을 의미할까요?

• 데이터 일관성 (Consistency)
  • 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
• 가용성 (Availability)
  • 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내 (Partition Tolerance)
  • 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.

CAP 정리는 이들 가운데 어떤 두 가지를 충족하면 나머지 하나는 반드시 희생되어야 한다는 것을 의미합니다. 따라서 나올 수 있는 분산 키-값 저장소는 다음과 같습니다.

그러나 통상 네트워크 장애는 피할 수 없는 문제입니다. 따라서 파티션 문제를 필수적으로 감내할 수 있도록 설계되어야 합니다. 그렇기에 실제로 CA 시스템은 존재하지 않습니다. 그렇다면 CP 시스템과 AP 시스템의 실제 예시로는 무엇이 있을까요?

• CP 시스템 은행권 시스템은 보통 데이터 일관성을 양보하지 않는다. 예를 들어 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못한다면 큰 문제일 것이기 때문이다.
  
• AP 시스템 일관성 대신 가용성을 선택한 시스템은 설사 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용하는 것이다.
  

💬 데이터 파티션

대규모 애플리케이션의 경우 전체 데이터를 한 대의 서버에 모두 넣는 것은 불가능합니다. 가장 단순한 해결책은 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장하는 것입니다. 이렇게 파티션 단위로 나눌 때 다음 두 문제를 중요하게 따져 봐야 합니다.

1. 데이터를 여러 서버에 고르게 분산할 수 있는가?
2. 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가?

안정 해시는 이런 문제를 푸는 데 적합한 기술 중 하나일 수 있습니다. 규모 확장에 용이하고 각 서버가 용량에 맞게 가상 노드의 수를 조정할 수 있기 때문입니다.

💬 데이터 다중화

높은 가용성과 안정성을 확보하기 위해서는 데이터를 n개의 서버에 비동기적으로 다중화해야 합니다. 여기서 n은 튜닝 가능한 값입니다.

가상 노드를 사용할 경우 n개의 노드가 대응될 실제 물리 서버의 개수보다 작아질 가능성이 있습니다. 따라서 노드를 선택할 떄 같은 물리 서버를 중복으로 선택하지 않도록 해야 합니다.

💬 데이터 일관성

여러 노드에 다중화된 데이터는 적절하게 동기화돼 있어야 합니다. 정족수 합의 프로토콜을 쓰면 읽기와 쓰기 연산에 대해 일관성을 보장할 수 있습니다.

N: 사본 개수

W: 쓰기 연산에 대한 정족수 (쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 완료됐다는 응답을 받아야 한다)
R: 읽기 연산에 대한 정족수 (읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 읽기 연산이 완료됐다는 응답을 받아야 한다)

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

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

데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성이 생깁니다. 이를 해결하기 위해 Versioning과 Vetor Clock이라는 기술이 등장하게 되었습니다. 벡터 시계는 데이터가 몇 번째 버전의 데이터인지 시간성을 가지는 데이터로 관리하는 것입니다. 예시를 통해 이해해 보겠습니다.

D: 데이터

Vi: 버전 카운터

Si: 서버 번호

1. 클라이언트가 데이터 D1을 시스템에 기록한다. 이 쓰기 연산을 처리한 서버는 Sx이다. 따라서 벡터 시계는 D1[Sx, 1]으로 변한다.
2. 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트한 다음 기록한다. D2는 D1에 대한 변경이므로 D1을 덮어쓴다. 이때 쓰기 연산은 같은 서버 Sx가 처리한다고 가정하자. 벡터 시계는 D2([Sx, 2])로 바뀔 것이다.
3. 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록한다. 이 쓰기 연산은 Sy가 처리한다고 가정하자. 벡터 시계 상태는 D3([Sx, 2], [Sy, 1])로 바뀐다.
4. 또 다른 클라이언트가 D2를 읽고 D4로 갱신한 다음 기록한다. 이때 쓰기 연산은 서버 Sz가 처리한다고 가정하자. 벡터 시계는 D4([Sx, 2], [Sz, 1])일 것이다.
5. 어떤 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 된다. D2를 Sy와 Sz가 각기 다른 값으로 바꾸었기 때문이다. 이 충돌은 클라이언트가 해소한 후에 서버에 기록한다. 이 쓰기 연산을 처리한 서버는 Sx였다고 하자. 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz, 1]) 로 바뀐다.

이러한 방식은 두 가지의 단점을 가집니다. 하나는 충돌 감지 및 해소 로직이 클라이언트에 있어서 클라이언트 구현이 복잡해진다는 것입니다. 다른 하나는 [서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다는 것입니다.

두 번째 문제의 경우 어떤 임계치를 설정하고 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 하는 것입니다.

💬장애 처리

❕장애 감지

한 대의 서버가 어떤 서버에 장애가 있다는 보고를 제시한다고 해서 바로 장애 처리를 하지는 않습니다. 보통 여러 대의 서버가 어떤 서버에 대해 장애가 발생한 것 같다고 응답했을 경우, 실제로 장애가 발생했다고 간주하게 됩니다. 이를 위해서는 모든 노드 사이에 멀티캐스팅 채널을 구현하는 것이 가장 쉬운 방법이지만, 이는 서버가 많을 떄 비효율적입니다. 따라서 가십 프로토콜 같은 분산형 장애 감지 솔루션을 선택하는 쪽이 더 좋습니다.

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

1. 각 노드는 멤버십 목록을 유지합니다. 멤버십 목록은 각 멤버 ID와 그 박동 카운터 쌍의 목록입니다.
2. 각 노드는 주기적으로 자신의 박동 카운터를 증가시킵니다.
3. 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냅니다.
4. 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신값으로 갱신합니다.
5. 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주합니다.

❕일시적 장애 처리

엄격한 정족수 접근법을 쓴다면 읽기와 쓰기 연산을 금지해야 합니다. 하지만 느슨한 정족수 접근법은 이 조건을 완화하여 가용성을 높입니다. 정족수가 요구하는 사항을 강제하는 것보다 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고릅니다.

네트워크나 서버 문제로 장애가 발생하면 해당 서버로 가는 요청을 잠시 다른 서버가 맡아서 처리합니다. 그동안 발생한 변경 사항은 해당 서버가 복구되었을 때 일괄로 반영하여 일관성을 보존하는 방식입니다.

❕영구 장애 처리

반-엔트로피 (Anti-Entrophy) 프로토콜을 구현하여 사본들을 동기화합니다. 반-엔트로피 프로토콜은 사본들의 데이터를 비교하여 각 사본을 최신 버전으로 갱신하는 과정을 의미합니다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 사용하면 좋습니다.

머클 트리란 해시 트리라고도 불리는데, 각 노드에 그 자식 노드들에 보관된 값의 해시나 자식 노드들의 레이블로부터 계산된 해시 값을 테이블로 붙여 두는 트리입니다. 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있습니다.