키-값 저장소 설계안

• key-value store는 NoSQL 데이터베이스이다.
• 이 저장소에 저장되는 값은 고유 식별자(identifier)를 키로 가져야 한다.
• 키-값 쌍에서의 키는 유일해야 하며 해당 키에 매달린 값은 키를 통해서만 접근 가능
• 키는 일반 텍스트, 해시 값 모두 가능하지만, 성능상의 이유로 키는 짧을수록 좋다
• 값은 문자열, list, object… 가능 (보통 무엇이 되든 상관x)
• 널리 알려진 제품
  • Amazon DynamoDB
  • memcached
  • Redis

문제 이해 및 설계 범위 확정

• 이번 글에서는 다음 특성을 갖는 키-값 저장소를 설계할 것
  • 키-값 쌍의 크기는 10KB 이하
  • 큰 데이터를 저장할 수 있어야 함
  • 높은 가용성을 제공해야함, 장애가 생기더라도 빠른 응답 필요
  • 높은 규모 확정성 제공, 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 함
  • 데이터 일관성 수준은 조정 가능해야 함
  • 응답 지연시간(latency)이 짧아야 함

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

• 단일서버 설계는 어렵지 않다.

  가장 직관적인 방법

• 키-값 쌍 전부를 메모리에 해시 테이블로 저장
• 하지만, 데이터가 많아지면, 모든 데이터를 메모리 안에 두는 것이 불가능할 수 있음

해결책

• 데이터 압축
• 자주 쓰이는 데이터만 메모리에 두고 나머지는 티스크에 저장

그러나 한 대 서버로 부족한 때가 찾아오므로, 분산 키-값 저장소 (distributed key-value store)를 설계해야 함

2. 분산 키-값 저장소

• 분산 키-값 저장소는 분산 해시 테이블이라고도 불림
• 분산 시스템 설계시에는 CAP 정리 (Consistency, Availibility, Partition Torlerance theorem)을 이해해야 함

2.1 CAP 정리

• CAP 정리는 데이터 일관성, 가용성, 파티션 감내(여기서 파티션은 DB 테이블 파티션이 아니다! 네트워크 단절에 의한 partition을 의미함)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리
  • 데이터 일관성 : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 함
  • 가용성 : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함
  • 파티션 감내 : 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미, 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 하는 것을 뜻함
• 위 조건 가운데 어떤 두가지를 충족하려면, 나머지 하나는 반드시 포기해야함

CP 시스템

• 일관성과 파티션 감내를 지원하는 키-값 저장소, 가용성을 희생

AP 시스템

• 가용성과 파티션 감내를 지원하는 키-값 저장소, 데이터 일관성을 희생

CA 시스템 (실제로 존재하지 않음)

• 일관성과 가용성을 지원하느 키-값 저장소
• 파티션 감내를 지원하지 않으나, 통산 네트워크 장애는 피할 수 없으므로, 실세계에 CA 시스템은 존재하지 않음

구체적인 예

• 정의만으로는 이해하지 어려우니, 구체적인 예를 살펴보자
• 그림 6-2와 같이 세 대의 복제 노드 n1, n2, n3에 데이터를 복제한다고 가정

이상적 상태

• 이상적 환경이라면 네트워크가 파티션되는 상황은 일어나지 않음
• n1에 기록된 데이터는 자동적으로 n2와 n3에 복제
• 데이터 일관성과 가용성도 만족

실세계의 분산 시스템

• 분산 시스템은 파티션 문제를 피할 수 없음
• 파티션 문제가 발생하면 일관성과 가용성 사이에서 하나를 선택해야 함
• 그림 6-3은 n3에 장애가 발생하여 n1, n2와 통신할 수 없는 상황
  • 클라이언트가 n1, n2에 저장한 데이터는 n3에 저장되지 않음
  • n3에 기록되었으나 n1, n2로 전달되지 않은 데이터가 있다면 n1과 n2는 오래된 사본을 갖고있음
