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

키-값 저장소 (key-value store) 는 데이터를 '키-값' 쌍으로 저장하는 비 관계형 데이터베이스이다. 키는 저장소에서 유일해야 하며, 값은 키를 통해서만 접근할 수 있다. 키는 텍스트나 해시 값일 수도 있고, 값은 문자열이나 리스트, 또는 객체일 수도 있다. 주로 레디스, 아마존 다이나모, memcached 등이 사용된다.

 

이 장에서는 다음의 두가지 연산을 지원하는 키-값 저장소를 설계해본다.

- put(key, value): 키-값 쌍을 저장소에 저장한다.
- get(key): 인자로 주어진 키에 매핑된 값을 반환한다.

1. 문제 이해 및 설계 범위 확정

키-값 저장소를 설계할 때는 키-값 쌍의 크기, 데이터의 크기, 가용성, 확장성, 데이터 일관성, 응답 지연시간 등을 고려해야 한다. 이러한 요소들은 사용하는 목적에 따라 타협하며 결정해야 한다.

2. 단일 서버 키-값 저장소

단일 서버 키-값 저장소의 경우 간단하게 메모리에 해시 케이블로 구현할 수 있다. 그러나 이 방법은 모든 데이터를 메모리에 두기 때문에 용량의 문제가 있다. 이러한 문제를 해결하기 위해서 데이터를 압축하거나 자주 쓰이는 데이터만 메모리에 로드하고 나머지는 디스크에 저장하는 등의 방법을 사용할 수 있다.

 

그러나 이러한 개선에도 단일 서버는 한계가 있다. 이러한 단계에 다다르면 분산 키-값 저장소를 고려해야 한다.

3. 분산 키-값 저장소

분산 키-값 저장소는 분산 해시 테이블이라고도 부른다. 이러한 시스템을 설계할 때는 CAP 정리 (consistency, availability, partition tolerance theorem) 에 대한 이해가 필요하다.

- CAP 정리

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

 

- 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속하든 언제나 같은 데이터를 보게 되어야 한다.
- 가용성: 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
- 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생겨도 시스템이 계속 동작해야 함을 의미한다.

 

CAP 정리는 이들 가운데 어떤 두 가지를 충족하려면 나머지 한 가지를 희생해야 한다는 것을 의미한다. CAP 정리를 기반으로 어느 두 가지를 만족하느냐에 따라 CP 시스템, AP 시스템, CA 시스템으로 구분할 수 있다.

 

키-값 저장소를 사용하는 목적에 따라 어떤 요소들을 만족시키도록 할 것인지 결정하고 구현해야한다.

- 시스템 컴포넌트

1) 데이터 파티션

대규모 애플리케이션의 경우 데이터를 작은 파티션 단위로 여러 서버에 분산하여 저장해야 한다. 파티션 단위를 나눌 때에는 다음의 문제를 고려해야 한다.

 

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

 

이러한 문제는 5장에서 정리한 안정 해시를 사용하여 해결할 수 있다. 안정 해시를 사용하면 한 서버에 부하가 걸리지 않게 파티션 서버를 정하고 서버 추가, 삭제에 자동으로 대응할 수 있게 된다.

2) 데이터 다중화

높은 가용성과 안정성을 위해서는 원본 데이터를 N개의 서버에 다중화할 필요가 있다. 안정 해시를 기반으로 설계한다면 특정 키를 기준으로 시계 방향으로 링을 순회하면서 만나는 N개의 서버에 데이터 사본을 저장하도록 하여 다중화 할 수 있다.

 

가상 노드를 사용하다 보면 선택된 다중화 노드의 실제 물리 서버의 개수가 N개 보다 작아질 수 있다. 이러한 문제에는 같은 물리 서버를 중복 선택하지 않도록 해야한다.

3) 데이터 일관성

다중화된 데이터는 동기화가 필요하다. 읽기/쓰기 연산의 일관성을 보장하기 위해서 정족수 합의 (Quorum Consensus) 프로토콜을 사용할 수 있다.

 

N = 사본 개수
W = 쓰기 연산에 대한 정족수
R = 읽기 연산에 대한 정족수

 

정족수 합의 프로토콜은 각 연산에 대해 정족수로 설정된 서버로부터 연산에 대한 성공 응답을 받아야 한다. 쓰기의 경우 W 값만큼의 서버로부터 쓰기 연산에 대한 성공 응답을 받아야하고 읽기 연산의 경우 R 값만큼의 응답이 필요하다.

 

