Dev/etc

키-값 저장소 설계

ssyoni 2023. 2. 24. 10:47

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - ch5,6 정리

아키텍처 설계는 결국 트레이드 오프이다.

선택에 따른 장단점이 존재하기 때문에 구현하고자 하는 서비스의 방향성에 따라서 각 도구들의 장점과 단점들을 타협하거나 선택하게 된다.

5,6 장은 키-값 저장소를 설계하기 위해 어떤 점들을 고려해서 트레이드오프를 해야 하는지에 대한 대안점들을 제시해 준다.

5장 안정 해시 설계

서버 장애가 났을 때 유연하게 서버를 증설하고 삭제하는 일을 대비해서 요청이나 데이터를 여러 서버에 균등하게 나누는 것이 중요하다. (수평적 규모 확장성)

안정해시는 서버에 데이터나 요청을 어떻게 균등하게 나누는지에 대한 해답을 제시한다.

일반적인 해시 알고리즘을 통해서 서버 인덱스를 할당하는 방법을 먼저 알아보면

해시 키 재배치(refresh)문제

serverIndex = hash(key) % N

N개의 서버가 있다고 했을 때 해시 값을 계산한 다음 N(서버의 개수)로 나누었을 때의 값이 서버 인덱스

각각의 key들은 할당된 서버에 분배되어 저장된다.

ex) hash(key0) % 4 = 1이라면 key0에 보관된 데이터를 가져오기 위해서는 1번 서버에 접속해야 한다.

단점

서버가 추가되거나 기존 서버가 삭제되면 문제 생김. 위의 공식 그대로 적용했을 때 N의 값이 달라지면 나머지값인 서버인덱스의 값도 달라져서 재배치가 일어난다. 그럼 서버 1이 죽으면 나머지 서버 2,3,4에 키들이 할당되고, 서버 2에 있는 데이터 값을 못 가져오는 캐시미스(cashe miss)가 발생하게 된다.

안정해시

위의 해시 키 재배치 문제를 효과적으로 해결할 수 있음

테이블 크기가 조정될 때 오직 k/n 개의 키만 재배치하는 해시 기술. k=key, n=slot

ex) 키가 10개, 서버 노드가 3개라면 3개의 키만 재배치된다.

해시 공간과 해시 링

해시 공간의 범위를 정의한다.
해시 링의 형태로 생성한다.
해시 함수를 사용해서 서버 IP나 이름을 링 위에 배치한다.
링 위에 캐시 할 키를 해시 링 위에 배치한다.
키가 서버에 저장될 때 키의 시계 방향으로 링을 탐색해서 나오는 첫 번째 서버에 저장된다.
서버를 추가하게 된다면 추가된 부분에 위치한 키만 재배치해주면 된다.
서버가 제거되면 키 가운데 일부만 재배치된다.

문제점

파티션의 크기를 균등하게 유지하는 게 불가능
- 파티션이란? 서버와 서버 사이의 공간
- 파티션이 즉 해시 공간이고 해시 공간에 키가 저장될 수 있는 건데, 서버가 추가, 삭제될 때마다 해시 공간이 어디는 엄청 작아지고 어디는 엄청 큰 공간을 할당받게 되는 것이다.
키의 균등 분포를 달성하기가 어려움
- 어떤 서버는 키를 전혀 할당받지 않게 되고 또 어떤 서버는 많은 양의 키를 할당받게 된다.

가상노드(replica)

안정해시의 문제를 해결하기 위에 제안된 기법이다.

서버의 복제본이라고도 한다.

하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

서버의 가상노드는 여러 파티션에 고르게 위치하게 된다.

키 저장

시계방향으로 링을 탐색하다 만나는 최초의 가상 노드에 키가 저장된다.
가상 노드의 개수를 늘리면 키의 분포는 더 균등해짐 - 표준편차가 작아지기 때문
- 표준편차 : 테이터가 어떻게 퍼져나갔는지 보이는 척도 (가상노드가 더 촘촘하게 분포되어 있을수록 분포는 점점 더 균등해지겠지?)
- 파지만 가상노드 저장할 공간이 더 많이 필요하게 되기 때문에 타협적 결정이 필요하다.

