TIL

6장 키-값 저장소 설계

키-값 저장소는 비 관계형 데이터베이스이다.
키-값 쌍에서 키는 유일하며 키를 통해서만 값에 접근할 수 있다.
- 키는 텍스트일 수도 있고 해시 값일 수도 있다.
- 성능상 키는 짧을 수록 좋다.
- 값은 문자열일 수도 리스트 또는 객체일 수도 있다.
키-값 저장소 예: 다이나모, memcached, 레디스 등

문제 이해 및 설계 범위 확정

읽기, 쓰기, 메모리 사용량 사이에서 균형을 찾아야 한다.
데이터 일관성과 가용성 사이에서 타협을 해야 한다.
전제 조건을 정의해보자
- 키-값 쌍 크기는 10KB 이하
- 큰 데이터를 저장할 수 있어야 한다.
- 높은 가용성을 제공해야하며 장애에 빨리 응답해야 한다.
- 높은 규모 확장성을 제공해야 하며 트래픽에 따라 자동 서버 증설/삭제가 필요
- 데이터 일관성 수준은 조정 가능해야 한다.
- 응답 지연 시간이 짧아야 한다.

단일 서버 키-값 저장소

가장 직관적인 방법은 키-값 쌍 전부 메모리에 해시 테이블로 저장하는 것
- 빠른 속도 보장
- 모든 데이터를 메모리에 두기 불가능할 수 있다.
- 데이터 압축이나 자주 쓰는 데이터만 메모리에 두는 방법을 사용하여 개선할 수는 있다.
한 대 서버로는 부족한 때가 곧 찾아오게 된다.

분산 키-값 저장소

분산 해시 테이블이라고도 불린다.
분산 시스템 설계할 때는 CAP 정리를 이해할 필요가 있다.

CAP 정리

CAP 정리란 아래 세 요구사항을 동시에 만족하는 분산 시스템 설계는 불가능하다는 정리이다.
- 일관성 (consistency)
- 가용성 (availability)
- 파티션 감내성 (partition tolerance)
데이터 일관성: 분산 시스템의 어떤 노드에 접속해도 언제나 같은 데이터를 본다.
가용성: 일부 노드에 장애가 발생하더라도 항상 응답 받을 수 있다.
파티션 감내: 파티션은 두 노드 사이의 통신 장애 발생을 의미한다. 파티션 감내는 파티션이 생기더라도 시스템은 동작하여야 한다는 것을 의미한다.
CAP 정리에 따르면 어떤 두 가지를 충족하면 나머지 하나는 반드시 희생되어야 한다.
- CP 시스템: 가용성을 희생하여 일관성과 파티션 감내를 지원하는 시스템
- AP 시스템: 일관성을 희생하여 가용성과 파티션 감내를 지원하는 시스템
- CA 시스템: 파티션 감내를 희생하는 시스템이지만 통상 네트워크 장애는 피할 수 없기에 분산 시스템은 반드시 파티션 감내를 지원해야 한다. 그러므로 실세계에 CA는 존재하지 않는다.
즉 실세계에 적용되는 CAP 정리란 파티션 감내를 무조건 지원하면서 가용성과 일관성 중 하나를 선택해야 한다는 것이다.

CAP 정리의 구체적 사례

3개의 노드 n1, n2, n3에 데이터를 복제해서 보관하고 있다고 가정
이상적인 상태
- 네트워크가 파티션되는 상황이 일어나지 않음
- n1에 기록된 데이터는 자동적으로 n2, n3에 복제되어 일관성과 가용성을 모두 만족
실세계의 분산 시스템
- 분산 시스템은 파티션 문제를 피할 수 없다.
- 만약 n3 노드에 장애가 발생했다고 가정
- n1, n2에 기록한 데이터는 n3에 전달되지 않는다.
- n3에 기록되었으나 n1, n2에 전달되지 않은 데이터가 있을 수도 있다. (최신 데이터가 유실)
파티션 상황에서 가용성과 일관성의 트레이드 오프
- 파티션이 발생해도 전체 시스템을 다운할 수 없다. (파티션 감내)
- 일관성을 선택(CP): 가용성을 희생하여 n1, n2 노드에 쓰기 연산을 중단시킨다. 일관성이 깨지는 문제가 발생하면 상황이 해결될 때까지 오류를 반환해야 한다.
- 가용성을 선택(AP): 설사 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용하며 n1, n2에 쓰기 연산도 계속 허용한다. 파티션 문제 해결 후 세 데이터를 n3에 전송
분산 키-값 저장소를 만들 때는 요구사항에 맞도록 CAP 정리를 적용해야 한다.

