6. 키-값 저장소 설계

들어가며

• key-value database

  • non relational database

  • e.g. Amazon dynamo, memcached, Redis...

문제 이해 및 설계 범위 확장

• 키-값 쌍의 크기는 10KB 이하이다.

  • 어느 정도일까?

  • 평균적으로 1-5KB

• 큰 데이터를 저장할 수 있어야 한다

  • e.g. 수십 TB ~ PB

• 높은 가용성을 제공해야 한다

  • 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다

  • e.g. 99.9%

• 높은 규모 확장성을 제공해야 한다

  • 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다

• 데이터 일관성 수준은 조정이 가능해야 한다

  • C(consistency), A(Availability) Trade off 조절

• 응답 지연시간(latency) 이 짧아야 한다

단일 서버

• 한 대의 서버만 이용

• 키-값 쌍 전부를 해시 테이블에 저장하는 것

• 빠르지만, 모든 데이터를 메모리에 두는 것은 불가능함.

  • 이를 위해 data compression, 자주 사용하는 데이터만 메모리에 올려두고, 나머지는 디스크에 저장하는 방법

• 그래도 한계가 올 것

분산 키-값 저장소

• CAP

  • Consistency

    • 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야한다.

  • Availability

    • 클라이언트는 일부 노트에 장애가 발생했더라도, 항상 응답을 받을 수 있어야한다.

  • Partition tolerance

    • 두 노드 사이에 통신 장애가 발생했더라도, 시스템은 계속 동작해야한다.

![[Pasted image 20250817151259.png]]

• 3가지를 모두 달성하는 시스템은 존재 불가

• CP -> 데이터 일관성, 파티션 감내 지원, 가용성 희생

• AP -> 가용성, 파티션 감내 지원, 일관성 희생

• CA -> 일관성, 가용성 지원, 파티션 감내 희생

  • 통상적으로 네트워크 장애는 피할 수 없다.

  • 그러므로 파티션 문제는 감내할 수 있도록 설게되어야함

  • 그러므로 CA만 지원하는 시스템은 실세계에![[Pasted image 20250817151259.png]] 없음.

![[Pasted image 20250817151831.png]]

• n3 node에서 장애, n1, n2 노드와는 통신할 수 없는 상태

  • 즉 n1, n2 에서 기록한 데이터가 n3에 전달되지 않고,

  • n3에 기록되었으나, n1, n2 로 전달되지 않는 데이터도 있을 수 있음.

• 이 상황에서 일관성을 선택한다면?

  • n1, n2 에서 쓰기 연산을 중단시켜야한다.

  • 이럴 경우 가용성은 깨진다.

  • e.g. 은행권 시스템

• 가용성을 선택한다면?

  • 일단 읽기 연산을 허용한다.

  • n1, n2 에 쓰기 연산을 허용하고,

  • 파티션 문제가 해결되면 n1, n2 의 새로운 데이터가 n3에 전송될 것

시스템 컴포넌트

• 데이터 파티션

• 데이터 다중화(replication)

• 일관성 (consistency)

• 일관성 불일치 해소(inconsistency resolution)

• 장애 처리

• 시스템 아키텍처 다이어그램

• 쓰기 경로(write path)

• 읽기 경로(read path)

데이터 파티션

• 파티션을 나눌 때 가장 중요한 것 2가지

  • 데이터를 여러 서버에 고르게 분산할 수 있는가?

  • 노드가 추가되거나, 삭제 될때 데이터의 이동을 최소화할 수 있는가?

• Consistency Hashing

• Virtual nodes를 통해 균등한 부하 분산 추가할 수 있음.

[물리 노드만 사용]
Ring: A(10°)--B(20°)--C(300°)
      └─작은구간─┘    └─큰구간─┘
      
→ C가 전체의 80% 처리!

[Virtual Nodes 사용]
Ring에 각 노드를 여러 개 배치:
A-1, B-1, C-1, A-2, B-2, C-2, A-3, B-3, C-3...

→ 각 노드가 링 전체에 고르게 분포
→ 표준편차 3% 이하로 균등 분산

• 노드 추가 제거시 최소한 데이터 이동 평균(평균 K/N개의 키만 재배치, K=전체 키, N=노드 수)

[해시 링 구조]

        0°/360°
          |
    NodeA(45°)
          |
    Key1(60°) → NodeB로
          |
    NodeB(120°)
          |
    Key2(150°) → NodeC로
          |
    NodeC(240°)
          |
    Key3(300°) → NodeA로 (순환)

[노드 추가 시]
NodeD를 180°에 추가
→ Key2만 NodeC에서 NodeD로 이동
→ 나머지는 그대로!

• 노드를 추가하면 그 구간의 데이터만 이동하면 되니까, 평균적으로 전체 데이터의 1/N만 이동

데이터 다중화

• 높은 가용성, 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동적으로 다중화(replication) 할 필요 있음.

  • N은 튜닝 가능한 값

![[Pasted image 20250817153456.png]]

• N = 3 이라면, 시계방향으로 돌면서 만난 3가지 노드 s1, s2, s3 에 저장된다.