재배치할 키 결정

서버가 추가되거나 제거될 때는 제거하는 서버와 반시계 방향에 있는 서버 사이에 있는 키들이 재배치가 된다.

6장 키-값 저장소 설계

키 값 저장소란?

비 관계형 데이터베이스. 흔히 말하는 레디스나 nosql 등이 키값 저장소임.

특징

키-값 쌍에서 키는 유일해야 한다.
값은 키를 통해서만 접근할 수 있다.
키는 일반 텍스트일 수도 있고 해시값일 수도 있다.
값은 Object 객체일 수도 있고 list일 수도 있고 자유롭다.
AWS DynamoDB, memcached, Redis 등이 있다.

put(key, value), get(key) 연산을 지원하는 키-값 저장소를 설계하는 예시를 통해 알아보자.

요구사항

키-값 쌍의 크기는 10KB 이하
큰 데이터를 저장할 수 있어야 한다.
높은 가용성을 제공해야 한다. 시스템 장애가 있더라도 빨리 응답해야 한다.
높은 규모 확장성을 제공해야 한다. 트래픽 양에 따라 자동적으로 서버 증설/삭제 가 이루어져야 한다.
데이터 일관성 수준은 조정이 가능해야 한다.
응답 지연시간(latency)이 짧아야 한다.

단일 서버 키-값 저장소

한 대의 서버에 키-값 저장소를 전부 메모리에 해시테이블로 저장해 버리면 접근할 때 속도는 빠르겠지만 많은 데이터를 전부 메모리 안에서 관리하는 것은 불가능하다.

이를 개선하기 위해서는

데이터 압축
자주 쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장

등의 방법이 있겠지만, 결국 한계점이 찾아온다.

때문에 대용량 데이터를 보관하려면 분산 키-값 저장소를 만들어야 한다.

분산 키-값 저장소

분산 키-값 테이블은 분산 해시 테이블이라고도 말하며 분산 시스템을 설계할 때는 CAP정리를 이해하고 있어야 한다.

CAP 정리

데이터 일관성(consistency)
가용성(availability)
파티션 감내(partition tolerance)

이 세 가지를 동시에 만족하는 분산시스템은 불가능하다는 정의

데이터 일관성

→ 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접근하든지 간에 언제나 같은 데이터를 조회할 수 있어야 한다.

가용성

→ 분산 시스템에 접속하는 모든 클라이언트는 일부 노드에 장애가 발생하더라도 상관없이 항상 응답을 받을 수 있어야 한다.

파티션 감내

→ 파티션 : 두 노드 사이에 통신 장애 발생

→ 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다.

CP 시스템(일관성, 파티션감내)

AP 시스템(가용성, 파티션감내)

CA 시스템(일관성, 가용성) → 네트워크 장애는 피할 수 없는 일로 여겨지기 때문에 분산시스템에서 반드시 파티션 문제를 감내할 수 있도록 설계가 되어있어야 함. 때문에 CA시스템은 존재하지 않는다고 보면 됨

⇒ 즉 일관성을 포기하느냐, 가용성을 포기하느냐의 문제인 듯

사례)

분산시스템에서 데이터는 여러 노드에 복제되어 보관된다.

3대의 replica노드 n1, n2, n3에 데이터를 복제하여 보관하는 상황이라고 예시를 들어보자.

이상적 상태라면 n1에 저장된 데이터가 n2, n3에 저장되며 데이터 일관성과 가용성도 만족할 것이다.

하지만,

실제로 분산 시스템은 파티션 문제를 피할 수 없다. 파티션 문제가 발생했을 때 우리는 일관성과 가용성 하나를 선택해야 할 수밖에 없다.

만약 n3 노드에 장애가 발생하였다면?

클라이언트가 n1 or n2에 저장한 데이터는 n3에 전달되지 않는다.(일관성 선택)

→ 가용성을 포기한다면 n1, n2에 쓰기 연산을 중단시켜야 한다.

