가상 면접 사례로 배우는 대규모 시스테 설계 기초 #6 (키-값 저장소 설계)

박주진·2022년 5월 28일
0

키-값 저장소란?

  • 키-값 데이터베이스 라고도 불림
  • 저장되는 모든 값은 고유 식별자를 키로 가져야 함
  • 해당 키에 매달린 값은 키를 통해서만 접근 가능
  • 키는 텍스트 or 해시 값일 수 있다 (성능상 짧을수록 좋다.)
    • 일반 텍스트키 - "last_logged_in_at"
    • 해시 키 - 253DDEC4
  • 값으로는 다양한 값이 될수 있다 (문자열, 리스트, 객체...)
  • 아마존 다이나모, memcached, 레디스 등이 대표적인 예이다

문제 이해 및 설계 범위 확정

  • 완벽한 설계란 없다. 읽기, 쓰기, 메모리 사용량 사이에 균형을 찾고, 데이터 일관성, 가용성 사이에서 타협적인 결정을 내린 설계란면 쓸만한 답일것이다.
  • 이번장은 다음의 특성을 갖는 키-값 저장소를 설계해보자
    • 키-값 쌍의 크기는 10kb 이하
    • 큰 데이터를 저장 가능해야 함
    • 높은 가용성 즉 장애가 있더라도 빠르게 응답해야 함
    • 높은 규모 확장성 즉 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 함
    • 데이터 일관성 수준은 조정이 가능해야 함
    • 응답 지연시간이 짧아야 함

단일 서버 키-값 저장소

  • 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 방식으로 구현 가능

장점

  • 빠른 접근 속도 보장

단점

  • 모든 데이터를 메모리에 둘 수 없음
  • 데이터 압축, 자주쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장 하는 방법이 있지만 많은 데이터를 저장하려면 부족하다.

분산 키-값 저장소

  • 분산 해시 테이블이라고도 부름
  • 키-값 쌍을 여러 서버에 분산 시키는 방법

cap (consistency, availability, partition tolerance)

  • 데이터 일관성(consistency) 란? 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다라는 것이다
  • 가용성 (availability) 란? 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다는 것이다
  • 파티션 감내 (partition tolerance) 란? 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미하나다. 즉 네트워크 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것이다
  • 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능 하며 두 가지를 충족하려면 나머지 하나는 반드시 희생 되어야 한다는 것을 의미한다.

cap 분류

  • cp 시스템 - (일관성 + 파티션 감내 지원) 가용성을 희생
  • ap 시스템 - (가용성 + 파테션 감내 지원) 데이터 일관성 희생
  • ca 시스템 - (일관성 + 가용성 지원) 파티션 감내 희생 (파티션 문제는 피할 수 없음으로.. 분산 시스템은 파티션 문제를 감내할 수 있어야 함!! 고록 실세계에는 존재하지 않는 시스템 종류 )

분산 시스템 예시

   n1
  /  \
 /    \
n2 --- n3

이상적인 상태

  • 이상적인 환경이라면 네트워크가 파티션되는 상황은 절대로 일어나지 않는다. 고로 n1에 기록된 데이터는 자동적으로 n2, n3에 복제된다. 즉 일관성 가용성 모두 만족된다.

실세계

  • n3가 장애가 발생하여 n1, n2와 통신할 수 없는 상황이 발생 될 수 있다.
  • 일관성 선택시 데이터 불일치를 피하기 위해 n1, n2에 쓰기 연산을 중단 시킨다. 고로 가용성이 깨진다.
  • 가용성 선택시 낡은 데이터를 반환할 위험이 있더라도 읽기 연산을 허용한다. n1,n2에도 쓰기 연산을 허용하고 파티션 문제가 해결된 후 새데이터를 n3에 전송한다.

시스템 컴포넌트

데이터 파티션

  • 대규모 어플리케이션의 경우 데이터가 많기 때문에 작은 파티션으로 분할하여 여러 서버에 저장하여야 한다.
  • 데이터를 파티션 단위로 나눌 때 2가지 문제를 중요하게 따져야 한다.
    • 데이터를 고루 분배 할 수 있는가?
    • 노드가 추가되거나 삭제될 때 데이터 이동을 최소화할 수 있는가?
  • 안정 해시를 이용해서 해결할 수 있다. 그리고 아래와 같은 장점이 있다.
    • 규모 확장 자동화 (시스템 부화에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있다.)
    • 다양성 (각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다. 즉 고성능은 좀더 많이 가상 노드를 들고 있을수 있도록 조절 가능하다)