• 가상 노드를 사용하면 실제 물리서버의 갯수는 N보다 작아질 수 있으므로, 노드를 선택할 때 같은 물리서버를 중복으로 선택하지 않도록 해야함

데이터 일관성

• 복제 전략: Quorum 기반 복제

  • N-W-R 모델 적용:

    • N = 3 (복제본 수)

    • W = 2 (쓰기 정족수, 2개 노드에 쓰기 성공해야 완료)

    • R = 2 (읽기 정족수, 2개 노드에서 읽어야 완료)

      • Strong Consistency

  • 이유:

    • W + R > N (2+2 > 3)이므로 강한 일관성 보장

    • 필요시 R=1로 조정하여 가용성 우선 모드 가능

    • 1개 노드 장애 시에도 읽기/쓰기 가능

• 이 W+R > N 전략의 핵심은 '쓰기 집합과 읽기 집합이 반드시 겹친다'

[초기 상태 - 모든 노드가 v1 가지고 있음]
Node A: v1
Node B: v1  
Node C: v1

[쓰기 발생 - v2로 업데이트, W=2]
Client → Write v2
         ↓
Node A: v2 ✓ (성공)
Node B: v2 ✓ (성공)
Node C: v1   (아직 전파 안됨)
→ 2개 노드 쓰기 성공, 응답 반환

[이후 읽기 시나리오들, R=2]

Case 1: A,B에서 읽기
Node A: v2 ┐
Node B: v2 ┘→ 둘 다 v2 → v2 반환 ✓

Case 2: A,C에서 읽기  
Node A: v2 ┐
Node C: v1 ┘→ v2 > v1 → v2 반환 ✓

Case 3: B,C에서 읽기
Node B: v2 ┐
Node C: v1 ┘→ v2 > v1 → v2 반환 ✓

• 모든 경우에 최신 값 v2를 읽게 됨.

• 정리해보면

[W+R > N인 경우: W=2, R=2, N=3]

쓰기 집합: {A, B}
가능한 읽기 집합: {A,B}, {A,C}, {B,C}

→ 모든 읽기 집합이 쓰기 집합과 최소 1개 겹침!
→ 항상 최신 데이터를 가진 노드를 포함

[W+R ≤ N인 경우: W=1, R=1, N=3]

쓰기 집합: {A}
가능한 읽기 집합: {A}, {B}, {C}

→ B나 C에서 읽으면 구버전 읽을 수 있음!
→ 일관성 보장 안됨

• Strong Consistency (강한 일관성)

  • W=2, R=2, N=3 (W+KaR=4 > N=3)

  • 장점: 강한 일관성

  • 단점: 2개 노드 응답 필요 → 느림

• Weak Consistency (약한 일관성)

• Eventual Consistency (최종 일관성)

  • W=1, R=1, N=3 (W+R=2 < N=3)

  • 장점: 빠른 응답

  • 단점: 일시적 불일관성 가능

• 사용 예시

  • 금융 데이터: W=2, R=2 (일관성 우선)

  • 로그 데이터: W=1, R=1 (성능 우선)

  • 일반 서비스: W=2, R=1 (쓰기는 안전하게, 읽기는 빠르게)

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

• 버저닝 (versioning)

  • 데이터를 변경할 때 마다 해당 데이터의 새로운 버전을 만드는 것.

  • 따라서 각 버전의 데이터는 변경 불가능 (immutable)

• 벡터 시계 (vector clock)

  • '서버, 버전' 의 순서쌍을 데이터에 매단 것

[초기 상태]
Value: "v0"
VClock: {A:0, B:0, C:0}

[Client1이 Node A에 쓰기]
Value: "v1"  
VClock: {A:1, B:0, C:0}

[Client2가 Node B에서 읽고 수정]
Read: "v1" {A:1, B:0, C:0}
Write: "v2" {A:1, B:1, C:0}

[Client3가 Node A에서 v1 읽고 동시 수정]
Read: "v1" {A:1, B:0, C:0}
Write: "v3" {A:2, B:0, C:0}

[충돌 감지]
v2: {A:1, B:1, C:0}
v3: {A:2, B:0, C:0}

→ v2가 v3보다 크지도, 작지도 않음
→ 동시 쓰기(Sibling) 발생!

• LWW (Last Write Win)

[각 쓰기에 타임스탬프 추가]

Write 1: {
  value: "홍길동",
  timestamp: 1000  
}

Write 2: {
  value: "김철수",
  timestamp: 1001
}

→ 1001 > 1000 이므로 "김철수" 선택

• 장점

  • 구현 간단

  • 자동 충돌 해결

  • 저장 공간 적음

• 단점

  • 시계 동기화 이슈

  • 데이터 손실 가능성

  • 진짜 마지막이 아닐 수 있음

장애 감지

• gossip protocool

  • decentralized failure detection, 중앙 서버 없이 각 노드가 독립적으로 장애를 감지하는 방법

  • A 노드 -> B 노드 (랜덤), A 노드가 가지고 있는 heartbeat counter list를 보냄

  • B 노드는 list를 기반으로 최신 값으로 갱신해야함.

  • if 갱신하지 않으면? B node는 장애 상태이다!

