[대규모 시스템 설계 스터디] 6장 정리

김연준·2026년 7월 30일

[대규모 시스템 설계 스터디]

목록 보기

6/13

키-값 저장소

1. 키-값 저장소란

고유한 키를 이용해 값을 저장하고 조회하는 비관계형 데이터 저장소
키는 저장된 값을 식별하는 역할 수행
키는 일반 문자열이나 해시값 등의 형태로 구성 가능
저장소는 일반적으로 값의 내부 구조를 직접 해석하지 않음
제품이 허용하는 크기와 형식 안에서 문자열, 객체, 바이너리 데이터 등 다양한 값 저장 가능

기본 API

`put(key, value)`

키와 값의 쌍을 저장소에 저장
동일한 키가 이미 존재하면 기존 값을 새로운 값으로 갱신할 수 있음

`get(key)`

입력한 키에 대응하는 값 조회
해당 키가 없으면 값이 존재하지 않음을 반환

2. 대표적인 키-값 저장소

2.1 Amazon Dynamo

Amazon이 내부 서비스의 높은 가용성을 위해 설계한 분산 키-값 저장소
2007년 논문을 통해 설계 원리 공개
외부 고객에게 직접 제공되는 AWS 서비스가 아니라 Amazon 내부 시스템의 설계 사례
일부 서버와 네트워크에 장애가 발생해도 쓰기 요청을 가능한 한 계속 처리하는 것을 중요하게 설계
강한 일관성보다 높은 가용성과 최종 일관성을 우선
다음과 같은 분산 시스템 기법 활용
- 안정 해시
- 데이터 복제
- 정족수(읽기나 쓰기를 성공으로 인정하기 위해 필요한 최소 서버 수)
- 벡터 시계
- 가십 프로토콜
- 단서 후 임시 위탁
- 머클 트리

Amazon Dynamo는 Amazon의 핵심 서비스에 항상 사용 가능한 저장 기능을 제공하기 위해 설계된 고가용성 키-값 저장소임.

2.2 Redis

메모리를 중심으로 동작하는 고성능 데이터 저장소
문자열뿐 아니라 다양한 자료구조 제공
- 리스트
- 집합
- 정렬 집합
- 해시
캐시 외에도 다음 용도로 활용 가능
- 세션 저장
- 순위표
- 분산 락
- 메시지 전달
- 실시간 카운터
설정에 따라 메모리의 데이터를 디스크에 저장하여 장애 후 복구 가능

2.3 Memcached

메모리에 데이터를 저장하는 단순한 분산 캐시 시스템
키를 이용한 값의 저장과 조회 기능에 집중
Redis보다 제공 기능과 자료구조가 단순함
기본적으로 데이터 영속성을 제공하지 않음
서버가 재시작되거나 캐시 항목이 제거되면 데이터가 사라질 수 있음

2.4 Amazon Dynamo와 DynamoDB의 차이

Amazon Dynamo
- Amazon 내부 서비스의 높은 가용성을 위해 개발된 분산 키-값 저장소
- 2007년 논문을 통해 설계 원리 공개
- 일반 사용자가 직접 사용할 수 있는 AWS 서비스는 아님
- 안정 해시, 벡터 시계, 가십 프로토콜, 단서 후 임시 위탁, 머클 트리 등의 기법 활용
- 강한 일관성보다 높은 가용성과 최종 일관성을 우선한 설계
Amazon DynamoDB
- AWS가 고객에게 제공하는 완전관리형 서버리스 NoSQL 데이터베이스
- 사용자가 AWS 콘솔, CLI, SDK 및 API를 통해 직접 사용 가능
- 서버 구성, 확장, 장애 대응 등의 인프라 운영을 AWS가 담당
- Dynamo의 설계 원칙에서 영향을 받았지만 Dynamo와 동일한 시스템은 아님
- 강력한 일관된 읽기, 트랜잭션, 보조 인덱스, 백업 등 상용 데이터베이스 기능 제공

즉, Amazon Dynamo는 분산 키-값 저장소의 설계 사례이고, DynamoDB는 해당 설계 철학의 영향을 받아 만들어진 실제 AWS 데이터베이스 서비스임.

3. 설계 목표

