책 읽어보고 재잘재잘/대규모 시스템 설계 기초1

키-값 저장소 설계

띠리링구 2024. 3. 1. 12:38

문제 이해 및 설계 범위 확정

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

 

단일 서버 키-값 저장소

한 대의 서버만 사용하는 저장소는 설계하기 매우 쉽다.

가장 직관적이고 쉬운 방법은 그냥 메모리에 해시 테이블로 모든 키-값 쌍을 저장하는 것.

하지만 이렇게 하면 모든 데이터를 메모리 안에 두기엔 저장공간이 부족할 수 있다.

 

개선책

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

그러나 이렇게 해도 한 대의 서버로 부족한 순간이 찾아온다.

많은 데이터를 저장하려면 분산 키-값 저장소를 만들어야 한다.

 

분산 키-값 저장소

= 분산 해시 테이블

 

* CAP 정리 (Consistency, Availability, Partition Tolerance theorem)

데이터 일관성, 가용성, 파티션 감내성 세 가지 요구사항을 동시에 만족하는 분산 시스템은 없다.

 

데이터 일관성 : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계 없이 언제나 같은 데이터를 보게 되어야 한다.

가용성 : 분산 시스템에 접속하는 클라이언트느 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.

파티션 감내 : 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야함을 의미한다.

 

CAP정리는 이 중 두 가지를 충족하려면 나머지 하나는 버려야 하는 것을 의미한다.

CP 시스템 : 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성(A)을 희생.

AP 시스템 : 가용성과 파티션 감내를 지원하는 키-값 저장소. 일관성(C)을 희생.

CA 시스템 : 일관성과 가용성을 지원하는 키-값 저장소. 현실세계에서 파티션은 반드시 발생하므로 CA시스템은 실무에서 설계하지 않는다.

 

금융권에서는 보통 일관성을 포기할 수 없어 CP 시스템

 

핵심 컴포넌트들 및 기술들

데이터 파티션

consistent hash를 이용해 서버를 해시 링에 배치.

데이터 다중화

consistent hash ring에서 서로 다른 N개의 노드에 데이터 사본을 저장.

단, 가상 노드들이 모두 다른 데이터 센터의 노드들이어야 함.

데이터 일관성

* 정족수 합의(Quorum Consensus) 프로토콜

N = 사본수

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

R = 읽기 연산에 대한 정족수.

 

이것으로 일관성 수준 조절 가능

1. R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템

2. W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템

3. W + R > N : 강한 일관성이 보장됨

4. W + R < N : 강한 일관성이 보장되지 않음

 

일관성 모델

강한 일관성 (Strong Consistency) : 모든 읽기 연산이 최근에 갱신된 결과를 반환. 클라이언트는 절대 낡은 데이터를 보지 못함.

약한 일관성 (Weak Consistency) : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.

 

결과적 일관성 (Eventual Consistency) : 약한 일관성의 한 형태. 갱신 결과가 결국에는 모든 사본에 반영되는 모델.

 

강한 일관성을 달성하려면 모든 사본에 쓰기 연산의 결과가 반영되기까지 해당 데이터에 대한 읽기/쓰기 금지. 하지만 고가용성 시스템엔 적합하지 않음. 다이나모나 카산드라는 결과적 일관성 채택. 결과적 일관성을 채택하면 일관성이 깨지는 경우가 생기는데 이문제는 클라이언트가 해결해야 함.

 

비 일관성 해소 기법 : 데이터 버저닝 (벡터시계)

벡터시계는 D([S1,v1], [S2,v2] ... )와 같이 표현한다고 가정.

D는 데이터이고 vi는 버전카운터, Si는 서버 번호.

D를 서버 Si에 기록하려면 시스템은 아래 작업 가운데 하나를 수행

  • [Si, vi]가 있으면 vi를 증가시킴
  • 그렇지 않으면 [Si, 1]을 만듬

한 데이터에 대한 두 개의 벡터시계가 있을 때

벡터시계A의 모든 vi가 벡터시계B의 모든 vi보다 작으면 A는 B보다 오래된 데이터

어떤 vi는 A가 더크고 어떤 vi는 B가 더 크다면 충돌이 발생한 것.

 

단점 : 충돌 감지 및 해소 로직이 클라이언트에 들어가야함.

단점2 : 서버-버전 순서쌍 개수가 빠르게 늘어남. threshold를 설정하고 이보다 순서쌍이 길어지면 오래된 순서쌍을 삭제해서 해결 가능. 이것때문에 선후관계가 불분명해지는일을 발견한적은 없다고 함.(Amazon)

 

장애감지

분산 시스템에서는 여러 대의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 장애가 발생함으로 간주.

 

가십 프로토콜

각 노드는 멤버십 리스트를 가지고 자기의 heartbeat를 갱신.

무작위로 여러 노드들에게 주기적으로 자기의 heartbeat를 보냄.

heartbeat를 받은 노드들은 최신값으로 갱신.

어떤 멤버의 heartbeat가 일정시간 이상 갱신되지 않으면 장애 상태로 간주.

 

일시적 장애처리

엄격한 정족수(strict quorum) vs 느슨한 정족수(sloppy quorum)

 

strict : 읽기와 쓰기 연산 금지

sloppy : 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버 고르기. 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아서 처리하고 장애가 복구되면 일괄 반영.

 

영구 장애처리

머클(Merkle)트리를 이용해 사본 사이에 일관성이 망가진 상태를 탐지하고 갱신.

각 노드를 해시하고 해시한 노드들을 해시해 부모노드에 해시값을 저장하는식으로 쌓아올려가면

나중에 루트노드의 해시값만 비교해도 두 사본의 일관성이 깨진지 알 수 있음.

 

데이터 센터 장애처리

여러 데이터 센터에 데이터를 다중화.

 

시스템 아키텍처

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

즉 모든 노드가 클라이언트API, 장애감지, 데이터 충돌 해소, 장애 복구 메커니즘, 다중화, 저장소 엔진 등을 모두 갖고있어야함.

 

쓰기

카산드라의 사례 참고.

1. 쓰기 요청은 커밋로그 파일에 기록됨.

2. 데이터가 메모리 캐시에 기록됨.

3. 메모리 캐시가 임계치에 도달하면 데이터는 디스크에 있는 Sorted String Table에 기록됨.

 

읽기

1. 메모리 캐시에 데이터가 있으면 바로 반환

2. 없으면 블룸필터를 검사해 어떤 SSTable에 키가 있는지 알아냄.

3. SSTable에서 데이터를 가져와 클라이언트에게 반환