[Architecture]분산 키-값 저장소 설계

개요

키-값 저장소는 키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스입니다. 이 저장소에 저장되는 값은 고유 식별자를 키로 가져야 하며, 키와 값 사이의 이런 연결 관계를 "키-값" 쌍이라고 합니다. 키는 유일해야 하며 성능상의 이유로 짧을수록 좋습니다.

이 글에서는 다음 연산을 지원하는 키-값 저장소를 설계하고 분석합니다.

• put(key, value): 키-값 쌍을 저장소에 저장한다.
• get(key): 인자로 주어진 키에 연결된 값을 꺼낸다.

문제 이해 및 설계 범위 확정

분산 키-값 저장소 설계 시 고려해야 할 주요 요구사항은 다음과 같습니다:

• 키-값 쌍의 크기는 10KB 이하이다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성을 제공해야 한다: 시스템 장애가 있더라도 빨리 응답해야 한다.
• 높은 규모 확장성을 제공해야 한다: 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
• 데이터 일관성 수준은 조정이 가능해야 한다.
• 응답 지연시간(latency)이 짧아야 한다.

분산 서버 키-값 저장소: 분산 해시 테이블

분산 시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 합니다.

CAP 정리 이해하기

CAP 정리란 분산 시스템은 원하는 세 가지 특성, 즉 일관성(Consistency), 가용성(Availability) 및 분할 내성(Partition Tolerance) 중 두 가지만 제공할 수 있음을 증명한 정리입니다.

CAP의 의미:

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

위 그림의 CA, CP, AP와 같이 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 합니다.

이상적 상태 vs 실제 분산 시스템

이상적인 상태에서는 모든 노드의 데이터가 자동으로 동기화되고 네트워크 파티션 문제가 발생하지 않습니다. 하지만 실제 분산 시스템에서는 파티션 문제를 피할 수 없으며, 이 경우 일관성과 가용성 사이에서 선택을 해야 합니다.

이상적 상태

이상적인 분산 시스템에서는 다음과 같은 상황을 가정합니다:

• 완벽한 동기화: n1의 데이터가 즉시 자동으로 n2, n3에 복제됩니다.
• 네트워크 안정성: 네트워크 파티션 문제가 발생하지 않습니다.
• 즉각적인 응답: 모든 노드가 항상 즉시 응답 가능한 상태입니다

실제 분산 시스템

분산 시스템은 파티션 문제를 피할 수 없다. 그리고 파티션 문제가 발생하면 우리는 일관성과 가용성 사이에서 하나를 선택해야한다.

현실적 상황:

• n3에 장애가 발생하여 n1, n2와 통신할 수 없는 상태입니다.
• 클라이언트는 여전히 n1, n2, n3 모두에 접근을 시도할 수 있습니다.

발생 가능한 문제:

1. 데이터 불일치: 클라이언트가 n1, n2에 기록한 새로운 데이터는 n3에 저장되지 않습니다.
2. 오래된 데이터: n3에 기록되었으나 아직 n1, n2로 전달되지 않은 데이터가 있다면, n1과 n2는 오래된 버전의 데이터를 가지고 있게 됩니다.

이런 상황에서 시스템은 일관성(Consistency)과 가용성(Availability) 중 하나를 선택해야 합니다:

1. CP(Consistency + Partition Tolerance) 시스템: 예시: 온라인 뱅킹 시스템에서 사용자 A가 계좌에서 $100를 인출하려고 합니다.
   • 접근 방식: 가용성 대신 일관성을 선택합니다.
   • 구체적 행동: n1, n2에 대한 쓰기 연산을 중단시킵니다.
   • 장점: 모든 노드가 항상 동일한 최신 데이터를 가집니다.
   • 단점: n3가 복구될 때까지 시스템의 일부 기능이 중단될 수 있습니다.
   • 적합한 사례: 은행 시스템, 주식 거래 플랫폼 등 데이터 정확성이 절대적으로 중요한 경우
   • 시스템은 n3와의 통신이 불가능하므로 거래를 거부합니다.
   • 사용자는 일시적으로 불편을 겪지만, 잘못된 계좌 잔액 정보로 인한 심각한 문제는 방지됩니다.