시스템 컴포넌트

분산 키-값 저장소 구현에 사용될 핵심 컴포넌트 및 기술들이며 널리 사용되는 키-값 저장소인 다이나모, 카산드라, 빅테이블 사례를 참고

데이터 파티션

대규모 애플리케이션의 데이터를 작은 파티션으로 분할 후 여러 서버에 저장해야 한다.
균형적인 데이터 분포와 노드 추가/삭제에 따른 비용을 최소화하기 위해 안정 해시를 사용할 수 있다.
안정 해시를 사용하여 데이터를 파티션하면 규모 확장 자동화와 다양성을 충족할 수 있다.
- 다양성: 각 서버 용량에 맞게 가상 노드 수를 조절

데이터 다중화

높은 가용성과 안정성을 위해 데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다.
해시 링 위에서 키가 서버 노드를 시계 방향으로 탐색할 때 만나는 첫 N개에 데이터 사본을 보관
가상 노드를 사용한다면 N개의 가상 노드가 실제로는 더 적은 물리 서버일 수도 있기에 같은 서버를 중복 선택하지 않도록 해야 한다.
자연재해 등의 문제를 피하기 위해 데이터 사본을 지리적으로 떨어진 다른 데이터 센터에 보관하고 센터들은 고속 네트워크로 연결한다.

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화 되어야 한다.
정족수 합의 (Quortum Consensus) 프로토콜을 통해 읽기/쓰기에 모두 일관성을 보장할 수 있다.
관련 정의: N = 사본 개수, W = 쓰기 연산에 대한 정족수, R = 읽기 연산에 대한 정족수
ex) W = 1은 여러 서버 중 적어도 1개 서버로부터 쓰기 연산에 성공했다는 응답을 받아야 한다는 뜻
W, R, N의 값은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 전형적인 과정이다.
- R = 1, W = N: 빠른 읽기 연산에 최적화
- R = N, W = 1: 빠른 쓰기 연산에 최적화
- W + R > N: 강한 일관성이 보장됨
- W + R ≤ N: 강한 일관성이 보장되지 않음
일관성 모델
- 강한 일관성: 모든 읽기 연산은 가장 최근 변경 사항을 반환해야 함
- 약한 일관성: 읽기 연산은 가장 최근 변경 사항을 반환하지 못할 수도 있다.
- 최종 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영되는 모델
- 강한 일관성을 위해선 모든 사본이 동기화될 때까지 읽기/쓰기를 금지해야 하지만 고가용성 시스템엔 부적합
- 다이나모 또는 카산드라 등은 최종 일관성 모델을 채택
비 일관성 해소 기법: 데이터 버저닝
- 데이터를 다중화하면 일관성이 깨질 가능성이 높아진다.
  - 한 데이터를 두 요청이 동시에 변경할 때 쓰기 저장소가 하나라면 덮어쓰기가 되겠지만 각각 다른 쓰기 저장소에 반영되면 충돌을 해결해야 한다.
- 버저닝: 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만든다. 즉 각 버전 데이터는 불변
- 백터 시계: [서버, 버전] 순서쌍을 데이터에 매단 것으로 어떤 것이 선행 버전인지, 충돌이 있는지 판별하는데 쓰인다.
- 백터 시계 단점
  - 충돌을 감지하고 해소하는 로직이 클라이언트에 있다.
  - [서버: 버전] 순서쌍 개수가 굉장히 빠르게 늘어나기에 임계치를 설정해 오래된 순서쌍을 제거하도록 해야 한다.
  - 오래된 쌍을 제거하면 버전 간 선후관계가 정확하지 않을 수도 있지만 다이나모 문서에 따르면 아마존에서 그런 문제가 발생한 적이 없다고 한다.

장애 처리

장애 감지
- 모든 노드 사이에 멀티 캐스팅 채널을 구축하는 것이 가장 쉬운 방법이지만 서버가 많을 땐 비효율적
- 가십 프로토콜(gossip protocol) 같은 분산형 장애 감지 솔루션이 보다 효율적
  - 각 노드가 맴버십 목록을 유지. 멤버십 목록은 각 멤버 ID와 박동 카운터 쌍의 목록이다.
  - 각 노드는 자신의 박동 카운터를 주기적으로 증가시키며 무작위로 선정된 다른 노드들에게 자기 박동 카운터를 보낸다.
  - 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
  - 어떤 멤버의 박동 카운터 값이 지정된 시간 안에 갱신되지 않으면 장애 상태인 것으로 간주