[각 노드가 관리하는 정보]

Node A의 Membership List:
{
  NodeA: {heartbeat: 100, timestamp: t1},
  NodeB: {heartbeat: 95,  timestamp: t2},
  NodeC: {heartbeat: 97,  timestamp: t3},
  NodeD: {heartbeat: 50,  timestamp: t4} ← 오래됨!
}

매 초마다:
1. 자신의 heartbeat 증가
2. 랜덤 노드 선택해서 리스트 교환
3. 더 최신 정보로 업데이트
4. Timeout(15초) 지난 노드 → Suspected (e.g. Node D, 마지막 업데이트 시간이 15초나 되었네?)
5. 30초 지나면 → Dead

[감염 모델로 분석]

Round 0: Node D 죽음
Round 1: 1개 노드가 감지
Round 2: 2개 노드가 알게됨
Round 3: 4개 노드가 알게됨
...
Round log(N): 모든 노드가 알게됨

1000개 노드 → 10 라운드면 전파 완료!

• 일시적 장애 처리

  • strict quorum : 장애가 발생한 순산 읽기 쓰기 연산 금지

  • sloppy quorum : 가용성을 높이는 방향.

    • 즉 쓰기 연산 수행할 W 개의 건강한 노드

    • 읽기 연산을 수행할 R개의 건강한 노드를 고르는 방향.

    • 선택에서 장애 노드는 무시

    • 장애노드로 가는 요청들은 다른 서버가 처리.

      • hinted handoff 기법.

        • 임시로 쓰기 연산을 처리한 서버가 그에 대한 힌트를 남겨서, 장애 회복 노드가 추후 인지할 수 있도록 하는 방법

• Hinted Handoff

[기본 아이디어]

"너한테 줄 편지인데 네가 없어서 
 내가 들고 있다가 돌아오면 줄게"

정상 상황:
Client → Node B (Primary): 데이터 저장

Node B 장애 시:
Client → Node D (임시): 데이터 + "B한테 줄 것" 메모
         ↓
      B 복구 시
         ↓
Node D → Node B: "네가 없을 때 받은 데이터야"

• 프로세스

[정상 상황 - Preference List 사용]

Key: "user:123"
Preference List: [B, C, D]  (B가 primary)

쓰기 요청:
Client → B: "user:123" = "홍길동" ✓
      → C: 복제본 ✓
      → D: 복제본 ✓

[Node B 장애 시]

Preference List: [B(죽음), C, D, E]

쓰기 요청:
Client → C: "user:123" = "김철수" ✓
      → D: 복제본 ✓
      → E: 복제본 + Hint ✓

E가 저장하는 내용:
{
  hint: {
    target_node: "B",
    original_key: "user:123"
  },
  data: {
    key: "user:123",
    value: "김철수",
    timestamp: 1234567890,
    version: 2
  }
}

[Handoff 시나리오]

Timeline:
T0: Node B 다운
T1: 쓰기 요청 → E가 hint와 함께 저장
T2: 추가 쓰기들 → E에 계속 쌓임
T3: Node B 복구
T4: E가 B 복구 감지
T5: E → B: Hint된 데이터 전송 시작
T6: 전송 완료, Hint 삭제

E의 Hint Storage:
Before: [(B, key1), (B, key2), (B, key3)]
After: [] (모두 전달 완료)

• 장점

  • 고가용성 달성

    • 99.9% → 99.99% 가용성

    • Hinted는 1개의 노드만 살아있어도 됨.

  • 일시적 장애 투명성

    • 클라이언트는 장애를 모르고,

    • 자동 복구되며,

    • 개발자 (운영자) 의 개입이 최소화 된다.

• 단점

  • Hint 폭증

    • 대량 장애 시, 스토리지가 부족해질 수 있음.

  • 읽기 일관성

  • 복구 부하

  • Hint 만료

• 영구 장애 처리

  • anti-entropy

    • 사본들을 동기화.

    • 사본들을 비교하여 최신 버전으로 갱신

    • 즉 주기적으로 데이터를 비교하고 동기화 하는 과정

• Merkle Tree 기반 동기화

• 구조

[데이터를 트리로 해싱]

        Root Hash
        /        \
    Hash01      Hash23
    /    \      /    \
 Hash0  Hash1 Hash2  Hash3
   |      |     |      |
 Data0  Data1 Data2  Data3

각 노드: 자식들의 해시를 다시 해시
Root: 전체 데이터셋의 지문(fingerprint)

• 비교 과정

[Node A와 Node B 동기화]

Step 1: Root 비교
Node A Root: 0xABCD
Node B Root: 0xABCD
→ 같으면 종료 (데이터 일치!)

Step 2: Root가 다르면 자식 비교
Node A: [Hash01: 0x1234, Hash23: 0x5678]
Node B: [Hash01: 0x1234, Hash23: 0x9999]
→ Hash23 영역만 불일치!

Step 3: 불일치 영역만 깊이 탐색
Hash23 하위 비교...
→ Data3만 다름 발견

Step 4: 최소 데이터만 전송
Node A → Node B: Data3만 전송