2. AP(Availability + Partition Tolerance) 시스템: 예시: 소셜 미디어 플랫폼에서 사용자 B가 새 게시물을 작성합니다.
   • 접근 방식: 일관성 대신 가용성을 선택합니다.
   • 구체적 행동: 오래된 데이터를 반환할 위험이 있더라도 계속 쓰기 연산을 허용합니다.
   • 장점: 시스템이 계속 운영되며 사용자는 서비스를 이용할 수 있습니다.
   • 단점: 일시적으로 노드 간 데이터 불일치가 발생할 수 있습니다.
   • 적합한 사례: 소셜 미디어 플랫폼, 콘텐츠 관리 시스템 등 즉각적인 가용성이 더 중요한 경우
   • 시스템은 n1과 n2에 게시물을 저장하고, 사용자에게 성공 메시지를 보냅니다.
   • n3가 복구된 후, 새 게시물 데이터가 n3에 동기화됩니다.
   • 이 과정에서 일부 사용자는 잠시 동안 게시물을 볼 수 없을 수 있지만, 전반적인 서비스는 계속 이용 가능합니다.

분산 키-값 저장소의 핵심 컴포넌트 분석

분산 키-값 저장소는 여러 핵심 컴포넌트로 구성되어 있으며, 각 컴포넌트는 시스템의 성능, 신뢰성, 확장성을 보장하는 데 중요한 역할을 합니다. 이 섹션에서는 각 컴포넌트를 자세히 살펴보고, 그 구현 방법과 실제 적용 사례를 분석하겠습니다.

시스템 컴포넌트 분석하기

키-값 저장소 구현에 사용될 핵심 컴포넌트

• 데이터 파티션
• 데이터 다중화(replication)
• 일관성(consistency)
• 일관성 불일치 해소(inconsistency resolution)
• 장애 처리
• 시스템 아키텍처 다이어그램
• 쓰기 경로
• 읽기 경로

데이터 파티션

대규모 애플리케이션의 경우 전체 데이터를 한 대 서버에 저장하는 것은 불가능합니다. 이때 가장 단순한 해결책은 데이터를 작은 파티션들로 분할한 다음 여러대 서버에 저장하는 것입니다.

데이터를 파티션 단위로 나눌 때는 다음 두 문제를 중요하게 생각해야 합니다.

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

 

안정 해시 설계(consistent hash) 는 이런 문제를 푸는데 적합한 기술이 됩니다.

구현 방법:

• 안정 해시(Consistent Hashing): 데이터와 서버를 가상의 원형 해시 공간에 매핑합니다.

장점:

1. 데이터를 여러 서버에 균등하게 분산할 수 있습니다.
2. 노드 추가/삭제 시 데이터 재분배를 최소화할 수 있습니다.

데이터 다중화 (Data Replication)

높은 가용성과 안정성을 위해서는 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있습니다.

N개 서버를 선정하는 방법:

• 어떤 키를 해시 링 위에 배치한 후, 그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 보관한다.

구현 방법:

• N개의 서버에 비동기적으로 데이터를 복제합니다.
• 안정 해시 링을 사용하여 복제 대상 서버를 선정합니다.

주의사항:

• 가상 노드 사용 시 같은 물리 서버를 중복 선택하지 않도록 주의해야 합니다.

데이터 일관성 (Data Consistency)

데이터 일관성은 여러 노드에 분산된 데이터가 서로 일치하도록 유지하는 기술입니다.

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

구현 방법:

• 정족수(Quorum) 프로토콜: 이를 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있습니다.
  • N: 총 복제본 수
  • W: 쓰기 연산 정족수, 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 연산이 성공했다는 응답을 받아야 한다.
  • R: 읽기 연산 정족수, 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 연산이 성공했다는 응답을 받아야 한다.

예를 들어 N=3, W=1의 의미는 쓰기 연산이 성공했다고 판단하기 위해서는 중재자(coordinator)는 최소 한대 서버로 부터 쓰기 성공 응답을 받아야 한다는 뜻이다. 따라서 n1으로부터 ACK를 받았다면 n0, n2로 부터의 응답은 기다릴 필요가 없다.

중재자는 클라이언트와 노드 사이에서 proxy 역할을 한다.

W, R, N을 정하는 방법 예시:

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

일관성 모델

