[시스템 디자인] 6장. 키-값 저장소

혀어어언·2025년 9월 29일
nosql스키마리스시스템디자인시스템설계키-값저장소해시테이블
0

[북스터디] 시스템 디자인

목록 보기
8/14

6장. 키-값 저장소(key-value store) 설계

분산 키 - 값 저장소가 가져야 하는 기능과 기능 구현에 이용되는 기술들

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

1. 키 값 저장소란?

1-1. 이론적 정의

  • 데이터를 키(Key)와 값(Value) 쌍으로 관리하는 가장 단순한 형태의 DB 모델
  • 내부적으로 해시 테이블 유사 구조 사용
  • 스키마리스(Schema-less)
  • 값에는 문자열·JSON·Blob 등 다양한 데이터 저장 가능

1-2. 기본 연산

  • PUT(key, value), GET(key), DELETE(key) 등 최소한의 조작 인터페이스

1-3. 성능 특성

  • O(1)에 가까운 조회/쓰기 성능 제공 (메모리 기반 접근, 해시 인덱스 활용)
    • 기본적으로 해시 테이블이나 LSM-Tree 구조를 활용하여 매우 빠른 접근 성능을 보장
  • 분산 환경에서 수평 확장(Scale-Out) 가능
    • Dynamo는 "highly available key-value store"로 설계되었으며, Consistent Hashing을 기반으로 새로운 노드를 추가하거나 제거할 때 전체 데이터를 재분배하지 않고도 수평 확장 가능하도록 설계됨

1-4. 예시

  • Redis: In-memory key-value DB, 다양한 데이터 타입 지원
  • Memcached: 캐싱 중심 단순 Key-Value Store
  • DynamoDB: AWS 관리형 Key-Value + Document DB (밀리초 단위 성능, 자동 샤딩)
  • Cosmos DB: Azure의 글로벌 분산 Key-Value DB API 지원

2. 단일 서버 키-값 저장소 설계

  • 단일 서버 수준에서는 키-값 저장소를 해시 테이블 기반의 빠른 조회·쓰기를 중심으로 설계하면 충분

2-1. 단일 서버 수준에서 다루는 사항들

  • 데이터 모델

    • 단순한 Key → Value 매핑
    • 키는 유일성을 보장해야 하며, 값은 문자열·JSON·바이너리 등 어떤 형태든 저장 가능→ 스키마 유연성(Schema-less)

  • 저장 구조

    • 메모리 기반 해시 테이블(dictionary)을 사용해 평균 O(1) 조회 성능 제공
    • 필요 시 디스크에 주기적 스냅샷(RDB)이나 Append-Only File(AOF)로 내구성 보장

  • 만료/퇴출 정책

    • TTL(Time-To-Live)로 키의 생존 시간을 제한
    • 메모리 부족 시 LRU/LFU/Random 같은 eviction 정책으로 데이터 제거

  • 동시성/원자성

    • 단일 스레드 이벤트 루프 또는 락 분할(shard) 기반 멀티스레딩

  • 단일 서버에서는 빠른 접근(O(1))·TTL/eviction·내구성 옵션까지 갖추면 실무적으로 충분

3. 분산 서버 키-값 저장소 설계

3-1. 분산 시스템 설계 시 알아둬야 하는 개념들

1) CAP 정리

  • Eric Brewer (2000) 제안, 이후 Gilbert & Lynch(2002)에 의해 정리된 이론
  • 분산 시스템에서는 Consistency(일관성), Availability(가용성), Partition Tolerance(분할 내성) 세 가지 속성을 동시에 모두 만족할 수 없다는 이론
요구사항의미
Consistency (일관성)모든 노드가 같은 시점에 동일한 데이터를 보여준다
Availability (가용성)모든 요청에 대해 항상 응답을 돌려줄 수 있다 (성공/실패 여부 무관)
Partition Tolerance (분할 내성)네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 뜻
1-1) 핵심 포인트
  • 네트워크 분할 가능성을 완전히 배제할 수 없기 때문에 P(Partition Tolerance)는 분산 시스템에서는 사실상 필수
  • 따라서 실제 선택은 AP vs CP의 문제
  • 즉, 네트워크 파티션이 발생했을 때, 시스템은 C(일관성)과 A(가용성) 중 하나를 희생해야 함
