카테고리 없음

[System Design] 확장 가능한 키-값 저장소(Key-Value Store) 설계하기

kkyu0718 2026. 2. 1. 23:42

대규모 시스템에서 데이터를 효율적으로 저장하고 조회하기 위한 키-값 저장소의 설계 원칙과 주요 기술들을 정리합니다.

1. 분산 시스템의 기초: CAP 이론

분산 시스템을 설계할 때 반드시 고려해야 하는 세 가지 속성입니다.

  • C (Consistency, 일관성):* 어떤 노드에 접속하든 모든 클라이언트는 항상 같은 데이터를 보아야 합니다.
  • A (Availability, 가용성):* 일부 노드에 장애가 발생하더라도 시스템은 항상 응답을 반환해야 합니다.
  • P (Partition Tolerance, 파티션 감내):* 노드 간 네트워크 장애(파티션)가 발생해도 시스템이 계속 동작해야 합니다.

결론: 네트워크 장애(P)는 피할 수 없으므로, 우리는 CP(일관성 중심) 시스템을 만들 것인지, AP(가용성 중심) 시스템을 만들 것인지 선택해야 합니다.

PACELC 이론 (추가 개념)

파티션 장애 상황(P) 외에도, 정상 상황(Else)일 때 지연 시간(Latency)과 일관성(Consistency) 사이의 절충안을 설명하는 이론입니다.

2. 데이터 분산과 확장: 안정 해시 (Consistent Hashing)

데이터를 여러 서버에 고르게 분산하고, 서버 추가/삭제 시 데이터 이동을 최소화하기 위해 안정 해시를 사용합니다.

  • 가상 노드(Virtual Node): 각 서버의 용량에 따라 가상 노드 수를 조절하여 부하를 균등하게 분산할 수 있습니다.
  • 장점: 시스템 부하에 따라 규모를 자동으로 확장(Auto-scaling)하기 용이합니다.

3. 데이터 일관성과 장애 처리

정족수 합의 (Quorum Consensus)

여러 노드에 복제된 데이터의 일관성을 보장하기 위해 사용합니다.

  • N: 복제본 개수
  • W: 쓰기 성공으로 인정받기 위해 필요한 승인 수
  • R: 읽기 성공으로 인정받기 위해 필요한 승인 수
  • R = 1, W = N: 빠른 읽기
  • R = N, W = 1: 빠른 쓰기
  • W+R > N: 강한 일관성 → 고가용성 보장 못함
  • W+R ≤ N: 강한 일관성이 보장되지 않음

비일관성 해소: 벡터 시계 (Vector Clock)

데이터 변경 시 버전 카운터를 관리하여 데이터 간의 충돌을 감지하고 해결합니다.

각 노드(서버)는 자신만의 카운터를 관리하며, 전체 시스템의 상태를 배열 형태로 유지합니다. 예를 들어 노드가 A, B, C 세 개라면 벡터 시계는 [A: n_1, B: n_2, C: n_3] 형태가 됩니다.

1. 데이터 쓰기: 특정 노드(예: A)가 데이터를 업데이트하면, 벡터 시계에서 자신의 카운터를 1 증가시킵니다. ([A: 1, B: 0, C: 0])

2. 데이터 전달: 이 데이터가 다른 노드로 복제될 때 벡터 시계 정보도 함께 전달됩니다.

3. 충돌 판정 (비교 규칙):

  • 이전/이후 관계: 버전 X의 모든 요소가 버전 Y의 요소보다 작거나 같으면, X는 Y의 이전 버전입니다. (충돌 없음)
  • 충돌(Concurrent): 어떤 요소는 X가 크고, 어떤 요소는 Y가 크다면 두 작업은 동시에 발생한 것으로 간주하여 충돌로 판명합니다
  • 단점: 클라이언트 측의 로직이 복잡해지고, 버전 순서쌍이 빠르게 늘어날 수 있습니다. 순서쌍 임계치를 설정할 수 있지만 정확성이 떨어질 수 있습니다.

장애 감지: 가십 프로토콜 (Gossip Protocol)