→ 은행권 시스템 같은 경우 데이터 일관성이 필수이기 때문에 가용성을 포기한다.(ex 계좌 조회할 때는 무조건 최신 정보를 조회할 수 았어야 해서 장애가 발행해서 최신정보를 못 가져오게 되면 상황 해결될 때까지 오류 반환)

2. n3에 기록되었으나 아직 n1, n2로 전달되지 않은 데이터가 있다면 n1, n2는 오래된 사본을 갖고 있게 된다(가용성 선택)

→ 일관성을 포기하고 가용성을 선택한다면 n1, n2 가 오래된 사본을 갖고 있을지라도 읽기 연산을 허용해야 한다.

→ 또한 n1, n2에 쓰기 연산도 같이 허용하여 파티션 문제가 해결된 뒤에 새 데이터를 n3으로 전송하게 된다.

때문에 요구사항에 맞게 CAP 정리를 적용해서 시스템 설계를 해야 한다.

시스템 컴포넌트

키-값 저장소 구현에 사용되는 핵심 컴포넌트 및 기술들

데이터 파티션
데이터 다중화(replication)
일관성(consistency)
일관성 불일치 해소(inconsistency resolution)
장애 처리
시스템 아키텍처 다이어그램
쓰기 경로(write path)
읽기 경로(read path)

데이터 파티션

데이터를 작은 파티션으로 분할한 후에 여러 서버에 나눠서 저장하는 것

고려사항
- 데이터를 여러 서버에 고르게 분산해야 한다
- 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있어야 한다.
해결방안
- 안정해시 사용
  - 규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 증설/삭제된다.
  - 다양성 : 각 서버 용량에 맞게 가상노드의 수를 조정할 수 있음. 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있다.

데이터 다중화

높은 가용성과 안정성 확보를 위해 데이터를 N개의 서버에 비동기적으로 다중화할 수 있다.

N : 튜닝 가능한 값
N개의 서버를 산정하는 방법
- 해시 링 위에 키를 배치한다.
- 시계 방향으로 링을 순회하면서 만나는 N개 서버에 데이터 사본을 보관한다.

하지만,

가상노드를 사용하게 되면 N개의 노드가 대응될 실제 물리서버의 개수가 N보다 작아질 수 있다.

때문에 노드를 선택할 때 같은 물리서버를 중복 선택하지 않도록 해야 한다.

왜냐면 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제가 발생하면 동시에 장애를 겪게 되기 때문이다.

따라서 안정성을 담보하기 위해 데이터의 사본은 다른 센터 서버에서 보관해야 한다.

데이터 일관성

여러 노드에 저장된 데이터들은 동기화도 고려해야 한다.

정족수 합의 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.

정족수란? 합의체가 의사(議事)를 진행하고 의결하는 데 필요한 최소의 구성원의 출석수.

N : 사본 개수
W : 쓰기 연산에 대한 정족수( 최소 W개의 서버에서 쓰기 연산 성공 응답을 받아야 쓰기 연산이 성공한 것으로 간주)
R : 읽기 연산에 대한 정족수(최소 R개의 서버로부터 응답을 받아야 읽기 연산 성공한 것으로 간주)

W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정이다.

R=1, W=N : 빠른 읽기 연산에 최적화된 시스템
- 읽기 연산 시 서버 한대로부터만 응답을 받으면 되기 때문에
W=1. R=N : 빠른 쓰기 연산에 최적화된 시스템
- 쓰기 연산시 서버 한대로부터만 응답을 받으면 되기 때문에
W+R> N : 강한 일관성이 보장됨
W+R≤N : 강한 일관성이 보장되지 않음

일관성 모델

강한 일관성:
- 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다.
- 클라이언트는 절대로 낡은 데이터를 보지 못한다
- 고가용성 시스템에 적합하지 않음(장애 나면 읽기, 쓰기 막아버리기 때문에)
약한 일관성:
- 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수도 있다.
- 고가용성 시스템에 적합(최신 데이터가 아니더라도 결과를 반환하기 때문에)
최종 일관성:
- 약한 일관성의 한 형태
- 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델이다.
- 클라가 최신 데이터 못 받을 수도 있는데, 이럴 경우 클라 단에서 해결함
  - 데이터 버전 정보 활용해서 일관성이 깨진 데이터 읽지 않도록 함

