가상 면접 사례로 배우는 대규모 시스템 설계 기초 Study [6장] 키-값 저장소 설계

키 값 저장소

• 키-값 데이터베이스라고도 하며 비 관계형 데이터베이스이다.
• 고유 식별자identifier를 키로 설정하며 키는 유일해야하고 키에 매달린 값은 키를 통해서만 접근 가능하다.
• 키는 짧을 수록 좋다.
• 값은 문자열, 리스트, 객체 등 어떤 값이 오든 상관없다.
• 아마존 다이나모, memcached, 레디스 등

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

읽기, 쓰기 그리고 메모리 사용량 사이 균형을 찾고 데이터 일관성과 가용성 사이에 타협점을 찾는 설계를 한다

• 키-값 쌍의 크기를 정한다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성 제공해야 한다.
• 높은 규모 확장성을 제공
• 데이터의 이로간성
• 응답 지연시간이 짧아야 한다.

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

• 가장 직관적인 방법은 키-값 쌍 전부를 메모리 해시 테이블로 저장
• 빠른 속도를 보장하나 모든 데이터를 메모리에 두는 것은 불가능
• 해결 방안
  • 데이터 압축compression
  • 자주 쓰는 데이터만 메모리에 두고 나머지는 디스크에 저장

3. 분산 키-값 저장소

• 분산 해시 테이블
• 분산 시스템 설계시 CAP 정리Consistency, Availability, Partition Tolerance theorem를 이해해야 함

3.1 CAP 정리

아래의 세가지 요구사항을 동시에 만족하는 분산 시스템 설계는 불가능하다.

• 일관성consistency : 분산 시스템에 접속하는 모든 클라이언트는 언제가 같은 데이터를 보아야 한다.
• 가용성availability : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내partition tolerance : 파티션은 두 노드 사이에 통신 장애가 발생함을 의미. 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다.

• CP 시스템
  일관성과 파티션 감내를 지원. 가용성을 희생
• AP 시스템
  가용성과 파티션 감내를 지원. 데이터 일관성을 희생
• CA 시스템
  일관성과 가용성을 지원. 파티션 감내는 지원하지 않는다. 네트워크 장애는 피할 수 없는 문제이므로 파티션 문제를 감내할 수 있도록 설계는 반드시 필요하다. (실세계에서는 존재하지 않음)

3.1.1 실세계의 분산 시스템

• 분산 시스템에서 파티션 문제는 피할 수 없으며 파티션 문제가 발생하면 우리는 일관성과 가용성 사이에 하나를 선택해야 한다.

  

CP 시스템(일관성)

• 세 서버 사이에 데이터 불일치 문제를 피하기 위해 n1, n2 쓰기 연산을 중단
• 가용성 깨짐
• 은행권 시스템등에서는 데이터 일관성이 중요

AP 시스템(가용성)

• 오래된 데이터를 반환하더라도 계속 읽기 연산을 허용
• n1, n2는 계속 쓰기 연산을 허용
• 파티션 문제 해결 후 n3에 새로운 데이터를 전송하여 동기화

3.1.2 컴포넌트

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

3.1.2 데이터 파이션

• 데이터를 작은 파티션으로 분할한 다음 여러대 서버에 저장한다.
• 데이터를 고르게 분산할 수 있는지 노드가 추가 및 삭제 되었을 때 데이터의 이동을 최소화 할 수 있는가

안정 해시를 사용하여 좋은점

• 규모 확정 자동화automatic scaling : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제
• 다양성heterogeneity : 각 서버 용량에 맞게 가상 노드의 수를 조정한다. 고성능 서버는 더 많은 가상 서버를 갖도록 설정 가능

3.1.3 데이터 다중화

• 높은 가용성과 안정성을 확보하기위해서는 데이터를 N개 서버에 비동기적으로 다중화replication할 필요가 있다.

3.1.4 데이터 일관성

• 여러 노드에 다중화 된 데이터는 적절히 동기화 되어야 한다.
• 정족수 합의Quorum Consensus 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.

• 중재자coordinator는 최소 한대 서버로부터 쓰기 응답을 받아야 한다는 뜻
• s1으로부터 성공 응답을 받았다면 s0, s2로 부터 응답은 기다릴 필요가 없다.
• 중재자는 클라이언트와 노드 사이에 프락시 역할을 한다.
• W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 전형적인 과정

N, W, R 값을 결정하는 방법

요구되는 일관성 수준에 따라 각각의 값을 정하면 된다.

• R=1, W=N : 빠른 읽기 연산에 최적화
• W=1, R=N : 빠른 쓰기 연산에 최적화
• W+R > N : 강한 일관성이 보장됨
• W+R <= N : 강한 일관성이 보장되지 않음

일관성 모델