일관성 모델은 분산 시스템 내에서 데이터가 어떻게 업데이트되고 액세스되는지 정의합니다. 이는 시스템의 예측 가능성과 신뢰도를 보장하는 데 중요합니다.

종류:

• 강력한 일관성(Strong Consistency): 모든 노드가 항상 최신 데이터를 볼 수 있도록 보장합니다. 사용자는 언제나 최신의 데이터를 보게 됩니다.
  • 방법: 모든 사본에 현재 쓰기 연산의 결과가 반영될 때 까지 해당 데이터에 대한 읽기/쓰기를 금지
  • 문제: 고가용성 시스템에는 적합하지 않습니다.
• 약한 일관성(Weak Consistency): 데이터는 일정 시간이 지나면 최신 상태로 동기화됩니다. 사용자가 오래된 데이터를 보게 될 수 있습니다.
• 최종 일관성(Eventual Consistency): 시스템이 어떠한 업데이트 후에 결국에는 일관성 있는 상태로 수렴한다는 것을 보장합니다.
  • 문제: 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있다.
  • 해결 방법: 클라이언트측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록한다.

비 일관성 해소 기법: 데이터 버저닝(Data Versioning)

데이터 버저닝은 동시 수정으로 인한 데이터 충돌을 해결하는 기술입니다. 각 데이터 업데이트에 고유한 버전 번호를 부여하여 변경 사항을 추적하고, 충돌을 해결합니다.

구현 방법:

• 각 데이터 업데이트에 고유한 버전 번호를 부여합니다.
• 벡터 시계(Vector Clock)를 사용하여 이벤트의 인과관계를 추적합니다.

예시:

사용자 A와 B가 동시에 같은 문서를 수정할 경우:

1. 두 수정 사항에 각각 다른 버전 번호를 부여합니다.
2. 시스템은 두 버전을 모두 저장하고, 충돌 해결을 위해 애플리케이션 로직이(어떤 수정 사항이 더 최신인지 결정)나 사용자 개입을 요청할 수 있습니다.

장애 처리 (Failure Handling)

장애 처리는 분산 시스템 설계에서 중요한 부분입니다. 시스템이 예상치 못한 오류나 문제에도 계속 작동할 수 있도록 보장하는 방법론입니다.

이를 위해서는 장애를 신속하게 감지하고 해당 문제를 해결하고 시스템을 정상 상태로 복구하는 과정을 거처야합니다.

전략:

• 장애 감지 (Failure Detection): 시스템의 비정상적인 동작을 신속하게 감지합니다. 예를 들어, 온라인 쇼핑몰에서 결제 서버가 갑자기 응답하지 않을 경우, 이를 빠르게 감지해야 합니다.
• 장애 해소 (Failure Resolution): 감지된 문제를 해결하고, 시스템을 정상 상태로 복구하는 과정입니다. 예를 들어, 결제 서버에 문제가 생겼다면, 다른 서버로 작업을 옮기거나 서버를 재시작하는 등의 조치를 취할 수 있습니다.
• 영구 장애 처리(Failure Resolution): 영구 장애 처리는 시스템의 한 부분이 복구 불가능한 상태로 손상되었을 때 이를 감지하고 대응하는 방법입니다. 이는 일시적 장애와 달리 장기적이고 근본적인 해결책을 필요로 합니다.

장애 감지(Failure Detection)

장애 감지는 시스템의 어떤 부분이 제대로 작동하지 않고 있는지 신속하게 파악하는 과정입니다. 서버가 많을때는 Gossip Protocol을 사용하면 효율적으로 장애 감지를 할 수 있습니다.

• Gossip Protocol: 각 노드가 주기적으로 서로에게 '살아있음' 메시지를 보냅니다. 노드가 예상 시간 안에 메시지를 보내지 않으면, 다른 노드들은 그 노드가 실패한 것으로 간주합니다. 예를 들어, 여러 데이터 센터에 퍼져 있는 서버들이 서로의 상태를 주기적으로 확인할 수 있습니다.

일시적 장애 처리(Failure Resolution)

Gossip Protocol로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야한다.

방법:

• Gossip Protocol: 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 취합니다. 예를 들어, 한 노드가 일시적으로 응답하지 않는다면, 다른 노드가 그 작업을 일시적으로 인계받을 수 있습니다.
• Hinted Handoff: 일시적으로 도달할 수 없는 노드가 다시 온라인 상태가 되었을 때, 누락된 데이터를 전달하기 위해 '힌트'를 주고받습니다. 예를 들어, 데이터베이스 클러스터에서 한 노드가 일시적으로 다운되었다가 복구되었을 때, 누락된 데이터를 안전하게 복구할 수 있도록 합니다.

영구 장애 처리(Failure Resolution)

영구 장애 처리는 시스템의 한 부분이 영구적으로 손상되었을 때, 이를 감지하고 대응하는 방법입니다.

방법:

• Anti-Entropy: 시스템의 다른 부분 간에 데이터를 주기적으로 동기화하여, 영구적으로 손상된 데이터를 복구하고 일관성을 유지합니다. 예를 들어, 클라우드 스토리지 시스템에서는 주기적으로 데이터를 검사하고, 필요하면 복제하여 데이터 손실을 방지합니다. 이를 효과적으로하기 위해 Merkle Trees가 사용 된다.
• Merkle Trees: 사본 간 일관성이 망가진 상태를 효과적으로 탐지하고, 전송 데이터 양을 최소화하기 위해 사용됩니다. 데이터 블록의 해시를 트리 구조로 저장하여, 두 사본의 데이터가 다를 경우 어느 부분이 다른지 빠르게 식별할 수 있게 합니다. 예를 들어, 대규모 분산 데이터베이스에서는 Merkle 트리를 사용하여 빠르고 효율적으로 데이터 불일치를 찾아낼 수 있습니다.

시스템 아키텍처

분산 키-값 저장소의 전체적인 구조는 다음과 같습니다.

• 클라이언트는 API(get, put)를 통해 시스템과 통신합니다.
• 중재자(Coordinator)는 클라이언트와 노드 사이의 프록시 역할을 합니다.
• 노드들은 안정 해시 링 위에 분포되어 있습니다. 안정 해시 설계(consistent hash) 참고
• 시스템은 완전히 분산되어 있어 노드의 자동 추가/삭제가 가능합니다.
• 데이터는 여러 노드에 다중화되어 저장됩니다.
• 단일 장애점(SPOF)이 없는 구조입니다.

쓰기 경로에서 발생하는 일

1. 쓰기 요청이 커밋로그 파일에 기록됩니다.
2. 데이터가 메모리 캐시에 기록됩니다.
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.

SStable: Sorted-String Table의 약어로 키-값의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

읽기 경로에서 발생하는 일

1. 데이터가 메모리 있는지 검사합니다. 없으면 2로 이동합니다.
2. 데이터가 메모리에 없으므로 블룸 필터를 검사합니다.
3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냅니다.
4. SSTable에서 데이터를 가져옵니다.
5. 해당 데이터를 클라이언트에게 반환합니다.

Bloom Filter: 어떤 키가 어떤 SSTable에 있는지 확인하는 빠른 방법으로 확률적으로 정확하며 빠르게 키 존재 여부를 판단하는 데이터 구조입니다.

요약

분산 키-값 저장소의 각 컴포넌트는 서로 긴밀하게 연결되어 작동하며, 전체 시스템의 성능, 확장성, 신뢰성을 보장합니다. 안정 해시, 데이터 다중화, 일관성 모델, 버저닝, 장애 처리 등의 기술을 적절히 조합함으로써, 대규모 데이터를 효율적으로 관리하고 높은 가용성을 제공하는 강력한 분산 시스템을 구축할 수 있습니다.

분산 키-값 저장소 설계에 사용되는 주요 기술과 그 목적을 정리하면 다음과 같습니다.

목표/문제 기술

대규모 데이터 저장	안정 해시를 사용하여 서버에 부하 분산
읽기 연산에 대한 가용성 보장	데이터를 여러 데이터센터에 다중화
쓰기 연산에 대한 가용성 보장	버저닝 및 벡터 시계를 사용하여 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성(heterogeneity)	안정 해시
조절 가능한 데이터 일관성	정족수 합의(quorum consensus)
일시적 장애 처리	느슨한 정족수 프로토콜 및 단서 후 임시 위탁
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터센터에 다중화

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