이번 장에서 설계하는 분산 키-값 저장소의 요구사항은 다음과 같음.

데이터 크기

개별 키-값 쌍의 크기는 10KB 이하
시스템 전체로는 대규모 데이터 저장 가능

높은 가용성

일부 서버에 장애가 발생하더라도 가능한 한 빠르게 응답
장애 노드 때문에 전체 시스템이 중단되지 않도록 설계

높은 규모 확장성

데이터와 요청량이 증가하면 서버 추가 가능
서버 추가와 제거 과정 자동화
서버 수 변경 시 데이터 이동량 최소화

조정 가능한 일관성

서비스 요구사항에 따라 읽기·쓰기 일관성 수준 조정 가능
강한 일관성과 높은 가용성 사이에서 적절한 절충 필요

짧은 응답 지연 시간

읽기와 쓰기 요청을 빠르게 처리
디스크 접근과 네트워크 통신 비용 최소화

4. 단일 서버 키-값 저장소

4.1 기본 구조

모든 키-값 쌍을 한 서버의 메모리 해시 테이블에 저장
키를 해싱하여 값의 위치를 빠르게 탐색
단순한 구조로 빠른 읽기와 쓰기 가능

4.2 개선 방법

데이터 압축을 통한 메모리 사용량 감소
자주 사용하는 데이터만 메모리에 저장
자주 사용하지 않는 데이터는 디스크에 저장

4.3 한계

메모리 기반 해시 테이블 자체는 빠름
그러나 한 서버의 메모리 용량과 처리 능력에는 한계 존재
데이터와 요청량이 증가하면 단일 서버만으로 처리하기 어려움
서버 장애 시 전체 저장소가 중단되는 단일 장애 지점 발생
대규모 시스템에서는 여러 서버에 데이터를 분산하는 구조 필요

분산 키-값 저장소

5. CAP 정리

CAP는 다음 세 가지 속성에 관한 분산 시스템의 제약을 설명함.

일관성
가용성
파티션 감내

5.1 일관성

어떤 노드에 접속하더라도 동일한 데이터를 보게 되는 성질
완료된 최신 쓰기가 이후 읽기에 반영되어야 함
복제본마다 서로 다른 값을 반환하지 않도록 보장

5.2 가용성

일부 노드에 장애가 발생하더라도 요청에 응답하는 성질
모든 정상적인 요청이 성공 또는 실패 여부를 포함한 응답을 받을 수 있어야 함

5.3 파티션 감내

노드 사이의 네트워크 통신이 끊겨도 시스템이 계속 동작하는 성질
파티션은 일부 노드 그룹끼리 통신할 수 없는 네트워크 장애를 의미

5.4 CAP 정리의 의미

단순히 세 가지 중 항상 두 가지만 고르는 문제는 아님
네트워크가 정상일 때는 일관성과 가용성을 모두 제공할 수 있음
네트워크 파티션이 발생하면 일관성과 가용성을 동시에 완전하게 보장하기 어려움
현실적인 분산 시스템에서는 네트워크 장애를 피할 수 없으므로 파티션 감내 필요
파티션 발생 시 일관성과 가용성 가운데 어떤 속성을 우선할지 결정 필요

5.5 CAP 예시

서버 A와 서버 B가 동일한 데이터의 사본을 가지고 있다고 가정함.

서버 A와 서버 B 사이의 네트워크 단절
클라이언트가 서버 A의 데이터 변경
서버 A가 변경 내용을 서버 B에 전달하지 못함

일관성을 우선하는 경우

서버 B는 자신이 가진 값이 최신인지 확인 불가
오래된 값을 반환하지 않기 위해 읽기 또는 쓰기 요청 거부
일관성을 유지하는 대신 가용성 일부 포기

가용성을 우선하는 경우

서버 B가 자신이 가진 값을 계속 반환
사용자는 응답을 받을 수 있음
서버 A의 최신 값과 다른 값을 받을 가능성 존재
가용성을 유지하는 대신 일시적으로 일관성 포기

시스템 컴포넌트

6. 데이터 파티션

6.1 파티션이 필요한 이유

대규모 데이터 전체를 한 서버에 저장하기 어려움
전체 데이터를 여러 개의 작은 파티션으로 나누어 여러 서버에 분산
서버별 저장 공간과 처리 부하를 고르게 분배할 필요

