[CH6] 키-값 저장소 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

📢 키-값 저장소 : 고유 식별자 키에 매칭되는 값의 키-값 쌍(pair) 구조의 비 관계형 데이터베이스

• 키는 유일하며, 키를 통해서만 값에 접근할 수 있다.
  • 키는 텍스트 또는 해시 값
  • 키가 짧을 수록 성능 상 좋다

1️⃣ 문제 이해 및 설계 범위 확정

🤔 이런 요소들을 고민해보기

• 읽기, 쓰기, 메모리 사용량 사이에서 균형 찾기
• 데이터 일관성과 가용성 사이에서 타협적 결정 내리기
• Ex. 이런 특성을 고민해보자~~
  • 키-값 쌍의 크기
  • 큰 데이터 저장 가능
  • 높은 가용성 :: 장애 있어도 빠른 응답 가능
  • 높은 규모 확장성 :: 트래픽 양에 따라 자동으로 서버 증설/삭제 가능
  • 데이터 일관성 수준 조정 가능
  • 응답 지연 시간

✨ 단일 서버 키-값 저장소

• 키-값 쌍 모두를 메모리에 해시 테이블로 저장한다
  • 가장 직관적이고 빠르지만 모든 데이터를 메모리 안에 두는 것이 불가능 할 수 있다.
  • 이를 해결하기 위해 데이터 압축, 자주 쓰이는 데이터만 메모리에 저장하는 등의 방식을 사용한다.
• 하지만 한 대 서버로 부족하게 된다면? 분산 저장소를 만들어야 한다.

---

2️⃣ 분산 키-값 저장소 설계

📢 = 분산 해시 테이블 : 키-값 쌍을 여러 서버에 분산시킨다.

📍 CAP 정리

• 데이터 일관성, 가용성, 파티션 감내의 세 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다.
  • 데이터 일관성 (consistency): 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐와 관계 없이 언제나 같은 데이터를 보게 되어야 한다.
  • 가용성 (availability) : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생해도 항상 응답을 받을 수 있어야 한다.
  • 파티션 감내 (partition tolerance) : 파티션은 두 노드 사이에 통신 장애가 발생했음을 알린다. 따라서 파티션 감내는 파티션이 생겨도 시스템은 계속 동작해야 한다는 의미!

• 키-값 저장소의 분류
  • CP 시스템 : 일관성과 파티션 감내를 지원. 가용성 희생
    • 서버 A, B, C에서 C가 죽은 순간부터 서버에 읽기/쓰기 불가능
      • 일관성 = 언제, 무슨 일이 있어도 각 서버에 있는 모든 데이터가 동기화 됨’을 보장하겠다
      • 따라서 C가 죽은 순간, 데이터 일관성을 유지할 수 없으니 서버는 에러를 보낸다.
  • AP 시스템 : 가용성과 파티션 감내 지원, 데이터 일관성 희생
    • 서버 A, B, C에서 C가 죽은 순간 서버에 연산은 가능
      • 서버가 요청에 대해 ‘사용 가능’한 상태
      • 그러나 일관성을 희생했으므로, 서버에 저장된 데이터는 조금씩 다르다
      • 서버는 변경사항을 임시로 들고, 파티션 문제가 해결되면 데이터 동기화를 진행한다 = 어느 특정 시점에서 데이터 불일치 가능
  • CA 시스템 : 일관성과 가용성 지원, 파티션 감내 희생
    • 단, 통상 네트워크 장애는 피할 수 없는 문제! 분산 시스템은 반드시 파티션 이슈를 감내할 수 있어야 한다.
    • 따라서 개념상으로만 존재하지, 실세계에는 존재 X

📍 분산 시스템 데이터 보관 예시

• 세 대의 복제 (replica) 노드 n1, n2, n3에 데이터를 복제해서 보관하는 케이스를 가정
  • 이상적 상태
    • 네트워크 파티션? 응 절대 안일어나~
    • n1에 있는 데이터는 n2, n3에 자동으로 복제 → 일관성, 가용성 만족
  • 실세계의 분산 시스템
    • 네트워크 파티션? 응 절대 일어나~
      • 파티션 발생 시, 일관성과 가용성 둘 중 하나를 선택해야 한다.
    • Ex. n3가 죽어서 n1, n2와 통신할 수 없는 상황
      • CP 시스템 : 데이터 일관성을 위해 n1, n2에 대해 쓰기 연산 중단!
      • AP 시스템 : 시스템 가용성을 위해 n1, n2에 쓰기 연산 허용, 파티션 문제 해결 후 새 데이터를 n3에 전송!

📍 시스템 컴포넌트

📢 키-값 저장소 구현에 사용될 핵심 컴포넌트들

데이터 파티션