1-2) CAP 정리에 따른 키-값 저장소 분류
구분AP 시스템CP 시스템
보장가용성 + 분할 내성일관성 + 분할 내성
희생강한 일관성가용성
허용 일관성 수준최종 일관성(Eventual Consistency)강한 일관성(Strong Consistency)
장점고가용성, 글로벌 서비스에 유리데이터 무결성 보장, 트랜잭션 안전
단점일시적 불일치 허용서비스 중단 가능
대표 사례글로벌 소셜 네트워크, 메시징 서비스, 검색, 로그 수집금융 거래, 주문/결제, 분산 락/메타데이터, 인증
대표 시스템DynamoDB, Cassandra, RiakZooKeeper, HBase, Etcd

3-2. 시스템 컴포넌트(feat. Dynamo, Cassandra, BigTable)

1) 데이터 파티션

1-1) 데이터 파티셔닝에서 고려할 점
  • 데이터의 고른 분산
  • 노드 추가/삭제 시 데이터의 이동 최소화
1-2) 안정 해시를 사용한 파티셔닝의 장점
  • 규모 확장 자동화(automatic scaling)
  • 다양성(heterogeneity): 각 서버의 용량에 맞게 가상노드 수 조정 가능

2) 데이터 다중화

  • 높은 가용성과 안정성 확보를 위해 데이터를 N개 서버에 비동기적으로 다중화

3) 데이터 일관성

3-1) 일관성과 관련된 주요 프로토콜
프로토콜개념 설명대표 사례
2PC (Two-Phase Commit)Coordinator가 모든 참여 노드에 Commit 가능 여부를 묻고,
모두 동의하면 Commit, 아니면 Abort		전통적 RDB, 금융/ERP 시스템
PaxosProposer-Acceptor 구조에서 다수 노드가 단일 값에 합의하도록 보장
합의 알고리즘의 고전적 표준		Google Chubby, Megastore
Quorum-based읽기/쓰기 요청에서 다수파 응답을 요구하여 일관성 확보
R+W > N 규칙으로 CAP 트레이드오프 조정 가능		Cassandra, DynamoDB
RaftPaxos를 단순화한 합의 알고리즘
Leader 기반 로그 복제를 통해 분산 노드 간 일관성 유지.		etcd, Consul, CockroachDB, Kubernetes
CRDT (Conflict-free Replicated Data Types)수학적 성질을 가진 데이터 구조로 병합 시 항상 동일 결과
네트워크 분할이나 동시성 환경에서도 충돌 없는 최종 일관성 제공		Redis CRDT, Riak, Google Docs

  • 참고: Tunable Consistency란?

    • 정의: 분산 데이터베이스에서 읽기(Read)와 쓰기(Write) 연산 시 필요한 복제본(Replica)의 수를 조정하여, 일관성과 가용성 사이의 균형을 사용자가 선택할 수 있는 모델

    • 핵심 공식:

      R + W > N
      • N: 전체 복제본 수
      • R: 읽기에 필요한 복제본 수
      • W: 쓰기에 필요한 복제본 수

    • 특징:

      • 유연성: 애플리케이션의 요구에 따라 “일관성 우선(CP)” 또는 “가용성 우선(AP)”으로 운영 가능.
      • 대표 사례: Cassandra, Amazon DynamoDB → 클라이언트가 Consistency Level을 지정 가능 (ONE, QUORUM, ALL 등).
3-2) 일관성모델
모델설명
강한 일관성(strong consistency)모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
약한 일관성(weak consistency)
최종 일관성(eventual consistency)약한 일관성의 한 형태
갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델
3-3) 비일관성 해소 기법
예방 기법
  • 비일관성 발생 자체를 막음 (합의, 쿼럼, 동기 복제)
    • 장점: 데이터 무결성 보장
    • 단점: 지연(latency), 성능 비용
사후 해결 기법
  • 일관성 깨짐을 허용하고, 나중에 맞춤(Repair, Vector Clocks, CRDT, Anti-Entropy)
    • 장점: 확장성과 가용성에 유리
    • 단점: 충돌 처리 복잡, 사용자 체감 일관성 저하
