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

 

개발에서 키-값은 굉장히 중요하다. 데이터를 저장할 때 이름표처럼 붙는 고유한 식별자인 키를 기준으로 원하는 값을 빠르게 찾아낼 수 있다. NoSQL에서도 저장된 값을 가져올 때 키(key)를 식별자로 값을 꺼내온다. 이러한 연결 관계를 "키-값" 쌍 이라고 한다. 키는 식별자이기 때문에 중복될 수 없다. name과 같이 일반 텍스트가 키가 될 수 있고, 리스트 혹은 해시 값이 키일 수도 있다. 성능상 키의 길이가 짧을수록 좋다.

 

6장에서는 이러한 키-값 쌍을 저장하고(put), 키에 달려있는 값을 꺼내는(get) 키-값 저장소를 설계해 볼 것이다.

 

문제 이해 및 설계 범위 확정

완벽한 설계는 없지만, 우리는 최대한 균형잡힌 저장소를 설계해야 한다. 데이터 일관성과 가용성 사이에서 타협적 결정을 내린 설계가 좋다. 6장에서는 아래의 특성을 갖는 키-값 저장소를 설계할 것이다.

 

 ⦁ 키-값 쌍의 크기는 10KB 이하이다.

 ⦁ 큰 데이터를 저장할 수 있어야 한다.

 ⦁ 높은 가용성을 제공해야 한다. 시스템이 장애가 있어도 빨리 응답해야 한다.

 ⦁ 높은 규모 확장성을 제공해야 한다. 트래픽 양에 따라 서버 증설/삭제가 이루어져야 한다.

 ⦁ 데이터 일관성은 조절 가능해야 한다.

 ⦁ 응답 지연시간이 짧아야 한다.

 

단일 서버 키-값 저장소

단일 서버가 사용하는 키-값 저장소 설계는 쉽다. 그냥 키-값 쌍을 모두 해시 테이블로 저장하면 된다. 이 방식은 빠르긴 하지만 모든 데이터를 메모리에 두는 것이 불가능할 수 있어 데이터를 압축하거나 자주 쓰이는 데이터만 디스크에 저장하는 것이 좋다.

 

분산 키-값 저장소

단일 서버로는 부족하기 때문에 스케일 아웃을 통하여 분산 키-값 저장소로 확장하고, 분산 해시 테이블이라고 부른다. 분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 한다.

 

CAP 정리

CAP 정리는 다음 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능 하다는 정리이다.

 

 ⦁ 데이터 일관성 (Consistency) - 분산 시스템에 접속하는 클라이언트는 어떤 노드던 같은 데이터를 보게된다

 ⦁ 가용성 (Availability) - 분산 시스템에 접속하는 클라이언트는 항상 응답을 받을 수 있다

 ⦁ 파티션 감내 (Parition tolerance) - 두 노드 사이에 네트워크 통신 장애가 일어나도 시스템은 동작한다

 

 

 

따라서 키-값 저장소는 세 가지 요구사항 CAP 중 어떤 두 가지를 만족하는지에 따라서 저장소를 분류할 수 있다. 파티션이란, 두 노드 사이에 장애가 발생하였음을 의미한다.

 

 ⦁ CP 시스템 : 가용성을 희생하더라도 일관성과 파티션 감내를 지원하는 저장소

 ⦁ AP 시스템 : 데이터 일관성을 희생하더라도 가용성과 파티션 감내를 지원하는 저장소

 ⦁ CA 시스템 : 일관성과 가용성을 지원하지만, 통상적으로 네트워크 장애를 피할 수는 없기 때문에 분산 해시 테이블은 반드신 파티션 문제를 감내해야 한다!

  → 따라서 CA 시스템은 존재하지 않는다..!

 

구체적인 사례를 예시로 들어서 알아보자. 분산 시스템에서 데이터는 여러 노드에 복제되어 저장된다.

 

 

이상적인 환경이라면 네트워크 파티션되는 상황은 일어나지 않기 때문에 n1에 기록된 데이터는 n2와 n3에 복제된다. 지금 상황은 데이터 일관성과 가용성도 만족하는 상태이다.

 