• 선택 1 : 일관성 선택 (CP 시스템)
  • 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단 (가용성 깨짐)
  • ex) 은행권 시스템은 데이터 일관성을 양보하지 않음, 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못하면 큰 사고
• 선택 2 : 가용성 선택 (AP 시스템)
  • 낡은 데이터를 반환할 위험이 있더라도 읽기 연산 허용
  • n1, n2에도 쓰기 연산허용
  • 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송

2.2 시스템 컴포넌트

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

2.2.1 데이터 파티션

• 대규모 애플리케이션의 경우 모든 데이터를 하나의 서버에 저장하는 것은 불가능
• 데이터를 작은 파티션으로 분할한 다음 여러 서버에 저장한다.

고려해야할 점

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

해결법

• 5장에서 배운 안정 해시 사용
  • 규모 확장 자동화 (automatic scaling) : 시스템 부하에 따라 서버가 자동으로 추가/삭제
  • 다양성 (heterogeneity) : 각 서버의 용량에 맞게 가상 노드의 수를 조정 가능, 다시 말해, 다른 노드보다 고성능의 노드는 더 많은 가상 노드를 갖도록 설정 가능

2.2.2 데이터 다중화

• 높은 가용성과 안정성을 확보하기 위해서는 테이터를 N개 서버(N은 튜닝가능)에 비동기적으로 다중화 (replication)할 필요가 있음
• 2.2.1에서 설명한 안정 해시의 해시링 위에서 링은 순회하며 만나는 첫 N개의 서버에 데이터 사본 저장
• 같은 데이터 센터에 속한 노드는 물리적 이슈로 인해 문제를 동시에 겪을 가능성이 있으므로, 사본을 다른 센터의 서버에 저장해야 할 필요가 있음

2.2.3 데이터 일관성

• 여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 함
• 정족수 합의 (Quorum Consensus) 프로토콜을 사용하여 읽기/쓰기 연산 모두에 일관성 보장 가능
  • N = 사본 개수
  • W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.
  • R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 함

N = 3 인 경우에 대한 그림 6-6 예제

• W = 1 은 데이터가 한 대 서버에만 기록된다는 뜻 X. 쓰기 연산이 성공했다고 판단하기 위해 중재자(coordinator)는 최소 한 대 서버로부터 쓰기 성공 응답을 받아야 함
• 따라서 s1으로 부터 성공 응답을 받으면, 다른 서버로부터의 응답은 기다릴 필요 없음
• 중재자는 클라이언트와 노드 사이에서 프록시(proxy) 역할

W, R, N 값 정하기

• W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 것
• W=1 or R=1 구성의 경우 중재자는 한 대 서버로 부터 응답만 받으면 되니 응답속도는 빠름
• W or R > 1 인경우, 시스템이 보여주는 데이터 일관성의 수준은 향상될 테지만, 중재자의 응답 속도는 느린 서버로부터의 응답을 기다려야 하므로 느려짐
• W + R > N 인 경우에는 강한 일관성 (strong consistency) 보장, 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹칠 것
• 몇 가지 구성 가능 예제
  • R=1, W=N : 빠른 읽기 연산에 최적화
  • W=1, R=N : 빠른 쓰기 연산에 최적화
  • W+R>N : 강한 일관성이 보장됨 (보통 N=3, W=R=2)
  • W+R<=N : 강한 일관성이 보장되지 않음

일관성 모델

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

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

• 데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨진 가능성은 높아짐
• 해결책으로 버저닝(versioning), 벡터 시계(vector clock) 기술 사용
  • 버저닝 : 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만듦, 각 버전의 데이터는 immutable, conflict 발생 가능
  • 벡터 시계 : [서버, 버전]의 순서쌍을 데이터에 태깅
    • 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별
    • 두 버전 사이에 충돌을 확인하는 방법은, 모든 구성요소 값이 같거나 큰지만 보면 됨
      • D([s0,1],[s1,1])은 D([s0,1],[s1,2])의 이전 버전 (충돌 x)
      • D([s0,1],[s1,2])과 D([s0,2],[s1,1])는 서로 충돌
    • 단점
      • 충돌 감지 및 해소 로직이 클라이언트에 들어가야해서 구현이 복잡해짐
      • [서버:버전]의 순서쌍 갯수가 굉장히 빨리 늘어나므로, threshold 설정 필요