• 대규모 서비스의 경우, 데이터를 작은 파티션으로 분할한 다음 여러 대의 서버에 저장한다.
• 데이터를 파티션 단위로 나눌 때는 아래를 고려한다
  • 데이터를 여러 서버에 고르게 분산할 수 있는가?
  • 노드가 추가되거나 삭제될 때 데이터 이동을 최소화할 수 있는가?
• 안정 해시를 이용해 데이터를 파티션하면 이런 점이 좋다
  • 규모 확장 자동화 (automatic scaling) : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제
  • 다양성 (heterogeneity) : 각 서버 용량에 맞게 가상 노드 수를 조정할 수 있다 (= 고성능 서버는 더 많은 가상 노드)
    

데이터 다중화 (replication)

• 목적 : 높은 가용성과 안정성을 확보하기 위함
• 방법 : 데이터를 N개 (튜닝 가능한 값) 서버에 비동기적으로 다중화
  • N개 서버 선정 과정
    • 어떤 키를 해시 링 위에 배치 → 거기서부터 시계방향으로 링 순회하다 만나는 첫 N개 서버에 데이터 사본 보관
• 문제 : 가상 노드 사용 시, 선택한 N개 노드가 대응될 실제 물리 서버 개수가 N보다 작아질 수 있다.
• 해결 : 노드 선택 시 같은 물리 서버 중복 선택하지 않게 처리한다.
• 기타 문제 : 데이터 센터는 물리적 (정전, 자연재해 등) 문제를 겪을 수 있으니, 안정성을 위해 데이터 사본을 다른 데이터 센터 서버에 보관하고, 센터들은 고속 네트워크로 연결한다.

일관성 (consistency)

• 여러 노드에 다중화된 데이터는 적절한 동기화가 필요하다.
• 정족수 합의 프로토콜 (Quorum Consensus)
  • 읽기/쓰기 연산 모두에 일관성 보장 가능
  • 관계 정의
    • N = 사본 개수
    • W = 쓰기 연산에 대한 정족수
      :: 쓰기 연산 성공 = 중재자는 W개의 서버로부터 쓰기 연산 성공 응답 받아야 함
    • R = 읽기 연산에 대한 정족수
      :: 읽기 연산 성공 = 중재자는 R개의 서버로부터 응답 받아야 함
  • 면접에서 N, W, R 정하기
    • W = 1, R = N : 빠른 쓰기 연산에 최적화
      • 중재자는 클라이언트와 노드 사이에서 프록시 역할 수행
    • W = N, R = 1 : 빠른 읽기 연산에 최적화
      • 중재자는 한 대 서버의 응답만 받으면 됨 :: 응답속도 굿
    • W 또는 R이 1보다 큰 경우
      • 시스템의 데이터 일관성은 향상
      • 중재자 응답 속도는 느려짐 :: 가장 느린 서버로부터의 응답 기다려야 함
    • W + R > N : 강한 일관성 보장
      • 보통 N = 3, W = R = 2
    • W + R ≤ N : 강한 일관성 보장 X
• 일관성 모델 (consistency model)
  • 데이터 일관성의 수준을 결정한다.
  • 종류
    • 강한 일관성 (strong consistency)
      • 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
      • 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기 금지해서 달성
      • 새로운 요청의 처리가 중단되기 때문에, 고가용성 시스템에 적합 X
    • 약한 일관성 (weak consistency)
      • 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
    • 최종 일관성 (eventual consistency)
      • 약한 일관성의 한 형태
      • 갱신 결과가 결국에는 모든 사본에 반영 (=동기화) 된다.
      • 쓰기 연산이 병렬적으로 발생할 경우, 시스템에 저장된 값의 일관성이 깨질 수 있다.
        • 클라이언트가 직접 데이터 버전 정보를 이용해, 일관성이 깨진 데이터를 읽기 않게 처리한다.
          ⇒ 비일관성 해소 기법 사용

일관성 불일치 해소 (inconsistency resolution)