데이터 다중화

  • 높은 가용성과 안전성을 확보하기 위해서는 데이터를 다중화 해야 한다.
  • 안정해시 방법으로 시계방향으로 순회하면서 n개 서버에 데이터 사본을 저장하는 방식으로 할 수 있다. 하지만 가상 노드들이 존재함으로 같은 물리서버를 선택하지 않도록 해야 한다.
  • 같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있음으로 데이터의 사본은 다른 센터에 서버에 보관하고 고속 네트워크로 연결한다.

데이터 일관성

  • 정족수 합의 프로토콜을 이용하면 읽기/쓰기에 모두 일관성을 보장 가능
  • n=사본 개수, w=쓰기 연산에 대한 정족수를 의미하며 뜻하는 바는 쓰기 연산이 성공한 것으로 간주 될려면 적어도 w개의 서버로 부터 쓰기 연산이 성공했다는 응답을 받아야 한다. r=읽기 연산에 대한 정족수로 읽기 연산이 성공한 것으로 간주 되려면 적어도 r개의 서버로부터 응답을 받아야 한다는 의미이다.
  • w=1 의 뜻은 한대 서버에만 데이터를 쓴다는게 아니라 다중화된 여러 서버에 데이터를 쓰나 중재자가 성공 응답을 하나의 서버에서만 받으면 나머지 서버의 쓰기 연산 결과를 기다리지 않고 성공 처리 한다는 뜻이다.
  • N, W, R 다양한 구성 방법
    • r=1, w=n 빠른 읽기 연산에 최적화된 시스템
    • w=1, r=n 빠른 쓰기 연산에 최척화된 시스템
    • w+r>n 강한 일관성이 보장됨 (왜냐하면 최신 데이터를 가진 노드가 최소한 하나는 겹치기 때문에)
    • w+r<=n 강한 일관성이 보장되지 않음
일관성 모델 종류 (일관성 수준을 결정하게 위해서)
  • 강한 일관성
  • 약한 일관성
  • 최종 일관성 (약한 일관성의 한 형태로, 경신 결과가 결국에는 모든 동기화 되는 모델)
  • 강한 일관성을 달성하는 일반적인 방법은 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터의 읽기/쓰기를 금지하는것이다. 하지만 이는 고가용 시스템에 적절하지 않음
  • 현재 설계는 최종 일관성 모델을 택할것이고 병렬 쓰기연산 작업으로 인해 일관성이 깨질 수 있다.
비 일관성 해소 기법 - 데이터 버저닝
  • 데이터 다중화 되어 있는 상황에서 동시에 같은 값A를 서버 n1,n2에서 각각 (n1- A-> C, n2 - A -> D) 바꾼다면 충돌이 일어나게 된다.
    자세한 링크
    단점
  • 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다. (Last Write Wins (LWW) Conflict Resolution 과 같은 전술을 택할 수 도 있을듯)
  • [서버:버젼] 순서쌍 개수가 빨리 늘어난다는 것. 그래서 임계치를 설정하고 이 이상 늘어난다면 오래된 순서쌍을 벡터 시계에서 제거하도록 한다. 하지만 이렇게 하면 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지게 된다. (아마존 다이나모 디비에서는 동일한 방법을 적용했지만 문제가 된적은 없다.)

장애처리

대규모 시스템에서 장애는 흔하게 일어나는 사건이다. 그럼으로 장애 감지와 장애 해소 전략을 설명한다.

장애 감지
  • 분산 시스템에서 보통 두 대 이상의 서버가 똑같은 서버의 장애를 보고해야 장애 발생으로 간주한다.
  • 가장 쉬운 방법은 모든 노드 사이에 멀티 캐스팅 채널을 구축하고 정보를 전달 하는 방법이다. 하지만 이방법은 노드가 늘어나면 모든 노드에 메시지를 전달하는 방법으로 오버헤드가 늘어나 비효율적이다.
  • 가십 프로토콜 같은 분산형 장애 감지 솔루션 채택이 효율적이다.
    • 각 노드는 멤버십 목록을 유지하고 멤버십 목록은 각 멤버의 아이디와 박동 카운터를 가지고 있는다.
    • 각 노드는 주기적으로 자기 카운터만 증가시킨다.
    • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록 전부를 보낸다.
    • 박동 카운터 목록을 받은 노드는 박동 카운트를 최신 값으로 갱신한다.
    • 특정 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 장애로 간주한다.
