로고jiohh blog

6장 - 키-값 저장소 설계

목표

키-값 저장소는 비관 계형 데이터 베이스로 고유 식별자를 키로 가진 값이 저장되며
이런 연결 관계를 "키-값" 쌍이라고 칭한다.

키 : 유일해야하며 키를 통해서만 접근가능
값 : 리스트, 객체 등 무엇이 오든 상관없음

연산으로 두가지가 있다
put(key, value) : 키-값 쌍을 저장소에 저장
get(key) : 인자로 주어진 키에 매달린 값을 꺼낸다.

문제 이해 및 설계 범위 확정

  • 키-값 쌍의 크기는 10KB 이하이다.
  • 큰 데이터를 저장할 수 있어야 한다.
  • 높은 가용성을 제공해야 한다. 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다.
  • 높은 규모 확장성을 제공해야 한다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
  • 데이터 일관성 수준은 조정이 가능해야 한다.
  • 응답 지연시간이 짧아야 한다.

단일 서버 키-값 저장소

직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것
그러나 모든 데이터를 메모리안에 두는 것은 불가능

  • 데이터 압축
  • 자주 쓰이는 데이터만 메모리에 나머지는 디스크

이러한 방법을 서도 한대의 서버로는 부족하다.

분산 키-값 저장소

분산 키-값 저장소 = 분산 해시 테이블 키-값 쌍을 여러 서버에 분산 시키는 탓이다.

CAP 정리

데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)

위의 세가지를 모두 만족하는 분산 시스템을 설계하는 것은 불가능 하다.

  • 데이터 일관성 : 어떤 노드에 접속했든 언제나 같은 데이터를 보아야 한다.
  • 가용성 : 일부 노드에 장애가 발생하더라도 항상 응답 받을 수 있어야 한다.
  • 파티션 감내 : 파티션(두 노드 사이에 통신 장애)이 생겨도 시스템은 계속 동작해야한다.

다음 그림과 같이 두가지를 충족하면 하나는 무조건 희생되어야한다.

  • cp시스템 : 일관성, 파티션 감내 / 가용성을 희생
  • ap시스템 : 가용성, 파티션 감내 / 데이터 일관성 희생
  • ca시스템 : 일관성, 가용성 / 파티션 감내 미지원
    네트워크 장애는 피할 수 없음으로 파티션 감내를 무조건 지원해야함(분산시스템 정의) = ca시스템 존재하지 않음

실시계 분산 시스템

n1,n2,n3가 있을때 기록된 데이터가 서로 복제하며 일관성과 가용성도 만족한다.

그러나 n2가 문제가 일어날 경우 문제가 발생한다.(파티션 문제 발생)

n2에 기록되었으나 n1,n3로 전달되지 않은 데이터(데이터 일관성 문제 발생)

이때 가용성 대신 일관성(cp시스템)을 선택한다면 n1,n3에 대해 쓰기 연산을 중단한다(가용성 꺠짐)

이떄 일관성 대신 가용성(ap시스템)을 선택한다면 낡은 데이터 반환 위험을 감수하고 연산 허용(일관성 깨짐)

이 때문에 요구사항을 잘 정리하고 CAP정리를 적용해야한다.

시스템 컴포넌트

핵심 컴포넌트들과 기술들을 소개하겠다.

데이터 파티션

대규모 일경우 전체 데이터를 한대 서버에 넣는 것은 불가능
데이터를 작은 파티션들로 분할한 다음 여러 서버에 분할저장

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

안정 해시를 이용해 파티션한다. 다음 장점을 가져옴

  • 규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있다.
  • 다양성 : 서버 용량에 맞게 가상노드의 수를 조정할 수 있다 = 고성능 서버는 더많은 가상노드

데이터 다중화

N개의 서버에 비동기적으로 다중화 = 가용성과 안정성 확보

임의의 N을 선정하여 안정해시의 원형링을 순회하며 N개를 선택하는 방식으로 다중화 ➡️ 가상노드 사용시 같은 물리 서버를 중복 선택하지 않도록 조치

데이터 일관성

다중화된 데이터의 동기화 필요 ➡️ 정족수 합의 프로토콜 사용
읽기/쓰기 연산 모두 일관성을 보장

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

w=1 일 경우 한 대의 서버에 기록되는 뜻이 아닌 한대의 서버로 부터 쓰기 성공 응답을 받아야한다는 뜻이다.

w=1, r=1으로 설정할 경우 응답 속도는 빠르나 응답속도는 빠르나 일관성 수준이 떨어지게 된다. W + R > N인 경우 강한 일관성이 보장된다.