강한 일관성을 달성하기 위해서는 모든 사본에 쓰기 연산이 반영될 때까지 해당 데이터에 대한 읽기/쓰기 연산을 금지하는 것임.

이는 고가용성 서버에 적합하지 않다.

dynamoDB, 카산드라 같은 저장소는 최종 일관성 모델을 선택하고 있다.

최종 일관성 모델을 따를 경우에는 쓰기 연산이 병렬적으로 발생할 시에 일관성이 깨지게 되는데 이는 클라이언트 측에서 데이터 버저닝을 통해서 일관성이 깨진 데이터는 읽지 못하게 할 수 있다.

일관성 불일치 해소 : 데이터 버저닝

버저닝, 백터시계로 데이터 다중화 시에 일관성이 깨지는 문제를 해소할 수 있다.

버저닝이란? 데이터를 변경할 때마다 해당 데이터의 새 버전을 만드는 것

*데이터 일관성이 깨지는 사례

→ 두 개의 서버가 서로 통신하고 있는 n1, n2에게 get(”name”)을 요청할 경우 두 노드는 같은 결과인 “john”을 반환할 것이다.

이때 두 개의 서버가 동시에 name을 변경한다면? 충돌이 발생한 두 값을 갖게 된다. 이를 각각 v1, v2라고 하자.

이 충돌을 해결하려면 충돌을 발견하고 자동으로 해결할 버저닝 시스템이 필요하다.

*버저닝 시스템의 백터 시계의 동작 원리

백터 시계 : [서버, 버전]의 순서쌍. 어떤 버전이 선행, 후행 버전인지 아니면 다른 버전과 충돌이 있는지를 감지하는데 쓰인다.

D([S1, v1],[S2, v2],…,[Sn, vn])

D : 데이터

vi : 버전 카운터

Si : 서버 번호

EX) 어떤 데이터 D를 Si에 기록한다면?

[Si, vi]가 있으면 vi를 증가시킴
없으면 새로운 [Si, vi]를 만든다.

클라이언트가 데이터 D1을 시스템에 기록. 이때 쓰기 연산 처리한 서버는 Sx. → 백터시계 : D1([Sx, 1])
다른 클라이언트가 D1을 읽고 D2로 업데이트 한 다음 쓰기 연산. D2는 D1에 대한 변경이기 때문에 D1을 덮어쓴다. 이때 이전과 같은 서버 Sx가 쓰기연산 처리 → 백터시계 : D2([Sx,2])
다른 클라이언트가 D2를 읽어서 D3으로 갱신한 다음 쓰기연산. 이때 Sy서버가 처리 → 백터시계 : D3([Sx,2],[Sy, 1])
동시에 다른 클라이언트가 D2를 읽어서 D4로 갱신한 다음에 쓰기 연산. 이 때 Sz서버가 처리. → 백터시계 : D4([Sx,2],[Sx,1])
이후에 어떤 클라이언트가 D3, D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 된다. D2를 서버 Sy, Sx가 각각 다른 값으로 바꾸었기 때문에.

이때 클라이언트가 충돌을 해소한 후 서버에 다시 쓰기 연산 후 Sx 서버가 쓰기연산 처리하면 → 백터시계 : D5([Sx,3],[Sy,1],[Sz,1])

충돌 감지는 어떻게?

이전 버전에 포함된 모든 구성요소의 값이 이후 버전에 포함된 모든 구성요소 값보다 같거나 크지만 않으면 된다.

즉 어떤 버전 X, Y사이에 충돌이 있는지 보려면 Y의 구성요소 중에 X의 백터시계 동일서버 구성요소보다 작은 값을 갖는 것이 있는지 보면 된다.

ex) D([S0, 1],[S1,2]) ↔ D([S0, 2],[S1, 1]) 은 충돌

백터시계를 사용한 충돌 감지 및 해소 방법의 단점

충돌 감지 및 해소 로직이 클라이언트에 들어가야 해서 클라가 복잡해진다.
[서버:버전]의 순서쌍이 빨리 늘어난다. → 그 길이에 임계치를 설정하고, 그 이상으로 늘어나면 오래된 순서쌍을 제거해야 하는데 이러면 버전 간의 선후 관계를 정확하게 결정할 수 없어서 충돌 해소 과정의 효율성이 낮아진다.

