[대규모 시스템 설계] 키-값 저장소 설계

Gmini.Y·2024년 4월 16일

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

목록 보기

10/14

Key-Value 저장소는 비 관계형 데이터베이스이다. Key는 고유한 값이어야하며 짧을 수록 성능이 좋다. 값은 보통 무엇이 오든 상관하지 않는다. 대표적으로 다이나모디비, 레디스, memcached 등이 있다.

문제 이해 및 설계 범위 확정

읽기, 쓰기, 메모리 사용량 사이에 어떤 균형을 찾아 데이터의 일관성과 가용성 사이에서 타협적 결정을 내린다.
이번 장에서 설계할 특성은 아래와 같다.

키-값 쌍의 크기는 10KB 이하
큰 데이터 저장 가능
높은 가용성
높은 규모 확장성, 트래픽 양에 따라 자동 서버 증설/삭제 가능
데이터 일관성 수준은 조정 가능
짧은 응답 지연시간

단일 서버 키-값 저장소

단일 서버 키-값 저장소를 설계하는 것은 쉽고(전부 메모리에 해시 테이블로 저장) 빠른 속도를 보장하지만 메모리 한계로 인해 규모 확장이 필요하게 된다.
많은 데이터를 저장하기 위해서는 분산 키-값 저장소를 만들 필요가 있다.

분산 키-값 저장소

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

CAP 정리

CAP 정리는 데이터 일관성, 가용성, 파티션 감내 세 가지 요구사항을 모두 만족하는 설계는 불가능하다는 정리다.

데이터 일관성 : 모든 클라이언트가 접속한 노드와 상관없이 언제나 같은 데이터에 접근한다.
가용성 : 일부 노드에 장애가 발생하더라도 항상 응답이 가능하다.
파티션 감내 : 두 노드 사이에 통신장애가 발생하더라도 시스템이 동작 해야 한다.

이들 가운데 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다.

CA 시스템은 파티션 감내를 지원하지 않는다. 그러나 네트워크 장애는 피할 수 없으므로 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 그러므로 CA 시스템은 존재하지 않는다.

아래 예시는 노드 n1, n2, n3에 데이터를 복제하여 보관하는 상황이다.

실세계의 분산 시스템

n3에 장애가 발생하여 n1, n2와 통신할수 없다. 따라서 n1, n2에 기록한 데이터는 n3에 전달되지 않고 n3에 저장됐지만 n1, n2로 전달되지 않은 데이터가 있다면 n1, n2는 오래된 사본을 가지고 있게 된다.

가용성 대신 일관성을 선택하는 CP 시스템에서는 모든 쓰기 연산을 중지 시킨다. 가용성은 깨진다.
일관성 대신 가용성을 선택하면 오래된 데이터를 반환할 위험이 있어도 계속 연산을 허용한다. 파티션 문제가 해결된 뒤에 업데이트한다.

시스템 컴포넌트

이번 절에 다루는 내용은 많이 알려진 키-값 저장소인 다이나모, 카산드라, 빅테이블의 사례를 참고한다.

데이터 파티션

안정 해시를 통해 고른 데이터 분산과 노드 추가 삭제시 데이터를 최소로 갱신하도록 설계할 수 있다.
안정 해시로 데이터 파티션을 하면 아래와 같은 장점이 있다.

규모 확장 자동화 : 시스템 부하에 따라 서버 자동으로 추가/삭제
다양성 : 각 서버의 성능에 맞게 가상 노드 개수를 조정할수 있다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화(replication)한다.
해시 링에서 키가 순회하면서 만나는 N개의 서버에 데이터 사본을 저장한다. 아래는 N=3 일 때 예제이다. key0는 s1. s2. s3에 저장된다.

가상 노드를 사용하면 실제 물리 서버가 중복될 수 있으므로 중복 선택하지 않도록 구현한다. 또한 데이터 센터 역시 중복되지 않도록 구현한다.

데이터 일관성

다중화된 데이터는 적절히 동기화 되어야 한다. 정족수 합의 프로토콜을 사용한다.

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

W, R. N의 값을 정하는 것은 레이턴시와 데이터 일관성 사이의 트레이드 오프를 찾는 전형적인 과정이다. W나 R이 커지면 데이터 일관성은 향상되지만 레이턴시가 길어진다.
W + R > N인 경우에는 강한 일관성이 보장된다.

R=1, W=N : 빠른 읽기 연산
W=1, R=N: 빠른 쓰기 연산
W + R > N: 강한 일관성 보장 (보통 N=3, W = R = 2)
W + R <= N: 강한 일관성이 보장되지 않음

일관성 모델

강한 일관성: 모든 읽기 연산은 항상 가장 최근에 갱신된 결과를 반환한다. 모든 사본에 동기화 될 때까지 읽기/쓰기 금지. 고가용성 시스템에는 적합하지 않다.
약한 일관성: 읽기 연산은 최신 값을 반환하지 못할 수도 있다.
결과적 일관성: 갱신 결과가 결국에는 모두 동기화 되는 모델. 다이나모, 카산드라는 결과적 일관성 모델. 일관성이 깨지는 문제는 데이터 버전 정보를 활용해 클라이언트가 해결.

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