W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정이다. W나 R이 1인 구성의 경우 하나의 서버로부터만 응답을 받으면 되기 때문에 응답 속도는 빠르다. 반면에 1보다 클수록 응답 속도는 느리지만 데이터의 일관성 수준이 향상될 것이다. N < W + R 인 경우에는 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹치기 때문에 강한 일관성이 보장된다.

 

이러한 개념을 이해하고 상황과 목적에 맞게 값을 설정해야 한다.

 

일관성 모델

일관성 모델은 데이터 일관성 수준을 결정하는 요소로 다음과 같은 종류가 있다.

 

- 강한 일관성 (strong consistency): 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 클라이언트는 절대로 낡은 (out-of-date) 데이터를 보지 못한다.
- 약한 일관성 (weak consistency): 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못한다.
- 최종 일관성 (eventual consistency): 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영 (동기화) 되는 모델이다.

 

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

데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성도 높아진다. 버저닝과 벡터시계는 그 문제를 해소하기 위해 등장한 기술이다.

 

버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다. 따라서 각 버전의 데이터는 변경 불가능하다.

 

벡터시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이다. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 사용된다. 데이터를 서버 S에 기록하면 시스템은 아래와 같은 작업을 수행한다.

 

- [S, v] 가 존재하면 v를 증가시킨다. (v는 기록되는 데이터에 대한 버전)
- 존재하지 않으면 [S, 1]를 생성한다.

 

벡터 시계를 사용하면 어떤 버전이 이전 버전인지 쉽게 판단할 수 있다. 두 버전을 비교할 때는 한 버전에 포함된 모든 구성 요소의 값이 다른 버전에 포함된 모든 구성요소의 값보다 같거나 큰지만 보면 된다. 예를들어 벡터 시계 D([S0, 1], [S1, 1]) 은 D([S0, 1], [S1, 2]) 보다 이전 버전이다. 만약 두 버전 간의 충돌이 있는지 보려면 두 버전 간의 요소를 비교했을 때 큰 값과 작은 값들을 모두 포함하고 있는지를 보면 된다.

 

충돌을 감지하고 이를 해소하는 방법에는 단점이 있는데, 첫번째는 충돌 감지 및 해소 로직이 클라이언트에 들어가야한다는 것이다. 두 버전간의 충돌이 감지되는 경우 클라이언트는 이를 해소한 후에 서버에 기록하게 된다. 이때문에 클라이언트의 구현이 복잡해진다.

 

두번째는 [서버, 버전]의 순서쌍이 굉장히 빠르게 늘어난다는 것이다. 이 문제를 해결하기 위해서는 크기에 대한 임계치를 설정하고 임계치 이상으로 커지는 경우 오래된 순서썅을 벡터 시계에서 제거하도록 해야한다.

 

장애 감지

분산 시스템에서는 효율을 위해 가십 프로토콜 (gossip protocol) 같은 분산형 장애 감지 솔루션을 채택한다. 가십 프로토콜의 동작 원리는 다음과 같다.

 

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

 

일시적 장애 처리

가십 프로토콜로 장애를 감지했다면, 시스템은 가용성을 보장하기 위해 조치를 취해야 한다. 엄격한 정족수 접근법을 쓴다면, 읽기와 쓰기 연산을 금지해야 할 것이다.

 

느슨한 정족수 접근법은 보다 완화된 방식으로 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 정상 서버와 읽기 연산을 수행할 R개의 정상 서버를 해시 링에서 고른다. 이때 장애 서버는 무시한다.

 

장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아서 처리한다. 이떄 임시로 쓰기 연산을 처리한 서버는 그에 대한 단서를 남겨두어 후에 서버 복구시에 일괄 반영 할 수 있도록 한다. 이러한 장애 처리 방안을 단서 후 임시 위탁 (hinted handoff) 기법이라고 한다.

 

영구 장애 처리

영구적인 장애 처리를 위해서는 반-엔트로피 프로토콜을 사용한다. 반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클 트리를 사용할 것이다.

 

머클 트리는 해시 트리라고도 불리며, 각 노드에 자식 노드들에 보관된 값의 해시, 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리이다. 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있다.

 

두 머클 트리의 비교는 루트 노드부터 시작하여 해시값이 다른 노드 들을 향해 값을 비교해 나간다. 이를 반복해서 아래쪽으로 탐색하다 보면 다른 데이터를 가진 버킷을 찾을 수 있다. 이렇게 탐색한 버킷의 값을 동기화 하면 된다.

 

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

키-값 저장소의 아키텍처는 다음과 같이 구성된다.

 

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

 

완전히 분산되게 설계했기 때문에 각가의 노드가 클라이언트 API, 장애 감지 및 복구, 다중화, 데이터 충돌 해소 등등을 지원할 수 있어야 한다.