⇒ 이런 문제는 없었다고 아마존이 말한다. 갓마존이 말했으니 대부분 기업에서도 적용해도 괜찮은 방법일 것이다.

장애처리

장애 감지 기법
장애 해소 전략

장애 감지

보통 한 대의 서버에서 장애가 발생하면 바로 처리하는 것이 아니라 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야만 실제로 장애가 발생했다고 간주한다.

모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 가장 손쉬운 장애 감지 방법 → 서버가 많을 때는 비효율 적임. 모든 노드를 연결해야 하기 때문에 …

이때 분산형 장애 감지 솔루션인 가십 프로토콜을 채택하면 보다 효율적으로 장애 감지 가능

가십 프로토콜 원리

각 노드들은 멤버심 목록 이란 것을 유지한다.
- 멤버십 목록 : 멤버 ID, 박동 카운터, 시간
각 노드들은 심장 뛰는 것처럼 주기적으로 박동수 증가시킴
각 노드들은 무작위로 선정된 노드를 대상으로 주기적으로 자기 박동 카운터 목록 전송
목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신함
어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.

2. 장애 해소 전략

1) 일시적 장애 처리

*엄격한 정족수 접근법

→ 읽기, 쓰기 연산 금지

*느슨한 정족수 접근법

→ 정족수 요구사항 강제하는 대신에, 쓰기 연산 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 선택한다. 이때 장애난 서버는 무시

→ 장애가 난 서버로 가는 요청은 임시로 다른 서버가 요청을 처리하게 된다.

→ 이 때 임시 서버는 서버가 장애난 동안 변경 사항들을 해당 서버가 복구되면 일괄 반영하여 데이터 일관성을 보존하게 된다. (임시 위탁 기법)

2) 영구 장애 처리

단서 후 임시위탁 기법은 일시적 장애 처리. 영구적인 노드 장애는 어떻게 처리해야 할까?

반-엔트로피 프로토콜을 구현하여 사본들을 동기화하자.

반-엔트로피 프로토콜

: 사본들을 비교해서 최신 버전으로 갱신하는 과정을 보관. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리를 사용한다.

STEP1) 서버1, 서버2의 키 공간을 N개의 버킷으로 나눈다.

STEP2) 버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용해서 해시값을 계산

STEP3) 버킷별로 해시값을 계산하고 그 값을 레이블로 갖는 노드를 만든다.

STEP4) 자식노드의 레이블로부터 새로운 해시값을 계산하여 이진트리를 상향식으로 구성해 나간다.

각각 서버1, 서버2의 머클트리 비교

root 노드의 해시값 비교
왼쪽 → 오른쪽 노드 순서로 비교해서 내려감
값이 다른 데이터를 갖는 버킷을 찾으면 해당 버킷들만 동기화한다.

머클 트리 유의할 점

실제로 쓰이는 시스템의 경우 버킷 하나의 크기가 매우 크다.

3) 데이터센터 장애 처리

정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생할 수 있음

→ 여러 물리적인 데이터 센터에 다중화하는 것이 중요함.

쓰기 경로

쓰기 요청이 디스크의 커밋 로그 파일에 기록된다.
데이터가 메모리 캐시에 기록된다.
메모리 캐시가 가득 차거나 사전에 정의된 임계치에 도달하게 되면 데이터는 디스크에 있는 SSTable에 기록된다.

읽기 경로

데이터가 메모리 캐시에 있는지 살핀다.
메모리 캐시에 없을 경우 블룸 필터를 사용해 어떤 SSTable에 찾는 키가 있는지 알아낸다.
데이터 조회 후 반환한다.

SSTable를 이용한 데이터 저장

SSTable(Sorted String Table)은 storage engine을 구성하기 위한 데이터 저장에 사용되는 데이터 구조 중에 하나이다. 이름 그대로 파일에 데이터가 정렬되어 저장되는게 특징이다.데이터는 key와 value로 구

velog.io