가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장 - 키-값 저장소 설계

Posted Dec 14, 2022 Updated Sep 12, 2024

By ,

31 min read

가상 면접 사례로 배우는 대규모 시스템 설계 기초 책 정리 글입니다.

개요

키-값 저장소는 키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스다. 여기에 저장되는 값은 이를 식별할 수 있는 고유한 키를 가져야하고, 이러한 연결 관계를 키-값 쌍(pair)이라고 한다.

put(key,value): 키-값 쌍을 저장소에 저장한다.
get(key): 인자로 주어진 키에 달린 값을 꺼낸다.

✏️ 문제 이해 및 설계 범위 확정

다음 특성을 갖는 키-값 저장소를 설계해본다고 한다.

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

✏️ 단일 서버 키-값 저장소

한 대 서버만 사용하는 키-값 저장소를 설계하는 것은 쉽다.

키-값 쌍 전부 메모리에 해시 테이블로 저장해버려 빠른 접근속도를 보장하게 하지만 모든 데이터를 메모리 안에 두는게 사실상 불가능하다. 이를 해결하기 위해서는 데이터 압축(compression)이나 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장하는 방법이 있다.

결국 개선의 일종이고 단 한 대로 모든 데이터를 저장하는 것은 벅찰 때가 있다. 그래서 분산 키-값 저장소를 만들 필요가 있다.

✏️ 분산 키-값 저장소

분산 해시 테이블이라고도 불리는 분산 키-값 저장소는 키-값 쌍을 여러 서버에 분산 시키는 방식이다.

분산 시스템을 설계할 때에는 CAP정리(Consistency, Availability, Partition Tolerance theorem)을 이해하고 있어야 한다.

CAP 정리

데이터 일관성(C), 가용성(A), 파티션 감내(P)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리다.

데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 봐야한다.
가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드가 장애를 발생하더라도 항상 응답을 받아야 한다.
파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생했음을 의미하는데, 이러한 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 뜻이다.

CAP 정리는 이들 가운데 어떤 두 가지를 충족하려면 나머지 하나는 희생되어여 한다는 뜻이다.

위 그림에서 일관성과 가용성을 가져가고 파티션감내를 희생한 CA시스템은 실세계에 존재하지 않는다고 한다. 왜냐하면 네트워크 장애는 피할 수 없는 일로 여겨져 파티션 감내를 할 수 있도록 분산 시스템은 설계되어야 하기 때문이다.

위의 설계 예시를 들려면 먼저 이상적인 상태를 봐야한다.

분산 시스템에서 데이터는 여러 노드에 복제되어 보관된다. 위 그림에서 n1, n2, n3는 노드이고, 모두 원본 데이터를 완벽히 복제한 상태이다. 이상적인 환경이라면 네트워크가 파티션이 일어나지 않을 환경이다. 이런 경우 데이터 일관성과 가용성도 만족된다.

실세계의 분산 시스템

하지만 분산 시스템은 파티션 문제를 피할 수 없다. 그리고 파티션 문제가 발생하면 우리는 일관성과 가용성 사이에서 하나를 선택해야 한다.

n3가 고장난 상태. n1, n2과 통신 불가능

일관성을 선택한다면 데이터 불일치 문제를 피하기 위해 n1,n2에 쓰기 연산을 중단시켜야하는데, 그렇게 하면 가용성이 깨진다. 은행 시스템처럼 어느 서버에 들어가든 계좌의 같은 정보를 조회해야하는 곳은 일관성을 양보하지 못한다. 하지만 쓰기 연산을 중단하여 최신 계좌를 반환하지 못하는데, 어쩔 수 없이 파티션 문제를 해결할 때까지 오류를 반환하는 수 밖에 없다.

가용성을 선택한다면 설사 낡은 데이터를 반환할 위험이 있더라도 계속해서 읽기 연산을 허용해야 한다. n1, n2는 계속 쓰기를 허용할 것이고, 파티션 문제가 해결 된 뒤에 새 데이터를 n3에 전송할 것이다.

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트 및 기술들이라고 한다.

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

데이터 파티션

대규모 애플리케이션의 경우 전체 데이터를 한 대 서버에 욱여 넣는것은 불가능하다. 그렇기에 데이터를 작은 파티션들로 분할하여 여러 대의 서버에 저장하는게 좋다.

데이터를 파티션으로 나눌때 고려해야할 사항들이 있다.

데이터를 여러 서버에 고르게 분산할 수 있는가
노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