일시적 장애 처리
  • 장애가 감지되면 엄격한 정족수 접근법을 쓴다면 읽기와 쓰기 연산 모드 금지
  • 장애가 감지되면 느슨한 정족수 접근법은 가용성을 높이기 위해 대신 쓰기나 읽기를 수행할 건강한 대체 서버를 골라 처리한다. 장애 서버가 복구되면 그동안 발생한 변경사항을 임시 서버로부터 복구 한다.
영구 장애 처리
  • 반 엔트로피 프로토콜을 구현하여 사본을 동기화 할 수 있다.
  • 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터 양이 적은 머클 트리를 사용한다.
데이터 센터 장애 처리
  • 정전, 네트워크, 자연재해 등 다양한 이유로 발생 가능
  • 데이터 센터 다중화를 해야 데이터 센터 장애에 대응 가능

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

  • 클라이언트는 get, put 이 두가지 api로 통신한다.
  • 중재자는 client와 키값 저장소 사이에서 proxy 역할을 한다.
  • 노드들은 안정 해시의 해시 링 위에 분포된다.
  • 노드를 자동으로 추가/삭제 할 수 있도록 시스템은 완전히 분산된다.
  • 데이터는 여러 노드에 다중화된다.
  • 모든 노드가 같은 책임을 가지고 있어 spof는 존재하지 않는다.

쓰기 경로 (카산드라를 예로)

  1. 쓰기 요청이 커밋 로그 파일 (disk)에 기록된다.
  2. 데이터가 메모리 캐시에 기록된다.
  3. 메모리가 가득 차거나 특정 임계치에 도달하면 SStable에 기록된다.(disk)

읽기 경로 (카산드라를 예로)

  1. 읽기 요청을 받으면 메모리에 데이터가 있는지 검사한다. 있으면 해당 데이터 return
  2. 메모리에 없으면 블룸 필터를 통해 키가 들어 있는 sstable를 찾는다.
  3. 특정 ssTable에서 데이터를 가져온다.
  4. 해당 데이터를 클라이언트에 반환한다.

질문

bloom filter

  • 특정원소가 있는지 없는지를 판단하는 확률형 자료구조
  • 실제로 존재하는 원소가 없다고 말하는 일은 없다(False Negative) 하지만 속하지 않은 원소가 있다고 말하는 경우는 있다.(False Positive)
  • 실제 값을 저장 하지 않음으로 해시 테이블에 비해 공간 효율이 매우 높다.
  • 원소 유뮤를 판단해야 하는 집합의 크기가 굉장히 크거나 원소의 크기가 너무 커서 원소가 집합에 속해있는지 정확히 판단하는데 시간이 오래 걸리는 경우 bloom filter를 통해 아예 속할 일이 없는 데이터를 미리 걸러낼 수 있다.
    • 모든 요청을 bloom filter 처리-> 걸러진 요청만 실제 데이터베이스에 정확하게 검사 -> 요청 부하를 줄어듬 (disk io를 줄이기 위한 최적화 방법으로 주로 사용)
  • 대표적인 사용처가 chrome으로 위험 사이트 검사
  • 자세한 자료구조 동작 원리
  • cassandera에서 bloom filter는 ssTable별로 관리되는 걸로 보인다.
  • cassandera에서 데이터를 읽는 흐름
  • reference

임식 위탁 기법 (hinted handoff)

  • cassandra 에서는 중재자(coordinator)가 local hint table에 응답하지 못하는 노드에 대한 쓰기 관한 hint를 저장한다.
  • gossiping을 통해 해당 노드가 다시 살아났다는걸 인지하면 local hint table 기반으로 데이터 싱크를 맞춰준다.
  • 하지만 일정 시간 이상 노드가 살아나지 않으면 hint table에 더이상 저장 하지 않는다.
    해당 링크

데이터가 다중화 되어 있는 상황에서도 서버 추가 삭제시 키 재배치가 쉽게 이루어지나?

정족수 합의 프로토콜

  • 강한 일관성을 보장(W+R>N)은 읽기와 쓰기가 순차적일때에 한정된다. 만약 읽기가 쓰기가 끝나지 않은 시점에 또는 일부 노드에만 끝난 시점에 발생한다면 일관성이 보장 되지않는다!
    해당 링크
  • 결국 완벽한 강한 일관성 달성하려면 결국엔 쓰기연산이 반영 될때까지 해당 데이터에 대한 읽기 쓰기를 금지하는것 뿐인것 같다... 정족수 합의는 일관성을 도달하게 도와주는 방법 정도? 아니면 또다른 전략으로 보완이 필요해 보니다..
  • 정족수 합의 프로토콜 쓰기나 읽기시 정해진 replica 서버에 대해서만 요청해야지 의미가 있어보인다..
  • 엄격한 정족수(strict quorum) vs 느슨한 정족수(sloppy quorum)
    • 위에서 언급한 일반적인 정족수 합의 프로토콜과 조금 다른듯하다.
    • 핵심은 정해진 정족수를 맞추지 못했을때 기존 replica node이외에 다른 node를 쓰기(hinted)나 읽기에 사용하냐 마냐 (사용해서 맞춘다면 느슨한 아니면 엄격한)
    • 고로 엄격한 정족수는 일시적 장애시로 replica node만으로 정해진 정족수를 못맞추면 읽기 쓰기 연산을 모두 금지해야 한다.