하지만 분산 시스템에서는 파티션 문제를 피할 수 없다. 그렇기 때문에 우리의 선택지는 둘 중 하나인데 일관성을 선택하던지 아님 가용성을 선택해야 한다. 장애가 발생하여 n1, n2 ↔ n3이 통신할 수 없을 때는 한 쪽은 데이터 복제를 할 수 없기에 오래된 사본을 갖게 된다.

 

데이터 일관성 선택 ☑️

가용성 대신 일관성을 선택하는 CP 시스템을 선택한다면, 세개의 서버 간의 데이터 불일치 문제를 피해야 한다. n3에 데이터가 저장되었다고 하면 n1과 n2에 대해서는 쓰기연산을 중단해야 한다. 은행권에서는 데이터 일관성을 양보하지 않는다. 일관성이 깨져 계좌의 최신 정보를 출력하지 못하면 큰 문제가 된다.

 

가용성 선택 ☑️

일관성 대신 가용성을 선택한 시스템은 낡은 데이터를 반환할 위험이 있어도 계속 읽기 연산을 허용한다. n1과 n2는 계속 쓰기 연산을 허용하고 파티션 문제가 해결된 후 새로운 데이터를 n3에 전송하게 된다.

 

분산 키-값 저장소를 설계 시에는 요구사항에 맞도록 CAP정리를 적용해야 한다.

 

---

 

시스템 컴포넌트

지금부터는 키-값 저장소를 구현하는데 사용되는 컴포넌트와 기술들에 대해서 알아보도록 하겠다. 다음과 같은 컴포넌트가 있겠다.

 

 ⦁ 데이터 파티션

 ⦁ 데이터 다중화

 ⦁ 일관성

 ⦁ 일관성 불일치 해소

 ⦁ 장애 처리

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

 ⦁ 쓰기 / 읽기 경로

데이터 파티션

대규모 애플리케이션은 전체 데이터를 단일 서버에 저장할 수 없고, 데이터를 파티션으로 분할한 다음 여러 대의 서버에 저장해야 한다. 데이터를 나눌 때는 1. 여러 서버에 고르게 분산 할 수 있는지, 2. 노드의 추가나 삭제 시 데이터의 이동을 최소화 할 수 있는지를 따져봐야 하는데 5장에서 배운 안정 해시가 문제를 해결하는데 적합하다.

 

 

안정 해시를 다시 한번 보자면, 해시 링에 s0 ~ s7까지 8개의 서버를 배치하고 키를 배치한다. 키의 위치로부터 시계방향으로 순회하다 처음 만나는 서버가 해당 키의 값을 저장할 서버가 된다. key 0은 서버 1에 저장되게 된다.

 

안정 해시를 사용함으로 시스템 부하에 따라 서버가 자동으로 추가 / 삭제될 수 있고, 서버 용량에 맞는 가상 노드 수를 조정할 수 있다.

 

데이터 다중화

높은 안정성과 가용성을 위하여서 데이터를 N개의 서버에 다중화 할 필요가 있다. N개의 서버를 선정하는 방법은 어떤 키를 해시 링 위에 배치하고, 키의 위치로부터 시계 방향으로 해시 링을 순회하면서 만나는 첫 N개의 서버에 데이터 사본을 저장한다.

 

 

위 그림은 N=3이고, key0이 s1, s2, s3에 저장된다. 가상 노드를 사용하면 선택한 N개의 노드가 대응되는 물리 서버 개수가 N개보다 작아질 수 있다.

예를 들면 물리 서버 세 대 A, B, C가 있고 가상 노드도 서버 당 세개 씩 A1, A2, A3, ... , C1, C2, C3 있다고 하자. 요청이 들어와서 데이터를 N=3개의 서버에 다중화를 시켰는데 그게 A1, A3, A2가 되어 같은 서버에 저장되는 경우도 있다. 그렇기 때문에 노드를 선택 시 같은 물리 서버의 중복 선택을 피해야 한다.

 

데이터 다중화

여러 노드에 다중화된 데이터는 적절히 동기화해야 하는데, 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 I/O 연산 모두 일관성을 보장할 수 있다. 정족수 합의와 관련된 정의를 소개하겠다.

 

⦁ N : 사본 개수

⦁ W : 쓰기 연산에 대한 정족수. 적어도 W개 서버로부터 쓰기 연산 성공 응답을 받아야 쓰기 연산 성공