벡터 클락 (Vector Clock)

  • 개념

    • 버저닝의 확장 기법
    • 단순 타임스탬프(하나의 시간값) 대신, 각 노드별 버전 정보를 벡터 형태로 관리
    • 즉, 데이터 변경 이력이 다차원 벡터로 기록되어, 어떤 노드에서 어떤 시점에 변경이 발생했는지 알 수 있음

  • 동작 방식

    1. 각 노드가 자신의 카운터를 유지 (예: Node A=3, Node B=5)
    2. 데이터 변경 시 해당 노드의 카운터를 증가
    3. 변경 데이터를 다른 노드에 전송할 때 벡터 클락도 함께 전송
    4. 수신한 노드는 자신이 가진 벡터와 비교하여 충돌 여부를 판정

  • 충돌 판정

    • 완전히 포함: (A:2, B:1) vs (A:3, B:1) → 후자가 최신.
    • 교차: (A:3, B:1) vs (A:2, B:2) → 어느 쪽이 최신인지 판단 불가 → 충돌 발생.

  • 단점

    • 벡터 길이가 노드 수에 비례해 커짐 (확장성 문제)
    • 충돌을 탐지는 하지만, 최종 해결(Resolution) 은 애플리케이션 로직이 필요

4) 장애 처리

4-1) 장애 감지(failure detection) 기법
  • 가십 프로토콜 - 분산형 장애 감지 솔루션
    • 각 노드는 멤버십 목록 유지 (멤버 ID + 박동 카운터(heartbeat counter) 쌍)
    • 각 노드는 주기적으로 자신의 박동 카운터를 증가 시킴
    • 무작위로 선정된 다른 노드들에게 자신의 멤버십 목록(박동 카운터 포함)을 전송
    • 수신한 노드는 더 큰 값의 박동 카운터가 있으면 자신의 멤버십 목록을 갱신
    • 특정 멤버의 박동 카운터가 일정 시간 동안 갱신되지 않으면 장애(offline) 로 판정
4-2) 장애 해소(failure resolution)
일시적 장애 처리
  • 단서 후 임시 위탁 기법(hinted handoff)
    • 장애 노드가 쓰기를 받을 수 없을 때, 다른 노드가 대신 데이터를 저장
    • 장애 노드가 복구하면, 해당 데이터를 위탁 노드에서 넘겨받아 동기화
    • Dynamo, Cassandra에서 활용 → 일시적 네트워크 불안정에 효과적
영구 장애 처리
  • 반-엔트로피(anti-entropy) 프로토콜
    • 장애 노드가 장시간 복구되지 않으면 다른 노드 간 사본 비교 및 동기화 필요
    • 단순 전체 복사 대신, Merkle Tree 같은 자료구조로 차이를 효율적으로 비교
    • Gossip 기반 동기화와 함께 사용 가능 → Eventually Consistency 달성

5) 시스템 아키텍처 다이어그램(Cassandra 참고)

5-1) 쓰기경로
  1. 클라이언트 → 노드: 쓰기 요청
  2. Commit Log: 먼저 디스크에 Append → 장애 시 복구 가능
  3. Memtable: 메모리상에 데이터 기록 (쓰기 성능 향상)
  4. Flush: Memtable이 가득 차면 SSTable로 디스크에 영구 저장
5-2) 읽기 경로
  1. 클라이언트 → 노드: 읽기 요청
  2. Memtable 조회: 메모리에서 최신 데이터 확인
  3. Bloom Filter: 해당 키가 SSTable에 있는지 빠르게 확인
  4. Partition Index: SSTable 내 위치 확인
  5. SSTable 조회 후 병합: 여러 SSTable에서 데이터 가져와 병합
  6. 응답 반환: 최종 결과를 클라이언트에게 전달

4. 레퍼런스

profile
혀어어언
이전 포스트

[시스템 디자인] 5장. 안정 해시 설계

다음 포스트

[시스템 디자인] 7장. 분산 시스템을 위한 유일 ID 생성기 설계

0개의 댓글