데이터 다중화하면 가용성이 왜 높아지지?

  • 오류난 서버의 데이터의 사본을 다른 서버가 들고 있음으로 특정 서버의 장애에도 항상 응답이 가능함으로..

반-엔트로피 프로토콜(Anti-Entropy)

  • 네트워크 단절에도 노드간에 데이터 동기화를 위해 싱크가 맞지 않는 데이터를 고치고 누락된 데이터를 복구하기 위해 사용됨

머클 트리

  • Anti-Entropy를 위해 사용되는 자료형식인듯하다.

  • 왜 머클 트리를 사용하면 전송 데이터 양이 줄어들까?

    1. 데이터 동일 검증을 위해 데이터를 전체 보내는게 아니라 해시된 값/머클 트리만 보내서 검증하면 되니까
    2. 특정 문제된 버킷만 동기화를 진행하면 되니까? 전체 데이터를 overwrite하는 것 보다는 전송양이 적을 거 같다..
  • 그 밖에도 다양한 사용처가 있다.

    • 블록체인(transaction 변조 여부 판단), fileSystem(데이터 무결성 검증), git
  • dynamo db의 경우 노드들이 데이터를 다중화 해서 가지고 있기 때문에 key-range별로 머클 트리를 따로 가지고 있다.그리고 복구나 비교시 공통으로 key-range를 가지고 있는 여러 노드들과 각각 개별적으로 데이터 동일 검증을 진행한다. 참고

  • reference

gossip protocol에 대한 추가 사항

  • protocol 사용시 항상 모든 노드는 멤버십 목록을 유지해야 하나? 아닌듯 하다 멤버십 목록을 유지하면 단점은 추가시 모든 노드에 멤버십 목록에 추가 해주어야 할것 같다. 그래서 모두 유지 하지는 않고 자기가 gossiping 하면서 가변적으로 추가하고 할 수 있는걸로 보인다.
  • seed 노드라는 개념을 두면 손쉽게 노드를 추가 할 수있다. 모든 노드가 seed node의 존재를 인지하고 seed랑 소통하도록 하면 노드가 추가된 상황에서도 별도 작업없이 추가된 노드의 정보가 퍼져나갈 것이다. 하지만 중간에 노드를 삭제에도 효과적일까? seed Node 자세한 설명
  • 책에 설명에 따르면 박동 카운터 목록 전부를 보낸다고 하는데 이때 시간도 다른 서버에서 보낸값으로 업데이트 해줘야 할까? 아닌듯하다 그렇다면 모든 노드가 같은 시간을 가지도록 서버 시간도 동기화 해줘야 할것 같다. 안그러면 offline 시간 계산시에도 각자 노드의 현재 시각이 다르다면 틀어질듯..
    고로 시각은 박동 카운터를 최신화 할때 마다 각자 서버의 로컬 시간을 기반으로 최신화 하는 구조로 보인다.
  • gossip protocol 말고도 Centralized, Tree-Based multicast 하는 방법도 존재 한다.자세한 설명

cap 이론 모순 및 부족한 점

  • 성능과 지연에 대한 설명이 없다. cap에의하면 30일이 지나서 응답이 와도 가용성이 있다고 볼 수 있다고 한다.
  • CAP 이론은 분산 시스템인 장애인 상황에 국한 된다. 즉 정상 상황일때에 대한 설명이 부족하다. 그래서 이론 보완하기 위한 개념 PACELC 등장 했다.
   
     (partition?) ---- p ---- (else)
       /  \                     /   \
     /     \                   /     \
    A       C                 L      C
  • PACELC는 네트워크 장애인 상황일때는 A(availability) 과 C(consistency)는 상충하고 정상인 상황에서는 L(latency) 과 C(consistency) 가 상충한다고 설명한다.
    링크1
    링크2
    링크3

0개의 댓글