wooyounggggg commented 2 years ago

주제

5~6장을 읽고 내용을 요약하거나, 중요✨ 하다고 생각하는 키워드 및 관련 설명을 코멘트로 달아주세요

연관 챕터

16

@caffeine-library/readers-system-design-interview

wooyounggggg commented 2 years ago

5장 안정 해시 설계

해시 키 재배치(rehash) 문제

존재하는 데이터와, 그에 대한 논리적 연산의 동기화가 어긋나 발생하는 문제 ex) Modular N 연산을 Hashing에 사용하다가, N값이 변경되는 경우. 서버의 추가/제거 등

안정 해시

해시 테이블의 크기가 조정될 때, 평균적으로 k/n개의 키만 재배치하는 기술 기존의 전통적 해시 테이블이 대부분의 키를 재배치하는 것에 반해, k/n개만 재배치하여 시간 복잡도를 향상하는 특징을 가짐

안정 해시 알고리즘의 문제점

서버가 추가/삭제 되면서 파티션의 크기를 균등하게 유지하기 어려움
키의 균등 분포를 달성하기 어려움

가상 노드

안정 해시 알고리즘의 문제를 해결하기 위해 고안된 방법 서버의 개수보다 더 많은 가상 노드를 해시 링 내부에 분포시켜, 데이터 분포의 표준 편차를 낮추는 방법 서버 하나가 여러대의 가상 노드를 할당하여 사용하게 됨

JasonYoo1995 commented 2 years ago

6장 : 키-값 저장소 설계

분산 키-값 저장소

한 대의 서버만 사용하기엔 데이터가 너무 많음
- 해결 방법
  1. 데이터 압축
  2. 자주 쓰는 데이터만 메모리에, 나머지는 디스크에 저장
위 2가지 해결 방법에도 저장 공간이 부족
- 여러 대의 서버에 분산 저장하여 해결

CAP 정리

분산 시스템에서 다음 3가지 요구사항을 동시에 만족시키는 것은 불가능
- Consistency (일관성)
  - 어떤 노드에 접속하더라도 클라이언트는 같은 데이터를 봐야 함
- Availability (가용성)
  - 일부 노드에 장애가 발생하더라도 클라이언트는 응답을 받아야 함
- Partition Tolerance (파티션 감내)
  - 두 노드 사이에 통신 장애가 발생하여도 시스템은 계속 동작해야 함
분산 시스템 분류
- CP 시스템 : 일관성과 파티션 감내를 지원하는 시스템 (가용성은 지원하지 않음)
- AP 시스템 : 가용성과 파티션 감내를 지원하는 시스템 (일관성은 지원하지 않음)
- CA 시스템 : 일관성과 가용성을 지원하는 시스템 (파티션 감내는 지원하지 않음)
  - 현실 세계에서 네트워크 장애는 반드시 일어나기 때문에 파티션 감내는 필수적으로 지원되어야 하는 요구사항임
  - 따라서, 현실 세계에서 CA 시스템은 존재하지 않음

이상적 상태

이상적인 세계에서 네트워크가 파티션되는 상황은 일어나지 않음
따라서 n1에 데이터가 기록되면, 반드시 n2와 n3에도 자동 복제됨
C와 A와 P 모두가 만족됨

실세계의 분산 시스템

현실 세계에서는 파티션 문제를 피할 수 없음
위 그림에서 n3와의 통신에 장애가 발생하였고, 다음의 2가지 문제가 생김
1. n1과 n2에 기록된 데이터가 n3에 전달되지 않음
2. n3에 기록되었으나 아직 n1와 n2에 복제되지 않았던 데이터가 남아 있음
파티션 문제가 발생하면 일관성과 가용성 둘 중 하나만 지킬 수 있음
- 일관성을 지키는 경우 (=CP 시스템)
  - n1와 n2에 접근 중단
  - 접근 시도 시 오류 반환
  - ex) 은행권 시스템
- 가용성을 지키는 경우 (=AP 시스템)
  - n1와 n2에 접근 허용
  - 낡은(Stale) 데이터일지라도 반환
  - 파티션 문제가 해결되면
    - 그동안 n1와 n2에 생긴 변경사항을 n3에 복제
    - 그동안 n3에서 n1와 n2로 복제하지 못했던 데이터를 복제

데이터 파티션

