6장 - 키-값 저장소 설계

시작

키 값 저장소는 비 관계형 데이터베이스이다. 잘 아시다싶이 키 값은 고유 식별자를 키로 가져가야 한다. 

 

문제 이해 및 설계 범위 확정

6장에서 다룰 키-값 저장소 설계는 다음 요건을 충족하는것을 만들것이다.

- 키-값 쌍의 크기는 10KB 이하
- 큰 데이터를 저장할 수 있어야 한다.
- 높은 가용성
- 높은 규모 확장성
- 데이터 일관성 수준 조정 가능
- 응답 지연시간이 짧아야 한다. 

단일 서버 키-값 저장소 한대 서버에 키-값 저장소를 설계해서 해시 테이블에 저장하면 어떨까? 이 방법이 가장 직관적이다. 
모든 데이터를 안에 두게 되면 크기가 문제가 될 수 있다. 
- 데이터 압축
- 자주 쓰이는 데이터 메모리에 두고 나머지는 디스크 저장
임시방편으로 이런 제시를 할 수 있겠지만 서버를 무한정 늘릴 수 있는것이 아니기 때문에 분산 키-값 저장소 를 만들어야 한다.
-> Distributed Key-Value Store
분산-키 값 저장소같은 말로 분산 해시 테이블이라고 한다. 

CAP 정리

데이터 일관성 - 어떤 서버에 접속하였던 조회 시 데이터의 같은 값을 보장해야 한다. 
가용성 - 분산 시스템에 접속하는 클라이언트는 일부 노드가 장애가 발생하더라도 기존처럼 항상 응답을 받을 수 있어야 한다. 
분할내성(Partition Tolerance) - 시스템이 장애가 발생하더라도 계속 동작해야 한다. 

잘 모르겠지만 아래의 기준을 두 가지 충족하려면 나머지 하나는 반드시 희생해야 한다고 한다. 

https://azderica.github.io/00-db-cap/#google_vignette

그래서 두가지 조합을 여러 케이스로 생성해 볼 수 있다.

CP 시스템 - 일관성과 분할내성을 지원, 가용성 희생
AP 시스템 - 가용성과 분할 내성을 지원, 일관성 희생
CA 시스템 - 일관성과 가용성을  지원, 분할내성 희생

실세계의 분산 시스템

분산 시스템은 파티션 문제를 피할 수 없다. 가용성 혹은 일관성 어느것을 희생해야할지 결정해야 하는데 
일관성을 고려한다면 데이터 불일치를 고려해서 n1, n2 서버에 쓰기 연산을 중지시켜야 한다. -> 가용성을 깨진다. 
은행 시스템을 고려한다면 일관성을 채택하게 되는데 문제가 해결될 때 까지 오류를 반환받는다. 

만약, 가용성을 선택한다면 이전의 데이터를 반환할 위험이 있어도 계속 읽기 연산을 허용해야 한다. n1, n2 에도 쓰기는 계속 허용될것이고 시스템의 장애가 해결될때까지 새 데이터가 n3에 전송될 것이다. 

https://donghyeon.dev/

 

 

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트

- 데이터 파티션
- 데이터 다중화
- 일관성 
- 일관성 불일치 해소
- 장애처리
- 시스템 아키텍처 다이어그램
- 쓰기 경로
- 읽기 경로

 

데이터 파티션

전체 데이터를 한 대 서버에 욱여넣는것이 아니라 작은 파티션들로 분할한 다음 여러 대 서버에 저장하는것이다. 
- 데이터를 여러 서버에 고루 분산할 수 있는가?
- 노트 추가되거나 삭제될때 데이터의 이동을 최소화할 수 있는가? 
해시링을 적용해보자.
해시링을 구성하고 시계방향으로 순회하다 만나는 첫번째 서버가 바로 해당 키-값 쌍을 저장할 서버가 된다. 

해시링을 이용하면 장점?
- 규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 할 수 있다. 
(이걸 규모 확장이라고 볼 수 있는지 살짝 의문이다. 함께 얘기해보면 좋은 부분..) 
- 다양성 : 가상노드 수를 조정할 수 있다. 

데이터 다중화

높은 가용성과 안정성을 확보하기 위해서 데이터를 N개 서버에 비동기적으로 replication 을 한다. N은 튜닝 가능한 값이다. 
이것도 해시링을 적용해본다. (왜?)
시계 방향으로 링을 순회하면서 첫 N개 서버에 데이터 사본을 보관한다. 
그런데 실제 해시링에 배치된 노드의 개수보다 많으면 어떻게 할것인가? 
물리 서버 중복을 선택하지 않는다. 
즉, 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제로 부터 안정성을 보장하기 위해 데이터 사본은 다른 센터에 보관한다. 

데이터 일관성

여러 노드에 다중화된 데이터는 동기화되어야 한다. Quorun Consensus 프로토콜을 이용하면 읽기/쓰기 연산 모두 일관성을 보장할 수 있다.
(*Quorun Consensus 프로토콜 - 신뢰할 수 있는 시스템에서 다수의 참여자가 어떤 제안에 대해 합의하고, 이를 통해 시스템의 일관성과 신뢰성을 유지하는 것)

N = 서버 개수
W = 쓰기 연산에 대한 응답
R = 읽기 연산에 대한 응답 
여기서 중재자는 클라이언드와 서버 사이에 proxy 역할을 한다. 

case 1. W = 1, R = 1 
한대의 서버에서 응답을 처리하는것이므로 속도가 빠르다. 
case 2. W > 1, R > 1 
여러대의 서버에서 응답을 받야아하니 데이터 일관성을 고려한다면 느릴 수 밖에 없다. 