⦁ R : 읽기 연산에 대한 정족수. 적어도 R개 서버로부터 읽기 연산 성공 응답을 받아야 읽기 연산 성공

 

 

위의 그림은 N=3 인 경우이다. W = 1은 데이터가 서버 한 대에만 기록된다는 뜻이 아니라, 중재자가 최소 한 대 서버로부터 쓰기 성공 응답을 받아야 한다는 뜻이다. 만약 s0에게 쓰기 성공 응답을 받았다면 s1, s2의 응답까지 기다릴 필요는 없다.

 

W, R, N의 값을 정하는 과정은 데이터 일관성과 응답 지연 사이의 타협점을 찾는 과정이다. W나 R의 값이 1보다 큰 경우는 데이터 일관성이 향상되지만, 중재자의 응답 속도는 느려질 것이다.

W + R > N 이라면 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나 겹치기 때문에 강한 일관성이 보장된다.

 

면접 시 상황별로 N, W, R 값을 정하는 대략적인 구성은 다음과 같다.

 

⦁  R = 1, W = N : 빠른 읽기 연산에 최적화

⦁  W = 1, R = N : 빠른 쓰기 연산에 최적화

⦁  W + R > N : 강한 일관성이 보장

⦁  W + R <= N : 강한 일관성 보장X

 

일관성 모델

키-값 저장소 설계시 일관성 모델은 중요한 요소이다. 앞서 언급했던 강한 일관성 모델도 그 중 하나이다. 일관성 모델들을 설명하도록 하겠다.

 

⦁  강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다

⦁  약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다

⦁  최종 일관성 : 갱신 결과가 결국에는 모든 사본에 반영된다

 

강한 일관성을 달성하기 위해서는 현재 작업하는 쓰기 연산 결과가 반영되기 전까지 해당 데이터에 대해 I/O를 금지해야 하지만, 새로운 요청 처리가 중단되기 때문에 고가용성 시스템에 적합하지 않다. Amazon DynamoDB나 Cassandra는 최종 일관성을 채택하고 있기 때문에 6장에서도 최종 일관성을 목표로 키-값 저장소를 설계하겠다.

 

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

최종 일관성 모델을 따르면 쓰기 연산이 병렬적으로 발생하기 때문에 데이터 일관성이 깨질 수 있기 때문에 클라이언트 측에서 일관성이 깨진 데이터를 읽지 말아야 한다. 이것을 버저닝(versioning)과 벡터 시계(vector clock)를 사용하여 해결할 수 있다.

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

 

먼저 버저닝 전, 데이터 일관성이 깨지는 과정을 알아보겠다.

 

 

데이터의 사본이 n1과 n2에 보관되어있고, 서버 1, 2는 get("name") 연산을 통해 같은 결과를 얻는다. 여기서 서버 1은 name에 매달린 값을 johnSanFrancisco로, 서버 2는 johnNewYork로 바꾼다고 하자.

 

 

이 연산이 동시에 이뤄진다면 두 값이 충돌하게 된다. 이 문제를 해결하기 위해서는 충돌을 발견하고 자동으로 해결해 주는 벡터 시계를 사용할 수 있다.

 

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매달았는데, 이 순서쌍으로 어떤 버전이 선행인지 후행인지, 다른 버전과 충돌이 있는지 판별한다. 벡터 시계는 다음과 같이 표현할 수 있다.

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

 

 ⦁ D : 데이터

 ⦁ Si : 서버 번호

 ⦁ vi : 버전 카운터

 

데이터 D를 서버 Si에 기록했을 때 기존 Si가 있다면 vi를 증가시키고, 없었다면 새로운 항목 [Si, 1]를 만든다. 다음 그림을 통해서 로직의 동작 흐름을 알아볼 수 있다.

 

 

 

① 클라이언트가 데이터 D1을 시스템에 기록 → Sx 서버가 처리 →  D1([Sx, 1]) 

② 클라이언트가 D1 읽고 D2로 업데이트 → Sx 서버가 처리 → D2([Sx, 2])

③ 클라이언트가 D2 읽고 D3으로 업데이트 → Sy 서버가 처리 → D3([Sx,2], [Sy, 1])

④ 클라이언트가 D2 읽고 D4로 업데이트 → Sz 서버가 처리 → D4([Sx, 2], [Sz, 1])