버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만든다. 각 버전의 데이터는 변경 불가능하다.
서버 1과 서버 2가 동시에 다른 값으로 "name"을 변경한다면 충돌이 나게 된다. 이러한 충돌을 해결하기 위해 벡터 시계를 사용한다.

벡터 시계는 D([S1, v1], [S2, v2], ..., [Sn, vn])이라고 표현하자. D는 데이터, S는 서버 번호, v는 버전 카운터 이다.
데이터 D를 서버 Si에 기록하면, 시스템은 [Si, vi] 가 있다면 vi를 증가시키고 없으면 [Si, 1]을 만들게 된다.

틀라이언트가 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], [Sz, 1])이 된다.
클라이언트가 D3와 D4를 읽으면 D2가 Sy, Sz에 의해 다른 값으로 바뀌었다는 것을 알 수 있으므로 충돌이 있다는 것을 알 수 있다(충돌 감지 방법은 후에 알아본다). 이 충돌은 클라이언트가 해소한 후에 서버에 기록한다. 벡터 시계는 D5([Sx, 3], [Sy, 1], [Sz,1])이 된다.

버전 Y에 포함된 모든 구성 요소 값이 버전 X보다 같거나 크면 버전 Y는 버전 X 이후의 충돌이 없는 버전이다.
만약 버전 Y에 포함된 구성 요소 중 X 보다 작은 값을 갖는 것이 있으면 충돌된 값이다. 모든 값이 작다면 Y가 X의 이전 값이다.
예를 들어 D([s0, 1], [s1, 2])와 D([s0, 2], [s1, 1])은 충돌한다.

벡터 시계를 사용하면 충돌 감지 및 해소 로직이 클라이언트에 들어가므로 구현이 복잡해진다. 또한 벡터 시계의 개수가 굉장히 빨리 늘어나므로 어떤 임계치를 정하고 그 이상 길이가 길어지면 오래된 백터 시계 값을 제거하도록 한다. 그러나 이렇게 하면 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지게 된다.

장애 감지

보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주한다. 모든 노드 사이에 채널을 구축하는 것이 가장 간단하지만 서버가 많아지면 연결수가 엄청나게 증가하므로 비효율적이라서 가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 것이 보다 효율적이다.

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

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

일시적 장애 처리

시스템이 장애 감지시 가용성 보장을 위해 필요한 조치를 한다.

엄격한 정족수 : 읽기와 쓰기 연산을 금지한다.
느슨한 정족수 : 장애 서버는 무시하고 쓰기 연산을 수행할 W개의 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다.

장애 서버로 가는 요청은 잠시 다른 서버가 맡아 처리하면서 그에 관한 단서를 남겨둔다. 서버 복구시 일괄 반영하여 데이터 일관성을 보존한다.

영구 장애 처리

반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화한다. 반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정이 포함된다.
사본 간의 일관성이 망가진 상태를 탐지하기 위해 머클 트리를 사용한다.

머클 트리 구현 예제

키 공간을 다음과 같이 버킷으로 나눈다.
버킷에 보함된 각각의 키에 균등 분포 해시 함수를 적용해 해시 값을 계산한다.
버킷별로 해시값을 계산한 후 , 해당 해시 값을 레이블로 갖는 노드를 만든다.
자식 노드의 레이블로부터 새로운 해시 값을 계산하여 이진트리를 만든다.

루트 노드 해시값이 같다면 두 서버는 같은 데이터를 갖는 것이다. 그 값이 다른 경우 자식 노드의 해시 값을 아래쪽으로 비교하며 탐색해가면서 다른 데이터를 갖는 버킷을 찾는다. 그리고 그 버킷만 동기화 한다.

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

클라이언트는 get(key), put(key) API 통신한다.
중재자는 프록시 역할을 한다.
노드는 안정 해시의 해시 링 위에 분포한다.
노드가 자동으로 추가/삭제할 수 있도록 시스템은 완전히 분산된다.
데이터는 여러 노드에 다중화된다.
모든 노드가 같은 책임을 지므로 SPOF는 존재하지 않는다.

각 노드는 다음의 기능 전부를 지원한다.

쓰기 경로

아래는 카산드라의 사례이다.

쓰기 요청이 커밋 로그에 기록된다.
데이터가 메모리 캐시에 기록된다.
메모리 캐시가 가득차거나 어던 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다. SSTable은 Sorted-String Table로 정렬된 리스트 형태로 관리하는 테이블이다.

읽기 경로

캐시에 데이터를 먼저 확인한다. 없으면 어느 SSTable에 찾는 키가 있는지 알아내기 위해 블룸 필터를 사용한다.

1. 데이터가 메모리에 있는지 검사한다. 없으면 2로 간다.
2. 데이터가 메모리에 없으므로 블룸 필터를 검사한다.
3. 블룸 필터를 통해 어떤 SSTable에 데이터가 보관되어 있는지 알아낸다.
4. SSTable에서 데이터를 가져온다.
5. 해당 데이터를 클라이언트에 반환한다.