6.2 파티션 설계 시 고려 사항

데이터를 여러 서버에 고르게 분산할 수 있어야 함
서버가 추가되거나 제거될 때 데이터 이동량을 최소화해야 함
서버별 성능 차이를 데이터 분산에 반영할 수 있어야 함

6.3 안정 해시 활용

서버와 키를 동일한 해시 링 위에 배치
키의 위치에서 시계 방향으로 처음 만나는 서버가 해당 키 담당
서버가 추가되거나 제거되어도 영향받는 일부 키만 이동
전체 키를 다시 배치하는 문제 방지

안정 해시의 이점

자동적인 규모 확장에 유리
서버 추가·제거 시 데이터 이동 최소화
성능이 좋은 서버에 더 많은 가상 노드를 배치하여 서버 성능 차이 반영 가능

7. 데이터 복제

7.1 복제가 필요한 이유

하나의 서버에만 데이터를 저장하면 서버 장애 시 데이터 접근 불가
높은 가용성과 데이터 안정성을 위해 여러 서버에 동일한 데이터 사본 저장

7.2 복제 계수

N: 동일한 데이터를 저장할 복제본의 개수
예를 들어 N=3이면 하나의 데이터를 서로 다른 세 서버에 저장

7.3 복제 서버 선택

키의 위치에서 시계 방향으로 탐색
처음 만나는 서로 다른 물리 서버 N개에 데이터 저장
가상 노드를 사용하는 경우 동일한 물리 서버를 중복 선택하지 않도록 주의

7.4 복제 방식

쓰기 요청이 들어오면 여러 복제본에 데이터 전달
클라이언트는 그중 W개의 서버가 성공을 응답하면 쓰기 성공으로 판단 가능
즉시 응답하지 못한 나머지 복제본은 이후 비동기적으로 동기화 가능

8. 정족수와 데이터 일관성

복제된 데이터는 여러 서버에 저장되므로 읽기와 쓰기 과정에서 적절한 동기화 필요.

8.1 정족수 인자

N

데이터 사본의 전체 개수

W

쓰기 성공에 필요한 서버 응답 수
최소 W개의 복제본이 쓰기 성공을 응답해야 클라이언트에게 성공 반환

R

읽기 성공에 필요한 서버 응답 수
최소 R개의 복제본으로부터 데이터를 읽어 결과 결정

8.2 정족수 설정 예시

`R=1, W=N`

모든 복제본에 쓰기 완료 후 성공 처리
읽기는 하나의 복제본만 확인
읽기 속도에 유리
쓰기 지연 시간과 장애 민감도 증가 가능

`W=1, R=N`

하나의 복제본만 쓰기 성공해도 성공 처리
읽을 때 모든 복제본 확인
쓰기 속도와 가용성에 유리
읽기 비용 증가

`R+W>N`

읽기 정족수와 쓰기 정족수가 최소 한 복제본에서 겹침
최근 쓰기에 참여한 복제본이 읽기 대상에 포함될 가능성 확보
적절한 버전 비교와 충돌 처리 기능을 함께 사용하면 일관성 확보에 유리

`R+W≤N`

읽기 대상과 쓰기 대상이 전혀 겹치지 않을 수 있음
최신 쓰기를 보지 못하고 오래된 값을 반환할 가능성 증가

8.3 정족수 조건의 한계

R+W>N이라는 조건만으로 모든 시스템에서 강한 일관성이 자동 보장되는 것은 아님
다음 요소도 함께 고려해야 함
- 복제본 선택 방식
- 버전 비교
- 동시 쓰기 처리
- 장애 시 대체 노드를 사용하는 느슨한 정족수
- 읽기 복구
- 쓰기 순서 보장

Amazon Dynamo는 높은 가용성을 우선하므로 정족수, 버전 관리 및 비동기 복구를 사용하면서도 최종 일관성 모델을 채택함.

9. 일관성 모델

9.1 강한 일관성

읽기 요청에 완료된 최신 쓰기 결과 반환
클라이언트가 오래된 데이터를 보지 않도록 보장
읽기와 쓰기의 순서를 조정해야 함
합의, 리더 또는 정족수 등의 동기화 과정 필요
네트워크 장애 시 요청을 거부할 수 있어 가용성 저하 가능
추가 동기화 때문에 응답 지연 시간이 증가할 수 있음