⑤ D2가 Sy, Sz 모두 다른 값으로 바뀌어 충돌 → Sx가 충돌 처리 → D5([Sx, 3], [Sy, 1], [Sz, 1])

 

이렇게 벡터 시계를 사용하면 버전이 어떤 버전의 이전 버전인지 쉽게 파악할 수 있다. 버전 사이의 충돌도 쉽게 확인할 수 있다. 이전 버전의 모든 구성요소가 현재 버전의 값보다 크면 충돌이 있는 것이다.

D([s0, 1], [s1, 2])와 D([s0, 2], [s1, 1])는 충돌이 있지만, D([s0, 1], [s1, 1])와 D([s0, 1], [s1, 2])는 충돌이 없다.

 

하지만 벡터 시계를 사용하여 충돌을 감지하고 해결하는 것은 두 가지 단점이 있는데, 클라이언트 구현이 복잡하고, [서버: 버전] 순서쌍 개수가 빨리 늘어난다는 것이다. 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하기 때문에 클라이언트의 구현이 복잡해질 수 밖에 없고, 순서쌍은 임계치를 설정해서 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거해야 한다.

 

장애 감지 & 해소

대규모 시스템에서 장애는 흔하게 벌어지는 사건이다. 우선 장애를 감지하는 기법을 살펴보고 그 다음으로 장애를 해소하는 전략을 짚어보겠다.

 

분산시스템에서는 "서버 A가 죽었습니다" 만 가지고 장애처리를 하지 않고, 두 대 이상의 서버에서 서버 A의 장애 보고를 받아야 장애가 발생했다고 간주한다. 이를 감지하는 가장 손쉬운 방법은 멀티캐스팅 채널을 구축하는 방법이다.

 

멀티태스킹 장애 감지 구조

 

하지만 이 방법은 서버가 많을 때는 비효율적이다. 분산시스템에서는 가십 프로토콜과 같은 분산형 장애 감지 솔루션을 채택하는 것이 효율적이다.

 

가십 프로토콜 (gossip protocol)

 

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

 

 ⦁ 각 노드는 멤버 ID와 박동 카운터 쌍으로 이루어진 멤버십 목록을 유지한다.

 ⦁ 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다

 ⦁ 각 노드는 무작위 노드에게 자신의 박동 카운터 목록을 보내고, 받은 노드는 멤버십 목록을 최신 값으로 갱신한다

 ⦁ 어떤 노드의 박동 카운터 값이 일정 시간 갱신되지 않으면 장애(offline) 장태로 간주한다.

 

 

일시적 장애 처리

가십 프로토콜로 장애를 감지했으면 적절한 조치를 취해주어야 한다. 엄격한 정족수 접근법을 사용한다면 읽기와 쓰기 연산을 금지해야 하지만 가용성을 생각해서 느슨한 정족수 접근법으로 조건을 완화하여 가용성을 높일 수 있다. 

 장애 상태인 서버로 가는 요청은 다른 서버가 처리해주고, 그동안 발생한 변경사항은 서버가 복구된 후 일괄적으로 반영하여 데이터 일관성을 보존한다. 일시적으로 처리해주는 쓰기, 연산 서버는 장애 서버를 위해 단서를 남겨주게 되고, 이를 단서 후 임시 위탁 (hinted handoff) 기법이라고 한다

 

위의 그림을 보면 장애 상태인 노드 s2에 대한 연산을 일시적으로 s3가 처리해주고, s2가 복구되면 s3가 갱신된 데이터를 s2로 인계하면 된다.

 

영구 장애 처리

단서 후 임시 위탁 기법은 일시적 장애 처리를 위한 방법이고, 영구적 장애 상태 처리는 반-엔트로피 (anti-entropy) 프로토콜을 구현하여 사본들을 동기화 한다. 일관성이 깨진 상태를 탐지하고 데이터 전송량을 줄이기 위해 머클 트리 (Merkle tree)를 사용할 수 있다.

 

머클 트리는 각 노드에 자식 노드의 레이블에서 계산된 해시 값을 레이블로 붙여두는 트리이다. 다음 그림은 키 공간이 1~12까지 있을 때 머클 트리를 만드는 예제이고 일관성이 망가진 데이터는 노란색으로 표기했다.

 