데이터가 너무 많아서, 데이터를 여러 개의 파티션으로 나누어 여러 서버에 분산 저장하는 것
데이터 파티션 시 2가지 이슈
1. 데이터를 여러 서버에 고르게 분산
2. 노드가 추가/삭제될 때 데이터의 이동 최소화
→ 5장에서 다룬 ‘안정 해시(Consistent Hashing)’를 통해 해결 가능

데이터 다중화

높은 가용성을 확보하기 위해서, 같은 데이터를 N개의 서버에 복제(=다중화, Replication)
복제 서버 선정 방법 : 데이터의 key로부터 시계 방향으로 연속된 N개의 서버

데이터 일관성

특정 서버에 데이터가 기록되면, 서버 간에 동기화를 시킴으로써, 일관성을 지킬 수 있음
정족수 합의 프로토콜(Quorum Consensus Protocol)
- N : 사본의 개수
- W : 쓰기 연산에 대한 정족수
  - W개의 서버에 동기화가 끝나면, 클라이언트에게 응답
- R : 읽기 연산에 대한 정족수
  - R개의 서버로부터 읽어서, 클라이언트에게 응답

정족수에 따른 특성
- R=1, W=N : 빠른 읽기 연산
- W=1, R=N : 빠른 쓰기 연산
- W+R>N : 강한 일관성
- W+R≤N : 약한 일관성
→ ‘응답 지연 vs 일관성’ 사이의 Trade-off 존재
- 정족수가 작을수록, 빠른 응답과 낮은 일관성
- 정족수가 클수록, 느린 응답과 높은 일관성

일관성 모델

강한 일관성 모델 (Strong Consistency Model)
- 클라이언트는 반드시 최신 데이터를 받아보게 됨
약한 일관성 모델 (Weak Consistency Model)
- 클라이언트는 최신 데이터가 아닌 데이터를 받아볼 수도 있음
최종 일관성 모델 (Eventual Consistency Model)
- 약한 일관성 모델의 한 종류
- 갱신 결과가 결국에는 모든 사본에 동기화 됨
- 강한 일관성 모델의 경우, 서버 장애 발생 시 가용성을 잃어버린다는 문제가 최종 일관성 모델에서는 발생하지 않음
- 일관성이 깨어지는 문제를 클라이언트가 해결

비 일관성 해소 기법 : 데이터 버저닝(Data Versioning)

D([S, V], ...) : 벡터 시계
D : 데이터 / S : 서버 / V : 버전
위 그림은 최종 일관성 모델의 경우를 보여주는 듯함
따라서, 쓰기 시에는 동기화되지 않고, 읽기 시에 (클라이언트가 주체적으로) 동기화 시킴
벡터 시계를 비교하여 선행 여부와 충돌 여부를 알 수 있음
- D2([Sx, 2])와 D3([Sx, 2], [Sy, 1])는 버전만 모은 순서쌍으로 표현하면 D2(2, 0, 0)와 D3(2, 1, 0)인데 D3에서 모든 버전이 앞서므로 D3가 D2에 비해 최신 데이터라고 판단
- D3([Sx, 2], [Sy, 1])와 D4([Sx, 2], [Sz, 1])는 버전만 모은 순서쌍으로 표현하면 D3(2, 1, 0)와 D4(2, 0, 1)인데 둘 중 어느 것도 모든 버전이 앞서는 경우가 없으므로, 충돌 발생
책에는 벡터 시계를 누가 가지고 있는 지에 대한 설명이 없음

→ 개인적인 견해로, 중재자가 갖고 있어야 할 것 같음

→ 만약 그렇다면, 중재자 서버는 어떻게 선정하는지에 대한 의문과, 중재자 서버가 죽으면 벡터 시계가 날라갈 텐데 이는 어떻게 방지할 수 있는가 등의 의문이 남음

장애 감지

가십 프로토콜(Gossip Protocol)
- 주기적으로 자신의 박동 카운터(Heartbeat Counter)를 증가시킨다
- 무작위로 선정된 노드들에게 주기적으로 자신의 Membership List를 보낸다
- 받은 Membership List대로 자신의 Membership List를 최신화한다
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(Offline) 상태로 간주한다

일시적 장애 처리