9.2 약한 일관성

읽기 요청이 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
복제본 동기화가 끝나기 전에 오래된 값 조회 가능
강한 일관성보다 높은 가용성과 낮은 응답 지연 시간 제공 가능

9.3 최종 일관성

약한 일관성의 한 형태
새로운 갱신이 더 이상 발생하지 않으면 모든 복제본이 결국 같은 값으로 수렴
짧은 시간 동안 서로 다른 복제본이 다른 값을 가질 수 있음
높은 가용성과 낮은 지연 시간이 중요한 시스템에 적합
Amazon Dynamo가 채택한 일관성 모델

9.4 우리가 만들 시스템에서는..?

선착순 경품 지급
혹은 정확히 100번째 요청 판별

이러한 기능에는 단순히 최신 값을 읽는 것뿐 아니라 다음 기능도 필요함.

강한 일관성
원자적 카운터 연산
트랜잭션 또는 동시성 제어

10. 데이터 버저닝

10.1 버저닝이 필요한 이유

최종 일관성 시스템에서는 여러 복제본이 일시적으로 서로 다른 값 보유 가능
네트워크가 단절된 상태에서 서로 다른 서버가 동일한 키를 동시에 변경할 수 있음
어느 값이 최신인지 또는 두 값이 충돌했는지 판별 필요

10.2 데이터 버전 생성

데이터가 변경될 때마다 새로운 버전 생성
이미 생성된 버전의 데이터는 변경하지 않음
여러 버전 사이의 선후 관계 비교 가능

11. 벡터 시계

11.1 벡터 시계란

각 데이터 버전에 [서버, 버전 번호]의 순서쌍을 연결하는 방식
서버마다 자신이 수행한 변경 횟수를 별도로 관리
각 버전이 어떤 서버의 변경을 얼마나 포함하는지 표현

11.2 버전 비교 방법

두 버전 X와 Y를 비교할 때 다음 조건을 확인함.

X의 모든 서버 카운터가 Y보다 작거나 같음
최소 하나의 서버 카운터는 Y가 더 큼

위 조건을 만족하면 Y가 X의 모든 변경을 포함하므로 Y를 X보다 나중 버전으로 판단.

11.3 선후 관계가 있는 예시

X = [(A, 1), (B, 0)]
Y = [(A, 2), (B, 1)]

Y의 A 카운터가 X보다 큼
Y의 B 카운터도 X보다 큼
Y가 X의 모든 변경을 포함
Y를 X의 후속 버전으로 판단

11.4 충돌한 버전 예시

X = [(A, 2), (B, 0)]
Y = [(A, 1), (B, 1)]

X는 A 서버의 변경을 더 많이 포함
Y는 B 서버의 변경을 더 많이 포함
어느 버전도 상대방의 모든 변경을 포함하지 않음
두 버전은 서로 병렬적으로 생성된 충돌 관계

11.5 벡터 시계의 역할

버전 사이의 선후 관계 판별
동시 변경으로 발생한 충돌 탐지
충돌을 발견할 수 있지만 어떤 버전을 선택할지는 자동으로 결정하지 않음

11.6 충돌 해결 방법

사용자 또는 애플리케이션이 하나의 버전 선택
여러 버전의 내용을 병합
집합처럼 합칠 수 있는 데이터는 합집합 사용
업무 규칙을 이용한 서버 측 병합
마지막 쓰기 우선 방식 적용 가능

11.7 단점

Dynamo에서는 여러 버전의 충돌 해결 책임이 애플리케이션으로 전달될 수 있음
애플리케이션 또는 클라이언트 구현 복잡도 증가
서버가 많아질수록 [서버, 버전] 순서쌍 증가 가능
벡터 시계의 크기가 지속적으로 커질 수 있어 오래된 항목 정리 필요

장애 처리

12. 장애 감지

12.1 장애 판단의 어려움

분산 시스템에서는 서버 장애와 일시적인 네트워크 지연을 즉시 구분하기 어려움
한 노드의 보고만으로 바로 장애를 확정하면 정상 서버를 장애로 잘못 판단할 수 있음
여러 노드의 관찰이나 반복된 타임아웃을 바탕으로 장애 여부 판단 가능