저번 포스팅(5장)에서 안정 해시에 대해 이야기했고, 이 기술이 이런 문제를 푸는데 적합한 기술이다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화할 방법이 필요하다.

위에서 말한 안정 해시 기준으로 key0이 들어온다치고 그 지점으로부터 시계방향으로 순회하면서 N개의 노드를 거치면서 데이터 사본을 저장하는 것이다.

N이 3개이면 key0은 s1, s2, s3에 저장된다.

하지만, 가상 노드를 사용하면 가상 노드도 순회하면서 복사본을 저장하고 카운터를 올려주므로 실제 물리적 서버는 1군데만 거칠 수 있다.(s1이라는 서버를 가기 전에 s1을 가리키는 가상 노드 3개를 이미 거친 경우)

이런 경우를 대비하기 위해 같은 물리 서버를 중복 선택하지 않도록 해야한다.

같은 데이터 센터에 속한 노드들은 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 수 있으므로 데이터 사본들을 다른 센터의 서버에 보관하고, 센터의 네트워크 품질을 높이는 방법도 고려해봐야 한다.

데이터 일관성

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

N: 사본 개수
W: 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야한다.
R: 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 읽기 연산이 성공했다는 응답을 받아야한다.

N=3인 경우

W=1의 의미는 쓰기 연산이 성공했다고 판단하기 위해서는 중재자는 최소 한 대(1)의 서버에서 쓰기 성공 응답을 받아야 한다는 뜻이다.

위 예제에서 만약 s1에서 쓰기 연산에 성공했다고 응답을 받으면 s0, s2는 응답을 기다릴 필요가 없는 것이다.

중재자는 클라이언트와 노드 사이에서 proxy역할을 한다.

W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정이다. W=1 또는 R=1이면 중재자는 한 군데에서만 응답을 받으면 되니 응답속도가 빠를 것이다. W나 R의 값이 1보다 크면 응답속도는 느릴테지만 데이터 일관성의 수준은 향상될 것이다.

W+R > N인 경우에는 강한 일관성이 보장된다. 저 식을 만족하기 위해서는 적어도 하나의 노드는 쓰기와 읽기 둘 다 응답을 했기 때문이다.

그렇기에 W, R을 적절한 값으로 정해야한다. 밑은 예시라고 한다.

W=N, R=1: 빠른 읽기에 최적화된 시스템
R=N, W=1: 빠른 쓰기에 최적화된 시스템
W+R > N: 강한 일관성이 보장
W+R <= N: 강한 일관성이 보장되지 않음.

일관성 모델

일관성 모델은 데이터 일관성의 수준을 결정한다.

강한 일관성: 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다.
약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 받지 못할 수도 있다.
최종 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국 모든 사본에 반영(동기화) 되는 모델이다.

강한 일관성을 달성하려면, 모든 사본에 쓰기 연산의 결과가 반영되기 전까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다. 이 방법은 고가용성 시스템에 적합하지 않은데, 새로운 요청의 처리가 중단되기 때문이다.

카산드라, 다이나모 같은 저장소는 최종 일관성 모델을 채택하고 있다. 이 경우 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있는데, 이 문제는 클라이언트가 해결해야 한다고 한다. 일관성이 깨진 데이터를 읽지 않도록 하는 방법 중 데이터 버저닝이라는 것이 있다.

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

데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다.

다음과 같은 상황에서 데이터 일관성이 깨지게 될 것이다.

어떤 데이터의 사본이 노드n1, n2에 저장되어 있다.

만약 서버1과 서버2에서 노드n1, n2에 저장된 값을 동시에 수정하려고 한다면 충돌이 일어날 것이다.

n1에 저장된 값의 버전을 v1이라하고, n2에 저장된 값의 버전을 v2라하자.

이렇게 v1과 v2 사이의 충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요한데 벡터 시계(vector clock)은 이러한 문제를 푸는데 보편적으로 사용되는 기술이다.

벡터 시계

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이다.
D([S1,v1],[S2,v2]…[Sn,vn])처럼 표현한다고 가정하고 D는 데이터, $ S_i $는 서버, $ v_i $는 버전이다.
만일 데이터 D를 $ S_i $에 기록하면 아래 작업 가운데 하나를 수행해야 한다.

[Si, vi]가 있으면 $ v_i $을 증가시킨다.
그렇지 않으면 [Si, 1]을 만든다.

충돌 났을때 벡터 시계가 처리하는 방법

벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지 쉽게 판단할 수 있다. 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소의 값보다 같거나 큰지만 보면 된다.

D([s0,1],[s1,1])은 D([s0,1],[s1,2])의 이전 버전이다. 따라서 두 데이터 사이에 충돌은 없다.

어떤 버전 X와 Y 사이에 충돌이 있는지 확인하려면 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소의 값보다 작은지 보면 된다.(Y가 최신화 데이터라는 기준)

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

벡터 시계를 사용해 충돌을 감지하고 해소하는 방법에는 두 가지 단점이 있다.

충돌 감지 및 해소 로직이 클라이언트에 들어가, 클라이언트 구현이 복잡해짐.
[서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다는 점.

이 문제를 해결하기 위해서는 어떤 임계치를 설정하고 임계치 이상으로 길어지면 오래된 순서쌍을 제거하도록 해야하는데, 이렇게 하면 버전 간 선후 관계를 정확하게 결정할 수 없기에 효율성이 낮아진다.

하지만 다이나모 데이터베이스에 관계된 문헌에 따르면 아마존은 실제 서비스에서 그런 문제가 벌어지는 것을 발견한 적이 없다고 한다.

장애 처리

장애를 처리하기 위해서는 우선 장애 감지(failure detection) 기법들과 장애 해소(failure resolution)전략들을 볼 필요가 있다.

장애 감지

분산 시스템에서 한 대 서버(B) “A서버가 죽었습니다.” 라고해서 서버A를 바로 장애처리를 하지 않는다. 보통 두 대 이상의 서버가 똑같이 “A서버가 죽었습니다.”라고 해야 장애가 발생했다고 간주하게 된다.

이는 모든 노드 사이에 멀티캐스팅(multicasting) 채널을 구축하는 것이고, 장애를 감지하기 가장 손쉬운 방법이다. 하지만 이 방법은 노드 수가 많아지면 점점 비효율적으로 동작할 것이다.

가십 프로토콜(gossip protocol)가 같이 분산형 장애 감지 솔루션을 채택하는 편이 보다 효율적이다.

가십 프로토콜의 동작원리는 다음과 같다.

각 노드는 멤버십 목록을 유지한다. 멤버십 목록에는 각 멤버 ID와 그 박동 카운터 쌍의 목록이다.
각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
각 노드는 무작위로 선정된 노드들에게 주기적으로 자기의 박동 카운터 목록을 보낸다.
박동 카운터 목록을 받은 노드는 멤버십 목록을 최신값으로 갱신한다.
어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애상태인 것으로 간주한다.

위의 예시는 다음과 같이 동작한다.

노드 s0은 노드s2(멤버ID=2)의 박동 카운터가 오랫동안 증가되지 않은것을 발견한다.
노드s0은 노드s2를 포함하는 박동 카운터 목록을 무작위로 선택된 다른 노드들에게 전달한다.
노드s2의 박동 카운터가 오랫동안 증가되지 않았음을 발견한 모든 노드들은 해당 노드를 장애 노드로 표시한다.

일시적 장애 처리

가십 프로토콜로 장애를 감지하면 가용성을 보장하기 위해 필요한 조치를 취해야 한다.

위에서 설명한 정족수 합의의 느슨한 정족수 접근법을 통해 가용성을 올릴 수 있다. 엄격한 정족수 접근법을 쓰면 데이터 읽기와 쓰기 연산을 금지해야하기에 가용성이 떨어지기 때문이다.

네트워크나 서버 문제로 장애 상태인 서버로 가는 요청들은 다른 서버들이 임시로 맡아 처리한다. 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서(hint)를 남겨둔다. 이러한 방식을 단서 후 임시 위탁(hinted handoff)기법이라 부른다.

이러한 상태에서 노드s2에 대한 읽기 쓰기 연산은 일시적으로 s3가 처리할 것이다. s2가 복구되면 s3은 갱신된 데이터를 s2로 인계할 것이다.

영구 장애 처리

위의 임시 위탁 기법은 일시적 장애 처리를 위함이고, 영구 장애 처리를 위해서는 반-엔트로피(anti-entropy)프로토콜을 사용해야 한다. 이 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다. 또한 일관성이 망가진 데이터를 탐색하고 전송 데이터의 양을 줄이기 위해 머클(Merkle)트리를 사용한다.

밑은 키 공간 1부터 12까지일 때 머클 트리를 만드는 예제이다.

1단계: 키 공간을 버킷(bucket)으로 나눈다. (예제에서는 4개)