키-값 저장소 설계

6장 키-값 저장소 설계

키-값 저장소란 비 관계형 데이터베이스를 말한다.

값은 키를 통해서 접근할 수 있고, 예를 들어 레디스, 아마존 다이나모가 있다.

 

---

 

단일 서버 키-값 저장소

1. 메모리에 해시 테이블로 저장하기

가장 직관적인 방법으로, 키-값 쌍을 모두 메모리에 해시 테이블로 저장하는 방법이다. 빠른 속도를 보장하지만, 모든 데이터를 메모리 안에 두는 것이 가능할까?

ㄴ 데이터 압축, 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장하는 개선 방법

ㄴ 그래도 한 대 서버로 부족한 때가 온다.

 

2. 분산 키-값 저장소 (분산 해시 테이블)

ㄴ 대규모 데이터를 저장하기 위해서 안정 해시를 사용해 서버들에 부하 분산

 

CAP 정리

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

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

- 파티션 감내(Partition tolerance): 두 노드 사이에 통신 장애가 발생하였더라도 시스템은 계속 동작해야한다.

 

=> C,A,P 중 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다

 

 

 

• CP 시스템: 일관성, 파티션 감내를 지원하고 가용성을 희생
• AP 시스템: 가용성과 파티션 감내를 지원하고 데이터 일관성을 희생
• CA 시스템: 일관성과 가용성을 지원하고 파티션 감내를 희생

그러나 네트워크 장애는 피할 수 없는 일로 여겨지므로, 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 그러므로 실세계에 CA 시스템은 존재하지 않느다.

 

이상적 상태에서의 분산 시스템

이상적 환경에서 네트워크가 파티션되는 상황은 절대로 일어나지 않는다.

n1에 기록된 데이터는 자동적으로 n2, n3에 복제되고, 데이터 일관성 & 가용성 만족

 

실세계의 분산 시스템

실시계의 분산 시스템은 파티션 문제를 피할 수 없다. n3 서버에 장애가 발생한다면, 클라이언트가 n1, n2에 쓰기 연산을 할 경우 n3에는 복제되지 않는다. 그러면 일관성과 가용성 사이에서 하나를 선택해야 한다. 이 때, 일관성을 선택한다면 쓰기 연산을 중단시켜야한다. (n1, n2에 쓰기 연산 시도 시 오류 반환) 가용성을 선택한다면, 낡은 데이터라도 계속 읽기 연산을 허용한다. (n1, n2에 쓰기 연산을 허용하고, 파티션 문제가 해결되면 데이터를 n3로 전송한다.)

시스템의 요구사항에 맞추어 결정하자

 

 

데이터 파티션

전체 데이터를 한 대 서버에 욱여넣는 것은 불가능하다. 따라서 데이터를 작은 파티션으로 분할한 다음 여러 서버에 저장해야 한다. 이 때 고려할 점은 다음과 같다.

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

5장에서 살펴본 안정 해시를 사용하면 좋다. 추가적으로 고려할 점은 다음과 같다.

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

데이터 다중화

가용성과 안정성을 확보하기 위해서 데이터를 N개 서버에 비동기적으로 다중화한다. 그러나 가상 노드를 사용하다보면 같은 물리 서버를 중복 선택할 수도 있기 때문에, 안정성을 답보하기 위해서 데이터의 사본을 다른 센터의 서버에 보관하고, 센터간 고속 네트워크로 연결해야한다.

 

데이터 일관성을 위한 정족수 합의 프로토콜

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

W,R이 1이라면, 1개의 서버만 성공 응답을 받으면 되기 때문에 응답속도는 매우 빠를 것이다. 그러나 데이터 일관성은 보장할 수 없다. W,R>1이라면 가장 느린 서버로부터의 응답을 기다려야 하므로 느려진다. 그러나 데이터 일관성 수준은 향상될 것이다.

시스템 요구사항에 따라, 빠른 읽기 연산이 필요하다면 R=1, W=N과 같이 정한다. 강한 일관성이 보장되는 시스템일 경우에는 W + R > N과 같이 정한다.

 

일관성 모델

데이터 일관성의 수준을 결정하는 일관성 모델에는 다양한 종류가 있다.

1. 강한 일관성
   • 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환다.
   • 모든 사본에 쓰기반영될 때까지 읽기/쓰기 금지
2. 약한 일관성
   • 일기 연산 시, 가장 최근에 갱신된 결과가 아닐 수도 있다.
3. 최종 일관성
   • 약한 일관성의 한 형태, 갱신 결과가 (나중에라도) 결국에는 모든 사본에 동기화 되는 모델
   • 클라이언트가 비전 정보를 활용해서 일관성이 깨진 데이터는 읽기 않도록 한다.
   • ex) 카산드라, 다이나모