12.2 전체 노드 간 상태 교환

모든 노드가 서로 상태를 직접 전달하는 방식
노드 수가 적을 때 구조가 단순함
노드 수가 많아지면 통신 연결과 메시지 수가 크게 증가
대규모 분산 시스템에는 비효율적일 수 있음

13. 가십 프로토콜

13.1 멤버십 목록

각 노드는 클러스터에 참여하는 노드의 상태를 기록하는 멤버십 목록 유지.

멤버십 목록에는 다음 정보 포함 가능.

노드 또는 멤버 ID
박동 카운터
마지막 갱신 시간

13.2 동작 과정

각 노드가 주기적으로 자신의 박동 카운터 증가
무작위로 다른 노드 선택
책의 설계에서는 선택된 노드와 멤버십 목록 교환
상대방이 가진 정보와 자신의 정보 비교
더 큰 박동 카운터나 더 최근의 정보를 기준으로 목록 갱신
특정 노드의 박동 카운터가 일정 시간 동안 갱신되지 않으면 장애 의심

13.3 장점

모든 노드가 모든 노드에 직접 메시지를 보낼 필요 없음
일부 노드와 주기적으로 정보를 교환하면서 상태가 전체 클러스터로 확산
노드 수가 증가해도 비교적 효율적으로 멤버십 정보 전달 가능

14. 일시적인 장애 처리

14.1 느슨한 정족수

원래 데이터를 담당하는 서버가 일시적으로 응답하지 않는 상황
정상 상태인 다른 서버를 임시 복제본으로 선택
원래 복제 서버의 복구를 기다리지 않고 쓰기 요청 처리
높은 쓰기 가용성 유지

14.2 단서 후 임시 위탁

다른 서버가 장애 서버를 대신해 데이터를 임시 저장하는 방식
임시 저장된 데이터에 원래 담당 서버 정보를 함께 기록
이 정보를 단서라고 부름

14.3 단서에 포함되는 정보

해당 데이터의 원래 담당 서버
전달할 키와 값
데이터 버전
타임스탬프 또는 만료 정보

14.4 단서를 남기는 이유

임시 저장 서버가 해당 데이터가 자신의 정식 데이터인지 구분 가능
장애가 복구된 뒤 어느 서버로 데이터를 전달해야 하는지 확인 가능
원래 서버에 전달한 후 임시 사본 정리 가능

14.5 복구 과정

원래 담당 서버의 장애 발생
다른 정상 서버가 쓰기를 임시 저장
데이터와 함께 원래 담당 서버에 관한 단서 기록
원래 서버가 복구되었는지 주기적으로 확인
복구되면 임시 저장 데이터를 원래 서버로 전달
전달 완료 후 임시 데이터와 단서 제거

Amazon Dynamo는 일시적 장애 상황에서 높은 가용성을 유지하기 위해 느슨한 정족수와 단서 후 임시 위탁을 사용함.

15. 영구적인 장애 처리

15.1 반-엔트로피 프로토콜

장기간의 장애나 전달 실패로 서로 달라진 복제본을 동기화하는 과정
각 복제본이 가진 데이터 비교
오래되거나 누락된 데이터를 찾아 최신 상태로 갱신
모든 데이터를 매번 직접 비교하면 네트워크와 디스크 비용이 매우 큼

15.2 머클 트리 활용

복제본 사이의 차이를 효율적으로 찾기 위해 머클 트리 사용
전체 데이터를 작은 범위로 분할
각 데이터 범위의 해시값 계산
하위 노드의 해시값을 결합하여 상위 노드 해시값 계산
최종적으로 루트 해시값 생성

15.3 머클 트리 비교 과정

두 서버의 루트 해시값 비교
루트 해시값이 같으면 비교 대상 데이터가 동일한 것으로 판단
루트 해시값이 다르면 자식 노드의 해시값 비교
서로 다른 해시값을 가진 하위 구간으로 이동
실제 데이터가 다른 범위 탐색
차이가 있는 데이터 구간만 전송하여 동기화

15.4 장점

전체 데이터를 서버 간에 전송할 필요 없음
서로 다른 데이터 범위만 탐색 가능
네트워크 사용량 감소
대규모 데이터 집합의 비교 비용 감소