그래서 정리해보면 W+R > N 인 경우는 강한 일관성 

정답은
- R=1, W = N : 빠른 읽기
- W=1, R = N : 빠른 쓰기
- W+R>N : 강한 일관성 
- W+R<=N : 강한 일관성 보장 X

https://jonghoonpark.com/2023/06/01/key-value-store-consistency

일관성 모델 

앞서 강한 일관성에 대해 얘기했는데 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환, out-of-date 데이터는 보지 않는다. 
반면에 약한 일관성은 최근에 갱신된 결과를 반환하지 못할 수 있다. 

eventual consistency - 약한 일관성의 한 형태이지만 갱신 결과가 결국 모든 사본에 반영되어야 한다. 
강한 일관성이 부적합한 이유는 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다. -> 고가용성에서는 적합하지 않다. 
그럼 eventual consistency는 어떻게 이를 처리하고 있을까? 
클라이언트에서 버전을 관리하여 일관성이 깨진 데이터를 확인하고 읽지 않도록 처리하는 방법을 수행한다. 

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

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

https://velog.io/@dev_dc_hyeon

https://velog.io/@dev_dc_hyeon

벡터 시계는 [서버, 버전] 순서쌍을 데이터를 관리하는것이다. 
예를 들어서 D([S1, v1], [S2, v2], ... , [Sn, vn]) 같이 표현한다. 
D는 데이터, vi는 버전 카운터, Si는 서버 번호 

버전 X, Y 사이에 충돌이 있는지 보려면 

D([s0, 1], [s1, 2]) 와 D([s0,2], [s1,1])은 서로 충돌한다. 

벡터 시계에 대한것은 클라이언트 구현을 복잡하게 만든다. 
[서버: 버전]의 순서쌍 개수가 굉장히 많이 늘어난다.

길이에 대한 임계치(threshold)를 설정하고 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 한다. 

 

장애감지

모든 노드 사이에 멀티캐스팅 채널을 구축하는것이 장애 감지하는 가장 쉬운 방법이다. 
서버가 많으면 비효율적일 수 밖에 없다. 

여기서 가십 프로토콜 같은 분산형 장애 감치 솔루션을 채택하면 좋다.

https://velog.io/@dev_dc_hyeon

*가십 프로토콜(gossip protocol) 
- 각 노드는 membership list를 유지한다. member id, heartbeat counter 쌍의 목록
- 각 노드는 주기적으로 heartbeat counter 를 증가
- 각 노드는 무작위로 선정된 노드에 주기적으로 heartbeat counter list를 보낸다. 
- heartbeat counter list 를 받은 노드는 membership list를 최신값으로 갱신
- (중요) 어떤 멤버의 heartbeat counter 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인것으로 간주 

6-11
- 노드 s0가 s2멤버가 heartbeat counter 가 오랫동안 증가되지 않은것 발견
- 노드 s0는 노드 s2를 포함하는 heartbeat counter list를 무작위로 선택된 다른 노드에 전달 
- 노드 s2의 heartbeat counter 가 오랫동안 증가되지 않은것을 발견 모든 노드에 해당 노드를 장애 노드로 표시 

https://velog.io/@dev_dc_hyeon

 

일시적 장애처리

위와 같이 장애가 난 노드를 어떻게 조치를 해야할까? 해당 노드에 읽기와 쓰기 연산을 금지해야 할까? 
sloppy quorum 접근법 을 이용하여 쓰기 연산 W개의 서버, 읽기 연산 수행할 R개의 서버를 해시링에서 고른다. (장애 상태 서버 무시) 
이것은 네트워크나 서버 문제로 장애 상태인 서버로 가는 요청을 다른 서버가 잠시 맡아 처리하는것을 의미
장애 서버가 복구되면 일관 반영한다. 

영구 장애 처리

그럼 영구적인 장애처리는 어떻게 할까?
anti-entropy 프로토콜을 구현하여 사본들을 동기화한다. 
사본 간 일관성 망가진 상태 탐지하고 전송 데이터의 최적화를 위해서는 Merkle 트리 사용 
(*Merkle 트리 - 해시 트리)

예를 들어서 key space 1-12 까지 일 때Merkle 트리는 

1. 네개의 버킷으로 나눈다.
2. 버킷에 포함된 각 키의 값을 uniform hash 함수를 적용하여 해 시 값을 계산
3. 버킷별로 해시 값을 계산 한후, 해당 해시 값을 레이블로 갖는 노드 생성
4. 자식 노드의 레이블로부터 새로운 해시 값을 계산 이진 트리 상향식 구성

이러면 루트 노트의 해시값을 비교했을 때 해시 값이 일치하면 두 서버는 같은 데이터를 갖는다. 

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

- 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, get(key), put(key, value)로 통신
- 중재자는 클라이언트에 키-값 저장소에 대한 proxy 역할을 하는 노드
- 노드는 안정 해시의 해시 링 위에 분포

모든 노드가 같은 책임을 지므로 SPOF 는 존재하지 않는다. 

 

쓰기 경로 

- 쓰기 요청이 커밋 로그 파일에 기록
- 데이터가 메모리 캐시에 기록
- 메모리 캐시가 가득차거나 사전에 정의된 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록 (Sorted-String Table) (키, 값) 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

읽기 경로

- 데이터가 메모리에 없는 경우 디스크에서 가져온다. 
- SSTable에 찾는 키가 있는지 효율적인 방법이 필요할텐데 Bloom filter 를 사용
- Bloom filter 를 통해 어떤 SSTable에 키가 보관되어있는지 확인 
- SSTable에서 데이터 가져온다. 
- 해당 데이터 클라이언트에 반환