• 데이터 다중화 :: 가용성은 높아져도, 사본 간 일관성 깨질 가능성 높아짐
• 해결
  • 버저닝 (versioning) : 데이터 변경할 때마다 새로운 버전 생성
    • 각 버전의 데이터는 변경 불가능 (immutable)
  • 벡터 시계 (vector clock) : 버저닝에서 두 버전 사이의 충돌 해소
    • 동작 방식
      • [ 서버, 버전 ]의 순서쌍을 데이터에 맵핑
        • 어떤 버전이 선행인지, 후행인지, 다른 버전과 충돌이 있는지 판별하는데 사용!
      • 데이터 D를 서버 Si에 기록한다고 할 때, 시스템은 아래 작업 수행
        • [ Si, vi ] 가 있으면 버전 카운터 vi를 증가시킨다.
        • 그렇지 않으면 새 항목 [ Si, 1 ] 을 만든다.
    • 장점
      • 어떤 버전 X가 버전 Y의 이전 버전인지 (따라서 충돌이 없는지) 쉽게 판단 가능!
      • 버전 Y에 포함된 모든 구성 요소 값이 X에 포함된 모든 구성 요소 값보다 같거나 큰지만 체크하면 된다.
    • 단점
      • 충돌 감지 및 해소 로직이 클라이언트단에 추가 :: 클라이언트 구현 복잡
      • [서버:버전] 순서쌍 개수가 빠르게 증가
        • 길이에 임계치 정하고, 임계치 초과할 때 오래된 순서쌍을 벡터 시계에서 제거해야 한다.
        • 단, 이 경우 버전 간 선후 관계가 정확하게 결정될 수 없어 충돌 해소 효율성이 낮아진다.
          • Amazon dynamoDB말로는 이런 적이 없다고 하니, 사실상 안전한 솔루션이긴 하다. 참고만..!

장애 처리

• 장애 감지 (failure detectinon)
  • 분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 특정 서버의 장애를 보고해야, 해당 서버에 실제로 장애가 발생했다고 간주한다.
  • 서버 적을 때
    • 모든 노드 사이에 멀티캐스팅 (multicasting) 채널을 구축해 서버 장애 감지
  • 서버 많을 때
    • 분산형 장애 감지 (decentrallized failure detectino) 솔루션 사용
      • Ex. 가십 프로토콜 (gossip protocol)
        • 각 노드는 멤버십 목록을 유지 :: 멤버십 목록 = 각 멤버 ID와 박동 카운터 (heartbeat counter) 쌍 목록
          • 각 노드는 주기적으로 자신의 박동 카운터를 증가
          • 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다
          • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
          • 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않는다면? → 해당 멤버는 장애 상태인 것으로 간주
• 장애 해소 (failure resolution)
  • 일시적 장애 처리
    • 가십 프로토콜로 장애 감지 → 가용성 보장을 위해 조치
      • 엄격한 정족수 (strict quorum) 접근 : 읽기, 쓰기 연산 금지
      • 느슨한 정족수 (sloppy quorum) 접근 : 임시 위탁 (hinted handoff)
        1. 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. (장애 서버 무시)
        2. 장애 서버로 가는 요청은 위에서 고른 서버들이 맡아 처리한다.
        3. 변경사항들은 장애 서버가 복구되었을 때 일괄 반영해 데이터 일관성을 보존한다. 이를 위해 임시 쓰기 연산 처리 서버는 단서 (hint)를 남긴다.
  • 영구적 장애 처리
    • 반-엔트로피 (anti-entropy) 프로토콜을 이용해 사본 동기화
      • 사본들을 비교해 최신 버전으로 갱신
      • 사본 간의 일관성이 망가진 상태 탐지 → 전송 데이터 양을 줄이기 위해 머클 트리 사용 (Merkle)
        • 머클 트리 = 해시 트리
          • 각 노드에 그 자식 노드들에 보관된 값의 해시 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리
          • 대규모 자료 구조의 내용을 효과적이고 안전하게 검증 가능
          • 동기화해야 하는 데이터의 양은 존재하는 차이 크기에 비례하지, 두 서버에 보관된 데이터 총량과는 무관하다.
          • 단, 실제 시스템의 경우 버킷 크기가 크다는 것 참고
  • 데이터 센터 장애 처리
    • 데이터를 여러 데이터 센터에 다중화하자!
      

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

• 아키텍처의 주된 기능 예시
  • 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, get과 put와 통신한다.
  • 중재자 (coordinator)는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드다.
  • 노드는 안정 해시의 해시 링 위에 분포한다.
  • 노드를 자동으로 추가 또는 삭제할 수 있게 시스템은 완전히 분산된다.
  • 데이터는 여러 노드에 다중화된다.
  • 모든 노드가 같은 책임을 지므로, SPOP (Single Point of Failure)는 존재하지 않는다.
    

쓰기 경로 (write path)

• 쓰기 요청이 특정 노드에게 전달되었을 때 벌어지는 일
  • 카산드라 구조 참고
    • 쓰기 요청이 커밋 로그 파일에 기록
    • 데이터가 메모리 캐시에 기록
    • 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.
      

읽기 경로 (read path)

• 읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핀다.
  • 있으면 해당 데이터를 클라에게 반환
  • 없으면 디스크에서 가져온다
    • 어느 SSTable에 있는지 알아내기 위해 블룸 필터 (Bloom filter) 등을 사용한다.
      

---

3️⃣ 요약

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

[230204] 노션 -> 벨로그 이동 :: 가독성 개선 예정 😇