• 키-값 저장소를 설계할 때 고려해야할 또 다른 요소
• 강한 일관성strong consistency : 모든 읽기 연산은 최근에 갱신된 결과를 반환. 오래된out of date 데이터는 보지 못함
• 약한 일관성weak consistency : 읽기 연산은 최근에 갱신된 결과를 반환하지 못할 수 있음
• 결과적 일관성eventual consistency : 약한 일관성의 한 형태 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화) 되는 모델
• 강한 일관성을 유지하기 위해서는 모든 사본에 현재 쓰기 연산의 결과가 반영될 때 까지 해당 데이터에 대한 읽기/쓰기를 금지 -> 고가용성 시스템에는 적합하지 못함
• 다이나모 또는 카산드라 같은 경우 결과적 일관성 모델을 선택
  • 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있다.
  • 일관성이 깨지는 문제는 클라이언트가 해결해야 한다.

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

• 버저닝versioning과 벡터시계vector colock는 사본 간 일관성이 깨지는 문제를 해소화하기 위해 등장한 기술
• 버저닝은 데이터를 변경할 때 마다 해당 데이터 새로운 버전 생성한다. 각 버전은 변경 불가능immutable
• 두 버전간 충돌을 발견하고 자동으로 해결해내기 위해 베터 시계가 보편적으로 사용되는 기술
• 벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것이며 어떤 버전이 선행 혹은 후행인지 충돌이 있는지 판별

구체적인 사례

1. 클라이언트가 데이터 D1 기록. 쓰기연산을 Sx가 처리 : D1[Sx, 1]
2. 다른 클라이언트가 D1을 읽고 D2로 업데이트 Sx를 통해 기록. : D2[Sx, 2]
3. 다른 클라이언트가 D2을 읽고 D3로 업데이트 Sy를 통해 기록. : D3[Sx, 2][Sy, 1]
4. 또 다른 클라이언트가 D2를 읽고 D4로 업데이트 Sz를 통해 기록. : D4[Sx, 2][Sz, 1]
5. 어떤 클라이언트가 D3, D4를 읽으면 데이터 간 출돌이 있다는 것을 알게됨. 충돌은 클라이언트가 해소 후 Sx을 통해 기록. : D5[Sx, 3][Sy, 1][Sz, 1]

벡터 시계의 단점

• 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로 클라이언트는 구성이 복잡
• 순서쌍 개수가 굉장히 빨리 늘어남. 이를 해소하기 위해서는 임계치를 설정하고 임계치 이상으로 길어지면 오래된 순서쌍을 벡터 시계에 제거

장애 감지failure detection

• 모든 노드 사이에 멀티 캐스팅multicasting채널을 구축하는 것이 손쉬운 방법이지만 서버가 많은때는 비효율적
• 가십 프로토콜gossip protocol 같은 분산형 장애 감지decentralized failure detection 솔루션을 채택하는 것이 효율적

가십프로토콜의 동작 원리

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

일시적 장애 처리

• 가십 프로토콜로 장애를 감지한 시스템은 가용성 보장을 위해 필요한 조치를 해야 한다.
• 엄격한 정족수strict quorum 접근법을 쓴다면 앞서 데이터 일관성 절에서 설명한 대로 읽기와 쓰기 연산을 금지
• 느슨한 정족수sloppy quorum 접근법은 조건을 완하하여 가용성을 높인다.
  • 임시 위탁hinted handoff 기법
  • 정족수 요구성을 강제 대신 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 R개의 건강한 서버를 해시 링에서 고른다.
  • 네트워크 문제로 장애 상태인 서버는 다른 서버가 잠시 맡아 처리
  • 해당 서버가 복구되었을 때 일관성을 반영하여 데이터 일관성을 보존한다.
  • 임시로 쓰기 연산을 처리한 서버에는 단서hint를 남겨둔다

영구적인 장애 처리

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

머클 트리

• 노드에 그 자식 노드들에 보관된 해시(자식 노드가 종단 노드일 경우), 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙이는 트리
• 대규모 자료구조 내용을 효과적이면서 보안상 안전한 방법으로 검증 가능
• 두 머클 트리의 비교는 루트 노드의 해시값을 비교하는 것을 시작으로 왼쪽 자식 노드의 해시값을 비교 그 다음 오른쪽 해시값을 비교하여 아래쪽으로 탐색하여 비교한다.
• 아래쪽으로 탐색하다가 다른 데이터를 갖는 버킷을 찾을 수 있으므로 그 버킷만 동기화 하면 된다.

데이터 센터 장애 처리

• 데이터 센터 장애에 대응할 수 있는 시스템을 만들려면 데이터를 여러 데이터 센터에 다중화 하는 것이 중요

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

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

  

쓰기 경로

1. 쓰기 요청이 커밋 로그 파일에 기록
2. 데이터가 메모리 캐시에 기록
3. 메모리 캐시가 가득차거나 임계치에 도달하면 데이터는 디스크에있는 SSTable에 기록

• SSTable은 Sorted-String Table의 약어로 <키, 값>의 순서쌍을 정렬된 리스트 형태로 관리

읽기 경로

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