최종 일관성 기법을 사용할 때, 비 일관성을 해소하기 위해 데이터 버저닝을 사용한다. 데이터가 변경될 때마다 새로운 버전을 만드는 방법이다. 여러 서버가 다른 버전의 데이터를 가지고 있다면 어떻게 일관성을 유지해야할까?

 

벡터시계

 

벡터 시계는 데이터 버저닝 사용 시 쓰기연산에 대한 가용성 보장하는 방법이다.

 

클라이언트는 D3와 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 된다. D2에서 Sy와 Sz서버에서 각기 다른 값으로 바뀌었기 때문이다. 따라서 클라이언트는 충돌을 감지하면 이를 해소한 후에 서버에 기록한다. 이를 Sx 서버에 기록한다면, D5([Sx, 3], [Sy, 1], [Sz, 1])로 기록한다.

 

• 장점
  • 어떤 버전이 선행 버전인지, 후행버전인지, 다른 버전과 충돌이 있는 지 판별 가능하다.
  • 동일 서버 구성요소보다 작은 값이 있는 지 보면 충돌이 있는 지 알 수 있다.
• 단점
  • 충돌 감지 및 해소 로직이 클라이언트에 들어가야하므로, 클라이언트 구현이 복잡해진다
  • 순서쌍 개수가 굉장히 빨리 늘어나고, 임계치를 설정하여 오래된 순서쌍을 벡터 시계에서 제거하도록 해야한다. 그러나 삭제하다보면 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 효율성이 낮아진다. (그러나 아마존은 그런 문제가 벌어지는 것을 발견한 적이 없다고 한다)

장애 감지

• 두 대 이상의 서버가 서버 A의 장애를 보고해야 실제 장애가 발생했다고 간주한다.
  • 서버간의 장애를 전파하기 위한 멀티캐스팅 채널을 구축해야하는 데, 이를 모든 서버 사이에 구축하는 것은 비효율적이다.
• 가십 프로토콜 (gossip protocol) 
  • 위 문제를 해결하기 위한 분산형 장애 감지 솔루션 
  • 각 노드는 멤버십 목록을 가진다. 멤버십 목록이란 각 멤버 ID와 박동 카운터 쌍(heartbeat counter)의 목록이다. 
  • 각 노드는 자기 박동 카운터를 주기적으로 증가시키고, 멤버십 목록을 갱신한다.
  • 만약 어떤 멤버가 특정 시간동안 카운터가 갱신되지 않으면 장애상태인것으로 간주하다.

일시적 장애 처리

• 엄격한 정족수 접근법 : 장애를 감지하면, 데이터 일관성을 위해 읽기와 쓰기 연산을 금지한다.
• 느슨한 정족수 접근법 : 데이터 정족수 조건을 완화하여 가용성을 높인다. 장애 상태인 서버를 무시하고, 쓰기 연산 수행할 W개의 건강한 서버를 해시 링에서 고른다.
  • 장애로 가는 요청은 다른 서버가 잠시 맡아서 처리하고, 복구 되었을 때 일괄 반영하여 일관성을 보존한다.

영구 장애 처리

• 영구적인 노드의 장애 상태 처리
• 반-엔트로피 프로토콜
  • 머클 트리, 버킷 별로 해시값을 계산하여 이진 트리 형식으로 구성해나간다.
  • 루트 노드의 해시값을 비교하는 것으로 두 서버가 같은 데이터를 갖는 것인지 파악할 수 있다.
  • 동기화해야하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해진다.
  • 실제로 구성하다보면 하나의 버킷은 1000개의 키를 관리하게 되는 꽤 큰 크기

 

최종적인 시스템 아키텍처 다이어그램

• 클라이언트는 API와 통신한다
• 중재자는 클라이언트에게 키-값 저장소에 대한 proxy 역할을 한다.
• 노드는 안정 해시의 해시 링 위에 분포한다.
• 노드는 자동 추가/삭제될 수 있도록 완전히 분산된다
• 데이터는 여러 노드에 다중화한다.
• 모든 노드가 같은 책임을 지므로, no single point of failure
• 완전히 분산된 설게를 채택했으므로, 각 노드는 다중화, 데이터 충돌 해소, 장애 감지 등의 기능을 모두 지원해야한다.
• 서버에서는 캐시 요청이 오면 메모리 캐시에 기록하고, 메모리 캐시가 가득차거나 임계치에 도달하면 디스크에 있는 SSTable에 기록된다.
• 읽기 요청이 오면 메모리 캐시에 있는 지 확인해보고, 없을 경우 bloom filter를 사용해서 어떤 SSTable에 키가 보관되어있는 지 알아낸 후가 반환한다.

 

* 대규모 시스템 설계 기초 6장을 참고하여 정리한 글입니다