W : 쓰기 연산에 대한 정족수
- 위 그림의 경우, W=3
엄격한 정족수(Strict Quorum) 접근법
- W개의 서버 중 일부에 장애가 발생하면 동기화 시키지 못한 데이터는 (서버가 복구될 때까지) 읽기/쓰기가 중지됨
- 위 그림의 경우, s2가 복구될 때까지 key1에 대한 읽기/쓰기가 중지됨
느슨한 정족수(Sloppy Quorum) 접근법
- W개의 서버 중 일부에 장애가 발생하면 쓰기하고자 했던 데이터를 관리할 서버를 새로 선정하여 계속해서 읽기/쓰기 가능
- 이와 같이, 어떤 서버가 어떤 서버의 일을 대신하고 있는지 단서(hint)를 남기는 기법을 임시 위탁(Hinted Handoff)이라고 함
- 서버가 복구되면, 대신 관리되던 데이터는 (단서를 이용해) 복구된 서버로 인계
- 위 그림의 경우, s2에 장애가 발생하면 s3에게 임시 위탁하고, s2가 복구되면 s3로 인계

영구 장애 처리

영구적으로 장애가 발생한 서버의 최신 데이터들을 정상 기동 중인 다른 복제 서버(Replication)들로 반영할 필요가 있다

→ 반-엔트로피 프로토콜(Anti-entropy Protocol)
머클 트리(Merkle Tree) 이용하여, 두 서버 간에 불일치하는 사본들을 효율적으로 탐색할 수 있다
머클 트리 생성/갱신 방법
1. 여러 개의 Bucket 안에 여러 개의 key를 보관한다
2. 각 Bucket마다 1개의 해시 값을 추출한다
3. 자식 노드로부터 새로운 해시 값을 계산하여 이진 트리를 상향식으로 구성해간다
불일치 사본 탐색 방법
- 두 머클 트리의 루트 노드부터 하향으로 해시 값을 비교해나간다
- 해시 값이 같으면, 해당 노드의 말단 노드들의 데이터들은 모두 일치한다
- 해시 값이 다르면, 불일치 데이터가 포함된 자식 노드가 존재하는 것이므로 계속해서 하향으로 탐색해나간다

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

모든 노드가 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않는다

hyunrrr commented 2 years ago

6장 키-값 저장소 설계

키-값 저장소 설계시 고려해야 하는 문제

하나의 서버에 모든 데이터를 저장할 수 없음 -> 분산시스템으로 설계
분산시스템은 CAP(consistency, availability, partition tolerance)를 모두 만족할 수 없음 -> P는 현실에서 충족될 수 없으므로 CP, AP 중 알맞은 것을 선태해야 함

CAP

consistency(일관성): 모든 노드에 동일한 데이터가 있어야 함

availability(가용성): 클라이언트는 분산시스템으로 부터 항상 응답을 받을 수 있어야 함

partiton tolerance(파티션 감내): 통신 장애가 발생하더라도 시스템이 계속 동작하는 것 (파티션은 두 노드 사이에 통신 장애가 발생함을 의미함)

분산 키-값 저장소의 핵심 컴포넌트

데이터 파티션
- 수 많은 데이터를 여러대의 서버에 나눠서 저장 -> Hash ring으로 데이터를 나눔
데이터 다중화
- availability를 높이기 위해 같은 데이터를 N개의 서버에 저장함 -> Hash ring에서 서로 다른 N개의 서버를 선택해 저장
일관성 유지
- 데이터 다중화로 인해 여러 서버에 저장된 데이터의 일관성을 유지해야 함
- 일관성 모델은 [강한일관성, 약한일관성, 최종일관성]으로 나눌 수 있음
- 최종일관성 모델에서 [데이터 비저닝 + 벡터시계]로 일관성 불일치를 해결할 수 있음
장애처리
- 서버에 발생하는 장애를 감지하고 대응할 수 있어야 함
- 장애 감지 -> 모든 노드사이에 멀티캐스팅 채널을 구축하는 것은 비효율적 -> 분산형 장애감지(decentralized failure detection) 기법 사용 -> 가십 프로토콜(gossip protocol)
- 장애 해소
  - 일시적 장애처리 -> 엄격한 정족수(strict quorum)이면 모든 노드에서 읽기와 쓰기 연산 금지 -> 느슨한 정족수(strict quorum)이면 단서 후 임시 위탁(hinted handoff) 기법
  - 영구 장애처리 -> 반-앤트로피 프로토콜을 이용 -> 사본들을 비교해 최신 버전으로 갱신하는 과정을 포함 -> 머클(Merkle) 트리를 사용해 전송 데이터 양을 줄임
- 데이터센터 장애처리 -> 데이터센터를 여러 지역에 다중화해 데이터 영구손실을 방지

caffeine-library / system-design-interview

[keyword] 5~6장 키워드 정리 #17

주제