분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주합니다. 이때 모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이지만 비효율적입니다.

이때 나온 가십 프로토콜은 중앙 집중형이 아닌 분산형 장애 감지 방식입니다.

가십 프로토콜의 동작 원리

  • 각 노드는 멤버십 목록(membership list)를 유지. 멤버십 목록은 각 멤버 ID와 그 박동 카운터(heartbeat counter) 쌍의 목록
  • 각 노드는 주기적으로 자신의 박동 카운터를 증가시킴
  • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄
  • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
  • 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주

멀티캐스팅 - 비효율적 프로토콜
가십 프로토콜

4. 장애 처리 메커니즘 (Failure Handling)

1) 일시적 장애 처리: 느슨한 정족수와 임시 위탁

네트워크 장애나 특정 서버의 과부하로 인한 짧은 장애 상황에서는 가용성을 높이는 방향으로 대응합니다.

  • 느슨한 정족수 (Sloppy Quorum): 장애 상태인 서버를 무시하고, 가용성을 높이기 위해 건강한 서버들로만 정족수(W, R)를 계산합니다.
  • 단서 후기 임시 위탁 (Hinted Handoff)
    • 장애 서버(A)로 가야 할 쓰기 요청을 다른 건강한 서버(B)가 잠시 대신 맡아 처리합니다.
    • 이때 서버 B는 "이 데이터는 원래 A에게 줘야 함"이라는 **힌트(Hint)를 남겨둡니다.
    • 서버 A가 복구되면, B는 보관 중이던 데이터를 A에게 일괄 전달하여 데이터 일관성을 맞춥니다.

2) 영구적 장애 처리: 반-엔트로피와 머클 트리

서버가 영구적으로 다운되거나 데이터 사본 간의 불일치가 심각할 경우, 사본들을 동기화하는 반-엔트로피(Anti-entropy) 프로토콜을 가동합니다.

  • 머클 트리 (Merkle Tree) 활용: 대용량 데이터 사본 간의 일관성을 탐지할 때, 모든 데이터를 전송하는 것은 매우 비효율적입니다.
  • 작동 방식:
    1. 각 노드는 자신의 데이터를 버킷으로 나누고 해시 트리를 구성합니다.
    2. 두 서버의 루트(Root) 해시를 비교합니다.
    3. 루트 값이 같다면 데이터가 동일한 것이므로 즉시 종료합니다.
    4. 값이 다르다면 자식 노드로 내려가며 해시가 다른 지점(버킷)만 찾아냅니다.
  • 장점: 데이터 총량과 무관하게, 실제로 차이가 나는 부분만 골라 전송하므로 네트워크 전송량을 획기적으로 줄일 수 있습니다.

4. 카산드라 예시

저장소의 성능을 극대화하기 위해 메모리와 디스크를 유기적으로 사용합니다.

쓰기 경로 (Write Path)

  1. Commit Log: 장애 복구를 위해 쓰기 요청을 디스크의 로그 파일에 먼저 기록합니다.
  2. Memtable (Memory Table): 데이터를 메모리에 키 순서대로 정렬하여 저장합니다.
  3. SSTable (Sorted String Table): 메모리가 꽉 차면 정렬된 데이터를 디스크에 파일 형태로 내보냅니다(Flush).

읽기 경로 (Read Path)

  1. Memtable 확인: 메모리에 데이터가 있으면 즉시 반환합니다.
  2. 블룸 필터(Bloom Filter) 검사: 메모리에 없다면, 블룸 필터를 통해 어느 SSTable에 데이터가 있을지(혹은 확실히 없는지) 확인하여 헛걸음을 방지합니다.
  3. Index 및 SSTable 조회: 인덱스를 이용해 SSTable 내 정확한 위치에서 데이터를 가져옵니다.

 

💡 Appendix: LSM-Tree

대규모 시스템 설계에서 "쓰기 성능을 극대화하면서도 읽기 속도를 놓치지 않는" 비결은 무엇일까요? 유기적으로 맞물려 돌아가는 네 가지 핵심 기술을 데이터의 흐름에 따라 정리해 보았습니다.

