#06. 키-값 저장소 설계

Jnary·2023년 8월 21일

가상 면접 사례로 배우는 대규모 시스템 설계 기초

목록 보기

6/14

6장. 키-값 저장소 설계

key-value 저장소
- 비 관계형(non-relational) 데이터베이스
- 고유 식별자(identifier)를 키로 가져야 함
- pair: key, value간의 연결 관계
- ex. Amazon Dinamo, memcached, Redis
key
- 유일
- 해당 key에 매달린 value는 key를 통해서만 접근 가능
- 성능 상, key는 짧을 수록 👍
연산
- put(key, value): 키-값 쌍을 저장소에 저장
- get(key): 인자로 주어진 key에 매달린 value를 꺼냄

1. 문제 이해 및 설계 범위 확정

완벽한 설계는 X
- 읽기, 쓰기, 메모리 사용량 사이에 균형 찾기
- 데이터 일관성 & 가용성 사이에서 타협적 결정
다음 특성을 갖는 키-값 저장소를 설계해보자!
- 키-값 쌍의 크기 <= 10KB
- 큰 데이터 저장 가능
- 가용성 ⬆️: 장애가 있더라도 빠른 응답
- 규모 확장성 ⬆️: 트래픽 양에 따라 자동적으로 서버 증설/삭제
- 데이터 일관성 수준 조정 가능
- 응답 지연시간 ⬆️

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

키-값 쌍 전부를 메모리에 해시테이블로 저장
빠른 속도 보장
모든 데이터를 메모리 안에 두는 것은 불가능
개선책
- 데이터 압축 compression
- 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
  → But, 한 대 서버로 부족해짐

3. 분산 키-값 저장소

분산 해시 테이블
- 키-값 쌍을 여러 서버에 분산

CAP 정리

Consistency, Availability, Partition Tolerance theorem
- 데이터 일관성
- 가용성
- 파티션 감내
  → 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리
Consistency
- 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 됨
Availability
- 모든 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답 받을 수 있어야 함
Partition Tolerance
- Partition: 두 노드 사이에 통신 장애가 발생하였음을 의미
- 네트워크 Partition이 생기더라도 시스템은 계속 동작하여야 함
두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 함 (CA, CP, AP)
- 통상 네트워크 장애는 피할 수 없는 일!
- 분산 시스템은 반드시 Partition Tolerance를 지원해야함
  → 실세계에 CA 시스템은 존재 X
네트워크 장애로 일부 서버가 고장났을 때
- CP: 데이터 불일치 피하기 위해 다른 서버에 쓰기 연산 중단
- CA: 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산 허용

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트 및 기술
- 데이터 파티션
- 데이터 다중화 replication
- 일관성 consistency
- 일관성 불일치 해소 inconsistency resolution
- 장애 처리
- 시스템 아키텍처 다이어그램
- 쓰기 경로 / 읽기 경로

데이터 파티션

데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장
파티션 단위로 나눌 때 고려해야하는 것 (cf. 안정 해시)
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가, 삭제될 때 데이터의 이동을 최소화할 수 있는가

데이터 다중화

높은 가용성, 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화 필요
해시 링 위에서 시계 방향으로 순회하면서 첫 N개 서버에 데이터 사본 보관
가상 노드라면? 물리 서버의 개수가 N보다 작아질 수 있음
- 물리 서버 중복 선택하지 않도록 해야 함
- 안정성을 담보하기 위해 데이터의 사본은 다른 센터의 서버에 보관
- 센터들은 고속 네트워크로 연결

데이터 일관성

적절한 동기화 필요
Quorum Consensus(정족수 합) 프로토콜 사용 → read/write 연산 모두 일관성 보장
- N = 사본 개수
- W = write 연산에 대한 정족수
  → 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
- R = read 연산에 대한 정족수
  → 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 함
- coordinator(중재자): 성공 응답 받음. 클라이언트-노드 간의 proxy 역할
요구되는 일관성 수준에 따라 W, R, N의 값을 조정
- R = 1, W = N: 빠른 읽기 연산에 최적화
- W = 1, R = N: 빠른 쓰기 연산에 최적화
- W + R > N: 강한 일관성이 보장 (보통 N = 3, W = R = 2)
- W + R <= N: 강한 일관성 보장 X
일관성 모델
- 키-값 저장소 설계 시 고려해야 할 중요한 요소
- 데이터 일관성의 수준을 결정
- 종류
  - 강한 일관성: 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환. out-of-date 데이터 X. 쓰기 연산이 완료되는 순간 모든 노드에 동기화가 보장.
  - 약한 일관성: 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
  - 최종 일관성 eventual consistency: 약한 일관성의 한 형태. 갱신 결과가 언젠간 모든 사본에 동기화되는 모델
강한 일관성을 달성하는 방법
- 모든 사본에 현재 write 연산의 결과가 반영될 때까지 해당 데이터에 대한 read/write 연산 금지
  → 고가용성 시스템에는 적합 X
Dynamo, 카산드라: 최종 일관성 모델을 택하고 있음
- write 연산 병렬적으로 발생 시, 시스템에 저장된 값의 일관성이 깨질 수 있음
- 위 문제는 클라이언트에서 해결
  → 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록

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