1. 키 공간을 버킷으로 나눈다 (예시: 4개)

 

2. 버킷에 포함된 키에 균등 분포 해시(uniform hash) 함수를 적용하여 해시를 계산한다

 

 

3. 버킷별로 해시값을 계산 후, 해당 해시를 레이블로 갖는 노드를 생성한다

 

 

4. 자식 노드의 레이블에서 새로운 해시 값을 계산하여 이진 트리를 상향적으로 구성한다

 

두 머클 트리의 비교는 루트 노드의 해시값을 비교하면서 시작한다. 루트 노드의 해시값이 같으면 두 서버의 데이터는 같은 것이다. 다르다면 왼쪽 → 오른쪽 자식 노드 순서로 비교해 나가면서 다른 데이터를 갖는 버킷을 찾을 수 있고, 해당 버킷만 동기화하면 된다.

 

머클 트리 사용 시 버킷 하나의 크기가 꽤 크다. 10억개의 키를 100만개의 버킷으로 관리해야 하는데, 그러면 한 버킷당 1000개의 키를 관리하게 된다.

---

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

키-값 저장소를 구현하기 위한 기술적 고려사항을 알아봤으니, 아키텍처 다이어그램을 그려볼 수 있다. 아키텍처의 주요 기능을 나열해보자.

 

 ⦁ 클라이언트는 저장소가 제공하는 get, put API와 통신한다

 ⦁ 중재자는 클라이언트에게 저장소에 대한 proxy 역할을 하는 노드다

 ⦁ 노드는 안정 해시의 해시 링 위에 분포한다

 ⦁ 시스템이 완전히 분산되어 노드를 자동으로 추가 / 삭제할 수 있다

 ⦁ 데이터는 여러 노드에 다중화된다

 ⦁ 모든 노드가 같은 책임을 지기에 SPOF는 존재하지 않다 (Single Point of Failure)

 

아키텍처 다이어그램은 다음과 같고, 노드는 오른쪽의 기능을 지원해야 한다.

 

 

쓰기 경로

다음은 쓰기 요청이 특정 노드에 전달될 때의 흐름이다.

 

 

① 쓰기 요청이 로그 파일에 기록됨

② 데이터가 메모리 캐시에 기록됨

③ 메모리가 가득차거나, 임계치에 도달하면 데이터는 디스크의 SSTable에 저장됨

※ SSTable (Sorted-String Table) : <키, 값> 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

 

읽기 경로

읽기 요청은 데이터가 메모리 캐시에 있는지부터 찾아본다. 있는 경우는 메모리 캐시에서 반환하고 없는 경우는 디스크에서 가져온다.

 

 

 

① 데이터가 메모리에 있는지 검사 → 없으면 ②

② 데이터가 없기 때문에 블룸 필터 검사

※ 블룸 필터 : 찾는 키가 어느 SSTable에 있는지 확인하는 필터

 

③ 블룸 필터를 통해 키가 어떤 SSTable에 있는지 확인

④ SSTable에서 데이터 추출

⑤ 클라이언트에게 반환

 

마무리

6장 키-값 저장소 설계에서는 많은 개념들이 있었고, 저장소를 설계하기 위한 많은 기술적인 부분도 있었다. 정리해보자면 다음과 같다.

 

목표 / 문제	기술
대규모 데이터 저장	안정 해시로 부하 분산
읽기 연산에 가용성 보장	데이터를 데이터센터에 다중화
쓰기 연산에 가용성 보장	버저닝, 벡터 시계로 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성
다양성
조절 가능한 데이터 일관성	정족수 합의 (quorum consensus)
일시적 장애 처리	느슨한 정족수 프로토콜 & 단서 후 임시 위탁 (hinted handoff)
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터 센터에 걸친 데이터 다중화

 

6장을 읽고 정리하면서 저장소를 설계하는 일이 정말 어려운 일이라는 것을 깨닫게 되었다. 단순히 NoSQL에 값을 넣고 꺼내는 수준이 아닌 수많은 장애 가능성과 데이터 일관성, 확장성, 가용성을 모두 고려해야 한다. 그래야 대규모 트래픽이 들어와도 이를 감당해낼 수 있는 것 같다. 이게 진정한 아키텍처라는 생각이 들었다..👍