Amazon Dynamo는 복제본 사이의 불일치를 효율적으로 탐지하기 위한 반-엔트로피 과정에 머클 트리를 활용함.

아키텍처

16. 전체 구조

16.1 클라이언트

키-값 저장소의 get 및 put API 호출
특정 저장 노드의 위치를 직접 알 필요 없음

16.2 중재 노드

클라이언트 요청을 처음 받은 노드
클라이언트의 프록시 또는 코디네이터 역할 수행
키에 대한 담당 복제 서버 확인
읽기와 쓰기 요청 전달
필요한 정족수 응답 수집
충돌한 버전이 있으면 클라이언트 또는 애플리케이션에 전달 가능

16.3 저장 노드

안정 해시의 해시 링 위에 분포
자신이 담당하는 파티션의 데이터 저장
다른 노드의 데이터를 복제본으로 저장 가능

16.4 완전 분산 구조

노드를 자동으로 추가하거나 제거 가능
데이터를 여러 노드에 복제
모든 노드가 동일하거나 유사한 책임 수행
저장소 내부의 단일 장애 지점을 최소화
특정 중앙 서버 하나에 전체 기능이 의존하지 않도록 구성

16.5 각 노드가 수행할 수 있는 기능

클라이언트 요청 수신
중재 노드 역할
키의 담당 서버 탐색
데이터 읽기와 쓰기
복제본 저장
장애 감지
가십 프로토콜 참여
일시적 장애 데이터 임시 저장
복제본 동기화

데이터 저장 경로

17. 쓰기 경로

17.1 처리 과정

쓰기 요청 수신
커밋 로그에 요청 순차 기록
데이터를 메모리의 MemTable에 기록
MemTable이 설정된 임계 크기에 도달
MemTable의 데이터를 디스크의 SSTable로 플러시

17.2 커밋 로그

쓰기 내용을 디스크에 순차적으로 기록하는 로그
서버가 장애로 재시작되어도 아직 SSTable에 기록되지 않은 데이터 복구 가능
임의 위치를 수정하는 것보다 순차 쓰기를 사용해 디스크 쓰기 효율 향상 가능

17.3 MemTable

최근 쓰기 데이터를 임시로 보관하는 메모리 내 자료구조
일반적인 읽기 캐시가 아니라 디스크 기록 전 쓰기 버퍼 역할
키를 기준으로 정렬된 구조로 유지 가능
메모리 임계치에 도달하면 SSTable로 변환하여 디스크에 저장

17.4 SSTable

키를 기준으로 정렬된 키-값 쌍을 저장하는 불변 디스크 파일
한 번 생성된 이후 파일 내부 내용을 직접 수정하지 않음
새로운 쓰기나 수정 사항은 새로운 MemTable과 SSTable에 기록
여러 SSTable에 흩어진 오래된 데이터를 합치고 제거하는 컴팩션 과정 필요

Cassandra의 공식 저장 엔진 문서에서도 MemTable은 쓰기를 버퍼링하는 메모리 구조이며, 디스크로 플러시되면 불변 SSTable이 된다고 설명함.

18. 읽기 경로

18.1 기본 처리 과정

읽기 요청 수신
요청한 키가 MemTable 또는 메모리 캐시에 있는지 확인
메모리에 최신 값이 있으면 반환
메모리에 없으면 디스크의 SSTable 검색
블룸 필터로 키가 확실히 없는 SSTable 제외
키가 있을 가능성이 있는 SSTable의 인덱스와 데이터 확인
여러 버전이 발견되면 버전 또는 타임스탬프 비교
최신 값 반환

18.2 여러 SSTable을 확인하는 이유

SSTable은 생성된 이후 수정되지 않음
동일한 키의 서로 다른 버전이 여러 SSTable에 존재할 수 있음
최신 값을 찾기 위해 여러 SSTable을 검사해야 할 수 있음
모든 SSTable을 직접 읽으면 디스크 접근 비용 증가
불필요한 SSTable 접근을 줄이기 위해 블룸 필터 활용

19. 블룸 필터

19.1 블룸 필터란