데이터 다중화 → 가용성 ⬆️, 사본 간 일관성 ⬇️
- 해결법: versioning, vector clock
versioning
- 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것
- 각 버전의 데이터는 변경 불가능 immutable
vector clock
- [서버 번호, 버전 카운터] 의 순서쌍을 데이터에 매단 것
- 어떤 것이 선행 버전인지, 다른 버전과 충돌이 있는지 판별하는데 사용
- [Si, vi] 가 있으면 vi 증가
  그렇지 않으면, 새 항목 [Si, vi] 생성
  충돌이 발생한 경우, 충돌 해소된 데이터 기록 [Si, vi + 1]
이전 버전 판단 방법
- 버전 Y에 포함된 모든 구성 요소의 값 >= 버전 X에 포함된 모든 구성요소 값
  → 버전 X가 버전 Y의 이전 버전
충돌 여부 판단 방법
- Y의 vector clock 구성요소 가운데 X의 vector clock 동일 서버 구성요소보다 작은 값을 갖는 것이 있는지 확인
- ex. D([S0, 1], [s1, 2]) -충돌-D([S0, 2], [s1, 1])
vector clock의 단점
1. 충돌 감지 및 해소 로직이 클라이언트에 위임
  → 클라이언트 복잡성 ⬆️
2. [서버, 버전] 의 순서쌍 개수가 굉장히 빨리 늘어남
  → threshold 설정 후, 오래된 순서쌍을 vector clock에서 제거하도록 해야 함
  → but, 버전 간 선후관계가 정확하게 결정될 수 없음

장애 처리

failure detection → failture resolution
장애 감지
- 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고 → 실제로 장애가 발생햇다고 간주
- 모든 노드 사이에 multicasting 채널 구축
  - 서버 장애 감지하기 가장 손쉬운 방법
  - 서버가 많으면 비효율적
- 분산형 장애 감지 솔루션이 효율적 (ex. gossip protocol)
gossip protocol
- 각 노드는 membership list 유지
  → 각 memberId, heartbeatCounter 쌍의 목록
- 각 노드는 주기적으로 자신의 heartbeatCounter를 증가
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 heartbeatCounter 목록을 전송
- 목록을 받은 노드는 membership list를 최신 값으로 갱신
- 어떤 멤버의 heartbeatCounter 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 offline 상태인 것으로 간주 → 장애
일시적 장애 처리
- 장애를 감지한 시스템에 가용성을 보장하려면?
  - 엄격한 정족수 접근법: read/wirte 연산 금지
    → 완화: sloppy 느슨한 정족수 접근법
- 느슨한 정족수 접근법
  - 정족수 요구사항을 강제하는 대신, write 연산을 수행할 W개의 건강한 서버와 read 연산을 수행할 R개의 건강한 서버를 해시 링에서 고름
    → 장애 상태인 서버는 무시
  - 장애 상태인 서버로 가는 요청을 다른 서버가 맡아 처리
  - 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영 → 데이터 일관성 보존
  - 임시로 write 연산을 처리한 서버는 그에 대한 hint를 남겨둠
    → 단서 후 임시 위탁 기법 hinted handoff (일시적 장애 처리)
영구 장애 처리
- anti-entropy protocol
  - 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함
  - 사본 간의 일관성이 망가진 상태를 탐지
  - 전송 데이터의 양을 줄이기 위해 merkle 트리 사용
- merkle tree
  - hash tree
  - 각 노드에 그 자식 노드들에 보관된 값의 해시, 또는 자식 노드들의 레이블로부터 계산된 해시값을 레이블로 붙여두는 트리
  - 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증 가능
- 두 merkle tree 비교
  - root 노드의 해시값을 비교하는 것으로 시작
  - root 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 갖는 것
  - 값이 다른 경우, 왼쪽 자식 노드의 해시 값을 비교, 그 다음으로 오른쪽 자식 노드
  - 아래쪽으로 탐색하다보면 다른 데이터를 갖는 버킷 찾을 수 있음
    → 그 버킷들만 동기화
    → 동기화해야하는 데이터의 양: 존재하는 차이의 크기에 비례할 뿐. 데이터의 총량과는 무관해짐.
데이터 센터 장애 처리
- 정전, 네트워크 장애, 자연재해 등
- 데이터를 여러 데이터 센터에 다중화하는 것이 중요

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

주된 기능
- 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API와 통신 get(key) put(key,value)
- 중재자(coordinator): 클라이언트에게 키-값 저장소에 대한 proxy 역할을 하는 노드
- 노드는 안정 해시의 해시 링 위에 분포
- 노드를 자동으로 추가, 삭제할 수 있도록 시스템은 완전히 분산된다
- 데이터는 여러 노드에 다중화
- 모든 노드가 같은 책임 → SPOF 존재 X
완전히 분산된 설계 채택했으니 위에 제시된 기능 전부 지원 필요
- 클라이언트 API, 데이터 충돌 해소, 다중화, 장애 감지, 장애 복구 매커니즘, 저장소 엔진, ...
쓰기 경로
- 쓰기 요청이 commit log 파일에 기록
- 데이터가 메모리 캐시에 기록
- 메모리 캐시가 가득차거나 임계치에 도달하면 데이터는 디스크에 있는 SSTable로 내보내기(Flush)
  - SSTable: Sorted-String Table, <키,값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블
읽기 경로
- 데이터가 메모리 캐시에 있는지 확인
  - 있다면, 결과 반환
- 없다면, SSTable에 찾는 키가 있는지 확인
  - Bloom filter 검사
  - 어떤 SStable에 키가 보관되어 있는지 확인
  - SSTable에서 데이터 가져와서 클라이언트에게 반환