1. 데이터 저장의 흐름 (Write Path)

데이터가 들어오면 바로 디스크로 가지 않습니다. 디스크는 느리기 때문에 메모리를 거점으로 활용합니다.

  • Memtable (메모리 테이블): 데이터가 들어오면 일단 메모리에 저장합니다. 이때 가장 중요한 점은 키(Key) 순서대로 정렬해서 들고 있다는 것입니다.
  • SSTable (Sorted String Table): 메모리가 꽉 차면, 정렬된 데이터를 통째로 디스크에 던집니다. 이미 정렬되어 있으니 순서대로 쓰기만 하면 되어 매우 빠릅니다. 이 "정렬된 데이터 덩어리"가 바로 SSTable입니다.
  • LSM-Tree: 위와 같이 "메모리에 먼저 쓰고, 나중에 정렬된 파일로 디스크에 내려보내는" 전체적인 구조를 말합니다.

2. 읽기 성능의 구원자, 블룸 필터 (Bloom Filter)

디스크에 SSTable 파일이 수백 개 쌓이면, 내가 찾는 데이터가 어디 있는지 일일이 뒤질 수 없습니다. 이때 '문지기' 역할을 하는 블룸 필터가 등판합니다.

🔍 블룸 필터의 작동 원리: "흔적 남기기"

블룸 필터는 실제 데이터를 저장하는 게 아니라, 비트 배열(0과 1)과 해시 함수를 이용해 데이터의 존재 여부만 빠르게 판단합니다.

  1. 등록: apple을 저장할 때, 여러 해시 함수를 돌려 나온 번호(예: 3, 7, 12번)의 칸을 1로 바꿉니다.
  2. 확인: "apple 있어?"라고 물으면 똑같이 3, 7, 12번 칸이 1인지 확인합니다.
  3. 결과: * 하나라도 0이다? 👉 "절대로 없음" (100% 확실)
  • 모두 1이다? 👉 "있을지도 모름" (긍정 오류 가능성)

왜 "있을지도 모른다"고 하나요?
다른 데이터들의 흔적이 우연히 겹쳐서(3, 7, 12번이 우연히 다 1이 됨) 없는 데이터도 있다고 착각할 수 있기 때문입니다. 하지만 "없다"는 응답은 확실하기 때문에 무거운 디스크 조회를 획기적으로 줄여줍니다.

3. 파일 안의 약도, 인덱스 (Index)

블룸 필터가 "이 파일에 네가 찾는 게 있을지도 몰라"라고 했다면, 이제 진짜 파일 안을 뒤져야 합니다.

  • Index (인덱스): 수 GB에 달하는 SSTable을 처음부터 읽을 순 없겠죠? 파일 뒷부분에 "어떤 키는 파일의 몇 바이트 지점에 있다"라는 약도를 그려둡니다.
  • 데이터가 이미 정렬(Sorted)되어 있으므로, 이 약도를 보고 정확한 위치로 점프해서 데이터를 가져옵니다.

4. 사후 관리, 컴팩션 (Compaction)

SSTable은 한 번 쓰면 수정할 수 없는 '불변' 파일입니다. 데이터가 쌓이면 파일이 너무 많아져 읽기 성능이 떨어지죠.

  • 컴팩션: 백그라운드에서 여러 개의 SSTable을 하나로 합치면서, 오래된 데이터나 삭제된 데이터를 정리하고 새로운 압축 파일을 만드는 과정입니다.

🏃 최종 정리: 데이터 조회 시나리오

여러분이 user:123의 정보를 찾는다면 시스템은 이렇게 움직입니다!

  1. Memtable을 본다: "방금 쓴 데이터인가?" 👉 없네.
  2. 블룸 필터에게 묻는다: "1번 파일에 있니?" 👉 "아니", "2번은?" 👉 "응, 있을걸?"
  3. 인덱스를 본다: "2번 파일 약도를 보니 user:123은 500번 포지션에 있구나!"
  4. SSTable 조회: 2번 파일의 500번 위치에서 데이터를 딱 집어서 반환!

 

저작자표시 (새창열림)