특정 값이 집합에 존재하는지 빠르게 검사하는 확률적 자료구조
비트 배열과 여러 개의 해시 함수 사용
실제 키 전체를 저장하지 않고 해시 결과만 비트 형태로 표현
적은 메모리로 많은 키의 존재 가능성 검사 가능

Redis 공식 문서도 블룸 필터를 적은 고정 메모리로 원소의 집합 포함 여부를 검사하는 확률적 자료구조로 설명함.

19.2 데이터 추가

초기 비트 배열:

[0, 0, 0, 0, 0, 0, 0, 0]

apple을 추가한다고 가정함.

hash1(apple) → 1번
hash2(apple) → 4번
hash3(apple) → 6번

해당 위치의 비트를 1로 설정:

[0, 1, 0, 0, 1, 0, 1, 0]

19.3 데이터 조회

apple을 조회할 때 동일한 해시 함수 적용:

hash1(apple) → 1번
hash2(apple) → 4번
hash3(apple) → 6번

모든 비트가 1인 경우

1번, 4번, 6번이 모두 1
→ 해당 키가 있을 가능성이 있음

실제로 키가 존재할 수 있음
다른 키들이 우연히 같은 비트들을 1로 설정했을 수도 있음
실제 SSTable 조회 필요

하나라도 0인 경우

1번, 4번, 6번 중 하나라도 0
→ 해당 키는 확실히 없음

해당 키를 삽입했다면 모든 위치가 1이어야 함
하나라도 0이면 해당 SSTable을 검색할 필요 없음

19.4 블룸 필터의 특성

거짓 양성 가능

블룸 필터가 있다고 판단했지만 실제 데이터에는 없을 수 있음
해시 충돌로 다른 키들이 동일한 비트를 1로 만들 수 있기 때문
블룸 필터의 양성 결과 이후 실제 데이터 확인 필요

거짓 음성 없음

일반적인 블룸 필터는 없다고 판단한 데이터가 실제로 존재하는 상황이 발생하지 않음
하나의 비트라도 0이면 해당 키는 확실히 없음

블룸 필터는 거짓 양성이 발생할 수 있지만 일반적인 구현에서는 거짓 음성이 발생하지 않음.

19.5 SSTable에서의 역할

블룸 필터가 키의 정확한 저장 위치를 알려주는 것은 아님
각 SSTable에 특정 키가 존재할 가능성만 판단
키가 확실히 없는 SSTable을 검색 대상에서 제외
있을 가능성이 있는 SSTable만 실제로 조회
불필요한 디스크 접근 감소
읽기 응답 시간 개선

20. 전체 정리

데이터 분산

안정 해시로 키와 서버를 해시 링에 배치
서버 추가와 제거 시 이동하는 데이터 최소화
가상 노드로 서버별 부하와 데이터 분포 균등화

데이터 복제

동일한 데이터를 서로 다른 N개의 물리 서버에 저장
일부 서버 장애 시에도 다른 복제본을 통해 데이터 접근 가능

데이터 일관성

R, W, N 값을 조정하여 읽기·쓰기 성능과 일관성 수준 조절
R+W>N은 읽기와 쓰기 정족수의 교집합을 만드는 조건
이 조건만으로 강한 일관성이 자동 보장되지는 않음
Amazon Dynamo는 높은 가용성과 최종 일관성을 우선

충돌 처리

벡터 시계로 버전 사이의 선후 관계와 동시 변경 탐지
충돌한 데이터는 애플리케이션 또는 서버의 정책으로 병합

장애 감지와 복구

가십 프로토콜로 노드 상태 정보 전파
일시적 장애에는 느슨한 정족수와 단서 후 임시 위탁 사용
장기적인 데이터 불일치는 반-엔트로피와 머클 트리로 복구

데이터 저장

쓰기 요청을 커밋 로그와 MemTable에 기록
MemTable이 가득 차면 불변 SSTable로 디스크에 저장
여러 SSTable은 컴팩션으로 병합 및 정리

데이터 읽기

메모리에서 먼저 최신 데이터 확인
블룸 필터로 키가 확실히 없는 SSTable 제외
가능한 SSTable만 조회하여 디스크 접근 최소화

김연준

Live a life you will remember

이전 포스트

[대규모 시스템 설계 스터디] 5장 정리

다음 포스트