N, W, R은 어떻게 정해야 할까?

  • R = 1, W = N: 빠른 읽기 연산에 최적화된 시스템
  • W = 1, R = N: 빠른 쓰기 연산에 최적화된 시스템
  • W + R > N : 강한 일관성 보장(보통 N=3, W=R=2)
  • W + R ≤ N : 강한 일관성 보장 x

요구되는 일관성 수준에 따라 WRN의 값을 조정한다.

일관성 모델
데이터 일관성의 수준을 결정하는 모델

  • 강한 일관성 : 모든 읽기 연산은 최근에 갱신된 결과를 반환
    모든 사본에 쓰기 연산이 반영될때까지 읽기/쓰기 금지
  • 약한 일관성 : 읽기 연산은 최근 갱신된 결과를 반환하지 못할 수 있다.
  • 최종 일관성 : 약한 일관성의 한 형태, 갱신 결과가 모든 사본에 반영 되는 모델을 쓰기 연산이 병렬적으로 발생하면 일관성이 깨질 수 있음 -> 클라이언트가 해결

비 일관성 해소 기법

버저닝과 벡터 시계는 사본간 일관성 문제를 해소하기 위한 기술

버저닝 : 데이터 변경될때 해당 데이터의 새로운 버전을 만듬

버저닝만 사용할 경우 병렬로 처리되면 버전이 충될 되어 해소되기 어렵다. 이때 벡터 시계는 이런 문제를 풀이한다.

벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것
-> 어떤 버전이 선행 버전인지, 후행 버전인지, 충돌이 있는지 판별

데이터 D를 서버에 기록하면 다음 작업을 수행 하여야한다.

  • [Si, Vi]가 있으면 vi를 증가시킨다.
  • 그렇지 않으면 새항목 [Si, 1]를 만든다.

충돌 발생후 어느 클라이언트에서 D3또는 D4를 읽으면 충돌이 있다는 것을 알게 된다.
이 충돌을 클라이언트가 해소한 후에 서버에 기록한다.([Sx, 2][Sy, 1][Sz, 1])->([Sx, 3][Sy, 1][Sz, 1])

벡터 시계 단점

  • 충돌 감지 및 해소 로직이 클라이언트에 들어가야하므로 클라이언트 구현 복잡
  • [서버:버전]의 순서쌍이 빨리 늘어남 ➡️ 벡터 시계에서 오래된 순서쌍을 제거해야 한다.
    오래된 순서쌍을 제거 할 경우 선후관계가 정확하게 결정x 실제 서비스에서 그런문제 없다.

장애처리

  • 장애 감지
    장애에 정보가 한대의 서버에서 감지된다고 해서 바로 장애처리하지않는다 최소 두대이상 서버에서 장애처리해야 발생했다고 감지한다.

    • 멀티캐스팅 채널 구축 : 모든 서버 연결하여 장애 감지, 비효율적이다.
    • 가십 프로토콜 = 분산형 장애감지 솔루션 채택
      1. 각 노드가 주기적으로 자신의 박동 카운터를 증가하여 다른 노드들로 전송
      2. 각 노드는 멤버십 목록(박동 카운터 목록)을 최신으로 갱신한다.
      3. 어떤 멤버의 박동 카운터 값이지정한 시간 동안 갱신되지 않으면 해당 멤버는 장애상태로 간주한다.

  • 일시적 장애 처리 가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해서 조치를 취해야 한다.
    엄격한 정족수 대신 느슨한 정족수접근법을 사용한다면 조건을 완화하여 가용성을 높인다. 느슨한 정족수는 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시링에서 고른다.
    장애인 서버로 가는 요청은 잠시 다른 서버가 맡아 처리한다. 그동안 발생한 변경사항은 그에 관한 단서를 남겨둔다. 이러한 장애 처리 방안을 단서 후 임시위탁이라 부른다.
    이후 장애가 복구되면 임시위탁받은 노드는 갱신된 데이터를 장애복구된 서버로 옮기게 된다.

  • 영구 장애 처리 영구적인 노드의 장애 상태 처리르 어떻게 해야할까?

    반-엔트로피 프로토콜을 구현하여 사본들을 동기화 한다.
    = 사본들과 비교하여 최신 버전으로 갱신 머글 트리를 사용한다.(이해 필요)

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

아키텍처 주된 기능

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

완전히 분산된 설계로 모든노드는 클라이언트API, 장애감지, 데이터 충돌 해소, 장애 복구 메커니즘, 다중화, 저장소 엔진을 지원해야한다.

쓰기 경로

메모리 캐시가 가득차거나 임계치에 도달하면 SSTable([키, 값]의 순서쌍을 정렬된 리스트형태 테이블)에 저장된다.

읽기 경로

메모리에 있을 경우 읽기경로

메모리에 없는 경우 블룸필터를 사용하여 SSTable에 찾는 키가 있는 지 확인한다.