2.2.4 장애 처리

• 대다수 대규모 시스템에서 장애는 아주 흔하게 발생
• 장애 방지가 아닌 장애 감지 (failure detection)과 장애 해소 (failure resolution) 전략이 필요

장애 감지

• 분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주.
• 하지만 그림 6-10의 multicasting 채널을 구축하는 것은 비효율적 ($O(n^2)$)
• 가십 프로토콜(gossip protocol)같은 분산형 장애 감지(decentrailized failure detection) 솔루션을 채택하는 것이 효율적

가십 프로토콜 (gossip protocol)

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

일시적 장애 처리

• 느슨한 정족수 (sloppy quorum) 접근법 사용
• 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고름 (장애 서버는 무시)
• 장애 상태인 서보로 가는 요청은 다른 서버가 잠시 맡아 처리
• 그동안 발생한 변경사항은 해당 서버가 복귀되었을 때 일괄 반영하여 데이터 일관성 보존 (hint를 남겨놓음) -> 단서 후 임시위탁 (hinted handoff) (그림 6-12 예제)

영구적 장애 처리

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

머클 트리 (Merkle Tree)

• 정의
  • 해시 트리(hash tree)라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시(자식 노드가 leaf 노드인 경우), 또는 자식 노드들의 레이블로부터 계산되 해시 값을 레이블로 붙여두는 트리
  • 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증(verification)할 수 있음
• 사용 예제
  • 머클 트리 생성 과정
    • 키 공간을 버킷(bucket)으로 나눔
    • 버킷에 포함된 각각의 키에 균등 분포 해시 (uniform hash) 함수를 적용하여 해시 값 계산
    • 버킷별로 해시값을 계산 후, 해당 해시 값을 레이블로 갖는 노드 생성
    • 자식 노드의 레이블로부터 새로운 해시 값 계산 -> 이진 트리를 상향식으로 구성
  • 비교과정
    • 루트(root) 노드의 해시값을 비교
      • 루트 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 가짐
    • 값이 다른 경우 왼쪽 자식 노드의 해시 값을 비교, ㄷ그 다음으로 오른쪽 자식 노드의 해시 값 비교
    • 이렇게 하면서 아래쪽으로 탐색해 나가다 보면 다른 데이터를 갖는 버킷을 찾을 수 있으므로, 그 버킷들만 동기화 하면 된다
• 이점
  • 동기화 해야하는 데이터의 양이 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관
  • 차이가 존재하는 데이터를 찾는 시간이 $O(log_2 n)$

데이터 센터 장애 처리

• 정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생 가능
• 데이터를 여러 데이터 센터에 다중화하는 것이 중요함

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

아키텍처의 기능 (그림 6-17)

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

2.2.6 쓰기 경로

• 그림 6-19는 쓰기 요청이 특정 노드에 전달되었을 때의 상황을 보여줌 (Cassandra 예제)

1. 쓰기 요청이 커밋 로그(commit log)파일에 기록
2. 데이터가 메모리 캐시에 기록
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임게치에 도달하면 데이터는 디스크에 있는 SSTable(Sorted-String Table)에 기록

2.2.7 읽기 경로

• 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핌
• 있는 경우에는 그림6-20과 같이 해당 데이터를 클라이언트에게 반환
• 메모리에 없을 경우에는 디스크에서 가져와야함
  • 어느 SSTable에 찾는 키가 있는지 알아낼 효율적인 방법이 필요 -> Bloom filter 사용!
    • cf) 블룸필터 : 있다고 한 곳에 없을수는 있지만, 없다고 한 곳에 있는 경우는 없음

그림 6-21

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

3.요약

참고자료

• 알렉스 쉬, 가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장