System Design. Part06. 키 값 저장소 설계

Part04. 키 값 저장소 설계

분산 키-값 저장소는 대규모 데이터에 대해 확장성, 가용성, 내결함성을 달성하기 위해 다음 요소들을 종합적으로 고려한다.

CAP 정리

• CAP 정리:
  • 분산 시스템은 데이터 일관성(C), 가용성(A), 파티션 감내(P) 중 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리
  • 대부분 네트워크 장애(P)를 기본으로 가정하므로, 시스템 설계는 가용성(AP)과 일관성(CP) 사이의 트레이드오프를 중심으로 이루어진다.
• 아키텍처 유형:
  • Masterless (대칭형): 모든 노드가 동등한 역할을 수행하며 단일 장애점이 없다. (예: Dynamo, Cassandra)
  • Master-based (비대칭형): Master 노드가 메타데이터 관리, 노드 할당 등 핵심 역할을 수행한다. (예: Bigtable/HBase, Redis)

---

키-값 저장소 구현에 사용될 컴포넌트들 및 기술

1. 데이터 파티션

• 안정 해시: 해시 링 위에 서버와 키를 분산시켜 서버 추가/제거 시 데이터 이동을 최소화한다.
• 다양성: 서버 성능에 따라 가상 노드 수를 조절하여 부하를 균형 있게 분산한다.

2. 데이터 다중화

• N-way 복제: 가용성과 내구성을 위해 데이터를 N개의 노드에 복제한다.

3. 데이터 일관성

• 정족수 합의 (Quorum Consensus):
  • N(복제본 수), W(쓰기 정족수), R(읽기 정족수)를 설정하여 일관성 수준을 조절한다.

비 일관성 해소 기법

1. 버저닝: 데이터 수정 시 불변 버전 생성
2. 벡터 시계: [서버, 카운터] 쌍 부착, 선후/충돌 판단

4. 장애 처리

4.1 장애 감지

• Gossip Protocol: 멤버십 목록 교환, heartbeat 기반 감지

4.2. 일시적 장애 처리

• Sloppy Quorum: 정족수에 포함된 노드 일부가 장애 상태일 때 다른 건강한 노드가 임시로 요청을 처리하여 가용성을 유지
• Hinted Handoff: 장애 노드 대신 쓰기를 처리한 노드가 해당 데이터를 임시로 보관하다가 장애 노드가 복구되면 원래 위치로 데이터를 전송

4.3. 영구 장애 처리

• Anti-Entropy: 복제본 간 데이터 불일치를 해소하기 위해 주기적으로 데이터를 동기화하는 프로토콜
• Merkle Tree: 데이터 전체를 비교하지 않고 해시 트리 간의 비교를 통해 차이가 있는 부분만 찾아내어 동기화에 필요한 데이터 전송량을 최소화

5. 쓰기 경로

• Commit Log: 쓰기 요청을 로그 파일에 추가하여 내구성을 보장
• Memtable: 데이터를 메모리의 정렬된 자료구조에 기록
• Flush & SSTable: Memtable이 가득 차면, 디스크에 정렬된 문자열 테이블(SSTable) 파일로 저장
• Compaction: 백그라운드에서 여러 SSTable 파일을 병합하여 중복/삭제된 데이터를 정리하고 읽기 성능을 최적화

Compaction이란?

쓰기 경로에서 생성된 SSTable을 관리하는 백그라운드 프로세스.
흩어져 있는 여러 SSTable 파일들을 병합하여 새로운 SSTable을 만듦

6. 읽기 경로

• Bloom Filter 조회
  • 키가 특정 SSTable에 존재할 가능성이 있는지 빠르게 확인하여 불필요한 디스크 접근을 차단 -> 색인표
• Memtable 조회
• SSTable 스캔 (최신순)
• 정족수(R)를 만족하는 응답을 수집 후, 벡터 시계 등을 통해 가장 최신 버전의 데이터를 클라이언트에 반환

Bloom Filter란?

SSTable을 읽기 전에 특정 키가 ‘존재하지 않음’ 을 빠르게 판단해주는 확률적 자료구조
Memtable에 키가 없을 때 수많은 SSTable 파일을 모두 열어보지 않도록 하여 불필요한 디스크 I/O를 줄여줌