일시적 장애 처리
- 엄격한 정족수 접근법을 쓴다면 장애 발생 시 읽기/쓰기를 모두 금지하지만 이를 완화한 느슨한 정족수 접근법은 가용성을 더 높인다.
- 쓰기를 수행할 W개의 건강한 서버와 읽기를 수행할 R개 건강한 서버를 해시 링에서 고른다.
- 장애 상태 서버로 가는 요청을 다른 서버가 잠시 맡아 처리하고 그동안의 변경사항은 장애 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보장한다. (임시 위탁)
- 임시로 쓰기 연산을 처리한 서버엔 그에 관한 단서(hint)를 남긴다.
영구적 장애 처리
- 반-엔트로피(anti-entropy) 프로토콜로 영구적인 노드 장애를 처리할 수 있다.
- 반-엔트로피 프로토클은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다.
- 사본 간 일관성이 망가진 상태를 탐지하고 전송 데이터 양을 줄이기 위해 머클(Merkle) 트리를 사용한다.
- 머클 트리는 각 노드에 자식 노드들에 보관된 값의 해시(자식 노드가 리프 노드인 경우) 또는 자식 노드들의 레이블로부터 계산된 해시 레이블 값을 레이블로 붙여두는 트리다.
- 머클 트리의 루트 부터 비교하여 해시값이 같다면 두 서버는 같은 데이터를 갖는 것이고 다른 값이면 그 버킷들만 동기화하면 된다.
- 머클 트리를 사용하면 동기화가 필요한 데이터 양은 실제 존재하는 차이 크기에 비례할 뿐 데이터의 총량과는 무관하다.
데이터 센터 장애 처리
- 데이터 센터 장애는 정전, 네트워크 장애, 자연 재해 등 다양한 이유로 발생
- 데이터 센터 장애에 대응하려면 다중화하는 것이 중요

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

클라이언트는 키-값 저장소가 제공하는 두 가지 API(get(key), put(key, value))와 통신
중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 proxy 역할을 하는 노드
노드는 안정 해시의 해시 링 위에 분포
노드를 자동으로 추가, 삭제할 수 있도록 시스템은 완전히 분산된다.
데이터는 여러 노드에 다중화된다.
모든 노드가 같은 책임을 지므로 SPOF(Single Point of Failure)는 존재하지 않는다.
완전 분산된 설계를 채택함으로 모든 노드는 앞서 말한 모든 기능을 지원해야 한다.
- 클라이언트 API
- 장애 감지
- 데이터 충돌 해소
- 장애 복구 메커니즘
- 다중화
- 저장소 엔진
- …

쓰기 경로

카산드라(Cassandra)의 쓰기 경로를 참고

쓰기 요청이 커밋 로그 파일에 기록된다.
데이터가 메모리 캐시에 기록된다.
메모리 캐시가 가득 차거나 사전 정의된 임계치에 도달하면 데이터는 디스크의 SSTable에 기록된다.
SSTable(Sorted-String Table로 <키, 값> 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

읽기 경로

읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지 먼저 살핀다.
데이터가 메모리에 없으면 디스크에서 가져오는데 블룸 필터(Bloom filter)가 흔히 사용된다.
블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
SSTable에서 데이터를 가져온다.
데이터를 클라이언트에게 반환한다.

요약

대규모 데이터 저장 → 안정 해시를 사용해 서버들에 부하 분산
읽기 연산에 대한 높은 가용성 보장 → 데이터를 여러 데이터 센터에 다중화
쓰기 연산에 대한 높은 가용성 보장 → 버저닝 및 백터 시계를 사용한 충돌 해소
데이터 파티션 → 안정 해시
점진적 규모 확장성 → 안정 해시
다양성 → 안정 해시
조절 가능한 데이터 일관성 → 정족수 합의
일시적 장애 처리 → 느슨한 정족수 프로토콜과 단서 후 임시 위탁
영구적 장애 처리 → 머클 트리
데이터 센터 장애 대응 → 여러 데이터 센터에 걸친 다중화